操作系统第3章_1

1、1 第三章、进程管理第三章、进程管理 3.1进程的概念进程的概念3.2进程的描述进程的描述3.3进程状态及其转换进程状态及其转换3.4进程控制进程控制3.5进程互斥进程互斥3.6进程同步进程同步3.7进程通信进程通信3.8死锁问题死锁问题3.9线程线程3.1 进程的概念进程的概念一、程序的并发执行一、程序的并发执行1、程序的、程序的顺序顺序执行：执行：具独立功能的程序独占具独立功能的程序独占CPU及其它资源，直至得到结果。及其它资源，直至得到结果。特点：特点：1）顺序性）顺序性2）封闭性）封闭性3）可再现性）可再现性作业作业1作业作业223 2、程序的、程序的并发并发执行：执行：一组逻辑上独立

2、的程序在执行过程中，其执行时间一组逻辑上独立的程序在执行过程中，其执行时间在客观上重叠，一个程序执行尚未结束，另一段程序即在客观上重叠，一个程序执行尚未结束，另一段程序即开始执行。（多道程序之间、一道程序的持续段之间）开始执行。（多道程序之间、一道程序的持续段之间）特点：特点：1）失去封闭性）失去封闭性2）不可再现性）不可再现性3）间断性）间断性41）并发执行的特点）并发执行的特点 失去封闭性失去封闭性由于多个程序共享资源，资源的状态可由多个程序改由于多个程序共享资源，资源的状态可由多个程序改变，一个程序的运行会受到其它程序的影响。变，一个程序的运行会受到其它程序的影响。例例2：Procedu

3、re getaddr(top) begin local r r = (top) top = top 1 return(r) endProcedure reladdr(top) begin top = top + 1 (top) = blk end52）并发执行的特点）并发执行的特点 不可再现性不可再现性begin integer N = 0; cobeginprogramA:begin。 N = N + 1; goto programA endprogramB:begin。 print(N); N = 0; goto programB end coendendN = n 打印结果打印结果N值值

4、 n+1 0 n 0 n 1结论：结论： 程序的执行结果与并发程序程序的执行结果与并发程序的执行速度和顺序有关，即便的执行速度和顺序有关，即便初始条件相同，也可能得到不初始条件相同，也可能得到不同的结果。同的结果。例例3：63）并发执行的特点）并发执行的特点 间断性间断性由于多个程序共享资源，或为完成一项任务相互合作，使并发程由于多个程序共享资源，或为完成一项任务相互合作，使并发程序之间形成相互制约关系，导致其序之间形成相互制约关系，导致其“执行执行暂停暂停执行执行”这种间断这种间断性活动规律。性活动规律。相邻语句可并发执行的相邻语句可并发执行的Bernstein条件：条件： （P39） 例例

5、1：以下三个赋值语句哪两个之间可以并发执行：以下三个赋值语句哪两个之间可以并发执行：S1: a = x + yR(S1) = x , y W(S1) = aS2: b = z + 1R(S2) = z W(S2) = bS3: c = a + bR(S3) = a , b W(S3) = cS1与与S2可并发执行：可并发执行：R(S1)W(S2) W(S1)R(S2) WR(S1)W(S2) = S1与与S3不能并发执行：不能并发执行：W(S1)R(S3) = aS2与与S3不能并发执行：不能并发执行：W(S2)R(S3) = b38总总 结结 多道程序环境下程序的特征：多道程序环境下程序的特

6、征：并发性：外设并发性：外设-主机，外设主机，外设-外设，程序外设，程序-程序；程序；制约性：共享资源、相互合作，相互牵制；制约性：共享资源、相互合作，相互牵制；动态性：走走停停、异步运行。动态性：走走停停、异步运行。“程序程序”概念的局限：概念的局限：程序是完成某个功能的指令的集合，静态的程序是完成某个功能的指令的集合，静态的概念，无法反映程序运行的动态性概念，无法反映程序运行的动态性运行在运行在CPU上只有一个程序，对于多任务则上只有一个程序，对于多任务则无法反映并发性无法反映并发性思考：今天借书和明天借书有何不同？今天借书和明天借书有何不同？上午踢球和下午踢球有何不同？上午踢球和下午踢球

