操作系统

引论

定义

  • os是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充
  • 主要作用提高利用率并为用户和应用程序提供一个简单的接口，便于用户使用
  • 大量的应用软件，都直接依赖于操作系统的支持，取得它所提供的服务

os的目标

  • 方便性
  • 有效性
  • 可扩充性
  • 开放性

os的作用

  • 作为用户和计算机硬件系统之间的接口
  • 作为计算机系统资源的管理者，资源分为【处理机、存储器、IO设备、文件（数据和程序）】
  • 实现了对计算机资源的抽象

操作系统的特征

基本特征

  • 并发
  • 共享
  • 虚拟
  • 异步

主要功能

处理机管理功能

  • 进程控制
  • 进程同步
  • 进程通信
  • 调度

存储器管理功能

  • 内存分配
  • 内存保护
  • 地址映射
  • 内存扩充

设备管理功能

  • 缓冲管理
  • 设备分配
  • 设备处理

文件管理功能

  • 文件存储空间管理
  • 目录管理
  • 文件读写管理和保护

os和用户之间的接口

  • 用户接口
  • 程序接口

进程的描述和控制

程序

顺序执行时的特征

  • 顺序性
  • 封闭性
  • 可再现性

并发执行的特征

  • 间断性
  • 失去封闭性
  • 不可再现性

进程和程序的区别

进程 程序
动态 静态
是程序的执行 是有序代码的集合
独立的运行单位，能与其他的进程并发执行 而程序不行
暂时的 永久的
进程的组成包括：程序段、数据块、进程控制块（PCB）

进程

定义：进程是进程实体的运行过程，是系统进行分资源分配和调度的一个独立单位

特征：

  • 动态性【【由创建而产生，由调度而执行，因得不到资源的阻塞，由撤销而消亡】
  • 并发性
  • 独立性
  • 异步性【交替相互执行】

三种基本状态

  • 就绪状态

    已准备好运行，即进程已分配到除CPU以外的所有必要资源，只要获得CPU，便可立即执行。系统中若有多个进程处于就绪状态，通常将他们按一定的策略【如优先级策略】排成队列，该队列为就绪队列。

  • 执行状态

    进程获得CPU。对于时刻而言，在单处理机系统中，只有一个进程处于执行状态。在多处理机系统中，有多个进程处于执行状态。

  • 阻塞状态

    指正在执行的进程由于发生某时间（如I/O请求、申请缓冲区失败等）暂时无法执行时的状态，亦即进程的执行收到阻塞

    此时引起进程调度，OS把处理机分配给另一个就绪进程，而让受阻进程处于暂停状态，一般这种暂停状态称为阻塞状态【等待状态、封锁状态】，阻塞队列

基本状态的转换

除三种基本状态以外还有一个重要操作【挂起操作】

  • 挂起：强迫进程释放分配到的资源，将进程调出到外存
  • 活动：未被挂起的就绪和阻塞状态，称为活动就绪和活动阻塞
  • 静止：被挂起的就绪状态和阻塞状态，为静止就绪和静止阻塞



进程管理中的数据结构

PCB的作用

  • PCB 是进程存在的唯一标志
  • 使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，成为能与其它进程并发执行的进程

进程同步

基本概念

  • 两种形式的制约关系（直接和间接）
  • 临界资源
  • 临界区：每个进程中访问临界资源的那段代码叫临界区
  • 同步机制应遵循的规则：
    • 空闲让进： 交替不行！！！
      1. 有效的利用临界资源
      2. 有没有“交替”，有了就违反
      3. 不能有“轮流访问”的情况，要“按需”
    • 忙则等待： 互斥！！！
      1. 保证对临界资源的互斥访问
      2. 讲武德，互斥
    • 有限等待 一直在里面等待，一个时间段之内出不来，因为没人通知他能出来
      1. 避免“死等”
      2. 对于要访问临界资源的进程，要在有限的时间内进入临界区
    • 让权等待 if while …不停访问资源
      1. 以免“忙等”
      2. 不能平明的问cpu临界资源有没有被已有进程使用，霸占cpu（比如一直循环问）

信号量机制

  • 整型信号量

    /*p*/
wait(S){
	while(S<=0);
	S--;
}

