湖南大学操作系统作业-(4)

操作系统第二次作业第七章7.2Considerthedeadlocksituationthatcouldoccurinthedining-philosophersproblemwhenthephilosophersobtainthechopsticksoneatatime.Discusshowthefournecessaryconditionsfordeadlockindeedholdinthissetting.Discusshowdeadlockscouldbeavoidedbyeliminatinganyoneofthefourconditions.考虑哲学家进餐问题中可能出现死锁的情况，即当哲学家一次拿一只筷子时，讨论4个死锁必要条件的存在性，讨论如何通过避免四种情况之一来消除死锁答死锁的4个必要条件为：互斥、占有等待、非抢占、循环等待考虑互斥性，A哲学家拿了筷子C1后该C1筷子在未被释放资源前无法被其他哲学家B获取，故互斥。这个问题可以通过哲学家的筷子可以互相使用来实现。考虑占有等待性，A哲学家必须先占有左手筷子C1，并等待右手筷子C2，而C2可能为其他哲学家所占有。这个问题可以通过设置哲学家在申请更多筷子时，必须释放现已分配的所有筷子，或协议每个哲学家在进餐前申请并获得所有筷子，即预先静态分配。考虑非抢占性，A哲学家占有筷子C1时不能被B哲学家抢占。这个问题可以通过协议某个哲学家占有筷子并申请另一个不能被立即分配的筷子时，那么其现已拥有的筷子均可被抢占，即自己剥夺自己。考虑循环等待，出现循环等待的可能性为：每个哲学家同时只拥有左手的筷子而等待右手的筷子，而右手的筷子只能通过右手的哲学家释放其左手的筷子才能得到，故出现循环等待。这个问题可以通过对筷子进行编号，对筷子的申请顺序由低到高来实现。7.6Considerasystemconsistingoffourresourcesofthesametypethataresharedbythreeprocesses,eachofwhichneedsatmosttworesources.Showthatthesystemisdeadlock-free.考虑一个由4种相同资源、3个共享进程，每个需要2个该资源的系统，试证明这个系统不会出现死锁答：这个问题比较简单，“抽屉原理”表明，4个资源分配给3个进程，则至少有一个进程分配到2个资源，那么该进程就得以运行，运行结束时，该进程会释放已分配的2个资源给系统里剩下的两个进程，这时4个资源分配给2个进程，不会出现死锁。7.7Considerasystemconsistingofmresourcesofthesametype,beingsharedbynprocesses.Resourcescanberequestedandreleasedbyprocessesonlyoneatatime.Showthatthesystemisdeadlockfreeifthefollowingtwoconditionshold:a.Themaximumneedofeachprocessisbetween1andmresourcesb.Thesumofallmaximumneedsislessthanm+n考虑一个系统由m个同种资源被n个进程共享，某一资源一次只能被请求或释放，证明这个系统如满足下面2个条件则不会死锁A每个进程最大需求资源为1-m之间B最大资源需求之和m+n答：每个进程占有资源Allocation[]并申请资源Need[]，如果发生了死锁，说明m个资源全部被分配，即∑Allocation[i]𝑛𝑖=1=m而由题设，∑Max[i]𝑛𝑖=1𝑚+𝑛而Max[i]=Allocation[i]+Need[i]，这说明∑Need[i]𝑛𝑖=1m+𝑛−𝑚，即∑Need[i]𝑛𝑖=1𝑛这说明n个进程，当前的总需求小于n，因而总有某个进程的需求Need[i]=0，即该进程不再需要请求资源，故该进程在完成后会释放资源，而进程在完成后会释放资源的数目为1~m之间，所以这个进程会把释放的资源分配给其他进程，如果再在某时刻出现∑Allocation[i]𝑛𝑖=1=m的情况，一样可以通过这个过程推导，得到某进程不再需要申请资源，进而说明该系统不会死锁。7.8Considerthedining-philosophersproblemwherethechopsticksareplacedatthecenterofthetableandanytwoofthemcouldbeusedbyaphilosopher.Assumethatrequestsforchopsticksaremadeoneatatime.Describeasimplerulefordeterminingwhetheraparticularrequestcouldbesatisfiedwithoutcausingdeadlockgiventhecurrentallocationofchopstickstophilosophers.考虑哲学家进餐问题，如果所有筷子放在桌子中间，且一个哲学家可以用任意两只筷子，假设一次只能请求一只筷子。描述一个简单的规则来确定在当前哲学家进餐的筷子分配情况下，是否一个特殊请求可以在不会触发死锁的情况下完成答：这个题目的描述很模糊…我的考虑是这样，如果已知了当前筷子的分配，在某个哲学家申请第一只筷子的时候，判断两个条件条件1：是否其他哲学家均没有同时拿到两根筷子的情况，（即所有哲学家占有并等待）条件2：是否桌上只剩一根筷子，（如果所有人占有等待，那么当前这个筷子只能分配给申请第二根筷子的哲学家，而不能分配给申请第一根筷子的哲学家）如果以上两个条件均为是，则不给该哲学家分配筷子，否则，分配给该哲学家筷子7.11Considerthefollowingsnapshotofasystem:AllocationMaxNeedAvailableABCDABCDABCDABCDP00012001200001520P1100017500750P2135423561002P3063206520020P4001406560642Answerthefollowingquestionsusingthebanker’salgorithm:a.WhatisthecontentofthematrixNeed?b.Isthesysteminasafestate?c.IfarequestfromprocessP1arrivesfor(0,4,2,0),cantherequestbegrantedimmediately?使用银行家算法回答下列问题ANeed矩阵的内容？B这是个安全状态的系统吗？CP1的某个请求需要[0420],这个需求能立即被满足吗？答：（A）Need矩阵的内容，公式为Need[i]=Max[i]-Allocation[i]，所以把Max矩阵和Allocation矩阵各项对应相减即可得到Need矩阵的内容。（B）安全状态判断：首先设置所有进程finish=false，从第一个finish=false进程开始按顺序判断，如果某进程Need矩阵全小于等于Available矩阵，则说明该进程可以得到资源分配，系统可以将资源分配给该进程并等待进程结束释放资源，同样将其Allocation加到Available矩阵上。将该进程finish设置为true。下面开始分析：P0进程：由于其Need矩阵全为0，说明可以释放资源，将该进程finish设置为true。将其Allocation加到Available矩阵上，此时Available矩阵为[1532]P1进程，Need矩阵不小于Available矩阵，故不分配资源，考虑下一进程P2进程，其need矩阵全小于等于Available矩阵，将该进程finish设置为true。将其Allocation加到Available矩阵上，此时Available矩阵为[2886]下面两种策略均可：一是从头循环，第二种是继续按顺序判断，我在此处采取第二种。P3进程，其need矩阵全小于等于Available矩阵，将该进程finish设置为true。将其Allocation加到Available矩阵上，此时Available矩阵为[214118]P4进程，其need矩阵全小于等于Available矩阵，将该进程finish设置为true。将其Allocation加到Available矩阵上，此时Available矩阵为[2141212]P1进程，其need矩阵全小于等于Available矩阵，将该进程finish设置为true。将其Allocation加到Available矩阵上，此时Available矩阵为[3141212]最终所有进程的finish均为true，说明系统安全（C）资源请求算法：如果request[i]need[i]，再判断request[i]avaiable，如果可以的话，更新矩阵的值为：Available-=request[i]，need[i]-=request[i]，allocation[i]+=request[i]然后再重新进行一次安全性判断，如果仍安全，说明可以立即分配，反之则不能立即分配request下面用这种方法来判断能否立即分配给request首先request[1]need[1]，且request[1]avaiable，分配给P1资源，并修正矩阵值当前available=[1100],need[1]=[1330],allocation[1]=[1420]下面按B的方法判断当前安全性首先选P0，其need矩阵全小于等于Available矩阵，将该进程finish设置为true。将其Allocation加到Available矩阵上，此时Available矩阵为[1112]P1不能得到满足，选取P2，其need矩阵全小于等于Available矩阵，将该进程finish设置为true。将其Allocation加到Available矩阵上，此时Available矩阵为[2466]选择P3，其need矩阵全小于等于Available矩阵，将该进程finish设置为true。将其Allocation加到Available矩阵上，此时Available矩阵为[21098]选择P4，其need矩阵全小于等于Available矩阵，将该进程finish设置为true。将其Allocation加到Available矩阵上，此时Available矩阵为[2101012]选择P1，其need矩阵全小于等于Available矩阵，将该进程finish设置为true。将其Allocation加到Available矩阵上，此时Available矩阵为[3141212]最终所有进程的finish均为true，说明系统安全,说明P1请求的资源可以立即满足。