计算机软件技术基础-课件 第6章 处理器管理

第二部分操作系统第5章操作系统概论第6章处理器管理第7章存储器管理第8章设备管理第9章文件管理第6章处理器管理(1)6.1进程的概念

6.2进程的状态和转换

6.3进程的控制

6.4进程的协调

6.5进程间的通信

6.6进程的安全性

6.7线程的概念

6.8作业管理

6.9处理器调度进程管理处理器（CPU）是整个计算机系统中核心的、宝贵的硬件资源。有效地管理CPU、最大限度地提高CPU的利用率，是操作系统最重要的管理任务。采用多道程序设计技术、组织多个作业同时执行解决CPU的调度、分配和回收等问题处理器管理高级处理器管理：作业管理（调度），确定哪个作业进入内存。低级处理器管理：进程管理（调度），哪个作业中的哪个进程将获得CPU。进程，是系统分配资源的独立单位。第6章处理器管理进程管理学习目标:1.掌握：进程定义，临界区概念，进程的状态及其变化，进程的同步与互斥。2.理解：多道程序设计概念，进程的组成，进程管理的基本命令，信号量和P、V

操作及其应用。3.了解：进程间的通信。

单道批处理系统单道运行：每次只调用一个用户作业程序进入内存并运行

6.1进程的概念（概念的引入）1.程序的顺序执行(单道批处理系统)

一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式就称为程序的顺序执行。特点(1)顺序性－－只有前一个操作结束,才能执行后续操作(2)唯一对应性－－程序与执行过程一一对应(3)封闭性－－程序运行时独占全机资源

程序一旦开始执行，其计算结果不受外界的影响。(4)可再现性－－与执行速度无关

程序执行的结果与初始条件有关，而与执行时间无关。多道批处理系统多道程序的思想：在内存中允许同时存放若干道相互独立的程序，并允许它们交替执行，共享系统软硬件资源。特征：(1)资源共享。(2)程序并发执行。用户程序A用户程序B请求盘输入请求带输入启动盘调度B启动带中断处理中断处理调度A调度B监督程序磁带操作磁盘操作结束中断结束中断T6.1进程的概念程序的并发执行(多道批处理系统)特点1)并发性 若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。2)开放性（失去了封闭性） 系统中并发执行的程序，共享资源，程序的执行与外部因素（如执行速度）有关，不再具有封闭性。 注：若一个程序的执行可改变另一个程序的变量，程序执行的结果不仅依赖于程序的初始条件，还依赖于程序执行时的相对速度，在这种情况下就失去了程序的封闭性。例：有两个循环程序A和B，它们共享一个变量N。[程序A]执行N∶=N+1操作；[程序B]执行Print(N)； N:=0；程序A和B以不同的速度运行。结果：

(1)N∶=N+1在Print(N)和N∶=0

之前，此时得到的N值分别为N+1,N+1(输出),0。(2)N∶=N+1在Print(N)和N∶=0

之后，此时得到的N值分别为N(输出),0,1。(3)N∶=N+1在Print(N)和N∶=0

之间，此时得到的N值分别为N(输出),N+1,0。

进程概念的引入-并发执行的特点3)动态性（程序与执行活动不再一一对应）并发程序中的并发活动是动态产生、动态消亡的。程序的并发执行时，可能有多用户共享使用同一个程序，但处理（执行时）的对象却是不同的。在程序顺序执行时，一个程序总是对应一个具体的执行。例如，在多用户环境下，可能同时有多个用户调用C语言的编译程序，这就是典型的一个程序对应多个用户源程序的情况。4)程序并发执行的相互制约间接制约无逻辑关系的用户程序之间竞争使用资源而产生的制约关系使本来并无逻辑关系的程序之间产生了相互制约关系。程序活动的工作状态与环境有密切关系，并发程序具有“执行—暂停—执行”的活动规律。直接制约存在逻辑关系的程序之间相互等待而发生的制约关系顺序执行与并发执行的特征比较顺序执行并发执行

程序顺序执行唯一对应性

程序具有封闭性独享资源具有可再现性间断执行，多个程序各自在“走走停停”中进行动态性

程序失去封闭性共享资源失去其可再现性有直接和间接的相互制约

1.进程的定义

背景：当程序顺序执行时，具有封闭性和可再现性，但为了提高计算机的速度和增强系统的处理能力，广泛采用多道程序设计技术，从而导致程序的并发进行和资源共享。这带来新的特性，即失去封闭性、程序与计算机活动失去一一对应，并使程序并发执行时产生了相互制约的关系。为了更好描述程序的并发活动，引入了“进程”概念。

1.进程的定义进程的定义：

进程是程序在并发环境中的执行过程，是系统进行资源分配和调度的一个独立单位。说明：1）进程最根本的属性是动态性和并发性

2）进程和程序是两个完全不同的概念

3）尚无统一的定义和名称：美国MIT称进程（process）、IBM公司称任务（task）、Univac公司称活动（action）。1.进程的定义进程和程序主的联系和区别联系：程序是构成进程（程序、数据、进程控制块）的组成部分之一。一个进程的运行目标是执行它所对应的程序；如果没有程序，进程就是去了存在意义。区别：程序是静态概念；进程是程序的一次执行过程，是动态概念。

程序

进程静态的概念

动态的概念不能并行活动

独立的运行单位，能并行活动不是一个基本单位

是处理机调度、竟争资源的基本单位一个程序可对应多个进程

一个进程可以执行多个程序段类似于乐曲与乐曲的一次演奏之间的关系。2.进程的特征

动态性：进程是程序在并发系统内的一次执行。进程“由创建而产生，由调度而执行，因得不到资源而暂停执行，由撤消而消亡”

并发性：概念引入的起源

独立性：一个进程是一个相对完整的资源分配单位。每个进程按照各自独立、不可预知的速度执行（异步性）。制约性：进程之间的相互制约（互斥使用资源、必要的同步和通信）结构性：程序+数据+进程控制块（PCB,ProcessControlBlock）3.进程的组成进程的组成：程序、数据集合、进程控制块（PCB）这三部分构成“进程实体”，也称为“进程映象”。

