李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 第 4 讲 进程管理(2) 李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 1/

Presentation on theme: "李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 第 4 讲 进程管理(2) 李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 1/"— Presentation transcript:

1 李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com
第 4 讲 进程管理(2) 李元金 计算机与信息工程学院 1/

2 进程管理 教学目标 理解进程同步、临界资源、临界区的概念； 掌握常用的信号量机制； 理解管程机制。 教学内容 进程同步 2/

3 复习 顺序执行程序的特征 并发执行程序的特征 进程有哪些特征？ 进程有哪些状态？ 进程控制块的作用是什么？ 3/

4 进程同步 进程同步 任务：对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。 4/

5 进程同步的基本概念 两种形式的制约关系 临界资源：（一次仅允许一个进程访问的资源） 资源共享关系：（间接相互制约）
相互合作关系：（直接相互制约） 临界资源：（一次仅允许一个进程访问的资源） 引起不可再现性是因为临界资源没有互斥访问。 5/

6 生产者－消费者问题 Dijkstra把同步问题抽象成一种生产者和消费者关系，计算机系统中的许多问题都可以被归结为生产者和消费者关系，例如，生产者可以是计算进程，消费者是打印进程，输入时输入进程是生产者，计算进程是消费者。我们可以通过一个缓冲区把生产者和消费者联系起来。 in out 6/

7 生产者－消费者问题 var n, integer; Type item=…;
var buffer: array[0,1,…,n-1] of item; in, out: 0,1, …, n-1; counter: 0,1,…,n; 7/

8 生产者－消费者问题 producer: repeat … produce an item in nextp; until false;
while counter=n do no-op; buffer[in]:=nextp; in:=(in+1)mod n; counter:=counter+1; until false; consumer: repeat while counter=0 do no-op; nextc:=buffer[out]; out:=(out+1) mod n; counter:=counter-1; consumer the item in nextc; until false; 8/

9 生产者－消费者问题 设counter的初值为5 register1:=counter; register2:=counter;
register1 :=register1+1; register2:=register2-1; counter :=register1; counter :=register2; register1:=counter; (register1:=5) register1 :=register1+1; (register1:=6) register2:=counter; (register2:=5) register2 :=register2-1; (register2:=4) counter :=register1; (counter:=6) counter :=register2; (counter:=4) 9/

10 临界区 定义：进程中访问临界资源的那段代码。 访问临界资源的描述： 进入区：检查有无进程进入 临界区： 退出区：将访问标志复位 剩余区：
Repeat Entry section Critical section Exit section remainder section Until false 10/

11 同步机制应遵循的准则 同步机制应遵循的规则 空闲让进 忙则等待 有限等待：应保证为有限等待，不会产生死等。
让权等待：不能进入临界区的执行进程应放弃CPU执行权。 11/

12 信号量（Semaphores）机制 1965年，荷兰学者Dijkstra提出信号量机制是一种卓有成效的进程同步工具。 整型信号量
是一个整型量S，通过2个原子操作wait(S)和 signal(S)来访问。(P、V操作) Wait(S): while S<= 0 do no-op; S:=S-1; Signal(S): S:=S+1; 计算机科学与技术系 信息与教育技术中心 12/

13 记录型信号量 由于整型机制中会不断测试不满足“让权等待”而引入。 type semaphore=record value: integer;
L: list of process; end L:为进程链表指针，用于链接所有等待该类资源进程。 procedure wait(s) var S: semaphore begin S.value:=S.value –1; if S.value <0 them block (S.L) 13/

14 记录型信号量 procedure signal (S) var s:semaphone begin S.value:=S.vaule+1
if S.value<=0 then wakeup(S.L) end 在记录型信号量机制中： s.value初值：表示系统中某类资源的数目。 s.value<0,|s.value|表该信号量链表中已阻塞进程的数目。 14/

15 AND型信号量 process A: wait(Dmutex); wait(Emutex); process B:
若两进程交替执行，则死锁 死锁：在无外力作用下,两者都将无法从僵持状态中解脱出来。 AND型信号量特点：要么全分配，要么一个也不分配。 15/

