期末复习操作系统

Chapter3:ProcessesChapter3:ProcessesProcessConcept进程的概念ProcessScheduling进程调度OperationsonProcesses进程的操作CooperatingProcesses进程协作InterprocessCommunication进程间通信CommunicationinClient-ServerSystems客户机-服务器系统通信ConcurrenceCurrent-daycomputersystemsallowmultipleprogramstobeloadedintomemoryandexecutedconcurrently.EfficiencyEfficiencysequentialexecution:CumulativeTime：80CPUEfficiency：40/80=50%DEV1Efficiency：15/80＝18.75%DEV2Efficiency：25/80=31.25%ConcurrenceCumulativeTime

：45CPUEfficiency：40/45=89%DEV1Efficiency：15/45=33%DEV2Efficiency：25/45＝55.6%并行（Parallel）vs并发（Concurrency）Problem①②③④①②③④①②③④…2222…①③②④①③②④①③②④…1111…begin--------------------------------------------endCcompilerProcess1(datasection)Sourcecode1Objectcode1Process2(datasection)Sourcecode2Objectcode2Data是自己的，program是共享的进程引入ProcessConcept进程的概念Anoperatingsystemexecutesavarietyofprograms:操作系统执行一系列的程序Batchsystem–jobs批处理系统：作业Time-sharedsystems–userprogramsortasks分时系统：用户程序或任务Textbookusesthetermsjobandprocessalmostinterchangeably本书中作业=进程Process–aprograminexecution;processexecutionmustprogressinsequentialfashion进程：程序的执行，程序顺序执行进程:1.程序在执行中；2.一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程,是系统进行资源分配和调度的独立单位进程与程序有何差别？进程是一个动态概念，程序是一个静态概念；进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的。进程具有并发性，而程序没有；进程是竞争计算机系统资源的基本单位，其并发性受到系统本身的制约；不同的进程可以包含同一程序，只要程序所对应的数据集不同Main()-----------open()----------Open()-------------------------------returnSystemcallProcess1(usermode)UserstackProcess1(monitormode)Kernelstack一个进程对应多个程序例ProcessConcept进程的概念Aprocessincludes:Text

section文本段（代码段）programcounter程序计数器Stack堆栈datasection数据段ProcessinMemory进程的特征特征结构特征动态性并发性独立性异步性程序段、数据段、进程控制块PCB最基本的特征，进程是动态产生，动态消亡的；进程在其生命周期内，在三种基本状态之间转换（就绪、等待和执行）任何进程都可以同其他进程一起向前推进每个进程都以其相对独立的、不可预知的速度向前推进进程是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。进程和程序的区别与联系进程程序动态静态暂时永久并发PCB——多个一个一个多个ProcessState进程状态Asaprocessexecutes,itchangesstatenew:Theprocessisbeingcreated新的running:Instructionsarebeingexecuted运行waiting:Theprocessiswaitingforsomeeventtooccur等待ready:Theprocessiswaitingtobeassignedtoaprocessor就绪terminated:Theprocesshasfinishedexecution终止DiagramofProcessState进程状态图一个进程的生命期中，每个状态将经历几次？进程状态转换（1/2）就绪-->运行调度程序选择一个新的进程运行运行-->就绪运行进程用完了时间片运行进程被中断，因为一高优先级进程处于就绪状态进程状态转换（2/2）运行-->等待OS尚未完成服务对一资源的访问尚不能进行初始化I/O且必须等待结果等待某一进程提供输入(IPC)等待-->就绪当所等待的事件发生时ProcessControlBlock(PCB)ContainerfortheuniqueinformationforeachprocesswhentheyarerunningintheoperatingsystemPCB用来保存程序运行期间的重要信息(1)进程存在的唯一标识(2)记录了OS所需的用于描述进程及控制进程所需的全部信息InformationassociatedwitheachprocessProcessstate进程状态Programcounter程序计数器CPUregisters

CPU寄存器CPUschedulinginformation

CPU调度信息Memory-managementinformation内存管理信息Accountinginformation记账信息I/Ostatusinformation