4.进程控制块进程控制块

是进程组成中最关键的部分，它含有进程的描述信息和控制信息，是进程动态特性的集中反映，是系统对进程进行识别和控制的依据。进程创建时建立PCB（唯一的、进程存在标志）。在进程的生命周期内，操作系统（OS）通过对PCB的管理来实现对进程的管理。进程撤消时删除其相应的PCB。4.进程控制块进程控制块包含的内容：(1)进程名：外部标识符(2)标识码（进程号）PID：内部标识符(3)优先数(4)位置信息：存储器中的物理位置(5)状态信息：当前活动状态(6)现场信息：与运行相关的信息（通用寄存器、程序计数器PC、程序状态字PSW等）(7)通信信息(8)占用资源(9)其他信息6.2进程的状态和转换进程的动态性由它的状态和转换体现1、进程的三种基本状态1)运行态(running)：当进程得到处理器控制权时，它的程序正在处理机上运行，该进程所处的状态为运行状态。2)就绪态(ready)：存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到CPU，就可以立即运行，这些进程所处的状态称为就绪状态。3)阻塞态或等待态(blocked/wait)：若一个进程正等待着某一事件发生（如等待输入输出操作的完成）而暂时停止执行。这时，即使给它CPU时间，它也无法执行，则称该进程处于等待状态（又可称为封锁状态或等待状态）。2、进程状态的转换进程三态模型及其状态转换图.就绪—运行.运行—阻塞.运行—就绪.阻塞—就绪2、进程状态的转换a.创建—就绪b.就绪—运行c.运行—阻塞d.运行—就绪e.运行—终止f.阻塞—就绪创建状态退出状态具有五种状态的进程状态转换图（1）就绪->运行处于就绪状态的进程被调度程序选中，分配到CPU后，该进程的状态就由就绪态变成运行态。处于运行态的进程也称作当前进程。此时当前进程的程序在CPU上执行，它真正是活动的。（2）运行->阻塞正在运行的进程因某种条件而未满足而放弃对CPU的占用。这个进程的状态就由运行态变为阻塞态。2、进程状态的转换（3）阻塞->就绪

处于阻塞状态的进程所等待的事件发生了,此时该进程就从阻塞队列中出来,进入到就绪队列中,然后与就绪队列中的其它进程竞争CPU。（4）运行->就绪正在运行的进程如用完了本次分配给它的CPU时间片，它就得从CPU上退下来，暂停运行。该进程的状态就由运行态变为就绪态，以后进程调度程序选中它，它就又可以继续运行了。2、进程状态的转换3.挂起状态某些系统中，为了更好地管理和调度进程及适应系统的功能目标，引入了挂起状态。引入挂起状态的原因（1）负荷调节的需要由于不断地创建进程，系统资源（特别是主存资源）已经不能满足进程运行的要求，此时必须把某些进程挂起（suspend），置于磁盘对换区中，释放其占用的某些资源，起到平滑系统负载的目的；（2）终端用户或父进程的请求可能系统出现某种故障，需要暂时挂起一些进程，以便在故障消除之后，解除挂起并恢复进程的运行；用户在调试程序过程中，可以请求挂起进程，以便进行某种检查或修改。两个新状态：挂起就绪、挂起阻塞原来的就绪状态成为活动就绪原来的阻塞状态称为活动阻塞具有挂起状态的进程状态图图：具有挂起状态的进程状态图活动就绪运行挂起就绪挂起阻塞活动阻塞挂起时间片完被调度激活挂起等待事件事件发生(唤醒)事件发生(唤醒)激活挂起6.3进程的控制进程管理的功能系统中的进程不断地产生和消亡，进程生命周期的动态变化过程由进程管理来控制。通过原语操作实现：进程创建、进程终止、进程阻塞、进程唤醒、进程挂起、进程激活等。1.原语操作

所谓原语（Primitive）操作：是完成系统特定功能的不可分割的过程，它具有原子操作性，其程序段不允许被中断（原语不能并发执行）机器指令的延伸，往往是为完成某些特定的功能而编制的一段系统程序。系统对进程的控制如果不采用原语，会造成状态的不确定性，不能达到进程控制的目的。原语操作也称“原子操作”，即一个操作中的所有动作要么全做，要么全不做。6.3进程的控制2.进程创建（原语）

父进程创建子进程（提交批处理作业、操作系统创建服务进程等）时要调用进程创建原语。进程创建原语的主要操作过程是：(1)申请一个空闲的PCB(ProcessControlBlock),指定进程标识号PID(进程内部名)(2)为新进程分配资源(3)将新进程的PCB初始化（各种参数）(4)将新进程加到就绪队列中6.3进程的控制2.进程创建（原语）实现方法：传统UNIX：父进程使用fork()创建子进程子进程继承父进程的全部资源(相同的存储映像、环境字符串、打开文件)Windows系统：进程使用Win32API的CreateProcess()函数创建进程新老进程之间不存在族系关系操作系统为新进程创建新的地址空间6.3进程的控制3.进程终止（原语） 进程完成特定的工作或出现严重错误之后，操作系统将回收其所占有的地址空间和PCB，即进程终止。进程终止的主要操作过程：(1)从系统的PCB表中找到指定进程的PCB,若它正处于运行态，则立即终止该进程的运行；(2)回收该进程所占用的全部资源；(3)若该进程还有子孙进程，则还要终止其所有子孙进程，回收它们所占用的全部资源；(4)释放被终止进程的PCB，并从原队列中摘走。6.3进程的控制4.进程阻塞（原语）

进程阻塞：进程让出处理器，转而等待一个事件（等待资源、等待I/O操作完成、等待某事件发生等）。进程通常调用阻塞原语来阻塞自己当等待事件完成时，会产生一个中断，激活操作系统，在系统的控制下将被阻塞的进程唤醒进程阻塞过程：(1)立即停止当前进程的执行；(2)将现行进程的CPU现场送到该进程的PCB现场保护区保存起来；(3)把该进程PCB中的现行状态由“运行”

