第一章操作系统引论

操作系统的目标和作用

OS的作用

OS是用户与计算机硬件系统之间的接口
OS是计算机系统资源的管理者

在一个计算机系统中，通常都含有各种各样的硬件和软件资源。归纳起来可将资源分为四类：**处理器、存储器、 I/O设备以及信息(数据和程序)**。相应地，OS的主要功能也正是针对这四类资源进行有效的管理，即：处理机管理，用于分配和控制处理机；存储器管理，主要负责内存的分配与回收；I/O设备管理，负责I/O设备的分配与操纵；文件管理，负责文件的存取、共享和保护。可见，OS确是计算机系统资源的管理者。事实上，当今世界上广为流行的一个关于OS作用的观点，正是把OS作为计算机系统的资源管理者。
OS用作扩充机器

系统调用：

操作系统将计算机的资源（如CPU、内存、硬盘等）划分为两个空间：用户空间和内核空间。用户程序运行在用户空间，而操作系统的核心部分（内核）运行在内核空间。为了安全和稳定，用户程序不能直接访问内核空间，必须通过系统调用来请求内核服务。

操作系统的发展过程

无操作系统的计算机系统

人工操作方式（穿孔纸带）

(1) 用户独占全机。(2) CPU等待人工操作。

脱机输入/输出方式

(1) 减少了CPU的空闲时间。(2) 提高I/O速度。

单道批处理系统

(1) 自动性。(2) 顺序性。(3) 单道性。

多道批处理系统

(1) 提高CPU的利用率。(2) 可提高 [内存和I/O设备] 利用率。(3) 增加系统吞吐量。

CPU利用率和系统吞吐量的关系
高CPU利用率并不一定带来高吞吐量。例如，如果CPU一直在处理低效的任务，CPU利用率可能很高，但吞吐量却很低。
高吞吐量通常需要较高的CPU利用率，但也受到其他系统资源的限制。
(1) 多道性。(2) 无序性。(3) 调度性。
(1)资源利用率高。(2) 系统吞吐量大。(3) 平均周转时间长。(4) 无交互能力。
需要解决：(1) 处理机管理问题。(2) 内存管理问题。(3) I/O设备管理问题。(4) 文件管理问题。(5) 作业管理问题。

分时系统

计算机将CPU时间分成许多时间片，然后轮流分配给各个用户，由于切换速度很快，用户感觉就像独占计算机一样。
(1) 多路性。(2) 独立性。(3) 及时性。(4) 交互性。

实时系统

所谓“实时”，是表示“及时”，而实时系统(Real-Time System)是指系统能及时(或即时)响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。

周期性实时任务

定义： 任务以固定的时间间隔重复执行。
例子：
- 汽车防抱死系统（ABS）： 定期检测车轮速度，调整制动压力。
- 工业自动化控制： 定期采样传感器数据，控制执行器。
- 多媒体播放： 定期刷新屏幕，播放音频/视频帧。
- 雷达系统： 定期扫描指定区域。

非周期性实时任务

定义： 任务的执行时间不固定，由外部事件触发。
例子：
- 飞机紧急制动系统： 在检测到紧急情况时立即启动。
- 医疗监护仪： 在检测到病人异常生理指标时发出警报。
- 网络数据包处理： 在接收到网络数据包时进行处理。
- 用户点击鼠标： 在用户点击鼠标时进行响应。

硬实时任务

定义： 任务必须在严格的时间限制内完成，否则会导致灾难性后果。
例子：
- 飞行控制系统： 任何延迟都可能导致飞机失控。
- 核电站控制系统： 任何延迟都可能导致核泄漏。
- 导弹制导系统： 任何延迟都可能导致目标丢失。
- 汽车安全气囊系统： 在碰撞发生后，必须在极短的时间内展开。

软实时任务

定义： 任务尽可能在时间限制内完成，但偶尔的延迟是可以接受的。
例子：
- 多媒体播放： 偶尔的丢帧或卡顿不会导致严重后果。
- 网络游戏： 偶尔的网络延迟会影响游戏体验，但不会导致游戏崩溃。
- 视频会议： 偶尔的音频/视频延迟是可以接受的。
- 实时股票行情显示： 偶尔的延迟是可以接受的。

总结

周期性和非周期性是根据任务的执行频率来划分的。
硬实时和软实时是根据任务对时间限制的严格程度来划分的。
实际应用中，一个任务可能同时具有多种属性，例如，汽车ABS系统既是周期性任务，又是硬实时任务。

操作系统的基本特性

并发 (Concurrency)

定义: 指两个或多个事件在同一时间间隔内发生。

定义: 指系统中的资源可以被多个程序或用户共同使用。
在操作系统中: 资源可以是硬件（如CPU、内存、磁盘）或软件（如文件、数据）。
(1) 互斥共享方式 (2) 同时访问方式

虚拟 (Virtualization)

定义: 指通过技术手段将一个物理实体转化为多个逻辑实体，或者将多个物理实体转化为一个逻辑实体。
在操作系统中:
- 虚拟内存：将物理内存扩展为更大的逻辑地址空间。
- 虚拟CPU：通过时间片轮转，使每个程序都感觉拥有独立的CPU。
关键点: 强调的是资源的逻辑抽象，这提高了资源的灵活性和效率。

异步 (Asynchrony)

由于资源等因素的限制，使进程的执行通常都不是“一气呵成”，而是以“停停走走”的方式运行。
进程是以人们不可预知的速度向前推进，此即进程的异步性。
尽管如此，但只要运行环境相同，作业经多次运行，都会获得完全相同的结果。因此，异步运行方式是允许的，是操作系统的一个重要特征。

这四个概念是操作系统中非常重要的基本特征，它们共同构成了现代操作系统的基础。

操作系统的主要功能

处理机管理功能

进程控制

主要功能是为作业创建进程、撤消已结束的进程，以及控制进程在运行过程中的状态转换。

进程同步

进程同步的主要任务是为多个进程(含线程)的运行进行协调。
有两种协调方式：
1. 进程互斥方式，这是指诸进程(线程)在对临界资源进行访问时，应采用互斥方式；
2. 进程同步方式，指在相互合作去完成共同任务的诸进程(线程)间，由同步机制对它们的执行次序加以协调。
为了实现进程同步，系统中必须设置进程同步机制。最简单的用于实现进程互斥的机制，是为每一个临界资源配置一把锁W，当锁打开时，进程(线程)可以对该临界资源进行访问；而当锁关上时，则禁止进程(线程)访问该临界资源。

进程通信

在多道程序环境下，为了加速应用程序的运行，应在系统中建立多个进程，并且再为一个进程建立若干个线程，由这些进程(线程)相互合作去完成一个共同的任务。而在这些进程(线程)之间，又往往需要交换信息。
当相互合作的进程(线程)处于同一计算机系统时，通常在它们之前是采用直接通信方式，即由源进程利用发送命令直接将消息(message)挂到目标进程的消息队列上，以后由目标进程利用接收命令从其消息队列中取出消息。

调度

在后备队列上等待的每个作业，通常都要经过调度才能执行。在传统的操作系统中，包括作业调度和进程调度两步。
作业调度的基本任务，是从后备队列中按照一定的算法，选择出若干个作业，为它们分配其必需的资源(首先是分配内存)。在将它们调入内存后，便分别为它们建立进程，使它们都成为可能获得处理机的就绪进程，并按照一定的算法将它们插入就绪队列。
而进程调度的任务，则是从进程的就绪队列中选出一新进程，把处理机分配给它，并为它设置运行现场，使进程投入执行。
值得提出的是，在多线程OS中，通常是把线程作为独立运行和分配处理机的基本单位，为此，须把就绪线程排成一个队列，每次调度时，是从就绪线程队列中选出一个线程，把处理机分配给它。

存储器管理功能

内存分配

分配方式：
1. 静态分配
2. 动态分配
为了实现内存分配，在内存分配的机制中应具有这样的结构和功能：
1. 内存分配数据结构，该结构用于记录内存空间的使用情况，作为内存分配的依据；
2. 内存分配功能，系统按照一定的内存分配算法，为用户程序分配内存空间；
3. 内存回收功能，系统对于用户不再需要的内存，通过用户的释放请求，去完成系统的回收功能。

内存保护

主要任务是确保每道用户程序都只在自己的内存空间内运行，彼此互不干扰。
一种比较简单的内存保护机制，是设置两个界限寄存器，分别用于存放正在执行程序的上界和下界。
系统须对每条指令所要访问的地址进行检查，如果发生越界，便发出越界中断请求，以停止该程序的执行。
如果这种检查完全用软件实现，则每执行一条指令，便须增加若干条指令去进行越界检查，这将显著降低程序的运行速度。因此，越界检查都由硬件实现。当然，对发生越界后的处理，还须与软件配合来完成。

地址映射

地址映射是逻辑地址到物理地址的映射。
为使程序能正确运行，存储器管理必须提供地址映射功能，以将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址。该功能应在硬件的支持下完成。

内存扩充

借助虚拟存储技术，从逻辑上去扩充内存容量，使用户所感觉到的内存容量比实际内存容量大得多；或者是让更多的用户程序能并发运行。
用于实现下述各功能：
(1) 请求调入功能。
(2) 置换功能。

1. 请求调入功能

概念：
- 当程序运行时，并非所有代码和数据都需要立即加载到物理内存中。
- 请求调入功能允许操作系统只将当前需要的程序部分（例如，代码页或数据页）加载到内存中。
- 当程序尝试访问不在内存中的部分时，会产生一个“缺页中断”，操作系统会响应这个中断，并将所需的部分从磁盘（或其他存储介质）加载到内存中。
作用：
- 提高内存利用率：只加载必要的部分，减少了内存的浪费。
- 支持更大的程序：允许程序使用比物理内存更大的地址空间。

