第三篇4：进程管理

计算机系统平台——

第4章操作系统的内部实现机制王琳ise_wanglin@

已讲的内容第一篇：计算机操作平台（操作系统）第二篇：计算机硬件平台（计算机硬件组成、信息表示）问题：什么是操作系统?操作系统的作用是什么?部分操作系统部分操作系统操作系统的层次结构操作系统抽象CPUMemdiskI/OOperatingSystemprocessaddressspacefile操作系统定义OSisacontrolprogramApieceofsystemsoftwareControlsexecutionofprogramstopreventerrorsandimproperuseofthecomputerExecuteuserprogramsandmakesolvinguserproblemseasierMakethecomputersystemconvenienttouseOSisaresourceallocatorAninterfacebetweenapplicationsandhardwareManagesallresourcesDecidesbetweenconflictingrequestsforefficientandfairresourceuseUsethecomputerhardwareinanefficientmannerNouniversallyaccepteddefinition操作系统定义(Cont.)‏FunctionsofOSserviceproviderresourcemanagerextendedmachinevirtualmachine操作系统作为服务提供者ServiceproviderProvidestandardfacilitiesFilesystemStandardlibrariesGUIWindowsystemInterface……操作系统作为资源管理者ResponsibleformanagingresourcesFunctionssamewayasordinarycomputersoftwareItisaprogramthatisexecutedOperatingsystemrelinquishescontroloftheprocessor操作系统作为扩展机器Hardware+interruptsVirtualMemProcess+primitivesComm.PrmtvsFilesys.DevicesDirectoriesShellUserProcessesWebClientsApplicationClientsWebServerApplicationServer操作系统作为虚拟机器(a)Nonvirtualmachine(b)virtualmachineNon-virtualMachineVirtualMachine进程的管理进程概念的引入进程的状态进程的调度进程间的通信线程进程概念的引入什么是程序？进程概念的引入什么是进程操作系统抽象概念里的程序运行操作系统的基本执行单元进程是程序的运行（实体）程序=静态文件(image)进程=程序执行=程序+执行状态.不同进程可以运行同一个程序的不同实例同一程序，不同进程多道程序系统下，多个执行进程执行至少要求以下资源:用以装载程序代码和数据的内存空间支持执行的一系列CPU寄存器从程序到进程用C语言编写一个程序编译器把程序转化成指令集连接器生成可执行文件(code+data)载入可执行程序到内存(makereadytorun)voidX(intb){if(b==1){…intmain(){inta=2;X(a);}CodeHeaderInitializeddataExecutableFileSourceCodeCompile+Link进程在内存中的存在形式voidX(intb){if(b==1){…intmain(){inta=2;X(a);}WhatyouwroteWhatisinmemory.voidX(intb){if(b==1){…intmain(){inta=2;X(a);}Codemain;a=2X;b=2HeapStack进程的剖析CodeHeaderInitializeddataExecutableFileCodeInitializeddataHeapStackDLL’smappedsegmentsProcess’saddressspaceLoad进程控制块CodeInitializeddataHeapStackDLL’smappedsegmentsProcess’saddressspacePCSPOtherRegistersPIDUIDSchedulingPriorityListofopenfiles…PCB操作系统用来存放进程有关的信息每个进程都有一个进程控制块进程管理的任务进程的调度系统决定在某个时刻应该执行哪个进程(因为多道程序的存在)进程间资源的竞争与共享多个进程同时需要同一个资源（打印机）进程的同步与互斥任务多个进程访问同一个数据（温度测控与显示）进程通信进程间通告状态或者任务信息main{

intchildPID;S1;

childPID=fork();

if(childPID==0)<codeforchildprocess>

else{<codeforparentprocess>wait();

}

S2;

}Unixfork()产生进程实例（很多方式产生进程）Theexecutioncontextforthechildprocessisacopyoftheparent’scontextatthetimeofthecallfork()returnschildPIDinparent,and0inchildCodeDataStackCodeDataStackParentChildfork()childPID

=0childPID

=xxx进程的生命周期ProcessiscreatedatStartandtransitionstoReadywhenitbecomesrunnableReadyStart进程的生命周期ProcesstransitionsfromReadytoRunningwhenkernelschedulesitRunningReadyStart进程的生命周期ProcesstransitionsfromRunningtoWaitingwhenitisblocked,waitingforaneventtooccur(e.g.,waitingforanI/Otofinish)RunningReadyWaitingStart进程的生命周期ProcesstransitionsfromWaitingtoReadywhentheeventoccurs(e.g.,I/Ocompletion)RunningReadyWaitingStart进程的生命周期ProcesstransitionsfromRunningtoReadyonaninterruptandpre-emptiveschedulingRunningReadyWaitingStart进程的生命周期ProcesstransitionsfromRunningtoDoneonexit()RunningReadyWaitingStartDone进程的生命周期ProcessesarealwayseitherRunning,Ready(toexecute)orWaiting(foraneventtooccur)RunningReadyWaitingStartDone内存进程的状态基本状态“执行”、“就绪”、“阻塞”其他状态挂起内存不足、特殊阶段性进程（计划任务）内存到外存（代码除外）阻塞进程先挂起僵死进程信息依然存在等待能被信号唤起：浅睡眠不能被信号唤起：深睡眠挂起将暂不执行的进程换出到外存，节省内存空间“挂起就绪状态”“挂起阻塞状态”进程的七状态图内存外存Linux的进程状态图就绪队列（链表）structlist_head{ structlist_head*next,*prev;};structtask_struct{ …… structlist_headrun_list; ……}进程队列实例回顾几个问题操作系统通常包含哪四种子系统？进程和程序的区别？除了初始状态与退出状态，在五状态模型中还包括哪几种状态？其状态转移关系是怎么样的？考虑挂起的情况下，又可增加哪几种状态？新的状态转移关系是怎么样的？进程的调度CPU的分配方式剥夺式（可中断，间断调用）当一个进程正在执行，处于它的一个CPU周期期间，系统可基于某种原则，强行剥夺现行进程正占用的CPU，并把CPU分配给另一进程。非剥夺式（不可中断，一直执行）非剥夺式调度，也称“非抢占式调度”。它的含义是：当一个进程获得CPU后，除非它因某种原因阻塞或者运行完毕，系统不能从该进程夺走CPU控制权。即现行进程完成它的当前CPU周期后，系统才重新调度。周转时间是从作业提交到作业完成的时间间隔。

平均周转时间是指进程调度时,各个进程的周转时间的平均值。等待时间是指一个作业从被提交到获得资源来被处理的那段等待时间，也被称为响应时间。平均等待时间是指进程调度时,各个进程的等待时间的平均值。周转时间与等待时间先来先服务策略该准则实质对应于FIFO队列若进程终止或阻塞,则CPU被分配给队列中的下一个进程例子—三个进程P1,P2,P3,执行时间分别是12,3,3.作业抵达顺序P1,P2,P3作业抵达顺序P2,P3,P1该策略属于哪种CPU的分配方式？短作业优先策略短作业先执行按照预估完成时间的顺序进行排队该策略属于哪种CPU分配方式？可以是剥夺式，也可以是非剥夺式若是剥夺式的话:也称做最短剩余时间优先策略HeadTail短作业优先法的性能进程

执行时间

P1

15P2 4P3 3平均周转时间：（22+7+3）/3=10.7平均等待时间：（7+3+0）/3=3.3若使用FCFS策略，进程到达的顺序为

P1、P2、P3。平均周转时间是多少？平均等待时间又是多少？平均周转时间：（15+19+22）/3=18.7平均等待时间：（0+15+19）/3=11.3P3P2P103722时间最短剩余时间优先策略的性能行程

CPU执行时间

到达时间

P1 6

0 P2 3

1 P3 7

2P4 4

3 平均周转时间是多少？平均等待时间又是多少？平均周转时间：（13+3+18+5）/4=9.75平均等待时间：（7

+

0+11+1）/4=4.75P1P3P1P2P4时间

01481320时间片轮转法采用被称做时间片的离散单元来分配处理器在每个时间片的末期，进程状态转换为就绪状态进程每(n–1)q个时间单元执行一次该策略属于哪种CPU分配方式？时间片轮转法示例时间片为20，进程抵达顺序与运行时间如下

P1 53

P2 8

P3 68

P4 24甘特图等待时间P1=(68-20)+(112-88)=72 P2=(20-0)=20

P3=(28-0)+(88-48)+(125-108)=85

P4=(48-0)+(108-68)=88平均等待时间=(72+20+85+88)/4=66¼P1P2P3P4P1P3P4P1P3P302028486888108112125145153优先级法为每一个进程分配一个优先级，并按照优先级来调度进程 若将优先级定义为作业的预计执行时间,则变为了短作业优先缺点:进程饥饿低优先级进程可能永远不会被执行！避免进程饥饿的方法：年龄增长 随时间逐步增加进程的优先级进程调度策略总结先来先服务就绪队列：时间先后短作业（遇上复杂作业）短作业优先短作业先服务长作业可能很久不被执行时间片轮转法时间片，轮流（刚获得CPU资源，执行I/O操作）为I/O就绪进程单设队列优先级法优先级别（紧急情况优先）进程饥饿（调整优先级）进程切换开销时间和空间上的系统开销根据策略选择进程需要时间和空间调度策略最后反映在实物上就是操作系统代码时间的角度：这些代码的执行需要时间空间的角度：这些代码以及用到的相应数据结构都要放在内存中切换时保存和恢复进程的上下文（保护现场）需要保护的对象如程序计数器、状态寄存器的内容保存在哪进程控制块或者与当前进程有关的一些内存区域中进程上下文OperatingSystem“SystemSoftware”UserProgram1UserProgram2UserProgram2UserProgramn...Program1Program2OSI/ODevicek:read()k+1:startIO()endio{interruptmain{main{}read{}}schedule()Memorysave

stateschedule()restore

statesavestate上下文交换图示进程的同步与互斥进程同步与互斥需求（操作系统协调）互斥：进程要求对资源的使用不受其他进程干扰（打印机硬件/数据资源）例子：照片编辑器和照片查看器都要打印机打印照片同步：协调进程的执行顺序 例子：一个进程负责收集温度，另外一个进程负责显示时间以及该时刻的温度操作系统怎么支持进程互斥地访问资源呢程序声明互斥访问的资源（硬件互斥资源操作系统声明）使用互斥资源先申请资源未被使用，让申请进程使用使用完资源，明确声明，然后操作系统才会让其他进程使用操作系统提供相关系统调用程序中访问互斥资源的那段代码：临界区、或敏感区、或危险区互斥实现互斥锁

加锁和开锁的操作由操作系统实现程序员在程序中使用系统调用，且需要很小心地使用这些功能操作系统实现检测数据是否被锁住加锁的过程不能被打断锁抽象成一个变量，称为互斥量。互斥量的操作用原子操作实现全部动作过程不会被打断的操作互斥锁的应用 进程1： 进程2：

…

…

lock(w)； lock(w)； 执行临界段1； 执行临界段2；

unlock(w)； unlock(w)；进程的同步典型示例：生产者和消费者问题消费者产品数量大于1时,消费使产品数量减少、库房（空）数量增加生产者库房数量大于1时,放产品使产品的数量增加，库房（空）的数量减少制约资源产品、库房生产者/消费者问题简化单向制约库房无限大、产品数量消费者消费一个产品，数量减1减1后的产品数量不小于0表示还有产品，消费者就从库房中取出产品小于0，表明没有产品，消费者去排队等待生产者/消费者问题简化生产者生产一个产品，产品数量加1产品数量加1后，如果产品的数量还是小于0的，表示有消费者在等待，唤醒（V操作）。关键问题增/减数量、判断、等待/唤醒所有步骤需要一次完成：原子操作同步的实现信号量对于需要同步访问的资源，操作系统让程序为它声明一个信号量信号量是一个整数。值是资源的个数。操作系统提供两种对信号量的操作P操作（荷兰语：Passeren通过）V操作（荷兰语：Vrijgeven释放）同步的实现P操作对信号量的值减1判断信号量是否小于等于0；如果不是，则调用P操作的进程继续执行否则，进程到这个信号量的等待队列中去等待V操作对信号量加1判断信号量是否大于0；如果是，则调用进程继续执行否则说明有进程在等待该信号量，通知等待进程以原语操作的形式实现（不可分割，不可中断）

一般来说，信号量S>0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S<0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。同步的实现buffer：=1；（缓冲区数量） data：=0；（数据数量）P计算： P打印：Repeat RepeatP(buffer)； P(data)；写入数据； 输出数据；

V(data)； V(buffer)；Untilfalse； Untilfalse；进程间的通信信号管道消息队列共享内存基于网络连接的通信信号需求要传递的信息很少信号事先定义对应每个信号进程有一个处理程序信号队列每个进程有一个存放其他进程发给它、等待它处理的信号操作系统提供发送信号的接口函数把进程要发送的信号放到目标进程的信号队列中进程在执行过程中的特定时刻，检查并处理自己的信号队列如从系统空间返回到用户空间之前发送信号时，必须指明发送目标进程的号码一般用在具有亲缘关系的进程之间管道需求大量信息上游的进程往管道中写入数据，下游的一方从管道接收数据先进先出的单向通信双向通信需要建立两个管道操作系统提供建立管道的系统调用函数命名管道管道同步：操作系统负责管道的容量有限，管道满时，发送进程睡眠等待以字节为单位：没有格式的字节流“清明时节雨纷纷，路上行人欲断魂，借问酒家何处有，牧童遥指杏花村。”“清明时节／雨／纷纷路上行人／欲断魂／借问酒家何处／有牧童遥指／杏花村”消息队列需求 保持数据逻辑边界操作系统提供创建消息队列的系统调用一个进程可以使用系统调用创建一个消息队列任何进程都可以向该队列中发送消息，也可以从队列中接收消息操作系统负责同步若消息队列已满，则写消息的进程排队若取消息进程没有找到需要的消息，读等待队列共享内存速度最快的进程间通信方式管道和消息队列都需要数据的复制发送进程把数据复制到管道或者队列中接收进程把数据从管道或者队列复制到自己的内存区中操作系统提供系统调用让一个进程创建一块共享内存区其他进程通过系统调用把这段内存映射到自己的用户地址空间中进程像正常的内存访问一样读写共享内存区间不涉及数据的复制没有同步机制基于网络连接的通信插口、也叫套接字（socket）不同计算机进程间通过插口机制通信需要通信的双方首先要各自创建一个插口，插口声明自己接收来自某端口地址的数据主机地址：通信地址端口号：人名进程通过插口把消息发送到网络中消息中指明接收进程所在主机名、端口号网络中的传输设备根据主机地址把消息传递给目的主机。操作系统按照消息中端口号找到声明接收该信息的插口，并把数据复制到插口的缓冲区内。目的进程从插口中接收到数据可用在同一台计算机上的进程之间通信进程的缺点进程切换开销大上下文切换：保存和恢复相关寄存器的内容；与进程运行有关的这些数据都需要修改；进程控制块中的各种队列（如阻塞队列、就绪队列、通信队列）；存储管理有关的一些记录信息；文件管理有关数据；进程的地址空间要转换成新被指派运行的进程的地址空间涉及到读写内存、需要花费很多时间 进程的个数很多、进程转换又频繁发生，那么系统的性能就会下降

怎样减少开销？为什么要切换这么多信息？切换处理机