改为“阻塞”，把它插入到具有相同事件的阻塞队列中；(4)转到进程调度程序，重新从就绪队列中挑选一个合适的进程投入运行。6.3进程的控制5.进程唤醒（原语）

被阻塞的进程所等待的事件出现（所需数据到达、等待的I/O操作完成等）时，由另外的与被阻塞进程相关的进程调用唤醒原语，来唤醒被阻塞进程。被阻塞进程不能唤醒自己。唤醒原语执行过程是:(1)把阻塞进程从相应的阻塞队列中摘下；(2)将现行状态改为就绪态，再把该进程插入到就绪队列中；(3)如果被唤醒进程比运行进程有更高的优先级，则设置重新调度标志。6.3进程的控制6.进程挂起（原语） 当出现引起挂起的事件时，系统或进程会利用挂起原语将指定进程或处于等待态的进程挂起。进程挂起原语执行大致过程是:(1)检查要被挂起进程的状态，若处于活动就绪态，就修改为挂起就绪态；若处于活动阻塞态，就修改为挂起阻塞态；(2)被挂起进程PCB的非常驻部分要交换到磁盘对换区；(3)队列操作。6.3进程的控制7.进程激活（原语） 当系统资源（尤其是存储资源）充裕或请求激活指定进程时，系统或相关进程会调用激活原语把指定进程激活。只能由其它进程激活。进程激活原语执行过程大致是:(1)把被挂起进程PCB的非常驻部分调入主存；(2)修改状态：挂起阻塞态改为活动阻塞态，挂起就绪态改为活动就绪态；(3)队列操作。6.3进程的控制作业：习题66.1,6.4,6.5第6章处理器管理（2）6.1进程的概念

6.2进程的状态和转换

6.3进程的控制

6.4进程的协调

6.5进程间的通信

6.6进程的安全性

6.7线程的概念

6.8作业管理

6.9处理器调度进程管理6.4进程的协调

6.4.1进程互斥

6.4.2进程同步

6.4.3信号量和P、V操作6.4进程的协调概述：

在多道程序设计系统中，许多进程可并发执行，但由于资源共享和进程合作，而产生了进程之间的两类相互制约的关系:

互斥关系 同步关系6.4进程的协调(1)互斥关系（竞争关系）:间接制约关系。指进程之间因相互竞争使用系统资源（独占型资源），而产生的制约关系。主要由资源共享引起。表现形式：“进程——资源——进程”。进程间的间接相互作用构成进程互斥。进程互斥(mutualexclusion)：若干进程因相互争夺独占型资源(打印机、共享变量等)而产生的竞争制约关系。资源竞争会引发两个控制问题：死锁(deadlock)

一组进程如果都获得部分资源，还想要得到其他进程所占有的资源，最终所有进程将陷入永远等待的状态。饥饿(starvation)

一个可运行进程由于其它进程总是优先于它，被调度程序无限期的拖延而不能被执行。进程的协调(2)同步关系(协作关系):一个用户作业可以涉及一组并发进程，它们为了完成共同的任务需要分工协作。例：有A、B两个进程，A进程负责从键盘读数据到缓冲区，B进程负责从缓冲区读数据进行计算。要完成取数据并计算的工作，A进程和B进程要协同工作。即B进程只有等待A进程把数据送到缓冲区后才能进行计算。A进程只有等待B进程发出已把缓冲区数据取走的信号之后才能从键盘向缓冲区中送数据，否则就会出现错误。由于每个进程都独立地以不可预知的速度推进，在执行的先后次序上就要有约束，需要相互协作的进程在某些关键点上协调各自的工作。当其中的一个进程到达关键点后，在尚未得到协作进程发来的消息（或信号）之前应阻塞自己，等待协作进程发来消息后方被唤醒继续执行。这种协作进程之间需要排定执行先后次序的协调关系是直接制约关系，称为进程同步。进程的协调(2)同步关系(协作关系):进程同步（synchronization）是指，为完成共同任务的并发进程基于某个条件来协调其活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号（或消息）所产生的相互制约关系。可由资源共享引起，也可由进程合作引起。各个进程的行动时间次序必须满足某种依赖关系。表现形式：“进程——进程”进程间的直接作用构成进程的同步。注：进程互斥关系（逐次使用互斥共享资源）是一种特殊的进程同步关系6.4.1进程互斥1.进程互斥与临界区进程互斥在系统中，许多进程常常需要共享资源，而这些资源往往要求排它地使用，即一次只能为一个进程服务。因此，各进程间互斥使用这些资源，进程间的这种关系是进程的互斥。临界资源和临界区

临界资源（criticalresource）：

一次仅允许一个进程使用的资源称为临界资源。许多物理设备（如打印机、光盘刻录机等）和软件资源（如变量、数据、队列等）都具有这种独占性的特点。

临界区(criticalsection)：（Dijkstra于1965年首次提出） 在进程中访问临界资源的那段代码称为临界区。要注意区分临界资源与临界区。2互斥的概念与要求进程的互斥（临界区、临界资源）系统中，当一个进程先进入临界区使用临界资源时，另一个进程必须等待；当占用临界资源的进程退出临界区后，另一进程才允许访问此临界资源。2互斥的概念与要求互斥进程进入临界区的准则/要求：①空闲让进。 无进程处于临界区时，可允许一个申请进入临界区的进程立即进入自己的临界区。②忙则等待。 任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。③有限等待。 入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。④让权等待。 等待进入临界区的进程，应放弃占用CPU，避免进程出现“忙等”现象。

