操作系统笔记

考试信息：

• 选择
• 判断
• 分析（简答）
• 大题

课后题重要，但没有原题

参考视频：王道操作系统考研

2.1 进程与线程

进程的概念、组成、特征

• 程序: 是静态的,就是个存放在磁盘里的可执行文件,就是一系列的指令集合。

• 进程(Process) :是动态的,是程序的一次执行过程

  同一个程序多次执行会对应多个进程

进程实体的组成

• PCB ：以下信息都被保存在一个数据结构PCB (Process Control Block)中,即进程控制块, 操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在PCB中

  • 进程描述信息：操作系统要记录进程标识符(PID)、进程所属用户ID（UID)

  • 资源分配清单：还要记录给进程分配了哪些资源（如：分配了多少内存、正在使用哪些I/O设备、正在使用哪些文件）

  • 进程控制和管理信息：还要记录进程的运行情况（如：CPU使用时间、磁盘使用情况、网络流量使用情况等）,

    进程当前状态：就绪态/阻塞态/运行态…

  • 处理机相关信息：处理机相关信息如PSW、PC等等各种寄存器的值（用于实现进程切换）

• 程序段：程序的代码（指令序列）

• 数据段：运行过程中产生的各种数据（程序中定义的变量）

进程的特征

• 动态性：进程是程序的一次执行过程，是动态地产生、变化和消亡的
• 并发性：内存中有多个进程实体,各进程可并发执行
• 独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位
• 异步性：各进程按各自独立的、不可预知的速度向前推进，操作系统要提供"进程同步机制"来解决异步问题
• 结构性：每个进程都会配置一个PCB,结构上看,进程由程序段、数据段、PCB组成

进程的状态

状态包括：（前三个是三种基本状态）

• 运行状态(Running)
• 就绪状态(Ready)
• 阻塞状态(Waiting/Blocked)(等待态)
• 创建状态(New)(新建态)
• 终止状态(Terminated)(结束态)

状态间的转换

• 就绪态—>运行态
• 运行态—>就绪态
• 运行态—>阻塞态
• 阻塞态—>就绪态

进程状态的转换：丁字裤模型

进程PCB中，会有一个变量 state 来表示进程的当前状态。如：

• 1表示创建态
• 2表示就绪态
• 3表示运行态…

为了对同一个状态下的各个进程进行统一的管理,操作系统会将各个进程的PCB组织起来。

进程的组织：

• 链接方式：类似于链表（大多数操作系统用这个）

• 索引方式

进程控制

进程的控制使用原语

原语的执行具有原子性,即执行过程只能一气呵成,期间不允许被中断。可以用“关中断指令”和“开中断指令”这两个特权指令实现原子性

进程的创建

创建原语

• 申请空白PCB
• 为新进程分配所需资源
• 初始化PCB
• 将PCB插入就绪队列

引起进程创建的事件

• 用户登录：分时系统中，用户登录成功，系统会建立为其建立一个新的进程
• 作业调度：多道批处理系统中,有新的作业放入内存时,会为其建立一个新的进程
• 提供服务：用户向操作系统提出某些请求时，会新建一个进程处理该请求
• 应用请求：由用户进程主动请求创建一个子进程

进程的终止

撤销原语

• 从PCB集合中找到终止进程的PCB
• 若进程正在运行，立即剥夺CPU，将CPU分配给其他进程
• 终止其所有子进程
• 将该进程拥有的所有资源归还给父进程或操作系统
• 删除PCB

引起进程终止的事件

• 正常结束
• 异常结束
• 外界干预

进程的阻塞

阻塞原语

• 找到要阻塞的进程对应的PCB
• 保护进程运行现场，将PCB状态信息设置为“阻塞态"，暂时停止进程运行
• 将PCB插入相应事件的等待队列

引起进程阻塞的事件

• 需要等待系统分配某种资源
• 需要等待相互合作的其他进程完成工作

进程的唤醒

唤醒原语

• 在事件等待队列中找到PCB
• 将PCB从等待队列移除,设置进程为就绪态
• 将PCB插入就绪队列，等待被调度

引起进程唤醒的事件：等待的事件发生

进程的切换

切换原语

• 将运行环境信息存入PCB
• PCB移入相应队列
• 切换原语选择另一个进程执行，并更新其PCB
• 根据PCB恢复新进程所需的运行环境

引起进程切换的事件

• 当前进程时间片到
• 有更高优先级的进程到达
• 当前进程主动阻塞
• 当前进程终止

进程通信

• 共享存储
  • 设置一个共享内存区域，并映射到进程的虚拟地址空间
  • 要互斥地访问共享空间(由通信进程自己负责实现互斥)
  • 两种方式
    • 基于数据结构（低级）
    • 基于存储区的共享（高级）
• 消息传递
  • 传递结构化的消息(消息头/消息体)
  • 系统提供“发送/接受原语”
  • 两种方式
    • 直接通信方式：消息直接挂到接收进程的消息队列里
    • 间接（信箱）通信方式：消息先发到中间体（信箱）
• 管道通信
  • 1,管道只能采用半双工通信,某一时间段内只能实现单向的传输。如果要实现双向同时通信,则需要设置两个管道。
  • 2,各进程要互斥地访问管道(由操作系统实现)
  • 3,当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。
  • 4,当管道读空时,读进程将阻塞,直到写进程往管道中写入数据,即可唤醒读进程。
  • 5,管道中的数据一旦被读出,就彻底消失。因此,当多个进程读同一个管道时,可能会错乱。对此,通常有两种解决方案:
    • ①一个管道允许多个写进程,一个读进程(2014年408真题高教社官方答案)
    • ②允许有多个写进程,多个读进程,但系统会让各个读进程轮流从管道中读数据(Linux的方案)

线程的概念

引入线程后带来的变化

• 资源分配、调度
  • 传统进程机制中，进程是资源分配、调度的基本单位
  • 引入线程后，进程是资源分配的基本单位，线程是调度的基本单位
• 并发性
  • 传统进程机制中，只能进程间并发
  • 引入线程后,各线程间也能并发,提升了并发度
• 系统开销
  • 传统的进程间并发,需要切换进程的运行环境,系统开销很大
  • 线程间并发,如果是同一进程内的线程切换,则不需要切换进程环境,系统开销小
  • 引入线程后,并发所带来的系统开销减小

线程的属性

• 线程是处理机调度的单位
• 多CPU计算机中,各个线程可占用不同的CPU
• 每个线程都有一个线程ID、线程控制块(TCB)
• 线程也有就绪、阻塞、运行三种基本状态
• 线程几乎不拥有系统资源
• 同一进程的不同线程间共享进程的资源
• 由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
• 同一进程中的线程切换，不会引起进程切换
• 不同进程中的线程切换,会引起进程切换
• 切换同进程内的线程,系统开销很小
• 切换进程，系统开销较大

多线程的优点

• 响应性: 如果部分线程被阻塞，仍可以继续执行，这对于用户界
  面设计尤其重要，快速响应;
• 资源共享: 线程共享进程资源，比进程共享内存或消息传递更容
  易，允许一个应用程序在同一地址空间内有多个不同的活跃线程;
• 经济: 比进程创建更便宜，线程切换比上下文切换开销更低。进
  程创建是线程创建的几十倍，进程切换比线程切换慢5倍;
• 可扩展性（可伸缩性）: 线程可以利用多核体系结构;

Amdahl定律

$$S_A=\frac 1 {s+\frac {1-s}{N}}$$

$N$: 为处理器数量

$s$: 指程序中串行部分的工作量占整个程序工作量的比例

$S_A$:加速比

$$\frac{新的性能}{旧的性能}=\frac{旧运行时间}{新运行时间}=S_A$$

Amdahl定律说明什么?

省流:并行计算没有前途

$N \to \infin,\frac{1-s}N\to 0,S_A\to \frac 1s$

$S_A$存在上限

对计算机系统的某个部分采用并行优化措施后所获得的计算机性能的提高是有上限的，这个上限取决于串行部分所占的比例

该定律没有考虑到当代多核系统,需要在分母加一项, 表示内核间的通信

线程的实现方式和多线程模型

线程的实现方式

• 用户级线程：从用户视角能看到的线程，由线程库实现

  管理线程的所有工作都由应用程序完成；内核意识不到线程的存在；采用第三方库来创建如pthreads;

  • 优势: 灵活; 可以运行在任何操作系统, 而不必作代码的改变

  • 劣势: 只要一个线程执行了系统调用, 整个进程都会被阻塞; 无法充分利用多核

  • 解决方案: 套管技术:把一个产生阻塞的系统调用转化为一个非阻塞的系统调用；把应用程序写成一个多进程程序而非多线程程序,每次切换都变成进程间的切换而非线程间切换

