Hexo
0%

操作系统第二章

发表于 更新于 分类于
第二章学习笔记

进程的定义、组成、组织方式、特征

操作系统知识总览2.1
这里要注意图片的格式是jpg还是png

一、进程的定义
1、程序：就是一个指令序列
2、早期的计算机（只支持单道程序）程序包含程序段和数据段，程序的代码放在程序段内，程序运行过程处理的数据放在数据段内（如变量）。
3、引入多道程序技术之后：内存中同时放入多道程序，各个程序的代码、运算数据存放的位置不同。操作系统要确定各个程序的存放位置。为了方便操作系统管理，完成各程序并发执行、引入了进程、进程实体的概念。
系统位每个运行的程序配置一个数据结构，称为进程控制块（PCB），用来描述进程的各种信息（如程序代码存放位置）
PCB、程序段、数据段三部分构成了进程实体（进程映像）
4、程序段、数据段、PCB三部分组成了进程实体（进程映像）。一般情况下，我们把进程实体就简称为进程，例如，所谓创建进程，实质上是创建进程实体中的PCB；而撤销进程，实质上是撤销进程实体中的PCB。
注意：PCB是进程存在的唯一标志。
5、进程是程序的一次执行过程。
6、进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
7、进程是具有独立功能的程序在数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。
8、567从不同的角度定义了了进程，他们都强调“动态性”。
9、在引入进程实体的概念后，可把进程定义为：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
10、严格来说，进程实体和进程并不一样，进程实体是静态的，进程则是动态的。不过，除非题目专门考察二者区别，否则可以认为进程实体就是进程。因此我们也可以说“进程有程序段、数据段、PCB三部分组成”。

二、进程的组成
1、进程（进程实体）由程序段、数据段、PCB三部分组成。
2、程序段存放的就是程序的代码本身。程序运行时使用、产生的运算数据。如全局变量、局部变量、宏定义的变量就存放在数据段内。
3、操作系统通过PCB来管理进程，因此PCB中应该包含操作系统对其进行管理所需的各种信息。
操作系统PCB2.1
进程标识符PID：当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的ID，用于区分不同的进程（类似于身份证号）
保存各种寄存器值的原因：当进程切换时需要把进程当前的运行状况记录下来保存在PCB中，如程序计数器的值表示了当前程序执行到哪一句。
4、另一种分类方式
进程标识符
处理机状态
进程调度信息
进程控制信息
操作系统进程的组成2.1
注意：进程的管理者（操作系统）所需的数据都在PCB中。程序段和数据段存放的是程序本身运行所需的数据。

三、进程的组织
1、在一个系统中，通常有数十、数百乃至数千个PCB。为了能对他们加以有效的管理，应当用适当的方式把这些PCB组织起来。
注：进程的组成讨论的是一个进程内部由哪些部分构成的问题，而进程的组织讨论的是多个进程之间的组织方式问题。
操作系统进程的组织方式2.1
2、链接方式
执行指针：指向当前处于运行态（执行态）的进程。单CPU计算机中，同一时刻只会有一个进程处于运行态。
就绪队列指针：指向当前处于就绪态的进程
阻塞队列指针：指向当前处于阻塞态的进程，很多操作系统还会根据阻塞原因不同，再分为多个阻塞队列。
3、索引方式
上述指针指向的是一个索引表而不是一个队列（链表）的队头。

四、进程的特征
操作系统进程的特征2.1
1、动态性是进程最基本的特征。
2、进程是资源分配、接受调度的基本单位。
3、异步性会导致并发程序执行结果的不确定性。具体会在“进程同步”相关小节进行学习。

操作系统知识回顾2.1
1、PCB是进程存在的唯一标志。
2、进程管理者（操作系统）所需的数据都在PCB中
3、程序本身的运行所需的数据在程序段、数据段中

进程的状态与转换

操作系统知识总览2.2

一、进程的状态—三种基本状态
1、进程是程序的一次执行。在这个执行过程中，有时进程正在被CPU处理，有时又需要等待CPU服务，可见，进程的状态是会有各种变化。为了方便对各个进程的管理，操作系统需要将进程合理地划分为几种状态。
操作系统进程的三种基本状态2.2
2、运行态注意：单核处理机环境下，每一时刻最多只有一个进程处于运行态。（双核环境下可以同时有两个进程处于运行态）
3、就绪态注意：进程已经拥有了除处理机之外所有需要的资源，一旦获得处理机，即可立即进入运行态开始运行。即：万事俱备，只欠CPU
4、阻塞态注意：等待操作系统分配打印机、等待读磁盘操作的结果。CPU是计算机中最昂贵的部件，为了提高CPU的利用率，需要先将其他进程需要的资源分配到位，才能得到CPU的服务。

二、进程的状态—另外两种状态
1、操作系统需要完成创建进程。操作系统为该进程分配所需的内存空间等系统资源，并为其创建、初始化PCB（如：为进程分配PID）
2、进程运行结束（或者由于bug导致进程无法继续执行下去，比如数组越界错误），需要撤销进程。
操作系统需要完成撤销进程相关的工作。完成将分配给进程的资源回收、撤销进程PCB等工作。
操作系统进程的另外两种状态2.2

三、进程状态的转换
操作系统进程状态的转换2.2
1、运行态->阻塞态是一种进程自身做出的主动行为。
2、阻塞态->就绪态不是进程自身能控制得，是一种被动行为。
3、注意：不能由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态（因为进入阻塞态是进程主动请求得，必然需要进程在运行时才能发出这种请求）

操作系统知识回顾2.2

进程控制

操作系统知识总览2.3

一、进程控制
1、进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。
简化理解：进程控制就是要实现进程状态转换
操作系统实现进程控制2.3
2、用原语实现进程控制。原语的特点是执行期间不允许中断，只能一气呵成。这种不可被中断的操作即原子操作。
3、原语采用“关中断指令”和“开中断指令”实现
4、显然，关/开中断指令的权限非常大，必然是只允许在核心态下执行的特权指令。

二、进程控制相关的原语
1、学习技巧：进程控制会导致进程状态的转换。无论哪个原语，要做的无非三类事情。更新PCB中的信息、将PCB插入合适的队列、分配/回收资源。
2、更新PCB中的信息（如修改进程状态标志、将运行环境保存到PCB、从PCB恢复运行环境）
a、所有的进程控制原语一定都会修改进程状态标志
b、剥夺当前运行进程的CPU使用权必然需要保存其运行环境
c、某进程开始运行前必然要恢复其运行环境
操作系统进程的创建2.3
3、创建原语：无->创建态->就绪态
操作系统进程的终止2.3
4、撤消原语：就绪态/阻塞态/运行态->终止态->无。
操作系统进程的阻塞和唤醒2.3
5、阻塞原语：运行态->阻塞态
6、唤醒原语：阻塞态->就绪态
7、因何事阻塞，就应由何事唤醒
8、阻塞原语唤醒原语必须成对使用
操作系统进程的切换2.3
9、切换原语：运行态->阻塞态/就绪态；就绪态->运行态
操作系统知识回顾2.3

进程通信

操作系统知识总览2.4

一、什么是进程通信
1、顾名思义，进程通信就是指进程之间的信息交换。
2、进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。
3、为了保证安全，一个进程不能直接访问另一个进程的地址空间。
4、但是进程之间的信息交换又是必须实现的。为了保证进程间的安全通信，操作系统提供了一些方法。
5、进程通信的方法：共享存储、消息传递、管道通信。