3.互斥的实现方法1）软件的方法方法一：设置公用整型变量turn，保存进入临界区的进程标识。Dekker’sAlgorithm[Dijkstra65]例如：有两个进程P0和P1，互斥共享某个资源。P0、P1是循环进程，它们执行一个无限循环程序，每次使用该资源一个有限的时间间隔。若turn=0，允许进程P0进入临界区，否则等待。退出临界区时，修改turn为1。P1的算法类似。互斥的实现:软件方法一P0() {…… while(turn!=0)；

CS0；//P0的临界区

turn=1；

……

} turn=0;P1() {…… while(turn!=1)；

CS1;//P1的临界区

turn=0；

……

} 缺点：满足不了“空闲让进”原则3.互斥的实现方法1）软件的方法：方法二：（1981G.L.Peterson提出） 设置全局变量turn，指示允许进入临界区的进程标识。 定义数组flag[]表示进程是否希望进入临界区或是否在临界区执行。若flag[0]=true，表示进程P0希望进入临界区或已经进入临界区。若turn=0，表示进程P0允许进入临界区。互斥的实现:软件方法二P0() {…… flag[0]=true;turn=1;while(flag[1]&&turn==1)；

CS0；//P0的临界区

flag[0]=false；

……

} blooleanflag[2]={false,false};特点：满足“空闲让进”、“忙则等待”原则；P1() {…… flag[1]=true;turn=0;while(flag[0]&&turn==0)；

CS1；//P1的临界区

flag[1]=false；

……

} 互斥的实现方法2）硬件的方法：

（1）中断屏蔽方法当一个进程进入临界区时，通过屏蔽中断来防止其它进程进入临界区。禁用中断->时钟中断或其它均无效->CPU无法切换到其它进程优点：简单、有效，对操作系统自身很有用。缺点：不适合作为通用的互斥机制关中断时间过长会影响性能和系统效率，降低系统对外部中断的响应速度，影响系统处理紧急事件的能力。不适用于多处理器计算机系统。一个处理器关中断，不能阻止进程在其他处理器上执行相同的临界区。损害其他“无辜的”进程，阻止了多个进程并发地进入不同的临界区。互斥的实现方法2）硬件的方法：（2）硬件指令方法使用硬件指令实现进程互斥测试与设置指令TS(TestandSet);交互指令Swap(或Exchange)特点：指令对内存单元内容的操作（包括读和写）是不可分割的（原子性的），即该指令执行结束之前，其他处理器均不允许访问该内存单元。（2）硬件指令方法TS(TestandSetLock)指令把该指令看做函数，它有布尔型参数和返回条件码。TS(&x)返回x的值，并将x值设置为TRUE。其本身不做测试，调用该函数的程序做测试工作，如while(…)。TS指令的处理过程如下(C语言版本)：booleanTS(boolean*x){booleanrv=*x;*x=TRUE;returnrv;}（2）硬件指令方法TS(TestandSet)指令用TS指令管理临界区时，可以把一个临界区与一个布尔型变量s相关联。变量s代表临界资源的状态，把它看成一把锁。s的初值为FALSE，表示没有进程在临界区内，资源可用。系统利用TS指令实现临界区上的上锁和开锁原语操作。P0{…While(TS(&s));CS0;//临界区s=FALSE;…P1{…While(TS(&s));CS1;//临界区s=FALSE;…booleanTS(boolean*x){booleanrv=*x;*x=TRUE;returnrv;}bools=FALSE;（2）硬件指令方法Swap指令 对换指令可以交换两个字节的内容，其处理过程为：voidSwap(boolean*a,boolean*b){ booleantemp=*a; *a=*b; *b=temp;}(在Intelx86中)使用对换指令可以简单有效地实现互斥,方法是:

为每个临界区设置布尔型锁变量lock，当其值为FALSE时表示无进程在临界区内。boollock=FALSE; //初始化Pi{ … booleankey=TRUE; while(key) Swap(&key,&lock); //上锁

CSi;//临界区

Swap(&key,&lock); //开锁

…互斥的实现方法

（2）硬件指令方法优点：(1)适用范围广。硬件方法适用于任何数目的进程，在单处理机和多处理机环境中完全相同。(2)简单。硬件方法的标志设置简单，含义明确，容易验证其正确性。(3)支持多个临界区。在一个进程内有多个临界区时，只需为每个临界区设立一个布尔变量。缺点：进程在等待进入临界区时要耗费处理机时间，不能实现让权等待；由于进入临界区的进程是从等待进程中随机选择的，有的进程可能一直选不上，从而导致饥饿现象。6.4.2进程的同步系统中的各进程可以并发共享资源，从而使系统资源得到充分利用，但是共享资源往往使并发进程产生某种时序上的约束关系。例如:有A、B两个进程，A进程负责从键盘读数据到缓冲区，B进程负责从缓冲区读数据进行计算。要完成取数据并计算的工作，A进程和B进程要协同工作：即B进程只有等待A进程把数据送到缓冲区后才能进行计算。A进程只有等待B进程发出已把缓冲区数据取走的信号之后才能从键盘向缓冲区中送数据，否则就会出现错误。进程同步示意图6.4.2进程的同步进程同步：进程同步是指进程之间一种直接的协同工作关系，这些进程相互合作，共同完成一项任务。进程间的直接相互作用构成进程的同步。进程互斥的实质也是同步，进程互斥可以看成是一种特殊的进程同步。6.4.3信号量（Semaphore）及PV操作1.信号量及PV操作原语实现进程之间互斥关系的方法软件算法太复杂，效率低下；硬件方法虽然简单，但采用了“忙等待”，浪费CPU资源；将测试能否进入临界区的责任推卸给各个竞争的进程，会削弱系统的可靠性，加重用户的编程负担。这些方案只能解决进程互斥却不能解决进程同步问题。信号量和P、V操作1965年，荷兰计算机科学家EdsgerWDijkstra（迪杰斯特拉）提出的同步工具；将交通管制中的信号灯管理方法引入操作系统，让两个或多个进程通过特殊变量展开交互；一个进程在某一关键点上被迫停止执行直至接收到对应的特殊变量值（信号量）；进程通过P、V两个特殊操作来发送和接收信号。6.4.3信号量（Semaphore）及PV操作1.信号量及PV操作原语信号量是一种特殊的变量，表示资源的物理实体（即表示系统中某类资源的数目）。它的表面形式是一个整型变量附加一个队列；仅能被施加3种操作：初始化和2个特殊的原语操作

(1)初始化操作,信号量能初始化为非负的值。

(2)P操作（荷兰语Proberen,尝试减小try）

(3)V操作（荷兰语Vehogen，增加raise/makehigher）数值指针S6.4.3信号量（Semaphore）及PV操作

信号量(S)的数据结构:

为一个值和一个指针，指针指向等待该信号量的下一个进程。数值指针SStructsemaphore{intvalue;point_to_PCBqueue;}信号量及PV操作

设信号量为S，S可以取不同的整数值。信号量的值与相应资源的使用情况有关。当S>=0时，表示当前可用资源的数量；当S<0时，其绝对值表示等待使用该资源的进程个数。

注意:信号量的值仅能由PV操作来改变。

数值（－3）·指针·PCB1·0·信号量·PCB2·PCB3·信号量及PV操作

PV操作既能实现进程互斥，又能实现进程同步。它由P操作原语和V操作原语组成，对信号量进行操作，定义如下：V（S）操作①将信号量S的值加1，即S=S+1；②如果S>0，则该进程继续执行；否则(S≤0)还要释放S信号量队列中第一个等待的进程（阻塞态改为就绪态）。P（S）操作①将信号量S的值减1，即S=S-1；②如果S

0，则该进程继续执行；否则(S<0)该进程置为阻塞状态，排入S信号量的等待队列。VoidP(semaphore*s)//P操作{s->value--;if(s->value<0){/*placethisprocessins->queue*/;/*blockthisprocess*/;asleep(s->queue)}}VoidV(semaphore*s)//V操作{s->value++;if(s->value<=0){/*removeaprocessPfroms->queue*/;/*placeprocessPonreadylist*/;

wakeup(s->queue)}}操作流程见教材信号量及PV操作

