操作系统--进程管理

1、3.3 进程(jnchng)控制3.3.1 进程控制的概念 系统使用具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换的过程。通过进程控制，可以达到多进程高效率并发执行，同时也能很好地协调(xitio)并发进程之间的推进速度，实现资源共享。操作系统中是通过原语来完成对进程的控制。原语：操作系统提供的为完成某系统功能的最基本的不可分割的操作。原语是不允许并发执行的。原语分为机器指令级的原语和功能级原语两类，它们都在核心态下执行。控制进程的原语：创建、撤消、阻塞、唤醒等1共六十二页3.3.2 进程的创建与撤销1、进程的创建：（1）、创建进程的典型事件批处理系统中的作业调度；用户登录；用

2、户启动应用程序；由操作系统创建的系统服务；创建新的进程。（2）、创建方式：A）由系统程序统一(tngy)创建B）由父进程创建不管用那种方式创建进程，都是调用创建进程原语实现的2共六十二页(3)创建进程原语的工作(gngzu)过程A)申请空闲的PCB表项B)填PCB表的内容C)把当前PCB加入就绪队列D)将当前PCB加入进程家族或进程链(4)进程控制块常用数据项Idi:进程标识符;i.status:进程状态;i.state:队列指针;i.Addr:队列中;i.Priority:进程优先数;i.CPU-state:CPU的状态保护区i.mainstore:分配的主存储区域;i.resource:资

3、源清单;i.parent:父进程指针;geny:后代进程指针.3共六十二页(5)创建(chungjin)原语算法void create(n,s0,k0,m0,r0,acc)i=getinternal-name(n);i.id=n;i.priority=k0;i.CPU-state=s0;i.mainstore=m0;i.resource=r0;i.status=“ready”;j=*Ep;i.parent=j;geny=nil;geny=I;i.state=RL;insert(RL,i)4共六十二页2、进程的撤消(1)撤消进程的原因:A)进程完成任务(rn wu)

4、,正常终止B)进程运行出错异常终止C)其祖先进程要求撤消不管由于哪种原因撤消进程,都是调用撤消进程原语实现的.进程的撤消方式有两种:A)仅撤消该PID代表的进程B)撤消该PID代表的进程及其所有子孙进程这两种方式各有优缺点5共六十二页(2)撤消进程原语的工作过程:A)根据进程PID查找(ch zho)进程链或进程家族,a)如找到,则看其有无子进程,如有:再调用撤消进程原语继续查找,若无,继续执行Bb)若未找到,做出错处理B)释放该进程所占有的资源C)释放该进程的PCBD)返回6共六十二页(3)撤消原语算法(sun f)描述void destroy(n)i=getinternal-name(n)

5、;sched=false;kill(i);if (sched=true) scheduler;else continue;kill (i)if (i.status=“ready”)stop(i);sched=ture;while (geny) kill(s);remove(i.state,i);7共六十二页3.4.3 进程(jnchng)等待与唤醒1、进程等待阻塞原语的工作过程A)保存当前进程的CPU现场B)将其状态修改(xigi)为等待状态C)将其插入对应的等待队列D)转进程调度程序阻塞原语的算法描述void block(WQr)i=*EP;/*取得调用者进程的PCB*/stop

6、(i);/*剥夺CPU*/i.status=”blocked”/*将进程i的状态置为阻塞状态*/i.state=WQr;/*填入所在队列的首指针*/insert(WQr);/*插入相应阻塞队列*/scheduler;/*进程调度*/8共六十二页2、进程唤醒唤醒原语的工作过程:A)根据唤醒原因,从对应的等待队列中摘下一PCBB)将其状态(zhungti)修改为就绪状态(zhungti)C)将其插入就绪队列D)转进程调度程序或返回唤醒原语的算法描述:void wakeup(WQr)i=remove(WQr);/*查找并得到PCB(n)，从阻塞队列wQr中移出n*/i.status=”ready”;

7、/*置进程i的状态为就绪状态*/i.state=RQ;/*填入所在队列的首指针*/insert(RQ，i);/*插入就绪队列RQ*/scheduler;/*进程调度*/9共六十二页3.4 进 程 协作与系统(xtng)的支持 3.4.1 进程竞争(jngzhng)与合作 1、间接制约：由共享公有资源而造成的对并发进程执行速度的间接制约，称为间接制约；受相互间接制约的各进程在推进顺序上是任意的。2、直接制约：一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程的直接制约。10共六十二页3.4.2 进程互斥的概念1、临界资源：在一段时间内只允许一

