操作系统第2章进程管理(藏汉双语)

1、主讲：头旦才让主讲：头旦才让计算机学院藏文信息科学系计算机学院藏文信息科学系第二章第二章 进程描述与控制进程描述与控制 程序执行一前趋图和程序执行进程的描述、控制二进程同步、经典同步问题三线程及其实现四v 掌握分析进程的结构，特征掌握分析进程的结构，特征， PCBPCB。v 描述进程的基本状态及转换规则与原因。描述进程的基本状态及转换规则与原因。v 掌握解决互斥与同步的方法。掌握解决互斥与同步的方法。v 掌握掌握3 3个经典问题的解决方法：个经典问题的解决方法： 生产者生产者/ /消费者问题、消费者问题、 读者读者/ /写着问题、写着问题、 哲学家进餐问题。哲学家进餐问题。通过本章的学习通过本

2、章的学习，你应该学会以下内容：你应该学会以下内容：第二章第二章 进程描述与控制进程描述与控制 程序执行一前趋图和程序执行进程的描述、控制二进程同步、经典同步问题三线程及其实现四P1P3P8P9P4P2P5P6P7S1S2S3(a) 具有九个结点的前趋图(b) 具有循环的前趋图图图a所示的前趋关系为：所示的前趋关系为：P1-P2，P1-P3，P1-P4，P2-P5，P3-P5，P4-P6，P4-P7，P5-P8，P6-P8，P7-P9，P8-P9对，俺不是我是前趋图，他不是2.1 .2 程序的顺序执行程序的顺序执行 S1: a=x+y; S2: b=a-5; S3: c=b+1;(a) 程序的顺

3、序执行(b) 三条语句的顺序执行I1C1P1I2C2P2S1S2S3I1I2I3I4C1C2C3C4P1P2P3P4t2.1 .3 程序并发执行程序并发执行：S1S2S3S42.1 .3 程序并发执行程序并发执行2.1 .3 程序并发执行程序并发执行顺序执行并发执行一一对应一个程序可对应多个执行独占资源，具有封闭性共享资源，不具有封闭性具有无具有无无有直接或间接制约关系第二章第二章 进程描述与控制进程描述与控制 程序执行一前趋图和程序执行进程的描述、控制二进程同步、经典同步问题三线程及其实现四2.2 进程的描述2.2 进程的描述l 2.2.1进程的特征 进程是动态的，程序是静态的进程是动态的，

4、程序是静态的 进程是暂时的，程序是永久的进程是暂时的，程序是永久的 程序是由多个进程运行的程序是由多个进程运行的 进程与程序的组成不同进程与程序的组成不同 进程与程序的对应关系进程与程序的对应关系进程和程序之间不存在一一对应关系。进程和程序之间不存在一一对应关系。一个程序可以对应多一个程序可以对应多个进程；反之，一个进程至少要对应一个程序，或对应多个个进程；反之，一个进程至少要对应一个程序，或对应多个程序，多个进程也可对应相同的程序。程序，多个进程也可对应相同的程序。 进程具有并发特征（独立性和异步性）进程具有并发特征（独立性和异步性）2.2 进程的描述l 进程和程序的联系及区别进程和程序的联

5、系及区别理解进程的实例 想象一位有一手好厨艺的计算机科学家正在为他的女儿烘制生日蛋糕。他有做生日想象一位有一手好厨艺的计算机科学家正在为他的女儿烘制生日蛋糕。他有做生日蛋糕的食谱，厨房里有所需的原料：面粉、鸡蛋、糖、香草汁等等。在这个比喻中，做蛋糕的食谱，厨房里有所需的原料：面粉、鸡蛋、糖、香草汁等等。在这个比喻中，做蛋糕的食谱就是程序蛋糕的食谱就是程序( (即用适当形式描述的算法即用适当形式描述的算法) )，计算机科学家就是处理机，计算机科学家就是处理机(CPU)(CPU)，而做，而做蛋糕的各种原料就是输入数据。进程就是厨师阅读食谱、取来各种原料、以及烘制蛋糕蛋糕的各种原料就是输入数据。进程