说明：信号量S

0时，S表示某类可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；减1后,若S<0，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；加1后,若S

0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态（阻塞状态）的进程，使之能运行下去。2.利用P、V原语实现进程互斥

设有A、B两个进程，竞争使用某一临界资源。利用信号量和PV原语操作可以方便地实现进程间的互斥执行。设mutex为公共互斥信号量。初值为1，取值范围为（1，0，-1）。mutex＝1表示进程A、B都没有进入临界区。mutex＝0表示进程A、B中的一个已经进入临界区。mutex＝-1表示进程中，一个进程已经进入临界区，另一个进程被阻塞，等待前一进入临界区的进程退出并释放资源后唤醒它。2.利用P、V原语实现进程互斥

令mutex初值为1，进程A、B竞争进入临界区的程序可以写成： 进程A 进程B … …

P(mutex)； P(mutex)；

A临界区 B临界区

V(mutex)； V(mutex)；注意：PV操作必须成对出现，先做P进临界区；后做V，出临界区。互斥信号量初值一般为1。3.利用P、V原语实现进程同步设两个信号量S1和S2S1表示缓冲区是否为空（信息是否取走，空闲单元的个数）S1=0,缓冲区不空；S1=1，缓冲区空。S2表示缓冲区是否为满（是否装满信息，非空单元/数据的个数）S2=0，缓冲区不满；S2=1，缓冲区满。赋予初值S1为1，S2为0，程序可写成：进程A P(S1)；把信息送入缓冲区；V(S2)；进程BP(S2)；把信息从缓冲区取走；V(S1)；注意事项：分析进程间的制约关系，确定信号量种类。通过信号量协调进程的执行先后顺序。(当进程需要等待相关协同进程完成某个协作任务时，就可以对初值为0的信号量执行P操作，以使自己在此点阻塞。)信号量初值与资源数量有关，也与PV操作的出现位置有关。同一信号量的P、V操作“成对”出现，但分别在不同的进程代码中。互斥和同步对信号量PV操作方法的差异都是通过对信号量的P、V操作来实现，但策略不同互斥：不同进程对同一信号量进行P、V操作一个进程在成功地对信号量执行了P操作后进入临界区；在退出临界区后，由该进程对信号量执行V操作。同步：进程PA要同步等待PB。由进程PA对信号量进行P操作后，只能由进程PB对同一个信号量进行V操作，从而使PA能够继续执行。若进程PB也要同步等待PA，则要设置另一个信号量。4.生产者—消费者问题“生产者和消费者”问题是一个典型的进程同步的例子计算机系统中的许多问题都可以被归结“生产者和消费者”问题：针对某类资源，一个进程如果产生并释放它，则该进程称作生产者；一个进程如果使用这类资源，则该进程称作消费者；例如:生产者可以是计算进程，消费者是打印进程生产者和消费者可以通过一个缓冲区联系起来。（课本P131）生产者存放产品的单元数不能超过缓冲区的容量N;消费者取出产品的总量不能超过生产者生产产品的总量。4.生产者—消费者问题可设信号量buffers:空闲的缓冲区数目。初值为N。products:已存入缓冲区的产品数目。初值为0。mutex:互斥信号量。初值为1。生产者和消费者问题的一般过程为：生产者在执行P(buffers)之后，只要buffers≥0(还有空闲的缓冲区)，就可将产品送入。消费者在执行P(products)后，只要products≥0(产品还未取完)，就可以从缓冲区中取走产品，并消费之。否则，生产者或消费者进程就被阻塞。为什么需要互斥信号量mutex？缓冲区是个临界资源4.生产者—消费者问题生产者:while(){生产一个产品;P(buffers);

P(mutex);将产品放入缓冲区;V(mutex);V(products);

}消费者:while(){P(products);P(mutex);从缓冲区取出一个产品;V(mutex);

V(buffers)消费一个产品;}思考：两个P操作的次序能否颠倒？颠倒后,可能造成进程死锁！利用信号量和PV操作解题的关键