8、个进程使用的资源2、临界区（临界段）：进程中访问临界资源的代码段3、进程互斥：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须(bx)以一个不允许交叉执行的单位执行。也就是说，不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。4、同步机构应遵循的准则(1) 空闲让进。(2) 忙则等待。 (3) 有限等待。 (4) 让权等待。11共六十二页3.4.3 上锁原语和开锁原语1、信号量（信号灯）1）问题的引入：为临界资源(zyun)S设置锁key，当key为1时，资源可用，否则不可用。Lock(keys)测试key，若key为1,则将key赋值为0并退出，unlock（ke

9、ys)则将key赋值为1。PA：A：lock(keys)Unlock(keys)GOTO APB：B：lock(keys)Unlock(keys)GOTO B结果：容易导致一个(y )进程饥饿12共六十二页2）信号量定义(dngy)：信号量：除赋初值外仅能由同步原语（P、V操作）对其操作的整型变量，其值与其代表的资源使用情况有关。信号量的物理意义：当其值0时，代表可用资源的数量。当其值0时，其绝对值代表因请求使用该信号量所代表的资源而被阻塞的进程数量。3）建立一个信号量时，必须说明所建信号量所代表的意义和赋初值13共六十二页4）信号量的分类：按其数据类型分类：整型信号量记录型信号量Struct

10、 semaphore int value;Pointer:*struct PCB;5)信号量的初值：由于信号量是代表(dibio)资源的相关属性的，因此，其初值就应该为当前该资源的可使用数量。如：我们设定用信号量S代表系统内的打印机资源，系统内有5台打印机，则S的初值就应该为5。14共六十二页3.4.4 P、V原语P、V原语是操作系统中提供(tgng)的用于对进程之间相互推进速度进行控制的最基本的操作。它操作的对象只能是信号量。1）P(sem)原语的主要动作：sem=sem-1若sem0，则返回否则调用阻塞原语把当前进程阻塞转进程调度程序15共六十二页2）V(sem)原语的主要动作：sem=s

11、em+1若sem0，则返回否则调用唤醒原语把当前阻塞队列中的对首进程唤醒或全部唤醒转进程调度程序(chngx)或返回3、P、V原语的实现P原语的实现P（sem):关中断Lock(lockbit)/用于防止多个进程同时调用P,V操作Valsem=valsem-1If valsem0调用阻塞原语相关功能Unlock(lockbit)开中断 16共六十二页V原语的实现V（sem):关中断Lock(lockbit)/用于防止多个进程同时调用P,V操作Valsem=valsem+1If valsem=0调用唤醒原语相关功能Unlock(lockbit)开中断 4、P、V原语实现互斥用P、V原语实现进程互

12、斥：（1）定义信号量，必须说明其所代表的资源(zyun)（2）设定信号量的初值：1（3）在临界段进入区执行：P（信号量）操作（4）在临界段退出区执行：V（信号量）操作17共六十二页例如：有两个用户进程A和B，在运行过程中都要使用系统中的一台打印机输出计算结果。(1) 试说明A、B两进程之间存在什么样的制约关系？(2) 为保证这两个进程能正确地打印出各自(gz)的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。18共六十二页（1）A、B两进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用(shyng)完之后另一个进程才能使用(shy

13、ng)。（2）mutex：用于互斥的信号量，因为只有一台打印机，所以初值为1。进程A 进程B. . .P(mutex)； P(mutex)；申请打印机； 申请打印机；使用(shyng)打印机； 使用(shyng)打印机；V(mutex)； V(mutex)； 19共六十二页作业：系统有三个进程Read,Write1,Write2共享一个(y )整数缓冲器b,b中每次只能存放一个整数。Read进程每次启动输入设备输入一个整数到b。若b中是奇数，则由进程Write1将其取出打印；若b中是偶数，则由进程Write2将其取出打印。规定输入与打印整数的个数和次序完全一致。（用、原语实现）20共六十二页

14、1. 整型信号量 最初由Dijkstra把整型信号量定义为一个(y )整型量，除初始化外，仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。 wait和signal操作可描述为： wait(S): while S0 do no-op S=S-1; signal(S): S =S+1; 3.4.5 信号量机制(jzh) 21共六十二页 2. 记录型信号量 在整型信号量机制中的wait操作，只要是信号量S0， 就会不断地测试。因此，该机制并未遵循“让权等待”的准则， 而是使进程处于“忙等”的状态。记录型信号