6、就是厨师阅读食谱、取来各种原料、以及烘制蛋糕的一系列动作的总和。的一系列动作的总和。 现在假设计算机科学家的儿子哭着跑了进来，说他被一只蜜蜂螫了。计算机科学家现在假设计算机科学家的儿子哭着跑了进来，说他被一只蜜蜂螫了。计算机科学家就记录下他照着食谱做到哪儿了就记录下他照着食谱做到哪儿了( (保存进程的当前状态保存进程的当前状态) )，然后拿出一本急救手册，按照，然后拿出一本急救手册，按照其中的指示处理螫伤。这里，我们看到处理机从一个进程其中的指示处理螫伤。这里，我们看到处理机从一个进程( (做蛋糕做蛋糕) )切换到另一个高优先切换到另一个高优先级的进程级的进程( (实施医疗救治实施医疗救治)

7、)，每个，每个( (进程进程) )拥有各自的程序拥有各自的程序( (食谱和急救书食谱和急救书) )。当蜜蜂螫伤处。当蜜蜂螫伤处理完之后，计算机科学家又回来做蛋糕，从他离开时的那一步继续做下去。理完之后，计算机科学家又回来做蛋糕，从他离开时的那一步继续做下去。 这里的关键思想是：一个进程是某种类型的一个活动，它有程序、输入、这里的关键思想是：一个进程是某种类型的一个活动，它有程序、输入、输出、及状态。单个处理机被若干进程共享，它使用某种调度算法决定何时停输出、及状态。单个处理机被若干进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另一个进程提供服务。止一个进程的工作，并转而为另一

8、个进程提供服务。理解进程的实例主讲：头旦才让主讲：头旦才让计算机学院藏文信息科学系计算机学院藏文信息科学系就绪就绪阻塞阻塞执行执行时间片完时间片完进程调度进程调度分配分配CPUI/O请求请求I/O完成完成图图2 25 5 进程的三种基本状态及其转换进程的三种基本状态及其转换2.2.2 进程的基本状态及转换三种基本状态的转换三种基本状态的转换l 创建状态和终止状态创建状态和终止状态2.2.2 进程的基本状态及转换图图2 26 6 进程的五种基本状态及其转换进程的五种基本状态及其转换2.2.2 进程的基本状态及转换2.2.2 进程的基本状态及转换 2.2.2 进程的基本状态及转换l 被挂起进程的特

9、征被挂起进程的特征2.2.2 进程的基本状态及转换执行执行活动活动就绪就绪静止静止就绪就绪活动活动阻塞阻塞静止静止阻塞阻塞激活激活挂起挂起许可许可创建创建终止终止调度调度时间片完时间片完激活激活挂起挂起事件发生事件发生释放释放释放释放2.2.2 进程的基本状态及转换挂起挂起释放释放许可许可2.2.4 进程管理中的数据结构资源（进程）信息表：标识资源（进程）信息表：标识+ +描述描述+ +状态状态+ +指针指针OSOS管理的数据结构分为四类：内存表、设备表、文件表、进程表管理的数据结构分为四类：内存表、设备表、文件表、进程表内存内存设备设备文件文件进程进程内存表内存表内存表进程进程1进程2进程3

10、进程n进程1进程实体及所用资源列表进程实体及所用资源列表进程npid处理机状态处理机状态进程状态进程状态优先级优先级其他信息其他信息程序地址程序地址同步机制同步机制资源清单资源清单链接指针链接指针标识标识处理机状态处理机状态进程调度信息进程调度信息进程控制信息进程控制信息2.2.3 进程管理中的数据结构第二章第二章 进程描述与控制进程描述与控制 程序执行一前趋图和程序执行进程的控制二进程同步、经典同步问题三线程及其实现四2.3.1 进程控制描述2.3.2 进程的创建2.3.2 进程的创建开始开始查查PCBPCB链表链表填空表填空表PCBPCB将有关参数填入将有关参数填入PCBPCB相应项相应项

