第七次作业死锁

7.3，7.6，7.5，7.16，7.23，7.277.3Considerthefollowingsnapshotofasystem:AllocationMaxAvailableABCDABCDABCDP0001200121520P110001750P213542356P306320652P400140656Answerthefollowingquestionsusingthebanker’salgorithm:a.WhatisthecontentofthematrixNeed?b.Isthesysteminasafestate?c.IfarequestfromprocessP1arrivesfor(0,4,2,0),cantherequestbegrantedimmediately?答：a：需要一个n*m大小的matrixNeed，即5个进程*4个资源类型：4×5=20b：首先P0执行，等P0执行完之后，释放资源，可用资源为：1532然后P1不可以进行P2可执行，等P2执行完之后，释放资源，可用资源为：2886P3可执行，等P3执行完之后，释放资源，可用资源为：214118P4可执行，等P4执行完之后，释放资源，可用资源为：2141212P1可执行，等P1执行完之后，释放资源，可用资源为：3141212全部进行完毕，所以系统是安全的。c：如果P1的请求立刻被授予，那么可用的资源还剩1100首先P0执行，等P0执行完之后，释放资源，可用资源为：1112然后P1不可以进行P2可执行，等P2执行完之后，释放资源，可用资源为：2466P3可执行，等P3执行完之后，释放资源，可用资源为：21098P4可执行，等P4执行完之后，释放资源，可用资源为：2101012P1可执行，等P1执行完之后，释放资源，可用资源为：3101012所以可以被赋予。7.5ProvethatthesafetyalgorithmpresentedinSection7.5.3requiresanorderofm×n2operations.（证明7.5.3中的安全算法需要m×n2的复杂度）答：因为进程序列最差情况是完全逆序的，每次遍历一遍进程序列，只会执行一次进程，所以需要n次遍历长度为n的进程序列，所以复杂度为n2，又因为每次判断，都需要判断m种资源，所以复杂度需要再乘m，所以复杂度为)*(2nm。伪代码如图所示：7.6Consideracomputersystemthatruns5,000jobspermonthandhasnodeadlock-preventionordeadlock-avoidancescheme.Deadlocksoccurabouttwicepermonth,andtheoperatormustterminateandrerunabouttenjobsperdeadlock.Eachjobisworthabouttwodollars(inCPUtime),andthejobsterminatedtendtobeabouthalfdonewhentheyareaborted.Asystemsprogrammerhasestimatedthatadeadlock-avoidancealgorithm(likethebanker’salgorithm)couldbeinstalledinthesystemwithanincreaseofabout10percentintheaverageexecutiontimeperjob.Sincethemachinecurrentlyhas30percentidletime,all5,000jobspermonthcouldstillberun,althoughturnaroundtimewouldincreasebyabout20percentonaverage.a.Whataretheargumentsforinstallingthedeadlock-avoidancealgorithm?b.Whataretheargumentsagainstinstallingthedeadlock-avoidancealgorithm?a.可以确保永远不会发生死锁。此外，尽管周转时间有所增加，但所有5,000个工作岗位仍然可以运行。b.死锁很少发生，并且在它们发生时它们的成本很低。7.16Inarealcomputersystem,neithertheresourcesavailablenorthedemandsofprocessesforresourcesareconsistentoverlongperiods(months).Resourcesbreakorarereplaced,newprocessescomeandgo,andnewresourcesareboughtandaddedtothesystem.Ifdeadlockiscontrolledbythebanker’salgorithm,whichofthefollowingchangescanbemadesafely(withoutintroducingthepossibilityofdeadlock),andunderwhatcircumstances?a.IncreaseAvailable(newresourcesadded).b.DecreaseAvailable(resourcepermanentlyremovedfromsystem).c.IncreaseMaxforoneprocess(theprocessneedsorwantsmoreresourcesthanallowed).d.DecreaseMaxforoneprocess(theprocessdecidesitdoesnotneedthatmanyresources).e.Increasethenumberofprocesses.f.Decreasethenumberofprocesses.答：a、d、f在任何条件下都是可以被安全引进的。b.减少可用资源(资源被从系统中永久性地移出):这可能会影响到系统,并导致可能性死锁因为系统的安全性假定其拥有一定数量的可用资源c.增加一个进程的Max(进程需要更多的资源,超过所允许给予的资源):这可能会影响到系统,并可能导致死锁e.增加进程的数量:如果允许分配资源给新进程,那么该系统并没有进入一个不安全的状态7.23Considerthefollowingsnapshotofasystem:AllocationMaxAvailableABCDABCDABCDP0200142123321P131215252P221032316P313121424P414323665Answerthefollowingquestionsusingthebanker’salgorithm:a.Illustratethatthesystemisinasafestatebydemonstratinganorderinwhichtheprocessesmaycomplete.（通过演示进程可能完成的顺序，说明系统处于安全状态。）b.IfarequestfromprocessP1arrivesfor(1,1,0,0),cantherequestbegrantedimmediately?c.IfarequestfromprocessP4arrivesfor(0,0,2,0),cantherequestbegrantedimmediately?a.对于P0还需要2211的资源，可用资源为3321，所以P0可以执行P0执行完之后，释放资源，可用资源变为5322对于P1还需要2131的资源，可用资源为5322，所以P1不可以执行对于P2还需要0213的资源，可用资源为5322，所以P2不可以执行对于P3还需要0112的资源，可用资源为5322，所以P3可以执行P3执行完之后，释放资源，可用资源变为6634对于P4还需要2233的资源，可用资源为6634，所以P4可以执行P4执行完之后，释放资源，可用资源变为71066对于P1还需要2131的资源，可用资源为71066，所以P1可以执行P1执行完之后，释放资源，可用资源变为101187对于P2还需要0213的资源，可用资源为101187，所以P2可以执行全部进程都可以执行完毕，此操作系统的安全的，执行序列为P0，P3，P4，P1，P2b.首先，可用资源为3321，P1请求1100，可以满足。假设P1的请求被满足，当前可用资源为2221P0可执行，可用资源变为4222P1，P2不可执行。P3可执行，可用资源变为5534P4可执行，可用资源变为6966P1可执行，可用资源变为101187P2可执行全部进程都可以执行完毕，所以系统是安全的，执行序列为P0，P3，P4，P1，P2所以可以立刻授予P1的请求。c.首先，可用资源为3321，P4请求0020，可以满足。假设P4的请求被满足，当前可用资源为3301P0，P1，P2，P3，P4不可执行。所以系统不是安全的，所以不可以立刻授予P4的请求。7.27ImplementyoursolutiontoExercise7.25usingPOSIXsynchronization.Inparticular,representnorthboundandsouthboundfarmersasseparatethreads.Onceafarmerisonthebridge,theassociatedthreadwillsleepforarandomperiodoftime,representingtravelingacrossthebridge.Designyourprogramsothatyoucancreateseveralthreadsrepresentingthenorthboundandsouthboundfarmers.7.25Asingle-lanebridgeconnectsthetwoVermontvillagesofNorthTunbridgeandSouthTunbridge.Farmersinthetwovillagesusethisbridgetodelivertheirproducetotheneighboringtown.Thebridgecanbecomedeadlockedifanorthboundandasouthboundfarmergetonthebridgeatthesametime.(Vermontfarmersarestubbornandareunabletobackup.)Usingsemaphoresand/ormutexlocks,designanalgorithminpseudocodethatpreventsdeadlock.Initially,donotbeconcernedaboutstarvation(thesituationinwhichnorthboundfarmerspreventsouthboundfarmersfromusingthebridge,orviceversa).答：使用POSIX的无名信号量来操作POSIX同步。#includestdio.h#includeunistd.h#includepthread.h#includesemaphore.h//线程1void*thread_func1(void*arg);//线程2void*thread_func2(void*arg);sem_tsem;//信号量初始化sem_init(&sem,0,1);intcount=0;intmain(void){pthread_ttid1,tid2;pthread_create(&tid1,NULL,thread_func1,0);pthread_create(&tid2,NULL,thread_fu