计算机操作系统

由于本学期学习了计算机操作系统，所以打算边学习边整理，一方面帮助自己梳理知识结构，另一方面可以帮助大家理解。

注意：该总结用的是汤小丹第四版！

关于知识脑图，我是边学边做的，推荐大家也自己做脑图，而不是直接拿走照搬，因为只有自己梳理的东西才是自己的。

做知识脑图的好处是可以对知识整体结构有好的把握，不会让自己迷失于细节；还可以复习时快速找到知识点等。

废话不多说，赶紧开始吧。

第二章进程的描述与控制（上）

一、前趋图和程序执行

1、前趋图

前趋图是一个有向无循环图，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序或前趋关系“→”。

没有前趋的结点称为初始结点；没有后继的结点称为终止结点。

每个结点还具有一个权重，用于表示该结点所含有的程序量或结点的执行时间。
具有九个节点的前前趋图
对于上图所示的前趋图，存在下述前趋关系：
P1→P2, P1→P3, P1→P4, P2→P5, P3→P5, P4→P6, P4→P7, P5→P8, P6→P8, P7→P9, P8→P9
具有循环的图
前趋图中必须不存在循环，但在上图中却有着下述的前趋关系：S2→S3, S3→S2 (这种前趋关系是不可能满足的)

2、程序顺序执行

程序的顺序执行

仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入( I )用户的程序和数据，然后进行计算( C )，最后才能打印( P )计算结果。

例b：
S1: $a = x + y$ ;
S2: $b = a - 5$ ;
S3: $c = b + 1$ ;

程序顺序执行时的特征
(1) 顺序性：每一操作必须在上一个操作结束之后开始。
(2) 封闭性：程序运行时独占全机资源，资源的状态(除初
始状态外)只有本程序才能改变它。执行结果不受外界因
素影响。
(3) 可再现性：程序重复执行，结果相同。

3、程序并发执行

程序的并发执行
批作业处理时描述为：

存在下述前趋关系： $I_i→C_i，I_i→I_{i+1}, C_i→P_i, C_i→C_{i+1}，P_i→P_{i+1}$
$I_{i+1}$ 和 $C_i$ 及 $P_{i-1}$ 是重迭的，即在 $P_{i-1}$ 和 $C_i$ 以及 $I_{i+1}$ 之间，可以并发执行。
对于具有下述四条语句的程序段：
S1: $a = x + 2$
S2: $b = y + 4$
S3: $c = a + b$
S4: $d = c + b$
程序并发执行时的特征

间断性
程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约的关系，相互制约将导致并发程序具有“执行—暂停—执行”这种间断性的活动规律。
失去封闭性
程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。
不可再现性
程序在并发执行时，由于失去了封闭性，也将导致其再失去可再现性。

二、进程的描述

1、进程的定义和特征

进程的定义
传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。
进程控制块(Process Control Block,PCB) 操作系统用于管理进程的专门的数据结构。
进程实体（进程映像）就是由代码、数据、进程控制块PCB这三部分构成。
进程的特征
动态性：由创建而产生，由调度而执行，由撤销而消亡。
并发性：多个进程实体同存于内存之中，且能在一段时间内同时执行。
独立性：独立执行、独立获得资源、独立接受调度的基本单位。
异步性：按各自独立的、不可预知的速度向前推进。

2、进程的基本状态及转换

进程的三种基本状态定义
（1) 就绪(Ready)状态
（2) 执行(Running)状态
（3) 阻塞(Block)状态
三种基本状态的转换
创建状态和终止状态
1）创建状态
创建工作：分配PCB，并填写必要信息；其次将其转入就绪队列。
2）终止状态
终止工作：OS做善后处理；PCB清空并归还给系统。

3、挂起操作和进程状态的转换

挂起操作的引入
(1) 终端用户的请求。
(2) 父进程请求。
(3) 负荷调节的需要。
(4) 操作系统的需要。
引入挂起原语操作后，基本进程状态的改变：
(1)活动就绪→静止就绪。
(2)活动阻塞→静止阻塞。
(3)静止就绪→活动就绪。
(4)静止阻塞→活动阻塞。

4、进程管理中的数据结构

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

(2)链接方式

(3)索引方式

三、进程控制

进程控制是用来管理从进程诞生、运行、到结束过程中的一切事情，故而要由操作系统内核中的原语来实现。

