岛屿尽

dyingjin

计算机操作系统(1-3)

发表于 更新于 分类于

操作系统引论

目标和作用

目标：方便性、有效性、可扩展性、开放性
作用

  1. 作为用户与计算机硬件系统之间的接口
  2. 操作系统作为计算机系统资源的管理者
  3. 实现了对计算机资源的抽象

发展过程

人工操作方式、脱机输入输出方式
单批道处理系统
多批道处理系统（资源利用率高，系统吞吐量大，平均周转时间长，无交互能力）
分时系统（多路性、独立性、及时性、交互性）
实时系统（多路性、独立性、及时性、交互性、可靠性）
微机操作系统（单用户多用户）

基本特征

  • 并发 - 并发性是指两个或多个事件在同一时间间隔内发生，而并行性是指两个或多个事件在同一时刻发生。
  • 共享 - 资源共享是指系统中的资源可供内存中多个并发执行的进程共同使用。一段时间内只允许一个进程访问的资源称为临界资源一个进程访问结束并释放系统资源后才允许另一进程对该资源访问的方式称为互斥访问
  • 虚拟 - 通过空分复用或时分复用技术将一条物理信道变为若干条逻辑信道的技术
  • 异步 - 进程的执行本身具有异步性（不可预知完成时间与顺序）所以要设计同步机制

主要功能

处理机管理功能

  • 进程控制
  • 进程同步
  • 进程通信
  • 调度

内存管理功能

  • 内存分配
  • 内存保护
  • 地址映射
  • 内存扩充

(I/O)设备管理功能

  • 缓冲管理
  • 设备分配
  • 设备处理

文件管理功能

  • 文件存储空间管理
  • 目录管理
  • 文件读写管理与保护

操作系统与用户之间的接口

  • 用户接口（联机用户接口、脱机用户接口、程序接口）
  • 程序接口

结构设计

无结构

程序紧凑，高效利用内存
但是随着系统的不断扩大，所设计出的操作系统就会变得既庞大又杂乱。
一方面会使编制的程序错误很多给调试工作带来困难
另一方面也使程序难以阅读和理解，增加了维护负担

模块化结构

模块化OS由程序设计的模块化设计思想演变而来
衡量模块化设计的两个标准：内聚性、耦合性
优点：

  1. 提高OS设计的正确性、可理解性和可维护性。
  2. 增强OS的可适应性。
  3. 加速OS开发过程。
    问题：
  4. 最初模块接口规定难以满足实际需求
  5. 无序设计

分层式结构

将模块接口法中对模块的设计顺序由无序变为有序，自底向上分层设计
优点：

  1. 易保证系统的正确性
  2. 易扩充和易维护性
    缺点：
  3. 系统效率降低：单向依赖的层次使得必须建立层次之间的通信机制增加通信开销

习题

  1. 设计现代OS的主要目标是什么？
    方便性、有效性、可扩展性、开放性

  2. 试说明推动分时系统形成和发展的主要动力是什么。
    满足人机交互需求，实现共享主机

  3. 为什么要引入实时操作系统？
    更好的满足实时控制实时信息处理领域对时间控制的需求

  4. 试从交互性、及时性以及可靠性方面将分时系统与实时系统进行比较。
    交互性：实时系统的交互性不像分时系统为终端用户提供数据和资源共享服务，而限于特定专用服务程序
    及时性：分时系统的响应时间间隔通常为人们所能接受的1~3秒，实时系统由截至时间所确定通常为秒级到毫秒级
    可靠性：实时系统相比分时系统要求更高的可靠性，所以采取多级容错措施保障系统的安全性

  5. OS有几大特征？最基本的特征是什么？
    并发性、共享性、虚拟性、异步性；并发性最基本

  6. 处理机管理有哪些主要功能？其主要任务是什么？
    进程控制、进程同步、进程通信、调度
    创建进程结束进程控制正在运行的进程、使多个进程有序同步进行、交换进程任务的信息、选择作业分配资源运行的作业调度和选择进程分配处理器设置现场执行的进程调度

  7. 存储器有哪些主要功能？其主要任务是什么？
    内存分配、内存保护、地址映射、内存扩充
    为程序分配内存空间、确保程序运行空间不干扰、将逻辑地址映射为物理地址、实现调用置换等功能

  8. 设备管理有哪些主要功能？其主要任务是什么？
    缓冲管理、设备分配、设备处理
    完成用户IO请求分配所需IO设备执行IO操作、提高CPU和IO设备的利用率提高IO速度方便用户使用

  9. 文件管理有哪些主要功能？其主要任务是什么？
    文件存储空间管理、目录管理、文件读写管理与保护
    分配外存空间提高外存利用率、为文件建立目录加以有效组织、根据用户请求读写外存数据、防止文件被非法窃取和受到破坏保障文件安全性

进程的描述与控制

前趋图和程序执行

前趋图（Precedence Graph）是一个有向无循环图，用于描述进程之间执行的前后关系。

程序的顺序执行

  • 顺序性
  • 封闭性
  • 可再现性

程序的并发执行

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

进程的描述

而由程序段、相关的数据段和PCB三部分便构成了进程实体。

典型定义

  1. 进程是程序的一次执行。
  2. 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
  3. 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位

特征

  • 动态性
  • 并发性
  • 独立性
  • 异步性

状态

IMG_20220304_151207_edit_772433114767030

PCB数据结构

  1. 进程标识符 - 用于惟一地标识一个进程。分为内部标识符和外部标识符
  2. 处理机状态 - 组成：①通用寄存器②指令计数器③程序状态字PSW④用户栈指针
  3. 进程调度信息 - 包括：①进程状态②进程优先级③进程调度所需的其它信息④事件，阻塞原因
  4. 进程控制信息 - ①程序和数据的地址 ②进程同步和通信机制 ③资源清单 ④链接指针
pid
进程状态
现场
优先级
阻塞原因
程序地址
同步机制
资源清单
链接指针