• 内核级线程：从操作系统视角看到的线程，由操作系统实现（内核级线程才是处理机分配的单位)

  • 优势: 可以充分利用多核资源; 进程中的一个线程阻塞，内核可以调度同一个进程中的另一个线程；
  • 劣势: 需要切换内核模式, 时间开销大

• 组合方式：上述两种方式的结合

  很复杂, 没有哪个操作系统能做好, 现在的主流操作系统都没有采用这个

线程模型即用户线程与内核线程的对应关系；

多线程模型

• 一对一模型：
  • 一个用户级线程映射到一个内核级线程
  • 优:各个线程可分配到多核处理机并行执行,并发度高
  • 缺:线程管理都需要操作系统支持,开销大
• 多对一模型：
  • 多个用户级线程映射到一个内核级线程
  • 优：线程管理开销小效率高
  • 缺:一个线程阻塞会导致整个进程都被阻塞(并发度低)
• 多对多模型
  • n个用户级线程映射到m个内核级线程(n≥m)
  • 集二者之所长

多线程分为异步线程和同步线程

• 异步线程: 父子线程同时运行, 数据共享不多
• 同步线程: 父线程等待子线程结束, 数据共享多

线程的状态与转换

graph LR;
id1(就绪) --3 被调度程序选中--> id2(运行);
id2 --2 时间用完--> id1;
id3(阻塞) --4 等待的事件发生-->id1;
id2 --1 等待某事件-->id3;

线程没有挂起态, 因为线程没有自己管理的内存, 而挂起的含义是将内存写入磁盘

2.2 处理机调度

调度的概念、层次

调度的三个层次

	要做什么	调度发生在	发生频率	对进程状态的影响
高级调度(作业调度)	按照某种规则，从后备队列中选择合适的作业将其调入内存,并为其创建进程	外存→内存（面向作业）	最低	无→创建态→就绪态
中级调度(内存调度)	按照某种规则,从挂起队列中选择合适的进程将其数据调回内存	外存→内存（面向进程）	中等	挂起态→就绪态（阻塞挂起→阻塞态）
低级调度(进程调度/处理机调度)	按照某种规则,从就绪队列中选择一个进程为其分配处理机	内存→CPU	最高	就绪态→运行态

进程的挂起态与七状态模型

进程调度的时机、切换与过程调度方式

进程调度（低级调度），就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

需要进行进程调度与切换的情况

• 当前运行的进程主动放弃处理机
  • 进程正常终止
  • 运行过程中发生异常而终止
  • 进程主动请求阻塞(如等待I/O)
• 当前运行的进程被动放弃处理机
  • 分给进程的时间片用完
  • 有更紧急的事需要处理(如I/O中断)
  • 有更高优先级的进程进入就绪队列

不能进行进程调度与切换的情况

• 在处理中断的过程中。中断处理过程复杂，与硬件密切相关,很难做到在中断处理过程中进行进程切换。
• 进程在操作系统内核程序临界区中。
• 在原子操作过程中(原语)。原子操作不可中断,要一气呵成(如之前讲过的修改PCB中进程状态标志，并把PCB放到相应队列)

进程调度的方式

• 非剥夺调度方式,又称非抢占方式。即,只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达,当前进程依然会继续使用处理机,直到该进程终止或主动要求进入阻塞态。
• 剥夺调度方式,又称抢占方式。当一个进程正在处理机上执行时,如果有一个更重要或更紧迫的进程需要使用处理机,则立即暂停正在执行的进程,将处理机分配给更重要紧迫的那个进程。

切换的过程

• 对原来运行进程各种数据的保存
• 对新的进程各种数据的恢复

调度器和闲逛进程

调度器

graph LR;
id1(就绪) --3 被调度程序选中--> id2(运行);
id2 --2 时间用完--> id1;
id3(阻塞) --4 等待的事件发生-->id1;
id2 --1 等待某事件-->id3;

其中2和3由调度程序引起

• 非抢占式调度策略,只有运行进程阻塞或退出才触发调度程序工作
• 抢占式调度策略，每个时钟中断或k个时钟中断会触发调度程序工作

闲逛进程(idle)

调度程序永远的备胎,没有其他就绪进程时,运行闲逛进程

• 优先级最低
• 可以是0地址指令,占一个完整的指令周期(指令周期末尾例行检查中断)
• 能耗低

调度算法的评价指标

• CPU利用率

$$CPU利用率=\frac{忙碌的时间}{总时间}$$

对于多道程序并发执行的情况，可以用甘特图辅助计算

• 系统吞吐量

$$系统吞吐量=\frac{总共完成了多少道作业}{总共花了多少时间}$$

• 周转时间

从作业被提交给系统开始,到作业完成为止的这段时间间隔。

它包括四个部分:

• • 作业在外存后备队列上等待作业调度(高级调度)的时间
  • 进程在就绪队列上等待进程调度(低级调度)的时间
  • 进程在CPU上执行的时间
  • 进程等待I/O操作完成的时间

$$平均周转时间=\frac{各作业周转时间之和}{作业数}$$

$$带权周转时间=\frac{作业周转时间}{作业实际运行的时间}=\frac{作业完成时间-作业提交时间}{作业实际运行的时间}$$

• • 对于周转时间相同的两个作业，实际运行时间长的作业在相同时间内被服务的时间更多,带权周转时间更小，用户满意度更高。
  • 对于实际运行时间相同的两个作业，周转时间短的带权周转时间更小,用户满意度更高。

• 等待时间

指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

• • 对于进程来说,等待时间就是指进程建立后等待被服务的时间之和,在等待I/O完成的期间其实进程也是在被服务的,所以不计入等待时间。
  • 对于作业来说,不仅要考虑建立进程后的等待时间,还要加上作业在外存后备队列中等待的时间。

• 响应时间

从用户提交请求到首次产生响应所用的时间

优化原则：

• 最大CPU利用率
• 最大吞吐量
• 最小周转时间
• 最小等待时间
• 最小响应时间
• 大多数情况下，优化的是平均值；有些情况下优化的是最小值或最大值，也可以最小化方差；

调度算法

（1）适用于早期的批处理系统

算法	思想	规则	可抢占？	优点	缺点	考虑到等待时间&运行时间？	会导致饥饿？
FCFS(First Come First Serve)先来先服务	公平	按照作业/进程到达的先后顺序进行服务	否	公平、算法实现简单	缺点：排在长作业（进程）后面的短作业需要等待很长时间,带权周转时间很大,对短作业来说用户体验不好。	等待时间√，运行时间×	不会
SJF(Shortest Job First)短作业优先 / SPF(Shortest Process First)短进程优先	追求最少的平均等待时间,最少的平均周转时间、最少的平均平均带权周转时间	最短的作业/进程优先得到服务(所谓“最短”,是指要求服务时间最短）	SJF和SPF是非抢占式的算法。但是也有抢占式的版本——最短剩余时间优先算法（SRTN, Shortest Remaining Time Next)	“最短的”平均等待时间、平均周转时间	缺点:不公平。对短作业有利,对长作业不利。可能产生饥饿现象。另外,作业/进程的运行时间是由用户提供的，并不一定真实,不一定能做到真正的短作业优先	等待时间×，运行时间√	会
HRRN(Highest Response Ratio Next)高相应比优先	要综合考虑作业/进程的等待时间和要求服务的时间	在每次调度时先计算各个作业/进程的响应比,选择响应比最高的作业/进程为其服务	否	综合考虑了等待时间和运行时间(要求服务时间)。等待时间相同时,要求服务时间短的优先(SJF的优点)，要求服务时间相同时，等待时间长的优先（FCFS的优点）。对于长作业来说,随着等待时间越来越久,其响应比也会越来越大，从而避免了长作业饥饿的问题	无	等待时间√，运行时间√	不会

$$响应比=\frac{等待时间+要求服务时间}{要求服务时间}$$

（2）适用于交互式操作系统

• 时间片轮转调度算法(RR，Round-Robin)

  • 算法思想：公平地、轮流地为各个进程服务,让每个进程在一定时间间隔内都可以得到响应

  • 算法规则：按照各进程到达就绪队列的顺序,轮流让各个进程执行一个时间片(如100ms)。若进程未在一个时间片内执行完,则剥夺处理机,将进程重新放到就绪队列队尾重新排队。

  • 用于作业/进程调度：用于进程调度(只有作业放入内存建立了相应的进程后,才能被分配处理机时间片)

  • 是否可抢占？若进程未能在时间片内运行完,将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到

  • 优缺点：

    优点：公平;响应快,适用于分时操作系统;

    缺点: 由于高频率的进程切换,因此有一定开销;不区分任务的紧急程度。

  • 是否会导致饥饿？不会

