购买

¥30.0

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 计算机操作系统第三版课件 第三章

计算机操作系统第三版课件 第三章.ppt

计算机操作系统第三版课件 第三章

中小学精品课件
2019-05-26 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《计算机操作系统第三版课件 第三章ppt》,可适用于高等教育领域

第三章进程同步与死锁进程同步经典进程的同步问题管程机制进程通信线程死锁第三章进程同步与死锁第三章进程同步与死锁本章习题习题集页:页。补充习题有三个并发进程:R负责从输入设备读入信息块M负责对信息块加工处理P负责打印输出信息块。今提供一个缓冲区可放置K个信息块二个缓冲区每个可放置K个信息块试用信号量和P、V操作写出三个进程正确工作的流程。要求:月日请各班学习委员收第三组作业按学号排好序交到软件办公室。返回第三章进程同步与死锁本章习题第三章进程同步与死锁进程同步进程同步的基本概念进程之间两种形式的制约关系间接相互制约关系。()直接相互制约关系。对操作时间所加的一种限制。同步是对操作时间顺序所加的必要限制的一种说法。同步的定义:互斥的定义:其限制规则是“操作A和操作B决不能在同一时刻执行”。同步与互斥的相同之处在于它们都是由于并发进程对资源共享而引起的进程间制约关系。进程同步信号量机制信号量的应用第三章进程同步与死锁临界资源许多资源都是一次仅允许一个进程使用称为临界资源。两进程对变量count进行访问修改R、R是CPU中的寄存器:按P,P,P,P,P,P顺序执行count增加了。按P,P,P,P,P,P的顺序执行count增加了。可见问题的发生在于执行顺序不同而产生了不同结果以致数据结果有误。这种错误叫与时间有关的错误。为了预防这种错误必须限制对count的访问不允许多个进程交叉访问和修改否则难以达到预期效果。这就是说:必须将count作为临界资源处理。打印机、输入机、磁带机等。此外许多软件资源如数据表格、变量、队列等也属临界资源。第三章进程同步与死锁临界区(criticalsection)可把一个访问临界资源的循环进程描述如下:repeat进入区criticalsection临界区退出区remaindersection非临界区untilfalseentrysectionexitsection第三章进程同步与死锁同步机制应遵循的规则空闲让进。()忙则等待。()有限等待。()让权等待。返回第三章进程同步与死锁信号量机制一整型信号量最初由Dijkstra把整型信号量定义为一个整型量除初始化外仅能通过两个标准的原子操作(AtomicOperation)wait(S)和signal(S)来访问。这两个操作一直被分别称为原始的P、V操作。wait和signal操作可描henfori∶=tondoSi∶=SiendforelseplacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi<,andsettheprogramcountofthisprocesstothebeginningofSwaitoperationendif}Ssignal(S,S,……,Sn){fori∶=tondoSi=SiRemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor}只要有一类资源不满足插入第一类不足资源队列。下次全部从头开始当每类资源数都大于时就分配从等待Si的阻塞队列取出队首进程插入就绪队列返回第三章进程同步与死锁四、信号量集Swait(S,t,d,…,Sn,tn,dn)ifSi≥tand…andSn≥tnthenfori∶=tondoSi∶=SidiendforelsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSi<tiandsetitsprogramcountertothebeginningoftheSwaitOperationendifsignal(S,d,…,Sn,dn)fori∶=tondoSi∶=SidiRemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor第三章进程同步与死锁一般“信号量集”的几种特殊情况:()Swait(S,d,d)。此时在信号量集中只有一个信号量S但允许它每次申请d个资源当现有资源数少于d时不予分配。()Swait(S,,)。此时的信号量集已蜕化为一般的记录型信号量(S>时)或互斥信号量(S=时)。()Swait(S,,)。这是一种很特殊且很有用的信号量操作。当S≥时允许多个进程进入某特定区当S变为后将阻止任何进程进入特定区。换言之它相当于一个可控开关。返回第三章进程同步与死锁信号量的应用一利用信号量实现进程互斥利用信号量实现进程互斥的进程可描述如下:Varmutex:semaphore∶=beginparbeginprocess:beginrepeatwait(mutex)criticalsectionsignal(mutex)remainderseetionuntilfalse利用信号量实现进程同步与互斥基本方法:依据问题条件写出流程图依据要求设计信号量、变量及其初值在流程图上找出适当位置填写P、V操作第三章进程同步与死锁endprocess:beginrepeatwait(mutex)criticalsectionsignal(mutex)remaindersectionuntilfalseendparend第三章进程同步与死锁二利用信号量实现前趋关系图前趋图举例第三章进程同步与死锁Vara,b,c,d,e,f,gsemaphore∶=,,,,,,beginparbeginbeginSsignal(a)signal(b)endbeginwait(a)Ssignal(c)signal(d)endbeginwait(b)Ssignal(e)endbeginwait(c)Ssignal(f)endbeginwait(d)Ssignal(g)endbeginwait(e)wait(f)wait(g)Sendparendend返回第三章进程同步与死锁经典进程的同步问题一、生产者消费者问题前面我们已经对生产者消费者问题(Theproceducerconsumerproblem)做了一些描述但未考虑进程的互斥与同步问题因而造成了数据Counter的不定性。由于生产者消费者问题是相互合作的进程关系的一种抽象例如在输入时输入进程是生产者计算进程是消费者而在输出时则计算进程是生产者而打印进程是消费者因此该问题有很大的代表性及实用价值。一、生产者消费者问题利用记录型信号量解决生产者消费者问题利用AND信号量解决生产者消费者问题二、哲学家进餐问题利用记录型信号量解决哲学家进餐问题利用AND信号量机制解决哲学家进餐问题三、读者写者问题利用记录型信号量解决读者写者问题第三章进程同步与死锁利用记录型信号量解决生产者消费者问题假定在生产者和消费者之间的公用缓冲池中具有n个缓冲区这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效只要缓冲池未满生产者便可将消息送入缓冲池只要缓冲池未空消费者便可从缓冲池中取走一个消息。对生产者消费者问题可描述如下:第三章进程同步与死锁Varmutex,empty,full:semaphore∶=,n,buffer:array[,…,n]ofitemin,out:integer∶=,beginparbeginproceducer:beginrepeat…produceranitemnextp…wait(empty)wait(mutex)buffer(in)∶=nextpin∶=(in)modnsignal(mutex)signal(full)untilfalseend第三章进程同步与死锁consumer:beginrepeatwait(full)wait(mutex)nextc∶=buffer(out)out∶=(out)modnsignal(mutex)signal(empty)consumertheiteminnextcuntilfalseendparendend第三章进程同步与死锁在生产者消费者问题中应注意:首先在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现其次对资源信号量empty和full的wait和signal操作同样需要成对地出现但它们分别处于不同的程序中。例如wait(empty)在计算进程中而signal(empty)则在打印进程中计算进程若因执行wait(empty)而阻塞则以后将由打印进程将它唤醒最后在每个程序中的多个wait操作顺序不能颠倒。应先执行对资源信号量的wait操作然后再执行对互斥信号量的wait操作否则可能引起进程死锁。返回第三章进程同步与死锁利用AND信号量解决生产者消费者问题armutex,empty,full:semaphore∶=,n,buffer:array[,…,n]ofiteminout:integer∶=,beginparbeginproducer:{生产者repeat…produceaniteminnextp生产下一个产品…swait(empty,mutex)申请资源全有则行缺一则停buffer(in)∶=nextp产品放入BUFin∶=(in)modn指针前行Ssignal(mutex,full)释放资源有等待者就唤醒untilfalse}第三章进程同步与死锁consumer:{消费者进程repeatswait(full,mutex)申请资源全有则行缺一则停nextc∶=buffer(out)从BUF中取出产品out∶=(out)modn指针前行signal(mutex,empty)释放资源有等待者就唤醒consumertheiteminnextc消费产品untilfalse}parend}返回第三章进程同步与死锁二、哲学家进餐问题利用记录型信号量解决哲学家进餐问题经分析可知放在桌子上的筷子是临界资源在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用可以用一个信号量表示一只筷子由这五个信号量构成信号量数组。其描述如下:Varchopstick:array[,…,]ofsemaphore第三章进程同步与死锁所有信号量均被初始化为第i位哲学家的活动可描述为:repeatwait(chopstick[i])wait(chopstick[(i)mod])…eat…signal(chopstick[i])signal(chopstick[(i)mod])…thinkuntilfalse第三章进程同步与死锁可采取以下几种解决方法:()至多只允许有四位哲学家同时去拿左边的筷子最终能保证至少有一位哲学家能够进餐并在用毕时能释放出他用过的两只筷子从而使更多的哲学家能够进餐。()仅当哲学家的左、右两只筷子均可用时才允许他拿起筷子进餐。()规定奇数号哲学家先拿他左边的筷子然后再去拿右边的筷子而偶数号哲学家则相反。按此规定将是、号哲学家竞争号筷子、号哲学家竞争号筷子。即五位哲学家都先竞争奇数号筷子获得后再去竞争偶数号筷子最后总会有一位哲学家能获得两只筷子而进餐。返回第三章进程同步与死锁利用AND信号量机制解决哲学家进餐问题在哲学家进餐问题中要求每个哲学家先获得两个临界资源(筷子)后方能进餐这在本质上就是前面所介绍的AND同步问题故用AND信号量机制可获得最简洁的解法。Varchopsiickarray[,…,]ofsemaphore∶=(,,,,)processirepeatthinkSswait(chopstick[(i)mod],chopstick[i])eatSsignat(chopstick[(i)mod],chopstick[i])untilfalse返回第三章进程同步与死锁三、读者写者问题利用记录型信号量解决读者写者问题为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。另外再设置一个整型变量Readcount表示正在读的进程数目。由于只要有一个Reader进程在读便不允许Writer进程去写。因此仅当Readcount=,表示尚无Reader进程在读时Reader进程才需要执行Wait(Wmutex)操作。若wait(Wmutex)操作成功Reader进程便可去读相应地做Readcount操作。同理仅当Reader进程在执行了Readcount减操作后其值为时才须执行signal(Wmutex)操作以便让Writer进程写。又因为Readcount是一个可被多个Reader进程访问的临界资源因此应该为它设置一个互斥信号量rmutex。第三章进程同步与死锁读者写者问题可描述如下:Varrmutex,wmutex:semaphore∶=,Readcount:integer∶={parbeginReader:beginrepeatwait(rmutex)ifreadcount=thenwait(wmutex)Readcount∶=Readcountsignal(rmutex)…performreadoperation…第三章进程同步与死锁wait(rmutex)readcount∶=readcountifreadcount=thensignal(wmutex)signal(rmutex)untilfalse}writer:{repeatwait(wmutex)performwriteoperationsignal(wmutex)untilfalseendparend}第三章进程同步与死锁管程机制一、管程的基本概念管程的定义把分散在各个进程中的临界区集中管理把共享资源用数据结构抽象表示出来并由秘书程序管理到来的访问者。这个秘书程序就是管程。管程由三部分组成:①局部于管程的共享变量说明②对该数据结构进行操作的一组过程③对局部于管程的数据设置初始值的语句。此外还须为管程赋予一个名字。一、管程的基本概念二、利用管程解决生产者消费者问题第三章进程同步与死锁图管程的示意图第三章进程同步与死锁管程的一般形式如下:type管程名=monitor{局部变量说明条件变量说明初始化语句define管程内定义的、管程外可调用的过程或函数名列表use管程外定义的、管程内将调用的过程或函数名列表过程名函数名(形参表){《过程函数体》}……过程名函数名(形参表){《过程函数体》}……}返回第三章进程同步与死锁条件变量管程中对每个条件变量都须予以说明其形式为:Varx,y:condition。该变量应置于wait和signal之前即可表示为Xwait和Xsignal。例如由于共享数据被占用而使调用进程等待该条件变量的形式为:nonbusy:condition。此时wait原语应改为nonbusywait相应地signal应改为nonbusysignal。应当指出Xsignal操作的作用是重新启动一个被阻塞的进程但如果没有被阻塞的进程则Xsignal操作不产生任何后果。这与信号量机制中的signal操作不同。因为后者总是要执行s∶=s操作因而总会改变信号量的状态。第三章进程同步与死锁如果有进程Q处于阻塞状态当进程P执行了Xsignal操作后怎样决定由哪个进行执行哪个等待可采用下述两种方式之一进行处理:()P等待直至Q离开管程或等待另一条件。()Q等待直至P离开管程或等待另一条件。采用哪种处理方式当然是各执一词。但是Hansan却采用了第一种处理方式。返回第三章进程同步与死锁二、利用管程解决生产者消费者问题在利用管程方法来解决生产者消费者问题时首先便是为它们建立一个管程并命名为ProclucerConsumer,或简称为PC。其中包括两个过程:()put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中并用整型变量count来表示在缓冲池中已有的产品数目当count≥n时表示缓冲池已满生产者须等待。第三章进程同步与死锁()put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中并用整型变量count来表示在缓冲池中已有的产品数目当count≥n时表示缓冲池已满生产者须等待。()get(item)过程。消费者利用该过程从缓冲池中取出一个产品当count≤时表示缓冲池中已无可取用的产品消费者应等待。第三章进程同步与死锁typeproducerconsumer=monitorVarin,out,count:integerbuffer:array[,…,n]ofitemnotfull,notempty:conditionprocedureentryput(item)beginifcount≥nthennotfullwaitbuffer(in)∶=nextpin∶=(in)modncount∶=countifnotemptyqueuethennotemptysignalend第三章进程同步与死锁procedureentryget(item)beginifcount≤thennotemptywaitnextc∶=buffer(out)out∶=(out)modncount∶=countifnotfullquenethennotfullsignalendbeginin∶=out∶=count∶=end第三章进程同步与死锁在利用管程解决生产者消费者问题时其中的生产者和消费者可描述为:producer:beginrepeatproduceaniteminnextpPCput(item)untilfalseendconsumer:beginrepeatPCget(item)consumetheiteminnextcuntilfalseend第三章进程同步与死锁进程通信一、进程通信的类型共享存储器系统(SharedMemorySystem)基于共享数据结构的通信方式。()基于共享存储区的通信方式。一、进程通信的类型二、消息传递通信的实现方法四、消息缓冲队列通信机制第三章进程同步与死锁消息传递系统(Messagepassingsystem)不论是单机系统、多机系统还是计算机网络消息传递机制都是用得最广泛的一种进程间通信的机制。在消息传递系统中进程间的数据交换是以格式化的消息(message)为单位的在计算机网络中又把message称为报文。程序员直接利用系统提供的一组通信命令(原语)进行通信。操作系统隐藏了通信的实现细节大大减化了通信程序编制的复杂性而获得广泛的应用。消息传递系统的通信方式属于高级通信方式。又因其实现方式的不同而进一步分成直接通信方式和间接通信方式两种。第三章进程同步与死锁管道(Pipe)通信所谓“管道”是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件又名pipe文件。向管道(共享文件)提供输入的发送进程(即写进程)以字符流形式将大量的数据送入管道而接受管道输出的接收进程(即读进程)则从管道中接收(读)数据。由于发送进程和接收进程是利用管道进行通信的故又称为管道通信。这种方式首创于UNIX系统由于它能有效地传送大量数据因而又被引入到许多其它操作系统中。第三章进程同步与死锁为了协调双方的通信管道机制必须提供以下三方面的协调能力:①互斥即当一个进程正在对pipe执行读写操作时其它(另一)进程必须等待。②同步指当写(输入)进程把一定数量(如KB)的数据写入pipe便去睡眠等待直到读(输出)进程取走数据后再把他唤醒。当读进程读一空pipe时也应睡眠等待直至写进程将数据写入管道后才将之唤醒。③确定对方是否存在只有确定了对方已存在时才能进行通信。返回第三章进程同步与死锁二、消息传递通信的实现方法直接通信方式这是指发送进程利用OS所提供的发送命令直接把消息发送给目标进程。此时要求发送进程和接收进程都以显式方式提供对方的标识符。通常系统提供下述两条通信命令(原语):Send(Receiver,message)发送一个消息给接收进程Receive(Sender,message)接收Sender发来的消息例如原语Send(P,m)表示将消息m发送给接收进程P而原语Receive(Pm)则表示接收由P发来的消息m。第三章进程同步与死锁在某些情况下接收进程可与多个发送进程通信因此它不可能事先指定发送进程。例如用于提供打印服务的进程它可以接收来自任何一个进程的“打印请求”消息。对于这样的应用在接收进程接收消息的原语中的源进程参数是完成通信后的返回值接收原语可表示为:Receive(id,message)第三章进程同步与死锁我们还可以利用直接通信原语来解决生产者消费者问题。当生产者生产出一个产品(消息)后便用Send原语将消息发送给消费者进程而消费者进程则利用Receive原语来得到一个消息。如果消息尚未生产出来消费者必须等待直至生产者进程将消息发送过来。生产者消费者的通信过程可分别描述如下:repeat…produceaniteminnextp…send(consumer,nextp)untilfalserepeatreceive(producer,nextc)…consumetheiteminnextcuntilfalse第三章进程同步与死锁间接通信方式()信箱的创建和撤消。进程可利用信箱创建原语来建立一个新信箱。创建者进程应给出信箱名字、信箱属性(公用、私用或共享)对于共享信箱还应给出共享者的名字。当进程不再需要读信箱时可用信箱撤消原语将之撤消。()消息的发送和接收。当进程之间要利用信箱进行通信时必须使用共享信箱并利用系统提供的下述通信原语进行通信。Send(mailbox,message)将一个消息发送到指定信箱Receive(mailbox,message)从指定信箱中接收一个消息第三章进程同步与死锁信箱可由操作系统创建也可由用户进程创建创建者是信箱的拥有者。据此可把信箱分为以下三类。)私用信箱用户进程可为自己建立一个新信箱并作为该进程的一部分。信箱的拥有者有权从信箱中读取消息其他用户则只能将自己构成的消息发送到该信箱中。这种私用信箱可采用单向通信链路的信箱来实现。当拥有该信箱的进程结束时信箱也随之消失。第三章进程同步与死锁)公用信箱它由操作系统创建并提供给系统中的所有核准进程使用。核准进程既可把消息发送到该信箱中也可从信箱中读取发送给自己的消息。显然公用信箱应采用双向通信链路的信箱来实现。通常公用信箱在系统运行期间始终存在。)共享信箱它由某进程创建在创建时或创建后指明它是可共享的同时须指出共享进程(用户)的名字。信箱的拥有者和共享者都有权从信箱中取走发送给自己的消息。第三章进程同步与死锁在利用信箱通信时在发送进程和接收进程之间存在以下四种关系:()一对一关系。这时可为发送进程和接收进程建立一条两者专用的通信链路使两者之间的交互不受其他进程的干扰。()多对一关系。允许提供服务的进程与多个用户进程之间进行交互也称为客户服务器交互(clientserverinteraction)。()一对多关系。允许一个发送进程与多个接收进程进行交互使发送进程可用广播方式向接收者(多个)发送消息。()多对多关系。允许建立一个公用信箱让多个进程都能向信箱中投递消息也可从信箱中取走属于自己的消息。第三章进程同步与死锁进程同步方式发送进程阻塞、接收进程阻塞。()发送进程不阻塞、接收进程阻塞。()发送进程和接收进程均不阻塞。三、消息传递系统实现中的若干问题(略)返回第三章进程同步与死锁四、消息缓冲队列通信机制消息缓冲队列通信机制中的数据结构()消息缓冲区。在消息缓冲队列通信方式中主要利用的数据结构是消息缓冲区。它可描述如下:typemessagebuffer=recordsender发送者进程标识符size消息长度text消息正文next指向下一个消息缓冲区的指针end第三章进程同步与死锁()PCB中有关通信的数据项。在利用消息缓冲队列通信机制时在设置消息缓冲队列的同时还应增加用于对消息队列进行操作和实现同步的信号量并将它们置入进程的PCB中。在PCB中应增加的数据项可描述如下:typeprocesscontrolblock=record…mq消息队列队首指针mutex消息队列互斥信号量sm消息队列资源信号量…end第三章进程同步与死锁发送原语发送进程在利用发送原语发送消息之前应先在自己的内存空间设置一发送区a见图所示把待发送的消息正文、发送进程标识符、消息长度等信息填入其中然后调用发送原语把消息发送给目标(接收)进程。发送原语首先根据发送区a中所设置的消息长度asize来申请一缓冲区i接着把发送区a中的信息复制到缓冲区i中。为了能将i挂在接收进程的消息队列mq上应先获得接收进程的内部标识符j然后将i挂在jmq上。由于该队列属于临界资源故在执行insert操作的前后都要执行wait和signal操作。第三章进程同步与死锁图消息缓冲通信第三章进程同步与死锁proceduresend(receiver,a)begingetbuf(asize,i)根据asize申请缓冲区isender∶=asender将发送区a中的信息复制到消息缓冲区之中isize∶=asizeitext∶=atextinext∶=getid(PCBset,receiverj)获得接收进程内部标识符wait(jmutex)insert(jmq,i)将消息缓冲区插入消息队列signal(jmutex)signal(jsm)end第三章进程同步与死锁接收原语接收原语描述如下:procedurereceive(b)beginj∶=internalnamej为接收进程内部的标识符wait(jsm)wait(jmutex)remove(jmq,i)将消息队列中第一个消息移出signal(jmutex)bsender∶=isender将消息缓冲区i中的信息复制到接收区bbsize∶=isizebtext∶=itextend第三章进程同步与死锁线程的概念线程与进程的关系线程的状态线程类型线程的概念第三章进程同步与死锁线程的概念线程是一个进程内的基本调度单位也称为轻型进程。它可以由操作系统内核控制也可以由用户程序控制。操作系统设计的问题是既要提高系统内多个程序的并发程度,又要尽量减少系统开销。作为进程的两个基本特性,资源分配的独立单位特性和调度的基本单位特性是可以分开的,于是引入线程概念。多线程意味着一个程序的多行语句同时执行。从物理上看,线程是处理机调度的基本单位。从逻辑上看,线程是指程序内部一个单位的顺序控制流。返回第三章进程同步与死锁线程与进程的关系线程具有传统进程的许多特征将线程称为轻型进程传统进程称为重型进程。线程与进程的关系可以从四方面来分析比较:调度和切换并发性拥有资源系统开销线程成为调度的基本单位而进程则作为拥有资源的基本单位使传统进程的两个属性分开使得线程能够轻装运行这样可显著地提高系统的并发程度。在同一进程中线程的切换不会引起进程切换只有在不同进程间的线程间的切换才会引起进程切换。在现代操作系统中进程之间可以并发执行同时在同一进程中的多个线程之间也可以并发执行从而使操作系统具有更好的并发性能更有效地使用系统资源和提高系统吞吐量。线程自己不拥有系统资源(除了一点必不可少的资源外)但是它可以访问其所属进程的资源。即一个进程的资源如已打开的文件、IO设备等可供同一进程内的所有线程共享。在进行进程切换时要保存当前进程CPU环境和设置新运行进程的CPU环境。但是线程的切换只需要保存和设置少量寄存器的内容并不涉及存储器管理方面的操作。所以进程切换的开销也远远大于线程切换的开销。返回第三章进程同步与死锁线程的状态线程也具有:就绪、阻塞和运行三种状态。一般来说线程是没有挂起状态的。线程的四个基本操作:创建新线程是在创建新进程时同时创建的。同进程一样当需要等待一个事件时它将被阻塞。创建线程线程的阻塞当线程等待的一个事件到来时就可由阻塞状态转变成就绪状态了。线程的唤醒当线程执行任务结束后系统将释放它所占用的寄存器上下文和栈空间。线程的完成返回第三章进程同步与死锁线程类型用户级线程不依赖于内核线程一般分为两类:用户级线程(UseLevelThreads)核心级线程(KernelSupportedThreads)核心级线程是由内核支持的线程这些线程依赖于内核。第三章进程同步与死锁与核心级线程相比用户级线程的优点:只需要完成线程切换就可以了这就大大节省了用户态与核心态两种模式之间的切换开销。这是因为管理线程的数据结构都是处于同一进程的用户地址空间。()调度程序的特定性()灵活性由于无需修改下层的核就可以支持用户级线程所以用户级线程能在任何操作系统上运行。它能够面向特定的应用系统调度。()线程间的切换不需要核心态特权。第三章进程同步与死锁将一个进程内的控制从一个线程转换到另一个线程时需要切换到核心态。在纯核心级线程机构中所有的线程管理是由内核来完成的。在应用程序领域没有线程管理代码只是简单地靠应用程序接口访问内核的线程结构。这种方法被许多操作系统所采用像WindowsNT和OS。图描述了纯核心级线程结构。核心级线程的缺点:第三章进程同步与死锁用户级线程与核心级线程的区别在于:线程的调度与切换速度内核支持线程的调度和切换与进程十分相象。当然线程调度和切换所花费的开销要比进程小得多。例如当一个线程阻塞后会自动地切换到下一个具有相同功能的线程所以用户级线程的切换速度很快。用户级线程的切换通常是发生在一个应用进程的诸线程之间不仅无须通过中断进入操作系统内核而且切换的规则也远比进程的规则简单。第三章进程同步与死锁系统调用如果系统中设置的是内核支持线程则调度是以线程为单位的。当一个线程调用一个系统调用时内核把系统调用只看作是该线程的行为因而阻塞该线程并调度该进程中的其它线程执行。这样就提高了运行效率。在用户级线程调用一个系统调用时由于内核把系统调用看作是整个进程的行为于是使该进程等待而调度另一个进程执行同样是在内核完成系统调用返回时进程才能继续执行。第三章进程同步与死锁线程执行时间进程P可以获得的CPU时间是进程P的倍进程P可使个系统调用并发工作但是P只能是一个系统调用工作。在只设置了用户级线程的系统中进程是调度的基本单位。如果采用轮转调度算法各个进程轮流执行一个时间片这对诸进程而言好像是公平的。但假如在进程P中包含了一个用户级线程而在另一个进程P中含有个线程。这样以来进程P中线程的运行时间将是进程P中各线程运行时间的倍当然速度就快倍。假如系统中是设置的内核支持线程它的调度是以线程为单位进行的第三章进程同步与死锁多线程OS中的进程在多线程OS中进程是作为拥有系统资源的基本单位通常的进程都包含多个线程并为它们提供资源但此时的进程就不再作为一个执行的实体。多线程OS中的进程有以下属性:()作为系统资源分配的单位。()可包括多个线程。()进程不是一个可执行的实体。第三章进程同步与死锁三、内核支持线程和用户级线程内核支持线程这里所谓的内核支持线程也都同样是在内核的支持下运行的即无论是用户进程中的线程还是系统进程中的线程他们的创建、撤消和切换等也是依靠内核实现的。此外在内核空间还为每一个内核支持线程设置了一个线程控制块内核是根据该控制块而感知某线程的存在的并对其加以控制。第三章进程同步与死锁用户级线程用户级线程仅存在于用户空间中。对于这种线程的创建、撤消、线程之间的同步与通信等功能都无须利用系统调用来实现。对于用户级线程的切换通常是发生在一个应用进程的诸多线程之间这时也同样无须内核的支持。由于切换的规则远比进程调度和切换的规则简单因而使线程的切换速度特别快。可见这种线程是与内核无关的。返回第三章进程同步与死锁一、产生死锁的原因竞争资源。()进程间推进顺序非法。产生死锁的原因和必要条件死锁死锁是两个以上的进程为竞争系统资源而无休止的相互等待造成不可终止的状态。产生死锁的原因和必要条件一、产生死锁的原因二、产生死锁的必要条件三、处理死锁的基本方法预防死锁的方法一、预防死锁二、系统安全状态三、利用银行家算法避免死锁死锁的检测与解除一、死锁的检测二、死锁的解除第三章进程同步与死锁竞争资源引起进程死锁可剥夺和非剥夺性资源)竞争非剥夺性资源)竞争临时性资源第三章进程同步与死锁图IO设备共享时的死锁情况第三章进程同步与死锁图进程之间通信时的死锁返回第三章进程同步与死锁PP……………………………………………………………………………………••………………完成任务点危险区不可达到区死锁点PRel(R)PRel(R)PReq(R)PReq(R)Req(R)PReq(R)PRel(R)PRel(R)P图:两进程联合推进安全到达释放申请释放申请…………………进程推进顺序不当引起死锁返回第三章进程同步与死锁二、产生死锁的必要条件互斥条件()请求和保持条件()不剥夺条件()环路等待条件返回第三章进程同步与死锁三、处理死锁的基本方法预防死锁。()避免死锁。()检测死锁。()解除死锁。返回第三章进程同步与死锁预防死锁的方法一、预防死锁摒弃“请求和保持”条件摒弃“不剥夺”条件摒弃“环路等待”条件第三章进程同步与死锁二、系统安全状态安全状态在避免死锁的方法中允许进程动态地申请资源但系统在进行资源分配之前应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态则将资源分配给进程否则令进程等待。所谓安全状态是指系统能按某种进程顺序(P,P,…Pn)(称〈P,P,…,Pn〉序列为安全序列)来为每个进程Pi分配其所需资源直至满足每个进程对资源的最大需求使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列则称系统处于不安全状态。第三章进程同步与死锁安全状态之例我们通过一个例子来说明安全性。假定系统中有三个进程P、P和P共有台磁带机。进程P总共要求台磁带机P和P分别要求台和台。假设在T时刻进程P、P和P已分别获得台、台和台磁带机尚有台空闲未分配如下表所示:经分析:发现T时刻是安全的存在一个安全系列:P,P,P,使之系统按此进程系列分配资源,就可使每个进程顺利顺利完成。第三章进程同步与死锁由安全状态向不安全状态的转换如果不按照安全序列分配资源则系统可能会由安全状态进入不安全状态。例如在T时刻以后P又请求台磁带机若此时系统把剩余台中的台分配给P则系统便进入不安全状态。因为此时也无法再找到一个安全序列例如把其余的台分配给P这样在P完成后只能释放出台既不能满足P尚需台的要求也不能满足P尚需台的要求致使它们都无法推进到完成彼此都在等待对方释放资源即陷入僵局结果导致死锁。返回第三章进程同步与死锁三、利用银行家算法避免死锁银行家算法中的数据结构()可利用资源向量Available。这是一个含有m个元素的数组其中的每一个元素代表一类可利用的资源数目其初始值是系统中所配置的该类全部可用资源的数目其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K则表示系统中现有Rj类资源K个。第三章进程同步与死锁()最大需求矩阵Max。这是一个n×m的矩阵它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K则表示进程i需要Rj类资源的最大数目为K()分配矩阵Allocation。这也是一个n×m的矩阵它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K则表示进程i当前已分得Rj类资源的数目为K。()需求矩阵Need。这也是一个n×m的矩阵用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K则表示进程i还需要Rj类资源K个方能完成其任务。Need[i,j]=Max[i,j]Allocation[i,j]第三章进程同步与死锁银行家算法设Requesti是进程Pi的请求向量如果Requesti[j]=K表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后系统按下述步骤进行检查:()如果Requesti[j]≤Need[i,j]便转向步骤否则认为出错因为它所需要的资源数已超过它所宣布的最大值。()如果Requesti[j]≤Available[j]便转向步骤()否则表示尚无足够资源Pi须等待。第三章进程同步与死锁()系统试探着把资源分配给进程Pi并修改下面数据结构中的数值:Available[j]∶=Available[j]Requesti[j]Allocation[i,j]∶=Allocation[i,j]Requesti[j]Need[i,j]∶=Need[i,j]Requesti[j]()系统执行安全性算法检查此次资源分配后系统是否处于安全状态。若安全才正式将资源分配给进程Pi以完成本次分配否则将本次的试探分配作废恢复原来的资源分配状态让进程Pi等待。第三章进程同步与死锁安全性算法()设置两个向量:①工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目它含有m个元素在执行安全算法开始时Work∶=Available②Finish:它表示系统是否有足够的资源分配给进程使之运行完成。开始时先做Finish[i]∶=false当有足够资源分配给进程时再令Finish[i]∶=true。第三章进程同步与死锁()从进程集合中找到一个能满足下述条件的进程:①Finish[i]=false②Need[i,j]≤Work[j]若找到执行步骤()否则执行步骤()。()当进程Pi获得资源后可顺利执行直至完成并释放出分配给它的资源故应执行:Work[j]∶=Work[i]Allocation[i,j]Finish[i]∶=truegotostep()如果所有进程的Finish[i]=true都满足则表示系统处于安全状态否则系统处于不安全状态。第三章进程同步与死锁银行家算法之例假定系统中有五个进程{P,P,P,P,P}和三类资源{A,B,C}各种资源的数量分别为、、在T时刻的资源分配情况如图所示。图T时刻的资源分配表首先试为P分配情况如括号资源分配时,Work-need≥()则分配否则继续查找下一个进程第三章进程同步与死锁()T时刻的安全性:图T时刻的安全序列系统可提供进程尚需量系统已分量系统回收后情况=availabe完成状况资源分配时,Work-need≥()则分配否则继续查找下一个进程第三章进程同步与死锁()P请求资源:P发出请求向量Request()系统按银行家算法进行检查:①Request(,,)≤Need(,,)②Request(,,)≤Available(,,)③系统先假定可为P分配资源并修改Available,Allocation和Need向量由此形成的资源变化情况如图中的圆括号所示。④再利用安全性算法检查此时系统是否安全。第三章进程同步与死锁图P申请资源时的安全性检查系统可提供进程尚需量系统已分量系统回收后情况=availabe第三章进程同步与死锁()P请求资源:P发出请求向量Request()系统按银行家算法进行检查:①Request(,,)≤Need(,,)②Request(,,)<Available(,,)让P等待。()P请求资源:P发出请求向量Requst()系统按银行家算法进行检查:①Request(,,)≤Need(,,)②Request(,,)≤Available(,,)③系统暂时先假定可为P分配资源并修改有关数据如图所示。第三章进程同步与死锁图为P分配资源后的有关资源数据返回系统回收后情况=availabe系统已分量进程尚需量第三章进程同步与死锁死锁的检测与解除一、死锁的检测资源分配图(ResourceAllocationGraph)图每类资源有多个时的情况第三章进程同步与死锁()凡属于E中的一个边e∈E都连接着P中的一个结点和R中的一个结点e={pi,rj}是资源请求边由进程pi指向资源rj它表示进程pi请求一个单位的rj资源。e={rj,pi}是资源分配边由资源rj指向进程pi,它表示把一个单位的资源rj分配给进程pi。第三章进程同步与死锁死锁定理图资源分配图的简化第三章进程同步与死锁死锁检测中的数据结构()可利用资源向量Available它表示了m类资源中每一类资源的可用数目。()把不占用资源的进程(向量Allocation∶=)记入L表中即Li∪L。()从进程集合中找到一个Requesti≤Work的进程做如下处理:①将其资源分配图简化释放出资源增加工作向量Work∶=WorkAllocationi。②将它记入L表中。第三章进程同步与死锁()若不能把所有进程都记入L表中便表明系统状态S的资源分配图是不可完全简化的。因此该系统状态将发生死锁。Work∶=AvailableL∶={Li|Allocationi=∩Requesti=}forallLiLdobeginforallRequesti≤WorkdobeginWork∶=WorkAllocationiLi∪Lendenddeadlock∶=(L={p,p,…,pn})返回第三章进程同步与死锁二、死锁的解除剥夺资源。()撤消进程。为把系统从死锁状态中解脱出来所花费的代价可表示为:R(S)min=min{Cui}min{Cuj}min{Cuk}…第三章进程同步与死锁图付出代价最小的死锁解除方法第三章进程同步与死锁补充习题答案、有三个并发进程:R负责从输入设备读入信息块M负责对信息块加工处理P负责打印输出信息块。今提供:()一个缓冲区可放置K个信息块()二个缓冲区每个可放置K个信息块试用信号量和P、V操作写出三个进程正确工作的流程。第三章进程同步与死锁()的答案:一、画出流程图第三章进程同步与死锁()的答案:二、设计信号量、变量及初值varB:array,kofitem信息块数组sread:semaphore:=kR读入信息用信号量smanage:semaphore:=M读写用信号量swrite:semaphore:=P打印用信号量rptr:integer:=R读入信息用指针mptr:integer:=M读写用指针wptr:integer:=P打印用指针x:item信息内容第三章进程同步与死锁()的答案:三、填写PV操作P(sread)V(smanage)mptr:=(mptr)modkP(smanage)V(smanage)wptr:=(wptr)kP(swrite)V(sread)V(swrite)P(smanage)rptr:=(rptr)modkP(smanage)第三章进程同步与死锁()的答案:四、写出伪代码processM{L:P(smanage)x:=BmptrmanagethemessageinxBmptr:=xmptr:=(mptr)modkV(swrite)gotoL}ProcessP{L:P(swrite)x:=Bwptrwptr:=(wptr)kV(sread)PrintthemessageinxgotoL}coendcobeginprocessR{L:readamessageintoxP(sread)Brptr:=xrptr:=(rptr)modkV(smanage)gotoL}第三章进程同步与死锁()的答案:一、画出流程图M进程从A取出信息加工后放入B加工处理第三章进程同步与死锁()的答案:设计信号量指针及初值()答案varA,B:array,kofitemAB缓冲区数组sput:semaphore:=kA缓冲区送数信号量sput:semaphore:=kB缓冲区送数信号量sget:semaphore:=A缓冲区取数信号量sget:semaphore:=B缓冲区取数信号量put:integer:=A缓冲区送数指针put:integer:=B缓冲区送数指针get:integer:=A缓冲区取数指针get:integer:=B缓冲区取数指针cobegin第三章进程同步与死锁()的答案:三、流程图上添PV操作P(sput)put:=(put)modkV(sget)P(sget)get:=(get)modkV(sput)put:=(put)modkV(sget)P(sput)P(sget)get:=(get)modkV(sput)第三章进程同步与死锁()答案:四、伪代码varA,B:array,kofitemsput:semaphore:=ksput:semaphore:=ksget:semaphore:=sget:semaphore:=put:integer:=put:integer:=get:integer:=get:integer:=cobeginbeginL:readamessageintoxP(sput)Aput:=xput:=(put)modkV(sget)GotoLend第三章进程同步与死锁processmanagerbeginL:P(sget)x:=Agetget:=(get)modkV(sput)ManagethemessageintoxP(sput)Bput:=xput:=(put)modkV(sget)GotoLendprocesswriterbeginL:P(sget)x:=Bgetget:=(get)modkV(sput)PrintthemessageinxGotoLendcoend第三章进程同步与死锁、系统有A、B、C、D共种资源在某时刻进程P、P、P、P和P对资源的占有和需求情况如表试解答下列问题:系统此时处于安全状态吗?若此时P发出request(、、、)系统能分配资源给它吗?为什么?第二题答:()系统处于安全状态存在安全序列:PPPPP。()不能分配否则系统会处于不安全状态。ProcessAllocationClaimAvailableABCDABCDABCDPPPPP第三章进程同步与死锁第二三章内容小结进程的定义是基础(题集)进程的静态组成进程控制块的定义、意义程序的分类:纯的和不纯的进程状态及状态转换、状态转换的原因及其应用:,,,教材页题CPU执行状态分为核心态和用户态系统指令分为特权和非特权指令:进程控制,进程调度的条件时机步骤教材页,,题进程同步与互斥中信号量的物理意义、初值的设置:生产者消费者问题非常重要须记住:(教材~页)当前有那几种通信机制:(教材~页)共享存储系统消息传递系统管道通信系统。其中消息传递系统功能为(页):数据交换格式化通信细节透明支持多机系统表示第二章第一大题第小题第三章进程同步与死锁试说明进程在三个基本状态之间转换的典型原因答案:a处于就绪状态的进程当进程调度程序为之分配了处理机后该进程便由就绪状态变为执行状态b当前进程因发生某事件而无法执行如访问已被占用的临界资源就会使进程由执行状态转变为阻塞状态c当前进程因时间片用完而被暂停执行该进程便由执行状态转变为就绪状态返回上页处理机调度中,调度适应,作业调度及有关调度算法,调度来源重点是进程调度:进程调度算法方式,进程调度与控制调度与系统开销死锁产生的基本原因与必要条件:处理死锁的方法:,第二三章内容小结第三章进程同步与死锁第二三章内容小结教材页,,题试说明引起进程创建的主要事件答案:a用户登陆b作业调度c提供服务d应用请求试说明引起进程撤消的主要事件正常结束b异常结束c外界干预在创建一个进程时需完成的主要工作是什么a操作系统发现请求创建新进程事件后调用进程创建原语Creat()b申请空白PCBc为新进程分配资源d初始化进程控制块e将新进程插入就绪队列试说明引起进程阻塞或被唤醒的主要事件是什么答案:a请求系统服务b启动某种操作c新数据尚未到达d无新工作可

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/125

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利