二、共享存储
操作系统进程通信共享存储2.4
1、两个进程对共享空间的访问必须是互斥的（互斥访问同故宫操作系统提供的工具实现）。
2、操作系统只负责提供共享空间和同步互斥工具（如P，V操作）
3、共享存储：基于数据结构的共享、基于存储区的共享
4、基于数据结构的共享：比如共享空里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式。
5、基于存储区的共享：在内存中画出一块共享存储区，数据的形式、存放位置都由进程控制，而不是操作系统。相比之下，这种共享方式速度更快，是一种高级通信方式。

三、管道通信
操作系统进程通信管道通信2.4
1、“管道”是指用于连接读写进程的一个共享文件，又名pipe文件。其实就是在内存中开辟一个大小固定的缓冲区。
2、管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
3、各进程要互斥地访问管道。
4、数据以字符流的形式写入管道，当管道写满时，写进程的write（）系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read（）系统调用将被阻塞。
5、如果没写满，就不允许读。如果没读空，就不允许写。
6、数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。

四、消息传递
1、进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。
2、消息包括消息头和消息体两部分。消息头包括：发送进程ID、接受进程ID、消息类型、消息长度等格式化的信息（计算机网络中发送的“报文”其实就是一种格式化的消息）
３、消息传递的两种方式
直接通信方式:消息直接挂到接收进程的消息缓冲队列上
间接通信方式:消息要先发送到中间实体(信箱)中,因此也称”信箱通信方式”.Eg:计网中的电子邮件系统
操作系统知识回顾2.4

线程概念多线程模型

操作系统知识总览2.5
一、线程
1、有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此，引入了“线程”，来增加并发度。
2、传统的进程是程序执行流的最小单位。
3、引入线程后，线程成为了程序执行流的最小单位。
4、可以把线程理解为“轻量级进程”。
5、线程是一个基本的CPU执行单元，也是进程执行流的最小单位。引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务。
6、引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。
操作系统引入线程的变化2.5
操作系统线程的属性2.5

二、线程的实现方式
1、用户级线程（User-Level Thread,ULT）
操作系统用户级线程2.5
2、内核级线程
操作系统内核级线程2.5
3、在同时支持用户级线程和内核级线程的系统中，可采用二者组合的方式：将n各用户级线程映射到m各内核级线程上（n>=m）
操作系统线程的实现方式2.5

三、多线程模型
1、在同时支持用户级线程和内核级线程的系统中，由几个用户级线程映射到几个内核级线程的问题引出了“多线程模型”问题。
操作系统多对一模型2.5
操作系统一对一模型2.5
操作系统多对多模型2.5
操作系统知识回顾2.5

处理机调度概念、层次

操作系统知识总览2.6
一、调度的基本概念
1、当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题。
2、在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程。
3、处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。
二、调度的三个层次—高级调度
1、由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则来决定将作业调入内存的顺序。
2、高级调度（作业调度）：按一定的原则从外存上处于后备队列的作业中挑选一个（或多个）作业，给他们分配内存等必要资源，并建立相应的进程（PCB），以使它（们）获得竞争处理机的权利。
3、高级调度使辅存（外存）与内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。
三、调度的三个层次—中级调度
1、引入了虚拟存储技术之后，可将暂时不能运行的进程调至外存等待。等它重新具备了运行条件且内存又稍有空闲时，再重新调入内存。
2、这么做的目的是为了提高内存利用率和系统吞吐量。
3、暂时调到外存等待的进程状态为挂起状态。值得注意的是，PCB并不会一起调到外存，而是会常驻内存。PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到挂起队列中。
4、中级调度（内存调度）：就是要决定将哪个处于挂起状态的进程重新调入内存。
5、一个进程可能会被多次调出、调入内存，因此中级调度发生的频率比高级调度更高。
四、进程挂起态与七状态模型
1、暂时调到外存等待的进程状态为挂起状态（挂起态，suspend）。
2、挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。
3、五状态->七状态
操作系统七状态模型2.6
4、有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。
五、调度的三个层次—低级调度
1、低级调度（进程调度）其主要任务时按照某种方法和策略从就绪对列中选取一个进程，将处理机分配给它。（调度算法要研究的问题）
2、进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。
3、进程调度的频率很高，一般几十毫秒一次。
操作系统三层调度的联系对比2.6
操作系统知识回顾2.6

进程调度的时机、切换与过程、调度方式

操作系统知识总览2.7
一、进程调度的时机
1、进程调度（低级调度），就是按照某种算法从就绪队列中选择一个进程为其分配处理机。
操作系统进程调度的时机2.7
2、进程在操作系统内核程序临界区中不能进行调度与切换。
错误表述：进程处于临界区时不能进行处理机调度。（区分普通临界区和内核临界区）
3、临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。
4、临界区：访问临界资源的那段代码。
5、内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程的PCB组成）
6、如果进程还没退出临界区（还没解锁）就进行进程调度，此时进程调度相关的程序也需要访问就绪队列，但此时就绪对列被锁住了，因此又无法顺利进行进程调度。
因此内核程序临界区访问的临界资源如果不尽快释放的话，极有可能影响到操作系统内核的其他管理工作。因此在访问内核程序临界区期间不能进行调度与切换。要让进程尽快的完成对临界资源的访问从而尽快解锁。
7、在打印机打印完成之前，进程一直处于临界区内，临界资源不会解锁。但打印机又是慢速设备，此时如果一直不允许进程调度的话就会导致CPU一直空闲。
普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。因此在访问普通临界区时可以进行调度与切换。
8、虽然需要进行进程调度与切换的情况有两种（主动放弃和被动放弃），但是在有的操作系统中，只允许进程主动放弃处理机。有的操作系统中，进程可以主动放弃处理机，当有更紧急的任务需要处理时，也会强行剥夺处理机（被动放弃）。
9、进程在操作系统内核程序临界区中不能进行进程的调度与切换，但是进程在普通临界区中时可以进行调度、切换的。
二、进程调度的方式
1、非剥夺调度方式，又称非抢占式。即，只允许进程主动放弃处理机。在运行过程中即便又更紧迫的任务到达，当前进程依然会继续使用处理机，知道该进程终止或主动要求进入阻塞态。
特点：实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统。
2、剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。
特点：可以优先处理更紧急的进程，也可实现让各个进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统。
三、进程的切换与过程
1、“狭义的进程调度”与“进程切换”的区别：
狭义的进程调度指的是从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）
2、进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。
3、广义的进程调度包含了选择一个进程和进程切换两个步骤。
4、进程切换的过程主要完成了：
（1）对原来运行进程各种数据的保存。
（2）对新的进程各种数据的恢复。（如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块）
5、进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。
操作系统知识回顾2.7

调度算法的评价指标

操作系统知识总览2.8
一、CPU利用率
1、由于早期的CPU造价极其昂贵，因此人们会希望让CPU尽可能多地工作。
2、CPU利用率：指CPU“忙碌”的时间占总时间的比例。

3、有的题目还会要求计算某种设备的利用率。通常会考察多道程序并发执行的情况，可以用“甘特图”来辅助计算。
二、系统吞吐量
1、对于计算机来说，希望能用尽可能少的时间处理完尽可能多的作业。