11、将将PCBPCB加入就绪队列加入就绪队列将将PCBPCB加入进程家族或进程链加入进程家族或进程链创建失败创建失败是是无无空表空表2.3.2 进程的创建2.3.2 进程的创建2.3.3 进程的终止2.3.3 进程的终止开始开始查进程家族或进程链查进程家族或进程链释放该进程所占有的资源释放该进程所占有的资源释放该释放该PCBPCB结构本身结构本身出错处理出错处理有有无无由此由此PCB吗吗该该PCB有子进程吗？有子进程吗？返回返回有有无无2.3.4 进程的阻塞和唤醒第二章第二章 进程描述与控制进程描述与控制 程序执行一前趋图和程序执行进程的控制二进程同步、经典同步问题三线程及其实现四v 进程同步的主

12、要任务：使并发程序的执行有可再现性进程同步的主要任务：使并发程序的执行有可再现性两种形式的制约关系两种形式的制约关系v 间接制约关系（进程互斥）间接制约关系（进程互斥） ：是进程共享独占型资源而必须互斥执行的间接制约关系。v 直接制约关系（进程同步）直接制约关系（进程同步）：即为完成同一个任务的诸进程间，因需要协调它们的工作而相互等待、相互交换信息所产生的直接制约关系。 v 同步与互斥比较同步与互斥比较同同 步步互互 斥斥进程-进程进程-资源-进程时间次序上受到某种限制竞争到某一物理资源时不允许进程工作相互清楚对方的存在及作用，交换信息不一定清楚其进程情况往往指有几个进程共同完成一个任务往往指

13、多个任务多个进程间通讯制约例：生产与消费之间，发送与接受之间，作者与读者之间，供者与用者之间例：交通十字路口2.4.1 进程同步的基本概念 到站停车到站停车 开开 车车 开车门开车门 关车门关车门 售票售票 正常行车正常行车。售票员进程售票员进程B B司机进程司机进程A A进程同步例子司机操作的规则：司机操作的规则： 只有只有B B关门后，关门后，A A才能行驶才能行驶售票员操作的规则：售票员操作的规则： 只有只有A A停车后，停车后，B B才能开门，才能开门，B B关门后，向关门后，向A A发开车信号，发开车信号，A A收到信号才能开收到信号才能开临界资源（临界资源（ ）：）：一次只允许一个

14、进程使用的资源称为临界资源。临界区（临界区（ ）：）：在每个进程中访问临界资源的程序段成为临界区。临界资源和临界区 空闲让进空闲让进：当无进程在临界区时，任何有权使用临界区的进：当无进程在临界区时，任何有权使用临界区的进程可进入程可进入 忙则等待忙则等待：不允许两个以上的进程同时进入临界区（互斥）：不允许两个以上的进程同时进入临界区（互斥） 有限等待有限等待：任何进入临界区的要求应在有限的时间内得到满：任何进入临界区的要求应在有限的时间内得到满足（死等）足（死等） 让权等待让权等待：处于等待状态的进程应放弃占用：处于等待状态的进程应放弃占用CPUCPU（忙等）（忙等）同步机制应遵守的原则2.4

15、.3 信号量机制 Semaphore 整型信号量Wait(S)和和signal(S)操作操作描述如下：描述如下：记录型信号量：信号量的类型信号量的类型2.4.4 2.4.4 信号量的应用信号量的应用1.1.利用信号量实现进程互斥利用信号量实现进程互斥进程能互斥访问临界资源设置互斥信号量-mutex初始值=1临界区CS置于中间临界区CS置于中间Wait(mutex)Wait(mutex)Mutex=1,Mutex=1,两个进程两个进程未进入临界区未进入临界区Mutex=0,Mutex=0,一个进程进入临界一个进程进入临界区运行，另一个等待区运行，另一个等待Mutex=-1,Mutex=-1,一个

16、进程进入临界区一个进程进入临界区运行，另一个阻塞，等待唤醒运行，另一个阻塞，等待唤醒2.2.利用信号量实现前趋关系利用信号量实现前趋关系 图 2-14 前趋图举例 S4S5S3S1S6S2左图所示了一个前趋图，其中S1、S2，S3，S4，S5，S6是最简单的程序段，为使个程序段能正确执行，应设置若干个初始值为“0”的信号量： 信号量S1-S2 aS1-S3 bS2-S4 cS2-s5 dS3-S6 eS4-S6 fS5-S6 g Var a，b，c，d，e，f，g； semaphore =0，0，0，0，0，0，0； begin parbegin begin S1；signal(a)； sig