PCB的组织方式

  1. 线性方式 将系统中的所有PCB组织在一张线性表中，将该表的首地址存放在一个专用区域中。
  2. 链接方式 把具有同一状态的PCB，用其中的链接字链接成一个队列，排成就绪队列，若干个阻塞队列以及空白队列。
  3. 索引方式 系统根据所有进程的状态建立几张索引表。

进程控制

进程控制是用于创建一个新进程，终止一个已完成的进程，或去终止一个因出现某事件而使其无法运行下去的进程，还负责进程运行中的状态转换。

操作系统内核

OS内核—-常驻内存。
包含与硬件紧密相关的模块（中断处理） 常用设备驱动、运行频率高的模块（时钟管理、进程调度）
目的：1、保护；2、提供OS效率

  1. 支撑功能 - 中断处理 时钟管理 原语操作
  2. 资源管理功能 - 进程管理 存储器管理 设备管理

进程的创建

进程的层次结构

即父进程、子进程（可以继承父进程所拥有的资源）

引起创建进程的事件

  1. 用户登录
  2. 作业调度
  3. 提供服务
  4. 应用请求

进程创建

调用进程创建原语Creat（ ）按下述步骤创建一个新进程：

  1. 申请空白PCB。
  2. 为新进程分配资源。
  3. 初始化进程控制块。包括：
    ①初始化标识信息。
    ②初始化处理机状态信息。
    ③初始化处理机控制信息。
  4. 将新进程插入就绪队列。

进程的终止

引起进程终止的事件

  1. 正常结束: 批处理中用Holt指令，分时中用Logs off指令。
  2. 异常结束：
    ①越界错误。存储区。
    ②保护错。写一个只读文件。
    ③非法指令。执行一条不存在的指令。
    ④特权指令错。用户访问只允许OS执行的指令。
    ⑤运行超时。
    ⑥等待超时。
    ⑦算术运算错。被0除。
    ⑧I/O故障。
  3. 外界干预：外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。
    ① 操作员或操作系统干预。
    ② 父进程请求终止该进程。
    ③ 当父进程终止时，OS也将他的所有子孙进程终止。

进程的终止过程

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

进程的阻塞与唤醒、挂起与激活

引起进程阻塞的事件

  1. 请求系统服务：提出I/O服务时，并不立即满足该进程的要求时，转变为阻塞状态来等待
  2. 启动某种操作：当进程启动某种操作后，在该操作完成之后才能继续执行。
  3. 新数据尚未到达：对于相互合作的进程而言。
  4. 无新工作可做。如发送进程。

进程阻塞过程

正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block( )把自己阻塞。

  1. 把进程控制块中的现行状态由“执行”改为“阻塞”，并将PCB插入阻塞队列。
  2. 转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换。

进程唤醒过程

当被阻塞进程所期待的事件出现时，则由有关进程（比如，用完并释放了该I/O设备的进程）调用唤醒原语wakeup( )，将等待该事件的进程唤醒。

  1. 首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪
  2. 然后再将该PCB插入到就绪队列中。

进程的挂起

当出现了引起进程挂起的事件时，系统将利用挂起原语suspend( )将指定进程进程挂起。

  1. 首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；
  2. 对于活动阻塞状态的进程，则将之改为静止阻塞状态。

进程的激活

当发生激活进程的事件时，则可将在外存上处于静止就绪状态的进程换入内存。 系统利用激活原语active( )将指定进程激活:

  1. 激活原语先将进程从外存调入内存，检查该进程的现行状态;
  2. 若是静止就绪，便将之改为活动就绪；若为静止阻塞，便将之改为活动阻塞。

进程同步

为什么：
由于进程的异步性，也会给系统造成混乱，在OS中引入进程同步。
任务：
使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

进程同步的基本概念

  • 两种形式的制约关系：1）间接相互制约关系。由于资源共享 2）直接相互制约关系。主要由于进程间的合作。
  • 临界资源 一次仅允许一个进程访问的资源为临界资源 。
  • 临界区 把在每个进程中访问临界资源的那段代码称为临界区。
  • 同步机制规则 ：1)空闲让进 2)忙则等待 3)有限等待 4)让权等待

硬件同步机制

利用计算机硬件指令解决临界区问题
对临界区管理将标识看做一个锁，“锁开”进入，“锁关”等待。 初始打开，每个进入临界区的进程必须对锁进行测试。 测试和关锁操作必须连续（原子操作）
方法：

  • 关中断
  • 利用Test-and-Set指令实现互斥
  • 利用Swap指令实现进程互斥

优点：

  • 适用于任意数目的进程，在单处理器或多处理器上
  • 简单，容易验证其正确性
  • 可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量

缺点：

  • 等待要耗费CPU时间，不能实现“让权等待”
  • 可能“饥饿”：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上

信号量机制

信号量（Semaphores）机制:是一种卓有成效的进程同步工具。

整形信号量

  1. 必须置一次且只能置一次初值，并且初值不能为负数。
  2. 只能执行P、V操作。
  3. 必须成对使用P、V操作：P操作遗漏则不能保证互斥访问，V操作遗漏则不能在使用临界资源之后将其释放；P，V次序不能错误、重复或遗漏。
    整形信号量机制的问题：忙等。
    wait操作中信号量S<=0时，会不停的测试
    未遵循让权等待的原则

记录型信号量

只能用于共享一个临界资源

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct{
	int value;
	struct process_control_block *list;
}semaphore;

wait(semaphore *S){
	S->value--;
	if(S->value<0)block(S->list);
}
signal(semaphore *S){
	S->value++;
	if(S->value<=0)wakeup(S->list);
}

信号量的初值：0，1，n三种情况
1：表示临界资源；
0：表示进程间的同步（前驱）关系
n：表示若干个资源

AND型信号量

AND同步机制的基本思想：将进程在整个运行过程中需要的所有资源，一次性全都地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。
原子操作：要么全部分配到进程，要么一个也不分配。
在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Swait（S1，S2，···，Sn ） {
     while（true）{
         if（ S1≥1 and S2≥1 and…and Sn≥1 ）{
            for (i = 1 ; i<= n; i++){
                     Si =  Si – 1;
             }
             break;
        }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//将进程置于与在 Si<1 的条件下找到的**第一个** Si 关联的等待队列中，并将此过程的程序计数设置为 Swait 操作的开始
       }
}