三、周转时间
1、对于计算机的用户来说，他很关心自己的作业从提交到完成花了多少时间。
2、周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。
3、它包括四个部分：作业在外存后备队列上等待作业调度（高级调度）的时间、进程在就绪队列上等待进程调度（低级调度）的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。后三项在一个作业的整个过程中，可能发生多次。
(作业)周转时间 = 作业完成时间 - 作业提交时间

对于用户来说，更关心自己的单个作业的周转时间。
对于操作系统来说，更关心系统的整体表现，因此更关心所有作业周转时间的平均值。
4、
对于周转时间相同的两个作业，实际运行时间长的作业在相同时间内被服务的时间更多，带权周转时间更小，用户满意度更高。
对于实际运行时间相同的两个作业，周转时间短的带权周转时间更小，用户满意度更高。
5、带权周转时间必然$\geqslant 1$.因为周转时间包含了作业实际运行的时间。
6、带权周转时间与周转时间都是越小越好。
7、

四、等待时间
1、计算机的用户希望自己的作业尽可能少的等待处理机。
2、等待时间，指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。
1）作业在后备队列等待被服务（调度）
2）作业调入内存后，建立相应的进程。这个进程会被CPU服务、会被I/O设备服务，当然也会有等待被服务的时候。
3、对于$进程$来说，等待时间就是指$进程建立后$等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。（此时I/O设备正在服务进程）
4、对于$作业$来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。
注意区分进程和作业等待时间定义的不同
5、一个作业总共需要被CPU服务多久，被I/O设备服务多久一般是确定不变的，因此调度算法其实只会影响作业/进程的等待时间。当然，与前面指标类似，也有“平均等待时间”来评价整体性能。
五、响应时间
1、对于计算机用户来说，会希望自己提交的请求（比如通过键盘输入了一个调试命令）尽早地开始被系统服务、回应。
2、响应时间，指从用户提交请求到首次产生响应所用的时间。
操作系统知识回顾2.8

调度算法 先来先服务、最短作业优先、最高响应比优先

操作系统知识总览2.9
Tips:各种调度算法的学习思路
1、算法思想
2、算法规则
3、这种调度算法是用于作业调度还是进程调度
4、抢占式？非抢占式？
5、优点和缺点
6、是否会导致饥饿（某进程/作业长期得不到服务）
一、先来先服务（FCFS，First Come First Serve）
1、算法思想：主要从“公平”的角度考虑（类似于我们生活中排队买东西的例子）
2、算法规则：按照作业/进程到达的先后顺序进行服务
3、用于作业/进程调度：用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列。
4、非抢占式算法。
5、先来先服务调度算法：按照到达的先后顺序调度，事实上就是等待时间越久的越优先得到服务。
操作系统先来先服务2.9
6、优缺点
优点：公平，算法实现简单
缺点：排在长作业（进程）后面的短作业需要等待很长时间。带权周转时间很大，对短作业来说用户体验不好。即，FCFS算法对长作业有利，对短作业不利。（Eg：排队买奶茶…）
7、不会导致饥饿。
二、短作业优先（SJF，Shortest Job First）
1、算法思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间。
2、算法规则：最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）。
3、用于作业/进程调度：既可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先（SPF，Shortest Process First）算法”。
4、SJF和SPF是非抢占式的算法。但是也有抢占式的版本—最短剩余时间优先算法（SRTN，Shortest Remaining Time Next）
5、短作业/进程优先调度算法：每次调度时选择当前已到达且运行时间最短的作业/进程。
操作系统短作业优先2.9
6、抢占式的短作业优先算法又称最短剩余时间优先算法（SRTN）：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度。
操作系统最短剩余时间优先2.9
操作系统短作业优先二2.9
7、如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的。
8、很多书上都会说“SJF调度算法的平均等待时间、平均周转时间最少”
严格来说，这个表述是错误的，不严谨的。之前的例子表明，最短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少。
应该加上一个条件“在所有进程同时可运行时，采用SJF调度算法的平均等待时间、平均周转时间最少”
或者说“在所有进程几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少”；
如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法（最短剩余时间优先，SRTN算法）的平均等待时间、平均周转时间最少”。
9、虽然严格来说，SJF的平均等待时间、平均周转时间不一定最少，但相比于其他算法（如FCFS），SJF依然可以获得较少的平均等待时间、平均周转时间。
10、如果选择题中遇到“SJF算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是又很明显的错误，如果没有更合适的选项，那也应该选择该选项。
11、优缺点
优点：“最短的”平均等待时间、平均周转时间
缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先。
12、会导致饥饿。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称为“饿死”。
13、对FCFS和SJF两种算法地思考…
FCFS算法是在每次服务地时候选择一个等待时间最长地作业（进程）为其服务。但是没有考虑到作业地运行时间，因此导致了对短作业不友好地问题。
SJF算法是选择一个执行时间最短的作业为其服务。但是又完全不考虑各个作业的等待时间，因此导致了对长作业不友好的问题，甚至还会造成饥饿问题。
设计一个算法，既考虑到各个作业的等待时间，也能兼顾运行时间。
三、高响应比优先算法（HRRN，Highest Response Ratio Next）
1、算法思想：要综合考虑作业/进程的等待时间和要求服务的时间
2、算法规则：在每次调度时先计算各个作业/进程的响应比，选择相应比最高的作业/进程为其服务

响应比$\geqslant 1$
3、用于作业/进程调度:既可用于作业调度，也可用于进程调度
4、非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比。
5、高响应比优先算法：非抢占式的调度算法，只有当前运行的进程主动放弃CPU时（正常/异常完成，或主动阻塞），才需要进行调度，调度时计算所有就绪进程的响应比，选响应比最高的进程上处理机。
操作系统高响应比优先2.9
6、优缺点
1）综合考虑了等待时间和运行时间（要求服务时间）
2）等待时间相同时，要求服务时间短的优先（SJF的优点）
3）要求服务时间相同时，等待时间长的优先（FCFS的优点）
4）对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿问题。
7、不会导致饥饿。
操作系统知识回顾2.9

调度算法 时间片轮转 优先级调度 多级反馈队列