15、量机制，则是一种(y zhn)不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为： 22共六十二页type semaphore=record value:integer; L:list of process; end相应地，wait(S)和signal(S)操作(cozu)可描述为：procedure wait(S) var S

16、: semaphore; begin S.value =S.value-1; if S.value0 then block(S,L) end procedure signal(S) var S: semaphore; begin S.value =S.value+1; if S.value0 then wakeup(S,L); end 23共六十二页 在记录型信号量机制中，S.value的初值表示系统中某类资源的数目， 因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，因此描述为S.value =S.value-1； 当S.value0时，表示该类资源已分配完毕，

17、因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。可见，该机制遵循了“让权等待”准则(zhnz)。 此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。 对信号量的每次signal操作，表示执行进程释放一个单位资源，故S.value =S.value+1操作表示资源数目加1。 若加1后仍是S.value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。 24共六十二页3. AND型信号量

18、在两个进程中都要包含两个对Dmutex和Emutex的操作， 即process A: process B:wait(Dmutex); wait(Emutex);wait(Emutex); wait(Dmutex);若进程A和B按下述次序交替执行wait操作：process A: wait(Dmutex); 于是(ysh)Dmutex=0process B: wait(Emutex); 于是Emutex=0process A: wait(Emutex); 于是Emutex=-1 A阻塞process B: wait(Dmutex); 于是Dmutex=-1 B阻塞 25共六十二页 AND同步机制

19、的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。 由死锁理论可知，这样(zhyng)就可避免上述死锁情况的发生。为此，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作， 即Swait(Simultaneous wait)定义如下： 26共六十二页Swait(S1, S2, , Sn) if Si1 and and Sn1 then for i =1

20、 to n do Si=Si-1; endfor else place the process in the waiting queue associated with the first Si found with Si1, and set the program count of this process to the beginning of Swait operation endifSsignal(S1, S2, , Sn) for i =1 to n do Si=Si+1; Remove all the process waiting in the queue associated

21、with Si into the ready queue. endfor; 27共六十二页4. 信号量集 Swait(S1, t1, d1, , Sn, tn, dn) if Sit1 and and Sntn then for i=1 to n do Si=Si-di; endfor else Place the executing process in the waiting queue of the first Si with Siti and set its program counter to the beginning of the Swait Operation. endif s

22、ignal(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; 28共六十二页 一般“信号量集”的几种(j zhn)特殊情况： (1) Swait(S, d, d)。 此时在信号量集中只有一个信号量S， 但允许它每次申请d个资源，当现有资源数少于d时，不予分配。 (2) Swait(S, 1, 1)。 此时的信号量集已蜕化为一般的记录型信号量(S1时)或互斥信号量(S=1时)。

23、 (3) Swait(S, 1, 0)。这是一种很特殊且很有用的信号量操作。当S1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。 29共六十二页3.4.6 信号量的应用(yngyng) 1. 利用(lyng)信号量实现进程互斥 利用信号量实现进程互斥的进程可描述如下：Var mutex:semaphore =1; begin parbegin process 1: begin repeat wait(mutex); critical section signal(mutex); remainder seetion until false;

24、30共六十二页 end process 2: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end parend 31共六十二页2. 利用信号量实现(shxin)前趋关系 前趋图举例(j l) 32共六十二页 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); sig