Ssignal（S1，S2，···，Sn）{
    for(  i = 1; i<= n; i++ ){
         Si = Si+1;
         Remove  all  the  process  waiting  in  the  queue  associated  with  Si  into  the  ready  queue//将与 Si 关联的队列中**所有**等待的进程移动到就绪队列中
    }
}

信号量集

一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源(预留下限)还存在一个临界值时的信号量处理
一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Swait（S1，t1，d1，…，Sn，tn，dn）（满足ti≥ di）    
    if( S1 ≥t1 &…& Sn≥tn){  
          for(  i =1; i<=n; i++){
                    Si ＝Si － di;
          }
     }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//将进程置于与在 Si<ti 的条件下找到的**第一个** Si 关联的等待队列中，并将此过程的程序计数设置为 Swait 操作的开始
    }//end if
}//end Swait 

 Ssignal（S1，d1，···，Sn，dn）{
    for( i =1; i<= n; i++){  
        Si = Si + di；
        Remove  all  the  process  waiting  in  the  queue  associated  with  Si  into  the  ready  queue//将与 Si 关联的队列中**所有**等待的进程移动到就绪队列中
    }
}

三种特例：

  1. Swait(S,d,d)：允许每次申请d个资源。当资源数少于d时，不予分配。
  2. Swait (S,1,1)：S>1，记录型信号量。S=1时，互斥型信号量。
  3. Swait(S,1,0)，可控开关，当S>=1时，允许进入，S<1时，不能进入。

经典进程的同步问题

生产者——消费者问题

记录型信号量解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void producer( ){
    do{
		…
		Produce an item in nextp;
		…
		wait(empty);
		wait(mutex);
		buffer(in):=nextp;
		in:=(in+1) mod n;
		signal(mutex);
		signal(full);
	}while(TRUE);
}

void consumer{
  do{
  		wait(full);
		wait(mutex);
		nextc:=buffer(out);
		out:=(out+1) mod n;
		signal(mutex);
		signal(empty);
		Consumer the item in nextc;
		……
	}while(TRUE);
}

AND信号量解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int  in=0, out=0;
item    buffer[ n ];
semaphore  mutex=1, empty=n, full=0;
void producer( ){
	do{
		…
		produce an item in nextp;
		…
		Swait(empty, mutex);
		buffer[in] = nextp;
		in = (in+1) % n;
		Ssignal(mutex, full);
	}while(TRUE);
} //end producer

void consumer{
	do{
		Swait(full, mutex);
		nextc = buffer[out];
		out = (out+1) % n;
		Ssignal(mutex, empty);
		consumer the item in nextc;
	}while(TRUE);
}

哲学家进餐问题

几种解决方法：

  1. 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。
  2. 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。
  3. 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是1、 2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐

AND信号量解决

1
2
3
4
5
6
7
8
semaphore chopstick[5]={1,1,1,1,1};
do{
	……;
	think;
	Sswait(chopstick[(i+1) % 5],chopstick[i]);
	eat;
	Ssignal(chopstick[(i+1) % 5],chopstick[i]);
}while(TRUE);

读者——写者问题

记录型信号量解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
semaphore rmutex=1, wmutex = 1;
int readcount = 0;

void reader( ){
	do{
		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);
	}while(TRUE);
}//end reader

void writer( ){
	do{
		wait(wmutex)
		perform write operation;
		signal(wmutex)
	}while(TRUE);
}

void main(){
	cobegin
	reader(); writer();
	coend
}

信号量集解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int RN;
Semaphore L=RN, mx=1;
//RN标示同时允许多少读进程存在
void reader( ){
	   do{
              swait(L,1,1);
              swait(mx,1,0);
                   …
 	        perform read operation;
		        …
	         ssignal(L,1);
        }while(TRUE);
}//end reader

 void writer( ){
        do{
             swait(mx,1,1; L,RN,0);
             perform write operation;
             ssignal(mx, 1);
        }while(TRUE);
 } //end writer

 void main( ){
    cobegin
       reader(); writer();
    coedn
}

进程通信

类型

  • 共享存储器系统 - 基于共享数据结构的通信方式。基于共享存储区的通信方式。
  • 消息传递系统 - 是目前的主要通信方式，信息单位：消息（报文）实现：一组通信命令（原语），具有透明性、同步的实现。实现方式的不同，而分成：
    （1）直接通信方式
    （2）间接通信方式
  • 管道通信系统 - 管道：连接一个读进程和一个写进程之间通信的共享文件。 功能：大量的数据发收。 注意：
    （1）互斥
（2）同步
（3）**对方是否存在**
  • 客户机服务器系统

消息传递通信的实现方法

  • 直接通信方式
    这是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。
    系统提供下述两条通信命令（原语）：
    Send （Receiver， message）；
    Receive（Sender， message）；

  • 间接通信方式
    指进程之间利用信箱的通信方式。发送进程发送给目标进程的消息存放信箱；接收进程则从该信箱中，取出对方发送给自己的消息；消息在信箱中可以安全地保存，只允许核准的目标用户随时读取。
    系统为信箱通信提供了若干条原语，分别用于信箱的创建、撤消和消息的发送、接收等。优点：在读/写时间上的随机性
    信箱分为以下三类：
    （1）私用信箱
    （2）公用信箱
    （3）共享信箱
    在利用信箱通信时，在发送进程和接收进程之间，存在以下四种关系：
    （1）一对一关系。
    （2）多对一关系，客户/服务器交互。
    （3）一对多关系， 广播方式。
    （4）多对多关系。

消息格式

消息头：含控制信息如：收/发进程名，消息长度、类型、编号
消息内容：
定长消息：系统开销小，用户不便（特别是传长消息用户）
变长消息：开销大，用户方便。

消息格式进程同步方式