17、nal(b)；end； begin wait(a)； S2；signal(c)； signal(d)；end； begin wait(b)； S3；signal(e)；end； begin wait(c)；S4；signal(f)；end； begin wait(d)；S5；signal(g)；end； begin wait(e)；wait(f)；wait(g)；S6；end； parend end P(S) ； V(S)； wait(S) ； signal(S) ； S4S5S3S1S6S2abcdegf2.2.利用信号量实现前趋关系利用信号量实现前趋关系 2.4.5 2.4.5 管管 程程

18、 机机 制制 1. 管程的定义管程的定义 2. 管程由四部分组成：管程由四部分组成： 管程的名称。 局部于管程内部的共享数据结构说明； 对该数据结构进行操作的一组过程； 对局部于管程的数据设置初始值的语句。 一个管程定义了一个数据结构和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。第二章第二章 进程描述与控制进程描述与控制 程序执行一前趋图和程序执行进程的控制二经典的进程同步问题三线程及其实现四公共汽车问题公共汽车问题同步同步 到站停车到站停车 开开 车车 开车门开车门 关车门关车门 售票售票 正常行车正常行车。售票员进程售票员进程B B司机进程司机进程A Asemaph

19、ore S1=0；/是否允许司机启动汽车semaphore S2=0；/是否允许售票员开门void siji（） /司机进程begin while（1） begin P（S1）;/司机进程暂停，售票员关车门 启动车辆； 正常行驶； 到站停车； V（S2）；/激活售票员，允许B开门End；End；void spy（） /售票员进程Begin while（1） begin 关车门； V（S1）；/激活司机，允许A开车 售票； P（S2）；/等待司机 开车门； 上下客； end；End；mian （） Begin Siji（）； Spy（）； end.公共汽车问题公共汽车问题同步同步【桔子苹果问题桔

20、子苹果问题】 放苹果发同步信号S2放桔子发同步信号S3初始状态：同步信号量S1=1，表示盘子为空爸爸桔子或苹果苹果桔子女儿儿子女儿等信号S2发信号S1儿子等信号S3发信号S1 桌子上有一只盘子，盘子中只能放一只水果。爸爸专向盘子中放苹果或桔桌子上有一只盘子，盘子中只能放一只水果。爸爸专向盘子中放苹果或桔子，儿子专等吃盘子中的桔子，女儿专等吃盘子中的苹果。用子，儿子专等吃盘子中的桔子，女儿专等吃盘子中的苹果。用PVPV操作实现他们操作实现他们之间的同步机制。之间的同步机制。semaphore S1=1；semaphore S2=0；semaphore S3=0；father（）（）Begin w

21、hile(1) Begin P(S1);/等待水果盘中有空位等待水果盘中有空位 将水果放入盘中将水果放入盘中 if (是是苹果苹果) then V(S2); else V(S3); end；End；daughter( ) begin while(1) begin P(S2);/等待盘中放了苹果等待盘中放了苹果 取出苹果；取出苹果； V(S1);/，置盘中无水果，通知，置盘中无水果，通知爸爸可以放爸爸可以放 end；End；【桔子苹果问题桔子苹果问题】 son( ) begin while(1) begin P(S3);/等待盘中放了桔子等待盘中放了桔子 取出桔子；取出桔子； V(S1); /置

22、盘中无置盘中无水果，通知水果，通知爸爸爸可以放爸可以放 End；End；独木桥问题独木桥问题互斥互斥semaphore s=1； /s代表对桥的独占控制void e2w（） /由东向西 while（1） P（s）； pass（）； V（s）；【例例】一条小河上有一座独木桥，规定每次只允许一个人过桥。一条小河上有一座独木桥，规定每次只允许一个人过桥。现河东和河西都有人在等待过桥，如果把每个过桥者看做一个进现河东和河西都有人在等待过桥，如果把每个过桥者看做一个进程，为保证安全，用信号量和程，为保证安全，用信号量和P P、V V操作来管理。操作来管理。void w2e（） /由西向东 while（1