7、有何不同？张师傅和李师傅炒的回锅肉是否一样美味？张师傅和李师傅炒的回锅肉是否一样美味？9借书的程序：借书的程序：11你的一天你的一天1、早餐、早餐2、上午上课、上午上课3、午餐吃小炒、午餐吃小炒4、图书馆借书、图书馆借书5、打网球、打网球6、晚自习、晚自习7、洗澡、洗澡8、睡觉、睡觉教务处安排时段和教室教务处安排时段和教室候时长短取决于时机候时长短取决于时机书是否被借走？书是否被借走？有场地？有场地？有搭档？有搭档？冲突时安排顺序冲突时安排顺序四年内的独占资源四年内的独占资源教室？图书馆？宿舍？教室？图书馆？宿舍？食堂早上开门时段食堂早上开门时段12宏观角度：学校各部门有序管理和分配资源宏观角

8、度：学校各部门有序管理和分配资源共享共享 争夺资源：争夺资源：目标：公平、安全、高效目标：公平、安全、高效实施：资源的实施：资源的分配策略分配策略 管理机制管理机制（登记、时限、归还）（登记、时限、归还）前提：以个体或班级为管理对象前提：以个体或班级为管理对象 实施实施动态动态的分配和管理的分配和管理用一个概念来描述：用一个概念来描述：学生或班级进行某项活动的动态过程学生或班级进行某项活动的动态过程 13进进 程程14微观角度：学生按需申请使用资源微观角度：学生按需申请使用资源1、注册登记，分配基本资源；注册登记，分配基本资源；2、活动状态的记录和转换；、活动状态的记录和转换；3、进行一项活动

9、之前：、进行一项活动之前：A、是否具备参加的资格？、是否具备参加的资格？（前提：别人的配合？自己的准备？）（前提：别人的配合？自己的准备？）B、能否获得需要资源？、能否获得需要资源？（申请（申请等待等待分配分配使用使用归还）归还）4、活动的开展；、活动的开展；5、结束后归还资源。、结束后归还资源。进程的描述进程的描述进程状态及管理进程状态及管理进程同步进程同步进程互斥进程互斥进程的执行进程的执行进程的撤销进程的撤销15二、进程：二、进程：1、定义：、定义：进程进程 是一个具有独立功能的是一个具有独立功能的程序程序对某个数据对某个数据集在处理机上的集在处理机上的执行过程执行过程，是系统进行资源分

10、配，是系统进行资源分配和调度的基本单位。和调度的基本单位。进程是可并发执行的程序在一个数据集合上的进程是可并发执行的程序在一个数据集合上的运行过程运行过程。162、进程与程序的区别：、进程与程序的区别：进程进程程序程序动态特征动态特征执行过程，执行过程，有生命期，创有生命期，创建建调度调度撤消撤消有序指令的集合，不反映执行有序指令的集合，不反映执行过程，静态过程，静态并发特征并发特征多个进程在同一时间内同时多个进程在同一时间内同时运行运行没有为之建立进程的程序不能没有为之建立进程的程序不能并发执行并发执行独立特征独立特征独立运行、分配资源、调度独立运行、分配资源、调度的基本单位的基本单位未建进

11、程的程序，不能作为独未建进程的程序，不能作为独立单位运行立单位运行异步特征异步特征按各自独立、不可预知的速按各自独立、不可预知的速度向前推进，相互协调度向前推进，相互协调独占全机运行，结果确定，不独占全机运行，结果确定，不需协调需协调结构特征结构特征程序段程序段+数据段数据段+进程控制块进程控制块PCB不同的进程可对应同一程序，不同的进程可对应同一程序，只要对应的数据集不同只要对应的数据集不同173、进程与作业的区别：、进程与作业的区别：1）作业是用户向计算机提交的）作业是用户向计算机提交的任务实体任务实体，提交后放在，提交后放在外存等待队列中；外存等待队列中；进程是完成用户任务的进程是完成用

12、户任务的执行实体执行实体，是分配资源的基本，是分配资源的基本单位，创建后部分存于内存。单位，创建后部分存于内存。2）作业由一个或多个进程组成。）作业由一个或多个进程组成。3）作业的概念主要用于批处理系统中；）作业的概念主要用于批处理系统中； 进程的概念主要用于多道程序系统中。进程的概念主要用于多道程序系统中。183.2 进程的描述进程的描述程序部分程序部分：描述进程的功能：描述进程的功能数据结构集：执行时的工作区和操作对象数据结构集：执行时的工作区和操作对象进程控制块：描述进程的情况和控制其运行所需的信息进程控制块：描述进程的情况和控制其运行所需的信息一、进程控制块一、进程控制块PCB1、基本