/*s*/
signal(S){
	S++;
}

    定义为一个用于表示资源数目的整型量S，除初始化外，仅能通过两国和标准原子操作 wait(S) signal(S)来访问，很长时间依赖，这两个操作分别称为P、V操作

    缺点：只要s<=0，就会不断测试，因此未遵循“让权等待”原则

  • 记录型信号量 解决了”忙等“的问题

    采取“让权等待“策略后，有出现了多个策略同时等待同一临界资源的情况。为此，不仅需要一个value变量来表示资源数目，还需要一个进程链表指针list，用于链接所有等待进程

    typedef struct{
	int value;
	struct process_controller_block *list;
}semaphore;

wait(semaphore *S){
    S->value--;
    if(s->value<0) block(S->list);
}
signal(semaphore *S){
    s->value++;
    if(S->value<=0) wakeup(S->list);
}

  • AND信号量 解决了”死锁“的现象

    上面的机制仅适用于各进程间只共享一个临界资源的情况，当进程需要几个共享资源时，容易出现死锁现象

    AND同步机制：进程需要的所有资源一次性分配给进程，进程使用完后再一起释放。所以之前的wait操作变为了同时wait操作，即Swait（Simultaneous wait）

    所以PV操作变为了：Swait(S1,S2,……,Sn)，Ssignal(S1,S2,……,Sn)。

  • 信号量集：

    当要求在资源量大于某一下限值时，才予分配，且一次性需要N个某类临界资源时，可以采用信号量集机制(S为信号量，t为该资源的分配下限值，d为进程对该资源的需求值)：

    Swait(S1,t1,d1,…..,Sn,tnndn)

    Ssinal(S1,t1,d1,…..,Sn,tnndn)

    特殊情况：

    Swait(S,d,d)：**仅有一个信号量S，每次申请d个资源，但现有资源少于d时，不予分配

    Swait(S,1,1)：即为一般的记录型信号量（S>1时），或互斥信号量（S=1时）。

    Swait(S,1,0)：S≥1时，允许多个进程进行某特定区；S变为0后，阻止任何进程进入特定区。相当于一个可控开关。

信号量的应用

p56-57，时间关系，先列出来，不仔细写了

  • 利用信号量实现进程互斥
  • 利用信号量实现前驱关系

经典进程的同步问题

生产者-消费者问题

哲学家进餐问题

读者-写者问题

线程

为了更好的理解，这里把线程和进程放在一起写

  • 进程是执行的程序，资源分配的最小单位
  • 线程是CPU调度的基本单位
  • 线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。

区别

进程 线程
是拥有资源的最小单位 是调度的最小单位
拥有自己独立的地址空间，每启动一个进程，系统会为其分配地址空间，建立数据来维护代码段、堆栈段、数据段 没有独立的空间地址，它使用相同的地址空间共享数据
cpu切换花费大 cpu切换花费小
创建的开销大 创建的开销小
占用资源大 占用资源小
线程之间通信更方便，同一进程下，线程共享全局变量、静态变量等数据
多进程程序更加安全、生命力更强，一个进程死掉不会影响另一个进程（它拥有独立地址空间） 多线程程序不易维护，一个线程死掉，整个线程就结束了（共享地址空间）
进程保护要求高，开销大，效率相对较低 线程效率就比较高，可以频繁切换

处理机调度与死锁

处理机调度的层次和调度算法的目标

处理机调度的层次

  1. 高级调度（长程调度、作业调度） 调度对象是作业

    决定将外存上处于后背队列中的哪几个作业调入内存

  2. 低级调度（短程调度、进程调度） 调度对象是进程

    决定就绪队列中的哪个进程应获得处理机

  3. 中级调度 （内存调度）

    提高内存利用率和系统吞吐量

调度算法的目标

处理机点都算法的共同目标

  • 资源利用率
    $$
    cpu的利用率=cpu有效工作时间/（cpu有效工作时间+cpu空闲等待时间）
    $$

  • 公平性

  • 平衡性

  • 策略强制执行

各类时间

周转时间=完成时间-到达时间

等待时间=周转时间-运行时间

带权周转时间=周转时间/运行时间

作业与作业调度

作业

作业：一个比程序更为广泛的概念。包含了通常的程序和数据，还配有一份作业说明书

作业步：作业步组成做鱼

JCB作业控制块 ：作业在系统中存在的标志

作业运行的三个阶段和三个状态：

  • 收容、运行、完成 三个阶段
  • 后备、运行、完成 三个状态