• 优先级调度算法

  • 算法思想：随着计算机的发展,特别是实时操作系统的出现,越来越多的应用场景需要根据任务的紧急程度来决定处理顺序

  • 算法规则：调度时选择优先级最高的作业/进程

  • 用于作业/进程调度：既可用于作业调度,也可用于进程调度。甚至,还会用于在之后会学习的I/O调度中

  • 是否可抢占？抢占式、非抢占式都有。做题时的区别在于:非抢占式只需在进程主动放弃处理机时进行调度即可,而抢占式还需在就绪队列变化时,检查是否会发生抢占。

  • 优缺点：优点：用优先级区分紧急程度、重要程度,适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。缺点:若源源不断地有高优先级进程到来,则可能导致饥饿

  • 是否会导致饥饿？会

• 多级反馈队列调度算法

  • 算法思想：对其他调度算法的折中权衡
  • 算法规则：
    1. 设置多级就绪队列,各级队列优先级从高到低,时间片从小到大
    2. 新进程到达时先进入第1级队列,按FCFS原则排队等待被分配时间片,若用完时间片进程还未结束,则进程进入下一级队列队尾,如果此时已经是在最下级的队列,则重新放回该队列队尾
    3. 只有第k级队列为空时,才会为k+1级队头的进程分配时间片
  • 用于用于作业/进程调度：用于进程调度
  • 是否可抢占？抢占式的算法。在k级队列的进程运行过程中,若更上级的队列（1~k-1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中,因此新进程会抢占处理机,原来运行的进程放回k级队列队尾。
  • 优缺点：
    • 对各类型进程相对公平(FCFS的优点)
    • 每个新到达的进程都可以很快就得到响应(RR的优点)
    • 短进程只用较少的时间就可完成(SPF的优点)
    • 不必实现估计进程的运行时间（避免用户作假)
    • 可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程(拓展:可以将因I/O而阻塞的进程重新放回原队列,这样I/0型进程就可以保持较高优先级)
  • 是否会导致饥饿？会

• 多级队列调度算法

按照优先级从高到低的队列分别为：

系统进程（如内存管理进程）

交互式进程（如游戏,打字软件）

批处理进程（如AI模型训练）

队列之间可采取固定优先级,或时间片划分固定优先级：高优先级空时低优先级进程才能被调度时间片划分：如三个队列分配时间50%、40%、10%

各队列可采用不同的调度策略，如系统进程队列采用优先级调度，交互式队列采用RR，批处理队列采用FCFS

2.3 进程同步与互斥

进程同步、进程互斥

进程同步：

同步亦称直接制约关系,它是指为完成某种任务而建立的两个或多个进程,这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

进程互斥：

graph LR;
id1[两种资源共享方式] --->id2(互斥共享方式)
id1 --->id3(同时共享方式)
id2 --->id4[一个时间段内只允许一个进程访问该资源]
id3 --->id5[允许一个时间段内由多个进程同时对它们进行访问]

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

对临界资源的访问,必须互斥地进行。互斥,亦称间接制约关系。进程互斥指当一个进程访问某临界资沙时,另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束,释放该资源之后,另一个进程才能去访问临界资源。

访问临界资源的代码逻辑：

do 
{
    entry section; //进入区,进入区负责检查是否可进入临界区,若可进入,则应设置正在访问临界资源的标志(可理解为"上锁")，以阻止其他进程同时进入临界区
    critical section; //临界区,临界区是进程中访问临界资源的代码段，也可称为“临界段”。
    exit section; //退出区,退出区负责解除正在访问临界资源的标志（可理解为“解锁”）
    remainder section;//剩余区
} while(true)

进入区和退出区是负责实现互斥的代码段

为了实现对临界资源的互斥访问,同时保证系统整体性能,需要遵循以下原则:

1. 空闲让进。临界区空闲时,可以允许一个请求进入临界区的进程立即进入临界区;
2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待
3. 有限等待。对请求访问的进程,应保证能在有限时间内进入临界区(保证不会饥饿)
4. 让权等待。当进程不能进入临界区时,应立即释放处理机,防止进程忙等待。

进程互斥的软件实现方法

单标志法

也称严格备选(strict Alternation)

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予

实现代码：

int turn = 0; //turn 表示当前允许进入临界区的进程号

P0进程

while(turn != 0);
critical section;
turn = 1;
remainder section;

P1进程

while(turn != 1);
critical section;
turn = 0;
remainder section;

该算法可以实现“同一时刻最多只允许一个进程访问临界区”

只能按P0→P1→P0→P1→... 这样轮流访问。这种必须“轮流访问”带来的问题是,如果此时允许进入临界区的进程是P0,而P0一直不访问临界区,那么虽然此时临界区空闲,但是并不允许P1访问。因此,单标志法存在的主要问题是:违背“空闲让进”原则。

如果一个进程想要连续两次访问临界区，这种方法无法实现

双标志先检查法

算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿

bool flag[2];
flag[0] = false;
flag[1] = false;

P0进程

while(flag[1]);  //1
flag[0] = true;  //2
critical section;//3
flag[0] = false; //4
remainder section;

P1进程

while(flag[0]);   //5
flag[1] = true;   //6
critical section; //7
flag[1] = false;  //8
remainder section;

按照152637执行，P0和P1会同时访问临界区

双标志先检查法的主要问题是:违反“忙则等待”原则。原因在于,进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后, “上锁”前可能发生进程切换。

双标志后检查法

算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁” ,但是这两个操作又无法一气呵成,因此导致了两个进程同时进入临界区的问题。因此,人们又想到先“上锁”后“检查”的方法,来避免上述问题。

bool flag[2];
flag[0] = false;
flag[1] = false;

P0进程

flag[0] = true;  //1
while(flag[1]);  //2
critical section;//3
flag[0] = false; //4
remainder section;

P1进程

flag[1] = true;   //5
while(flag[0]);   //6
critical section; //7
flag[1] = false;  //8
remainder section;

按照1526的顺序执行，P0和P1都无法进入临界区

双标志后检查法虽然解决了“忙则等待”的问题,但是又违背了“空闲让进”和“有限等待原则,会因各进程都长期无法访问临界资源而产生“饥饿”现象。两个进程都争着想进入临界区,但是谁也不让谁,最后谁都无法进入临界区。

Peterson算法

算法思想:结合双标志法、单标志法的思想。如果双方都争着想进入临界区,那可以让进程尝试“孔融让梨” (谦让)。做一个有礼貌的进程。

bool flag[2];
flag[0] = false;
flag[1] = false;
int turn = 0;

P0进程

flag[0] = true;
turn = 1;
while(flag[1] && turn ==1);
critical section;
flag[0] = false;
remainder section;

P1进程

flag[1] = true;
turn = 0;
while(flag[0] && turn == 0);
critical section;
flag[1] = false;
remainder section;

Peterson 算法用软件方法解决了进程互斥问题,遵循了空闲让进、忙则等待、有限等待三个原则,但是依然未遵循让权等待的原则（进不了临界区就卡在while循环，而不是让出处理机）。

进程互斥的硬件实现方法

中断屏蔽方法

利用“开/关中断指令”实现(与原语的实现思想相同,即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)

优点：简单、高效

缺点:不适用于多处理机; 只适用于操作系统内核进程,不适用于用户进程(因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)

TestAndSet指令

简称TS指令，或TSL指令

简称TS指令,也有地方称为TestAndSetLock指令,或TSL指令TSL指令是用硬件实现的,执行的过程不允许被中断,只能一气呵成。以下是用c语言描述的逻辑

//布尔型共享变量 lock 表示当前临界区是否被加锁
//true 表示已加锁，false 表示未加锁
bool TestAndSet (bool *lock){
    bool old;
    old = *lock; //old用来存放lock原来的值
    *lock = true;//无论之前是否已加锁，都将lock设为true
    return old;//返回lock原来的值
}

//以下是使用 TSL 指令实现互斥的算法逻辑
while (TestAndSet (&lock)); //"上锁"并"检查”
临界区代码段..
lock = false;//“解锁”
剩余区代码段...

优点:

实现简单,无需像软件实现方法那样严格检查是否会有逻辑漏洞

适用于多处理机环境

缺点:

不满足“让权等待”原则,暂时无法进入临界区的进程会占用CPU并循环执行TSL指令,从而导致“忙等”。

Swap指令

也称为XCHG指令

Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑

//以下是用 Swap 指令实现互斥的算法逻辑
//lock 表示当前临界区是否被加锁
bool old = true;
while (old== true)
    Swap (&lock, &old);
临界区代码段...
lock = false;
剩余区代码段…..

优缺点同TestAndSet指令

互斥锁

互斥锁mutex lock，也称为自旋锁spin lock

特性：

• 需忙等，进程时间片用完才下处理机,违反“让权等待”
• 优点:等待期间不用切换进程上下文,多处理器系统中,若上锁的时间短,则等待代价很低
• 常用于多处理器系统,一个核忙等,其他核照常工作,并快速释放临界区
• 不太适用于单处理机系统，忙等的过程中不可能解锁

信号量机制

信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量,比如:“系统中只有一台打印机,就可以设置一个初值为1的信号量。

