计算机操作系统之进程管理

第二章进程管理•2.1.1程序的顺序执行及特征o一、程序执行有固定的时序。（图2-1p27）o二、特征：顺序性、封闭性、可再现性2.1进程的基本概念I1C1P1I2C2P22.1.2前趋图定义•有向无循环图•表示方式：o（1）p1---p2o（2）---={(p1,p2)|p1必须在p2开始前完成}•（图2-2P27）•节点表示：一条语句，一个程序段，一进程。P1P1P1P12.1.3程序的并发执行•一、多个程序的并发执行（可能性分析）I1I2I3I4C1C2C3C4P1P2P3P4t程序的并发执行(2)•二、特征o间断性o失去封闭性：主要由共享资源引起o不可再现性：P29例，设N的初值为n。o有2个循环程序A和B，它们共享一个变量N，程序A每执行一次时，都要做N:=N+1;B则每次要执行Print(N),然后再做N:=0.若程序A,B以不同的速度运行有以下三种不同的结果程序的并发执行(3)•N:=N+1在print(N)和N:=0之前，则N值分别为n+1,n+1,0.•N:=N+1在print(N)和N:=0之后，则N值分别为n,0，1.•N:=N+1在print(N)和N:=0之间，则N值分别为n,n+1,0.2.1.4进程的特征和状态•1.进程的特征和定义o一、定义：程序的一次执行过程o1.结构特征进程：由程序段、数据段及进程控制块三部分构成，总称“进程映像”。o2.动态性由“创建”而产生，由“调度”而执行；由得不到资源而阻塞；由撤消而消亡。（而程序是静态的）。2.1.4进程的特征和状态(2)•3.并发性o只有建立了进程，才能并发执行。•4.独立性。o独立运行，独立获得资源。•5.异步性：（间断性）2.1.4进程的特征和状态(3)•2.进程的三种基本状态（图2-5p31）o就绪状态o执行状态o阻塞状态就绪阻塞执行时间片完进程调度I/O请求I/O完成图2－5进程的三种基本状态及其转换2.1.4进程的特征和状态(4)•3.挂起状态（被换出内存的状态）o引入原因终端用户请求父进程请求负荷调节需要操作系统需要o进程状态的转换(图2-6)活动就绪•静止就绪活动阻塞•静止阻塞静止就绪•活动就绪静止阻塞•活动阻塞图2－6具有挂起状态的进程状态图执行活动就绪静止就绪活动阻塞静止阻塞激活挂起激活挂起释放释放挂起请求I/O实验•写一个程序描述进程状态迁移过程。•要求：o提供导致进程状态变化的调用接口，包括创建、删除、调度、阻塞、时间到、挂起、激活等。o实现进程列表显示的接口。o注：这里设计的进程是一个假设的对象实体，是由程序自己创建和删除，不是系统维护的进程。2.1.5进程控制块•1.进程控制块的作用o是进程存在的唯一标志；oPCB(processcontrolblock)常驻内存•2.进程控制块中的信息o标识、处理机状态，进程调度信息，进程控制信息链接指针资源清单同步机制程序地址阻塞原因优先级现场进程状态pid2.1.5进程控制块(2)•3.PCB的组织o链接（p33图2-7）o索引(p34图2-8)执行指针就绪队列指针阻塞队列指针空闲队列指针1PCB90PCB89PCB77PCB6PCB58PCB40PCB33PCB24PCB1等待队列示例structwait_queue{structtask_struct*task;structwait_queue*next;};PCBPCBPCB2.1.5进程控制块(3)•3.PCB的组织o索引(p34图2-8)PCB7PCB6PCB5PCB4PCB3PCB2PCB1执行指针就绪表指针阻塞表指针补充•PCB和进程的代码数据放在一起吗？o系统态和用户态o系统空间和用户空间•系统调用和普通调用的区别？o系统调用会引起从用户态进入核心态2.2进程控制•2.2.1进程的创建•一、进程图：o描述了进程的家族关系：（P34图2-9）o子进程可继承父的资源，撤消时应归还给父进程，父的撤消会撤消全部子进程。•二、引起创建进程的事件：o1.用户登录：为终端用户建立一进程o2.作业调度：（不是进程调度）为被调度的作业建立进程o3.提供服务：如要打印时建立打印进程2.2.1进程的创建(2)•4.应用请求：o由应用程序建立多个进程•三、进程的创建：（creat原语）o1.申请空白PCB（一个系统的PCB是有限的）o2.为新进程分配资源（不同于一般的分配，PCB-LIST在一个特殊区域）o3.初始化PCBo4.将新进程插入就绪队列。2.2.2进程的终止•一、引起进程终止的事件o1.正常结束：如Halt、logoffo2.异常结束：如Protecterror、overtime等o3.外界干预：a.系统员kill进程；b.父进程终止；c.父进程请求。2.2.2进程的终止(2)•二、进程的终止过程o（1）检查进程状态；o（2）执行态――中止，且置调度标志为真。o（3）有无子孙需终止。o（4）归还资源给其父进程或系统。o（5）从PCB队列中移出PCB.2.2.3进程的阻塞与唤醒•一、引起进程阻塞和唤醒的事件o1.请求系统服务而得不到满足时，如问系统请求打印。o2.启动某种操作而需同步时：如该操作和请求该操作的进程需同步运行（即非异步操作）。o3.新数据尚未到达：如进程A写，进程B读，则A未写，完B不能读。o4.无新工作可做。2.2.3进程的阻塞与唤醒(2)•二、进程阻塞过程：o是进程自身的一种主动行为oa.调block原语ob.停止执行，修改PCB入阻塞队列（一个或多个），并转调度。•三、唤醒过程o其它相关进程完成。oa.wakeup原语ob.修改PCB，入就绪队列o可见，有block原语，在其它进程中就应有wakeup原语。2.2.4进程的挂起与激活•一、进程的挂起过程o由进程自己或其父进程调suspend原语完成，将该进程PCB移到指定区域，注意状态的改变，有可能要重新调度。•二、进程的激活过程。oactive原语（如在外存，调入内存，改变状态，根据情况看是否调度，如抢先或非抢先）。•阻塞、唤醒一般由OS实现，而挂起与激活可由用户干预。2.3进程同步•同步：并发进程在执行次序上的协调，以达到有效的资源共享和相互合作，使程序执行有可再现性。2.3.1进程同步的基本概念•1.两种形式的制约关系o资源共享关系：（进程间接制约）需互斥地访问临界资源。o相互合作关系：（进程直接制约）•2.临界资源：（一次仅允许一个进程访问的资源）o引起不可再现性是因为临界资源没有互斥访问。生产者－消费者问题Varn,integer;Typeitem=…;varbuffer:array[0,1,…,n-1]ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;生产者－消费者问题producer:repeat…produceaniteminnextp;…whilecounter=ndono-op;buffer[in]:=nextp;in:=(in+1)modn;counter:=counter+1;untilfalse;consumer:repeatwhilecounter=0dono-op;nextc:=buffer[out];out:=(out+1)modn;counter:=counter-1;consumertheiteminnextc;untilfalse;生产者－消费者问题（2）设counter的初值为5register1:=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)•定义：进程访问临界资源的那段代码。•访问临界资源的描述：进入区：检查有无进程进入临界区：退出区：将访问标志复位RepeatEntrysectionCriticalsectionExitsectionUntilfalse3.临界区4.同步机制应遵循的准则•1.空闲让进•2.忙则等待•3.有限等待：应保证为有限等待，不会产生死等。•4.让权等待：不能进入临界区的执行进程应放弃CPU执行权。2.3.2信号量机制•1整型信号量o是一个整型量，通过2个原子操作wait(s)和signal(s)来访问。Wait(s):whiles=0dono-ops:=s-1;Signal(s):s:=s+1;2记录型信号量•由于整型机制中会不断测试不满足“让权等待”而引入typesemaphore=recordvalue:integer;L:listofprocess;endL:为进程链表，用于链接所有等待该类资源进程。procedurewait(s)vars:semaphorebegins.value:=s.value–1;ifs.value0themblock(S,L)end2记录型信号量(2)proceduresignal(S)vars:semaphonebegins.value:=s.vaule+1ifs.value=0thenwakeup(s.L)end用wait(s)和signal(s)实现同步与互斥。在记录型信号量机制中：s.value初值：表示系统中某类资源的数目。s.value0:表该信号量链表中已阻塞进程的数目。3AND型信号量•当不用它时，有可能发生系统死锁。•死锁：在无外力作用下的一种僵持状态。•AND信号量例：P42.•特点：要么全分配，要么一个也不分配。3AND型信号量processA:wait(Dmutex);wait(Emutex);processB:wait(Emutex);wait(Dmutex);若2进程交替执行，则死锁3AND型信号量Swait(s1,s2,…,sn)ifs1≥1and…andsn≥1thenfori:=1tondosi:=si-1;endforelseplacetheprocessinthewaitingqueuewiththefirstsifoundwithsi1,andsettheprogramcountofthisprocesstothebeginningofswaitoperationendifSsignal(s1,s2,…,sn)fori:=1tondosi:=si+1;removealltheprocesswaitinginthequeueassociatedwithsiintothereadyqueueendfor4信号量集(略)•为提高效率而对AND信号的扩充。（P43）•三种特例：•（1）Swait(S,d,d)：允许每次申请d个资源。当资源数少于d时，不予分配。•（2）Swait(s,1,1)：S1，记录型信号量。S=1时，互斥型信号量。•（3）Swait(s,1,0)，可控开关，当时，允许进入，S1时，不能进入。2.3.3信号量的应用•1.利用信号量实现互斥varmutex:semaphore:=1beginparbeginprocess1:beginrepeatwait(mutex);criticalsetionsignal(mutex);remaindersectionuntilfalse;end1.利用信号量实现互斥(2)process2:beginrepeatwait(mutex);criticalsetionsignal(mutex);remaindersectionuntilfalse;endparend2.利用信号量来描述前趋关系(1)S1S