原语(Primitive)是由若干条指令组成的，用于完成一定功能的一个过程。它与一般过程的区别在于：它们是“原子操作(Action Operation)”。所谓原子操作，是指一个操作中的所有动作要么全做，要么全不做。换言之，它是一个不可分割的基本单位，因此，在执行过程中不允许被中断。原子操作在管态（核态，相对用户态）下执行，常驻内存。

内核的实现是通过原语实现的，而原语又是由原子操作构成的。

1、操作系统内核

操作系统内核：操作系统中与硬件紧密相关的模块（如中断处理程序、设备驱动程序等）以及运行频率较高（如时钟管理、进程调度等）的模块，它们常驻内存。

设置操作系统内核的作用：
(1)便于对软件进行保护，防止被其它程序破坏；
(2)提高操作系统的运行效率。

处理机执行状态：
(1)系统态（管态或内核态）；
(2)用户态（目态）。

操作系统内核两大功能：

支撑功能
(1)中断处理：内核对中断进行“有限处理”后，转入相关进程接续后续处理。
(2)时钟管理：定时产生时钟信号。
(3)原语操作：原语是完成一定功能的过程，具有不可分割性。
资源管理功能
(1)进程管理：运行频率较高的模块（如进程调度、创建与撤销等），常被调用模块如同步原语等均放入内核。
(2)存储器管理：运行频率较高也要放入内核。
(3)设备管理：与硬件相关也要放入内核。

2、进程的创建

进程的层次结构
进程的层次结构 体现为进程创建过程中生成的进程家族树，如unix下的进程树。
windows中不存在进程层次结构的概念，进程之间（通过句柄）只有控制与被控制的关系。
进程图(Process Graph)
父进程子进程祖先子孙
引起创建进程的事件
(1) 用户登录。
(2) 作业调度。
(3) 提供服务。
(4) 应用请求。
进程的创建(Creation of Progress)
(1)申请空白PCB。
(2)为新进程分配资源。
(3)初始化进程控制块。
(4)将新进程插入就绪队列，如果进程就绪队列能够接纳新进程,便将新进程插入就绪队列。

3、进程的终止

引起进程终止(Termination of Process)的事件
1)正常结束在任何计算机系统中，都应有一个用于表示进程已经运行完成的指示。例如，在批处理系统中，通常在程序的最后安排一条Holt指令或终止的系统调用。当程序运行到Holt指令时，将产生一个中断，去通知OS本进程已经完成。在分时系统中，用户可利用Logs off去表示进程运行完毕，此时同样可产生一个中断，去通知OS进程已运行完毕。
2)异常结束
在进程运行期间，由于出现某些错误和故障而迫使进程终止。
① 越界错误。 ② 保护错。访问不当; ③ 非法指令。把数据当成了指令； ④ 特权指令错。⑤ 运行超时。 ⑥ 等待超时。 ⑦ 算术运算错。例如被0除； ⑧ I/O故障。
3)外界干预
外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。这些干预有：
① 操作员或操作系统干预。例如，发生了死锁;
② 父进程请求。
③ 父进程终止。当父进程终止时，OS也将他的所有子孙进程终止。
进程的终止过程
(1) 根据被终止进程的标识符，从PCB检索出该进程的PCB；
(2) 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。
(3) 终止该进程的所有子孙进程，以防他们成为不可控的进程。
(4) 将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。
(5) 将被终止进程(它的PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息。

4、进程的阻塞与唤醒

引起进程阻塞和唤醒的事件
1)向系统请求共享资源失败
2)等待某种操作的完成
3)新数据尚未到达
4)等待新任务的到达
进程阻塞过程
正在执行的进程，当发现阻塞事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。
进入block过程后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换。
进程唤醒过程
当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤醒原语wakeup( )，将等待该事件的进程唤醒。
唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。

5、进程的挂起与激活

进程的挂起
当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起，系统将利用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起。
挂起原语的执行过程：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后，若被挂起的进程正在执行，则转向调度程序重新调度。
进程的激活过程
当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语active( )将指定进程激活。
激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。

四、进程同步

1、进程同步的基本概念