原语是一种特殊的程序段,其执行只能一气呵成,不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”,因此如果能把进入区、退出区的操作都用“原语”实现,使这些操作能“一气呵成”就能避免问题。

一对原语: wait(S)原语和signal(S)原语,可以把原语理解为我们自己写的函数,函数名分别为wait和 signal，括号里的信号量 S 其实就是函数调用时传入的一个参数。

wait、signal原语常简称为P、V操作(来自荷兰语proberen和verhogen)。因此，做题的时候常把wait(S)、 signal(S)两个操作分别写为P(S)、V(S)

整型信号量

• 用一个整数型变量作为信号量，数值表示某种资源数
• 整型信号量与普通整型变量的区别：对信号量只能执行 初始化、P、V 三种操作
• 整型信号量存在的问题：不满足让权等待原则

记录型信号量

/*记录型信号量的定义*/
typedef struct {
    int value;//剩余资源数
    Struct process *L; //等待队列
} semaphore;
/*某进程需要使用资源时,通过 wait 原语申请*/
void wait (semaphore S) {
    S.value--;
    if (S.value < 0 ) { 
        block (S.L);//自我阻塞，将当前运行的进程从运行态变为阻塞态
    }
}
/*进程使用完资源后,通过 signal 原语释放*/
void signal (semaphore S){
    S.value++;
    if (S.value <= 0) {
        wakeup(S.L);
    }
}
//进程代码
...
wait(S);
使用打印机
signal(S);
...

用信号量实现进程互斥、同步、前驱关系

实现进程互斥

semaphore mutex=1;//初始化信号量
P1(){
    P(mutex);//使用临界资源前加锁
    临界区代码;
    V(mutex);//使用临界资源后解锁
}
P2(){
    P(mutex);
    临界区代码;
    V(mutex);
}

实现进程同步

/*信号量机制实现同步*/
semaphore S=0; //初始化同步信号量，初始值为0
P1(){
    代码1;
    代码2;
    V(S);
    代码3;
}
P2(){
    P(S);
    代码4;
    代码5;
    代码6;
}

可以保证代码4一定在代码2之后执行

实现前驱关系

graph TD;
id1(S1)--a-->id2(S2)
id1 --b--> id3(S3)
id2--c-->id4(S4)
id2 --d--> id5(S5)
id4--e-->id6(S6)
id5--f-->id6
id3--g-->id6

实现方式：

P1(){
    S1;
    V(a);
    V(b);
}
P2(){
    P(a);
    S2;
    V(c);
    V(d);
}
P3(){
    P(b);
    S3;
    V(g);
}
P4(){
    P(c);
    S4;
    V(e);
}
P5(){
    P(d);
    S5;
    V(f);
}
P6(){
    P(e);
    P(f);
    P(g);
    S6;
}

生产者-消费者问题

系统中有一组生产者进程和一组消费者进程,生产者进程每次生产一个产品放入缓冲区,消费者进程每次从缓冲区中取出一个产品并使用。(注:这里的“产品”理解为某种数据)

生产者、消费者共享一个初始为空、大小为n的缓冲区。

• 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。

• 只有缓冲区不空时,消费者才能从中取出产品,否则必须等待。

• 缓冲区是临界资源，各进程必须互斥地访问。

graph LR;
id1[有产品,缓冲区没空,V]--full-->id2[P,消费者消费];
id3[缓冲区没满,V]--empty-->id4[P,生产者生产]

semaphore mutex = 1; //互斥信号量,实现对缓冲区的互斥访问
semaphore empty = n; //同步信号量,表示空闲缓冲区的数量
semaphore full = 0;//同步信号量,表示产品的数量,也即非空缓冲区的数量
producer(){//生产者
    while(1){
    	生产一个产品;
    	P(empty);//消耗一个空闲缓冲区
    	P(mutex);
    	把产品放入缓冲区;
    	V(mutex);
    	V(full);//增加一个产品
    }
}
consumer(){//消费者
    while(1){
        P(full);//消耗一个产品
        P(mutex);
        从缓冲区取出一个产品;
        V(mutex);
        V(empty);//增加一个空闲缓冲区
        使用产品;
    }
}

为了避免死锁，实现互斥的P操作一定要在实现同步的P操作之后。

上面的例子中，如果颠倒P(empty);和P(mutex);的顺序就会造成死锁

但是V(mutex);和V(full);的顺序可以交换

生产产品和使用产品的代码可以放在PV操作之间，但是为了让临界区的代码尽可能短，一般不会将这些代码放在PV操作之间

多生产者-多消费者问题

桌子上有一只盘子,每次只能向其中放入一个水果。

爸爸专向盘子中放苹果,妈妈专向盘子中放橘子,儿子专等着吃盘子中的橘子,女儿专等着吃盘子中的苹果。

只有盘子空时,爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时,儿子或女儿可以从盘子中取出水果。

互斥关系：对缓冲区(盘子)的访问要互斥地进行

同步关系（一前一后）：

1. 父亲将苹果放入盘子后,女儿才能取苹果

2. 母亲将橘子放入盘子后,儿子才能取橘子

3. 只有盘子为空时,父亲或母亲才能放入水果

semaphore mutex = 1; //实现互斥访问盘子(缓冲区)
semaphore apple = 0; //盘子中有几个苹果
semaphore orange = 0; //盘子中有几个橘子
semaphore plate = 1;//盘子中还可以放多少个水果
dad(){
    while(1){
        准备一个🍎;
        P(plate);
        P(mutex);
        把🍎放入盘子;
        V(mutex);
        V(apple);
    }
}
mom(){
    while(1){
        准备一个🍊;
        P(plate);
        P(mutex);
        把🍊放入盘子;
        V(mutex);
        V(orange);
    }
}
daughter(){
    while(1){
        P(apple);
        P(mutex);
        从盘中取走🍎;
        V(mutex);
        V(plate);
        吃掉🍎;
    }
}
son(){
    while(1){
        P(orange);
        P(mutex);
        从盘中取走🍊;
        V(mutex);
        V(plate);
        吃掉🍊;
    }
}

在这个例子中，不用mutex，也可以实现对盘子的互斥访问

吸烟者问题

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它,但是要卷起并抽掉一支烟,抽烟者需要有三种材料:烟草、纸和胶水。

三个抽烟者中,第一个拥有烟草、第二个拥有纸、第三个拥有胶水。

供应者进程无限地提供三种材料,供应者每次将两种材料放桌子上, 拥有剩下那种材料的抽烟者卷一根烟并抽掉它,并给供应者进程一个信号告诉完成了,供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）

semaphore offer1 = 0; //桌上组合一的数量
semaphore offer2 = 0; //桌上组合二的数量
semaphore offer3 = 0; //桌上组合三的数量
semaphore finish = 0; //抽烟是否完成
int i = 0;//用于实现“三个抽烟者轮流抽烟”
provider(){
    while(1){
        if(i==0){
            把组合一放在桌儿上;
            V(offer1);
        }else if(i==1){
            把组合二放在桌儿上;
            V(offer2);
        }else{
            把组合三放在桌儿上;
            V(offer3);
        }
    }
    i=(i+1)%3;
    P(finish);
}
smoker1(){
    while(1){
        P(offer1);
        从桌上拿走组合一;卷烟;抽掉;
        V(finish);
    }
}
smoker2(){
    while(1){
        P(offer2);
        从桌上拿走组合二;卷烟;抽掉;
        V(finish);
    }
}
smoker3(){
    while(1){
        P(offer3);
        从桌上拿走组合三;卷烟;抽掉;
        V(finish);
    }
}

读者写者问题

有读者和写者两组并发进程,共享一个文件。

当两个或两个以上的读进程同时访问共享数据时不会产生副作用,但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。

因此要求:

1. 允许多个读者可以同时对文件执行读操作;

2. 只允许一个写者往文件中写信息

3. 任一写者在完成写操作之前不允许其他读者或写者工作

4. 写者执行写操作前,应让已有的读者和写者全部退出。

实现代码

semaphore rw=1;//用于实现对共享文件的互斥访问
int count = 0;//记录当前有几个读进程在访问文件
semaphore mutex = 1;//用于保证对count变量的互斥访问
semaphore w = 1;//用于实现“读写公平”
writer(){
    while(1){
        P(w);
        P(rw);
        写文件;
        V(rw);
        V(w);
    }
}
reader(){
    while(1){
        P(w);
        P(mutex);
        if(count==0)
            P(rw);
        count++;
        V(mutex);
        V(w);
        读文件;
        P(mutex);
        count--;
        if(count==0)
            V(rw);
        V(mutex);
    }
}

哲学家进餐问题

一张圆桌上坐着5名哲学家,每两个哲学家之间的桌上摆一根筷子,桌子的中间是一碗米饭。

