操作系统

Huang_Chun2024-07-092024-07-09

起步

操作系统的概念

操作系统是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源分配；以提供给用户和其他软件方便的接口和环境；它是计算机系统中最基本的系统软件

操作系统是系统资源的管理者

向上层提供方便易用的服务

是最接近硬件的一层软件

系统资源的管理者

提供的功能

处理机管理

存储器管理

文件管理

设备管理

目标：安全，高效

执行一个程序前需要将该程序放到内存中，才能被cpu处理

向上层提供方便易用的服务

最接近硬件的层次

操作系统对硬件技巧的拓展：将CPU，内存，磁盘，显示器，键盘等硬件合理地组织起来，让各种硬件能够相互协调配合，实现更多更复杂的功能。

操作系统的发展与分类

手工操作阶段：用户独占全机，人机速度矛盾导致资源利用率极低。

批处理阶段——单道批处理系统：引入脱机输入、输出技术，并有监督程序否则控制作业的输入、输出。

优点：缓解了一定程度的人机速度矛盾，资源利用率有所提升。

缺点：内存中仅能有遇到程序运行，但是CPU有大量的时间是在空闲等待I/O完成。

多道批处理系统：每次往内存中读入多道程序，支持多道程序并发运行。

分时操作系统：计算机以时间片为单位轮流为各个用户、作业服务，各个用户可通过终端与计算机进行交互。

优点：用户请求可以被即时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互登录，感受不到别人的存在。

不能优点处理一些紧急任务。

实时操作系统：在实时操作系统的控制下，计算机系统接收到外部信号后即时进行处理，并且要在严格的时限内处理完事件。实时操作系统的主要特点是及时性和可靠性。

总结

操作系统运行机制

中断和异常

中断的作用：中断会使CPU有用户态变为内核态，是操作系统重新夺回对CPU的控制权

CPU上会运行两种程序，一种是操作系统内核程序，一种是应用程序

中断是让操作系统内核夺回CPU使用权的唯一途径

中断的类型

内中断：与当前执行的指令有关，中断信号来源于CPU内部

例子1：试图在用户台下执行特权指令

例子2：执行除法指令是发现除数为0

例子3：有时候引用程序想请求操作系统内核的服务，此时会执行一条特殊的指令——陷入指令，该指令会引发一个内部中断信号。

若当前执行的指令是非法的，则会引发一个中断信号

外中断：与当前执行的指令无关，中断信号来源于CPU外部。

例子1：时钟中断——有时钟部件发来的中断信号。

例子2：I/O中断——有输入、输出设备发来的中断信号

每一条指令执行结束时，CPU都会例行检查是否有外中断信号。

中断机制的基本原理

总结

系统调用

定义：系统调用是操作系统提供给应用程序使用的接口，可以理解wield一种可供应用程序调用的特殊函数，应用查询可以通过系统调用来请求获取操作系统内核的服务。

总结

中断，异常和系统调用的区别

源头：

中断：外设，如鼠标，键盘，声卡等

异常：应用查询意想不到的行为，如除零操作等行为。

系统调用：应用程序请求操作提供服务。

处理时间:

中断：异步，即应用程序不知道什么时候发生。

异常：同步，当应用程序触发某条指令，代表发生了一次。

系统调用：同步或异步

响应:

中断：持续，对用户应用程序是透明的，即用户看不见的，注意不到的。

异常：杀死或重新执行意想不到的应用程序指令

系统调用：等待和持续

中断和异常的处理机制

中断：

硬件：

设置字段标记[CPU初始化]

将内部，外部时间设置中断标记

中断事件的ID，根据该中断ID得出是哪个外设中断了，将该中断号发给我们的操作系统

软件(操作系统):

保存当前处理状态

中断服务程序处理

清除中断标记，让服务继续执行

恢复之前保存的处理状态，这个过程也是透明的

异常:异常编号

保存现场

异常处理(两种情况)

杀死产生异常的程序

重新执行异常指令

恢复现场

系统调用:

普通程序不能直接操作硬件，普通程序想要调用硬件功能，操作系统提供接口给应用程序，普通程序实现该接口即可，其余需要由操作系统来直接完成调用硬件，这样我们的应用程序就可以完成各种各样的功能。

跨越操作系统边界的开销

在执行时间上开销超过程序调用

开销：

建立中断，异常，系统调用对应服务历程映射关系的初始化开销

建立内核堆栈

验证参数

内核态映射到用户态的地址空间更新页面映射权限

内核态独立地址空间

这些开销是必须的，也是值得的，它能保证在一个在安全可靠的环境中执行

操作系统内核的特征

并发

并发：一个时间段内多个程序同时运行，一个CPU即可实现，由CPU去调到运行该程序。

并行：一个时间点上可以多个程序同时运行，需要多个CPU才可实现，也就是多核CPU。

共享

“同时”访问

互斥共享

虚拟

利用多道程序设计技术，让每个用户都觉得有一个计算机专门为他服务。

如将CPU虚拟化为进程，磁盘虚拟化为文件，内存虚拟化为地址。

异步

程序的执行不是一贯到底，而是走走停停，向前推进的速度不可预知。

但只要运行环境相同，操作系统保证程序的结果也要相同。

在计算机运行中中内核是被信任的第三方，而其他软件不是被信任的，可能会带来恶意病毒，因此需要通过操作系统来控制应用软件，从而控制硬件。

只有内核可以执行特权指令

为了方便应用程序，操作系统来操作硬件，而向上提供简单的接口，使用户不用关心硬件的实现，就可以实现该功能。

内存

计算机体系结构

内存分层体系

在操作系统中管理内存的不同方法

程序重定位

分段

分页

虚拟内存

按需分页虚拟内存

实现高度依赖于硬件

必须知道内存架构

MMU(内存管理单元)：硬件组件负责处理CPU的内存访问请求

地址空间

物理地址空间：硬件支持的地址空间

逻辑地址空间：应用运行的程序所拥有的内存范围

连续内存分配

内存碎片问题

定义：空间内存不能被利用

外部碎片：在分配单元间的未使用内存

内部碎片：在分配单元中的未使用内存，即已经分配给了这个应用程序，但是这个应用程序无法进一步使用，我们需要避免内存碎片。

分区的动态分配

简单的内存管理方法：

当一个程序准许执行在内存中时，分配一个连续的区间

分配一个连续的内存区间给运行的程序一访问数据

分配策略：

首次适配

最优适配

最差适配

首次适配

需求：

按地址排序的空间块列表

分配需要寻找一个合适的分区

重分配需要检查，看是否只有分区能合并于相邻的空间分区(若有)

优势：简单，易于产生更大空闲块，向着地址空间的结尾

劣势：外部碎片，不确定性

最优适配

好处：

为了避免分割空闲块

为了最小化外部碎片产生的尺寸

需求：

按尺寸排列的空闲块列表

分配需要寻找一个合适的分区

重分配需要搜索即合并于相邻的空闲分区(若有)

优势：

当大部分分配是小尺寸是非常有效

比较简单

劣势：

外部碎片

重分配慢

以产生很多没有的微小碎片(不怎么好)

最差适配

压缩式碎片整理

重置程序以合并孔洞

要求所有程序是动态可重置的

交换式碎片整理

运行程序需要更多的内存

抢占等待的程序&回收它的内存

非连续内存分配

问题：

为什么需要非连续内存来管理物理内存？

答：1. 连续内存分配的缺点：分配给一个程序的物理内存是连续的；内存利用率较低；有外碎片、内碎片的问题。2. 非连续分配的优点：一个程序的物理内存是非连续的；更好的内存利用和管理；允许共享代码与数据(共享库等)；支持动态加载和动态链接。3. 非连续分配的缺点：开销比较大。

策略：

分段(Segmentation)

分页(Paging)

页表(Page table)

分段

程序的分段地址空间

一个运行的程序的逻辑地址空间看成一个一维线性数组或一个大的连续的字节流，通过段机制映射关系，可以将不同的内存块，如代码，数据，堆栈等，分别映射到不同的物理段内存中。

如果通过软件的进行段机制的来寻址，开销是很大的，因此需要硬件机制来进行分段的寻址。

分段寻址方案:

段表:

在分段存储管理系统，为每一个分段分配一个连续的分区。进程中的各个段可以离散的装入内存中不同位置。为此在系统中需要为为每一个进程建立一张兑换映射表，简称“段表”。每个段在表中均占有一个表项，其中记录了该段在起始地址和段的长度 。段表可以存放在一组寄存器中，以提高地址变换速度，但更常见的方法时将段表存放在内存中。在配置了段表后，执行中的进程可通过查找段表来找到每个段对应的内存区。所以，代表是用于实现从逻辑段到物理内存区映射的。

分页(主流)

分页地址空间

划分物理内存至固定大小的帧：大小是2的幂次方

划分逻辑地址空间至相同大小的页：大小是2的幂次方

建立方案转换逻辑地址为物理地址

页寻址方案:

页表

页表概述：

分页机制的性能问题：

访问一个内存单元需要2次内存访问

一次用于获取页表项

一次用于访问数据

页表可能非常大

如何处理？

缓存

间接访问

二级、多级页表

由来：针对难以找到连续的大内存空间来存放页表的问题，可利用将页表进行分页的方法，是每个页面的大小与内存物理块的大小相同，并为它们编号，异常编号为0页，1页……n页，然后离散第将各个页面分别存放在不同物理块中。同时，也要为这些分离分配的页表再建立一张页表，称之为“外层页表”，在每一个页表项中记录页表页面的物理块号。32位计算机通常用二级页表，64位计算机则用多级页表。

二级：二级页表是一种简单的页表组织形式，它将整个虚拟地址空间分成若干个固定大小的页框，然后将这些页框映射到物理内存中相应的页框上。具体来说，二级页表由两个层级构成：外部页表和内部页表。

外部页表：外部页表存储的是页表项的起始地址，每个页表项对应着一个内部页表。

内部页表：内部页表存储着虚拟页号到物理页框号的映射关系。

这种结构的优点是简单直观，但当虚拟地址空间较大时，内存开销会比较大，因为每个进程都需要有自己的二级页表。

多级：多级页表则是为了解决二级页表中内存开销较大的问题而提出的一种方案。它将整个虚拟地址空间进行更加灵活的划分，并采用多级的页表结构来管理。

多级页表的主要思想是将虚拟地址空间按照一定的规则划分成多个部分，然后使用多级的页表来管理这些部分。这样可以有效地减小每个进程所需的页表大小，节省内存空间。

总体来说，多级页表相比于二级页表在大型地址空间下更为高效，但实现上会稍微复杂一些。

反向页表

反向页表是一种与传统的页表组织方式相反的内存管理结构。在传统的页表中，虚拟地址被映射到物理地址，而在反向页表中，物理地址被映射到虚拟地址(逻辑地址)。

具体来说，反向页表由两部分组成：物理页框号和虚拟页号的映射关系，以及一些额外的控制信息（如访问权限等）。

反向页表的主要优点是节省了内存空间，因为每个物理页框只需要一条表项，而不是每个虚拟页都需要一条表项。这在大型系统中特别有用，因为系统中可能有大量的物理页框，但每个进程通常只有较少的虚拟页。

然而，使用反向页表也会增加地址转换的开销，因为每次访问都需要查找物理页框号对应的虚拟页号，而这通常需要遍历整个反向页表。

总体来说，反向页表在节省内存空间方面有优势，但在访问速度上可能会有些损失。

1.

页寄存器方案的权衡

利：

转换表的大小相对于物理内存来说很小

转换表的大小跟逻辑地址空间的大小无关

弊：

需要的信息对调了，即根据帧号可找到页号。

2.

3.

虚拟内存

虚拟内存是计算机操作系统中的一种技术，它通过将部分程序数据存储在磁盘上，从而扩展了物理内存的可用空间。这种技术使得每个进程能够看到一个连续的、私有的地址空间，称为虚拟地址空间，而不必担心物理内存的限制。

虚拟内存的主要组成部分包括：

页表：用于将虚拟地址转换为物理地址。当程序访问一个虚拟地址时，操作系统会检查页表并将虚拟地址映射到物理地址。

页面置换算法：用于在物理内存不足时将部分数据从内存中换出到磁盘，以便为新的数据腾出空间。常见的页面置换算法包括最近最少使用（LRU）和先进先出（FIFO）等。

页面错误处理机制：当程序访问的数据不在物理内存中时，会发生页面错误。操作系统需要处理这些错误，通常的做法是将缺失的页面从磁盘加载到内存中，并更新页表。

虚拟内存的优势包括：

更大的地址空间：每个进程可以拥有一个巨大的虚拟地址空间，而不受物理内存的限制。

更好的内存管理：操作系统可以更灵活地管理物理内存，根据需求动态地调整页面的存储位置。

更好的程序共享：多个进程可以共享同一个物理页面的副本，从而节省内存空间。

虚拟内存是现代操作系统中重要的一部分，它提供了对内存资源的高效利用和管理，同时为程序员提供了一个更加简单和统一的内存访问模型。

覆盖技术

目标：是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。

原理：

虚拟内存的覆盖技术是一种在内存有限的情况下，允许加载和执行超出物理内存容量的程序的方法。它的原理是根据程序执行的需求，将程序的不同部分分成若干页或段，并在需要时将其加载到物理内存中。

具体而言，覆盖技术的原理包括以下几个步骤：

程序分段或分页：将程序分成多个段或页，每个段或页可以独立地加载到内存中。

内存分配：当程序运行时，操作系统根据程序的当前执行部分，动态地为其分配内存空间。

覆盖操作：当程序执行到需要加载的新段或页时，操作系统会将当前不需要的段或页从内存中移出，然后加载新的段或页进入内存。这个过程称为覆盖操作。

存储管理：操作系统需要跟踪哪些部分被加载到了内存中，以及它们的位置。通常会使用页表或段表等数据结构来管理这些信息。

切换执行：一旦新的段或页被加载到内存中，控制权就会转移到这些新的部分，程序可以继续执行。

虚拟内存的覆盖技术允许在有限的物理内存条件下运行大型程序，但它也会增加系统开销，因为需要频繁地进行内存交换操作。因此，在设计和实现中需要权衡内存利用率和性能开销。

交换技术

目标：

多道程序在内存中时，让正在运行的程序或需要运行的程序获得更多的内存资源。

虚拟内存的交换技术是一种在内存不足时，将部分数据从内存移到磁盘上的方法，以便为新的数据腾出空间。这种技术的原理是根据程序的访问模式和内存使用情况，动态地将部分数据从物理内存交换到磁盘上，并在需要时再次将其加载到内存中。

以下是虚拟内存交换技术的原理：

页面置换：当物理内存不足时，操作系统需要选择哪些页面从内存中移出。常见的页面置换算法包括最近最少使用（LRU）、先进先出（FIFO）、时钟（Clock）等。这些算法根据页面的访问情况来确定哪些页面被置换出去。

页面交换：被选中要被置换出去的页面会被写回到磁盘上的交换文件或页面文件中。同时，从磁盘中选择一部分页面加载到物理内存中，以便为新的数据腾出空间。

页面访问：当程序访问一个被置换出去的页面时，操作系统会发生页面错误，然后从磁盘中加载该页面到内存中，并更新页表。

内存管理：操作系统需要跟踪哪些页面被置换出去，以及它们被置换到了磁盘的哪个位置。通常会使用交换文件或页面文件来管理这些信息。

虚拟内存的交换技术允许系统在内存不足时继续运行程序，但频繁的页面交换操作会增加系统开销，降低性能。因此，设计和实现时需要权衡内存利用率和性能开销，以提供最佳的系统性能。

交换技术现实中的几个问题：

交换时机的确定：合适需要发生交换？

答：只当内存空间不够或有不够的危险是换出。

交换区的大小：必须足够大以存放所有用户的进程的所有内存映像的拷贝；必须能对这些内存映像进行紫萼存取。

程序换入时的重定位：换出后再换入的内存位置一定要在原来的位置上吗？最好采用动态地址映射的方法。

覆盖与交换的比较

覆盖只能发生在那些相互之间没有调用关系的程序模块之间，因此程序员必须给出程序内的各个模块之间的逻辑覆盖结构。

交换技术是以内存中的程序大小为单位来进行的，它不需要程序员给出各个模块之间的逻辑覆盖结构。换言之，交换发生在内存中查询与管理查询或操作系统组件，而覆盖则发生在运行程序的内部。

虚拟内存管理技术

目标：

像覆盖技术那样，不是吧程序的所有内容都放在内存中，因而能够运行弊当前的空间内存空间还要打的程序。但做得更好，有操作系统自动来完成，无须程序员的干涉；