23、） P（s）； pass（）； V（s）； semaphore S1=1； /S1代表东边的人先过桥semaphore S2=0； /S2代表西边的人先让东边人过桥void e2w（） /由东向西 while（1） P（S1）； pass（）； V（S2）；独木桥问题独木桥问题同步同步v 要求：两边轮流过桥，以保证公平性；且东边的人先过桥要求：两边轮流过桥，以保证公平性；且东边的人先过桥void w2e（） /由西向东 while（1） P（S2）； pass（）； V（S1）；看电影问题看电影问题 有有3 3个网友，未曾谋面，他们相约去看电影，费用个网友，未曾谋面，他们相约去看电影，费用AA

24、AA制，条件是制，条件是3 3个人必须都到电影院的时候才能买票进入，如果缺一个人，就害个人必须都到电影院的时候才能买票进入，如果缺一个人，就害怕有危险，取消活动。试用信号量和怕有危险，取消活动。试用信号量和P P、V V操作描述操作描述3 3个人的行为。个人的行为。（请同学们思考一下，再看具体做法。）（请同学们思考一下，再看具体做法。） 这个问题看起来可能没有头绪，但问题倒是十分的简单明显，这个问题看起来可能没有头绪，但问题倒是十分的简单明显，那就是每个人到达电影院的时候，必须通知另外那就是每个人到达电影院的时候，必须通知另外2 2个人自己已经到个人自己已经到达（可以打电话或发手机短息告知哟）

25、，而且自己买票的行为取决达（可以打电话或发手机短息告知哟），而且自己买票的行为取决于另外于另外2 2个人确实已经到达。那么我们这里使用个人确实已经到达。那么我们这里使用6 6个信号量，来控制个信号量，来控制整个事情的流程。整个事情的流程。semaphore S12=0； /表示第1个人告知第2个人自己已到达semaphore S13=0； /表示第1个人告知第3个人自己已到达semaphore S21=0； /表示第2个人告知第1个人自己已到达semaphore S23=0； /表示第2个人告知第3个人自己已到达semaphore S31=0； /表示第3个人告知第1个人自己已到达semaph

26、ore S32=0； /表示第3个人告知第2个人自己已到达person1（） V(S12); V(S13); P(S21); P(S31); 买票；看电影问题看电影问题person2（） V(S21); V(S23); P(S12); P(S32); 买票；person3（） V(S31); V(S32); P(S13); P(S23); 买票；哲学家进餐问题哲学家进餐问题 哲学家进餐问题哲学家进餐问题#define N 5 / 哲学家数量#define LEFT (i+N-1)%N / i的左邻居编号#define RIGHT (i+1)%N / i的右邻居编号#define THINKIN

27、G 0 / 哲学家在思考#define HUNGRY 1 / 哲学家饥饿，试图拿叉子#define EATING 2 / 哲学家在进餐int stateN; / 数组用来跟踪记录每位哲学家的状态semaphore mutex=1; / 互斥进入临界区，初值为1semaphore sN=0; / 每位哲学家一个信号量，初值为0void philosopher(int i) / i为哲学家编号，从0到N-1 while(1) think(); / 哲学家在思考问题 take_forks(i); / 拿到两把叉子或者被阻塞 eat(); / 进餐 put_ forks(i); / 把叉子放回原处 哲

28、学家进餐问题哲学家进餐问题void take_ forks(int i) / i为哲学家编号，从0到N-1，拿叉子 P(mutex); / 进入临界区 statei=HUNGRY; / 记录哲学家i处于饥饿状态 test(i); / 试图拿两把叉子 V(mutex); / 离开临界区 P(si); / 如果得不到需要的叉子则阻塞void put_ forks(int i) / i为哲学家编号，从0到N-1，放下叉子 P(mutex); / 进入临界区 statei=THINKING; / 哲学家就餐完毕，开始思考 test(LEFT); / 查看左邻，现在能否进餐 test(RIGHT); /