哲学家们倾注毕生的精力用于思考和进餐,哲学家在思考时,并不影响他人。只有当哲学家饥饿时,才试图拿起左、右两根筷子(一根一根地拿起)。

如果筷子已在他人手上,则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐,当进餐完毕后,放下筷子继续思考。

要求：避免死锁

解决方案

①可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的

②要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子,而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子,另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。

③仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。

管程

为什么要引入管程？

解决信号量机制编程麻烦、易出错的问题

组成：

• 共享数据结构
• 组成对数据结构初始化的语句
• 一组用来访问数据结构的过程（函数)

基本特征：

• 各外部进程/线程只能通过管程提供的特定“入口"才能访问共享数据
• 每次仅允许一个进程在管程内执行某个内部过程

补充：

• 各进程必须互斥访问管程的特性是由编译器实现的
• 可在管程中设置条件变量及等待/唤醒操作以解决同步问题

面包师算法

伪代码：

可能会用(Number[j], j) < (Number[i], i)代替number[j] < number[i] || (number[j] == number[i] && j < i)

Entering: array [1..NUM_THREADS] of bool = {false};  
Number: array [1..NUM_THREADS] of integer = {0};  
void lock(integer i) {      
  Entering[i] = true;
  Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
  Entering[i] = false;
  for (integer j = 1; j <= NUM_THREADS; j++) { 
    // Wait until thread j receives its number:
    while (Entering[j]) {} 
    // Wait until all threads with smaller numbers or with the same          
    // number, but with higher priority, finish their work:
    while ((Number[j] != 0) && (number[j] < number[i] || (number[j] == number[i] && j < i))) {}      
  }  
}
void unlock(integer i) {  
  Number[i] = 0;  
}  
void Thread(integer i) {
  while (true) {
    lock(i);
    // The critical section goes here...          
    unlock(i);
    // non-critical section...      
    }
}

当一个线程想要进入临界区时，它必须检查轮到它了。它应该检查每个其他线程的Number值，以确保它是最大的。如果另一个线程具有相同的Number值，则具有最小编号的线程将首先进入临界区。

每个线程只写自己的存储，只读共享。值得注意的是，该算法不是建立在一些较低级别的“原子”操作之上。因此，该算法可用于在缺少同步原语的存储器上实现互斥

数组Entering是必要的，假设变量被删除，两个进程计算相同的Number [i]。如果在设置Number [i]之前优先级较高的进程被抢占，则低优先级进程将看到另一个进程的数量为零，并进入临界区;之后，高优先级进程将忽略较低优先级进程的相等Number [i]，并进入临界区。结果，两个进程可以同时进入临界区。

如果不使用Entering数组，假设最开始总共2个进程，它们的Number值都是0

进程号	0	1
Number值	0	0

进程0首先开始执行lock，当执行完第5行，它计算出 1 + max(Number[1], ..., Number[NUM_THREADS])的值为1，但是没有写回Number[0]时，它被进程1抢占了。

进程1执行完lock没有被打断，进入临界区继续执行，此时的Number表如下

进程号	0	1
Number值	0	1

现在进程0被唤醒，它继续lock操作，把1写回Number[0]，此时的Number表如下

进程号	0	1
Number值	1	1

进程0现在执行第12行代码，它没有被阻塞，也进入了临界区，互斥性被违背了。

2.4 死锁

当一组进程中的每个进程都在等待某个事件（资源)，而仅有这组进程中被阻塞的其他进程才可触发该事件时，则认为该组进程发生了死锁。

资源分为可重用资源（使用后不会耗尽）和消费型资源（例如中断信号）

进程使用资源的正确顺序：申请、使用、释放

死锁发生条件

死锁发生的必要条件

• 互斥：一次只有一个进程使用一个资源，其他进程不能访问分配给其他进程的资源
• 占有等待：当一个进程等待其他进程时,继续占有已分配的资源
• 非抢占：不能强行抢占进程已占有的资源
• 循环等待：存在一个闭合的进程链，每个进程至少占有此链中下一个进程所需的一个资源

资源分配图

表示进程和资源的关系：请求和分配

• 如果资源分配图中没有环，那么系统就没有进程死锁。
• 如果有环，可能存在死锁（并非一定死锁，如果资源实例有多个，资源足够，就不会发生死锁）

预防死锁

破坏上述四个条件的任何一个

破坏互斥条件

如果把只能互斥使用的资源改造为允许共享使用,则系统不会进入死锁状态。

比如:SPOOLing技术。操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备。比如,用SPOOLing技术将打印机改造为共享设备…

该策略的缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。

破坏不剥夺条件

不剥夺条件:

进程所获得的资源在未使用完之前,不能由其他进程强行夺走,只能主动释放。

破坏不剥夺条件：

方案一:

当某个进程请求新的资源得不到满足时,它必须立即释放保持的所有资源,待以后需要时再重新申请。也就是说,即使某些资源尚未使用完,也需要主动释放,从而破坏了不可剥夺条件。

方案二:

当某个进程需要的资源被其他进程所占有的时候,可以由操作系统协助,将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级(比如:剥夺调度方式,就是将处理机资源强行剥夺给优先级更高的进程使用)

该策略的缺点：

1. 实现起来比较复杂。
2. 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
3. 反复地申请和释放资源会增加系统开销,降低系统吞吐量
4. 若采用方案一,意味着只要暂时得不到某个资源,之前获得的那些资源就都需要放弃,以后再重新申请。如果一直发生这样的情况,就会导致进程饥饿。

破坏请求和保持条件

请求和保持条件：

进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。

可以采用静态分配方法,即进程在运行前一次申请完它所需要的全部资源,在它的资源未满足前,不让它投入运行。一旦投入运行后,这些资源就一直归它所有,该进程就不会再请求别的任何资源了。

该策略实现起来简单,但也有明显的缺点:

有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费,资源利用率极低。另外,该策略也有可能导致某些进程饥饿。

graph LR;
id1(A类进程) ---> id2[资源1]
id5(C类进程) ---> id2
id5 --->id4
id3(B类进程) ---> id4[资源2]

破坏循环等待条件

循环等待条件:

存在一种进程资源的循环等待链,链中的每一个进程已获得的资源同时被下一个进程所请求。

可采用顺序资源分配法。首先给系统中的资源编号,规定每个进程必须按编号递增的顺序请求资源,同类资源(即编号相同的资源)一次申请完。

原理分析:一个进程只有已占有小编号的资源时,才有资格申请更大编号的资源。按此规则,已持有大编号资源的进程不可能逆向地回来申请小编号的资源,从而就不会产生循环等待的现象。

该策略的缺点：

1. 不方便增加新的设备,因为可能需要重新分配所有的编号
2. 进程实际使用资源的顺序可能和编号递增顺序不一致,会导致资源浪费
3. 必须按规定次序申请资源,用户编程麻烦。

处理死锁

死锁预防的副作用是设备使用率低，系统吞吐率低

处理死锁有以下方案

• 确保系统永远不会进入死锁状态
  • 死锁预防
  • 死锁避免
• 允许系统进入死锁状态,然后检测和恢复
• 忽略该问题,并假装系统中从未发生死锁
  • 绝大多数操作系统所采用的的方法

资源分配图算法

仅当将申请边转换为分配边不会导致资源分配图中形成循环时,才能授予请求,利用环检测算法,检查安全性

• 需求边Pi-> Rj表示进程Pi可以请求资源Rj，用虚线表示
• 当进程请求资源时,需求边转换为请求边
• 将资源分配给进程时,请求边转换为分配边
• 当流程释放资源时,分配边将重新转换为需求边
• 必须在系统中预先声明资源
• 只有当进程Pi的所有边都为需求边时,才能允许将需求边增加到图中

银行家算法

银行家算法是荷兰学者Dijkstra为银行系统设计的,以确保银行在发放现金贷款时,不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于避免死锁。

核心思想:在进程提出资源申请时,先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态,就暂时不答应这次请求,让该进程先阻塞等待。

银行家算法步骤:

①检查此次申请是否超过了之前声明的最大需求数

②检查此时系统剩余的可用资源是否还能满足这次请求

③试探着分配，更改各数据结构

④用安全性算法检查此次分配是否会导致系统进入不安全状态

死锁的检测和解除

检测死锁的算法：

数据结构: 资源分配图

1)在资源分配图中,找出既不阻塞又不是孤点的进程Pi (即找出一条有向边与它相连,且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。若所有的连接该进程的边均满足上述条件,则这个进程能继续运行直至完成,然后释放它所占有的所有资源)。消去它所有的请求边和分配边,使之称为孤立的结点。

2)进程Pi所释放的资源,可以唤醒某些因等待这些资源而阻塞的进程,原来的阻塞进程可能变为非阻塞进程。根据 1)中的方法进行一系列简化后,若能消去途中所有的边,则称该图是可完全简化的。

死锁定理:如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

死锁的解除

1. 资源剥夺法。挂起(暂时放到外存上)某些死锁进程,并抢占它的资源,将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。