像交换技术那样，能够实现进程在内存与外存之间的交换，因而获得更多的空闲内存空间。但做得更好，只对进程的部分内容在内存与外存之间进行交换。

程序的局部性原理：

只程序在执行过程中的一个较短时期，锁执行的指令地址和指令的操作数地址，分别局限于一定区域。这可以表现为：

时间局部性：一条指令的一次执行和下一次执行，一个数据的一次访问和下一次访问都集中在一个较短的时期内；

空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的几个数据都集中在一个较小区域内。

程序的局部性原理表明，从理论上来说，虚拟内存技术是能够实现的，而且在实现了以后应该是能够取得应该满意的效果的。

基本特征：

大的用户空间：通过网络内存与外存项结合，提供给用户的虚拟内存空间通常大于书籍的物理内存，即实现了这两者的分离。如32位的虚拟地址理论上可以访问4GB，而可能计算机上仅有256M的物理内存，但硬盘容量大于4GB。

部分交换：与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的；

不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续

策略：

虚拟页式内存管理

虚拟页式内存管理是一种高效的虚拟内存管理技术，将虚拟内存和物理内存都划分成固定大小的页面，并使用页表将虚拟地址映射到物理地址。它是分页系统的一种扩展，将虚拟地址空间划分为固定大小的页，并在需要时将这些页加载到物理内存中。

原理

地址映射：当程序访问虚拟地址时，操作系统通过页表将虚拟地址映射到物理地址。页表存储了虚拟页号和物理页框号之间的映射关系。

请求调页：当一个用户查询要调入内存运行时，不是将该程序的所有页面都装入内存，而是只装入部分的页面，就可启动程序运行。

页面置换：当物理内存不足时，操作系统需要选择哪些页面从内存中置换出去。常见的页面置换算法适用于虚拟页式内存管理。

页面错误处理：当程序访问的页面不在物理内存中时，会发生页面错误。操作系统需要将缺失的页面加载到内存中，并更新页表。

页表管理：页表需要管理虚拟页号和物理页框号之间的映射关系，以及一些额外的控制信息（如访问权限等）。

优点

灵活性：虚拟页式内存管理允许程序访问一个连续的、私有的地址空间，而不必担心物理内存的限制。

内存利用率高：由于使用了页面置换算法，可以更灵活地管理物理内存，根据需求动态地调整页面的存储位置，提高了内存的利用率。

缺点

开销：虚拟页式内存管理需要维护页表，进行地址映射和页面置换，增加了系统的开销。

地址转换开销：每次访问都需要查找页表，进行地址转换，可能会增加访问速度的开销。

虚拟页式内存管理是现代操作系统中常用的内存管理技术之一，它提供了对内存资源的高效利用和管理，同时为程序员提供了一个更加简单和统一的内存访问模型。

缺页中断

理解一：缺页中断是虚拟内存管理技术中的重要概念，当程序访问的页面不在物理内存中时，操作系统会产生缺页中断。这时，操作系统需要将所需的页面加载到内存中，并更新页表，以便程序继续执行。

理解二：程序在运行时，如果它所要访问的页(段)尚未被调入内存中，称为缺页，须发出缺页中断请求，此时OS将利用请求调页(段)功能，将它们调入内存中，以使进程得以继续执行下去。但是如果这个时候内存已满，无法在装入新的页（段）,则OS还须在利用页(段)置换功能，将内存中展示不用的页(段)调至磁盘中，腾出足够的空间后，再将访问的页(段调入内存)，使程序进行执行下去。这样，便使一个大的用户查询能在较小的内存空间中运行，也可在内存中同时装入更多进程，使它们并发执行。

原理

页面访问检查：当程序访问一个虚拟地址时，操作系统首先检查对应的页面是否在物理内存中。

缺页中断：如果所需的页面不在物理内存中，操作系统会产生一个缺页中断。这时，操作系统需要处理中断，并将缺失的页面加载到内存中。

页面加载：操作系统根据缺页中断的地址信息，从磁盘上的交换文件或页面文件中加载所需的页面到物理内存中的空闲页面中。

更新页表：加载完页面后，操作系统更新页表，建立虚拟地址到物理地址的映射关系。

恢复执行：一旦所需的页面加载到内存中，并且页表更新完成，操作系统恢复程序的执行，使其继续执行。

优点

延迟加载：虚拟内存系统允许延迟加载页面，只有当程序访问到页面时才会加载到内存中，从而节省了内存空间和加载时间。

灵活性：通过缺页中断机制，操作系统可以根据程序的需求动态地管理内存，提高了内存的利用率和系统的响应能力。

缺点

性能开销：处理缺页中断会带来一定的性能开销，包括页面加载时间、更新页表等操作，可能会影响系统的响应速度和性能表现。

增加系统开销：频繁的缺页中断会增加系统的开销，包括磁盘IO、内存访问等，可能会影响系统的整体性能。

缺页中断是虚拟内存管理技术中的核心概念之一，它使操作系统能够在内存不足时继续执行程序，并根据需要动态地管理内存资源。

后备存储

在何处保存为被映射的页？

能够简单地识别在二级存储器中的页

交换空间(磁盘或文件):特殊格式，用于存储未被映射的页面

概念：

一个虚拟地址空间的页面可以被映射到一个文件(在二级存储中)中的某个位置

代码段：映射到可执行二进制文件

动态加载的共享库程序段：映射到动态调用的库文件。

其他段：可能被映射到交换文件(Swap file)

页面置换算法

功能：

当缺页中断发生，需要调入新的页面而内存已经满时，选择内存当中哪个物理页面被置换。

目标：

尽可能地减少页面的换进换出次数(即缺页中断的次数)。具体来说，把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理指导下依据过期的统计数据来进行预测；

页面锁定：用于描述必须常驻内存的操作系统的关键部分或时间关键的应用进程。实现的方法是：在页面中添加锁定标志位。

页面置换算法是虚拟内存管理技术中的重要组成部分，用于在物理内存不足时选择哪些页面置换出去，以便为新的页面腾出空间。不同的页面置换算法有不同的策略和原理，常见的算法包括：

最近最少使用（LRU）：LRU算法选择最长时间没有被访问的页面进行置换。它基于这样的假设：最近被访问的页面在未来也可能会被访问，而最长时间没有被访问的页面可能不会被再次访问。LRU算法需要维护一个页面访问顺序链表或使用其他数据结构来记录页面的访问情况。

先进先出（FIFO）：FIFO算法选择最早被加载到内存中的页面进行置换。它简单地按照页面加载的顺序来选择置换页面，但可能导致Belady异常，即增加物理页面数反而导致缺页次数增加的情况。

时钟（Clock）：时钟算法结合了LRU和FIFO的思想，通过使用一个时钟指针指向页表项来判断哪些页面最早被加载且未被访问。当需要置换页面时，时钟指针从当前位置开始顺时针旋转，如果指针指向的页面未被访问，则选择该页面进行置换；否则，将页面访问位清零，并继续向后搜索。

最少使用（LFU）：LFU算法选择被访问次数最少的页面进行置换。它假设被访问次数较少的页面在未来也可能不会被频繁访问，因此选择这些页面进行置换。LFU算法需要记录每个页面被访问的次数，并在需要置换页面时选择访问次数最少的页面。

最不经常使用（MFU）：MFU算法选择最近被访问次数最少的页面进行置换。与LFU相反，MFU算法认为最近被访问次数最少的页面可能在未来也不会被频繁访问，因此选择这些页面进行置换。

这些页面置换算法各有优缺点，适用于不同的场景和需求。在实际应用中，需要根据系统的特点和性能需求选择合适的页面置换算法。

局部页面置换算法

最优页面置换算法

基本思路：当一个缺页中断发生时，对保存在内存当中每一个逻辑页面，计算在他的下一次访问之前，还需等待多长时间，从中选择等待时间最长的那个，作为被置换的页面。

这只是一种理想情况，在实际系统中是无法实现的，因为操作系统无从知道每一个页面要等待多长时间以后才会再次被访问。

作用：可用于作为其他算法的性能评价的语句(在一个模拟器上运行某个程序，并记录每一个的页面访问情况，在第二遍运行时即可使用最优算法)。

先进先出算法（FIFO）

基本思路：选择在内存中驻留时间最长的页面并淘汰之。具体来说，系统维护着一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链首页面淘汰出局，并把新的页面添加到链表的末尾。