操作系统知识总览2.10
Tips:各种调度算法的学习思路
1、算法思想
2、算法规则
3、这种调度算法是用于作业调度还是进程调度
4、抢占式？非抢占式？
5、优点和缺点
6、是否会导致饥饿（某进程/作业长期得不到服务）
一、时间片轮转（RR，Round-Robin）
1、算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。
2、算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
3、用于进程/作业调度：用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）。
4、抢占式算法。若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到。
5、时间片轮转调度算法常用于分时操作系统，更注重“响应时间”，因而此处不计算周转时间。
6、时间片轮转调度算法：轮流让就绪队列中的进程依次执行一个时间片（每次选择的都是排在就绪队列对头的进程）
7、注意，2时刻，P1下处理机，同一时刻新进程P2到达，如果在题目中遇到这种情况，默认新到达的进程先进入就绪队列。
8、若P1进程已经处理完成但时间片还没用完，P1会主动放弃处理机。
9、如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。
另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。
一般来说，设计时间片要让切换进程的开销占比不超过1%。
10、优缺点
优点：公平、响应快，适用于分时操作系统。
缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度。
11、不会导致饥饿。
二、优先级调度算法
1、算法思想：随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。
2、算法规则：每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程。
3、既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的I/O调度中。
4、抢占式、非抢占式都有。做题时的区别在于：非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。
5、就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置。
6、根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。
静态优先级：创建进程时确定，之后一直不变。
动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。
7、通常：系统进程优先级高于用户进程。
前台进程优先级高于后台进程。
操作系统更偏好I/O型进程。（或称I/O繁忙型进程）I/O设备和CPU可以并行工作。如果优先让I/O繁忙型进程优先运行的话，则越有可能让I/O设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升。
注：与I/O型进程相对的是计算型进程（或称CPU繁忙型进程）
8、动态优先级的调整策略：
可以从追求公平、提升资源利用率等角度考虑。
如果某进程在就绪队列中等待了很长时间，则可以适当提高其优先级。
如果某进程占用处理机运行了很长时间，则可适当降低其优先级。
如果发现一个进程频繁地进行I/O操作，则可适当提升其优先级。
9、优缺点：
优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程地偏好程度。
缺点：若源源不断地有高优先级进程到来，则可能导致饥饿。
10、会导致饥饿。
三、多级反馈队列调度算法
1、算法思量：对其他调度算法地折中权衡。
2、算法规则：
1）设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
2）新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级地队列，则重新放回该队列队尾。
3）只有第k级队列为空时，才会为k+1级队头地进程分配时间片。
3、用于进程调度。
4、抢占式的算法。在k级队列的进程运行过程中，若更上级的队列（1到k-
1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列（本级队列）队尾。
5、优缺点：
优点：对各种类型进程相对公平（FCFS的优先）；每个新到达的进程都可以很快就得到响应（RR的优点）；短进程只用较少的时间就可完成（SPF的优点）；不必实现估计进程的运行时间（避免用户作假）；可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程（拓展：可以将因I/O而阻塞的进程重新放回原队列，这样I/O进程就可以保持较高优先级）
6、会导致饥饿。
操作系统知识回顾2.10
注：比起早期的批处理操作系统来说，由于计算机造假大幅度降低，因此之后出现的交互式操作系统（包括分时操作系统、实时操作系统等）更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。（比如UNIX使用的就是多级反馈队列调度算法）

进程同步 进程互斥

操作系统知识总览2.11
一、进程同步
1、知识点回顾：进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。
2、在管道通信中，读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行地先后顺序是不确定地。而实际应用中，又必须按照“写数据->读数据”的顺序来执行。如何解决这种异步问题，就是“进程同步”所讨论的内容。
3、同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。
二、进程互斥
1、进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免地需要共享一些系统资源（比如内存，又比如打印机、摄像头这样的I/O设备）
2、我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。
3、对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。互斥进程指当一个进程访问临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。
4、对于临界资源的互斥访问，可以在逻辑上分为如下四个部分：

1
2
3
4
5
6
do{
    entry section;//进入区
    critical section;//临界区
    exit section;//退出区
    remainder section;//剩余区
}while(true)

1)进入区：负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志（可理解为“上锁”），以阻止其他进程同时进入临界区。
2）临界区：访问临界资源的那段代码。
3）退出区：负责解除正在访问临界资源的标志（可理解为“解锁”）。
4）剩余区：做其他处理。
5、临界区是进程中访问临界资源的代码段。
6、进入区和退出区是负责实现互斥的代码段。
7、临界区也可称为“临界段”。
8、为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：
1）空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
2）忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
3）有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）。
4）让权等待。当进程不能进入临界区，应立即释放处理机，防止进程忙等待。
操作系统知识回顾2.11

进程互斥的软件实现方法

操作系统知识总览2.12
学习提示：
1、理解各个算法的思想、原理。
2、结合上小节学习的“实现互斥的四个逻辑部分”，重点理解各算法在进入区、退出区都做了什么。
3、分析各算法存在的缺陷（结合“实现互斥要遵循的四个原则”进行分析）
二、单标志法
1、算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

1
2
3
4
5
6
7
8
9
10
11
12
13
int turn = 0;//turn 表示当前允许进入临界区的进程号

P0进程：
while(turn !=0);(1)
critical section;(2)
turn = 1;(3)
remainder section;(4)

P1进程：
while(turn !=1);(5)//进入区
critical section;(6)//临界区
turn = 0;(7)//退出区
remainder section;(8)//剩余区

2、turn 的初值为0，即刚开始只允许0号进程进入临界区。
3、若P1先上处理机运行，则会一直卡在(5)。直到P1的时间片用完，发生调度，切换P0上处理机运行。代码(1)不会卡住P0，P0可以正常访问临界区，在P0访问临界区期间即使切换回P1，P1依然会卡在(5)。
4、只有P0在退出区将turn改为1后，P1才能进入临界区。
5、因此，该算法可以实现“同一时刻最多只允许一个进程访问临界区”。
6、turn 表示当前允许进入临界区的进程号，而只有当前允许进入临界区的进程访问了临界区之后，才会修改turn的值。也就是说，对于临界区的访问，一定是按P0->P1->P0->P1->……这样轮流访问。
7、这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是P0，而P0一直不访问临界区，那么虽然此时临界区空闲，但并不允许P1访问。
8、因此，单标志法存在的主要问题是：违背“空闲让进”原则。
二、双标志先检查法
1、算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0] = true”意味着0号进程P0现在想要进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool flag[2];//表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false;//刚开始设置为两个进程都不想进入临界区

P0进程：
while(flag[1]);(1)
flag[0] = true;(2)
critical section;(3)
flag[0] = false;(4)
remainder section;

P1进程：
while(flag[0]);(5)//如果此时P0想进入临界区，P1就一直循环等待
flag[1] = true;(6)//标记为P1进程想要进入临界区
critical section;(7)//访问临界区
flag[1] = false;(8)//访问完临界区，修改标记为P1不想使用临界区
critical section;

2、若按照(1)(5)(2)(6)(3)(7)….的顺序执行，P0和P1将会同时访问临界区。
3、因此，双标志先检查法的主要问题是：违反“忙则等待”原则。
4、原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。
三、双标志后检查法
1、算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool flag[2];//表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false;//刚开始设置为两个进程都不想进入临界区

P0进程：
flag[0] = true;(1)
while(flag[1]);(2)
critical section;(3)
flag[0] = false;(4)
remainder section;

P1进程：
flag[1] = true;(5)//标记为P1进程想要进入临界区
while(flag[0]);(6)//如果此时P0想进入临界区，P1就一直循环等待
critical section;(7)//访问临界区
flag[1] = false;(8)//访问完临界区，修改标记为P1不想使用临界区
critical section;

2、若按照(1)(5)(2)(6)….的顺序执行，P0和P1将都无法进入临界区。
3、因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。
4、两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。
四、Peterson算法
1、算法思想：双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。Gary L.Peterson想到了一种方法，如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”，主动让对方先使用临界区。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool flag[2];//表示进入临界区意愿的数组，初始值都是false
int turn = 0;//turn 表示优先让哪个进程进入临界区

P0进程：
flag[0] = true;(1)
turn = 1;(2)
while(flag[1] && turn == 1);(3)
critical section;(4)
flag[0] = false;(5)
remainder section;

P1进程：
flag[1] = true;(6)//表示自己想进入临界区
turn = 0;(7)//可以优先让对方进入临界区
while(flag[0] && turn == 0);(8)//对方想进，且最后一次是自己“让梨”(turn == 0)，那自己就循环等待
critical section;(9)
flag[1] = false;(10)//访问完临界区，表示自己已经不想访问临界区了
remainder section;

2、进入区：
1）主动争取；
2）主动谦让；
3）检查对方是否也想使用，且最后一次是不是自己说了“客气话”
3、Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是仍然未遵循让权等待的原则。
操作系统知识回顾2.12