2. 撤销进程法(或称终止进程法)。强制撤销部分、甚至全部死锁进程,并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间,已经接近结束了,一旦被终止可谓功亏一篑,以后还得从头再来。

3. 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

决定对哪个进程动手

1. 进程优先级
2. 已执行多长时间
3. 还要多久能完成
4. 进程已经使用了多少资源
5. 进程是交互式的还是批处理式的

3.1 内存

基础知识

内存管理

内存保护:

方法一：在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界。

方法二:采用重定位寄存器(又称基址寄存器)和界地址寄存器（又称限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。

覆盖与交换

解决内存大小不够的问题

覆盖技术

覆盖技术的思想:将程序分为多个段(多个模块)。常用的段常驻内存,不常用的段在需要时调入内存。

内存中分为一个“固定区”和若干个“覆盖区”。

需要常驻内存的段放在“固定区”中,调入后就不再调出（除非运行结束）

不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存

必须由程序员声明覆盖结构,操作系统完成自动覆盖。缺点: 对用户不透明,增加了用户编程负担。覆盖技术只用于早期的操作系统中，现在已成为历史。

交换技术

交换(对换)技术的设计思想:内存空间紧张时,系统将内存中某些进程暂时换出外存,把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)

等同于 中级调度

1. 具有对换功能的操作系统中,通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件,主要追求存储空间的利用率,因此对文件区空间的管理采用离散分配方式；对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度,因此对换区空间的管理主要追求换入换出速度,因此通常对换区采用连续分配方式(学过文件管理章节后即可理解)。总之,对换区的I/O速度比文件区的更快。
2. 交换通常在许多进程运行且内存吃紧时进行,而系统负荷降低就暂停。例如:在发现许多进程运行时经常发生缺页,就说明内存紧张,此时可以换出一些进程；如果缺页率明显下降,就可以暂停换出。
3. 可优先换出阻塞进程;可换出优先级低的进程;为了防止优先级低的进程在被调入内存后很快又被换出,有的系统还会考虑进程在内存的驻留时间……

(注意: PCB会常驻内存,不会被换出外存)

连续内存分配

动态分区分配算法

算法	算法思想	分区排列顺序	优点	缺点
首次适应	优先使用更小的分区,以保留更多大分区空闲分区	以地址递增次序排列	会有更多的大分区被保留下来，更能满足大进程需求	会产生很多太小的、难以利用的碎片；算法开销大，回收分区后可能需要对空闲分区队列重新排序
最佳适应	优先使用更小的分区,以保留更多大分区	空闲分区以容量递增次序排列	会有更多的大分区被保留下来，更能满足大进程需求	会产生很多太小的、难以利用的碎片；算法开销大，回收分区后可能需要对空闲分区队列重新排序
最坏适应	优先使用更大的分区，以防止产生太小的不可用的碎片	空闲分区以容量递减次序排列	可以减少难以利用的小碎片	大分区容易被用完，不利于大进程；算法开销大（原因同上）
邻近适应	由首次适应演变而来，每次从上次查找结束位置开始查找	空闲分区以地址递增次序排列（可排列成循环链表）	不用每次都从低地址的小分区开始检索。算法开销小（原因同首次适应算法)	会使高地址的大分区也被用完

基本分页存储管理

两级页表

基本分段存储管理方式

虚拟内存管理

• 先进先出FIFO算法
  • 可能出现Belady异常，page fault数量并非单调降低
• OPT最优页面置换算法
  • 替换在将来最长时间内不使用的页面
  • 不可实现，因为不可能预测未来。仅用于理论推导，作为算法可能实现的性能上限
• LRU最小最近使用算法
  • 替换在过去最长时间内不使用的页面
  • 实现方式：
    • 计数器，每次页面被引用了，都将当前时间写到页面的计数器中，替换时选择计数器值最小的页面
    • 堆栈，将被访问的页面移动到栈顶，但是调整页面到栈顶的过程开销大
• 近似LRU算法
  • 用一个8位的字节，记录最近8次访问每个页是否被访问
  • 每次访问页面都将这个字节右移一位，如果页面被访问就在高位填1，否则填0
• 第二次机会算法
  • 每个页有一个标志位
    • 0代表最近未使用，可用于替换
    • 1代表最近使用，扫描到时修改为0
  • 想要替换页面时循环扫描所有页，扫描到0就替换
• 增强型第二次机会算法
  • 通过使用引用位和一致修改位（如果可用）来改进算法
  • 采取有序配对（引用、修改）：
    • (0, 0)最近未使用未修改-要替换的最佳页面
    • (0, 1)最近未使用但已修改-不太好,必须在置换之前将页面写出；
    • (1, 0)最近使用但没有修改-可能很快会再次使用
    • (1, 1)最近使用和修改的-可能很快会再次使用，需要在更换前将页面写出；

优化：页面缓冲

始终保持一个空闲帧池

• 当出现缺页错误时,会像以前一样选择一个牺牲帧
• 将页面读入空闲帧,选择要退出的牺牲帧并添加到空闲池
• 方便时,驱逐牺牲帧,无需等待写出牺牲帧
• 把必须串行的磁盘读和写操作变成可并行的（或对先后顺序不敏感的）

页面替换

本地页面替换：替换进程自身的页面，不影响其他进程，可缓解系统抖动

优先级页面替换：高优先级进程可替换，低优先级进程等待

工作集(Working Set)

一个进程在最近给定时间长度内，所有访问到的页面总数

统计缺页错误率，如果小于给定阈值，减少进程的物理帧，如果大于阈值，增加进程的物理帧

系统抖动

进程的调页时间多于执行时间，那么这个进程就在抖动。或者说，进程的工作集（局部性访问的内存空间）大于总的物理内存大小

另外，操作系统检测到CPU利用率低时，可能会创建更多进程，这会造成恶性循环。

解决方案：

本地页面替换：替换进程自身的页面，不影响其他进程，可缓解系统抖动

优先级页面替换：高优先级进程可替换，低优先级进程等待

杀死并发的进程

4.1 文件

文件的逻辑结构

• 无结构文件
  • 由二进制流或字符流组成,无明显的逻辑结构
• 有结构文件
  • 由记录组成,分为定长记录、可变长记录

文件目录

文件物理结构

用户给出要访问的逻辑块号,操作系统找到该文件对应的目录项(FCB) …

连续分配

物理块号=起始块号+逻辑块号

当然,还需要检查用户提供的逻辑块号是否合法(逻辑块号≥长度就不合法)

优点：可以随机访问磁盘块

缺点：

1. 物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片可以用紧凑来处理碎片，但是需要耗费很大的时间代价。
2. 物理上采用连续分配的文件不方便拓展。

隐式链接分配

从目录项中找到起始块号(即0号块) ,将0号逻辑块读入内存，由此知道1号逻辑块存放的物理块号,于是读入1号逻辑块,再找到2号逻辑块的存放位置…以此类推。因此,读入i号逻辑块,总共需要i+1次磁盘I/O

优点:很方便文件拓展,不会有碎片问题,外存利用率高。

缺点:只支持顺序访问,不支持随机访问,查找效率低,指向下一个盘块的指针也需要耗费少量的存储空间。

显式链接分配

把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表(FAT， File Allocation Table)。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存,并常驻内存。

优点:很方便文件拓展,不会有碎片问题,外存利用率高,并且支持随机访问。相比于隐式链接来说,地址转换时不需要访问磁盘,因此文件的访问效率更高。

缺点:文件分配表的需要占用一定的存储空间。

索引分配

索引分配允许文件离散地分配在各个磁盘块中,系统会为每个文件建立一张索引表,索引表中记录了文件的各个逻辑块对应的物理块

（索引表的功能类似于内存管理中的页表—-建立逻辑页面到物理页之间的映射关系)。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

索引分配方式可以支持随机访问****。文件拓展也很容易实现（只需要给文件分配一个空闲块,并增加一个索引表项即可)

若文件太大,索引表项太多,可以采取以下三种方法解决:

1. 链接方案:如果索引表太大,一个索引块装不下,那么可以将多个索引块链接起来存放。

   缺点:若文件很大,索引表很长,就需要将很多个索引块链接起来。想要找到i号索引块,必须先依次读入0~i-1号索引块,这就导致磁盘I/O次数过多,查找效率低下。

2. 多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用K层索引结构,且顶级索引表未调入内存,则访问一个数据块只需要K+1次读磁盘操作。

   缺点:即使是小文件,访问一个数据块依然需要K+1次读磁盘

3. 混合索引:多种索引分配方式的结合。例如,一个文件的顶级索引表中,既包含直接地址索引(直接指向数据块),又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表) 。

   优点:对于小文件来说,访问一个数据块所需的读磁盘次数更少。

文件存储空间管理

空闲表法

如何分配磁盘块：与内存管理中的动态分区分配很类似,为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。