1）发送和接收进程阻塞（汇合）用于紧密同步，无缓冲区时。
2）发送进程不阻塞，接收进程阻塞（多个）相当于接收进程（可能是多个）一直等待发送进程，如：打印进程等待打印任务。
3）发送/接收进程均不阻塞一般在发、收进程间有多个缓冲区时。

进程运行与监控

Linux进程控制块

task_struct结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pid_t pid;
uid_t uid,euid; 
gid_t gid,egid;
volatile long state;
int exit_state;
unsigned int rt_priority;
unsigned int policy;
struct list_head tasks;
struct task_struct *real_parent;
struct task_struct *parent;
struct list_head children,sibling;
struct fs_struct *fs;
struct files_struct *files;
struct mm_struct *mm;
struct signal_struct *signal;
struct sighand_struct *sighand;
cputime_t utime, stime;
struct timespec start_time;
struct timespec real_start_time;

task_struct:进程状态

——volatile long state;
state成员的可能取值如下： 

1
2
3
4
5
#define TASK_RUNNING	0  
#define TASK_INTERRUPTIBLE	1  
#define TASK_UNINTERRUPTIBLE	2  
#define TASK_ZOMBIE	4  
#define TASK_STOPPED	8

进程状态切换

task_struct:文件管理

进程的启动

UNIX&Linux中创建进程的方式：

  • 在shell中执行命令或可执行文件由shell进程调用fork函数创建子进程

  • 在代码中（已经存在的进程中）调用fork函数创建子进程，fork创建的进程为子进程，原进程为父进程

  • Linux系统中进程0 （PID=0）是由内核创建，其他所有进程都是由父进程调用fork函数所创建的。进程0在创建子进程（PID=1，init进程）后，进程0就转为交换进程或空闲进程

  • 进程1（init进程）是系统中其他所有进程的共同祖先

fork

#include<unistd.h>头文件定义

1
2
3
/* Clone the calling process, creating an exact copy.
	Return -1 for errors, 0 to the new process,
	and the process ID of the new process to the old process.  */

fork函数被正确调用后，将会在子进程中和父进程中分别返回

  • 在子进程中返回值为0（不合法的PID，提示当前运行在子进程中）
  • 在父进程中返回值为子进程ID（让父进程掌握所创建子进程的ID号）
  • 出错返回-1

子进程是父进程的副本

  • 子进程复制/拷贝父进程的PCB、用户空间（数据段、堆和栈）
  • 父子进程共享正文段（只读）
    父进程继续执行fork函数调用之后的代码，子进程也从fork函数调用之后的代码开始执行为了提高效率，fork后不并立即复制父进程数据段、堆和栈，采用了写时复制机制（Copy-On-Write）：当父子进程任意之一要修改数据段、堆、栈时，进行复制操作，并且仅复制修改区域

子进程复制父进程的进程控制块

  • 父进程的文件描述符表被子进程复制，父子进程的同一文件描述符指向同一个文件表
  • 父子进程对同一文件访问基于相同的文件当前位置

父子进程对共享文件的常见处理方式：

  • 父进程等待子进程完成。当子进程终止后，文件当前位置已经得到了相应的更新
  • 父子进程各自执行不同的程序段，各自关闭不需要的文件

vfork函数保证子进程先执行，在它调用exec或者exit之后，父进程才会继续被调度执行（父进程处于TASK_UNINTERRUPTIBLE状态）

进程内存空间布局

  • 命令行参数和环境变量 - 主要用于支撑函数调用 存放参数、局部变量等
  • 堆栈 - 用于动态分配内存
  • 未初始化的数据 - 程序执行之前，将此段中 的数据初始化为0，如 全局变量long sum[1000];
  • 初始化的数据 - 包含了程序中需明确赋 初值的变量，如全局变量 int maxcount=99;
  • 正文 - CPU执行的代码部分，正文 段通常是共享、只读的

进程的运行控制

设置环境变量

设置环境变量的三种方法：

  • putenv - 将环境变量字符串放入环境变量表中
  • setenv - 将指定环境变量的值设置为参数指定值
  • unsetenv - 删除指定的环境变量字符串

exec系列函数

进程调用exec系列函数在进程中加载执行另外一个可执行文件
exec系列函数替换了当前进程（执行该函数的进程）的正文段、数据段、堆和栈（来源于加载的可执行文件），但并不修改PCB！
执行exec系列函数后从加载可执行文件的main函数开始重新执行
exec系列函数并不创建新进程，所以在调用exec系列函数后其进程ID(uid)并未改变，已经打开的文件描述符不变

execl execle execlp execv execve execvp
六个函数开头均为exec，所以称为exec系列函数

  • l：表示list，每个命令行参数都说明为一个单独的参数
  • v：表示vector，命令行参数放在数组中
  • e：表示由函数调用者提供环境变量表
  • p：表示通过环境变量PATH来指定路径，查找可执行文件

进程的监测

终止进程函数