进程互斥的硬件实现方法

操作系统知识总览2.13
学习提示：
1、了解各方法的原理。
2、了解各方法的优缺点。
一、中断屏蔽方法
1、利用“开/关中断指令”实现(与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)

1
2
3
关中断;//关中断后即不允许当前进程被中断，也必然不会发生进程切换
临界区;
开中断;//直到当前进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机并访问临界区

2、优点：简单
缺点：不适用于多处理机（只能限制当前处理机进程的切换）；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）
二、TestAndSet指令
1、简称TS指令，也有地方称为TestAndSetLock指令，或TSL指令。
2、TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//布尔型共享变量lock表示当前临界区是否被加锁
//true 表示已加锁，false表示未加锁
bool TestAndSet(bool *lock){
    bool old;
    old = *lock;//old用来存放lock原来的值
    *lock = true;//无论之前是否已加锁，都将lock设为true
    return old;//返回lock原来的值
}

//以下是使用TSL指令实现互斥的算法逻辑
while(TestAndSet(&lock));//“上锁”并“检查”
临界区代码段...
lock = false;//“解锁”
剩余区代码段...

3、若刚开始lock是false，则TSL返回的old值为false，while循环条件不满足，直接跳过循环，进入临界区。若刚开始lock是true，则执行TSL后old返回的值为true，while循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。
4、相比软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
5、优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境。
6、缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。
三、Swap指令
1、有的地方也叫Exchange指令，或简称XCHG指令。
2、Swap指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//Swap指令的作用是交换两个变量的值
Swap(bool *a,bool *b){
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

//以下是用Swap指令实现互斥的算法逻辑
//lock表示当前临界区是否被加锁
bool old = true;
while(old == true){
    Swap(&lock,&old);
}
临界区代码段...
lock = false;
剩余区代码段...

3、逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在old变量上），再将上锁标记lock设置为true，最后检查old，如果old为false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。
4、优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境。
5、缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。
操作系统知识回顾2.13

信号量机制

操作系统知识总览2.14
一、信号量机制
1、用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。
2、信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。
3、原语是一种特殊的程序段，其执行只能一气呵成，不可能被中断。原语是由于关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。
4、一对原语：wait（S）原语和signal（S）原语，可以把原语理解成为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S其实就是函数调用时传入的一个参数。
5、wait、signal原语常简称为P、V操作（来自荷兰语proberen:尝试和verhogen:增加）。因此，做题的时候常把wait（S）、signal（S）两个操作分别写为P（S）、V（S）。
二、信号量机制—整型信号量
1、用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。与普通整数变量的区别：对信号量的操作只有三种，即初始化、P操作、V操作。
2、Eg：某计算机系统中有一个打印机…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int S = 1;//初始化整型信号量S，表示当前系统中可用的打印机资源数

void wait(int S){//wait原语，相当于“进入区”
    while(S <= 0);//如果资源数不够，就一直循环等待
    S = S - 1;//如果资源数够，则占用一个资源
}

void signal(int S){//signal原语，相当于“退出区”
    S = S + 1;//使用完资源后，在退出区释放资源
}

进程P0：
wait(&S);//进入区，申请资源
使用打印机资源...//临界区，访问资源
signal(&S);//退出区，释放资源

3、“检查”和“上锁”一气呵成，避免了并发、异步导致的问题。
4、存在的问题：不满足“让权等待”原则，会发生“忙等”。
三、信号量机制—记录型信号量
1、整型信号量的缺陷时存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//记录型信号量的定义
typedef struct{
    int value;//剩余资源数
    struct process *L;//等待队列
}semaphore;

//某进程需要使用资源时，通过wait原语申请
void wait(semaphore S){
    S.value--;
    if(S.value < 0){
        block(S.L);
        //如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态，并把它挂到信号量S的等待队列（即阻塞队列）中。
    }
}

//进程使用完资源后，通过signal原语释放
void signal(semaphore S){
    S.value++;
    if(S.value <= 0){
        wakeup(S.L);
        //释放资源后，若还有别的进程在等待这种资源，则使用wakeup原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态。
    }
}

2、在考研题目中wait（S）、signal（S）也可以记为P（S）、V（S），这对原语可用于实现系统资源的“申请”和“释放”。
3、S.value的初值表示系统中某种资源的数目。
3、对信号量S的一次P操作意味着进程请求一个单位的该类资源，因此需要执行S.value—,表示资源数减1，当S.value<0时表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞（当前运行的进程从运行态->阻塞态），主动放弃处理机，并插入该类资源的等待队列S.L中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。
4、对信号量S的一次V操作意味着进程释放一个单位的该类资源，因此需要执行S.value++,表示资源数加1，若加1后仍是S.value<=0,表示依然有进程在等待该类资源，因此应调用wakeup原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态->就绪态）。
操作系统知识回顾2.14
5、若考试中出现P（S）、V（S）的操作，除非特别说明，否则默认S为记录型信号量。

用信号量机制实现进程互斥、同步、前驱关系

操作系统知识总览2.15
一、信号量机制实现进程互斥
1、分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）
2、设置互斥信号量mutex，初值为1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//信号量机制实现互斥
semaphore mutex = 1;//初始化信号量
//要会自己定义记录型信号量，但如果题目中没有特别说明，可以把信号量的声明简写成这种形式。

P1(){
    ...
    P(mutex);//使用临界资源前需要加锁
    临界区代码段...
    V(mutex);//使用临界区资源后需要解锁
    ...
}

P2(){
    ...
    P(mutex);
    临界区代码段...
    V(mutex);
    ...
}

3、在临界区之前执行P(mutex)。
4、在临界区之后执行V(mutex)。
5、对不同的临界资源需要设置不同的互斥信号量。
6、P、V操作必须成对出现。缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永远不被释放，等待进程永远不会被唤醒。
二、信号量机制实现进程同步
若P2的“代码4”要基于P1的“代码1”和“代码2”的运行结果才能执行，那么我们就必须保证“代码4”一定是在“代码2”之后才会执行。这就是进程同步问题，让本来异步并发的进程互相配合，有序推进。
用信号量实现进程同步：
1、分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
2、设置同步信号量S，初始为0。

1
2
//信号量机制实现同步
semaphore S = 0;//初始化同步信号量，初始化值为0

3、在“前操作”之后执行V（S）。
4、在“后操作”之前执行P（S）。P是申请资源的那个操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
P1(){
    代码1;
    代码2;
    V(S);
    代码3;
}

P2(){
    P(S);
    代码4;
    代码5;
    代码6;
}

若先执行到V(S)操作，则S++后S = 1。之后当执行到P(S)操作时，由于S = 1，表示有可用资源，会执行S—，S的值变回0，P2进程不会执行block原语，而是继续往下执行代码4。
若先执行到P(S)操作，由于S = 0，S—后S = -1，表示此时没有可用资源，因此P操作中会执行block原语，主动请求阻塞。之后执行完代码２，继而执行V(S)操作，S++，使S变回0，由于此时有进程在该信号量对应的阻塞队列中，因此会在V操作中执行wakeup原语，唤醒P2进程。这样P2就可以继续执行代码4了。
三、信号量机制实现前驱关系
其实每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作），因此：
1、要为每一对前驱关系各设置一个同步变量。
2、在“前操作”之后对相应的同步变量执行V操作。
3、在“后操作”之前对相应的同步变量执行P操作。
操作系统知识回顾2.15

生产者消费者问题

一、问题描述
1、系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）。
2、生产者、消费者共享一个初始为空，大小为n（若n = 5）的缓冲区。
操作系统问题描述2.16
3、只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
4、只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。
5、缓冲区是临界资源，各进程必须互斥地访问。
6、信号量机制可实现：
互斥：设置初值为1的互斥信号量。
同步：设置初值为0的同步信号量，实现“一前一后”。
对一类系统资源的申请和释放：设置一个信号量，初始值即为资源的数量。本质上也属于“同步问题”，若无空闲资源，则申请资源的进程需要等待别的进程释放资源后才能继续往下执行。
7、PV操作题目分析步骤：
1）关系分析。找出题目描述的各个进程，分析它们之间的同步、互斥关系。
生产者每次要消耗（P）一个空闲缓冲区，并生产（V）一个产品。消费者每次要消耗（P）一个产品，并释放（V）一个空闲缓冲区。往缓冲区放入/取走产品需要互斥。
2）整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
3）设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）

1
2
3
semaphore mutex = 1;//互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;//同步信号量，表示空闲缓冲区的数量
semaphore full = 0;//同步信号量，表示产品的数量，也即非空缓冲区的数量

二、如何实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
producer(){
    while(1){
        生产一个产品;
        P(empty);//消耗一个空闲缓冲区
        P(mutex);//实现互斥是在同一进程中进行一对PV操作
        把产品放入缓冲区;
        V(mutex);
        V(full);//增加一个产品
        //实现两进程的同步关系，是在其中一个进程中执行P，另一进程中执行V
    }
}

consumer(){
    while(1){
        P(full);//消耗一个产品（非空缓冲区）
        P(mutex);
        从缓冲区取出一个产品;
        V(mutex);
        V(empty);//增加一个空闲缓冲区
        使用产品;
    }
}

操作系统如何实现2.16

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
producer(){
    while(1){
        生产一个产品;
        P(mutex);(1)//mutex的P操作在P(empty)之前
        P(empty);(2)
        把产品放入缓冲区;
        V(mutex);
        V(full);
    }
}

consumer(){
    while(1){
        P(mutex);(3)
        P(full);(4)
        从缓冲区取出一个产品;
        V(mutex);
        V(empty);//增加一个空闲缓冲区
        使用产品;
    }
}

1、若此时缓冲区内已经放满产品，则empty = 0，full = n。
则生产者进程执行(1)使mutex变为0，再执行(2),由于已没有空闲缓冲区，因此生产者被阻塞。
由于生产者阻塞，因此切换回消费者进程。消费者进程执行(3),由于mutex为0，即生产者还没释放对临界资源的“锁”，因此消费者也被阻塞。
这就造成了生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒，出现“死锁”。
2、同样的，若缓冲区中没有产品，即full = 0，empty = n。按(3)(4)(1)的顺序执行就会发生死锁。
3、因此,实现互斥的P操作一定要在实现同步的P操作之后。
4、V操作不会导致进程阻塞，因此两个V操作顺序可以交换。
三、知识回顾与重要考点
1、生产者消费者问题是一个互斥、同步的综合问题。
2、对于初学者来说最难的是发现题目中隐含的两对同步关系。有时候是消费者需要等待生产者生产，有时候是生产者要等待消费者消费，者是两个不同的“一前一后问题”，因此也需要设置两个同步信号量。
操作系统知识回顾2.16
3、易错点：实现互斥和实现同步的两个P操作的先后顺序。

多生产者-多消费者问题

一、问题分析
操作系统问题分析2.17
二、如何实现

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
semaphore mutex = 1;//实现互斥访问盘子（缓冲区）
semaphore apple = 0;//盘子中有几个苹果
semaphore orange = 0;//盘子中有几个橘子
semaphore plate = 1;//盘子中还可以放多少水果

dad(){
    while(1){
        准备一个苹果;
        P(plate);//检查盘子中是否可以放入水果
        P(mutex);
        把苹果放入盘子;
        V(mutex);
        V(apple);//告诉女儿进程盘子中的苹果数加一了
    }
}

mom(){
    while(1){
        准备一个橘子;
        P(plate);
        P(mutex);
        把橘子放入盘子;
        V(mutex);
        V(orange);
    }
}

daughter(){
    while(1){
        P(apple);//检查盘子中是否已经有自己需要的水果
        P(mutex);
        从盘中取出苹果;
        V(mutex);
        V(plate);//告诉父亲和母亲进程盘子中已经空了
        吃掉苹果;
    }
}

son(){
    while(1){
        P(orange);
        P(mutex);
        从盘中取出橘子;
        V(mutex);
        V(plate);
        吃掉橘子;
    }
}

1、可以不用互斥信号量mutex。同时把上述代码中对mutex的P、V操作全部去掉。根据过程分析即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象。
2、原因在于：本题中的缓冲区大小为1，在任何时刻，apple、orange、plate三个同步信号量中最多只有一个是1.因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区。
3、如果盘子的容量为2的话，父亲在往盘子里放苹果，同时母亲也可以往盘子里放橘子。于是就出现了两个进程同时访问缓冲区的情况，有可能导致两个进程写入缓冲区的数据相互覆盖的情况。
4、因此，如果缓冲区大小大于1，就必须专门设置一个互斥信号量mutex来保证互斥访问缓冲区。
三、知识回顾
1、在生产者-消费者问题中，如果缓冲区大小为1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然，这不是绝对的，要具体问题具体分析。
2、在考试中如果来不及仔细分析，可以加上互斥信号量，保证各进程一定会互斥地访问缓冲区。但需要注意的是，实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起“死锁”。
3、解决“多生产者-多消费者问题”的关键在于理清复杂的同步关系。
在分析同步问题（一前一后问题）的时候不能从单个进程行为的角度来分析，要把“一前一后”发生的事看做是两种“事件”的前后关系。

吸烟者问题

一、问题分析
操作系统问题分析2.18
二、如何实现

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
semaphore offer1 = 0;//桌上组合一的数量
semaphore offer2 = 0;//桌上组合二的数量
semaphore offer3 = 0;//桌上组合三的数量
semaphore finish = 0;//抽烟是否完成
int i = 0;//用于实现“三个抽烟者轮流抽烟”

provider(){
    while(1){
        if(i == 0){
            将组合一放桌上；
            V(offer1);
        }
        else if(i == 1){
            将组合二放桌上；
            V(offer2);
        }
        else if(i == 2){
            将组合三放桌上；
            V(offer3);
        }
        i = (i+3)%3;
        P(finish);
    }
}

smoker1(){
    while(1){
        P(offer1);
        从桌上拿走组合一；卷烟；抽掉；
        V(finish);
    }
}

smoker2(){
    while(1){
        P(offer2);
        从桌上拿走组合二；卷烟；抽掉；
        V(finish);
    }
}

smoker3(){
    while(1){
        P(offer3);
        从桌上拿走组合三；卷烟；抽掉；
        V(finish);
    }
}

1、缓冲区大小为1，同一时刻，四个同步信号量中至多有一个的值为1。
三、知识回顾
1、吸烟者问题可以为我们解决“可以生产多个产品的单生产者”问题提供一个思路。
2、值得吸取的精华是：“轮流让各个吸烟者吸烟”必然需要“轮流的在桌上放组合一、二、三”，注意体会我们是如何用一个整型变量i实现这个“轮流”过程的。

3若一个生产者要生产多种产品（或者说会引发多种前驱事件），那么各个V操作应该放在各自对应的“事件”发生之后的位置。

读者 写者问题

一、问题描述
1、有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：
1）允许多个读者可以同时对文件执行读操作；
2）只允许一个写者往文件中写信息；
3）任一写者在完成写操作之前不允许其他读者或写者工作；
4）写者执行写操作前，应让已有的读者和写者全部退出。
2、与消费者进程不同，读者进程在读数据后并不会将数据清空，并不会改变数据。因此多个读者可同时访问共享数据。
二、问题分析
1、两类进程：写进程、读进程
互斥关系：写进程-写进程、写进程-读进程。读进程与读进程不存在互斥问题。
2、写者进程和任何进程都要互斥，设置一个互斥信号量rw，在写者访问共享文件前后分别执行P、V操作。
3、读者进程和写者进程也要互斥，因此读者访问共享文件前后也要对rw执行P、V操作。
4、如果所有读者进程在访问共享文件之前都执行P(rw)操作，那么会导致各个读进程之间也无法同时访问文件。Key：读者写者问题的核心思想—怎么处理该问题呢？
5、P(rw)和V(rw)其实就是对共享文件的“加锁”和“解锁”。既然各个读进程需要同时访问，而读进程与写进程又必须互斥访问，那么我们可以让第一个访问文件的读进程“加锁”，让最后一个访问完文件的读进程“解锁”。可以设置一个整数变量count来记录当前有几个读进程在访问文件。
三、如何实现

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
33
34
semaphore rw = 1;//用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count = 0;//记录当前有几个读进程在访问文件
semaphore mutex = 1;//用于保证对count变量的互斥访问
semaphore w = 1;//用于实现“写优先”

writer(){
    while(1){
        P(w);
        P(rw);//写之前“加锁”
        写文件...
        V(rw);//写之后“解锁”
        V(w);
    }
}

reader(){
    while(1){
        P(w);
        P(mutex);//各读进程互斥访问count
        if(count == 0){
            P(rw);//第一个读进程负责“加锁”
        }
        count++;//访问文件的读进程数+1
        V(mutex);
        V(w);
        读文件...
        P(mutex);//各读进程互斥访问count
        count--;//访问文件的读进程数-1
        if(count == 0){
            V(rw);//最后一个读进程负责“解锁”
        }
        V(mutex);
    }
}

1、若两个读进程并发执行，则两个读进程有可能先后执行P(rw),从而使第二个读进程阻塞的情况。
如何解决：出现上述问题的原因在于对count变量的检查和赋值无法一气呵成，因此可以设置另一个互斥信号量mutex来保证各读进程对count的访问是互斥的。
2、潜在的问题：只要有读进程还在读，写进程就要一直阻塞等待，可能“饿死”。因此，这种算法中，读进程是优先的。
如何解决：设置一个信号量w用于实现“写优先”。
效果：在有写者进程被阻塞的情况下，不允许有新的读者进程读文件。
3、结论：在这种算法中，连续进入的多个读者可以同时读文件；写者和其他进程不能同时访问文件；写者不会饥饿，但也并不是真正的“写优先”，而是相对公平的先来先服务原则。
有的书上把这种算法称为“读写公平法”。
四、知识回顾与重要考点
1、读者写者问题的核心思想在于设置了一个计数器count用来记录当前正在访问共享文件的读进程数。我们可以用count的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。
2、另外，对count变量的检查和赋值不能一气呵成导致了一些错误，但如果需要实现“一气呵成”，自然应该想到利用互斥信号量。
3、绝大多数的考研PV操作大题都可以用之前介绍的几种生产者-消费者问题的思想来解决，如果遇到更复杂的问题，可以想想能否用读者写者问题的这几个思想来解决。

哲学家进餐问题

一、问题描述
操作系统问题描述2.19
二、问题分析

1
2
3
4
5
6
7
8
9
10
11
semaphore chopstick[5] = {1,1,1,1,1};
Pi(){//i号哲学家的进程
    while(1){
        P(chopstick[i]);//拿左
        P(chopstick[(i+1)%5]);//拿右
        吃饭...
        V(chopstick[i]);//放左
        V(chopstick[(i+1)%5]);//放右
        思考...
    }
}

1、每位哲学家拿起自己面前的一只筷子，每位哲学家循环等待右边的人放下筷子（阻塞）。发生死锁
三、如何实现
1、如何防止死锁的发生呢？
1）可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。
2）要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么就只会有其中一个可以拿起第一只筷子，另一个会直接阻塞，这就避免了占有一支后再等待另一只的情况。
3)仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。更准确的说法应该是：各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1;//互斥地取筷子
Pi(){//i号哲学家的进程
    while(1){
        P(mutex);
        P(chopstick[i]);//拿左
        P(chopstick[(i+1)%5]);//拿右
        V(mutex);
        吃饭...
        V(chopstick[i])//放左
        V(chopstick[(i+1)%5]);//放右
        思考...
    }
}