两种形式的制约关系
(1) 间接相互制约关系。 —源于进程共享某种系统资源
(2) 直接相互制约关系。 —源于进程合作加工资源
临界资源(Critical Resouce) —采取互斥方式实现共享
生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。它描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。
临界区(critical section)
可把一个访问临界资源的循环进程描述如下：
同步机制应遵循的规则
(1) 空闲让进–临界资源空闲状态，应允许请求进入临界区
(2) 忙则等待–临界资源正被访问，进入临界区进程必须等待
(3) 有限等待–有限时间内能进入自己的临界区
(4) 让权等待–不能进入临界区时，应立即释放处理机

2、硬件同步机制

为防止多个进程同时测试到锁为打开的状态，测试与关锁操作必须是连续的，不允许分开进行。

关中断
锁测试之前关闭中断，上锁后再打开中断。这样进程在临界区内，不响应中断。
关中断的缺点：
⑴ 滥用关中断后果严重（不能及时响应）；
⑵ 关中断时间长，影响系统效率；
⑶ 该方法不适应多CPU系统。
利用test-and-set指令实现互斥（测试并建立）
利用swap指令实现互斥
对换指令描述如下：

lock=FALSE，key=TRUE；锁开，资源空闲
lock=TRUE，key=TRUE；锁关，资源忙碌，重复测试，忙等

3、信号量机制

整型信号量
最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作(Atomic Operation) wait(S) 和 signal(S) 来访问。这两个操作一直被分别称为P、V操作。

wait(S)和signal(S)是两个原子操作，因此，它们在执行时是不可中断的。
– 当一个进程在修改某信号量时，没有其他进程可同时对该信号量进行修改。此外，在wait操作中，对S值的测试和做S=S-1操作时都不可中断。
在wait操作中，只要是信号量S≤0，就会不断地测试。
– 该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。

记录型信号量
• 记录型信号量机制采取了“让权等待”的策略，又会出现多个进程等待访问同一临界资源的情况。
• 除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表指针，用于链接上述的所有等待进程。

• 整数值 s.count为了计该信号代表资源的数；
• s.queue存储的是阻塞在该信号量的各个进程的标识，构成一个进程等待队列；
信号量只能通过初始化和两个标准的原语来访问——作为 OS 核心代码执行，不受进程调度的打断。
信号量在始化时被指定一个非负整数值，表示空闲资源总数（又称为“资源信号量”），在进程执行过程中，信号量的值（即其计数值）可能发生变化：
• 若为非负值，表示当前的空闲资源数；
• 若为负值，其绝对值表示当前等待临界区的进程数。
利用信号量实现互斥的过程是：

P原语–P(s)或wait(s)：
申请使用临界资源时调用P原语，其实现原理为：

V原语—V(s) 或 signal(s)
V原语通常唤醒进程等待队列中的第一个进程，其实现原理为：

利用信号量实现互斥，需要注意的是：
• 必须成对使用P和V原语：遗漏P原语则不能保证互斥访问；遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；
• P、V原语不能出现次序错误、重复或遗漏。
信号量P、V操作的实现 :
P操作实现P(s)：

1.BEGIN 
2.lock(lockbit);//封锁中断; 
3.--s.count; //表示申请一个资源; 
4.if (s.count <0) //表示没有空闲资源; 
{ 调用进程进入等待队列s.queue; 
阻塞调用进程; } 
5.unlock(lockbit);//开放中断; 
6.END;

V操作实现V(s)：

1.BEGIN 
2. ock(lockbit); //封锁中断; 
3.++s.count; 
4.if (s.count <= 0) 
{ 从等待队列s.queue中取出一个进程P; 
进程P进入就绪队列; } 
5.unlock(lockbit);//开放中断; 
6.END;

以下为信号量和P、V原语实现互斥与同步的不同：

3. AND型信号量
若进程同时竞争2个临界资源d、e，描述如下：

若进程A和B按下述次序交替执行wait操作：
process A: wait(Dmutex); 于是Dmutex=0
process B: wait(Emutex); 于是Emutex=0
process A: wait(Emutex); 于是Emutex=-1 A阻塞
process B: wait(Dmutex); 于是Dmutex=-1 B阻塞

AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait(Simultaneous wait)定义如下：

4. 信号量集
• 在记录型信号量机制中，wait(S)或signal(S)操作仅能对信号量施以加1或减1操作，意味着每次只能获得或释放一个单位的临界资源。而当一次需要N个某类临界资源时，便要进行N次wait(S)操作，显然这是低效的。
• 在有些情况下，要求当资源数量低于某一下限值时，便不予以分配。因而，在每次分配之前，需要测试该资源的数量，看其是否大于其下限值。