注意区分1)公用信号量，互斥时使用的信号量（二元信号量）：它仅允许取值为“０”与“１”，用作互斥。它联系着一组并发进程，初值为１，每个进程均可对之施加Ｐ、Ｖ操作。2)私用信号量，一般信号量（资源信号量）：它联系着一组并发进程，但其初值为０，或为某个正整数ｎ，表示资源的数目，主要用于进程同步。步骤：信号量的设置；给信号量赋初值（常用的互斥和同步信号量值的大小）；P、V操作安排的位置

（其中，多个P操作的顺序不能颠倒，V操作的顺序任意）:先执行同步信号量的P操作，再执行互斥信号量的P操作。小结在多道程序设计系统中，许多进程可并发执行，但由于资源共享和进程合作，而产生了进程之间的两类相互制约的关系。进程互斥：指进程之间因相互竞争使用独占型资源，而产生的间接制约关系。“进程——资源——进程”。临界资源、临界区。互斥的实现方法。进程同步：进程之间为完成共同任务而发生的与执行次序、资源共享而产生的直接制约关系。“进程——进程”信号量和P、V操作的定义。利用信号量机制解决进程互斥和进程同步问题的方法。作业：习题66.8,6.9,6.14,6.17第6章处理器管理(3)6.1进程的概念

6.2进程的状态和转换

6.3进程的控制

6.4进程的协调

6.5进程间的通信

6.6进程的安全性

6.7线程的概念

6.8作业管理

6.9处理器调度进程管理6.6进程的安全性背景在多道程序系统中，多个进程并发运行，共享资源，从而提高了资源的利用率。但是若对资源的管理和使用不当，在一定条件下会导致系统发生一种随机性故障――死锁。在一些系统中，比如实时控制系统，系统一旦发生死锁将导致灾难性的后果。主要内容：6.6.1死锁的概念6.6.2产生死锁的必要条件6.6.3死锁的预防6.6.4死锁的避免6.6.5死锁的检测和解除(自学)6.6.1死锁的概念（1）什么叫死锁？ 死锁是多个（两个或两个以上）进程循环等待它方占有的资源，而无限期僵持下去的局面。若无外力作用它们都无法向前推进。说明：陷入死锁状态的进程称为死锁进程，等待它们所占用资源的或者需要它们进行某种合作的其它进程就会相继陷入死锁，最终可能导致整个系统处于瘫痪状态。

产生死锁的原因根本原因是：资源有限且操作不当。(1)竞争资源 当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁；(2)进程推进的顺序不当 进程在运行过程中，请求和释放资源的顺序不当，导致进程的死锁。说明：资源少未必会产生死锁。竞争资源1竞争非剥夺性资源：系统中的可重用资源（处理机、主存、暂存、I/O通道、打印机以及文件、数据库等）可分为：可剥夺性资源：处理机不可剥夺性资源：如打印机。当系统把这类资源分配给进程后，只能在使用完毕后由进程自愿释放，系统不能强行收回。R2已经分配给PA、R1已经分配给PB（互相等待对方释放资源）死锁模型：PA、PB和R1、R2间已经形成一个环路。以致进入死锁状态。R1R2PAPB申请R2已分配给PB申请R1已分配给PA打印机R2磁带机R1PAPB1竞争非剥夺性资源：2.进程推进顺序不当例：PV操作造成的死锁。信号量S1,S2(初值为1)，分别表示资源R1和R2空闲。进程PA：进程PB：

…

…L1:P(S1)

M1:P(S2)L2:P(S2)M2:P(S1)

使用资源R1和R2使用资源R1和R2V(S1)V(S2)V(S2)V(S1)

说明：有可能PA达到L1时进程PB达到M1。信号量S1和S2执行了P操作，其值均为0，当P1和P2继续执行时它们分别在L2和M2上无限期等待。这就造成了死锁。6.6.2产生死锁的四个必要条件（COFFMAN等人1971年总结了）发生死锁的四个必要条件

[ref]COFFMAN,E.G.,ELPHICK,M.J.,andSHOSHANI,A.:"SystemDeadlocks,"ComputingSurveys,vol.3,pp.67-78,June1971.⑴互斥条件:

进程访问的是临界资源，该资源一次只能被一个进程所使用。⑵不可抢占条件:

一个资源仅能被占有它的进程所释放，而不能被其他进程剥夺。⑶部分分配:（占有且申请条件） 一个进程在请求新的资源的同时，保持对某些资源的占有。⑷循环等待条件:

存在一个进程等待的环路链，链中每一个进程占用有着某个(或某些)资源，又在等待链中的另一个进程所占有的资源。6.6.3死锁的预防死锁的预防：保证系统不进入死锁状态的一种策略。根据产生死锁的四个必要条件，只要使用其中之一不能成立，死锁就不会出现。但必要条件1（互斥条件）是由设备的固有特性所决定的，不仅不能改变，相反还应加以保证。因此实际上只有三种方法。打破不可抢占条件打破占有且申请条件打破循环等待条件1.打破不可抢占条件采用的策略：一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，供其它进程使用，待以后需要时再重新申请。实现比较复杂，会降低系统性能反复地申请和释放资源，使进程的执行无限地推迟，延长了周转时间，增加了系统的开销，降低了系统吞吐量。2打破占有且申请条件

实行资源预先分配策略系统要求任一进程必须预先申请它所需的全部资源，而且仅当该进程的全部资源要求能得到满足时，系统才能给予一次性分配，然后启动该进程运行在分配时只要有一种资源不满足，系统就不会给进程分配资源。进程运行期间，不会再请求新的资源，所以，再分配就不会发生。特点：实现困难，一些进程无法预先确定所需全部资源。资源利用率低。进程延迟进行，降低进程的并发性。3.打破循环等待条件