作业调度

作业调度的任务：

  • 根据JCB中的信息，检查系统能不能满足作业对资源的需求。再通过调度算法，从外存的后背队列中选取某些作业调入内存，并为它们创建进程、分配资源。
  • 每次执行作业调度时，要决定 介绍多少个作业 和接纳哪些作业

调度算法

先来先服务作业 (FCFS)first come first served

短作业优先 (SJF) short job first

优先级调度算法 (PSA) priority scheduling algorithm

高响应比优先算法 (HRRN)highest response ratio next

  • FCFS算法只考虑作业的等待时间，没有考虑作业运行时间，而SJF刚好相反。

  • HRRN则两者都考虑到了

  • 响应比 （优先权）：这是个动态优先级
    $$
    响应比=（等待时间+要求服务时间）/要求服务时间
    $$

  • 等待时间+服务时间=响应时间
    $$
    响应比Rp=响应时间/要求服务时间
    $$

  • ↑↑↑就这玩意↑↑↑ 这玩意高的先上处理机

进程调度

进程调度的任务

  1. 保存处理机和现场信息
  2. 按某种算法选取进程
  3. 把处理机分配给进程

进程调度方式

  1. 非抢占方式
  2. 抢占方式

进程调度算法

p93

轮转调度算法

优先级调度算法

多队列调度算法

多级反馈队列算法

死锁

死锁的定义、必要条件、处理方法

定义：

产生死锁的必要条件

  1. 互斥条件
  2. 请求和保持条件
  3. 不可抢占条件
  4. 循环等待条件

处理方法

  1. 预防死锁
  2. 避免死锁
  3. 检测死锁
  4. 解除死锁

预防死锁

破坏“请求和保持”条件

破坏“不可抢占”条件

破坏循环等待条件

‘

避免死锁

系统安全状态

银行家算法（避免死锁）

需求矩阵怎么求？

死锁的检测与解除

  • 死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁
  • 死锁解除算法：当认定了系统已发生死锁，利用解除算法，将系统从死锁状态解脱出来

死锁的检测

资源分配图

对于进程p来说：出去是请求，进来是分配

死锁定理

通过简化资源分配图来检测是当系统处于s状态时，是否为死锁状态

简化方法：依次消除与不阻塞进程相连的边（死锁检测算法），知道无边可小

  1. 在资源分配图中，找到一个既不阻塞又非独立的进程节点Pi。顺利情况下，P可以获得资源并运行完毕，最后释放所占有的全部资源。相当于去掉P的请求边和分配边
  2. 重复步骤1
  3. 经过一系列简化后，如果能使所有的进程节点都称为鼓励节点，则称该图可完全简化

S为死锁的充分条件：当且仅当S状态的资源分配图是不可完全简化的。

  • 若资源分配图中没有环路，则系统中没有死锁；若有，则可能有死锁
  • 若每个资源表中只包含一个资源实例（只有一个资源），则环路是死锁存在的充要条件

死锁的解除

方法

  • 抢占资源。从n个进程中抢占足够多的资源，分配给死锁进程。
  • 终止（或撤销进程）。终止一个或多个进程，直到解除死锁状态（代价大）。
  • 进程回退法。

存储器管理

时间关系，先挑重点写了

程序的装入和链接

用户程序要在系统中运行，必须先装入内存，然后再编程一个可以执行的程序，步骤如下：

  1. 编译
  2. 链接
  3. 装入

程序的装入

绝对装入方式

可重定位装入方式 又叫静态重定位

动态运行时的装入方式 又叫动态重定位

程序的链接

  1. 静态链接方式
  2. 装入时动态链接方式
  3. 运行时动态链接方式

连续分配存储管理方式

单一连续分配

无外部碎片，实现简单

只适用于单用户，有内部碎片

固定分区分配

实现简单，无外部碎片

程序太大时，可能所有的分区都不能满足要求，会产生内部碎片，内存利用率低

动态分区分配

又称可变分区分配，根据进程实际需要，动态分配内存空间（不会预先划分分区）

无内部碎片，有外部碎片（可用紧凑技术解决）

动态分区分配中的数据结构

  • 空闲分区表
  • 空闲分区链

动态分区分配算法

从空闲分区表、链中选出一分区分配给该作业