I/O状态信息进程与PCB是一一对应的ProcessControlBlock(PCB)ConceptofProcess(进程描述)Part1ofPCB:描述信息ProcessID(PID)进程标识号EachprocesshasauniquePIDUsernameorUserID(UID)用户名或用户标识号FamilyRelationship家族关系ConceptofProcess(进程描述)Part2ofPCB:ControlInformation控制信息ProcessStatus进程当前状态ProcessPriority进程优先级Addressoftheprogramentrypoint程序的开始地址StatisticalInformation计时、资源使用等统计信息CommunicationInformation进程间通信信息ConceptofProcess(进程描述)Part3ofPCB:ResourceManagementInformation资源管理信息MemoryConsumptionInfo占用内存资源信息FileSystemInfo文件系统使用信息，如打开的文件等DeviceUsageInfo设备、I/O资源使用情况信息ConceptofProcess(进程描述)Part4ofPCB:CPUstatepreservationCPU现场信息通用寄存器(%eax,%ecx,…)

程序计数器PC(存放在寄存器IR中)

状态PSW

栈指针(%ebp,%esp)…CPUSwitchFromProcesstoProcess

CPU在进程间的切换ContextSwitch上下文切换WhenCPUswitchestoanotherprocess,thesystemmustsavethestateoftheoldprocessandloadthesavedstateforthenewprocess当CPU切换到另一个进程的时候，系统需要保存老进程的状态，并且加载新进程的状态Context-switchtimeisoverhead;thesystemdoesnousefulworkwhileswitching上下文切换的时间是系统的额外开销，切换时系统不做任何有用的工作Timedependentonhardwaresupport时间与硬件支持密切相关OrganizingPCBsProcessSpaceandSize进程空间和大小每个进程的控制块PCB要占据一定的内存系统中允许并发执行的进程数是有限的LinuxKernel2.2X中最多能够支持4090个用户进程同时工作ProcessSchedulingQueues进程调度队列Jobqueue–setofallprocessesinthesystem作业队列：保存系统中所有的进程Readyqueue–setofallprocessesresidinginmainmemory,readyandwaitingtoexecute就绪队列Devicequeues–setofprocesseswaitingforanI/Odevice设备队列：等待I/O设备的进程Processesmigrateamongthevariousqueues进程在不同的队列间移动ReadyQueueAndVariousI/ODeviceQueues

就绪队列和各种不同的设备队列每种设备拥有自己的设备队列RepresentationofProcessSchedulingqueuingdiagram队列状态图Schedulers调度程序Long-termscheduler(orjobscheduler)–selectswhichprocessesshouldbebroughtintothereadyqueue长期调度（作业调度）：选择一个进程进入内存的就绪队列Short-termscheduler(orCPUscheduler)–selectswhichprocessshouldbeexecutednextandallocatesCPU短期调度（CPU调度）：从就绪队列中选择一个进程，并为之分配CPUSchedulers(Cont.)Short-termschedulerisinvokedveryfrequently(milliseconds)(mustbefast)短期调度频率高Long-termschedulerisinvokedveryinfrequently(seconds,minutes)(maybeslow)长期调度频率低Thelong-termschedulercontrolsthedegreeofmultiprogramming

长期调度控制多道程序设计的程度Processescanbedescribedaseither:进程分类I/O-boundprocess–spendsmoretimedoingI/Othancomputations,manyshortCPUbursts

I/O为主的进程CPU-boundprocess–spendsmoretimedoingcomputations;fewverylongCPUbursts

CPU为主的进程进程的复杂状态（1）多个进程竞争内存资源内存资源紧张无就绪进程，处理机空闲：I/0的速度比处理机的慢的多，可能出现全部进程阻塞等待解决方案：Swapping(交换技术)：换出一部分内存到外存，以腾出内存空间。VirtualMemory(虚拟存储技术)：每个进程只装入一部分程序和数据（存储管理部分）。对换技术、交换技术（Swapping）将内存中暂时不能运行的进程，或暂时不用的数据和程序，换出到外存，以腾出足够的内存空间，把已经具备运行条件的进程，或进程需要的数据和程序，换入内存。分析：针对进程的存在位置（内存或者外存），进一步增加“阻塞挂起”和“就绪挂起”两种状态AdditionofMediumTermScheduling

