进程管理

操作系统的基本概念

操作系统的定义：能有效地组织和管理系统中的各种软/硬件资源，合理地组织计算机系统的工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口。

操作系统两个重要的作用：

1. 通过资源管理提高计算机系统的效率。

2. 改善人机界面向用户提供友好的工作环境。

操作系统的 4 个特征：并发性、共享性、虚拟性和不确定性。

操作系统的五大功能：进程管理、文件管理、存储管理、设备管理和作业管理。

进程的基本概念

进程是程序的一次执行。

进程通常是由程序、数据和进程控制块（PCB）组成的。

进程是资源分配和独立运行的基本单位，进程两个基本属性：可拥有资源的独立单位；可独立调度和分配的基本单位。

进程的状态转换

运行：当一个进程在处理机上运行时，则称该进程处于运行状态。

就绪：一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态。

阻塞：也称等待或睡眠状态，一个进程正在等待某一事件发生而暂时停止运行。

进程间的同步与互斥

进程间的同步：是指在系统中一些需要相互合作，协同工作的进程，这样的相互联系称为进程的同步。

进程间的互斥：是指系统中多个进程因争用临界资源而互斥执行。

临界资源：是指有些资源一次只能供一个进程使用。如打印机、共享变量等。

信号量机制（P、V操作）

信号量是一个整型变量，根据控制对象的不同被赋予不同的值。

1. 公用信号量：实现进程间的互斥，初值为 1 或资源的数目。
2. 私用信号量：实现进程间的同步，初值为 0 或某个正整数。

信号量 S 的物理意义：S≥0 表示某资源的可用数，S<0，则其绝对值表示阻塞队列中等待该资源的进程数。

PV 操作是实现进程同步与互斥的常用方法，P 操作和 V 操作是低级通信原语，在执行期间不可分割。其中，P 操作表示申请一个资源，V 操作表示释放一个资源。

P 操作

P 操作的定义：S=S-1，若 S≥0，则执行 P 操作的进程继续执行；若 S<0，则置该进程为阻塞状态（因为无可用资源），并将其插入阻塞队列。

P操作可以理解为

if ((S = S - 1) >= 0)
//继续执行本进程
else
//(S = S - 1) < 0
//挂起本进程（本进程等待），转到另一个进程

V 操作

V 操作定义：S=S+1，若 S>0，则执行 V 操作的进程继续执行；若 S≤0，则从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行 V 操作的进程继续。

V 操作可以理解为

if ((S = S + 1 ) > 0)
//不唤醒队列中的等待进程，继续执行本进程
else
//(S = S + 1) <= 0
//唤醒队列中的等待进程，同时继续执行本进程

生产者消费者问题

生产者进程 P1 不断地生产产品送入缓冲区，消费者进程 P2 不断地从缓冲区中取产品消费。

S1：同步/互斥信号量，初值为 1，代表缓冲区可放入的产品数量

S2：同步信号量，初值为 0，代表缓冲区可消费的产品数量

一个生产者和一个消费者，缓冲区中可存放 n 件产品，生产者不断地生产产品，消费者不断地消费产品，如何利用 PV 操作实现生产者和消费者的同步。

S： 互斥信号量，初值为 1

S1：同步信号量，初值为 n，代表缓冲区中还可放入的产品数量

S2：同步信号量，初值为 0，代表缓冲区中还有多少产品

进程调度

• 高级调度：又称“长调度”“作业调度”或“接纳调度”，它决定处于输入池中的哪个后备作业可以调入主系统做好运行的准备，成为一个或一组就绪进程。
• 中级调度：又称“中程调度”或“对换调度”，它决定于交换区中的哪个就绪进程可以调入内存， 以便直接参与对 CPU 的竞争。
• 低级调度：又称“短程调度”或“进程调度”，它决定处于内存中的哪个就绪进程可以占用 CPU 。 低级调度是操作系统中最活跃、最重要的调度程序，对系统的影响很大。

4 种常用的进程调度算法