16 for i:=1 to n do Si:=Si-1; endfor else
Swait(S1,S2,…,Sn) if S1≥1 and …and Sn ≥1 then for i:=1 to n do Si:=Si-1; endfor else place the process in the waiting queue with the first Si found with Si<1, and set the program count of this process to the beginning of swait operation end if Ssignal(S1,S2,…,Sn) for i:=1 to n do Si:=Si+1; Remove all the process waiting in the queue associated with Si into the ready queue endfor

17 信号量集 为提高效率而对AND信号的扩充。 三种特例： Swait(S,t,d)： S为信号量，d为需求值，t为下 限值。
Swait (S,1,1)：S>1，记录型信号量。 S=1时，互斥型信号量。 Swait(S,1,0)，可控开关，当s>=1时，允许多个进程进入，S<0时，将阻止任何进程进入特定区。 17/

18 if S1≥t1 and …and Sn ≥tn then for i:=1 to n do Si:=Si-di; endfor else
Swait(S1,t1,d1,…,Sn,tn,dn) if S1≥t1 and …and Sn ≥tn then for i:=1 to n do Si:=Si-di; endfor else place the executing process in the waiting queue of the first Si found with Si<ti, and set the program counter to of the beginning of Swait operation end if Ssignal(S1,d1,…,Sn,dn) for i:=1 to n do Si:=Si+di; Remove all the process waiting in the queue associated with Si into the ready queue endfor

19 信号量的应用 利用信号量实现互斥 wait(S): while S<= 0 do no-op; S:=S-1; 相当于 相当于
var mutex: semaphore:=1 begin parbegin process1:begin repeat wait(mutex); critical setion signal(mutex); remainder section until false; end wait(S): while S<= 0 do no-op; S:=S-1; 相当于 相当于 signal(S): S:=S+1; 19/

20 信号量的应用 process2: begin repeat wait(mutex); critical setion
Wait(S): while S<= 0 do no-op; S:=S-1; process2: begin repeat wait(mutex); critical setion signal(mutex); remainder section until false; end par end signal(S): S:=S+1; 20/

21 信号量的应用 利用信号量实现前趋关系 S1 a b S2 c S3 d S4 S5 e g f S6 图2－12前趋图举例 21/

22 Var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0; Begin parbegin
begin S1; signal(a); signal(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 22/

23 管程机制 为什么要引入管程？ 管程 管程的组成
代表共享资源的数据结构，以及由该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块。 定义(Hansan)：一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。 管程的组成 管程的名称；局部于管程内部的共享数据结构说明；对该数据结构进行操作的一组过程；对局部于管程内部的共享数据设置初始值的语句。 23/

24 管程机制 管程的特征（语言的角度） 管程与进程的区别 模块化 抽象数据类型 信息掩蔽
二者都定义了数据结构，但进程定义的是私有数据结构PCB，管程定义的是公共数据结构； 二者都存在对各自数据结构上的操作，但进程是由顺序程序执行有关的操作，而管程主要是进程同步和初始化操作； 设置进程的目的在于实现系统的并发性，而管程的设置则是解决共享资源的互斥使用问题； 24/

25 管程机制 进程通过调用管程中的过程对共享数据结构实行操作，该过程就如通常的子程序一样被调用，因而管程为被动工作方式，进程则为主动工作方式；
进程之间能并发执行，而管程则不能与其调用者并发； 进程具有动态性，管程则是操作系统中的一个资源管理模块，供进程调用。 25/

26 管程机制 条件变量 引入条件变量的原因 条件变量的说明：x,y:condition (wait,signal)
x.wait; x.signal 含义 x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列上，并释放管程，直到x条件发生了变化。 26/

27 管程机制 x.signal: 正在调用管程的进程发现x条件发生了变化， 则调用x.signal，重新启动一个因x条件而阻塞或挂起
的进程。如果存在多个这样的进程，则选择其中的一 个，如果没有，则继续执行原进程，而不产生任何结 果。 【问题】如果有进程Q因x条件处于阻塞状态，当正 在调用管程的进程P执行了x.signal操作后，进程Q被 重新启动，此时两个进程P和Q,如何确定哪个执行， 哪个等待？ 27/

28 小结 进程的同步、临界资源、临界去的概念。 进程同步的信号量机制及应用、管程机制。 28/

29 作业 P 实验一： Linux基本操作 29/