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

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