13、内容：、基本内容：描述信息、控制信息、资源信息、描述信息、控制信息、资源信息、CPU现场保护区现场保护区2、系统根据系统根据PCB感知进程的存在感知进程的存在，是进程存在的唯一标志，是进，是进程存在的唯一标志，是进程动态特征的集中反映，常驻内存程动态特征的集中反映，常驻内存PCB区。区。3、组织方式：、组织方式： 1）链接队列）链接队列 2）索引表）索引表19进程控制块进程控制块PCB主要内容主要内容进程标识符进程标识符家族关系家族关系现行状态现行状态互斥和同步机构互斥和同步机构进程通信机构进程通信机构进程优先数进程优先数链接字链接字程序与数据地址程序与数据地址资源清单资源清单CPU现场保护区

14、现场保护区二、进程上下文二、进程上下文 进程执行活动过程的静态描述，是进程执行所依赖的环境。进程执行活动过程的静态描述，是进程执行所依赖的环境。 当系统调度新进程占有处理机时，新老进程的发生当系统调度新进程占有处理机时，新老进程的发生上下文切换上下文切换。11CPU现场 四道程序并发执行：四道程序并发执行：上下文切换上下文切换列车的运行列车的运行:22列车行进列车行进进站上下旅客进站上下旅客 补给、换班补给、换班等待调度发车等待调度发车233.3 进程状态及其转换进程状态及其转换1、就绪状态就绪状态ready：已获得除已获得除CPU之外的所有必要资源。之外的所有必要资源。2、执行状态执行状态e

15、xcute：占有占有CPU正在执行。正在执行。3、等待（阻塞）状态等待（阻塞）状态blocked：因某事件（请求因某事件（请求I/O）而暂停执行，处于等）而暂停执行，处于等待执行的状态。待执行的状态。24发生阻塞的原因：发生阻塞的原因：1 1、等待外设操作完成；、等待外设操作完成；2 2、对某一资源（系统调用、文件、内存、外设）的访、对某一资源（系统调用、文件、内存、外设）的访问尚不能进行；问尚不能进行；3 3、等待具有合作关系的某一进程执行完毕；、等待具有合作关系的某一进程执行完毕；注意区分：注意区分：1 1、等待外设进行输入或输出操作这一过程的结束、等待外设进行输入或输出操作这一过程的结束

16、 2 2、等待外设准备进行输入或输出操作、等待外设准备进行输入或输出操作三个进程状态转换三个进程状态转换执行执行 就绪就绪 阻塞阻塞进程进程B进程进程A进程进程C分派程序分派程序执行执行 就绪就绪 阻塞阻塞26PCB队列结构队列结构：27PCB索引结构索引结构：索引表索引表就绪队列就绪队列等待队列等待队列 1等待队列等待队列 2PCB 1PCB 2PCB 3PCB 4PCB 5PCB 6PCB 7PCB n PCB表表28多道程序并发执行的实例多道程序并发执行的实例30作业调度与进程调度作业调度与进程调度3.4 进程控制进程控制进程控制：进程控制：系统使用一些具有特定功能的程序段来创建、撤消进

17、程，以及完成系统使用一些具有特定功能的程序段来创建、撤消进程，以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。源共享的目的。由操作系统的内核实现，通过执行原语操作进行控制。由操作系统的内核实现，通过执行原语操作进行控制。操作系统的内核：操作系统的内核：包括与硬件紧密相关的模块、运行频率高的公用模块；包括与硬件紧密相关的模块、运行频率高的公用模块；安排在靠近硬件的层次中，基于硬件的第一次软件扩充，常驻内存；安排在靠近硬件的层次中，基于硬件的第一次软件扩充，常驻内存；功能多为中断处理、进程管理、对外设

18、的基本操作。功能多为中断处理、进程管理、对外设的基本操作。原语原语：在系统态下执行某些特定功能的程序段，是机器指令的延伸，由若在系统态下执行某些特定功能的程序段，是机器指令的延伸，由若干指令组成，在执行期间不可分割、中断，具有原子性。干指令组成，在执行期间不可分割、中断，具有原子性。15一、进程创建一、进程创建create( )形成进程控制块形成进程控制块PCB创建方式：创建方式：1、系统程序模块统一创建、系统程序模块统一创建2、父进程创建、父进程创建创建事件：创建事件：1、用户登录、用户登录2、作业调度、作业调度3、提供服务、提供服务4、应用请求、应用请求33Procedure Create