基于上述两点，可以对AND信号量机制加以扩充，形成一般化的“信号量集”机制。

Swait操作中 $S_i$ 为信号量， $t_i$ 为下限值（少于不给分配），而 $d_i$ 为需求值。

一般“信号量集”的几种特殊情况：
(1) Swait(S, d, d)。此时在信号量集中只有一个信号量 S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配。
(2) Swait(S, 1, 1)。此时的信号量集已蜕化为一般的记录型信号量(S＞1时)或互斥信号量(S=1时)。
(3) Swait(S, 1, 0)。这是一种很特殊且很有用的信号量操作。当S≥1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。

4、信号量的应用

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

5、管程机制

管程的定义
(1)管程的引入
访问临界资源的进程自行使用P、V操作会出现误操作，比如：
P、V操作没有成对出现;
只有P，而没有V，或者只有V，而没有P；
P、V操作颠倒；
两个P操作颠倒等。
对此，有人提出能否将对临界资源的控制与管理集中起来，用户只要提出使用要求，其它诸如互斥、同步等问题则不需要用户自己解决，而由系统统一解决。
(2)管程的定义
系统中的各种硬件资源和软件资源均可用数据结构抽象地描述其资源特性，即用少量信息和对该资源所执行的操作来表征该资源，而忽略了它们的内部结构和实现细节。
20世纪70年代，Hoare 和B. Hansen提出了一种同步原语，称为管程。当进程共享某临界资源时，只需调用相应的管程，而对资源的使用及其出现的诸如同步、互斥等问题，则完全由管程去解决。
B.Hansen 给管程下的定义是：一个管程指定义了一个数据结构和能为并发程序在该数据结构上执行的一组操作，这组操作能同步进程和改变管程中的数据。
(3)管程的组成
1)管程标识符；
2)局部于管程内部的共享数据结构说明；
3)对该数据结构进行操作的一组过程；
4)对局部于管程的共享数据设置初始值的语句。

这里用数据结构对资源进行描述，一组过程体现对资源的使用方式。进程在管程外排队等候使用资源。

(4)管程的语法

(5)管程的特性
管程是一种程序设计语言结构成分，它和信号量有同等的表达能力，从语言的角度看，管程有以下特性：
1)模块化：基本程序单位，可单独编译；
2)抽象数据类型：有数据以及对数据的操作；
3)信息掩蔽：管程内的数据结构以及过程实现外部不可见。
(6)管程与进程的差别
1)进程私有数据结构（PCB），管程公共的；
2)进程是程序执行，管程是用于同步的机制；
3)进程目的是并发执行，管程解决公共资源互斥使用；
4)进程调用管程中的过程，进程主动，管程被动；
5)进程可以并发，管程不能与调用者并发；
6)进程具有动态性，有生命期，管程属于OS的资源管理模块，供进程调用的。
条件变量
管程中对每个条件变量，都须予以说明，其形式为： condition x, y；每个条件变量保存了一个链表，记录因该条件变量而阻塞的进程。提供两个操作，即x.wait和x.signal。
例如，由于共享数据被占用而使调用进程等待，该条件变量的形式为：condition nonbusy;此时， wait原语应改为 nonbusy.wait，相应地，signal应改为nonbusy.signal。
x.signal操作的作用，是重新启动一个被阻塞的进程，但如果没有被阻塞的进程，则x.signal操作不产生任何后果。这与信号量机制中的signal操作不同。因为，后者总是要执行 s:=s+1操作，因而总会改变信号量的状态。
如果有进程Q处于阻塞状态，当进程P执行了x.signal操作后，怎样决定由哪个进行执行，哪个等待，可采用下述两种方式之一进行处理：
(1) P等待，直至Q离开管程或等待另一条件。
(2) Q等待，直至P离开管程或等待另一条件。
采用哪种处理方式，当然是各执一词。但是Hansan却采用了第一种处理方式。Hoare采用了二者折中，设置让P执行的x.signal操作是管程中最后的操作，因此P执行 x.signal操作后就退出管程，然后Q马上被恢复执行。

原文链接：https://blog.csdn.net/qq_45556599/article/details/108816996

计算机操作系统第二章：进程的描述与控制（上）（知识梳理+脑图）

文章目录

计算机操作系统