中期调度（交换）七状态进程模型活动挂起事件发生事件发生等待事件挂起调度超时释放活动挂起概念：进程控制：系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程各状态之间的转换，从而达到多进程高效并发执行和协调，实现资源共享的目的。Atomicoperation(原语）：指用机器语言书写的，在系统态下运行的，在执行中不可被中断的程序段。。机器指令级：不允许中断，不可分割功能级：不允许并发执行（原语本身由若干条指令组成，要么全做，要么全不做，且顺序做）在OS中，大都把进程控制用程序段做成原语。完成进程控制的原语有：Create(创建）,Termination(终止），Blocked(阻塞），

Wakeup(唤醒），Suspend(挂起）等。Primitives(OperationonProcesses)createterminationblockedwakeup

ProcessCreation进程创建Parentprocesscreatechildrenprocesses,which,inturncreateotherprocesses,formingatreeofprocesses父进程创建子进程，子进程继续创建，从而形成一棵进程树Resourcesharing资源共享Parentandchildrenshareallresources父子进程共享所有资源Childrensharesubsetofparent’sresources子进程共享部分父进程的资源Parentandchildsharenoresources父子进程不共享任何资源ExecutionParentandchildrenexecuteconcurrently子进程和父进程并发执行Parentwaitsuntilchildrenterminate父进程等待直到子进程终止AtreeofprocessesonatypicalSolarisProcessCreation(Cont.)Addressspace地址空间Childduplicateofparent子进程是父进程的复制品Childhasaprogramloadedintoit子进程装入另一个新程序UNIXexamplesforksystemcallcreatesnewprocess

execsystemcallusedafteraforktoreplacetheprocess’memoryspacewithanewprogramProcessCreation在进程表中增加一项，并从PCB池中取一个空白PCB；为新进程分配资源，除内存空间外，还有其他各种资源；初始化进程控制块，为新进程分配进程标识符，初始化PSW；加入就绪进程队列ProcessCreationCProgramForkingSeparateProcessintmain(){pid_tpid; /*forkanotherprocess*/ pid=fork(); if(pid<0){/*erroroccurred*/ fprintf(stderr,"ForkFailed"); exit(-1); } elseif(pid==0){/*childprocess*/ execlp("/bin/ls","ls",NULL); } else{/*parentprocess*/ /*parentwillwaitforthechildtocomplete*/ wait(NULL); printf("ChildComplete"); exit(0); }}ProcessTermination进程终止Processexecuteslaststatementandaskstheoperatingsystemtodeleteit(exit)进程完成执行最后的语句并使用系统调用exit请求操作系统删除自身Outputdatafromchildtoparent(viawait)进程可以返回状态值给父进程（通过wait）Process’resourcesaredeallocatedbyoperatingsystem进程的资源被操作系统释放Parentmayterminateexecutionofchildrenprocesses(abort)父进程能够中止子进程的执行Childhasexceededallocatedresources子进程使用了超过它所分配到的一些资源Taskassignedtochildisnolongerrequired子进程的任务不再需要Ifparentisexiting如果父进程结束了Someoperatingsystemdonotallowchildtocontinueifitsparentterminates一些操作系统不允许子进程继续执行Allchildrenterminated-cascadingtermination级联终止ProcessTermination（进程终止）终止事由正常结束异常结束外界的干预终止流程OS通过调用进程终止原语完成进程的终止。第一步：根据被终止进程的标识符，从PCB集合中查找对应进程控制块并读出该进程的状态；第二步：若被终止进程正处于执行状态，则终止该进程的执行，并设置调度标志为真，用于指示该进程被终止后应重新进行调度，选择一新进程，把处理机分配给它。第三步：若进程还有子孙进程，应将其所有子孙进程终止，以防它们成为不可控制的。第四步：将进程所占有的全部资源释放（还给父进程或系统），释放进程控制块（若该进成为执行态，要进行进程调度）。第五步：将被终止进程（它的PCB）从所在队列（或链表）中移出，等待其他程序来收集相关信息。Blockingprocess进程阻塞引发事件请求系统服务启动某种操作新数据尚未到达无新工作可做BlockingprocessSavestate(现场）UpdatePCB(state:running->waiting)PutthePCBintoawaitqueueGotoscheduler(why?)Wakeupprocess(唤醒进程）UpdatePCB(state:waiting->ready)

PutPCBintoreadyqueue

MaybegotoschedulerCooperatingProcesses

进程协作Independentprocesscannotaffectorbeaffectedbytheexecutionofanotherprocess独立进程不能影响或被在系统内执行的其他进程所影响Cooperatingprocesscanaffectorbeaffectedbytheexecutionofanotherprocess协作进程影响或被在系统内执行的其他进程所影响Advantagesofprocesscooperation进程协作的好处Informationsharing信息共享Computationspeed-up加快计算Modularity模块化Convenience方便Producer-ConsumerProblem

生产者消费者问题Paradigmforcooperatingprocesses,producerprocessproducesinformationthatisconsumedbyaconsumerprocessunbounded-bufferplacesnopracticallimitonthesizeofthebuffer无限缓冲bounded-bufferassumesthatthereisafixedbuffersize有限缓冲InterprocessCommunication(IPC)Mechanismforprocessestocommunicateandtosynchronizetheiractions(IPC指的操作系统中为了进程之间相互通信以使得进程之间的动作同步的基本机制)常见的两种通信模式1.SharedMemory2.Messagesystem–processescommunicatewitheachotherwithoutresortingtosharedvariables

消息系统是一种典型的IPC形式，在基于消息系统实现的多进程程序中进程间的通信不依赖于共享变量两种基本的IPC模式SharedMemory共享内存MessagePassing消息传递Sharedmemory生产者/消费者问题：生产者与消费者通过共享缓冲区，实现数据传递。属于基于共享存储区通信。这里的共享存储区属于每个互相通信进程的组成部分。不要求数据移动，一般属于本地通信。需要交换信息的进程通过对同一共享数据区的操作来达到相互通信。对于远程通信来说，每台计算机拥有各自的内存区，不容易实现共享存储区的访问。SharedmemoryShmget建立一个新的共享存储区或返回一个已经存在的共享存储区Shmat从逻辑上把一个共享存储区附接到一个进程的虚拟地址空间Shmdt从一进程的虚拟地址空间断接一共享存储区Shmctl对共享存储区的相关联的各种参数进行操作基于消息系统的IPCIPCfacilityprovidestwooperations:send(message)–messagesizefixedorvariablereceive(message)

基于消息系统的IPC中，提供如下两个基本的操作send(message)–发送消息，参数message的大小可以固定，也可以不固定receive(message)–接收消息IfPandQwishtocommunicate,theyneedto:establishacommunication

linkbetweenthem（首先，建立相互通信的通信链接）exchangemessagesviasend/receive(通过send/receive进行消息交换)Implementationofcommunicationlink（通信链接的具体实现形式）physical(e.g.,sharedmemory,hardwarebus)

物理链接，如共享内存、硬件总线等logical(e.g.,logicalproperties)基于消息系统的IPCImplementationQuestionsHowarelinksestablished?链接是如何建立的？Canalinkbeassociatedwithmorethantwoprocesses?一个链接能够关联多于两个进程吗？Howmanylinkscantherebebetweeneverypairofcommunicatingprocesses?每一对通信进程间能够有多少条链接？Whatisthecapacityofalink?容量Isthesizeofamessagethatthelinkcanmodatefixedorvariable?消息的大小？Isalinkunidirectionalorbi-directional?链接是双向还是单向的？DirectCommunication直接通信Processesmustnameeachotherexplicitly:send(P,message)–sendamessagetoprocessPreceive(Q,message)–receiveamessagefromprocessQ直接通信模式下，发送消息的进程必须指定消息发送的对象，接收消息的进程也必须知道消息是来自于那一个进程PropertiesofcommunicationlinkLinksareestablishedautomatically链接自动创建Alinkisassociatedwithexactlyonepairofcommunicatingprocesses一个链接仅与两个进程相关Betweeneachpairthereexistsexactlyonelink每对进程间仅有一个链接Thelinkmaybeunidirectional,butisusuallybi-directional链接可以是单向的，但通常是双向的IndirectCommunication间接通信Messagesaredirectedandreceivedfrommailboxes(alsoreferredtoasports)通过邮箱或端口来发送和接收消息Eachmailboxhasauniqueid每个邮箱有一个固定IDProcessescancommunicateonlyiftheyshareamailbox只有进程共享一个邮箱时，才能通信PropertiesofcommunicationlinkLinkestablishedonlyifprocessesshareacommonmailbox只有进程共享邮箱时，才能建立链接Alinkmaybeassociatedwithmanyprocesses一个链接可以跟多个进程关联Eachpairofprocessesmayshareseveralcommunicationlinks两个进程之间可以有多个不同的链接Linkmaybeunidirectionalorbi-directionalIndirectCommunication间接通信Operationscreateanewmailbox创建新邮箱sendandreceivemessagesthroughmailbox通过邮箱发送和接收消息destroyamailbox删除邮箱Primitivesaredefinedas:原语

send(A,message)–sendamessagetomailboxA

receive(A,message)–receiveamessagefrommailboxAIndirectCommunicationMailboxsharingP1,P2,andP3sharemailboxAP1,sends;P2

andP3receiveWhogetsthemessage?Solutions解决方案Allowalinktobeassociatedwithatmosttwoprocesses一个链接最多与两个进程关联Allowonlyoneprocessatatimetoexecuteareceiveoperation一次最多一个进程执行receiveAllowthesystemtoselectarbitrarilythereceiver.Senderisnotifiedwhothereceiverwas.允许系统任意选择一个进程接收消息，也可以发送者指定接收者SynchronizationMessagepassingmaybeeitherblockingornon-blockingBlockingisconsideredsynchronous阻塞也成为同步BlockingsendhasthesenderblockuntilthemessageisreceivedBlockingreceivehasthereceiverblockuntilamessageisavailableNon-blockingisconsideredasynchronous非阻塞也称异步Non-blockingsendhasthesendersendthemessageandcontinueNon-blockingreceivehasthereceiverreceiveavalidmessageornullBuffering缓冲Queueofmessagesattachedtothelink;implementedinoneofthreeways链接的消息队列实现方法1. Zerocapacity–0messages

0容量：必须阻塞发送

Sendermustwaitforreceiver(rendezvous)2. Boundedcapacity–finitelengthofnmessages

Sendermustwaitiflinkfull有限容量3. Unboundedcapacity–infinitelength

Senderneverwaits无限容量Client-ServerCommunication客户机-服务器模式(C/S模式)的网络通信也属于一类进程间通信方式典型方式SocketsRemoteProcedureCallsRemoteMethodInvocation(Java)SocketsAsocketisdefinedasanendpointforcommunication

一个套接字是通信的一个端点ConcatenationofIPaddressandport套接字的信息主要包含IP地址+通信端口例如，Thesocket161.25.19.8:1625referstoport1625onhost161.25.19.8Communicationconsistsbetweenapairofsockets通信在一对套接字之间发生SocketCommunicationRemoteProcedureCalls远程过程调用Remoteprocedurecall(RPC)abstractsprocedurecallsbetweenprocessesonnetworkedsystems. RPC提供了在联网的计算机系统之间进行过程调用的机制Stubs–client-sideproxyfortheactualprocedureontheserver.Theclient-sidestublocatestheserverandmarshallstheparameters.

客户端的访问代理负责确定server的位置，并将远程过程调用所需的参数按规定的格式封装好Theserver-sidestubreceivesthismessage,unpacksthemarshalledparameters,a