ps:后面会讲传统的四种分配算法

分区分配操作

  1. 分配内存
  2. 回收内存

基于顺序搜索的动态分区分配算法

所谓顺序搜索，就是一次搜索空闲分区链上的空闲分区，寻找一个大小满足要求的分区

基于顺序搜索的动态分区算法有下面四种

  • 首次适应算法
  • 循环首次适应算法
  • 最佳适应算法（既满足要求，又是最小的空闲分区分配给作业，避免“大材小用”）
  • 最坏适应算法（总是挑选一个最大的空闲区）

分页存储管理方式

分页存储管理的基本方法

分页为了解决内存碎片

逻辑地址空间中的地址为A，页面大小为L

逻辑地址存在于进程当中

页号P=int（A/L）

页内地址d=A MOD L

地址变化机构

基本的地址变化机构

用于实现逻辑地址到物理地址的转换

说明：

  • 页表地址F
  • 页表长度M
  • 页号P
  • 页内地址（偏移量）W
  • 内存块号b
  • 页面大小L

步骤：

  1. 根据逻辑地址计算出页号和页内地址偏移量

  2. 判断页号是否越界

  3. 查询页表，找到页号对应的页表项

  4. 用内存块号和页内偏移量得到物理地址

    物理地址 E=b*L+w

  5. 访问目标内存单元

具有快表的地址变化机构

快表又称“联想寄存器”：用来存放最近访问的页面项表的副本，一种访问速度比内存快很多的告诉缓存

分段存储管理方式

具体来说：分段存储管理方式更符合用户和程序员如下多方面的需要

作用

  • 方便编程
  • 信息共享
  • 信息保护
  • 动态增长
  • 动态链接

分段系统的基本原理

分段

段表

地址变化机构

分页和分段主要区别

页 段
物理单位 逻辑单位
大小固定 长度不固定
分页的用户程序地址空间是一维的 分段系统中用户程序的地址空间是二维的

虚拟存储器

虚拟存储器概述

常规存储管理方式的特征和局部性原理

常规存储器管理方式的特征

  • 一次性
  • 驻留性

局部性原理

  • 时间局部性（典型的原因是在程序中存在着大量的循环操作）
  • 空间局部性（因为很多数据在内存中都是连续存放的，并且程序的指令也是顺序地在内存中存放）

虚拟存储器的基本工作情况

  1. 基于局部性原理可知，运行之前没必要把全部装入内存，而仅须将当前要运行的少数页面或段先装入内存（部分调入内存）
  2. 程序运行时如果它要访问的页（段）已调入内存，便继续执行
  3. 如果程序要访问的页、段尚未调入内存，便发出缺页（段）终端请求
  4. 此时OS利用请求调页（段）功能将他们调入内存
  5. 如果内存已满，OS利用页（段）置换功能，将内存中不要的页（段）调至盘上

虚拟存储器的定义和特征

虚拟存储器的定义

所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统

虚拟存储器的特征

  • 多次性
  • 对换性
  • 虚拟性

虚拟存储器的实现方法

目前，所有的虚拟存储器都是采用下述方式之一实现的

请求分页管理系统

就是在分页系统的基础上增加了请求调页功能和页面置换功能的一个页式虚拟存储系统

解决内存不够问题。

请求分段系统

类似于上面

请求分页存储管理方式

请求分页中的硬件支持

p157

请求分页中的内存分配

页面调入策略

页面置换算法

不要的页面换到外存取，需要的调入内存

最佳置换算法

先进先出置换算法

最近最久未使用算法

Clock置换算法（简单版）

Clock置换算法（改进版）

“抖动”与工作集

产生抖动的根本原因：

同时在系统中运行的进程太多，由此分配发给每一个进程的物理块太少，不能满足进程正常运行的基本要求

工作集

  • 基本概念
  • 定义

请求分段存储管理方式

请求分段中的硬件支持

请求段表机制

缺段中断机构

地址变换机构

分段的共享与保护

共享段表

共享段表的分配和回收

分段保护

  • 越界检查
  • 存储控制检查
  • 环保护机构
    • 一个程序可以访问驻留在相同环或较低特权环（外环）的数据
    • 一个程序可以访问驻留在相同环或较高特权环（内环）的服务

输入输出系统

IO系统的功能、模型、接口

IO系统的层次接口和模型