1. 先来先服务：有利于长作业，不利于短作业；有利于 CPU 繁忙的作业，不利于 I/O 繁忙的作业。主要用于宏观调度。
2. 时间片轮转：主要用于微观调度，通过时间片轮转提高进程并发性和响应时 间特性，从而提高资源的利用率。
3. 优先级调度：让每一个进程都拥有一个优先数，数值大的表示优先级高，系 统在调度时总选择优先数大的占用 CPU。分为静态优先级和动态优先级两种。
4. 多级反馈调度：是时间片轮转算法和优先级算法的综合与发展。优点有：第一，照顾了短进程以提高系统吞吐量，缩短了平均周转时间；第二，照顾 I/O型 进程 以获得较好的 I/O 设备利用率和缩短响应时间；第三，不必估计进程的执行时间，动态调节优先级。

死锁

死锁：是指两个以上的进程互相都要求对方已经占有的资源导致无法继续运行下去的现象。

例：现有5个进程，每个进程都需要4个资源，而系统一共有15个资源， 会发生死锁吗？

A	B	C	D	E

系统中共有 n 个进程共享同一类资源，当每个进程都需要 k 个资源时，至少需要多少个资源才不会发生死锁？

至少需要资源：M =(k-1)×n+1

产生死锁的 4 个必要条件：互斥条件、请求保持条件、不可剥夺条件、环路条件。

死锁的处理策略有：鸵鸟策略、预防策略、避免策略和检测与解除死锁。

死锁预防：采用某种策略限制并发进程对资源的请求。

死锁避免：如银行家算法。

死锁检测：系统定时地运行一个程序来检测是否发生死锁，若有，则设法加以解除。

死锁解除：有资源剥夺法和撤销进程法。

线程

进程两个基本属性：可拥有资源的独立单位；可独立调度和分配的基本单位。

引入线程后：线程作为调度和分配的基本单位，进程作为独立分配资源的单位。

一个进程中有多个线程，共享该进程的资源。

线程分为用户级线程和内核支持线程。

用户级线程不依赖于内核。该类线程的创建、撤销和切换都不利用系统调用来实现。

内核支持线程依赖于内核。该类线程的创建、撤销和切换都利用系统调用来实现。

线程是进程中的一个实体，是被系统独立分配和调度的基本单位，线程基本上不拥有资源，只拥有一点运行中必不可少的资源（如程序计数器、一组寄存器和栈），它可与同属一个进程的其他线程共享进程所拥有的全部资源。

线程也具有就绪、运行和阻塞3种基本状态，由于线程具有传统进程所具有的特性，故称为“轻型进程”；传统进程称为“重型进程”。线程可创建另一个线程，同一个进程中的多个线程可并发执行。

存储管理

基本概念

逻辑地址（虚拟地址、相对地址）：程序员使用的地址只是用符号命名的一个地址，称为符号名地址，这个地址并不是主存中真实存在的地址。

物理地址（绝对地址）：是主存中真实存在的地址

地址重定位

一个程序，没有运行时，存储在外存，程序运行时，需要装载到内存中，就需要把程序中的指令和数据的逻辑地址转换为对应的物理地址，这个转换的过程称为地址重定位。

静态重定位：在程序装入主存时已经完成了逻辑地址到物理地址的变化，在程序的执行期间不会再发生变化。

动态重定位：在程序运行期间完成逻辑地址到物理地址的变换。

分区存储管理

把主存划分成若干个区域，每个区域分配给一个作业使用。这就是分区存储管理方式。分为固定分区、可变分区和可重定位分区。

1. 固定分区：系统生成时已经分好区。
2. 可变分区：是一种动态分区方式，存储空间的划分是在作业装入时进行的，故分区的个数是可变的，分区的大小刚好等于作业的大小。
3. 可重定位分区：分配好的区域可以移动。

分页存储管理

分页原理

• 将进程的地址空间划分成若干个大小相等的区域，称为页。
• 将主存的空间也划分成与页相同大小的若干个物理块，称为块或页框。
• 在为进程分配主存时，将进程中若干页分别装入多个不相邻接的块中。

地址结构

页表

当进程的多个页面离散地分配到主存的多个物理块时，系统应能保证在主存中找到进程要访问的页面所对应的物理块，为此，系统为每个进程建立了一张页面映射表，简称页表。