四、知识回顾与重要考点
1、哲学家进餐问题的关键在于解决死锁。
2、这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。
3、如果在考试中遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。

管程

操作系统知识总览2.20
一、管程的定义和基本特征
1、管程是一种特殊的软件模块，由这些部分组成
1）局部于管程的共享数据结构说明；
2）对该数据结构进行操作的一组过程；（函数）
3）对局部于管程的共享数据设置初始值的语句；
4）管程有一个名字。
2、管程的基本特征：
1）局部于管程的数据只能被局部于管程的过程所访问。
2）一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
3）每次仅允许一个进程在管程内执行某个内部过程。
二、用管程解决生产者消费者问题

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
33
34
35
36
37
38
39
40
monitor ProducerConsumer
condition full,empty;//条件变量用来实现同步（排队）
int count = 0;//缓冲区中的产品数
void insert(Item item){//把产品item放入缓冲区
    if(count == N){
        wait(full);
    }
    count++;
    insert_item(item);
    if(count == 1){
        signal(empty);
    }
}
Item remove(){//从缓冲区中取出一个产品
    if(count == 0){
        wait(empty);
    }
    count--;
    if(count == N-1){
        signal(full);
    }
    return remove_item();
}
end monitor;

//生产者进程
producer(){
    while(1){
        item = 生产一个产品;
        ProdecerConsumer.insert(item);
    }
}