如何回收磁盘块:与内存管理中的动态分区分配很类似,当回收某个存储区时需要有四种情况——①回收区的前后都没有相邻空闲区；②回收区的前后都是空闲区; 3回收区前面是空闲区; ④回收区后面是空闲区**。总之,回收时需要注意表项的合并问题**。

空闲链表法

空闲盘块链：以盘块为单位组成一条空闲链

操作系统保存着链头、链尾指针。

如何分配: 若某文件申请K个盘块,则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。

如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。

空闲盘区链：以盘区为单位组成一条空闲链

操作系统保存着链头、链尾指针。

如何分配：若某文件申请 K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区,分配给文件。若没有合适的连续空闲块,也可以将不同盘区的盘块同时分配给一个文件,注意分配后可能要修改相应的链指针、盘区大小等数据。

如何回收:若回收区和某个空闲盘区相邻,则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。

位示图法

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	1	0	1	1	1	1	1	1	1	1	1	0	0	0	0
1	1	1	1	0	0	0	1	1	0	0	0	0	0	0	1	0
2	1	1	…
…

位示图:每个二进制位对应一个盘块。在本例中, "0”代表盘块空闲,“1”代表盘块已分配。

如何分配：若文件需要K个块，①顺序扫描位示图，找到K个相邻或不相邻的"0” ; ②根据字号、位号算出对应的盘块号,将相应盘块分配给文件;③将相应位设置为“1”。

如何回收:①根据回收的盘块号计算出对应的字号、位号;②将相应二进制位设为"0”

成组链接法

UNIX采用的策略,适合大型文件系统。理解即可,不方便用文字描述的知识点也很难作为考题

文件的基本操作

文件共享

基于索引结点的共享方式(硬链接)

知识回顾:索引结点,是一种文件目录瘦身策略。由于检索文件时只需用到文件名,因此可以将除了文件名之外的其他信息放到索引结点中。这样目录项就只需要包含文件名、索引结点指针。

索引结点中设置一个链接计数变量count,用于表示链接到本索引结点上的用户目录项数。

基于符号链的共享方式(软链接)

建立一个Link类型的文件，类似于windows的快捷方式

文件保护

• 口令保护
  • 为文件设置一个"口令",用户想要访问文件时需要提供口令,由系统验证口令是否正确
  • 实现开销小，但“口令”一般存放在FCB或索引结点中（也就是存放在系统中）因此不太安全
• 加密保护
  • 用一个"密码"对文件加密,用户想要访问文件时,需要提供相同的"密码"才能正确的解密
  • 安全性高,但加密/解密需要耗费一定的时间(Eg:异或加密)
• 访问控制
  • 用一个访问控制表（ACL)记录各个用户（或各组用户)对文件的访问权限
  • 对文件的访问类型可以分为：读/写/执行/删除 等
  • 实现灵活，可以实现复杂的文件保护功能

4.3 文件系统

性质

文件系统的性质

• 持久性
• 进程间共享
• 结构性，有复杂的组织结构

文件的最小操作集合

• create
• write
• read
• seek
• delete
• truncate（截断）

打开文件不属于基本操作

文件系统的层次结构

用一个例子来辅助记忆文件系统的层次结构：

假设某用户请求删除文件"D:/工作目录/学生信息.xlsx"的最后100条记录。

1. 用户需要通过操作系统提供的接口发出上述请求——用户接口
2. 由于用户提供的是文件的存放路径,因此需要操作系统一层一层地查找目录,找到对应的目录项——文件目录系统
3. 不同的用户对文件有不同的操作权限,因此为了保证安全，需要检查用户是否有访问权限一一存取控制模块（存取控制验证层）
4. 验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址——逻辑文件系统与文件信息缓冲区
5. 知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址——物理文件系统
6. 要删除这条记录，必定要对磁盘设备发出请求——设备管理程序模块
7. 删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收——辅助分配模块

文件系统的全局结构

物理格式化后

逻辑格式化后

open系统调用打开文件的背后过程

虚拟文件系统

虚拟文件系统的特点：

①向上层用户进程提供统一标准的系统调用接口,屏蔽底层具体文件系统的实现差异

②VFS要求下层的文件系统必须实现某些规定的函数功能,如: open/read/write.一个新的文件系统想要在某操作系统上被使用，就必须满足该操作系统VFS的要求

文件系统挂载

①在VFS中注册新挂载的文件系统。内存中的挂载表(mount table)包含每个文件系统的相关信息,包括文件系统类型、容量大小等。

②新挂载的文件系统，要向VFS提供一个函数地址列表

③将新文件系统加到挂载点（mountpoint) ,也就是将新文件系统挂载在某个父目录下

5.1 I-O设备

大容量存储

磁道 track

扇区 sector

柱面 cylinder

磁盘调度：

graph LR;
id1[等待设备可用] ===> id2[等待通道可用]
id2 ===> id3[寻道]
id3 ===> id4[旋转延迟]
id4 ===> id5[数据传送]
id6[设备忙] -->id2
id6 -->id5

磁盘格式化

高级格式化：格式化为文件系统，比如说ext4, fat32

低级格式化：格式化成扇区

磁盘调度

空闲磁盘可以立即处理I/0请求，繁忙磁盘意味着工作必须排队

只需提供LBA(逻辑区块地址)，磁盘设备将其转化为物理的扇区位置，读写数据

调度算法：

• FIFO先来先服务

  总是最公平的算法

• PRI基于优先级：由操作系统设置优先级

• SSTF:最短服务时间优先：选择使磁头臂从当前位置开始移动最少的磁盘I/O请求

• SCAN扫描算法/电梯算法：磁头往一个固定的方向移动，直到访问到该方向的最后一个请求，就折返

  是不公平的算法，因为不同请求序列的性能不同

• CSCAN扫描算法：限制扫描只能沿一个方向，不允许双向扫描

• N步SACN策略：准备若干长度为N的队列，队列内部使用SCAN算法扫描，队列间先来先服务

• FSCAN：准备2个队列，每次对一个队列SCAN扫描，另一个队列接收新的任务但不执行

进程更有可能在读的时候被阻塞，因为写的请求会收到互斥机制更严格的限制

linux的截止时间调度器

实现四个队列： 2个读取队列和2个写入队列

• 1个读和1个写队列按LBA顺序排序,基本上实现了C-SCAN
• 按FCFS顺序排序的1个读队列和1个写队列
• 批量发送的所有I/O请求都按该队列的顺序排序
• 每批处理后,检查FCFS中是否有任何请求早于配置的时间(默认为500毫秒）
  • 如果是，将为下一批I/O选择包含该请求的LBA队列

RAID

• RAID0: 没有冗余，将一个大文件分为多个strip，存在不同的磁盘，可以提高并行性，性能好
• RAID1: 数据1:1复制，可靠性高，性能比RAID0快
• RAID2: 在冗余磁盘存储海明码保证可靠性
• RAID3: 在冗余磁盘使用Bit-interleaved parity保证可靠性，需要更少冗余盘
• RAID4: 按照块Block-interleaved parity保证可靠性
• RAID5: 和RAID4相似，将校验码分散到所有磁盘
• RAID6: 和RAID4相似，校验码存2份，进一步保证可靠性

I-O设备的概念和分类

I-O控制器

I/O控制器的功能

• 接受和识别CPU发出的命令

  • 如CPU发来的 read/write 命令，I/O控制器中会有相应的控制寄存器来存放命令和参数

• 向CPU报告设备的状态

  • I/O控制器中会有相应的状态寄存器，用于记录I/O设备的当前状态。如：1表示空闲，0表示忙碌

• 数据交换

  • I/O控制器中会设置相应的数据寄存器。输出时，数据寄存器用于暂存CPU发来的数据，之后再由控制器传送设备。输入时，数据寄存器用于暂存设备发来的数据，之后CPU从数据寄存器中取走数据。

• 地址识别

  • 类似于内存的地址，为了区分设备控制器中的各个寄存器，也需要给各个寄存器设置一个特定的“地址”。I/O控制器通过CPU提供的“地址”来判断CPU要读/写的是哪个寄存器

组成

• CPU与控制器之间的接口(实现控制器与CPU之间的通信)
• I/O逻辑(负责识别CPU发出的命令,并向设备发出命令)
• 控制器与设备之间的接口（实现控制器与设备之间的通信）

两种寄存器编制方式

• 内存映射I/O
• 寄存器独立编制

I-O控制方式

计组学过，这里简略一点

轮询式

对于I/O的每个字节

1. 从状态寄存器读取忙位,直到该位清零
2. 主机设置读或写位,如果写入,则将数据复制到数据输出寄存器中
3. 主机设置命令就绪位
4. 控制器设置忙位
5. 控制器读取命令寄存器，并看到命令。从数据输出寄存器中读取一个字节，并向设备执行I/O操作
6. 传输完成时,控制器清除忙位、错误位、命令准备位

中断式

graph TD;
id1[设备驱动初始化I/O请求] --CPU在执行一条指令后检查中断请求-->id2[CPU收到中断请求,分发给相应中断服务例程]
id2 --> id3[中断服务例程进行中断处理]
id3 --> id4[CPU恢复被中断进程的执行]
id4 --> id1
id1 ==> id5(IO控制器初始化IO操作)
id5 ==> id6(IO控制器在操作完成或错误后产生中断)
id6 ==> id2

DMA

DMA控制器被集成在CPU上

• CPU干预的频率：仅在传送一个或多个数据块的开始和结束时，才需要CPU干预

• 数据传送的单位：每次读/写一个或多个块(注意:每次读写的只能是连续的多个块,且这些块读入内存后在内存中也必须是连续的)

• 数据的流向(不再需要经过CPU)

  • 读操作（数据输入）: I/O设备→内存
  • 写操作（数据输出）：内存→I/O设备

• 主要缺点和主要优点

  • 优点:数据传输以“块”为单位, CPU介入频率进一步降低。数据的传输不再需要先经过CPU再写入内存,数据传输效率进一步增加。CPU和I/O设备的并行性得到提升。
  • 缺点: CPU每发出一条I/O指令,只能读/写一个或多个连续的数据块。

通道

通道：一种硬件，可以理解为是“弱鸡版的CPU”。通道可以识别并执行一系列通道指令。与CPU相比，通道可以执行的指令很单一，并且通道程序是放在主机内存中的，也就是说通道与CPU共享内存

• CPU干预的频率
  • 极低,通道会根据CPU的指示执行相应的通道程序,只有完成一组数据块的读/写后才需要发出中断信号,请求CPU干预
• 数据传送的单位
  • 每次读/写一组数据块
• 数据的流向(在通道的控制下进行)
  • 读操作（数据输入): I/O设备→内存
  • 写操作（数据输出): 内存→I/O设备