缺点：性能较差，调出的页面有可能是进程要访问的页面，并有Belady现象，先进先出算法很少单独使用。

最近最久未使用算法（LRU）

基本思路：当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰之。

它是对最优页面转换算法的一个近似，其依据是程序的局部性原理，即在最近一小段时间(最近几条指令)内，如果某些页面被频繁地访问，那么在将来的一小段时间内，它们还可能会再一次被频繁地访问。反过来说，如果在过去某些页面长时间未被访问，那么在将来它们还可能会长时间得不到访问。

缺点：LRU算法需要记录各个页面使用时间的先后顺序，开销比较大。

实现方法（2种）：

系统维护一个页面链表，最近各个使用过的页面作为首结点，最久未使用的页面作为尾节点。每一次访问内存时，找到相应的页面，把它从链表中摘下来，再移动到链表之首。每次缺页中断发生事，淘汰链表末尾的页面。

设置一个活动页面栈，当访问某页时，将此页好压入栈顶，然后考察栈内是否与此页面相同的页号，若有则抽出。当需要淘汰一个页面时，总是选择栈底的页面，它就是最久未使用的。

时钟页面置换算法(Clock)

Clock页面置换算法，LRU的近似，对FIFO的一种改进；

基本思路：

需要用到页表项当中访问位，当一个页面被装入内存时，把该位初始化为0.然后如果这个页面被访问(读、写),则把该位置为1；

把各个页面组织长环形链表(类似钟表面)，把指针指向最老的页面(最先进来);

当发生一个缺页中断事，考察指针所指向的最老页面，若它的访问位为0，立即淘汰；若访问位为1，则把该位置为0，然后指针往下移动一格。如此下去，直到找到淘汰的页面，然后把指针移动它的下一格。

二次机会法(Clock的改进)