//消费者进程
consumer(){
    while(1){
        item = ProdecerConsumer.remove();
        消费产品item;
    }
}

1、item-由编译器负责实现各进程互斥地进入管程中的过程。每次仅允许一个进程在管程内执行某个内部过程。例如两个生产者进程并发执行，依次调用了insert过程……
2、管程中设置条件变量和等待/唤醒操作，以解决同步问题。
3、引入管程的目的无非就是要更方便地实现进程互斥和同步。
4、需要在管程中定义共享数据（如生产者消费者问题地缓冲区）。
5、需要在管程中定义用于访问这些共享数据地”入口“—其实就是一些函数（如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品）。
6、只有通过这些特定的“入口”才能访问共享数据。
7、管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入（如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意：这种互斥特性是由编译器负责实现的，程序员不用关心）。
8、可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出“入口”）；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。
9、程序员可以用某种特殊的语法定义一个管程（比如：monitor ProducerConsumer……end monitor），之后其他程序员就可以使用这个管程提供的特定“入口”很方便地实现进程同步/互斥了。
三、Java中类似于管程的机制
1、Java中，如果用关键字synchronized来描述一个函数，那么这个函数同一时间段内只能被一个线程调用

1
2
3
4
5
6
7
8
9
static class monitor{
    private Item buffer[] = new Item[N];
    private int count = 0;

