第2章-进程管理

第2章进程管理2.1进程（Process）2.2进程控制2.3进程同步2.4经典进程同步问题2.5进程间通信2.6线程（Thread）2.7小结2.1进程(Process)一、什么是进程？是程序的1次执行。或者说,进程是程序执行的1个实例。每个进程都有自己的地址空间。为什么要引入进程？2.1进程(Process)二、进程和程序的关系与差异程序是进程的静态实体（即执行代码）。程序是静态的，进程是动态的。同一个程序可以对应多个进程，每启动1次产生1个进程。启动执行（进程）程序1程序2程序3第1次执行（进程）第2次执行（进程）第3次执行（进程）同一个程序进程和程序的关系与差异2.1进程(Process)1.进程的5种基本状态（1）新建（new）：进程正在被创建。（2）就绪（ready）：进程可运行，正等待获得处理机。（3）运行（running）：进程的指令正在被执行。（4）阻塞（blocked）或等待：进程因等待某事件（如请求I/O）而暂停执行。（5）完成（done）：进程结束。三、进程的状态由于OS在建立一个新进程时，通常分为2步：第一步是创建进程，并为其分配资源，此时进程即处于new状态。第二步是把新创建的进程送入就绪队列，状态变为就绪状态。一个结束了的进程，其退出系统的过程也分为两步：第一步是将该进程从就绪队列中移出，使之成为一个不可能再运行的进程，相应的进程处于done状态。此时系统并不立即撤销它，而是将它暂时留在系统中，以便其它进程去收集该进程的有关信息。引入new和done状态的原因：进程的状态newreadyrunningdoneblocked创建成功正常或异常终止I/O完成或等待的事件发生I/O请求或等待某事件被OS选中执行时间片到或被剥夺2.状态之间的转换进程的状态3.七状态进程模型在有的系统中，为了暂时缓和内存的紧张状态，或为了调节系统负荷，又引入了挂起（suspend）功能：暂时挂起一部分进程，把它们从内存临时换出到外存。就绪状态分为2种：活动就绪状态（未被挂起的就绪进程）和静止就绪状态（被挂起的就绪进程）阻塞状态分为2种：活动阻塞状态（未被挂起的阻塞进程）和静止阻塞状态（被挂起的阻塞进程）进程的状态就绪(Ready)：进程在内存且可立即进入运行状态阻塞(Blocked)：进程在内存并等待某事件的出现阻塞挂起(Blocked,suspend)：进程在外存并等待某事件的出现就绪挂起(Ready,suspend)：进程在外存，但只要进入内存，即可运行运行新建完成七状态进程模型挂起（Suspend）：把一个进程从内存转到外存；可能有以下几种情况：阻塞→阻塞挂起：没有进程处于就绪状态或就绪进程要求更多内存资源时，可能发生这种转换，以提交新进程或运行就绪进程就绪→就绪挂起：当有高优先级阻塞（系统认为会很快就绪的）进程和低优先级就绪进程时，系统可能会选择挂起低优先级就绪进程运行→就绪挂起：对抢占式系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态七状态进程模型激活（Activate）：把一个进程从外存转到内存；可能有以下几种情况：就绪挂起→就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程时，可能发生这种转换阻塞挂起→阻塞：当一个进程释放足够内存时，系统可能会把一个高优先级阻塞挂起（系统认为会很快出现所等待的事件）进程从外存转到内存七状态进程模型激活挂起事件发生事件发生等待事件挂起调度超时释放激活挂起七状态进程模型2.1进程(Process)四、进程的描述进程控制块（ProcessControlBlock,PCB）1.PCB是什么？是OS管理和控制进程的数据结构。PCB记录着进程的描述信息。每个进程对应1个PCB。进程的描述PCB是进程的一部分进程由3部分组成：程序、数据、PCB。PCB伴随着进程的整个生命周期。进程创建时，由OS创建PCB;进程终止时，由OS撤消PCB；进程运行时，以PCB作为调度依据。2.PCB的作用进程的描述（1）进程本身的标识信息进程标识符pid(processID)：整数，由OS分配，唯一用户标识符uid(userID)：创建该进程的用户对应程序的地址：内存、外存3.PCB中的主要信息（2）CPU现场-为进程正确切换所需所有寄存器的值或称进程上下文(context)PCB中的主要信息（3）进程调度信息进程的状态优先级使进程阻塞的条件占用CPU、等待CPU的时间（用于动态调整优先级）（4）进程占用资源的信息进程间同步和通信机制，如信号量、消息队列指针打开文件的信息，如文件描述符表进程的描述一般来说，系统把所有PCB组织在一起，并把它们放在内存的固定区域，构成PCB表。PCB表的大小决定了系统中最多可同时存在的进程个数。4.PCB的组织方式空闲PCB队列头指针阻塞队列头指针就绪队列头指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB84308790PCB920执行进程指针PCB的组织方式同一状态进程的PCB组成一个链表，不同状态对应多个不同的链表，如就绪链表、阻塞链表索引表就绪队列阻塞队列1阻塞队列2PCB1PCB2PCB3PCB4PCB5PCB6PCB7…PCBnPCB表PCB的组织方式对具有相同状态的进程，分别设置各自的索引表，表明其PCB在PCB表中的地址PCB的组织方式创建、撤消进程以及完成进程各状态之间的转换，由具有特定功能的原语完成进程创建原语进程撤消原语阻塞原语唤醒原语挂起原语激活（解挂）原语改变进程优先级2.2进程控制创建一个PCB赋予一个唯一的进程标识符pid初始化PCB设置相应的链接如:把新进程加到就绪队列中进程创建收回进程所占有的资源撤消该进程的PCB进程撤消运行-阻塞：处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输完成、等待其它进程发送消息，当被等待的事件未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态。保护CPU现场到PCBPCB插入到阻塞队列进程阻塞阻塞-就绪：处于阻塞状态的进程，当等待的事件发生时，执行唤醒原语，使之由阻塞态变为就绪态。PCB插入到就绪队列进程唤醒2.３进程同步一、多个进程的并发执行在执行时间上互相重叠（或交替），一个进程的执行尚未结束，另一个进程的执行已经开始的执行方式。多个进程的并发执行【例】一种文件打印的实现方案。当一个进程需要打印文件时，将文件名放入一个特殊的目录spooler（即等待队列）下。由一个后台进程负责打印：周期性地检查spooler，看是否有文件需要打印。如果有，则打印之，并将其从spooler目录中删除。一种文件打印的实现方案具体的实现方法：设spooler目录有许多（潜在的无限多个）槽，编号为0，1，2，．．．。每个槽放1个文件名。设置2个共享变量（比如，保存在一个所有进程都能访问的文件中）：out：指向下一个要打印的文件in：指向下一个空闲的槽进程要打印文件时的处理方式：读in→free_slot;写文件名→spooler[free_slot];free_slot+1→in;能正确实现文件打印吗？一种文件打印的实现方案出现的问题：结果的不确定性。即结果取决于进程运行的时序。原因：由资源共享引起。为此，引入同步（synchronization）和互斥（mutualexclusion）。同步：进程之间需要一种严格的时序关系。如输入、计算、输出进程之间。互斥：不能同时访问共享资源。可以看作是一种特殊的同步。实现互斥是OS设计的基本内容。2.３进程同步二、临界资源（CriticalResource）与临界区（CriticalSection）临界资源：必须互斥访问的共享资源临界区：进程中访问临界资源的那段程序实现互斥的关键：两个（多个）进程不同时处于临界区。2.３进程同步三、实现互斥的方案一个好的互斥方案应满足以下条件：（1）任何两个进程不能同时处于临界区。（2）临界区外的进程不应阻止其他进程进入临界区。（3）不应使进程在临界区外无休止地等待。就是说，临界区代码执行时间要短。（4）不应对CPU的个数和进程之间的相对运行速度作任何假设。实现互斥的方案1.设置锁变量lock设置共享变量lock=0:临界区内无进程，初始值1:临界区内有进程while(lock);lock=1;CriticalSectionlock=0;NonCriticalSection该方案是错误的!2.严格轮转法设置共享变量turn,以指示进入临界区的进程号0:允许进程0进入临界区，初始值1:允许进程1进入临界区进程0：while(turn!=0);CriticalSectionturn=1;NonCriticalSection以2个进程为例。turn=进程1：while(turn!=1);CriticalSectionturn=0;NonCriticalSection实现互斥的方案不是一个可取的方案!当一个进程想进入临界区时，先调用enter_region函数，判断是否能安全进入，不能的话等待；当进程从临界区退出后，需调用leave_region函数，允许其它进程进入临界区。两个函数的参数均为进程号实现互斥的方案3.Peterson解决方案enter_region(process);//process是进入/离开临界区的进程号CriticalRegionleave_region(process);NoncriticalRegion#defineFALSE0#defineTRUE1#defineN2//进程的个数intturn;//轮到谁？intinterested[N];//兴趣数组，所有元素初始值均为FALSEvoidenter_region(intprocess)//process为进程号0或1{intother;//另外一个进程的进程号other=1-process;interested[process]=TRUE;//表明本进程希望进入临界区turn=process;//设置标志位while(turn==process&&interested[other]==TRUE);}voidleave_region(intprocess){interested[process]=FALSE;//本进程将离开临界区}Peterson解决方案turn、interested是共享变量turn:表示要进入临界区的进程号interested[i]==TRUE表示进程i要求进入或正在临界区执行4.关中断关中断;CriticalSection开中断;NonCriticalSection实现互斥的方案进程要进入临界区前先关中断，离开临界区前开中断。因为CPU只有发生中断时才进行进程切换。缺点：（1）对多处理机系统无效。在多处理机系统中，有可能存在一个以上的进程在不同处理机上同时执行，关中断是不能保证互斥的；（2）将关中断的权力交给用户不合适。5.机器指令（1）TestAndSet指令－TSL(TestandSetLock)指令为多处理机设计的计算机通常有类似的TSL指令。格式：TSLregister,memory功能：register←[memory];将内存单元的值送寄存器[memory]←1；置内存单元的值为非0执行TSL指令的CPU将锁住总线，以禁止其他CPU在本指令结束之前访问内存。实现互斥的方案TSL指令的功能用C语言描述：TSL指令实现互斥intTSL(int*pLock){intretval;retval=*pLock;*pLock=1;returnretval;}实现互斥的方法（用C语言描述）：TSL指令实现互斥voidenter_region(){while(TSL(&lock));}voidleave_region(){lock=0;}设置一个共享变量lock=0:未上锁，可进入临界区。初始值1:已上