29、 查看右邻，现在能否进餐 V(mutex); / 离开临界区 void test(int i) / i为哲学家编号，从0到N-1，思考 if(statei=HUNGRY & stateLEFT!=EATING & stateRIGHT!=EATING) statei=EATING; V(si); 哲学家进餐问题哲学家进餐问题第二章第二章 进程描述与控制进程描述与控制 程序执行一前趋图和程序执行进程的控制二经典的进程同步问题三线程及其实现四v 线程的引入 1. 线程的概念 引入线程主要的原因来自以下四个方面： （1）计算机网络的快速发展 （2）CPU速度的快速提升 （3）编程模式

30、的变化 （4）业务应用的需求2.6 2.6 线程（线程（ThreadsThreads）2.6.1 2.6.1 线程的引入线程的引入v 在操作系统中引入进程的目的是为了使多个程序并发执行，以提高资在操作系统中引入进程的目的是为了使多个程序并发执行，以提高资源的利用率和系统的吞吐量，而在操作系统中引入线程的目的则是为源的利用率和系统的吞吐量，而在操作系统中引入线程的目的则是为了减少程序并发执行时所付出的时空开销，使操作系统具有更好的并了减少程序并发执行时所付出的时空开销，使操作系统具有更好的并发性发性。v 操作系统引入进程后，虽然能使程序并发执行，但由于进程既是一个可以独立调度的基本单位，同时也是

31、一个可拥有资源的单位。因此程序并发执行时，系统必须为进程的创建、撤销和切换付出较大的时空开销。既然这样，系统中所设置的进程数目就不宜太多，进程切换的频率也不宜过高，因此它也限制了程序的并发执行程度。2.6.2 2.6.2 线程与进程的关系线程与进程的关系在引入线程的操作系统中线程和进程具有以下关系：v （1）线程是进程的一部分，它是进程内的一个执行单元。通常，一个进程含有若干个线程，至少也要有一个线程。一个进程的多个线程都在进程的地址空间里活动。v （2）引入线程的操作系统中，资源分配的对象是进程，而不是线程资源分配的对象是进程，而不是线程。进程仍是拥有资源的一个独立单位，它拥有自己的资源，一

32、般地说，线程除有一点必不可少的资源外不拥有系统资源。线程使用的资源是进程分到的资源。v （3）引入线程的操作系统中，调度的基本单位是线程而不是进程调度的基本单位是线程而不是进程。即CPU是分给线程的，真正在CPU上执行的是线程。2.6.2 2.6.2 线程与进程的关系线程与进程的关系v （4）进程之间可以并发执行，而一个进程中的这些线程之间亦可并发执行。而且在并发执行过程中，也需要协作同步。v （5）进程调度，系统要进行进程上下文的切换，需要系统大量的开销。v （6）线程调度，由于同一进程内的线程共享进程的资源，其切换是把线程仅有的一小部分资源变换即可，从而提高了系统的效率。线程切换比进程切换

33、快得多。因此有些人把线程又称为轻型进程。v （7）从一个进程的线程向另一个进程的线程切换，将引起进程的上下文切换。v （8）同一进程的多线程共享进程的所有资源，一个线程可以改变另一个线程的数据，而多进程机制则不会产生这个问题。2.6.3 2.6.3 线程的属性线程的属性 v 轻型实体。v 独立调度和分派的基本单位。v 可并发执行。v 共享进程资源。 (1) 状态参数。 寄存器状态 它包括程序计数器PC和堆栈指针中的内容； 堆栈 在堆栈中通常保存有局部变量和返回地址； 线程运行状态 用于描述线程正处于何种运行状态； 优先级， 描述线程执行的优先程度； 线程专有存储器 用于保存线程自己的局部变量拷贝； 信号屏蔽 即对某些信号加以屏蔽。 2.6.4 2.6.4 线程的状态线程的状态(2) 线程运行状态。 执行状态，表示线程正获得处理机而运行； 就绪状态， 指线程已具备了各种执行条件，一旦获得CPU便可执行的状态； 阻塞状态，指线程在执行中因某事件而受阻，处于暂停执行时的状态。 2.6.4 2.6.4 线程的状态线程的状态2.6.5 2.6.5 多线程多线程OSOS中的进程中的进程 在多线程OS中，进程是作为拥有系统资源的基本单位，通常的进程都包含多个线程并为它们提供资源，但此时的进程就不再作为一个执行的实体。 多线程OS中的进程有