    public synchronized void insert(Item item){
        //每次只能有一个线程进入insert函数，如果多个线程同时调用insert函数，则后来者需要排队等待
        ......
    }
}

操作系统知识回顾2.20

死锁的概念

操作系统知识总览2.21
一、什么是死锁
1、每位哲学家都在等待自己右边的人放下筷子，这些哲学家进程都因等待筷子资源而被阻塞。即发生“死锁”。
2、每个人都占有一个资源，同时又在等待另一个人手里的资源。发生“死锁”。
3、在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。发生死锁后若无外力干涉，这些进程都将无法向前推进。
二、死锁、饥饿、死循环的区别
1、死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
2、饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：短进程优先（SPF）算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。
3、死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的。
操作系统死锁饥饿死循环2.21
三、死锁产生的必要条件
产生死锁必须同时满足以下四个条件，只要其中任一条件不成立，死锁就不会发生。
1、互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。
2、不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
3、请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
4、循环等待条件：存在一种进程资源的循环等待链，链中的每个进程已获得的资源同时被下一个进程所请求。
5、注意：发生死锁时一定有循环等待，但是发生循环等待时未必死锁。（循环等待是死锁的必要不充分条件）
6、如果同类资源数大于1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。
四、什么时候会发生死锁
1、对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争是不会引起死锁的。
2、进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
3、信号量使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能造成死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系统资源）
4、总之，对不可剥夺资源的不合理分配，可能导致死锁。
五、死锁的处理策略
1、预防死锁。破坏死锁产生的四个必要条件中的一个或几个。
2、避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）。
3、死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。
操作系统知识回顾2.21

死锁的处理策略-预防死锁

操作系统知识总览2.22
一、破坏互斥条件
1、互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。
2、如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如：SPOOLing技术。
3、操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备。比如，用SPOOling技术将打印机改造为共享设备…
4、该策略的缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。
二、破坏不剥夺条件
1、不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
2、方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
3、方案二：当某个进程需要的资源被其他进程占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）
4、该策略的缺点：
1）实现起来比较复杂。
2）释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
3）反复地申请和释放资源会增加系统开销，降低系统吞吐量。
4）若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源都需要放弃，以后再重新申请。如果一直发生这种情况，就会导致进程饥饿。
三、破坏请求和保持条件
1、请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
2、可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源一直归它所有，该进程就不会再请求别的任何资源了。
3、该策略实现起来简单，但也有明显的缺点：
有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。
四、破坏循环等待条件
1、循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
2、可采用顺序分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。
3、原理分析：一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号资源，从而就不会产生循环等待的现象。
4、在任何一个时刻，总有一个进程拥有的资源编号是最大的，那这个进程申请之后的资源必然畅通无阻。因此，不可能出现所有进程都阻塞的死锁现象。
5、该策略的缺点：
1）不方便增加新的设备，因为可能需要重新分配所有的编号。
2）进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费。
3）必须按照规定次序申请资源，用户编程麻烦。
操作系统知识回顾2.22

死锁的处理策略-避免死锁

操作系统知识总览2.23
一、安全序列、不安全状态、死锁的联系
1、所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。
2、如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。
3、如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）。
4、因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。
二、银行家算法
1、银行家算法是荷兰学者Dijkstra为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于避免死锁。
2、核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这些请求，让该进程先阻塞等待。
3、将所有进程都加入安全序列中，最终可得一个安全序列。该算法称为安全性算法。可以很方便地用代码实现以上流程，每一轮检查都从编号较小的进程开始检查。实际做题时可以更快速的得到安全序列。
4、假设系统中有n个进程，m种资源。每个进程在运行前先声明对各种资源的最大需求数，则可用一个nm的矩阵（可用二维数组实现）表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵Maz，Max[i,j] = k表示进程Pi最多需要k个资源Rj。同理，系统可以用一个nm的分配矩阵Allocation表示对所有进程的资源分配情况。Max-Allocation = Need矩阵，表示各进程最多还需要多少各类资源。
5、另外还要用一个长度为m的一位数组$Request_i$表示本次申请的各种资源量。
6、可用银行家算法预判本次分配是否会导致系统进入不安全状态：
1）如果$Request_i[j] \leqslant Needi,j$便转向（2）；否则认为出错。因为它所需要的资源数已超过它所宣布的最大值。
2）如果$Request_i[j] \leqslant Availablej$便转向（3）；否则表示尚无足够资源，Pi必须等待。
3）系统试探着把资源分配给进程Pi，并修改相应的数据（并非真的分配，修改数值只是为了做预判）；
Available = Available - $Request_i;$
Allocation[i,j] = Allocation[i,j] + $Request_i[j];$
Need[i,j] = Need[i,j] - $Request_i[j];$
4）操作系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正是分配；否则，恢复相应数据，让进程阻塞等待。
三、知识回顾与重要考点
1、数据结构：
1）长度为m的一维数组Available表示还有多少可用资源；
2）nm矩阵Max表示各进程对资源的最大需求数；
3）nm矩阵Allocation表示已经给进程分配了多少资源；
4）Max - Allocation = Need矩阵表示各进程最多还需要多少资源；
5）用长度为m的一维数组Request表示进程此次申请的各种资源数。
2、银行家算法步骤：
1）检查此次申请是否超过了之前声明的最大需求数。
2）检查此时系统剩余的可用资源数是否还能满足这次请求。
3）试探着分配，更改各种数据结构。
4）用安全性算法检查此次分配是否会导致系统进入不安全状态。
3、安全性算法步骤：
检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。
不断重复上述过程，看最终是否能让所有进程都加入安全序列。
4、系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。

死锁的处理策略-检测和解除

操作系统知识总览2.24
如果系统中既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁。在这种情况下，系统应当提供两个算法：
1）死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁。
2）死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。
一、死锁的检测
1、为了能对系统是否已发生了死锁进行检测，必须：
1）用某种数据结构来保存资源的请求和分配信息。
2）提供一种算法，利用上述信息来检测系统是否已进入死锁状态。
操作系统资源分配图2.24
注意：
一般用矩形表示资源结点，矩形中的小圆代表该类资源的数量。
2、如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。
3、如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。
4、相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程…
5、如果按照上述分析，最终能消除所有边，就称这个图是可完全化简得。此时一定没有发生死锁（相当于能找到一个安全序列）。
6、如果最终不能消除所有边，那么此时就是发生了死锁。
7、最终还连着边得那些进程就是处于死锁状态得进程。
8、死锁检测得算法：
在资源分配图中，找出既不阻塞又不是孤点的进程$P_i$(即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。若所有的连接该进程的边满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源)。消去它所有的请求边和分配边，使之成为孤立的节点。
进程$P_i$所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。若能消去图中所有的边，则称该图是可完全化简的。
9、死锁定理：如果某时刻系统的资源分配图是不可完全化简的，那么此时系统死锁。
二、死锁的解除
1、一旦检测出死锁的发生，就应该立即解除死锁。
注意：并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程。
2、解除死锁的主要方法有：
1）资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
2）撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
3）进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。
操作系统知识回顾2.24