2. 置换功能

概念：
- 当物理内存已满，而程序又需要加载新的部分时，操作系统必须腾出一些空间。
- 置换功能负责选择哪些内存中的部分应该被移出到磁盘（或其他存储介质），以便为新的部分腾出空间。
- 置换算法（例如，LRU、FIFO）用于决定哪些部分应该被置换。
作用：
- 管理有限的物理内存：确保在内存不足时，系统能够继续运行。
- 优化内存使用：通过合理的置换算法，尽量减少频繁的磁盘I/O操作。

总结

请求调入和置换是虚拟内存技术的关键组成部分。
它们共同工作，使得程序可以使用比实际物理内存更大的地址空间，并提高了内存的利用率。
虚拟内存是现代操作系统中至关重要的技术。

设备管理功能

缓冲管理

如果在I/O设备和CPU之间引入缓冲，则可有效地缓和CPU（高速）和I/O设备速度（低速）不匹配的矛盾，提高CPU的利用率，进而提高系统吞吐量。
因此，在现代计算机系统中，都毫无例外地在内存中设置了缓冲区，而且还可通过增加缓冲区容量的方法，来改善系统的性能。
最常见的缓冲区机制有单缓冲机制、能实现双向同时传送数据的双缓冲机制，以及能供多个设备同时使用的公用缓冲池机制。

设备分配

根据用户进程的I/O请求、系统的现有资源情况以及按照某种设备分配策略，为之分配其所需的设备。
如果在I/O设备和CPU之间，还存在着设备控制器和I/O通道时，还须为分配出去的设备分配相应的控制器和通道。
系统中应设置设备控制表、控制器控制表等数据结构，用于记录设备及控制器的标识符和状态。据这些表格可以了解指定设备当前是否可用，是否忙碌，以供进行设备分配时参考。
在进行设备分配时，应针对不同的设备类型而采用不同的设备分配方式。对于独占设备(临界资源)的分配，还应考虑到该设备被分配出去后，系统是否安全。设备使用完后，还应立即由系统回收。

设备处理

设备处理程序又称为设备驱动程序。
其基本任务是用于实现CPU和设备控制器之间的通信，即由CPU向设备控制器发出I/O命令，要求它完成指定的I/O操作；反之由CPU接收从控制器发来的中断请求，并给予迅速的响应和相应的处理。
处理过程是：
1. 设备处理程序首先检查I/O请求的合法性，了解设备状态是否是空闲的，了解有关的传递参数及设置设备的工作方式。
2. 然后，便向设备控制器发出I/O命令，启动I/O设备去完成指定的I/O操作。
设备驱动程序还应能及时响应由控制器发来的中断请求，并根据该中断请求的类型，调用相应的中断处理程序进行处理。对于设置了通道的计算机系统，设备处理程序还应能根据用户的I/O请求，自动地构成通道程序。

虚拟设备

（没介绍）

文件管理功能

文件存储空间的管理

为每个文件分配必要的外存空间，提高外存的利用率，并能有助于提高文件系统的运行速度。
为此，系统
1. 应设置相应的数据结构，用于记录文件存储空间的使用情况，以供分配存储空间时参考；
2. 还应具有对存储空间进行分配和回收的功能。
为了提高存储空间的利用率，对存储空间的分配，通常是采用离散分配方式，以减少外存零头，并以盘块为基本分配单位。盘块的大小通常为512 B~8 KB。

目录管理

为了使用户能方便地在外存上找到自己所需的文件，通常由系统为每个文件建立一个目录项。
目录项包括文件名、文件属性、文件在磁盘上的物理位置等。由若干个目录项又可构成一个目录文件。
目录管理的主要任务，是为每个文件建立其目录项，并对众多的目录项加以有效的组织，以实现方便的按名存取。即用户只须提供文件名，即可对该文件进行存取。其次，目录管理还应能实现文件共享，这样，只须在外存上保留一份该共享文件的副本。此外，还应能提供快速的目录查询手段，以提高对文件的检索速度。

文件的读/写管理和保护

文件的读/写管理。该功能是根据用户的请求，从外存中读取数据；或将数据写入外存。在进行文件读(写)时，系统先根据用户给出的文件名，去检索文件目录，从中获得文件在外存中的位置。然后，利用文件读(写)指针，对文件进行读(写)。一旦读(写)完成，便修改读(写)指针，为下一次读(写)做好准备。由于读和写操作不会同时进行，故可合用一个读/写指针。
文件保护。① 防止未经核准的用户存取文件； ② 防止冒名顶替存取文件； ③ 防止以不正确的方式使用文件。

用户接口

命令接口
(1) 联机用户接口（终端或控制台）
(2) 脱机用户接口（也称批处理用户接口）
程序接口

由一组系统调用组成，每一个系统调用都是一个能完成特定功能的子程序，每当应用程序要求OS提供某种服务(功能)时，便调用具有相应功能的系统调用。

图形接口

用户虽然可以通过联机用户接口来取得OS的服务，但这时要求用户能熟记各种命令的名字和格式，并严格按照规定的格式输入命令，这既不方便又花时间，于是，图形用户接口便应运而生。
图形用户接口采用了图形化的操作界面，用非常容易识别的各种图标(icon)来将系统的各项功能、各种应用程序和文件，直观、逼真地表示出来。用户可用鼠标或通过菜单和对话框，来完成对应用程序和文件的操作。
此时用户已完全不必像使用命令接口那样去记住命令名及格式，从而把用户从繁琐且单调的操作中解脱出来。

操作系统的结构设计

软件工程的基本概念

软件的含义

所谓软件，是指当计算机运行时，能提供所要求的【功能和性能】的【指令和程序】的集合，该程序能够正确地处理信息的数据结构；作为规范软件，还应具有描述程序功能需求以及程序如何操作使用的文档。
如果说，硬件是物理部件，那么，软件则是一种逻辑部件，它具有与硬件完全不同的特点。

软件工程的含义

软件工程是指运用【系统的、规范的和可定量】的方法，来【开发、运行和维护软件】；或者说，是采用工程的概念、原理、技术和方法，来开发与维护软件，其目的是为了解决在软件开发中所出现的编程随意、软件质量不可保证以及维护困难等问题。

传统的操作系统结构

操作系统是一个十分复杂的大型软件。为了控制该软件的复杂性，在开发OS时，先后引入了分解、模块化、抽象和隐蔽等方法。开发方法的不断发展，促进了OS结构的更新换代。这里，我们把第一代至第三代的OS结构，称为传统的OS结构，而把微内核的OS结构称为现代OS结构。

无结构操作系统

模块化OS结构

每个模块具有某方面的管理功能，如进程管理模块、存储器管理模块、I/O设备管理模块和文件管理模块等，并规定好各模块间的接口，使各模块之间能通过该接口实现交互，然后再进一步将各模块细分为若干个具有一定管理功能的子模块，如把进程管理模块又分为进程控制、进程同步、进程通信和进程调度等子模块，同样也要规定各子模块之间的接口。若子模块较大时，再进一步将它细分。
优点：
1. 提高了OS设计的正确性、可理解性和可维护性。
2. 增强了OS的可适应性。
3. 加速了OS的开发过程。
缺点：
1. 在开始设计OS时，对模块的划分及对接口的规定并不精确，而且还可能存在错误，因而很难保证按此规定所设计出的模块会完全正确，这将使在把这些模块装配成OS时发生困难；
2. 其次，从功能观点来划分模块时，未能将共享资源和独占资源加以区别；
3. 由于管理上的差异，又会使模块间存在着复杂的依赖关系使OS结构变得不清晰。

分层式OS结构

分层式结构设计的基本原则是：每一层都仅使用其底层所提供的功能和服务，这样可使系统的调试和验证都变得容易。
层次的设置：
1. 程序嵌套。通常OS的每个功能的实现，并非是只用一个程序便能完成的，而是要经由若干个软件层才有可能完成。因此在划分OS层次时，首先要考虑在实现OS 的每个功能时所形成的程序嵌套。例如，作业调度模块须调用进程控制模块；在为某作业创建一进程时，进程控制模块又须调用内存管理模块为新进程分配内存空间，可见，进程控制模块应在内存管理模块之上；而作业调度模块又应在更高层。
2. 运行频率。在分层结构中，各层次软件的运行速度是不同的，因为A1层软件能直接在物理机器上运行，故它有最高的运行速度。随着层次的增高，其相应软件的运行速度就随之下降，因而An层软件的运行速度最低。为了提高OS的运行效率，应该将那些经常活跃的模块放在最接近硬件的A1层，如时钟管理、进程调度，通常都放在A1层。
3. 公用模块。应把供多种资源管理程序调用的公用模块，设置在最低层，不然，会使比它低的层次模块由于无法调用它而须另外配置相应功能的模块。例如，用于对信号量进行操作的原语Signal和Wait。
  
  这里提到信号量（Semaphore）是因为它是操作系统中用于进程同步与互斥的重要机制。信号量操作（如 Signal 和 Wait）通常是多个资源管理模块都会用到的基本功能，因此应放置在系统的底层，作为公用模块提供服务。这样可以避免不同模块重复实现相同的功能，提高系统的结构合理性和资源利用效率。
4. 用户接口。为方便用户(程序)，OS向用户提供了“用户与OS的接口”，如命令接口、程序接口以及图形用户接口。这些接口应设置在OS的最高层，直接提供给用户使用。

微内核OS结构

客户/服务器模式(Client-Server Model)