IO软件的层次结构

从上到下分别为

  1. 用户层IO软件
  2. 设备独立性软件
  3. 设备驱动程序
  4. 中断处理程序

IO设备和设备控制器

IO设备

IO设备的类型

按速率分配

  • 低速： 几到几百个字节如键盘鼠标

  • 中速：传输速率为每秒几千字节到数万字节如行式打印机，激光打印机

  • 高速：百千到千兆字节

信息交换单位分类：

  • 块设备

  • 字符设备

共享属性：

  • 独占

  • 共享

  • 虚拟

设备控制器

主要功能：控制一个或多个IO设备，以实现IO设备和计算机之间的数据交换。他是CPU和IO设备之间的接口

基本功能

  • 接受和识别命令（控制寄存器）
  • 数据交换（数据寄存器）
  • 标识和报告设备状态（状态寄存器）
  • 地址识别（地址译码器）
  • 数据缓冲区
  • 差错控制

设备控制器的组成

  • 设备控制器与处理机的接口
  • 设备控制器与设备的接口
  • IO逻辑

对IO设备的控制方式

即用什么样的方式来控制IO设备的数据读写

使用轮询的可编程IO方式

使用中断的可编程IO方式

直接存储器访问方式

也叫DMA

特点：

  • 数据传输的基本单位是数据块
  • 所传送数据是设备直接送入内存的，或相反
  • 只有一个或多个数据块开始或结束时，才需CPU干预

组成：

  • 主机和DMA控制器的接口
  • DMA控制器和块设备的接口
  • IO控制设备的逻辑

IO通道控制方式

是对DMA方式的发展，近一步减少cpu的干预

从一个数据块—>到一组数据块

通道程序

类似任务清单，通道是通过执行通道程序并与设备控制器共同实现对IO设备的控制的。

设备分配

设备的固有属性

  • 独占设备
  • 共享给设备
  • 虚拟设备（通过假脱机技术将独占设备改造成共享设备）

用户层的IO软件

假脱机（Spooling）系统

一般在用户层实现

通过假脱机技术，将一台物理IO设备虚拟为多态逻辑IO设备，这样也就允许多个用户共享一台物理设备。

Spooling的组成

  • 输入井和输出井
  • 输入缓冲区和输出缓冲区（中转站）
  • 输入进程和输出进程
  • 井管理程序

Spooling系统的特点

  • 提高了IO速度
  • 将独占设备改造成共享设备
  • 涉嫌了虚拟设备功能

缓冲区管理

缓冲器的引入

原因：

  • 缓和CPU和IO设备间速度不匹配的矛盾
  • 减少对CPU的中断频率，放宽对CPU中断响应时间的限制
  • 解决数据粒度不匹配的问题
  • 提高CPU和IO设备的并行性

单缓冲区

双缓冲区

环形缓冲区（循环缓冲区）

缓冲池

缓冲池管理多个缓冲区

为了方便，一般将缓冲池中具有相同类型的缓冲区链接成一个队列，于是课形成以下三个队列：

  • 空白缓冲队列 emq
  • 输入队列 inq
  • 输出队列 outq

磁盘存储器的性能和调度

磁盘性能简述

一个盘面有若干磁道，磁道之间有间隔

组成

参考：https://blog.csdn.net/zhanglh046/article/details/115710477

  • 盘面
  • 主轴
  • 磁道
  • 扇区
  • 柱面
  • 磁头臂（机械臂）
  • 磁头
  • 磁盘驱动器
  • 磁盘控制器

早期的磁盘调度算法

  • 先来先服务
  • 最短寻道时间优先

基于扫描的磁盘调度算法

  • 扫描算法
  • 循环扫描算法

文件管理

文件和文件系统

数据项、记录、文件

文件名和类型

文件类型

  • 按用途分类
    • 系统文件
    • 用户文件
    • 库文件
  • 按文件中数据的形式分类
    • 源文件
    • 目标文件
    • 可执行文件
  • 按存储的控制属性分类
    • 只执行文件
    • 只读文件
    • 读写文件
  • 按组织形式和处理方式分类
    • 普通文件
    • 目录文件
    • 特殊文件

文件系统的层次结构

文件系统的模型可分为三个层次：

  • 最高层：文件系统接口
  • 中间层：对对象操纵和管理的软件集合
  • 最底层：对象及其属性