分段存储管理

在分段存储管理中，将用户程序或作业的地址空间按内容划分为段，比如主程序一段，子程序一段，数据专门放一段，每个段的长度是不等的，但是每个段占用一个连续的分区。进程中的各个段可以离散地分配到主存的不同分区中。在系统中为每个进程建立一张段映射表，简称为“段表”。

段页式存储管理

先将整个主存划分成大小相等的存储块（页框），将用户程序按程序的逻辑关系分为若干个段，然后再将段划分成页。

段页式系统中同时有段表和页表：

• 段表：段号、页表始址、页表长度。
• 页表：页号、物理块号。
• 逻辑地址：段号、段内页号、页内地址
• 物理地址：块号、页内地址

虚拟存储管理

程序局部性原理：程序在执行时将呈现出局部性规律，即在一段时间内，程序的执行仅限于某个部分，它所访问的存储空间也局限于某个区域内。

1. 时间局限性：程序中的某条指令一旦执行，则不久的将来很有可能再次被访问；某个存储单元如果被访问，不久的将来它很可能再次被访问。
2. 空间局限性：一旦程序访问了某个存储单元，则不久的将来，其附近的存储单元也最有可能被访问。

如果我们运行程序的时候，允许将作业的一部分装入主存即可运行程序，而其余部分可以暂时留在磁盘上，等需要的时候再装入主存。这样一来，一个小的主存空间就可以运行比它大的一个作业。从用户角度看，系统具有的主存容量比实际的主存容量要大得多，称为虚拟存储器。

请求分页系统的实现

在纯分页的基础上增加了请求调页功能，页面置换功能。

在请求分页系统中，每当所要访问的页面不在主存时便产生一个缺页中断。

页面置换算法

1. 最佳置换算法：是一种理想化的算法，即选择那些是永不使用的，或者是在最长时间内不再被访问的页面置换出去。
2. 先进先出置换算法（FIFO）：优先淘汰最先进入主存的页面，也就是在内存中停留时间最长的页面。
3. 最近最少未使用算法（LRU）：优先淘汰最近这段时间用得最少的页面。系统为每一个页面设置一个访问字段，记录这个页面自上次被访问以来所经历的时间 T ，当要淘汰一个页面时，选择 T 最大的页面。
4. 最近未用置换算法（NUR）：优先淘汰最近一段时间未引用过的页面。系统为每一个页面设置一个访问位，访问位为 1 代表访问过，为 0 代表没有被访问过，置换页面时选择访问位为 0 的置换出去。

设备管理

I/O设备管理软件

设备管理的目标主要是如何提高设备的利用率，即提高 CPU 与 I/O 设备之间的并行操作速度，并为用户提供方便、统一的界面。

为了提供设备的利用率，我们采用了“分层构造”的思想，即把设备管理软件组织成为一系列的层次。

主要分为4层：中断处理程序、设备驱动程序、与设备无关的系统软件和用户级软件

各层之间既相互独立，又彼此协作。

例：某用户进程现在需要读取硬盘中的数据。

1. 与设备无关软件检查高速缓存中有没有要读的数据块，如果有，则直接从高速缓存中调取；如果没有，则调用设备驱动程序，向 I/O 硬件发出一个请求。
2. 用户进程转为阻塞状态，等待磁盘操作的完成。磁盘操作完成时，硬件产生一个中断，转入中断处理程序。
3. 中断处理程序检查中断的原因，认识到这时磁盘读取数据的操作已经完成，于是唤醒用户进程取回从磁盘读取的信息，此次 I/O 请求结束。
4. 用户进程得到了需要读取的数据内容，由阻塞转为就绪状态，继续运行。

设备管理采用的相关技术

1. 通道技术
2. DMA技术
3. 缓冲技术
4. Spooling技术

Spooling技术

目的：缓和 CPU 的高速性和 I/O 设备的低速性之间的矛盾。