为了提高OS的灵活性和可扩充性而将OS划分为两部分，一部分是用于提供各种服务的一组服务器(进程)，如用于提供进程管理的进程服务器、提供存储器管理的存储器服务器和提供文件管理的文件服务器等，所有这些服务器(进程)都运行在用户态。当有一用户进程(现在称为客户进程)要求读文件的一个盘块时，该进程便向文件服务器(进程)发出一个请求；当服务器完成了该客户的请求后，便给该客户回送一个响应。操作系统的另一部分是内核，用来处理客户和服务器之间的通信，即由内核来接收客户的请求，再将该请求送至相应的服务器；同时它也接收服务器的应答，并将此应答回送给请求客户。此外，在内核中还应具有其它一些机构，用于实现与硬件紧密相关的和一些较基本的功能。

平时我们提到 “服务器” 往往指的是云端或远程计算机提供的服务。但在操作系统（OS）内部，“服务器”指的是运行在用户态的系统进程，专门提供某些操作系统功能的服务。

单机环境下的客户/服务器模式

优点：
1. 提高了系统的灵活性和可扩充性。
2. 提高了OS的可靠性。
3. 可运行于分布式系统中。

面向对象的程序设计技术(Object-Orientated Programming)

面向对象技术的基本概念
面向对象技术是20世纪80年代初提出并很快流行起来的。该技术是基于“抽象”和“隐蔽”原则来控制大型软件的复杂度的。所谓对象，是指在现实世界中具有相同属性、服从相同规则的一系列事物的抽象，而把其中的具体事物称为对象的实例。OS中的各类实体如进程、线程、消息、存储器等，都使用了对象这一概念，相应地，便有进程对象线程对象、存储器对象等。
优点
1. 可修改性和可扩充性。由于隐蔽了表示实体的数据和操作，因而可以改变对象的表示而不会影响其它部分，从而可以方便地改变老的对象和增加新的对象。
2. 继承性。继承性是面向对象技术所具有的重要特性。继承性是指子对象可以继承父对象的属性，这样，在创建一个新的对象时，便可减少大量的时空开销。
3. 正确性和可靠性。由于对象是构成操作系统的基本单元，可以独立地对它进行测试，这样，比较易于保证其正确性和可靠性，从而比较容易保证整个系统的正确性和可靠性。

微内核技术

所谓微内核技术，是指精心设计的、能实现现代OS核心功能的小型内核，它与一般的OS(程序)不同，它更小更精炼，它不仅运行在核心态，而且开机后常驻内存，它不会因内存紧张而被换出内存。微内核并非是一个完整的OS，而只是为构建通用OS提供一个重要基础。由于在微内核OS结构中，通常都采用了客户/服务器模式，因此OS的大部分功能和服务，都是由若干服务器来提供的，如文件服务器、作业服务器和网络服务器等。
微内核所提供的功能，通常都是一些最基本的功能，如进程管理、存储器管理、进程间通信、低级I/O功能。

第二章进程管理

进程的基本概念

程序顺序执行时的特征

顺序性
封闭性
可再现性

前趋图

前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。
在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。

程序并发执行时的特征

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

进程的特征与状态

进程的特征

结构特征
动态性
并发性
独立性
异步性

较典型的进程的定义有：

进程是程序的一次执行。
进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。
在引入了进程实体的概念后，我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。

进程的三种基本状态

就绪(Ready)状态
执行状态
阻塞状态

挂起状态

引入挂起状态的原因
1. 终端用户的请求。
2. 父进程请求。
3. 负荷调节的需要。
4. 操作系统的需要。

进程状态的转换

在操作系统中，进程可能会经历多个状态，包括：

运行（Running）：进程正在 CPU 上执行。
就绪（Ready）：进程已获得所有必要资源，等待 CPU 调度执行。
- 活动就绪（Active Ready）：进程保留在内存中，随时可以被 CPU 调度。
- 静止就绪（Suspended Ready）：进程被挂起，暂时存放在外存中，需调回内存后才能被调度执行。
阻塞（Blocked）：进程正在等待某个事件（如 I/O 结束）。
- 活动阻塞（Active Blocked）：进程在内存中等待事件。
- 静止阻塞（Suspended Blocked）：进程被挂起，存放在外存，且仍在等待事件发生。

进程状态的转换

活动就绪→静止就绪。

由于系统资源管理（如内存不足），某个就绪进程可能会被挂起并移至外存。
活动阻塞→静止阻塞。

系统需要腾出内存，某个正在等待 I/O 或其他事件的阻塞进程被挂起并移至外存。
静止就绪→活动就绪。

当系统资源充足（如内存可用）时，进程从外存调入内存，回到“活动就绪”状态，等待 CPU 调度。
静止阻塞→活动阻塞。

进程从外存恢复到内存，但仍然在等待事件完成。

进程控制块（PCB，Process Control Block）

进程控制块的作用：
- 是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。
进程控制块中的信息：
1. 进程标识符（两种）
1. 内部标识符。
  
  在所有的操作系统中，都为每一个进程赋予一个惟一的数字标识符，它通常是一个进程的序号。
  设置内部标识符主要是为了方便系统使用。
2. 外部标识符。
  
  它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。
  为了描述进程的家族关系，还应设置父进程标识及子进程标识。
  此外，还可设置用户标识，以指示拥有该进程的用户。
1. 处理机状态
  
  处理机状态信息主要是由处理机的各种寄存器中的内容组成的。
1. 通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，有 8~32 个通用寄存器，在RISC结构的计算机中可超过 100 个；
2. 指令计数器，其中存放了要访问的下一条指令的地址；
3. 程序状态字PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；
4. 用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。
1. 进程调度信息
  
  在PCB中还存放一些与进程调度和进程对换有关的信息，包括：
1. 进程状态，指明进程的当前状态，作为进程调度和对换时的依据；
2. 进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；
3. 进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；
4. 事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。
1. 进程控制信息
  
  进程控制信息包括：
1. 程序和数据的地址，是指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；
2. 进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中；
3. 资源清单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单；
4. 链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。
进程控制块的组织方式：
1. 链接方式
  PCB链接队列示意图
2. 索引方式
  按索引方式组织PCB

进程控制

进程的创建

进程图

进程树

引起进程创建的事件

用户登录。
作业调度。
提供服务。
应用请求。

进程的创建

申请空白PCB。
为新进程分配资源。
初始化进程控制块。
将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。

进程的终止

引起进程终止(Termination of Process)的事件

正常结束
在任何计算机系统中，都应有一个用于表示进程已经运行完成的指示。例如，在批处理系统中，通常在程序的最后安排一条Holt指令或终止的系统调用。当程序运行到Holt指令时，将产生一个中断，去通知OS本进程已经完成。在分时系统中，用户可利用Logs off去表示进程运行完毕，此时同样可产生一个中断，去通知OS进程已运行完毕。
异常结束
在进程运行期间，由于出现某些错误和故障而迫使进程终止。这类异常事件很多，常见的有：
1. 越界错误。这是指程序所访问的存储区，已越出该进程的区域；
2. 保护错误。进程试图去访问一个不允许访问的资源或文件，或者以不适当的方式进行访问，例如，进程试图去写一个只读文件；
3. 非法指令。程序试图去执行一条不存在的指令。出现该错误的原因，可能是程序错误地转移到数据区，把数据当成了指令；
4. 特权指令错误。用户进程试图去执行一条只允许OS执行的指令；
5. 运行超时。进程的执行时间超过了指定的最大值；
6. 等待超时。进程等待某事件的时间，超过了规定的最大值；
7. 算术运算错。进程试图去执行一个被禁止的运算，例如，被0除；
8. I/O故障。这是指在I/O过程中发生了错误等。
外界干预
外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。这些干预有：
1. 操作员或操作系统干预。由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程；
2. 父进程请求。由于父进程具有终止自己的任何子孙进程的权利，因而当父进程提出请求时，系统将终止该进程；
3. 父进程终止。当父进程终止时，OS也将他的所有子孙进程终止。

进程的终止过程