头文件stdlib.h定义：void exit( int status )
头文件unistd.h定义：void _exit (int status ）
调用这两个函数均会正常地终止一个进程
调用 _exit 函数将会立即返回内核
调用 exit 函数执行一些预先注册的终止处理函数,执行文件I/O操作的善后工作，使得所有缓冲的输出数据被更新到相应的设备,返回内核

获知子进程状态改变

  • 主动获取 - 调用wait或waitpid函数等待子进程状态信息改变，并获取其状态信息
  • 异步通知 - 当一个进程发生特定的状态变化（进程终止、暂停以及恢复）时，内核向其父进程发送SIGCHLD信号，父进程可以选择忽略该信号，也可以对信号进行处理（默认处理方式为忽略该信号）

僵尸进程：
进程在退出之前会释放进程用户空间的所有资源，但PCB等内核空间资源不会被释放。当父进程调用wait或waitpid函数后，内核将根据情况关闭该进程打开的所有文件。而对于已经终止但父进程尚未对其调用wait或waitpid函数的进程（TASK_ZOMBIE状态），称为僵尸进程。

孤儿进程：
如果 父进程在子进程终止之前终止，则子进程的父进程将变为init进程，保证每个进程都有父进程，由init进程调用wait函数进行善后

wait函数

头文件：sys/wait.h
功能：获取任意子进程的状态改变信息（如果是终止状态则对子进程进行善后处理）
pid_t wait(int *statloc);
参数statloc：用于存储子进程的状态改变信息
若成功返回状态信息改变的子进程ID，出错返回-1
子进程状态改变信息包含了多种类型的信息，可以通过系统提供的宏来快速解析子进程的状态
如：
| 宏 | 功能说明 |
| — | — |
| WIFEXITED(statloc) | 当子进程正常终止时该宏为真，对于这种情况可进一步执行WEXITSTATUS(statloc)，获取子进程传递给exit、_exit函数参数的低8位 |
| WIFSIGNALED(statloc) | 当子进程异常终止时该宏为真，对于这种情况可进一步执行WTERMSTG(statloc)，获取使子进程终止的信号编号 |
| WIFSTOPPED(statloc) | 当子进程暂停时该宏为真，对于这种情况可进一步执行WSTOPSIG(statloc)，获取使子进程暂停的信号编号 |
| WIFCONTINUED(statloc) | 若子进程在暂停后已经继续则该宏为真 |

如果一个进程有几个子进程，那么只要有一个子进程状态改变，wait函数就返回

如何才能使用wait函数等待某个特定子进程的状态改变？

  1. 调用wait，然后将其返回的进程ID和所期望的子进程ID进行比较
  2. 如果ID不一致，则保存该ID，并循环调用wait函数，直到等到所期望的子进程ID为止
waitpid函数

功能：等待某个特定子进程状态改变
pid_t waitpid(pid_t pid, int *statloc, int options);
参数：

  • pid：pid == -1：等待任意子进程状态改变（同wait）；pid > 0：等待进程ID为pid的子进程状态改变；pid == 0：等待其组ID等于调用进程组ID的任意子进程；pid < -1：等待其组ID等于pid绝对值的任意子进程
  • statloc：用于存储子进程的状态改变信息
  • options：可以为0，也可以是以下常量：WNOHANG：如果没有任何已经终止的子进程则马上返回, 函数不等待，此时返回值为0；WUNTRACED：用于跟踪调试
    成功返回终止子进程ID，失败返回-1

waitpid可以实现非阻塞的等待操作，有时希望取得子进程的状态改变信息，但不希望阻塞父进程等待子进程状态改变

线程的基本概念

  1. 在一个已有进程中创建一个新线程比创建一个全新进程所需的时间少。
  2. 终止一个线程比终止一个进程花费的时间少。
  3. 线程间切换比进程间切换花费的时间少。
  4. 线程提高了不同的执行程序间通信的效率。同一个进程中的线程共享存储空间和文件，它们无需调用内核就可以互相通信。

线程的引入

引入进程是为了使多个程序能够并发执行，以提高资源利用率和系统吞吐量；
引入线程是为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性
进程的两个基本属性

  • 一个可拥有资源的独立单位
  • 一个可调度和分派的基本单位

调度和分派的部分通常称为线程或轻型进程，而资源所有权的部分通常称为进程。

线程与进程的比较

从调度性、并发性、系统开销和拥有资源等方面对线程和进程进行比较。
（线程必须在某个进程内执行 一个进程可以包含一个线程或多个线程）

调度

在传统的操作系统中，进程作为拥有资源和独立调度、分派的基本单位。而在引入线程的操作系统中，则把线程作为调度和分派的基本单位，而进程作为资源拥有的基本单位。

并发

在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，使得操作系统具有更好的并发性，从而能更加有效地提高系统资源的利用率和系统的吞吐量。

拥有资源

一般而言，线程自己不拥有系统资源(也有一点必不可少的资源)，但它可以访问其隶属进程的资源，即一个进程的代码段、数据段及所拥有的系统资源，如已打开的文件、I/O 设备等，可以供该进程中的所有线程所共享。

独立性

同一进程中的不同线程共享进程的内存空间和资源。
同一进程中的不同线程的独立性低于不同进程。

系统开销

线程的切换只需要保存和设置少量的寄存器内容，不涉及存储器管理方面的操作。
由于一个进程中的多个线程具有相同的地址空间，在同步和通信的实现方面线程也比进程容易。在一些操作系统中，线程的切换、同步和通信都无须操作系统内核的干预。（少）

支持多处理机系统

一个进程分为多个线程分配到多个处理机上并行执行，可加速进程的完成。

线程的属性

  1. 轻型实体
    线程自己基本不拥有系统资源，只拥有少量必不可少的资源：TCB，程序计数器、一组寄存器、栈。
  2. 独立调度和分派的基本单位
    在多线程OS中,线程是独立运行的基本单位,因而也是独立调度和分派的基本单位。
  3. 可并发执行
    同一进程中的多个线程之间可以并发执行，一个线程可以创建和撤消另一个线程。
  4. 共享进程资源
    它可与同属一个进程的其它线程共享进程所拥有的全部资源。

线程的状态

同进程一样，线程之间也存在共享资源和相互合作的制约关系，致使线程在运行时也具有间断性。
线程运行时有以下3种状态：
①执行状态:表示线程正获得CPU而运行；
②就绪状态:表示线程已具备了各种运行条件，一旦获得CPU便可执行；
③阻塞状态:表示线程在运行中因某事件而受阻，处于暂停执行的状态；

线程的组成

每个线程有一个TCB结构，即线程控制块，用于保存自己私有的信息，主要由以下部分组成：

  • 一个唯一的线程标识符；
  • 一组寄存器 ：包括程序计数器、状态寄存器、通用寄存器的内容；
  • 线程运行状态：用于描述线程正处于何种运行状态；
  • 优先级：描述线程执行的优先程度；
  • 线程专有存储器：用于保存线程自己的局部变量拷贝；
  • 信号屏蔽：对某些信号加以屏蔽；
  • 两个栈指针：核心栈、用户栈。

进程线程对比

应用功能 线程 进程
创建 pthread_create fork,vfork
退出 pthread_exit exit
等待 pthread_join wait、waitpid
取消/终止 pthread_cancel abort
读取ID pthread_self() getpid()
同步互斥/通信机制 互斥锁、条件变量、读写锁 无名管道、有名管道、信号、消息队列、信号量、共享内存

线程间的同步和通信

▪为使系统中的多线程能有条不紊的运行，系统必须提供用于实现线程间同步和通信的机制。在多线程OS中，通常提供多种同步机制:

  • 互斥锁(mutex) - 互斥锁是一种比较简单的、用于实现进程间对资源互斥访问的机制。 由于操作互斥锁的时间和空间开销都较低，因而较适合于高频度使用的关键共享数据和程序段。
  • 条件变量 - 每一个条件变量通常都与一个互斥锁一起使用。 单纯的互斥锁用于短期锁定，主要是用来保证对临界区的互斥进入。而条件变量则用于线程的长期等待， 直至所等待的资源成为可用的。
  • 信号量机制 - 当某线程需利用信号量来实现同一进程中各线程之间的同步时，可调用创建信号量的命令来创建一私用信号量，其数据结构存放在应用程序的地址空间中。

线程的实现方式

用户级线程

用户级线程仅存在于用户空间中。对于这种线程的创建、撤消、线程之间的同步与通信等功能，都无须内核来实现。
优点：

  • 线程切换不调用内核
  • 调度是应用程序特定的：可以选择最好的算法
  • 可运行在任何操作系统上（只需要线程库），可以在一个不支持线程的OS上实现
    缺点：
  • 当线程执行一个系统调用时，该线程及其所属进程内的所有线程都会被阻塞。
  • 多线程应用不能利用多处理机进行多重处理。

内核支持线程

内核支持线程，是在内核的支持下运行的，即无论是用户进程中的线程，还是系统进程中的线程，他们的创建、撤消和切换等，是依靠内核实现的。
优点：

  • 在多处理器系统中，内核能够同时调度同一进程中多个线程并行执行；
  • 如果进程中的一个线程被阻塞了，内核可以调度该进程中的其它线程占有处理器运行，也可以运行其它进程中的线程；
  • 内核支持线程具有很小的数据结构和堆栈，线程的切换比较快，切换开销小；
  • 内核本身也可以采用多线程技术，可以提高系统的执行速度和效率。
    缺点：
    对于线程切换而言，其模式切换的开销较大 在同一个进程中，从一个线程切换到另一个线程时，需要从用户态转到内核态再转到用户态进行，这是因为用户进程的线程在用户态运行，而线程调度和管理是在内核实现的，系统开销较大。

组合方式

用户级线程是在用户空间实现的。所有用户级线程都具有相同的数据结构，它们都运行在一个中间系统上：
运行时系统（又称为线程库）
内核控制线程又称为轻型进程LWP
enter description here

习题

  1. 什么是前趋图？为什么要引入前趋图？
    指一个有向无环图，用于描述进程之间执行的先后顺序

  2. 画出前趋图：S1:a=x+y;S2:b=z+1;S3:c=a-b;S4:w=c+1;
    未命名文件

  3. 为什么要引入进程，会产生什么影响？
    为了使程序并发的执行，并且可以对并发执行的程序加以描述与控制；使程序可以并发执行

  4. 从动态性、并发性和独立性的角度比较进程和程序
    动态性：进程的实质是进程实体的执行过程，具有生命周期。而程序是静态的一组有序指令集。
    并发性：进程可以并发执行。程序没有建立PCB不能并发执行。
    独立性：进程是一个能够独立运行的、独立获得资源的、独立接受调度的基本单位。未建立PCB的程序不能独立参与运行

  5. PCB的作用？为什么说PCB是进程唯一标志
    PCB是进程实体的一部分，PCB使一个程序成为能够独立运行的基本单位，PCB描述进程的基本情况和活动过程，进而控制和管理进程。操作系统是通过PCB来对进程进行控制和管理的。

  6. 进程的三个基本状态转化原因
    有1就绪状态——执行状态：进程调度
    执行状态——就绪状态：时间片完成
    执行状态——阻塞状态：I/O请求
    阻塞状态——就绪状态：I/O完成

  7. 为什么要引入挂起状态，有什么性质？
    有终端用户需求、父进程请求、负荷调节的需要、操作系统的需要；挂起状态进程静止不能被调度

  8. 进程切换时要保存的处理器状态信息有哪些？
    通用寄存器、指令寄存器、程序状态寄存器、用户栈指针

  9. 引起进程创建的主要事件
    用户登录、作业调度、提供服务、应用请求

  10. 引起进程撤销的主要事件
    正常结束、异常结束（越界错、保护错、非法指令、特权指令错、运行超时、等待超时、算数运算错、I/O故障）、外界干扰（操作员或操作系统干预、父进程请求、因父进程终止而终止）

  11. 创建进程时所要完成的主要工作
    申请空白PCB、为新进程分配资源、初始化PCB、插入就绪队列

  12. 引起进程阻塞或被唤醒的主要事件
    请求共享资源失败、等待某种操作、新数据尚未到达、等待新任务

  13. 从调度性、并发性、拥有资源及系统开销方面对比进程与线程
    调度性：线程作为调度和分派的基本单位，而进程作为资源拥有的基本单位。
    并发性：均可并发执行。
    拥有资源：进程是拥有资源的基本单位，线程只拥有必不可少的资源，本身不拥有系统资源，但可以访问隶属资源。
    系统开销：在创建、撤销和切换进程的开销显著大于线程。

  14. 解释用户级线程与内核支持线程
    用户级线程：用户级线程仅存在于用户空间中。对于这种线程的创建、撤消、线程之间的同步与通信等功能，都无须内核来实现。
    内核支持线程：内核支持线程，是在内核的支持下运行的，即无论是用户进程中的线程，还是系统进程中的线程，他们的创建、撤消和切换等，是依靠内核实现的。

处理机调度与死锁

处理机调度的层次

  • 高级调度 - 又称长程调度或作业调度，将外存作业调入内存，创建PCB等，插入就绪队列。用于批处理系统。调度最慢
  • 低级调度 - 又称进程调度或短程调度，决定就绪队列中的那个进程应获得处理机，并将处理机分配给选中的进程。调度最频繁
  • 中级调度 - 又称内存调度，把外存上那些已经具备运行条件的就绪进程重新载入内存。从静止就绪到活动就绪。

处理机调度算法的目标

共同目标：

  • 资源利用率：使系统处理器和资源尽可能忙碌
  • 公平性：为进程合理分配CPU时间，不会发生饥饿
  • 平衡性：为不同类型进程平衡分配资源
  • 策略强制执行：如安全策略可无条件准确执行

批处理系统的目标

  • 平均周转时间短
  • 系统吞吐量高：尽量多地选择短作业运行
  • 处理机利用率高：尽量选择计算量大的作业

分时系统的目标

  • 响应时间快
  • 均衡性：指系统响应时间的长短应与用户所请求服务的复杂性相适应。

实时系统的目标

  • 截至时间的保证：开始截止时间 完成截止时间 硬实时、软实时
  • 可以预测性：对调度结果的可预见性

作业与作业调度

  • 作业 Job：用户提交给系统的一项相对独立的工作。程序+数据+作业说明书
  • 作业步：在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，每一个加工步骤称为一个作业步，各作业步之间存在着相互联系。
  • 作业流：依次执行的作业步，作业步间非并行的。

作业控制块(JCB)

作业在系统中存在的标志，保存了系统对作业进行管理和调度的全部信息。
通常包含：

  • 作业标识
  • 用户名称
  • 用户账号
  • 作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)
  • 作业状态
  • 调度信息(CPU 繁忙型、I/O 繁忙型、批量型、终端型)
  • 资源需求(预计运行时间、要求内存大小、要求 I/O 设备的类型和数量等)
  • 资源使用情况等