实行资源有序分配有序资源使用法。基本思想：把系统中所有资源类型线性排队，并按递增规则赋予每类资源以唯一的编号（例如输入机＝1，打印机＝2，磁带机＝3，磁盘＝4等等）。进程申请资源时，必须严格按资源编号的递增顺序进行，否则系统不予分配。优点：资源利用率和系统吞吐量与另两种方法相比有较明显的改善。缺点：(1)限制了进程对资源的申请；对所有资源合理编号增加系统开销。(2)增加了进程对资源的占用时间：为了遵循原则，暂不使用的资源也需要提前申请。

6.6.4死锁的避免

死锁的避免与死锁的预防区别在于：

死锁的预防 设法至少破坏产生死锁的四个必要条件（去除不可抢占条件）之一，严格地防止死锁的出现。

死锁的避免 不那么严格地限制产生死锁必要条件的存在，只是在系统运行过程中小心地避免死锁的最终发生。因为即使死锁必要条件成立，也未必一定会发生死锁。死锁避免比死锁预防允许更多的并发。最著名的死锁避免算法是银行家算法(Dijkstra提出)。银行家算法银行家算法(避免死锁的调度方法)，EdsgerW.Dijkstra于1965年提出。假定小镇银行家拥有资金，数量为Σ，被N个客户共享，银行家对客户提出下列约束：每个客户必须预先说明所要的最大资金量；每个客户每次提出部分资金量的申请并获得分配；如果银行满足客户对资金的最大需求量，客户在资金运作后，应在有限时间内全部归还银行。只要客户遵守上述约束条件，银行家将保证做到：若一个客户所要的最大资金量不超过Σ，银行一定会接纳此客户，并满足其资金要求银行在收到一个客户的资金请求时，可能会因为资金不足而让客户等待，但能在有限时间内满足。资金——资源；客户——进程。银行家算法分配资源时，申请者要把同类资源的最大需求量告诉系统，若系统现存的可用资源数能满足申请者剩余需求量，就满足当前的部分/全部申请，否则推迟分配。目的：这样至少保证有一个申请者能得到所需的全部资源，可执行到结束，然后释放资源供别的申请者使用。若系统保证申请者在有限的时间内能获得所需的全部资源，则称系统处于安全状态；否则为不安全状态，有可能引起死锁。安全状态：指系统中的所有进程能按照某种次序{P1，P2，…，Pn}分配资源，并且依次运行完毕。安全序列{P1，P2，…，Pn}：对于每一个进程Pi(i=1,…,n)，它需要的附加资源（完成执行尚需要的资源数量）不超过系统中当前剩余资源与所有进程Pj(j<i)当前占有资源数量之和。不安全状态：在某个时刻系统中不存在一个安全序列。该算法对于进程的每一个资源申请加以动态检查。分配资源后，若系统进入不安全状态，则不予分配；若分配后，系统仍处于安全状态，则分配资源。安全状态和安全序列说明：只要系统处于安全状态，系统便可避免进入死锁状态；不安全状态可能会导致死锁，但不一定导致死锁进程运行过程中可能会主动释放一些资源，使系统重新回到安全状态；避免死锁的实质是如何使系统不进入不安全状态（预测可能发生死锁，并不能预测一定发生死锁）。安全状态的例子例：假定系统有三个进程P1、P2、P3，共有12个资源。进程P1总共要求10个资源，P2和P3分别要求4个资源和9个资源。设在T0时刻，进程P1、P2和P3已经获得5个资源、2个资源和2个资源，还有3个资源空闲没有分配。T0时刻系统时安全的。这时存在一个安全序列<P2，P1，P3>527进程最大需求已分配尚需P1105P2P34229系统剩余资源3

不安全状态的例子例：若进程P3提出再申请1个资源的要求，系统从剩余的资源中分配1个给P3后剩余2个资源。新的系统状态如下表所示：此时，找不到安全序列，系统已经从安全状态转到了不安全状态。进程最大需求已分配尚需P11055P2P3423926系统剩余资源2银行家算法是在能确保系统处于安全状态时才把资源分配给申请者。6.6.4死锁的避免死锁避免策略主要是根据系统是否处于安全状态，来决定分配资源与否。与死锁预防策略相比，死锁避免策略提高了资源利用率，但增加了系统开销。6.6.5死锁的检测和解除(自学)背景：死锁预防与死锁避免的方法比较保守，它们以牺牲系统效率和浪费资源为代价，与操作系统的设计目标相违背。死锁的检测和解除：系统为进程分配资源时不加以任何限制，即允许死锁发生；但操作系统不断监督进程的进展路径，判断系统是否发生死锁；若检测到死锁发生，则设法以最小的代价加以解除，使系统恢复正常。小结（1）死锁的概念死锁是两个或两个以上的进程中的每一个都在等待其中另一个进程释放资源而被封锁，它们都无法向前推进，称这种现象为死锁现象。

产生死锁的原因是共享资源有限；多个进程对共享资源的竞争，而且操作不当。

（2）产生死锁的四个必要条件互斥条件不可抢占条件占有且申请条件循环等待条件小结（3）解决死锁的方法死锁的预防：即破坏产生死锁的四个必要条件中的一个或多个，使系统绝不会进入死锁状态；死锁的避免：即在资源动态分配的过程中使用某种办法防止系统进入死锁状态；死锁的检测与解除：允许系统产生死锁，然后使用检测算法及时地发现并解除它。作业习题66.18,6.19第6章处理器管理(4)6.1进程的概念

6.2进程的状态和转换

6.3进程的控制

6.4进程的协调

6.5进程间的通信

6.6进程的安全性

6.7线程的概念

6.8作业管理