在将一个页面换出时，如果该页面已被修改过(写操作），则须将该页重新写回磁盘上；但如果该页未被修改过(读操作)，则不必将其重新写回磁盘中，销毁即可。换言之，对于修改过的页面，在换出时所付出的开销比未修改过的页面的大，或者说代价更大。所以在改进型Clock页面置换算法中，出须考虑页面的使用情况外，还须再增加一个需要考虑的因素——置换代价。这样选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面，将同时满足这两个条件的页面作为首选淘汰的页面。

最不常用算法(LFU)

基本思路：当一个缺页中断发生事，选择访问次数最少的那个页面，并淘汰之。

实现方法：对每一个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器加1，在发生缺页中断事，淘汰计数值最小的那个页面。

LRU和LFU的区别：LRU考察的是多久未访问，时间越短越好；而LFU考察的是访问的次数或频度，访问的次数越多越好。

Belady现象、LRU、FIFO、Clock的比较

Belady现象(Belady：一个科学家的名字)：在采用FIFO算法时，优势回出现分配的物理页面数增加，缺页率反而提高的异常现象。

Belady现象的原因：FIFO算法的置换特征与进程访问内存的冬天特征是矛盾的，与置换算法的目标是不一致的(即替换较少使用的页面)，因此，被它置换存储的页面并不一定时进程不会访问的。

全局页面置换算法

工作集模型

前面介绍的各种页面置换算法，都是基于一个前提，即程序的局部性原理。但是此原理是否成立？

如果局部性原理不成立，那么各种页面置换算法就没有什么分别，也没有什么意义。例如：假设进程对逻辑页面的访问顺序是1,2,3,4……,即单调递增，那么在物理页面数有限的前提下，不管采用何种置换算法，每次的页面访问都是不然到时缺页中断。

如果局部性原理是成立的，那么如何来证明它的存在，如何来对他进行定量地分析？这就是工作集模型。

定义：工作集模型是操作系统内存管理中一种重要的概念，它描述了一个进程当前所需的内存页集合。当发生缺页中断时，操作系统会根据工作集模型来做出页面置换的决策。

工作集模型通常由两个参数来描述：

工作集大小（Working Set Size）： 表示一个进程当前所需的内存页数量，通常以页面数或字节数表示。

工作集窗口（Working Set Window）： 表示用于计算工作集大小的时间窗口大小，即在过去多长时间内计算工作集大小。

当发生缺页中断时，操作系统首先会检查当前缺页的页面是否在进程的工作集内。如果在工作集内，则不需要进行页面置换，直接将该页面加载到内存中；如果不在工作集内，则需要根据页面置换算法选择一个页面进行替换，以便为新页面腾出空间。

工作集模型的主要目的是提高内存访问的效率，通过预测进程未来可能访问的页面，尽可能地减少缺页中断的发生，从而提高系统的性能和响应速度。

常驻集

常驻集是指在操作系统内存管理中，始终驻留在物理内存中的页面集合。这些页面不会被置换出去，因为它们被认为是进程执行所必需的，而且通常包括操作系统内核和一些常用的系统库或服务。当发生缺页中断时，如果所需的页面位于常驻集中，操作系统不需要进行页面置换，直接从内存中获取该页面，从而加快了访问速度。

缺页率页面置换算法

可变分配策略：常驻集大小可变。例如：每一个进程在刚开始运行的时候，先根据程序大小给它分配一定数目的物理页面，然后在进程运行过程中，再动态地调整常驻集的大小。

可采用全局页面置换的方式，当发生一个缺页中断时，被置换的页面可以是其他进程当中，各个并发进程竞争地使用物理页面。

优缺点：性能较好，但是增加了系统开销。

具体实现：可以使用缺页率算法来动态调整常驻集的大小。

缺页率

缺页率表示“缺页次数/内存访问次数”(比率或)”缺页的平均时间间隔的倒数”。影响缺页率的因素：

页面置换算法

分配给进程的物理页面数目

页面的本身大小

程序的编写方法

抖动问题

如果分配给一个进程的物理页面太少，不能包含整个的工作集，即常驻集<工作集，那么进程将会造成很多的页面中断，需要频繁地在内存与外存之间替换页面，从而是进程的运行速度变得很慢，我们把这种状态成为“抖动”。

产生抖动的原因：随着驻留内存的进程数目增加，分配进程物理也数不断减少，缺页率不断上升。所以OS要选择一个适当的进程数目和进程需要的帧数，以便在并发水平和缺页率之间达到一个平衡。

进程

概念

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

进程（Process）：是动态的，是程序的一次执行过程。同一个程序多次执行会对应多个进程。

思考：操作系统是这些进程的管理者，他要怎么区分各个进程？

答：当进程被创建时，操作系统会为该进程分配一个唯一的，不重复的“身份证号”——PID(Process ID,进程ID)

进程的组成

一个进程应该包括：

程序的代码

程序处理的数据

程序计数器中值，指示下一条将运行的指令。

一组通用的寄存器的当前值，堆，栈；

一组系统资源(如打开的文件)

总之，进程包含了正在运行的一个程序所有状态信息。

进程与程序的联系：

程序是产生进程的基础

程序的每次运行构成不同的进程

进程是程序功能的体现

通过多次执行，应该程序可对应多个进程；通过调用关系，应该进程可包含多个程序。

进程与程序的区别：

进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行，进程是核心态、用户态

进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可以长久保存

进程与程序的组成不同：进程的组成包括程序，数据和进程控制块(即进程的状态信息)

进程控制块（PCB）

描述进程的数据结构：进程控制块。

操作系统为每个进程都维护了一个PCB，用来保存与该进程有关的各种状态信息。

PCB是进程存在的唯一标志，当进程被创建时，操作系统为其创建PCB，当进程结束时，会回收其PCB。操作系统对进程进行管理工作所需的信息都存在PCB中。

PCB含有以下三大类信息：

进程标识信息：如本进程的标识，本进程订单产生者标识(父进程标识)；用户标识。

处理机状态信息保存区：保存进程的运行现场信息。

用户可见寄存器，用户程序可以使用的数据，地址等寄存器。

控制和状态寄存器，如程序计数器(PC),程序状态字(PSW)。

栈指针，过程调用、系统调用、中断处理和返回时需要用到它。

进程控制信息

调度和状态信息，用于操作系统调度进程并占用处理机使用。

进程间通信信息，为支持进程间的与通信相关的各种标识、信号、信件等，这些信息存在接收方的进程控制块中。

存储管理信息，包含有指向本进程映射存储空间的数据结构。

进程所用资源，说明由进程打开，使用的系统资源，如打开的文件等。

有关数据结果连接信息，进程可以连接到一个进程队列中，或了解到相关的其他进程的PCB。

PCB的组织方式

链表：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表，各状态的进程形成不同的链表：就绪链表，阻塞链表

索引表：同一状态的进程归为一个index表(由index指向PCB)，多个状态对应多个不同的index表，各状态的进行不同形成不同索引表：就绪索引表，阻塞索引表

程序段和数据段

程序段：程序的代码(指令序列)

数据段：运行过程中产生的各种数据(如：程序中定义的变量)。

PCB是给操作系统用的，程序段、数据段时给进程自己用的。

进程实体

一个进程实体(进程映像)由PCB、程序段、数据段组成。进程是动态的，进程实体是静态的。

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

进程的特征

程序是静态的，进程是动态的，相比与程序，进程的特征：

总结

进程的状态与转换

进程的状态

进程创建

引起进程创建的3个主要事件：

系统初始化

用户请求创建一个新进程；

正在运行的进程执行了创建进程的系统调用。

进程正在被创建时，它状态时**”创建态”**，在这个阶段操作系统会为进程分配资源，初始化PCB

当进程创建完成后，便进入**”就绪态”**，处于就绪态的进程已经具备运行条件，但由于没有空闲CPU，就暂时不能运行。

系统中可能会有很多个进程都处于就绪态，当CPU空闲时，操作系统就会选择一个就绪进程，让它上处理机运行。如果一个进程此时在CPU上运行，那么这个进程处于**”运行态”**，CPU会执行该进程对应的进程。

在进程运行的过程中，可能会请求等待某个事件的发生(如等待某种系统资源的分配，或者等待其他进程的响应)。在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，并让它进入“阻塞态”，当CPU空闲时，又会选择另一个“就绪态”进程上CPU运行.

一个进程可以执行exit系统调用，请求操作系统终止该进程。此时该进程会加入“终止态”，操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回收该进程的PCB。当终止进程的工作完成之后，这个进程就彻底消失了。

进程状态变化模型

进程的三种基本状态：进程在生命结束前处于并且仅次于三种基本状态之一。不同系统设置的进程状态数目不同。

运行态(running):当一个进程正在处理机上运行时。

就绪状态(Ready)：应该进程获得了出处理机之外的一切所需资源，一旦得到处理机即可运行。等待状态(又称阻塞状态Blocked):一个进程指针等待某一时间而暂停运行时。如等待某资源，等待输入、输出完成。

进程挂起

why?合理且充分地利用系统资源。

进程在挂起状态时，意味进程没有占用内存空间。处在挂起状态的进程影像在磁盘上。

挂起状态

阻塞挂起状态(Blocked-suspend)：进程在外存并等待某事件的出现；

就绪挂起状态(Ready-suspend)：进程在外存，但主要进入内存，即可运行。

状态队列

有操作系统来维护一组队列，用来表示系统当中所有进程的当前状态；

不同的状态分别用不同的队列来表示(就绪队列，各种类型的阻塞队列)；

每个进程的pcb都根据它的状态加入到相应队列当中，当一个进程的状态发生变化事，它的pcb从一个状态队列中脱离出来，加入到另外一个列队。

线程管理

为什么使用线程？

如何解决这些问题？

需要提出一种新的实体，满足一下特征：

实体之间可以并发执行

实体之间共享系统的地址空间(共享数据)

这种实体就是：线程(Thread)

定义

Thread:进程当中的一条执行流程。

从两个方面来重新连接进程：

从资源组合的角度：进程把一组相关的资源组合处理，构成了一个资源平台(环境)，包括地址空间(代码段，数据段)，打开的文件等各种资源。

从运行的角度：代码在这个资源平台上的一条执行流程(线程)

线程 = 进程 - 共享资源

线程优点：

一个线程中可以同时存在多个线程；

各个线程之间可以并发地执行；

各个线程之间可以共享地址空间和文件等资源

缺点：

一个线程崩溃，会导致其所属进程的所有线程崩溃。

不同操作系统对线程的支持

线程和进程的比较

进程是资源分配单位，线程是CPU调度单位；

进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；

线程同样具有就绪，阻塞和执行三种基本状态，同样具有状态之间的转换关系；

线程能减少并发执行的时间可空间开销：

线程的创建时间比进程短

程序的终止时间比进程短

同一进程内的线程切换时间比进程短

由于同一进程的各线程间共享内存和文件资源，可直接进行不通过内核的通信。

线程的实现

主要有三种线程的实现方式：

用户线程:在用户空间实现

内核线程：在内核中实现

轻量级进程：在内核中实现，支持用户线程。

用户线程与内核线程的对应关系

多对一

一对一

多对多

用户线程

缺点：

阻塞性的系统调用如何实现？如果一个线程发起系统调用而阻塞，则整个进程在等待。

当一个线程开始运行后，除非它主动递交出CPU的使用权，否则它所在的进程当中的其他线程将无法运行。

由于时间片分配给进程，故与其它进程比，在多线执行时，每个线程得到的时间片较少，执行会比较慢。

内核线程

轻量级进程

上下文切换

停止当前运行进程(从运行状态改变成其他状态)并且调度其他进程(转变成运行状态)

必须在切换之前存储许多部分的进程上下文

必须能够在之后恢复它们，所以进程不能显示它曾经被暂停过

必须快速(上下文转换时非常频繁的)

需要存储什么上下文

寄存器(PC,SP),CPU状态等

一些时候回可能费事，所以我们应该尽可能避免

进程控制

进程控制模块是操作系统中的一个关键部分，负责管理和控制进程的创建、终止、挂起、恢复以及进程间通信等功能。该模块通常包括以下几个主要组成部分：

进程创建：负责创建新进程。通常涉及分配必要的资源（如内存空间、文件描述符等），设置进程控制块（PCB），并初始化进程状态等。

进程终止：处理进程结束的情况。可能涉及释放进程占用的资源，更新进程状态，并通知相关的父进程或其他进程。

进程挂起和恢复：允许操作系统暂停一个进程的执行，并在需要时恢复其执行。这在多任务系统中特别重要，以便有效地管理系统资源。

进程调度：确定哪个进程应该在何时执行。这涉及到使用不同的调度算法（如先来先服务、最短作业优先、轮转调度等）来平衡系统的吞吐量、响应时间和公平性。

进程间通信：允许进程之间进行数据交换和信息共享。这可以通过共享内存、管道、消息队列、信号量等机制实现。

进程状态管理：维护并更新进程的状态信息，如运行、就绪、阻塞等状态，以便操作系统能够正确地管理和调度进程。

进程创建

进程创建是指操作系统启动一个新进程的过程。具体步骤包括：

分配资源：操作系统为新进程分配必要的资源，如内存空间、文件描述符、寄存器等。

初始化进程控制块（PCB）：每个进程都有一个独特的进程控制块，用于记录和管理进程的信息，如进程状态、优先级、资源使用情况等。

设置进程状态：新进程一般被设置为就绪状态，以等待CPU的调度。

加载程序：操作系统将程序加载到进程的地址空间，并初始化程序的运行环境。

进程终止

进程终止指的是进程结束执行的过程，可能因为完成了任务、出现错误或被用户终止。终止过程包括：

资源释放：操作系统释放进程使用的资源，如内存、文件描述符、其他I/O设备等。

更新进程状态：将进程状态设置为终止状态，并从系统的进程表中移除进程控制块。

通知父进程：如果进程有父进程，操作系统可能会通知父进程该进程已经终止。

进程挂起和恢复

进程挂起和恢复允许操作系统暂停一个进程的执行，并在需要时恢复其执行。这对于多任务系统的资源管理至关重要，具体操作包括：

挂起进程：将进程的当前状态保存，释放其占用的CPU和其他资源，使其暂停执行。

恢复进程：重新分配资源给进程，使其可以继续执行，从挂起状态恢复到就绪状态或运行状态。

进程调度

进程调度确定哪个进程在何时执行，以便有效地利用系统资源。常见的调度算法包括：

先来先服务（FCFS）：按照进入就绪队列的顺序进行调度。

最短作业优先（SJF）：优先执行估计执行时间最短的进程。

轮转调度（RR）：每个进程被调度一定时间片后，被挂起并放回就绪队列末尾。

进程间通信

进程间通信允许进程之间交换数据和信息，以便协作完成任务。通信机制包括：

共享内存：多个进程可以访问和更新同一块内存区域。

管道：单向通信，适用于有亲缘关系的进程。

消息队列：进程通过发送和接收消息进行通信。

信号量：用于控制多个进程对共享资源的访问。

进程状态管理

进程状态管理维护和更新进程的状态信息，以便操作系统能够正确地管理和调度进程。主要状态包括：

运行态：进程正在执行。

就绪态：进程已经准备好执行，正在等待CPU调度。

阻塞态：进程由于等待某种事件（如I/O操作完成）而暂时停止执行。

进程调度

背景

上下文切换：

切换CPU当前的任务，从一个进程/线程到另一个。

保存当前进程/线程在pcb/TCP中的执行上下文(cpu状态)

读取下一个进程/线程的上下文

CPU调度

从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程。

调度程序：挑选进程/线程的内核函数(通过一些调度策略)

什么时候调度？

内核运行调度程序的条件(满足一条即可)

一个进程从运行状态切换到等待状态

一个进程被终结了

不可抢占

调度程序必须等待事件结束

可以抢占

调度程序在中断被响应执行

当前订单进程从运行切换到就绪，或者一个进程从等待切换到就绪

当前运行进程可以被换出。

调度原则

执行模型：程序在CPU突发和IO中交替

每个调度决定都是关于在下一个CPU突发时将哪个工作交给CPU

在时间分片机制下，线程可能在结束当前CPU突发前被迫放弃CPU

相关概念

CPU使用率：CPU处于忙状态所占时间的百分比。

吞吐量：在单位时间内完成的进程数量。

周转时间：应该进程总初始化到结束，包括所有等待时间所花费的时间

等待时间：进程在就绪队列中的总时间

响应时间：从一个请求被提交到产生第一次响应所花费的时间。

调度原则目标

减少响应时间

减少平均响应时间的波动：在交互系统中，可预测性比高差异低平均更重要

增加吞吐量：减少开销(操作系统开销，上下文切换)；系统资源的高效利用(cpu,IO设备)

减少等待时间

低延迟调度增加了交互式表现

调度算法

先来先服务算法（FCFS）

FIFO队列的规定：

如果进程在执行中阻塞，队列中的下一个会得到CPU。

优点：简单

缺点：

平均等待事件波动较大

花费时间少的任务可能拍照花费时间长的任务后面

可能导致IO和CPU之间的重叠处理：CPU密集型进程会导致IO设备闲置时，IO密集型进程也在等待

短任务优先算法（SJF）

定义：按照预测的完成时间来将任务入队。

即可用于作业，也可用与进程

对作业：从后备队列中选择若干个估计运行时间最短的作业

对进程：关联到每个进程下一次运行的CPU区间长度，调度最短的进程

对进程调度，SJF有两种模式：

非抢占式SJF

抢占式SJF：抢占发生在有比当前进程剩余时间片更短的进程到达时，也称为最短剩余时间优先调度

SJF是最优的(对一组指定的进程而言)，它给出了最短的平均等待时间

优点：能有效降低作业的平均等待时间，提高系统吞吐量。

缺点：

只能估算进程的运行时间(估值不准确),所以常用于作业调度

对长作业不利

常用SJF算法时，人机无法实现交互

完全未考虑作业的紧迫程度

优先级调度算法(PR)

即可用于作业调度，也可用于进程调度

基于作业、进程的紧迫程度，有外部赋予作业相应的优先级，调度算法根据优先级进行调度

每个进程都有一个优先数，优先数为整数

默认：小的优先数具有高优先级

目前主流的操作系统调度算法

高响应比优先算法时一种优先调度算法，由于作业调度

优先级调度算法类型：

非抢占式：适用于批处理系统或实时性要求不高的系统

抢占式：适合于严格的实时系统或对性能要求较高的批处理和分时系统中

优点：

实现简单，考虑了进程的紧迫程度

灵活，可模拟其他算法

缺点：饥饿——低优先级的进程可能永远得不到运行

解决方法：老化——视进程等待时间的延长提高其优先数

时间片轮转(RR)调度算法

系统把就绪队列中的所有进程，按先来先服务的原则，排成一个队列

每次调度是，把CPU分配给队首进程，并让它执行一个时间片

每当执行的时间片用完，调度程序便停止该进程的执行，将其送入就绪队列尾部；然后进行下一次进程调度

时间片的大小：几ms~几百ms

时间片大小的确定

特征：时间片大，就成了FCFS；时间片小，增加上下文切换时间

时间片设置应考虑

系统对相应时间的要求

就绪队列中进程的数目

系统的处理能力

一般准则：时间片/10>进程上下文切换时间

多级反馈队列

实施过程：

设置多个就绪队列，赋予不同的优先级，各个队列优先级递减，时间片递增

新进程放入第一个队列尾部，FCFS原则排队调度，时间片内完成则撤离系统，如果没有完成则转入下一个队列尾部，依次类推，在第n个队列采取时间轮转调度

第一队列空闲，调度第二队列，依次类推，新进程如果优先级高，可抢占CPU

性能：

终端型作业用户，大多数交互性，作业小；

短批处理作业用户，周转时间短

长批处理用户，不用担心作业长期得不到处理

进程能在不同的队列键移动

优点：

不必事先知道各种进程所需的执行时间

可以满足各种类型进程的需要

实时调度

定义：正确型依赖于时间和功能两方面的一种操作系统

性能指标：

时间约束的及时性(deadlines)

速度和平均性能相对不重要

主要特性：时间约束的可预测性

强实时系统：需要在保证时间内完成重要的任务，必须完成。

弱实时系统：要求主要的进程优先级更高，尽量完成，并非必须

任务(工作单元)：一次计算，一次文件读取，一次信息传递等等。

属性：

硬时限：

如果错过了最后期限，可能会发生灾难性或非常严重的后果

必须验证：在最坏的情况下也能满足时限

保证确定性

软时限：

在理想情况下，时限一个被最大满足，如果有时限没有被满足，那么就相应地降低要求。

尽最大努力去保证

多处理器调度

多处理器的CPU调度更加复杂：

多个相同的单处理器组成一个多处理器

优点：负载共享

对称多处理器(SMP)

每个处理器运行自己的调度程序

需要在调度程序中同步

优先级反转

采用优先级调度和抢占式，可能产生优先级倒置。现象：高优先级进程被低优先级进程延迟或阻塞。

倒置原因：共享临界资源

解决方法

指定一些规定，如规定低优先级进程执行后，其所占用的处理机不允许被抢占。

建立动态优先级继承

进程同步

进程同步是指多个进程在共享资源时的协调与管理，以避免出现竞态条件和数据不一致等问题。在多任务环境下，多个进程同时运行，它们可能需要访问共享资源，如内存、文件等。进程同步的主要目的是确保多个进程能够按照一定的顺序访问共享资源，以维护数据的一致性和正确性。

常见的进程同步问题包括：

互斥（Mutual Exclusion）： 确保在同一时刻只有一个进程能够访问共享资源，其他进程需要等待。

死锁（Deadlock）： 多个进程因互相等待对方释放资源而陷入僵局，导致系统无法继续运行。

饥饿（Starvation）： 某些进程由于优先级低或其他原因长时间无法获得所需资源而无法执行。

并发访问导致的数据一致性问题： 多个进程同时访问共享数据，可能导致数据不一致或丢失。

解决进程同步问题的方法：

临界区（Critical Section）： 使用临界区机制确保在任意时刻只有一个进程能够进入临界区访问共享资源，其他进程需要等待。

互斥量（Mutex）： 使用互斥量对临界资源进行保护，只允许一个进程访问该资源，其他进程需要等待互斥量释放。

信号量（Semaphore）： 使用信号量实现进程之间的同步与互斥，通过对信号量的操作实现对临界资源的访问控制。

管程（Monitor）： 使用管程作为进程间通信的抽象机制，提供了一种更高级别的同步方法，以便更容易地实现进程之间的协作。

这些方法可以帮助解决进程同步问题，确保多个进程能够安全地共享系统资源，同时保持数据的一致性和正确性。

背景

独立的线程：

不和其他线程共享资源或状态

确定性：输入状态决定结果

可重现：能够重现起始条件，IO

调度顺序不重要

合作线程：

在多个线程中共享状态

不确定性

不可重现

不确定性和不可重现意味着bug可能是间歇性发生的。

进程/线程，计算机/设备需要合作

优点：

共享资源

一台电脑，多个用户

一个银行存款余额，多台ATM机

嵌入式系统

加速

IO操作和计算可以重叠

多处理器——将程序分成多个部分并行执行

模块化

将大程序分解为小程序

使系统易于扩展

重要概念

竞态条件：

系统缺陷：结果依赖于并发执行或者事件的顺序/时间。

不确定性

不可重现

怎样避免竞态？让指令不被打断。

原子操作：

原子操作是值一次不存在任何中断或者失败的执行。

实际上操作往往不是原子的

临界区：

临界区是指进程中的一段需要访问共享资源并且当另一个进程处于相应代码区域时便不会被执行的代码区域。

互斥：

当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区并且访问任何相同的共享资源。

死锁：

两个或以上的进程，在相互等待完成特定任务，而最终没法将自身任务进行下去

饥饿：

一个可执行的进程，被调度器持续忽略，以至于虽然处于可执行状态却不被执行

临界区

互斥：同一时间临界区中最多存在一个线程

progress：如果一个线程想要进入临界区，那么它最终会成功。

有限等待：如果一个线程i处于入口区，那么在i的请求被接受之前，其他线程进入临界区的时间是有限制的。

无忙等待(可选):如果一个进程在等待进入临界区，那么在它可以进入之前会被挂起。

解决临界区互斥的方法

软件同步机制

软件方法的基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志

缺点：

忙等待

实现过于复杂

需要高的编程技巧

Peterson算法如下：

硬件同步机制

关中断

在进入锁测试之前关闭中断，完成锁测试并上锁之后才打开中断。

可有效保证互斥，但存在许多缺点

临界区执行期间不响应中断，不会引发调度，也就不会发生进程或线程切换

缺点：

应用程序滥用关中断权利可能导致严重后果

关中断时间过长会影响系统效率

关中断方法也不适用于多CPU系统

Test-and-Set指令实现互斥

测试和置位

从内存中读取值

测试该值是否为1(然后返回真或假)

内存值设置为1

优点：

适用于单处理器或共享主存的多处理器中任意数量的进程。

简单且容易证明

可以用于支持多临界区

缺点：

忙等待消耗处理器时间

当进程离开临界区并且多个进程在等待的时候可能导致饥饿

死锁：如果一个低优先级的进程拥有临界区并且一个优先级进程也需求，那么高优先级会获得处理器并且等待临界区

Swap指令

交换内存中的两个值

信号量

抽象数据类型

一个整形(sem——信号量)，两个原子操作

p()：sem减1，如果sem<0,等待，否则继续。

v():sem加1，如果sem<=0，唤醒一个等待的P

信号量是整数

信号量是被保护的变量

初始化完成后，唯一改变一个信号量的值的办法是通过p()和v()

操作必须是原子

p()能够阻塞，v()不会阻塞

我们假定信号量是”公平的”

没有线程被阻塞在p()仍然堵塞，如果v()被无限频繁调用(在同一个信号量)

在实践中，FIFO经常被使用

两种类型信号量

二进制信号量：可以是0或1

一般计数信号量:可以去任何非负值

两者相互表现(给定一个可以实现另一个)

信号量可以用在2个方面

互斥

条件同步(调度约束——一个线程等待另一个线程的事情发生)

信号量的双用途：

互斥和条件同步

但等待条件式独立的互斥

读/开发代码比较困难：程序员必须非常精通信号量

容易出错：

使用的信号量已经被另一个线程占用

忘记释放信号量

不能够处理死锁问题

管程

管程的引入

信号量机制方便有效，但是每个要访问临界资源的进程都必须自备同步操作wait(s)和signal(S),使大量的同步操作分散的在各个进程中。

给系统管理带来麻烦

会因同步操作使用不当而导致系统死锁。

管程的基本思路是：把分散在各进程中的临界区集中起来进行管理，并把系统中的共享资源用数据结构抽象地表示出来。

定义

一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能同步进程和改变管程中数据。

管程的四个组成部分

名称

数据结构说明

对该数据结构进行操作的组过程/函数

初始化语句

管程(相当于围墙)把共享变量和对它进行操作的若干过程围起来

管程功能

互斥

管程中的变量只能被管程中的操作访问

任何时候只能一个进程在管程中操作

类似临界区

由编译器完成

同步

条件变量

唤醒和阻塞操作

目的：分离互斥和条件同步的关注

什么是管程：

一个锁：指定临界区

0或多个条件变量：等待/通知信号量用于管理并发访问共享数据

一般方法

收集在对象/模块中的相关共享数据

定义方法来访问共享数据

生产者/消费者

经典同步问题

读者写者问题

基于信号量的读者优先

动机：共享数据的访问

两种类型使用者

读者：不需要修改数据

写着：读取和修改数据

问题的约束：

允许同一个时间有多个读者，但在任何时候只有一个写者

当没有写者时读者才能访问数据

当没有读者和写者时，歇着才能访问数据

在任何时候只能有一个线程可以操作共享变量

多个并发进程的数据集共享

读者——只读数据集，它们不执行任何更新

写着——可以读取和写入

共享数据

数据集

信号量CountMutex初始化为1

信号量WriteMutex初始化为1

整数Rcount初始化为0

基于读者优先策略的方法：只要有一个读者处于活动状态，后来的读者都会被接纳。如果读者源源不断地出现的话，那么写者就始终处于阻塞状态。

基于写者优先策略的方法：一旦写者就绪，那么写者会尽可能地执行写操作。如果写者源源不断地出现的话，那么读者就始终处于阻塞状态。

基于管程的写者优先

哲学家就餐问题

方案一：

方案二：

方案三——临界区：

缺点：

它把就餐(而不是叉子)看成必须互斥访问的临界资源，因此会造成(叉子浪费)资源的浪费

从理论上来说，如果有五把叉子，应该允许两个不相邻的哲学家同时进行就餐

方案四：

死锁

死锁问题

定义：一组阻塞的进程持有一种资源等待获取另一个进程所占有的一个资源。

实例：

系统有2个磁带驱动器

p1和p2各有一个，都需要另外一个。

死锁原因

竞争不可抢占行资源引起死锁：系统中的不可抢占性资源，由于它们的数量不能满足诸进程运行的需要，会是进程在运行过程中，因争夺这些资源而陷入僵局。

竞争可消耗性资源引起死锁

进程推进顺序不当引起死锁

进程推进顺序合法/非法

死锁模型

资源类型R1，R2……Rm：如CPU，内存，I/O

每个资源类型Ri有Wi个实例。

每个进程使用资源如下：

可重复使用的资源

在一个时间只能一个进程使用且不能被删除。

进程获取资源，后来释放又其他进程重用

处理器，I/O通道，主和副存储器，设备和数据结构，如文件，数据库和信号量。

如果每个进程拥有一个资源并请求其他资源，死锁可能发生。

使用资源

创建和销毁

在I/O缓冲区的中断，信号，消息，信息

如果接收消息阻塞可能会发生死锁

可能少见的组合时间会引起死锁

资源分配图

无死锁：

有死锁：

有循环的资源分配图没有死锁：

结论

如果图中不包含循环 => 没有死锁

如果图中包含循环 =>

如果每个资源只有一个实例，那么死锁

如果每个资源有几个实例，可能死锁。

死锁特征

死锁可能出现如果四个条件同时成立：

互斥：在个时间只能有一个进程使用资源。

持有并等待：进程保持至少一个资源正在等待获取其他进程持有的额外资源。

无抢占：应该资源只能被进程自愿释放，进程已经完成了它的任务之后。

循环等待：存在等待进程集合{p0，p1……pn}，p0正在等待p1所占用的资源，p1正在等待p2占用的资源，……，PN-1在等待pn所占用资源，PN正在等待P0所占用的资源

死锁的处理办法

死锁预防

通过设置某些限制条件，取破坏死锁的四个必要条件中的一个或几个，预防死锁的发生。

避免死锁

在资源的动态分配过程中，用某种方法区防止系统进程不安全状态，从而避免发生死锁。

检测死锁

通过系统所设置的检测机制，即时地检测出死锁的发生，并精确地确定与死锁有关的继承和资源。

解除死锁

与死锁检测配合,通过撤销和挂起一些进程,以便回收一些资源,再将这些资源分配给处于阻塞状态的继承,使之就绪,以继续运行.

死锁预防

限制申请方式——打破四个必要条件

互斥：共享资源不是必须的，必须占用非共享资源。

占用并等待：必须保证当一个进程请求的资源，它不持有任何其他资源

需要进程请求并分配其所有资源，它开始执行之前或允许进程请求资源仅当进程没有资源。

资源利用率低：可能发生饥饿。

无抢占

如果进程占有某些资源，并请求其他不能被立即分配的资源，则释放当前正占有的资源。

被抢占资源添加到资源列表中

只有当它能够获取旧的资源以及它请求新的资源，进程可以得到执行

循环等待：对所有资源类型进行排序，并要求每个进程按照资源的顺序进行申请。

死锁避免

需要系统具有一些额外的先验信息提供

最简单和最有效的模式是要求每个进程声明它可能需要的每个类型资源的最大数目。

资源的分配状态是通过限定提供与分配的资源数量，和进程的最大需求。

死锁避免算法动态检查的资源分配状态，以确保永远不会有一个环形等待状态。

当一个进程请求可用资源，系统必须判断立即分配是否能使系统处于安全状态。

系统安全状态指:针对所有进程,存在安全序列

如果系统处于安全状态 => 无死锁

如果系统处于不安全状态 => 可能死锁

避免死锁：确保系统永远不会进入不安全状态

银行家算法

前提条件

多个实例

每个进程都必须最大限度地利用资源

当一个进程请求一个资源，就不得不等待

当一个就获得所有资源就必须在一段优先的时间释放它们

基于上述前提条件，银行家算法通过尝试寻找每个进程获得的最大资源并结束(把资源返还系统)的进程请求的一个理想执行时序，来决定一个进程是否是安全的。

死锁检测

死锁恢复

终止所有的死锁进程

在一个时间内终止一个进程直到死锁消除

终止进程的顺序应该是

进程的优先级

进程运行了多久以及需要多少时间才能完成

进程占用的资源

进程完成需要的资源

多少进程需要被终止

进程是交互还是批处理

选择一个受害者——最小的成本

回滚——返回到一些安全状态，重启进程到安全状态

饥饿——同一进程可能一直被选作受害者，包括回滚的数量。

进程通信

进程通信的类型

定义：进程通信是指进程之间的信息交换

低级进程通信：进程的同步和互斥

效率低，一次传送一个消息

通信对用户不透明，数据定义，数据传送，同步互斥实现要程序员完成

高级进程通信

使用方便

高效地传送大量数据

高级通信机制

共享存储器系统

管道通信系统(共享文件)

消息传递系统

直接通信方式

间接通信方式——信箱通信

客户机——服务器系统

共享存储器系统

基于共享数据结构：如读者写者共享缓冲区。OS仅提供共享存储区，程序员负责同步实现，效率低，属于低级工具

基于共享存储区：先申请、再附加、后使用，最后归还

管道通信系统

管道：用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。

首创于UNIX

管道机制的协调能力：互斥，同步，对方是否存在

消息传递系统

消息传递机制：一种高级通信机制(单机系统，多机系统、计算机网络)

以格式化的消息(message)为单位

计算机网络中，message又称为报文。

利用系统提供的一组通信命令(原语)进行通信。

OS隐蔽了通信实现细节，大大简化了通信程序编制的复杂性，因而得到广泛应用。

微内核于服务器的通信采用信息传递机制

客户机——服务器系统

计算机网络领域普遍采用客户机——服务器通信机制。

**套接字(Socket)**：

设计用在同一台主机上多个应用程序组件的通信(即进程间的通信)，主要为了解决多对进程同时通信时端口和物理线路的多路复用问题

套接字是最流行的网络通信程序接口

用于通信的数据结构，包含目的地址、端口号、传输协议、进程所在网络地址等

**远程过程调用(RPC)**：

一个通信协议，用于通过网络链接的系统

允许运行于一台主机(本地)系统上的进程调用另一台主机(远程)系统上的进程。

本地和远程主机都需要运行网络守护进程，负责网络消息传递。

文件管理

基本概念

文件系统和文件

文件系统：一种用于持久性存储的系统抽象

在存储器上：组织、控制、导航、访问和检索数据

大多数计算机系统包含文件系统

个人电脑、服务器、笔记本电脑

IPod、Tivo/机顶盒、手机

Google可能是一个文件系统构成的

文件：文件系统中一个的相关数据在操作系统中的抽象

文件系统的功能

分配文件磁盘空间

管理文件块(那一块属于哪个文件)

管理空闲空间(哪一块是空闲的)

分配算法(策略)

管理文件集合

定位文件及其内容

命名：通过名字找到文件的接口

最常见：分层文件系统

文件系统类型(组织文件的不同方式)

提供的便利及特征

保护：分层来保护数据安全

可靠性/持久性：保持文件的持久，即时发生崩溃、媒体错误、攻击等。

文件和块

文件属性：名称、类型、位置、大小、保护、创建者、创建时间、最近修改时间

文件头：

在存储元数据中保存了每个文件的信息

保存文件的属性

跟踪哪一块存储块属于逻辑上文件结构的哪个偏移

文件描述符

文件使用模式

使用程序必须在使用前”打开”文件

内核跟踪每个进程打开的文件

操作系统为每个进程维护一个打开文件表

应该打开描述符是这个表中的索引

需要元数据来管理打开文件

文件指针：指向最近的异常读写位置，每个打开了这个文件的进程都有这个指针

文件打开计数：记录文件打开的次数，当最后一个进程关闭了文件时，允许将其从打开文件表中移除

文件磁盘位置：缓存数据访问信息

访问权限：每个程序访问模式信息

用户视图：持久的数据结构

系统访问接口：

字节的集合(UNIX)

系统不会关心你想存储在磁盘上的任何的数据结构

操作系统内部视角

块的集合(块是逻辑转换单元，而扇区是物理转换单元)

块大小，扇区大小：在UNIX中，块大小是4KB

文件已目录的方式组织起来

目录是一类特殊的文件：每个目录都包含了一张表<name, pointer to file header>

目录和文件的树型结构：早期的文件系统是扁平的(只有一层目录)

层次名称空间

典型操作：搜索文件、创建文件、删除文件、枚举目录、重命名文件、在文件系统中遍历一个路径

操作系统应该只允许内核模式修改目录

保证映射的完整性

应用程序能够读目录(如 ls)

文件名的线性列表，包含了指向数据块的指针：编程简单，执行耗时短。

Hash表：Hash数据结构的线性表

一个文件系统需要先挂载才能被访问

一个为挂载的文件系统被挂载在挂载点上。

文件别名

两个或多个文件名关联同一个文件

硬链接：多个文件项指向一个文件

软链接：以“快捷方式”执行其他文件

通过存储真实文件的逻辑名称来实现

文件系统种类

文件可以通过网络被共享

文件位于远程服务器

客户端远程挂载服务器文件系统

标准系统文件访问被转换成远程访问

标准文件共享协议：NFS For Linux，CIFS for Windows

分布式文件系统的问题

客户端和客户端的用户辨别起来很复杂

例如：NFS是不安全的

一致性问题

错误处理模式

虚拟文件系统

分层结构

上层：虚拟(逻辑)文件系统

底层：特定文件系统模块

目的：对所有不同文件系统的抽象

功能：

提供相同的文件和文件系统接口

管理所有文件和文件系统关联的数据结构

高效查询历程，遍历文件系统

与特定文件系统模块的交互

卷控制块：

每个文件系统一个

文件系统详细信息

块、块大小、空余块、计数/指针等

文件控制块：

每个文件一个

文件详细信息

许可、拥有者、大小、数据库位置等、

目录节点：

每个目录项一个(目录和文件)

将目录项数据结构及树型布局编码成树型数据结构

指向文件控制块、父节点

文件系统数据结构

卷控制块(每个文件系统一个)

文件控制块(每个文件一个)

目录节点(每个目录项一个)

持续存储在二级存储中

在分配在存储设备中的数据块中

当需要时加载进内存

卷控制模块：当文件系统挂载进入内存

文件控制块：当文件被访问时进入内存

目录节点：在遍历一个文件路径时进入内存

数据块缓存

数据块按需读入内存

提供read()操作

预读：预选当前后面的数据块

数据块使用后被缓存

假设数据将会再次被使用

写操作可能被缓存和延迟写入

两种数据块缓存方式

普通缓冲区缓存

页缓存：统一缓存数据块和内存页

分页要求：当需要一个页时才将其载入内存

支持存储：

应该也(在虚拟地址空间中)可以被映射到一个本地文件中(在二级存储中)