作业运行的三个阶段和三种状态

收容阶段：后备状态
运行阶段：运行状态
完成阶段：完成状态

作业调度的主要任务

  • 接纳多少个作业：太多会影响系统服务质量，如延长周转时间；太少会导致资源利用率和系统吞吐量太低
  • 接纳哪些作业：将哪些作业从外存调入内存，取决于所采用的调度算法

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

在作业调度中是从后备队列调入内存运行。
在进程调度中则是从就绪队列中选出估计运行时间最短的进程分配处理机使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。

先来先服务：

既可用于作业调度，也可用于进程调度。有利于长作业（进程），而不利于短作业（进程）。

短作业(进程)优先调度算法SJ(P)F：

是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。
对长作业不利，不能保证紧迫性作业(进程)会被及时处理，根据用户所提供的估计执行时间而定不准确。

优先级调度算法和高响应比优先调度算法

优先级调度算法：
外部赋予作业（进程）相应的优先级，例如以作业的紧迫程度作为优先级。
选择优先级高的进程投入运行。既可用于作业调度算法，也可用于进程调度。

高响应比优先调度算法：
赋予作业动态优先级，优先级随作业等待时间延长而增加，从而使长作业的优先级在等待期间不断增加。
响应比Rp：
enter description here
算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务

进程调度