6.9处理器调度进程管理第6章处理器管理（4）学习目标:1.掌握作业调度和进程调度的功能，及两者之间的关系；掌握处理器管理的三级调度模型。2.掌握作业的四种状态：提交、后备、执行和完成。3.了解常用调度算法的评价指标： 吞吐量、周转时间、平均周转时间、带权周转时间和平均带权周转时间。4.了解三种基本调度算法的实现思想。重点：处理器管理的三级调度模型6.8作业管理学习内容：1、作业和作业步2、作业控制块3、作业的状态1.作业和作业步作业是用户提交给计算机系统完成的一个独立任务（job/task）。作业是早期批处理系统引入的一个概念；分时系统用户在一次登录后所进行的交互序列也常被看做一个作业；作业的分类（根据作业处理方式的不同）批处理作业交互式作业$LOAD装入编译好的目标程序$RUN运行程序并使用随后的数据$ENDendofjob1.作业和作业步批处理作业包括程序、数据和作业说明书。程序、数据用于解决用户的应用问题；作业说明书体现用户对作业的控制意图，包括作业基本描述：用户名、作业名、编程语言等；作业控制描述：各作业步的操作顺序、出错处理等；资源要求描述：估计的内存大小、处理时间、外设类型及数量、作业优先级、所需库函数或实用程序等$JOBcardspecifies:最大运行时间（分钟）Theaccountnumbertobecharged程序员名字$FORTRANcard:告诉操作系统从系统磁盘装入Fortran编译器；Fortan程序典型的FMS(FortranMonitoringSystem)作业结构1.作业和作业步批处理作业后备作业中的一个作业，经操作系统的作业调度程序选择进入内存，并为其建立作业控制进程。作业控制进程解释作业说明书的语句，根据作业步的要求为其建立进程。批处理作业由假脱机输入程序（SPOOLing输入程序）控制进入输入井(磁盘中的区域);后备状态。作业控制程序的工作原理1.作业和作业步交互式作业操作系统在启动时,为连接至系统的每个终端设备创建一个终端进程,此进程执行命令解释程序。在分时系统中，作业就是用户的一次上机交互过程。终端的创建是一个交互式作业的开始；退出命令的运行结束代表交互式作业的中止；用户逐条输入命令，即提交作业（步）和控制作业运行，系统则逐条命令执行并给出应答。1.作业和作业步作业步：一个作业的处理可以分成若干相对独立的执行步骤，称为作业步。例如，一个用C语言和汇编语言编写的程序，作为批处理作业处理，大致包括以下步骤：运用C语言编译程序对C语言源程序进行编译运行汇编程序对汇编代码部分进行汇编运行连接装配程序对前两部产生的结果进行装配执行上一步产生的代码通常，对于多作业步的作业来说，每个作业步可对应一个进程（对于单作业步的作业，一个作业就是一个进程）。作业流：一次有一批作业进入系统，并在操作系统的控制下，一个作业接一个作业地进行处理，这称之为作业流。2.作业控制块作业控制块JCB(JobControlBlock)为了便于对作业进行管理和调度，对每一个进入系统的作业都要建立一个作业控制块JCB，以便记录与该作业调度有关的信息。随时掌握并记录作业在各运行阶段的状况，包括资源分配及其使用情况，以及作业所处的状态等信息。通常每个JCB用一个一维数组表示，不同的操作系统JCB所包含的内容有所不同是作业在系统中存在的标志3.作业状态在批处理操作系统中，一个作业从进入系统到运行结束，其间有多个作业状态：提交状态后备状态执行状态完成状态3.作业状态1.提交状态:

即用户向系统提交一个作业时，该作业所处的状态。读卡机读入作业的过程；或用户通过键盘输入作业的过程。

2.后备状态：

用户作业的全部信息经输入设备（如读卡机）输入至外存的某些区域（这些外存区专门存放输入作业，称为输入井）中存放，等待调度进入内存时所处的状态。作业信息已转成机器可读的形式，其请求资源等信息也交给操作系统。系统为每个作业建立一个作业控制块（JCB），并把它加入到后备作业队列中，随时等待调度。（标志作业建立完成）3.执行状态：

作业被作业调度程序选中，调入内存、分配所需的资源，并在CPU上执行相应的作业步时所处的状态。此时该作业真正处于活动状态。4.完成状态：

作业正常运行结束(或因发生错误而终止时)的状态。系统回收分配给它的全部资源，将运行结果打印输出。3.作业状态运行就绪完成等待后备提交进入内存执行进程调度作业调度作业调度4.作业管理的任务确定计算机系统中哪些或哪个作业将获得CPU的服务。5.作业和进程的关系作业和进程的关系作业:用户向计算机提交的任务实体；进程:具体完成用户任务的运行实体，是系统分配资源和调度的基本单位；作业总是由一个以上的进程组成：对于多作业步的作业来说，每个作业步可对应一个进程；对于单作业步的作业，一个作业就是一个进程。6.9处理器调度学习内容：6.9.1处理器调度的层次6.9.2作业调度和进程调度功能6.9.3调度性能的评价6.9.4常用的调度算法调度：就是选出待分派的作业或进程。处理器调度：是为了分配处理器。从调度所实现的功能来分，处理机调度可分为三级：

1)作业调度（高级调度）2)进程挂起与对换（中级调度）3)进程调度（低级调度）6.9.1处理器调度的层次6.9.1处理器调度的层次1)作业调度（高级调度）： 其主要功能是根据一定的算法，从输入的一批作业中选出若干个作业进入内存执行：分配必要的资源(内存、外设等)；为它建立相应的用户作业进程和为其服务的系统进程（输入/输出进程等）；等待进程调度程序对其执行调度，并在作业完成后进行善后处理，回收系统资源。6.9.1处理器调度的层次2)进程挂起与对换（中级调度）引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待（对换技术）。把此时的进程状态称为挂起状态。不参与低级调度。当这些进程中又具备运行条件、且内存又有空闲时，由中级调度来决定把外存上的那些进程重新调入内存工作，从而能短期均衡系统负载，提高内存利用率和系统吞吐量。6.9.1处理器调度的层次3)进程调度（低级调度）主要功能是，根据一定的算法由进程调度程序将CPU分派给就绪队列中的一个进程。在一般类型的操作系统中都必须有进程调度，其策略的优劣直接影响整个系统的性能。说明：三级调度中，低级调度是各类操作系统必备的功能；多道批处理系统（一般操作系统）:存在高级和低级调度；分时系统/实时系统：不存在高级调度，只有中级调度和低级调度。功能完善