根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。
若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。
若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。
将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。
将被终止进程(它的PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息。

进程的阻塞与唤醒

引起进程阻塞和唤醒的事件

请求系统服务
启动某种操作
新数据尚未到达
无新工作可做

进程阻塞过程

正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。进入block过程后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞(等待)队列。最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态(在PCB中)，再按新进程的PCB中的处理机状态设置CPU的环境。

进程唤醒过程

正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。进入block过程后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞(等待)队列。最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态(在PCB中)，再按新进程的PCB中的处理机状态设置CPU的环境。

进程的挂起与激活

进程的挂起过程

当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起，系统将利用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后，若被挂起的进程正在执行，则转向调度程序重新调度。

进程的激活过程

当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语active( )将指定进程激活。激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。

进程同步

进程同步的基本概念

两种形式的制约关系

间接相互制约关系
直接相互制约关系

临界资源

生产者-消费者(producer-consumer)问题

生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。
它描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。

我们可利用一个数组来表示上述的具有n个(0，1，…，n-1)缓冲区的缓冲池。用输入指针in来指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，输入指针加1；用一个输出指针out来指示下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，输出指针加1。由于这里的缓冲池是组织成循环缓冲的，故应把输入指针加1表示成 in:=(in+1)mod n；输出指针加1表示成out:=(out+1) mod n。当(in+1) mod n=out时表示缓冲池满；而in=out则表示缓冲池空。此外，还引入了一个整型变量counter, 其初始值为0。每当生产者进程向缓冲池中投放一个产品后，使counter加1；反之，每当消费者进程从中取走一个产品时，使counter减1。生产者和消费者两进程共享下面的变量：
1
2
3
4
5
Var n, integer;
type item=…;
var buffer:array［0, 1, …, n-1］ of item;
in, out: 0, 1, …, n-1;
counter: 0, 1, …, n;

指针in和out初始化为1。在生产者和消费者进程的描述中，no-op是一条空操作指令，while condition do no-op语句表示重复的测试条件(condication)，重复测试应进行到该条件变为false(假)，即到该条件不成立时为止。在生产者进程中使用一局部变量nextp，用于暂时存放每次刚生产出来的产品；而在消费者进程中，则使用一个局部变量nextc,用于存放每次要消费的产品。

producer: repeat
     …
     produce an item in nextp;
     …
     while counter=n do no-op;
     buffer［in］:= nextp;
     in := in+1 mod n;
     counter := counter+1;
    until false;
consumer: repeat
     while counter=0 do no-op;
     nextc := buffer［out］;
     out := (out+1) mod n;
     counter := counter-1;
     consumer the item in nextc;
    until false;

虽然上面的生产者程序和消费者程序，在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时，就会出现差错，问题就在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述：
1
2
3
register1 := counter; register2 := counter;
register1 := register1 + 1; register2 := register2 - 1;
counter := register1; counter := register2;

假设：counter的当前值是5。如果生产者进程先执行左列的三条机器语言语句，然后消费者进程再执行右列的三条语句，则最后共享变量counter的值仍为5；反之，如果让消费者进程先执行右列的三条语句，然后再让生产者进程执行左列的三条语句，counter值也还是5，但是，如果按下述顺序执行：

register1 := counter; (register1 = 5)
register1 := register1 + 1; (register1 = 6)
register2 := counter; (register2 = 5)
register2 := register2 - 1; (register2 = 4)
counter := register1; (counter = 6)
counter := register2; (counter = 4)

临界区

可以把临界资源想象成一间只有一个人的厕所。
- “进入区段”就是你走到厕所门口，看看里面有没有人。
- “临界区”就是你在厕所里面。
- “退出区段”就是你从厕所出来，并且告诉别人厕所现在没人了。
- “剩余区段”就是你上完厕所之后的其他活动。

同步机制应遵循的规则

空闲让进
忙则等待
有限等待
让权等待

信号量机制

1. 信号量 (Semaphore) 是什么？

信号量是一种用于控制多个进程或线程访问共享资源的同步机制。你可以把它想象成一个计数器，它记录了可用资源的数量。

计数器 (value):
- 如果计数器大于 0，表示有可用资源，进程可以继续访问。
- 如果计数器等于 0，表示没有可用资源，进程需要等待。
作用:
- 互斥 (Mutual Exclusion): 确保同一时刻只有一个进程可以访问临界资源，防止数据竞争。
- 同步 (Synchronization): 控制进程的执行顺序，确保它们按照特定的顺序访问资源。

整型信号量 vs. 记录型信号量

2. 整型信号量 vs. 记录型信号量

整型信号量:
- 只包含一个整数变量 S，表示可用资源的数量。
- 当 S <= 0 时，进程会不断地测试 S 的值，直到 S > 0，这种方式称为“忙等”。
- “忙等”会浪费 CPU 资源，因为它让进程不断地循环检查，而不是让出 CPU。

记录型信号量:

为了解决“忙等”的问题，记录型信号量引入了一个进程链表 L。
当进程需要等待资源时，它会被加入到链表 L 中，并进入睡眠状态，让出 CPU。
当资源可用时，操作系统会唤醒链表 L 中的一个等待进程。
记录型信号量的数据结构：
1
2
3
4
type semaphore = record
value : integer
L : list of process;
end
- value: 整数，表示可用资源的数量。
- L: 进程链表，存储等待资源的进程。

wait(S)和signal(S)操作可描述为：

procedure wait(S)
var S : semaphore;
begin
  S.value := S.value-1;
  if S.value < 0 then block(S,L)
end
procedure signal(S)
var S : semaphore;
begin
  S.value := S.value+1;
  if S.value <= 0 then wakeup(S,L);
end

wait(S) 操作 (也称为 P 操作)
- 作用：
  - wait(S) 用于请求一个资源。当进程需要访问临界资源时，它会调用 wait(S)。
  - 它的主要目的是减少信号量 S 的值，并检查是否需要等待。
signal(S) 操作 (也称为 V 操作)
- 作用：
  - signal(S) 用于释放一个资源。当进程完成对临界资源的访问后，它会调用 signal(S)。
  - 它的主要目的是增加信号量 S 的值，并唤醒等待的进程（如果有）。

3. 代码解释

type semaphore = record ... end: 这段代码定义了一个名为 semaphore 的记录类型，它包含两个字段：
- value : integer: 一个整数类型的字段，用于存储信号量的计数值。
- L : list of process: 一个进程链表类型的字段，用于存储等待该信号量的进程。
wait(S)
1
2
3
4
5
6
procedure wait(S)
var S : semaphore;
begin
S.value := S.value - 1; // 减少信号量的值
if S.value < 0 then block(S, L) // 如果资源不足，则阻塞进程
end
1. S.value := S.value - 1;:
  - 这行代码将信号量 S 的值减 1。
  - 如果 S.value 原本是正数，减 1 后仍然是正数或 0，表示还有可用资源。
  - 如果 S.value 原本是 0，减 1 后变为负数，表示资源已被用完，进程需要等待。
2. if S.value < 0 then block(S, L):
  - 这行代码检查 S.value 是否小于 0。
  - 如果 S.value < 0，表示没有可用资源，进程需要等待。
  - block(S, L) 函数会将当前进程加入到信号量 S 的等待队列 L 中，并使进程进入阻塞（睡眠）状态，让出 CPU。
signal(S)
1
2
3
4
5
6
procedure signal(S)
var S : semaphore;
begin
S.value := S.value + 1; // 增加信号量的值
if S.value <= 0 then wakeup(S, L); // 如果有等待的进程，则唤醒一个
end
1. S.value := S.value + 1;:
  - 这行代码将信号量 S 的值加 1。
  - 这表示资源被释放，可用资源数量增加。
2. if S.value <= 0 then wakeup(S, L);:
  - 这行代码检查 S.value 是否小于等于 0。
  - 如果 S.value <= 0，表示有进程在等待该资源（因为 S.value 可能是负数，表示等待的进程数）。
  - wakeup(S, L) 函数会从信号量 S 的等待队列 L 中唤醒一个进程，使其进入就绪状态，等待 CPU 调度。

4. 记录型信号量的工作原理

P 操作 (Wait):
- 当一个进程想要访问临界资源时，它会执行 P 操作。
- P 操作会减少信号量的 value 值。
- 如果 value 变为负数，表示没有可用资源，进程会被加入到链表 L 中并进入睡眠状态。
V 操作 (Signal):
- 当一个进程释放临界资源时，它会执行 V 操作。
- V 操作会增加信号量的 value 值。
- 如果 value 变为非负数，表示有 value 个可用资源，操作系统会从链表 L 中唤醒一个进程。

5. 总结

记录型信号量通过引入进程链表和睡眠/唤醒机制，实现了 “让权等待” ，解决了整型信号量的 “忙等” 问题，显著提高了 CPU 的利用率。

AND型信号量

1. AND 型信号量的概念

AND 型信号量是一种扩展的信号量机制，用于解决进程需要同时申请多个资源的情况。
在传统的信号量机制中，进程每次只能申请一个资源。但在实际应用中，很多进程需要同时申请多个资源才能继续执行。
AND 型信号量允许进程一次性申请多个资源，只有当所有资源都可用时，进程才能继续执行。

2. AND 型信号量的作用

避免死锁：
- 死锁是指多个进程因竞争资源而互相等待，导致所有进程都无法继续执行的情况。
- AND 型信号量通过一次性申请所有资源，避免了进程逐步申请资源时可能发生的死锁。
提高资源利用率：
- 通过一次性申请所有资源，进程可以更快地获得所需的全部资源，从而提高资源利用率。
- 减少了进程多次申请资源带来的系统开销。

3. AND 型信号量的工作原理

当一个进程需要同时申请多个资源时，它会执行 AND 型 P 操作（也称为 Swait 操作）。
Swait 操作会检查所有需要的资源是否都可用。
如果所有资源都可用，Swait 操作会一次性减少所有相关信号量的值，进程继续执行。
如果任何一个资源不可用，Swait 操作会阻塞进程，并将进程放入所有相关信号量的等待队列中。
当其他进程释放资源时，它们会执行 AND 型 V 操作（也称为 Ssignal 操作）。
Ssignal 操作会增加相关信号量的值，并检查是否有等待进程可以被唤醒。
只有当所有相关资源都可用时，等待进程才会被唤醒。

4. 代码

Swait(S1, S2, …, Sn)
    if Si≥1 and … and Sn≥1 then
        for i := 1 to n do
        Si := Si-1;
        endfor
    else
    place the process in the waiting queue associated with the first Si found   with Si＜1, and set the program count of this process to the beginning of Swait operation
    endif
Ssignal(S1, S2, …, Sn)
    for i := 1 to n do
    Si=Si+1;
    Remove all the process waiting in the queue associated with Si into the ready queue.
  endfor;

5. 总结

AND 型信号量是一种用于解决进程需要同时申请多个资源的同步机制。
它通过一次性申请所有资源，避免了死锁，提高了资源利用率。
AND 型 P 操作（Swait）用于申请多个资源，AND 型 V 操作（Ssignal）用于释放资源。

信号量集

是对 AND 型信号量的扩展。
它不仅能一次性申请/释放多个资源，还能指定每个资源所需的具体数量。
这种机制更加灵活，可以更好地满足实际应用的需求。

Swait(S1, t1, d1, …, Sn, tn, dn)
    if Si ≥ t1 and … and Sn ≥ tn then
      for i := 1 to n do
        Si := Si - di;
      endfor
    else
    Place the executing process in the waiting queue of the first Si with Si＜ti and set its program counter to the beginning of the Swait Operation. 
    endif

Ssignal(S1, d1, …, Sn, dn)
    for i := 1 to n do
      Si ∶= Si + di;
      Remove all the process waiting in the queue associated with Si into the ready queue
    endfor;

信号量集的三种特殊情况

信号量集是一种强大的资源管理工具，通过 Swait 操作，我们可以一次性申请多个资源，并指定每个资源的需求量和阈值。以下是信号量集的三种特殊情况，它们展示了信号量集的灵活性和实用性：

(1) 资源批量申请：Swait(S, d, d)

说明： 这种形式的 Swait 操作仅涉及单个信号量 S，但允许进程一次性申请 d 个资源。
特性： 只有当信号量 S 的当前值大于等于 d 时，即现有可用资源数不少于 d 时，才会分配资源。否则，进程将进入等待状态。
应用： 适用于需要批量申请同一类型资源的场景，例如，一次性申请多个打印机或内存块。

(2) 简化为传统信号量：Swait(S, 1, 1)

说明： 这种形式的 Swait 操作实际上退化为传统的记录型信号量或互斥信号量。
特性：
- 当 S > 1 时，它等同于记录型信号量，允许多个进程并发访问资源。
- 当 S = 1 时，它等同于互斥信号量（mutex），确保同一时刻只有一个进程可以访问资源。
应用： 适用于需要互斥或同步的简单资源访问场景。

(3) 可控开关：Swait(S, 1, 0)

说明： 这是一种特殊且实用的信号量操作，用于实现可控的资源访问开关。
特性：
- 当 S ≥ 1 时，允许多个进程进入特定区域。
- 当 S 变为 0 时，阻止任何新进程进入该区域。
- 本质上，它充当了一个开关，可以动态地控制对特定区域的访问。
应用： 适用于需要动态控制资源访问权限的场景，例如，控制对某个共享缓冲区的访问或实现某种形式的门禁机制。

利用信号量实现前趋关系

举例

Var a,b,c,d,e,f,g; semaphore := 0,0,0,0,0,0,0;
  begin
    parbegin
      begin S1; signal(a); signal(b); end;
      begin wait(a); S2; signal(c); signal(d); end;
      begin wait(b); S3; signal(e); end;
      begin wait(c); S4; signal(f); end;
      begin wait(d); S5; signal(g); end;
      begin wait(e); wait(f); wait(g); S6; end;
    parend
   end

经典进程的同步问题

生产者-消费者问题

生产者-消费者问题是并发编程中一个经典的同步问题，它描述了两个或多个进程共享一个固定大小的缓冲区。生产者进程负责生成数据并放入缓冲区，而消费者进程则负责从缓冲区取出数据并进行处理。这个问题抽象了许多实际应用场景，例如：

输入/输出： 输入进程作为生产者，计算进程作为消费者；计算进程作为生产者，打印进程作为消费者。
线程池： 生产者线程生成任务，消费者线程从队列中取出任务执行。

核心挑战：

互斥访问： 多个生产者和消费者需要互斥地访问共享缓冲区，避免数据竞争。
同步： 生产者不能在缓冲区满时继续生产，消费者不能在缓冲区空时继续消费。

1. 利用记录型信号量解决生产者-消费者问题

场景描述：

共享缓冲区：包含 n 个缓冲区。
信号量：
- mutex：互斥信号量，初始值为 1，用于控制对缓冲区的互斥访问。
- empty：资源信号量，初始值为 n，表示空缓冲区的数量。
- full：资源信号量，初始值为 0，表示满缓冲区的数量。
指针：
- in：指向下一个要放入数据的空缓冲区。
- out：指向下一个要取出数据的满缓冲区。

代码实现：

Var mutex, empty, full: semaphore := 1, n, 0;
buffer: array[0, ..., n-1] of item;
in, out: integer := 0, 0;

begin
    parbegin
        producer: begin
            repeat
                // 生产数据
                producer an item nextp;

                wait(empty);  // 检查是否有空缓冲区
                wait(mutex);  // 获取互斥锁

                buffer[in] := nextp;
                in := (in + 1) mod n;

                signal(mutex); // 释放互斥锁
                signal(full);  // 增加满缓冲区计数

            until false;
        end

        consumer: begin
            repeat
                wait(full);   // 检查是否有满缓冲区
                wait(mutex);  // 获取互斥锁

                nextc := buffer[out];
                out := (out + 1) mod n;

                signal(mutex); // 释放互斥锁
                signal(empty); // 增加空缓冲区计数

                // 消费数据
                consumer the item in nextc;

            until false;
        end
    parend
end

关键点：

互斥： mutex 信号量确保了对缓冲区的互斥访问。
同步：
- empty 信号量控制生产者，防止缓冲区溢出。
- full 信号量控制消费者，防止缓冲区为空时消费。
顺序： wait(empty) 和 wait(mutex) 的顺序不能颠倒，否则可能导致死锁。

2. 利用 AND 信号量解决生产者-消费者问题

代码实现：

var mutex, empty, full: semaphore := 1, n, 0;
buffer: array[0, ..., n-1] of item;
in, out: integer := 0, 0;

begin
    parbegin
        producer: begin
            repeat
                // 生产数据
                produce an item in nextp;

                Swait(empty, mutex); // 同时申请空缓冲区和互斥锁

                buffer[in] := nextp;
                in := (in + 1) mod n;

                Ssignal(mutex, full); // 同时释放互斥锁和增加满缓冲区计数

            until false;
        end

        consumer: begin
            repeat
                Swait(full, mutex); // 同时申请满缓冲区和互斥锁

                nextc := buffer[out];
                out := (out + 1) mod n;

                Ssignal(mutex, empty); // 同时释放互斥锁和增加空缓冲区计数

                // 消费数据
                consumer the item in nextc;

            until false;
        end
    parend
end

关键点：

原子性： Swait 和 Ssignal 操作保证了资源申请和释放的原子性，避免了死锁的可能。
简化： 使用 AND 信号量可以简化代码，提高效率。

哲学家进餐问题

哲学家进餐问题是并发编程中一个经典的同步问题，它描述了五个哲学家围坐在一张圆桌旁，每两个哲学家之间都有一根筷子。哲学家有两种状态：思考和进餐。当哲学家想进餐时，他必须拿起他左右两边的筷子才能进餐。进餐完毕后，他会放下筷子继续思考。

核心挑战：

死锁： 如果每个哲学家都拿起自己左边的筷子，然后等待右边的筷子，就会发生死锁。
饥饿： 如果某个哲学家一直无法获得筷子，就会发生饥饿。

1. 利用信号量解决哲学家进餐问题

场景描述：

五个哲学家，五根筷子。
信号量：
- chopstick[5]：包含五个互斥信号量的数组，每个信号量代表一根筷子，初始值为 1。

代码实现：

var chopstick[5] semaphore := [1, 1, 1, 1, 1];

begin
    parbegin
        philosopher[i]: begin // i = 0, 1, 2, 3, 4
            repeat
                // 思考
                think();

                wait(chopstick[i]);          // 拿起左边的筷子
                wait(chopstick[(i+1) mod 5]); // 拿起右边的筷子

                // 进餐
                eat();

                signal(chopstick[i]);          // 放下左边的筷子
                signal(chopstick[(i+1) mod 5]); // 放下右边的筷子

            until false;
        end
    parend
end

问题分析：

死锁： 如果所有哲学家同时拿起左边的筷子，就会发生死锁。
饥饿： 如果某个哲学家一直无法获得筷子，就会发生饥饿。

2. 避免死锁的解决方案

方案一：最多允许四个哲学家同时进餐

原理： 这样可以保证至少有一个哲学家可以拿到两根筷子，从而避免死锁。
实现： 增加一个计数信号量 count，初始值为 4。哲学家在拿起筷子之前，需要先 wait(count)，进餐完毕后 signal(count)。

方案二：奇数号哲学家先拿左边的筷子，偶数号哲学家先拿右边的筷子

原理： 这样可以打破死锁的条件。
实现： 修改哲学家拿起筷子的顺序。

方案三：使用条件变量（PPT无）

原理： 使用条件变量可以更灵活地控制哲学家的状态。
实现： 每个哲学家都有一个状态变量，表示其思考、饥饿或进餐状态。哲学家在拿起筷子之前，需要检查其左右邻居的状态。

方案四：使用AND信号量（最简洁）

var chopstick[5] semaphore := [1, 1, 1, 1, 1];

begin
    parbegin
        philosopher[i]: begin // i = 0, 1, 2, 3, 4
            repeat
                // 思考
                think();

                // 尝试同时拿起左右两边的筷子
                Swait(chopstick[i], chopstick[(i+1) mod 5]);

                // 进餐
                eat();

                // 同时放下左右两边的筷子
                Ssignal(chopstick[i], chopstick[(i+1) mod 5]);

            until false;
        end
    parend
end

读者-写者问题

1. 记录型信号量

为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。另外，再设置一个整型变量Readcount表示正在读的进程数目。由于只要有一个Reader进程在读，便不允许Writer进程去写。因此，仅当Readcount=0, 表示尚无Reader进程在读时，Reader进程才需要执行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader进程便可去读，相应地，做Readcount+1操作。同理，仅当Reader进程在执行了Readcount减1操作后其值为0时，才须执行signal(Wmutex)操作，以便让Writer进程写。又因为Readcount是一个可被多个Reader进程访问的临界资源，因此，应该为它设置一个互斥信号量rmutex。

Var rmutex, wmutex:semaphore := 1,1;
    Readcount:integer := 0;
    begin
    parbegin
      Reader:begin
        repeat
          wait(rmutex);
          if readcount=0 then
          wait(wmutex);
          Readcount := Readcount+1;
          signal(rmutex);
          …
          perform read operation;
          …
          wait(rmutex);
          readcount := readcount-1;
          if readcount=0 then 
          signal(wmutex);
          signal(rmutex);
        until false;
      end
      writer:begin
        repeat
          wait(wmutex);
          perform write operation;
          signal(wmutex);
        until false;
      end
    parend
    end

2. 信号量集

Var RN integer;
    L, mx:semaphore := RN,1;
    begin
    parbegin
      reader:begin
        repeat
          Swait(L,1,1);
          Swait(mx,1,0);
          …
          perform read operation;
          …
          Ssignal(L,1);
        until false;
      end
      writer:begin
        repeat
          Swait(mx,1,1; L,RN,0);
          perform write operation;
          Ssignal(mx,1);
        until false;
      end
    parend
  end

管程机制

管程的基本概念

管程（Monitor）是一种用于多线程同步的机制，它提供了一种更高级、更安全的共享资源访问方式。

核心概念

共享资源封装：
- 管程将共享变量以及对这些变量的所有操作都封装在一个模块中。这样，所有对共享资源的访问都必须通过管程提供的接口进行，从而避免了直接访问可能导致的数据竞争。
互斥访问：
- 管程保证在任何时刻，最多只有一个线程可以进入管程执行。这种互斥性确保了共享数据的一致性。
条件变量：
- 管程内部通常包含条件变量，允许线程在不满足特定条件时等待，并在条件满足时被唤醒。这使得线程可以更灵活地进行同步。

主要特点

简化同步：
- 管程通过集中管理共享资源和同步操作，简化了并发编程的复杂性。
提高安全性：
- 管程的互斥访问特性和条件变量机制，减少了因不正确的同步操作而导致的数据竞争和死锁等问题。
模块化：
- 管程将共享资源和相关操作封装在一起，提高了代码的模块化和可维护性。

应用

管程被广泛应用于各种并发编程场景，例如：
- 操作系统中的进程同步
- 多线程应用程序中的共享资源管理
- 数据库系统中的并发控制

与信号量的区别

与信号量相比，管程提供了一种更高级别的同步机制，它将共享资源的访问控制和同步操作封装在一起，使得并发编程更加安全和可靠。

在java语言中的体现

java中的synchronized关键字和wait(),notify(),notifyAll()这三个方法是java中实现管程技术的组成部分。

总结

管程是一种强大的同步工具，它通过封装共享资源和提供高级同步机制，简化了并发编程，提高了程序的安全性和可靠性。

利用管程解决生产者-消费者问题

使用管程，我们可以将缓冲区和相关操作封装在一个模块中，并利用条件变量实现同步。

type producer-consumer=monitor
  Var in,out,count:integer;
    buffer:array［0,…,n-1］ of item;
    notfull, notempty:condition;
    procedure entry put(item)
      begin
        if count≥n then notfull.wait;
          buffer(in) := nextp;
          in := (in+1) mod n;
          count := count+1;
        if notempty.queue then 
          notempty.signal;
      end
    procedure entry get(item)
      begin
        if count≤0 then notempty.wait;
          nextc := buffer(out);
          out := (out+1) mod n;
          count := count-1;
        if notfull.quene then 
          notfull.signal;
      end
      begin 
        in := out := 0; 
        count := 0 
      end

在利用管程解决生产者-消费者问题时，其中的生产者和消费者可描述为：

producer:begin
  repeat
  produce an item in nextp;
  PC.put(item);
  until false;
end
consumer:begin
  repeat
  PC.get(item);
  consume the item in nextc;
  until false;
end

进程通信

进程通信的类型

共享存储器系统
(1) 基于共享数据结构的通信方式
(2) 基于共享存储区的通信方式
消息传递系统

消息传递系统是一种强大的通信机制，它在分布式系统和并发编程中发挥着重要的作用。它通过解耦、异步和可靠的通信方式，提高了系统的灵活性和可扩展性。

管道

管道是一种简单而有效的进程间通信机制，它通过单向的数据流和缓冲区，实现了进程之间的数据交换。

消息传递通信的实现方法

直接通信方法

间接通信方法

信箱的创建和撤销
消息的发送和接收

信箱分为三类：

私用信箱（用户为自己创建，只能自己读；作为进程的一部分，进程结束信箱消失；单向通信链路）
公用信箱（操作系统创建，给所有核准进程用；系统运行期间始终存在；双向通信链路）
共享信箱（某进程船舰，拥有者和共享者可取信息）

信箱通信时，发送/接受进程之间的四种关系：

一对一关系（这时可为发送进程和接收进程建立一条两者专用的通信链路，使两者之间的交互不受其他进程的干扰）
多对一关系（允许提供服务的进程与多个用户进程之间进行交互，也称为客户/服务器交互(client/server interaction)）
一对多关系（允许一个发送进程与多个接收进程进行交互，使发送进程可用广播方式，向接收者(多个)发送消息）
多对多关系（允许建立一个公用信箱，让多个进程都能向信箱中投递消息；也可从信箱中取走属于自己的消息）

消息传递系统实现中的若干问题

通信链路

为使在发送进程和接收进程之间能进行通信，必须在两者之间建立一条通信链路。
有两种方式建立通信链路：
1. 为使在发送进程和接收进程之间能进行通信，必须在两者之间建立一条通信链路。有两种方式建立通信链路。
  
  这种方式主要用于计算机网络中。
2. 发送进程无须明确提出建立链路的请求，只须利用系统提供的发送命令(原语)，系统会自动地为之建立一条链路。
  
  这种方式主要用于单机系统中。
根据连接方法分类通信链路：
1. 点—点连接通信链路，这时的一条链路只连接两个结点(进程)；
2. 多点连接链路，指用一条链路连接多个(n＞2)结点(进程)。
根据通信方式分类通信链路：
1. 单向通信链路，只允许发送进程向接收进程发送消息；
2. 双向链路，既允许由进程A向进程B发送消息，也允许进程B同时向进程A发送消息。

消息的格式

在某些OS中，消息是采用比较短的定长消息格式，这减少了对消息的处理和存储开销。这种方式可用于办公自动化系统中，为用户提供快速的便笺式通信；但这对要发送较长消息的用户是不方便的。
在有的OS中，采用另一种变长的消息格式，即进程所发送消息的长度是可变的。系统在处理和存储变长消息时，须付出更多的开销，但方便了用户。
这两种消息格式各有其优缺点，故在很多系统(包括计算机网络)中，是同时都用的。

进程同步的方式

发送进程阻塞、接收进程阻塞。
发送进程不阻塞、接收进程阻塞。
发送进程和接收进程均不阻塞。

消息缓冲队列通信机制

数据结构

在消息缓冲队列通信方式中，主要利用的数据结构是消息缓冲区。它可描述如下：

type message buffer=record
  sender; 发送者进程标识符
  size; 消息长度
  text; 消息正文
  next; 指向下一个消息缓冲区的指针
end

PCB中有关通信的数据项。在利用消息缓冲队列通信机制时，在设置消息缓冲队列的同时，还应增加用于对消息队列进行操作和实现同步的信号量，并将它们置入进程的PCB中。在PCB中应增加的数据项可描述如下：
1
2
3
4
5
6
7
type processcontrol block=record
…
mq; 消息队列队首指针
mutex; 消息队列互斥信号量
sm; 消息队列资源信号量
…
end

发送原语

procedure send(receiver, a)
  begin
    getbuf(a.size,i); 根据a.size申请缓冲区；
    i.sender:=a.sender; 将发送区a中的信息复制到消息缓冲区之中；
    i.size:=a.size;
    i.text:=a.text;
    i.next:=0;
    getid(PCB set, receiver.j); 获得接收进程内部标识符；
    wait(j.mutex);
    insert(j.mq, i); 将消息缓冲区插入消息队列；
    signal(j.mutex);
    signal(j.sm);
  end

接受原语

procedure receive(b)
  begin
    j:=internal name; j为接收进程内部的标识符；
    wait(j.sm);
    wait(j.mutex);
    remove(j.mq, i); 将消息队列中第一个消息移出；
    signal(j.mutex);
    b.sender:=i.sender; 将消息缓冲区i中的信息复制到接收区b;
    b.size:=i.size;
    b.text:=i.text;
  end

线程

线程的基本概念

为使程序能并发执行，系统还必须进行以下的一系列操作：
1. 创建进程
2. 撤销进程
3. 进程切换

线程的属性

轻型实体
独立调度和分派的基本单位
可并发执行
共享进程资源

线程的状态

状态参数

在OS中的每一个线程都可以利用线程标识符和一组状态参数进行描述。
状态参数通常有这样几项：
1. 寄存器状态，它包括程序计数器PC和堆栈指针中的内容；
2. 堆栈，在堆栈中通常保存有局部变量和返回地址；
3. 线程运行状态，用于描述线程正处于何种运行状态；
4. 优先级，描述线程执行的优先程度；
5. 线程专有存储器，用于保存线程自己的局部变量拷贝；
6. 信号屏蔽，即对某些信号加以屏蔽。

线程运行状态

三种基本状态：
1. 执行状态
2. 就绪状态
3. 阻塞状态

线程的创建和终止

在创建新线程时，需要利用一个线程创建函数（或系统调用），并提供相应的参数，如指向线程主程序的入口指针、堆栈的大小，以及用于调度的优先级等。
在线程创建函数执行完后，将返回一个线程标识符供以后使用。
终止线程的方式有两种：
1. 在线程完成了自己的工作后自愿退出；
2. 线程在运行中出现错误或由于某种原因而被其它线程强行终止。

多线程OS中的进程

在多线程OS中，进程是作为拥有系统资源的基本单位，通常的进程都包含多个线程并为它们提供资源，但此时的进程就不再作为一个执行的实体。
多线程OS中的进程有以下属性：
1. 作为系统资源分配的单位；
2. 可包括多个线程；
3. 进程不是一个可执行的实体。

线程间的同步和通信

互斥锁(mutex)

互斥锁是一种比较简单的、用于实现进程间对资源互斥访问的机制。
由于操作互斥锁的时间和空间开销都比较低，因而比较适合用于高频度使用的关键共享数据和程序段。
互斥锁有**开锁(unlock)和关锁(lock)**状态。
相应地，可用两条命令（函数）对互斥锁进行操作。其中的关锁lock操作用于将mutex关上，开锁操作unlock则用于打开mutex。

条件变量

每一个条件变量通常都与一个互斥锁一起使用。即，在创建一个互斥锁时便联系着一个条件变量。
单纯的互斥锁用于短期锁定，主要是用来保证对临界区的互斥进入。
而条件变量则用于线程的长期等待，直至所等待的资源成为可用的。
线程首先对mutex执行关锁操作，若成功便进入临界区，然后查找用于描述资源状态的数据结构，以了解资源的情况。
只要发现所需资源R正处于忙碌状态，线程便转为等待状态，并对mutex执行开锁操作后，等待该资源被释放；
若资源处于空闲状态，表明线程可以使用该资源，于是将该资源设置为忙碌状态，再对mutex执行开锁操作。

信号量机制

私用信号量
公用信号量

内核支持线程和用户级线程

内核支持线程

用户级线程

线程控制

内核支持线程的实现

用户级线程的实现

运行时系统

所谓“运行时系统”，实质上是用于管理和控制线程的函数（过程）的集合，其中包括用于创建和撤销线程的函数、线程同步和通信的函数以及实现线程调度的函数等。
正因为有这些函数，才能使用户级线程与内核无关。运行时系统中的所有函数都驻留在用户空间，并作为用户级线程与内核之间的接口。

内核控制线程

这种线程又称为轻型线程LWP(Light Weight Process)。每一个进程都可拥有多个LWP，同用户级线程一样，每个LWP都有自己的数据结构（如TCB），其中包括线程标识符、优先级、状态，另外还有栈和局部存储区等。
它们也可以共享进程所拥有的资源。
LWP可通过系统调用来获得内核提供的服务。这样，当一个用户级线程运行时，只要将它连接到一个LWP上，此时它便具有了内核支持线程的所有属性。

利用轻型进程作为中间系统

第三章处理及调度与死锁

处理机调度的基本概念

高级、中级和低级调度

高级调度

在每次执行作业调度时，都须做出以下两个决定：
1. 接纳多少个作业
2. 接纳哪些作业

低级调度(Low Level Scheduling)

非抢占方式(Non-preemptive Mode)

在采用非抢占调度时，可能引起进程调度的因素可以归结为这样几个：
1. 正在执行的进程执行完毕，或因发生某事件而不能再继续执行；
2. 执行中的进程因提出I/O请求而暂停执行；
3. 在进程通信或同步过程中执行了某种原语操作，如P操作（wait操作）、Block原语、Wakeup原语等。
这种调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统环境。
但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。
显然，在要求比较严格的实时系统中，不宜采用这种调度方式。

抢占方式(Preemptive Mode)

抢占的原则有：
1. 优先权原则
2. 短作业（进程）优先原则
3. 时间片原则

中级调度(Intermediate-Level Scheduling)

中级调度又称中程调度(Medium-Term Scheduling)。
引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。
为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。

高、中、低级调度的区别

在操作系统中，高级调度、中级调度和低级调度是三种不同层次的进程调度方式，它们在功能、调度对象和频率上有所区别。

1. 高级调度（作业调度或长程调度）

功能：
- 主要负责将外存（如硬盘）上的作业调入内存，为它们创建进程。
- 决定哪些作业可以进入内存，从而控制进入系统的作业数量。
调度对象：
- 作业（Job）。
调度频率：
- 较低，通常在作业进入系统或结束时进行。
特点：
- 主要用于批处理系统，目的是提高系统的吞吐量和资源利用率。
- 选择作业的依据通常是作业的优先级、资源需求等。

2. 中级调度（内存调度或交换调度）

功能：
- 负责内存和外存之间的进程交换，将暂时不能运行的进程调到外存（挂起状态），以释放内存空间。
- 提高内存利用率和系统吞吐量。
调度对象：
- 进程（Process）。
调度频率：
- 中等，通常在内存资源紧张时进行。
特点：
- 引入中级调度是为了提高内存的利用率，使得在内存资源紧张的时候，可以把暂时不能运行的进程挂起，从而腾出一些内存空间。
- 处于挂起状态的进程，在具备运行条件且内存又稍有空闲时，再由中级调度来决定把外存上的具备运行条件的就绪进程重新调入内存，修改其状态为就绪态，挂在就绪队列上。

3. 低级调度（进程调度或短程调度）

功能：
- 负责从就绪队列中选择一个进程，将处理器（CPU）分配给它。
- 是操作系统中最基本的调度，决定哪个进程占用 CPU 运行。
调度对象：
- 进程（Process）或线程（Thread）。
调度频率：
- 最高，通常几十毫秒一次。
特点：
- 是操作系统核心，对系统性能影响最大。
- 选择进程的依据通常是进程的优先级、时间片轮转等。

总结

高级调度：关注作业的整体调度，决定哪些作业进入内存。
中级调度：关注内存的利用率，负责进程的内存交换。
低级调度：关注 CPU 的分配，决定哪个进程占用 CPU 运行。

这三种调度方式共同协作，实现了对系统资源的有效管理和调度。

选择调度方式和调度算法的若干准则

面向用户的准则

周转时间短

周转时间公式：
带权周转时间公式： $W=T/T_S$
平均带权周转时间公式：

响应时间快
截至时间的保证
优先权准则

面向系统的准则

系统吞吐量高
处理机利用率好
各类资源的平衡利用

调度算法

先来先服务(FCFS)和短作业（进程）优先调度算法(SJF)

先来先服务调度算法

FCFS和SJF性能比较

短作业（进程）优先调度算法

缺点：
1. 对长作业不利。
2. 完全未考虑作业的紧迫程度，不能保证紧迫性作业（进程）会被及时处理
3. 执行时间是用户估计的，不一定能真正做到短作业优先调度

高优先权优先调度算法

优先权调度算法的类型

非抢占式优先权算法

这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。

抢占式优先权调度算法

常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。

优先权的类型

静态优先权

确定优先权的依据：
1. 进程类型
2. 进程对资源的需求
3. 用户要求

动态优先权

例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。
- 若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程，将因其动态优先权变得最高而优先获得处理机，此即FCFS算法。
- 若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机。
当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机。

高响应比优先调度算法

优先权等于响应比 $R_P$
如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。
当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。
对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。

基于时间片的轮转调度算法

时间偏轮转法

多级反馈队列调度算法

应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。
例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。如图：
当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。
仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1~(i-1) 队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。
多级反馈队列调度算法的性能
1. 终端型作业用户
2. 短批处理作业用户
3. 长批处理作业用户

实时调度

实现实时调度的基本条件

提供必要的信息

就绪时间
开始截止时间和完成截止时间
处理时间
资源要求
优先级

系统处理能力强

假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件，系统才是可调度的。
解决办法：
1. 仍采用单处理机系统，但增强其处理能力，以显著地减少对每一个任务的处理时间；
2. 采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制条件改为：

采用抢占式调度机制

当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。
对于一些小的实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制，以简化调度程序和对任务调度时所花费的系统开销。但在设计这种调度机制时，应使所有的实时任务都比较小，并在执行完关键性程序和临界区后，能及时地将自己阻塞起来，以便释放出处理机，供调度程序去调度那种开始截止时间即将到达的任务。

具有快速切换机制

对外部中断的快速响应能力。
快速的任务分派能力。

实时调度算法的分类

非抢占式调度算法

非抢占式轮转调度算法
非抢占式优先调度算法

抢占式调度算法

基于时钟中断的抢占式优先权调度算法
立即抢占(Immediate Preemption)的优先权调度算法

常用的实时调度算法

最早截至时间优先算法(EDF, Eariest Deadline First)

最低松弛度优先算法(LLf, Least Laxity First)

例如，一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100 ms之前调度执行，该任务的 紧急程度(松弛程度) 为100 ms。
一个按松弛度排序的实时任务就绪队列，松弛度最低（即紧急程度最高）的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。
该算法主要用于可抢占调度方式中。
周期性实时任务题目（见第三章ppt-38，很复杂）

多处理机系统中的调度

多处理器系统的类型

紧密耦合多处理器系统(TCMPS, Tightly Coupted Multiprocessor System)

这通常是通过高速总线或高速交叉开关，来实现多个处理器之间的互连的。
它们共享主存储器系统和I/O设备，并要求将主存储器划分为若干个能独立访问的存储器模块，以便多个处理机能同时对主存进行访问。系统中的所有资源和进程，都由操作系统实施统一的控制和管理。

对称多处理器系统(SMPS, Symmetric MultiProcessor System)

在系统中所包含的各处理器单元，在功能和结构上都是相同的，当前的绝大多数MPS都属于SMP系统。例如，IBM公司的SR/6000 Model F50, 便是利用4片Power PC处理器构成的。

非对称多处理器系统(ASMP, Asymmetric Multiprocessing System)

在系统中有多种类型的处理单元，它们的功能和结构各不相同，其中只有一个主处理器，有多个从处理器。

进程分配方式

对称多处理器系统中的进程分配方式

在SMP系统中，所有的处理器都是相同的，因而可把所有的处理器作为一个处理器池(Processor pool)，由调度程序或基于处理器的请求，将任何一个进程分配给池中的任何一个处理器去处理。在进行进程分配时，可采用以下两种方式之一。
1. 静态分配方式(Static Assignment)
2. 动态分配方式(Dynamic Assignment)

非对称多处理器系统中的进程分配方式

对于非对称MPS，其OS大多采用主—从(Master-Slave)式OS，即OS的核心部分驻留在一台主机上(Master)，而从机(Slave)上只是用户程序，进程调度只由主机执行。
每当从机空闲时，便向主机发送一个索求进程的信号，然后，便等待主机为它分配进程。在主机中保持有一个就绪队列，只要就绪队列不空，主机便从其队首摘下一进程分配给请求的从机。
从机接收到分配的进程后便运行该进程，该进程结束后从机又向主机发出请求。

进程（线程）调度方式

自调度方式(Self-Scheduling)

自调度机制

在多处理器系统中，自调度方式是最简单的一种调度方式。
在系统中设置有一个公共的进程或线程就绪队列，所有的处理器在空闲时，都可自己到该队列中取得一进程(或线程)来运行。
优点：
自调度方式的主要优点表现为：首先，系统中的公共就绪队列可按照单处理机系统中所采用的各种方式加以组织；其调度算法也可沿用单处理机系统所用的算法，亦即，很容易将单处理机环境下的调度机制移植到多处理机系统中，故它仍然是当前多处理机系统中较常用的调度方式。其次，只要系统中有任务，或者说只要公共就绪队列不空，就不会出现处理机空闲的情况，也不会发生处理器忙闲不均的现象，因而有利于提高处理器的利用率。
缺点：
1. 瓶颈问题
2. 低效性
3. 线程切换频率

成组调度方式(Gang Scheduling)
(1) 面向所有应用程序平均分配处理器时间
(2) 面向所有线程平均分配处理器时间
专用处理器分配方式(Dedicated Processor Assignment)

产生死锁的原因和必要条件

产生死锁的原因

竞争资源
进程间推进顺序非法

竞争资源引起死锁

可剥夺和非剥夺性资源
竞争非剥夺性资源
竞争临时资源

I/O设备共享时的死锁情况

进程之间通信时的死锁情况

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

进程推进顺序合法（不会发生死锁）
进程推进顺序非法（循环等待）

产生死锁的必要条件

互斥条件
请求和保持条件
不剥夺条件
环路等待条件

处理死锁的基本方法

预防死锁
避免死锁
检测死锁
解除死锁

预防死锁的方法

预防死锁

摒弃“请求和保持”条件
摒弃“不剥夺”条件
摒弃“环路等待”条件

系统安全状态

核心思想：
- 动态资源分配与安全性检查：
  - 允许进程动态申请资源。
  - 在分配资源前，系统进行安全性计算。
  - 只有当分配不会导致系统进入不安全状态时，才分配资源。
  - 否则，进程等待。
安全状态与不安全状态：
- 安全状态：
  - 系统能找到一个进程执行顺序（安全序列）。
  - 按照此顺序，每个进程都能获得所需资源并完成。
- 不安全状态：
  - 系统无法找到任何安全序列。
  - 可能导致死锁。

银行家算法

看王道
有点像某个数字游戏
如果系统处于安全状态，就一定不会发生死锁；如果系统进入不安全状态，就可能发生死锁。
处于不安全状态未必会发生死锁，但发生死锁时一定是在不安全状态。
银行家算法的核心思想：因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。
用在操作系统上，资源用矢量代替。
代码表示
- n*m矩阵-Max-各进程最大需求
- n*m矩阵-Allocation-分配矩阵（已为每个进程分配了多少资源）
- n*m矩阵-Need=Max-Allocation-各进程最多还需多少各类资源
- len=m的一维数组-Available-表示当前系统中还有多少可用资源
- len=m的一维数组-Request_i-表示某进程向系统申请的各种资源
- 分配资源：
  - 需改变Available、Allocation、Need数组，然后执行安全性检查（用以下安全性算法）。
安全性算法：
- Work（初始化为Available）、Need、Allocation、Work+Allocation、finish。
- 循环查找：
  1. 从所有Finish[i]==false的进程中，查找一个进程i，满足Need[i]<=Work。
  2. 如果找到这样的进程i，执行以下操作：
  - Work = Work + Allocation[i] （模拟进程i完成，释放其占有的资源）。
  - Finish[i]=true（标记进程i已完成）
  1. 重复上述步骤，直到所有进程都完成（即所有Finish[i]都为true），或者找不到满足条件的进程。
- 安全性判断：
  - 如果所有Finish[i]都为true，则系统处于安全状态。
  - 否则，系统处于不安全状态，可能发生死锁。

死锁的检测与解除

看王道

死锁的检测

最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（相当于能找到一个安全序列）。
如果最终不能消除所有边，那么此时就是发生了死锁。
最终还连着边的那些进程就是处于死锁状态的进程。

死锁的解除

方法

资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些资源。这种方法的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

如何决定“对谁动手”

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

第四章存储器管理

程序的装入和链接

连续分配方式

单一连续分配

最简单的一种存储管理方式
只能用于单用户、单任务的操作系统中
把内存区分为两部分：
- 系统区仅提供给OS使用，通常是放在内存的低址部分；
- 用户区是指系统区以外的全部内存空间，提供给用户使用。

固定分区分配

划分分区的方法

分区大小相等，即使所有的内存分区大小相等
分区大小不等

动态分区分配

数据结构

空闲分区表
空闲分区链

分区分配算法

首次适应算法FF
循环首次适应算法，该算法是由首次适应算法演变而成的
最佳适应算法

可重定位分区分配

进行紧凑形成连续空闲区

基本分页存储管理方式

基本分段存储管理方式

虚拟存储器的基本概念

所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。

请求分页存储管理方式

页面置换算法

最佳置换算法（OPT）

每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。
缺页中断之后未必发生页面置换。若还有可用的空闲内存块，就不用进行页面置换。
缺页率=缺页中断的次数/总共访问的页面次数*100%
因此操作系统实际无法提前预判页面访问序列，因此，最佳置换算法是理想的置换算法。在实际应用中是无法实现的。

先进先出置换算法（FIFO）

Belady异常——当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
**只有FIFO算法会产生Belady异常**。
另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。
因此，算法性能差。

最近最久未使用置换算法（LRU，Least Recently Used）

每次淘汰的页面是最近最久未使用的页面。
该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大。

时钟置换算法（CLOCK / NRU）

最佳置换算法性能最好，但无法实现；先进先出置换算法实现简单，但算法性能差；最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。
时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法（NRU，Not Recently Used）

改进型的时钟置换算法

用（访问位，修改位）的形式表示各页面状态。
改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描，而简单的时钟算法在淘汰一个页面的时候最多会进行两轮扫描。

请求分段存储管理方式

第五章设备管理

I/O系统

I/O设备

I/O设备的类型

按传输速率分类

低速设备。几字节~几百字节/s，键盘、鼠标器、语音的I/O设备。
中速设备。数千字节~数万字节/s，行式打印机、激光打印机。
高速设备。数百千字节~数十兆字节，磁带机、磁盘机、光盘机。

按信息交换的单位分类

块设备（Block Device）。

用于存储信息。
由于信息的存取总是以数据块为单位，故而得名。
属于有结构设备。
典型的块设备是磁盘，每个盘块的大小为512B~4KB。
磁盘设备的基本特征是其传输速率较高，通常每秒钟为几兆位；另一特征是可寻址，即对它可随机地读/写任一块；此外磁盘设备的I/O常采用DMA方式。
ppt-5-p3
字符设备（character Device）

用于数据的输入和输出。
其基本单位是字符，故称为字符设备。

按设备的共享属性分类

独占设备
共享设备
虚拟设备

设备与控制器之间的接口

设备控制器

I/O通道

通道类型

字节多路通道（Byte Multiplexor Channel）

适用于低速设备（键盘、打印机），逐字节传输（Byte），可以同时管理多个低速设备，适用于低速外设的数据输入/输出。

数组选择通道（Block selector Channel）

适用于高速设备（磁盘、磁带），按块传输（Block），一次只能管理一个设备，适用于大数据量的存储读写。

数组多路通道（Block Multiplexor Channel）

数组多路通道是将数组选择通道传输速率高和字节多路通道能使各子通道(设备)分时并行操作的优点相结合而形成的一种新通道。
数组多路通道是将数组选择通道传输速率高和字节多路通道能使各子通道(设备)分时并行操作的优点相结合而形成的一种新通道。
被广泛地用于连接多台高、中速的外围设备，其数据传送是按数组方式进行的。

第一章 操作系统引论

操作系统的目标和作用

OS的作用

系统调用：

操作系统的发展过程

无操作系统的计算机系统

单道批处理系统

多道批处理系统

分时系统

实时系统

操作系统的基本特性

并发 (Concurrency)

共享 (Sharing)

虚拟 (Virtualization)

异步 (Asynchrony)

操作系统的主要功能

处理机管理功能

进程控制

进程同步

进程通信

调度

存储器管理功能

内存分配

内存保护

地址映射

内存扩充

设备管理功能

缓冲管理

设备分配

设备处理

虚拟设备

文件管理功能

文件存储空间的管理

目录管理

文件的读/写管理和保护

用户接口

操作系统的结构设计

软件工程的基本概念

软件的含义

软件工程的含义

传统的操作系统结构

无结构操作系统

模块化OS结构

分层式OS结构

微内核OS结构

客户/服务器模式(Client-Server Model)

面向对象的程序设计技术(Object-Orientated Programming)

微内核技术

第二章 进程管理

进程的基本概念

程序顺序执行时的特征

前趋图

程序并发执行时的特征

进程的特征与状态

进程的特征

较典型的进程的定义有：

进程的三种基本状态

挂起状态

进程状态的转换

进程状态的转换

进程控制块（PCB，Process Control Block）

进程控制

进程的创建

进程图

引起进程创建的事件

进程的创建

进程的终止

引起进程终止(Termination of Process)的事件

进程的终止过程

进程的阻塞与唤醒

引起进程阻塞和唤醒的事件

进程阻塞过程

进程唤醒过程

进程的挂起与激活

进程的挂起过程

进程的激活过程

进程同步

进程同步的基本概念

两种形式的制约关系

临界资源

第一章操作系统引论

第二章进程管理

第三章处理及调度与死锁