原理：Spooling 技术引入了两个程序，分别实现脱机输入输出操作。预输入程序将输入设备上的数据通过输入缓冲区再传输到高速磁盘的输入井；缓输出程序将高速磁盘中输出井中的数据通过输出缓冲区传输到输出设备。CPU 读写数据只需要在高速磁盘上进行，大大提高了工作效率。而且输入输出操作与 CPU 数据的处理同时进行，这种在联机情况下实现的输入输出与 CPU 工作并行的技术叫做 Spooling 或假脱机操作。

磁盘调度算法

磁盘调度分为移臂调度和旋转调度两类，先进行移臂调度，再进行旋转调度。磁盘调度的目标是使磁盘的平均寻道时间最少。

读取磁盘数据的时间 = 寻道时间 + 旋转延迟 + 数据传输时间

移臂调度算法

1. 先来先服务：根据进程请求的先后次序进行调度。保证所有进程的请求都得到回应，但是平均寻道时间可能很长。
2. 最短寻道时间优先：选择访问的磁道与当前磁头所在的磁道距离最近的，使得每次的寻道时间最短。
3. 扫描算法（类似电梯调度）：不仅考虑到要访问的磁道与当前磁道的距离，更优先考虑的是磁头当前的移动方向。
4. 单向扫描调度算法：在扫描算法的基础上，规定磁头只做单向移动。

旋转调度算法

1. 如果进程请求访问的是不同编号的扇区（无论是否在同一磁道），则总是让首先到达磁头位置下的扇区先进行读写操作。
2. 如果进程请求访问的是相同编号的扇区（无论是否在同一磁道），旋转调度时可以任选一个扇区进行读写操作。

文件管理与作业管理

文件的结构和组织

文件的逻辑结构：从用户角度看到的文件组织形式就是文件的逻辑结构，但实际上这些文件在内存上的存放方式可能并不是这样的。

1. 有结构的记录式文件
2. 无结构的流式文件

文件的物理结构：从实现的角度看，文件在存储器上的存放方式。
1. 连续结构
2. 链接结构
3. 索引结构
4. 多个物理块的索引表

文件的目录结构

1. 一级目录结构：只有一张目录表，不允许重名，查找速度慢，不能实现文件共享。
2. 二级目录结构：由主文件目录和用户目录组成。
3. 多级目录结构：我们熟悉的 Windows 系统，以及 UNIX 系统都采用这种多级目录结构。

• 绝对路径：是指从根目录“\”开始的完整文件名，即它是由从根目录开始的所有目录名以及文件名构成。
• 相对路径：是从当前工作目录下的路径名。

文件存储空间的管理

在将文件保存到外存时，我们首先要知道哪些存储空间是“占用”的，哪些存储空间是“空闲”的。因此我们需要对磁盘空间进行管理。

常用的空闲空间的管理方法有空闲区表、位示图、空闲块链和成组链
接法。

1. 空闲区表。操作系统为磁盘的所有空闲区建立一张空闲表。它适用于连续文件结构。
   

2. 位示图：在外存上建立一张位示图（bitmap），记录文件存储器
   的使用情况。每一位对应文件存储器上的一个物理块，0 表示空闲，1 表示占用。

   

3. 空闲块链：每一个空闲物理块中设置一个指针，它指向下一个空
   闲物理块，所有空闲物理块构成一个链表，链表的头指针放在文件存储器的一个特定位置上（如管理块中）。

4. 成组链接法。在系统中将空闲块分成若干个组，每 100 个空闲块为一组，每组的第一个空闲块登记了下一组空闲块的物理盘块号和空闲块总数。

作业调度算法

1. 先来先服务：按作业到达的先后顺序进行调度。

2. 短作业优先：按作业运行时间的长短进行调度，即启动要求运行时间最短的作业。

3. 响应比高优先：响应比高的作业优先启动。

   响应比：

   $R_P = \dfrac{作业响应时间}{作业执行时间}=\dfrac{(作业等待时间+作业执行时间)}{作业执行时间}$

4. 优先级调度算法：按照系统设定的优先级或者用户指定的优先级，优先级高的先调度。

5. 均衡调度算法：根据系统的运行情况和作业本身的特性对作业进行分类，力求均衡地使用系统的各种资源，即注意发挥系统效率，又使用户满意。