主要任务

  • 保存处理机的现场信息
  • 按某种算法选取进程
  • 把处理机分配给进程strong text

进程调度机制

enter description here

进程调度方式

非抢占方式：

一旦进程投入运行，除了进程完成或者需要阻塞外，不能剥夺其处理机。
采用这种方式时，引起调度的原因可归结为：

  • 进程运行完毕或因发生某事件而无法继续运行
  • 因I/O请求而阻塞
  • 因通信或者同步而阻塞

抢占方式：

允许根据某种原则，暂停正在执行的进程，重新分配处理机。
使用抢占式的原因：

  • 批处理：防止长进程长期占用CPU，公平
  • 分时：人机交互
  • 实时：紧迫任务的执行
    主要原则
  • 优先权
  • 短进程优先
  • 时间片原则

轮转调度算法(RR)

基于时间片轮转
原理： FCFS策略+时钟中断+时间片原则
时间片太小：利于短作业，但增大调度和上下文切换频率，增大系统开销； 时间片太长：退化为FCFS算法。 时间片合适：略大于一次典型的交互所需的时间，使大多数交互式进程能在一个时间片内完成。
当进程的时间片耗尽或运行完毕，系统将CPU分配给队首进程（或新到达紧迫进程）

优先级调度算法

同样分为非抢占式和抢占式
对于优先级是的设立还分为静态优先权（简单，但低优先权作业可能长期不被调度）和动态优先权（长短兼顾 缺点：需计算 Rp=(等待时间＋服务时间)/服务时间 ）

多队列调度算法

针对：不同用户的调度策略需求:实时/分时/批处理混合系统
和多CPU单就绪队列的问题:互斥访问导致效率不高
解决办法:
不同类型或者性质的进程组织在不同的队列中
每个CPU和一个队列，分配优化，CPU间队列均衡

多级反馈队列调度算法

设置多个就绪队列，并为各个队列赋予不同的优先级。
优先级愈高的队列的进程的执行时间片就愈小。
新进程首先进入最高优先级的队列。每个队列采用FCFS算法。队列中的进程运行一个时间片后未结束则降级排到下一个队列的末尾。最低优先权队列中的进程则按RR方式运行。
按队列优先级调度。只有比队列的优先级高的队列均空时，才运行该队列中的进程。
特点：长、短作业兼顾，有较好的响应时间

基于公平原则的调度算法

  1. 保证调度算法 - 保证的是绝对运行时间，即启动后在某个时间段内必须获得多少运行时间。 例如N个进程平均分配时间。
  2. 公平分享调度算法 - 按照用户数量平均分配时间，而不是进程间平均分配。

实时调度

实时调度必须满足实时任务对截至时间的要求

实现实时调度的基本条件

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

单处理机条件下必须保证处理时间与截至时间之比小于1

实时调度算法的分类

非抢占式