• 主要缺点和主要优点
  • 缺点:实现复杂,需要专门的通道硬件支持
  • 优点: CPU、通道、I/O设备可并行工作,资源利用率很高。

I-O软件层次结构

逻辑设备表(LUT)

示例：

逻辑设备名	物理设备名	驱动程序入口地址
/dev/打印机1	3	1024
/dev/打印机2	5	2046
…	…	…

输入输出应用程序接口

阻塞/非阻塞I-O

• 阻塞I/O： 应用程序发出I/O系统调用，进程需转为阻塞态筹待。
  • eg：字符设备接口——从键盘读一个字符 get
• 非阻塞I/O应用程序发出I/O系统调用。
  • 系统调用可迅速返回,进程无需阻塞等待。
  • eg：块设备接口——往磁盘写数据 write

5.2 IO核心子系统

IO核心子系统实际要实现上图中间三层的功能

考研中，我们需要重点理解和掌握的功能是: I/O调度、设备保护、假脱机技术（SPOOLing技术）、设备分配与回收、缓冲区管理（即缓冲与高速缓存）

设备保护：

操作系统需要实现文件保护功能,不同的用户对各个文件有不同的访问权限(如:只读、读和写等）。

在UNIX系统中,设备被看做是一种特殊的文件,每个设备也会有对应的FCB。当用户请求访问某个设备时,系统根据FCB中记录的信息来判断该用户是否有相应的访问权限,以此实现“设备保护”的功能。(参考“文件保护”小节)

假脱机技术

• 又叫SPOOLing技术，用软件的方式模拟脱机技术
• 输入井和输出井——模拟脱机输入/输出时的磁带
• 输入进程和输出进程——模拟脱机输入/输出时的外围控制机
• 输入缓冲区和输出缓冲区——内存中的缓冲区，输入、输出时的“中转站”

用于共享打印机

当多个用户进程提出输出打印的请求时,系统会答应它们的请求,但是并不是真正把打印机分配给他们,而是由假脱机管理进程为每个进程做两件事:

(1)在磁盘输出井中为进程申请一个空闲缓冲区(也就是说,这个缓冲区是在磁盘上的) ,并将要打印的数据送入其中；

(2)为用户进程申请一张空白的打印请求表,并将用户的打印请求填入表中(其实就是用来说明用户的打印数据存放位置等信息的)，再将该表挂到假脱机文件队列上。

当打印机空闲时,输出进程会从文件队列的队头取出一张打印请求表,并根据表中的要求将要打印的数据从输出井传送到输出缓冲区,再输出到打印机进行打印。用这种方式可依次处理完全部的打印任务

虽然系统中只有一个台打印机,但每个进程提出打印请求时,系统都会为在输出井中为其分配一个存储区(相当于分配了一个逻辑设备),使每个用户进程都觉得自己在独占一台打印机,从而实现对打印机的共享。

SPOOLing技术可以把一台物理设备虚拟成逻辑上的多台设备,可将独占式设备改造成共享设备。

设备的分配与回收

设备的固有属性可分为三种：独占设备、共享设备、虚拟设备。

• 独占设备: 一个时段只能分配给一个进程（如打印机）
• 共享设备: 可同时分配给多个进程使用（如磁盘) ,各进程往往是宏观上同时共享使用设备,而微观上交替使用。
• 虚拟设备: 采用SPOOLing技术将独占设备改造成虚拟的共享设备,可同时分配给多个进程使用(如采用SPOOLing技术实现的共享打印机)

设备的分配算法：

• 先来先服务
• 优先级高者优先
• 短任务优先

从进程运行的安全性上考虑,设备分配有两种方式:

• 安全分配方式:为进程分配一个设备后就将进程阻塞,本次1/0完成后才将进程唤醒。
  • 一个时段内每个进程只能使用一个设备
  • 优点：破坏了“请求和保持”条件，不会死锁
  • 缺点：对于一个进程来说，CPU和I/O设备只能串行工作
• 不安全分配方式:进程发出I/O请求后,系统为其分配I/O设备,进程可继续执行,之后还可以发出新的I/O请求。只有某个I/O请求得不到满足时才将进程阻塞。
  • 一个进程可以同时使用多个设备
  • 优点:进程的计算任务和I/O任务可以并行处理,使进程迅速推进
  • 缺点:有可能发生死锁(死锁避免、死锁的检测和解除)

静态分配和动态分配：

• 静态分配:进程运行前为其分配全部所需资源,运行结束后归还资源
  • 破坏了“请求和保持”条件，不会发生死锁
• 动态分配：进程运行过程中动态申请设备资源

设备分配管理中的数据结构

设备控制表（DCT）：系统为每个设备配置一张DCT，用于记录设备情况

• 设备类型如：打印机/扫描仪/键盘
• 设备标识符: 即物理设备名,系统中的每个设备的物理设备名唯一
• 设备状态: 忙碌/空闲/故障…
• 指向控制器表的指针: 每个设备由一个控制器控制，该指针可找到相应控制器的信息
• 重复执行次数或时间: 当重复执行多次I/O操作后仍不成功，才认为此次I/O失败
• 设备队列的队首指针: 指向正在等待该设备的进程队列（由进程PCB组成队列)

控制器控制表(COCT) :每个设备控制器都会对应一张COCT。操作系统根据COCT的信息对控制器进行操作和管理。

• 控制器标识符: 各个控制器的唯一ID
• 控制器状态: 忙碌/空闲/故障…
• 指向通道表的指针: 每个控制器由一个通道控制，该指针可找到相应通道的信息
• 控制器队列的队首指针
• 控制器队列的队尾指针: 指向正在等待该控制器的进程队列(由进程PCB组成队列)

通道控制表(CHCT) :每个通道都会对应一张CHCT。操作系统根据CHCT的信息对通道进行操作和管理。

• 通道标识符: 各个通道的唯一ID
• 通道状态: 忙碌/空闲/故障…
• 与通道连接的控制器表首址: 可通过该指针找到该通道管理的所有控制器相关信息（COCT）
• 通道队列的队首指针
• 通道队列的队尾指针: 指向正在等待该通道的进程队列（由进程PCB组成队列

系统设备表(SDT) :记录了系统中全部设备的情况,每个设备对应一个表目。

每个表目包括：设备类型、设备标识符、DCT（设备控制表)、驱动程序入口

设备分配的步骤

①根据进程请求的逻辑设备名查找SDT（注：用户编程时提供的逻辑设备名其实就是“设备类型”）

②查找SDT,找到用户进程指定类型的、并且空闲的设备,将其分配给该进程。操作系统在逻辑设备表(LUT)中新增一个表项。

③根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程。

④根据COCT找到CHCT,若通道忙碌则将进程PCB挂到通道等待队列中,不忙碌则将通道分配给进程。

重复逻辑设备表的设置问题

• 整个系统只有一张LUT：各用户所用的逻辑设备名不允许

• 每个用户一张LUT:各个用户的逻辑设备名可重复