25、nal(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 33共六十二页作业：系统有三个进程Read,Write1,Write2共享一个整数缓冲器b,b中每次只能存放一个整数。Read进程每次启动输入设备输入一个整数到b。若b中是奇数，则由进程Write1将其取出打印；若b中是偶数，则由进程Write2将其取出打印

26、。规定输入与打印整数的个数和次序(cx)完全一致。（用、原语实现）34共六十二页3.5.1、同步的定义同步的定义：一组并发进程由于相互合作共同完成某种任务，因而相互等待，使得各进程按一定的速度执行的过程(guchng)。互斥是一种特殊的同步。私用信号量：只与制约和被制约进程有关的信号量。用于同步的信号量。例：分析：根据题意可知：只有当缓冲队列有一个及一个以上满缓冲时，Pb才可以继续执行，否则等待Pa发送数据；PbPaBufnBuf2Buf13.5 进程同步的概念(ginin)35共六十二页同理只有当缓冲队列中有一个及一个以上空缓冲时，Pa才可以继续执行，否则等待Pb取走数据(shj)；因此，P

27、a和Pb之间存在同步关系。信号量的设定：设代表满缓冲区数量的信号量为Full设代表空缓冲区数量的信号量为Empty设初值：Full=0, Empty=n36共六十二页3.5.2 用P、V实现进程同步示例生产者-消费者问题(wnt)分析1 2 3 np1p2pmc1c2cm分析生产者进程(jnchng)与消费者进程(jnchng)间的同步互斥关系1）生产者进程间（互斥）2）消费者进程间（互斥）3）生产者-消费者之间（同步互斥）37共六十二页信号量设定：设代表非空缓冲区数量的信号量为full,代表空缓冲区数量的信号量为empty，代表缓冲区资源使用情况的信号量为mutex(互斥）设定初值：full

28、=0,empty=n,mutex=1书写(shxi)算法：1、生产者首先申请空缓冲区资源，若无则等待申请占用缓冲区(why)查找空闲缓冲区，在找到的空缓冲区中填入数据，置满缓冲标志。放弃对缓冲区的占用，增加可用满缓冲数量38共六十二页2、消费者：首先申请满缓冲资源(zyun)，若无则等待申请占用缓冲区(why)查找满缓冲区，从找到的满缓冲区中取走数据，置空闲缓冲标志放弃对缓冲区的占用，增加可用空缓冲区数量main() int full=0; int empty=n int mutex=1; cobegin p1();p2();pm(); c1();c2();ck(); coend;39共六十二

29、页producer()while(生产(shngchn)未完成）生产一个产品；P(empty);P(mutex);送数据入缓冲区某单元；V(full);V(mutex);consumer()while(还要继续消费）P(full);P(mutex);取缓冲区某单元(dnyun)数据；V(empty);V(mutex);消费一个产品；40共六十二页3.5.2 用消息通信(tng xn)实现哲学家进餐问题分析:每个哲学家的行为是：思考，感到饥饿，拿到两只筷子，进餐，餐毕，放下两只筷子又继续思考。为了(wi le)进餐，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。但他可

30、能一支都拿不到。只有在他拿到两支筷子时方能进餐。设置信号量如下：哲学家进餐信号量sm，初值为4；筷子信号量chopsticki，初值为1；哲学家进餐问题描述如下:41共六十二页semaphore sm=4；semaphore chopstick5=1，1，1，1，1;void main()parbegin(philosopher0()，philosopher1()，philosopher2()，philosopher3()，philosopher4();void philosopheri();/*i=0，1，2，3，4*/while (true) Thinking; wait(sm); wai

31、t(chopsticki); wait(chopstick(i+1)%5); Eating; signal(chopstick(i+1)%5); signal(chopsticki); signal(sm); 42共六十二页3.6 进程(jnchng)通信3.6.1进程通信的概念进程通信：进程间数据的传递过程。进程通信分类：1）低级(dj)通信：进程之间传送数据量很小，一般都是用来传送控制信息，从而实现进程之间的同步和互斥。2）高级通信：进程之间进行大量数据传送的通信方式。其主要目的是为了交换信息。 进程的高级通信有三种形式：共享存储器通信方式、共享文件通信方式、消息传递通信方式。43共六十二

32、页还可以把进程通信分为直接通信和间接通信1）直接通信：是指发送方把信息直接传递给接收方。2）间接通信：是指通信过程要借助收发双方进程之外的共享数据结构作为(zuwi)通信中转如信箱。44共六十二页3.6.2 进程通信(tng xn)方式一、共享存储器的通信(tng xn)方式基于(jy)共享存储区通信方式基于共享数据结构的通信方式45共六十二页linux中共享存储区的创建、附接和断接（1）使用系统调用shmget(key,size,flag)获得一个共享存储区。（2）使用系统调用shmat(id,addr,flag)从逻辑上将(shngjing)一个共享存储区附接到进程的虚拟地址空间上。（3）

33、使用系统调用shmdt(addr)把一个共享存储区从指定进程的虚地址空间分开。（4）使用系统调用 shmctl(id,cmd,buf)对与共享存储区关联的各种参数进行操作，从而对共享存储区进行控制。 46共六十二页实验内容：编制一长度为1k的共享存储区发送和接收程序。 (1)为了便于操作和观察结果，用一个程序为“引子”，先后fork( )两个子进程，SERVER 和 CLIENT，进行通信。 (2)SERVER端建立一个KEY为75的共享区,并将第一个字节置为-1.作为数据空的标志.等待其他进程发来的消息.当该字节的值发生变化时,表示(biosh)收到了该消息,进行处理.然后再次把它 的值设为

34、-1.如果遇到的值为0,则视为结束信号,取消该队列,并退出SERVER.SERVER每接 收到一次数据后显示”(server)received”. (3)CLIENT端建立一个为75的共享区,当共享取得第一个字节为-1时, Server端空闲,可发送 请求. CLIENT 随即填入9到0.期间等待Server端再次空闲.进行完这些操作后, CLIENT 退出. CLIENT每发送一次数据后显示”(client)sent”. (4)父进程在SERVER和CLIENT均退出后结束. 47共六十二页二、共享文件(wnjin)通信方式1、通信方式 管道为建立管道的进程及其子孙进程提供了一条以比特流方式

35、传出消息的通信管道。管道在逻辑上被看作文件，物理(wl)上是由文件系统的高速缓冲区构成。48共六十二页发送：发送进程用文件系统的系统调用write(fd1,buf,size),把buf长度为size的消息送入管道入口fd1接收：接收进程则使用系统调用read(fd0,buf,size)从管道出口fd0读出size字符的消息送入buf中。注意：管道按FIFO（先进先出）方式传送(chun sn)消息，且为单向传送(chun sn)。2、算法先定义一个整型：int fd2,其中fd1为写入端，fd0为读出端，然后用调用pipe(fd)建立管道，最后调用write,read完成具体的读写。49共六十

36、二页3、示例#include main( ) int x,fd2;char buf30,s30;pipe(fd);/*创建管道*/while (x=fork()=-1);/*创建子进程失败(shbi)时，循环*/if(x=0)sprintf(buf,”This is an exmplen”);write(fd1,buf,30);/*写管道*/exit(0);elsewait(0);read(fd0,s,30);/*读管道*/printf(“%s”,s);50共六十二页三、消息传递通信(tng xn)方式不论是单机系统、多机系统，还是计算机网络，消息传递机制都是用得最广泛的一种进程间通信的机制。

37、在消息传递系统中，进程间的数据交换，是以格式化的消息(message)为单位的；在计算机网络中，又把message称为报文。程序员直接利用系统提供的一组通信命令(原语)进行通信。消息传递通信一般分为消息缓冲通信、信箱通信和基于消息传递通信等三种。 1、消息缓冲通信的实现 （1）、通信方式 发送进程在发送之前，先在自己的内存空间中设置一个发送区，把欲发送的消息填入其中，然后再用发送过程将其发送出去。接收(jishu)进程在接受之前，在自己的内存空间中设置相应的接收(jishu)区，然后用接收(jishu)过程接受消息。51共六十二页两个进程通信(tng xn)过程：52共六十二页（2）、通信的必

38、要条件在发送进程将消息写入缓冲区和把缓冲区挂入接收进程的消息队列时，应禁止其他进程对消息队列的访问，接收进程从消息队列取消息缓冲时，也应禁止其他进程对消息队列的访问（即消息队列是临界资源(zyun)，需互斥访问）当缓冲区中无消息时，接收进程不能接收消息。（3）、linux中的消息缓冲通信使用系统调用msgget(key,flag)获得一个消息的描述符，该描述符指定一个消息队列以便用于其他系统调用。 53共六十二页使用系统调用(dioyng)msgsnd(id,msgp,size,flag)发送一消息。使用系统调用msgrcv(id,msgp,size,type,flag)接收一消息。 使用系统

39、调用msgctl(id,cmd,buf)查询一个消息描述符的状态，设置它的状态及删除一个消息描述符。 54共六十二页2、信箱通信(tng xn)的实现（1）通信方式概述：由发送进程申请建立(jinl)一与接收进程连接的邮箱，双方通过邮箱交换信息，邮箱可视为发送进程与接收进程之间的大小固定的私有数据结构。邮箱的结构55共六十二页（2）通信的必要条件（一对一发送和接收为例）发送消息时，邮箱中至少(zhsho)要有一个空格能存放消息接收消息时，邮箱中至少要有一个消息存在（3）通信算法由上述分析可知，发送进程和接收进程之间存在同步关系，可以设以下信号量：fromnum:表示邮箱中的空格数，初值为n,(n为总格数）mesnum：表示邮箱中的消息个数，初值为056共六十二页发送(f sn)过程send(Mailbox,m):BeginLocal xP(fromnum)选择空格x将消息放入空格x,置格x的标志为满V(mesnum)End.接收过程receive(Mailbox,x):BeginP(mesnum)选择满格x将满格x的消息取出放入m中，置格x的标志为空V(fromnum)End.57共六十二页3、基于(jy)消息传递的通信基于消息传递的通信方式，不仅适合计算机内部