19、(n,S0,k0,M0,R0)begini:= Get Internal Name(n); * 进程外部名进程外部名Id(i) := n; * PCB内部标示号内部标示号Priority(i) := k0; *进程优先数进程优先数Cpustate(i) := S0; *CPU初始状态初始状态Main Store(i) := M0; *内存初始占有情况内存初始占有情况Resources(i) := R0; *其它资源初始占有情况其它资源初始占有情况Status(i) := Readys; *进程初始状态置为就绪进程初始状态置为就绪Parent(i) := CALLER; *父进程名父进程名Ins

20、ert(RL,i); *把把i插入就绪队列插入就绪队列end34相关系统调用相关系统调用 1、fork( )：创建子进程，子进程复制父进程程序数据资源：创建子进程，子进程复制父进程程序数据资源对对父进程返回正整数父进程返回正整数（子进程的进程标识号（子进程的进程标识号pid）对对子进程返回子进程返回0创建失败返回创建失败返回-1。2、getpid( )：获得当前进程的进程标识号：获得当前进程的进程标识号pid3、getppid( )：获得父进程的进程标识号：获得父进程的进程标识号pid35例例1：父进程创建一个子进程，在父子进程中分父进程创建一个子进程，在父子进程中分别输出各自的进程标识号。别

21、输出各自的进程标识号。 main()int x,p; if(p= fork() = 0) printf(this is child processn); printf( My PID (child) is %dn,getpid(); printf( My parent PID is %dn,getppid(); else printf(This is parent processn); printf(My PID(parent) is %dn,getpid(); printf(My child PID is %dn,p); 父进程CPU 子进程返回返回0返回子返回子pid例例2：父进程创建两个

22、子进程，各自输出一个字符。父进程创建两个子进程，各自输出一个字符。 通过多次运行的结果分析进程并发运行的特点。通过多次运行的结果分析进程并发运行的特点。#include main() int p1,p2; while (p1=fork()=-1) ; if (p1 = 0) putchar(b); /第一个子进程执行第一个子进程执行 else while (p2=fork()=-1) ； if(p2 = 0) putchar(c); /第二个子进程执行第二个子进程执行 else putchar(a); /父进程执行父进程执行 【执行结果执行结果】studentlocalhost $ ./1bc

23、astudentlocalhost $ ./1bcastudentlocalhost $ ./1bcastudentlocalhost $ ./1bastudentlocalhost $ c./1bcastudentlocalhost $ ./1bcastudentlocalhost $ ./1bcastudentlocalhost $ ./1bcastudentlocalhost $ ./1bcastudentlocalhost $ ./1bcastudentlocalhost $ ./1castudentlocalhost $ b父子进程父子进程PCB关系：关系：38程序；if ( p2

24、0 )输出a;；父进程PCB复制复制程序；if ( p1 = 0 )输出b;；子进程P1 PCB程序；if ( p2 = 0 )输出c;；子进程P2 PCB二、进程撤消二、进程撤消destroy( )释放各种资源释放各种资源撤消原因：撤消原因： 1、正常结束、正常结束 2、异常结束、异常结束 3、外界干预、外界干预40Destroy(n):撤消指定标识符的进程及其所有子进程撤消指定标识符的进程及其所有子进程 由父进程或祖先进程发出，不会自己撤消自己，由父进程或祖先进程发出，不会自己撤消自己，被撤消进程的全部系统资源全部释放出来归还给系统。被撤消进程的全部系统资源全部释放出来归还给系统。若其正在

25、运行则调用处理机调度程序。若其正在运行则调用处理机调度程序。Procedure Destroy(n)beginSched := false;i:= Search Internal Name(n);KILL(i);if Sched = true then Scheduler; end Sched：标志是否需要调用处理机调度程序标志是否需要调用处理机调度程序。41KILL(i):杀死所有属于杀死所有属于i的子进程并释放所有资源的子进程并释放所有资源Procedure KILL(i)beginif Status(i) = Running thenbegin STOP(i); Sched := tru

26、e endREMOVE(Queue(i),i);/从进程i所在队列移走进程ifor all Pprogeny(i) do KILL(P);/杀死所有属于i的子进程for all r progeny(i) do RELEASE(r);/释放进程i占用的所有资源 RELEASE(PCB(i);end三、进程等待三、进程等待block( )和唤醒和唤醒wakeup( )原因：原因：1、请求操作系统服务、请求操作系统服务 2、启动某种操作、启动某种操作 3、新数据未到、新数据未到 4、无新工作可做、无新工作可做Procedure blockbegini:= EP; / EP-执行进程的指针stop(i)