enter description here

  1. 非抢占式轮转调度
  2. 非抢占式优先调度

抢占式

  1. 基于时钟中断的抢占式
  2. 立即抢占式

EDF最早截至时间算法

就绪队列按各任务截止时间的早晚排序；具有最早截止时间的任务排在队列的最前面。

LLF最低松弛度优先算法

松弛度=完成截至时间–剩余运行时间–当前时间
按松弛度排序实时任务的就绪队列，松弛度值最小的任务排在队列最前面

优先级倒置

即高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞。
主要原因可能是较低优先级任务占用临界资源后未释放而切换任务执行
解决方法：

  • 规定进入临界区后不允许抢占
  • 优先级继承机制(动态优先级)，即占用同样资源的低优先级进程继承需要资源的进程的高优先级

死锁

资源问题

  • 可重用性资源(打印机)和消耗性资源(消息)
  • 不可抢占性资源(打印机)

计算机系统的死锁

原因：

  1. 竞争可重用资源、可消耗资源
  2. 进程间推进顺序非法。
    enter description here

定义、必要条件和处理方法

定义：如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的

四个条件：

  1. 互斥条件：指进程对所分配到的资源进行排它性使用 。
  2. 请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求 。
  3. 不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
  4. 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链 。

预防死锁

通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。
预防死锁使四个必要条件中的第2、3、4条件之一不能成立

破环条件2

通过：

  • 第一种协议规定开始运行之前，必须一次性申请所需的全部资源
  • 第二种协议规定进程在运行过程中要逐步释放已用资源再请求新资源
  • *优点**：简单、易于实现且很安全。
  • *缺点**：资源被严重浪费，使进程延迟运行。
破环条件3

当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源。待以后需要时再重新申请
缺点：因反复地申请和释放资源，致使进程执行被无限推迟，延长进程周转时间、增加系统开销、降低吞吐量

破环条件4

将所有资源按类型进行线性排队，并赋予不同的序号。 所有进程对资源的请求必须严格按照资源序号递增的次序提出
优点：相比前两种提高了资源利用率和系统吞吐量
缺点：各类资源分配的序号必须相对稳定限制了新设备类型的增加；作业使用顺序与系统规定顺序不同造成资源浪费；增加了程序设计难度。

避免死锁

是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。不会事先设置限制
安全状态是指系统能按某种进程顺序，使每个进程都可顺利地完成，称系统处于安全状态。

Dijkstra银行家算法

可利用资源向量Available
最大需求矩阵Max
分配矩阵Allocation
需求矩阵Need
P120

死锁的检测与解除

检测死锁：通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；
解除死锁：当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤消或挂起一些进程。
配套使用

检测：

系统必须保存有关资源的请求和分配信息，根据信息通过资源分配图或死锁定理的方法检测死锁

解除：

两种常用方法：抢占资源(使死锁进程抢占其它进程资源以完成进程解除死锁)、终止进程(终止或撤销死锁进程)
其中终止方法可终止所有死锁进程，更好是按付出代价最小算法逐个解除

付出代价最小算法

  • 一种找到付出代价最小的终止顺序，但成本高的算法：

    1. 先从死锁进程组中取出一个，形成第一层终止，若有n个死锁进程，则有n个第一层。
    2. 再从n个第一层中取一个，形成第二层终止，每个第一层又有n-1个第二层终止。
    3. 如此循环，直到解除死锁，将各层的总代价计算，得到最小的终止顺序。
      理解为从最低代价开始依次找到导致死锁的最低代价进程

  • 另一种比较有效的算法：

    1. 找到死锁进程组中，终止代价最小的，将其从死锁进程组中删去。
    2. 再从新的死锁进程组中，找到终止代价最小的，删去。
    3. 如此循环，直到解除死锁。
      理解为一直解除最低代价进程(不判断此时死锁是否由它导致)直到解除死锁

习题

1、假设一个多级反馈队列的实现共有4级，各个队列的时间片长度是1、2、4、6秒，已知当前仅在第一级队列上有一个执行时长为10秒的进程O，在两秒后将有一个执行时长为8秒的任务A到达，请算出任务A的周转时间。
1:10-1=9O
2
4
6

1
2:9-1=8O
4
6
任务A到达
1:8-1=7A
2:
4:8O
6

1:
2:7A
4:8O-4=4O
6

1:
2:7A-2=5A
4:
6:4O

1:
2:
4:5A
6:4O-4=0O完成

1:
2:
4:5A-4=1A
6:

1:
2:
4:
6:1A-1=0A完成

所以答案等于1+4+2+4+4+1=16s

2、简述死锁的必要条件，以及预防死锁方法与必要条件的关系。
四个条件：

  1. 互斥条件：指进程对所分配到的资源进行排它性使用 。
  2. 请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求 。
  3. 不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
  4. 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链

预防死锁通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。预防死锁使四个必要条件中的第2、3、4条件之一不能成立：

破环条件2通过：第一种协议规定开始运行之前，必须一次性申请所需的全部资源
第二种协议规定进程在运行过程中要逐步释放已用资源再请求新资源；

破环条件3当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源。待以后需要时再重新申请；

破环条件4将所有资源按类型进行线性排队，并赋予不同的序号。 所有进程对资源的请求必须严格按照资源序号递增的次序提出。

3、在银行家算法中，若出现下述资源分配情况，试问：
| Process | Allocation | Need__ | Available |
|—|—|—|—|
| P0 | 0 0 3 2 | 0 0 1 2 | 1 6 2 2 |
| P1 | 1 0 0 0 | 1 7 5 0 |
| P2 | 1 3 5 4 | 2 3 5 6 |
| P3 | 0 3 3 2 | 0 6 5 2 |
| P4 | 0 0 1 4 | 0 6 5 6 |

（1）该状态是否安全？
安全，先执行P0后按P3、P4、P1、P2顺序即可完成全部进程
（2）若进程 P2 提出请求 Request（1，2，2，2）后，系统能否将资源分配
给它？
能，可按P2、P0、P3、P4、P1执行完成

---------------THEEND---------------