视窗
loading...
您现在的位置:首页 > IT认证 > 软件水平 >

软考软件设计师重点难点:死锁


2012年软考软件设计师重点难点:死锁

  死锁(Deadlock)是指多个进程在运行的过程中因争夺资源而造成的一种僵局。当进程处于这种僵持状态时,若无外力作用,它们都将无法再向前推进。在软件设计师的考试当中,这个知识点的考查是以选择题的形式出现的,考点主要有:死锁的必要条件、解决死锁的方法,最难高难度会考到“银行家算法”。本文将介绍死锁的相关知识,但不会具体讲解“银行家算法”,该算法将在本系列的下一篇文章中详细说明。

  1、死锁发生的必要条件

  死锁的发生必须具备四个必要条件,这四个条件相互联系、缺一不可。

  (1)互斥条件:指进程对所分配到的资源进行排他性使用,即在一段时间内某资源只由一个进程占用。如果此时还有其他进程请求该资源,则请求者只能等待,直至占有该资源的进程用完并释放。

  (2)请求和保持条件:指进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源又已被其他进程占有,此时请求进程阻塞,但又对自己已获得的其他资源保持不放。

  (3)不剥夺条件:指进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完时由自己释放。

  (4)环路等待条件:指在发生死锁时,必然存在一个进程--资源的环形链,即进程集合{P0,P1,P2…Pn}中的P0正在等待一个P1占用的资源,P1正在等待P2占用的资源,……Pn正在等待已被P0占用的资源。

  2、解决死锁的策略

  解决死锁的策略通常有三种:死锁预防、死锁避免以及死锁解除。前两种方法是“事前措施”,而死锁解除是“事后解决方案”。

  (1)死锁预防:“解铃还需系铃人”,随便破坏导致死锁这任意一个必要条件就可以预防死锁。例如,要求用户申请资源时一起申请所需要的全部资源,这就破坏了保持和等待条件;将资源分层,得到上一层资源后,才能够申请下一层资源,它破坏了环路等待条件。预防通常会降低系统的效率。

  (2)死锁避免:避免是指进程在每次申请资源时判断这些操作是否安全,典型算法是“银行家算法”(本系列文章的下一篇将详细讲解该问题)。但这种算法会增加系统的开销。

  (3)死锁解除:该方法的思路很简单,通过死锁检测判断系统是否处于死锁状态,若死锁,则由系统强制剥夺部分进程的资源,将资源强行分配给别的进程。

  3、判断系统是否可能进入死锁状态

  从上面的死锁解决方案来看,无论哪一种方式都不可避免的要增加系统的负担。而同时一个系统是否有可进入死锁状态受系统资源数量,需要使用该资源的进程数量等因素影响。若系统本不可能引起死锁,而我们采用了死锁解决方案,是很不合理的。所以,考试中常考到这样的题型:给出系统的资源数,以及需要使用该资源的进程数量等参数,让考生判断系统有无可能产生死锁。下面我们以例题的方式来说明如何解决这类问题。

  例题1:

  系统有3个进程:A、B、C。这3个进程都需要5个系统资源。如果系统有多少个资源,则不可能发生死锁。

  解答:

  在分析这个问题时,我们可以取一些简单的数据代入试题进行验证、分析,以得到相应的规律。

  如:

  (1)当系统资源数量为9时,若给A与B分别分配了4个资源,C分配了1个资源,则系统中的每个进程都存在资源不足的情况,而都不放手自己拥有的资源。不能正常运行完毕,发生死锁。

  (2)当系统资源数量为12时,若给A、B、C各分配4个资源,则死锁。

  (3)当系统资源数量为13时,无论如何分配,总有至少1个进程能得到5个资源,得到5个资源的进程可以正常运行完毕,而后将自己占用的资源分配给其它进程,所以这样能使所有进程运行完毕。

  从上面的尝试,我们可以总结出一个规律:先给所有进程分配他们所需要的资源数减1个资源,然后系统如果能再剩余1个资源,则系统不会发生死锁。这样解答本题变得非常容易。

  (5-1)*3+1=13。

  例题2:

  一台计算机有10台磁带机被m个进程竞争,每个进程最多需要三台磁带机,那么m至多为 时,系统没有死锁的危险。

  A.3 B.4 C.5 D.6

  解答

  首先从m=6开始考察,首先每个进程分配1台,剩下的4台只能分配给4个进程,还有2个进程没有分配,如果已经分配了2台的4个进程需要3台的话,则系统就会死锁。同样,如果m=5,也会发生这种情况。当m=4时,每个进程可以分得2台,还有2个进程可分得3台,则可正常运行,运行完毕后可释放资源,从而不会死锁。在解这道题时有些学员提出“如果按照答案m=4,则这4个进程都是需要3台磁带机的话,共需要12台磁带机,这样还不会死锁?”。这种想法是错误的,因为并不是同时把所有进程都分配给足够的资源才能完成这些进程,可以是一个进程先执行完,释放完资源再执行另一个进程。

  例如:4个进程中,每个进程分配2台磁带机,用去了8台。剩下2台,仍然可以满足两个进程,直到他们完成,释放他们暂用的磁带机

闂傚倷绶氬ḿ褍螞瀹€鍕;闁跨噦鎷�

闂傚倷绶氬ḿ褍螞瀹€鍕;闁跨噦鎷�

闂傚倷绶氬ḿ褍螞濞嗘挸绀夐柡鍥ュ灩閸屻劑鏌曢崼婵囧閻庢艾顭烽弻銊モ攽閸℃ê鐝旂紓浣瑰敾缂嶄線寮婚敓鐘茬妞ゆ劧瀵岄埀顒侇殜閺岀喖鎽庨崒姘ギ闂佽鍟崶褔鍞堕梺缁樻煥閹芥粎绮旈鍕厽闁绘ê寮堕幖鎰版煟鎺抽崝灞藉祫闂佺鎻粻鎴g箽闂備浇娉曢崳锕傚箯閿燂拷
闂傚倷绀侀幖顐︽偋濠婂牆绀堟繛鎴欏灪閸嬬喐銇勯弽顐沪闁绘帡绠栭弻鏇熺箾閸喖濮庨梺璇叉唉椤曆嗗絹闂佹悶鍎荤徊鑺ユ櫠閹绘崡褰掓偂鎼淬垹娈楅悗娈垮枛閻栧吋淇婇悜鑺ユ櫆闁告挆鍐帗婵犵數鍋涢悺銊у垝瀹€鈧懞閬嶆嚃閳哄嫬小婵炲鍘ч悺銊╁吹閸岀偞鐓涢柛鎰╁妼閳ь剝宕电划鏃囥亹閹烘挾鍙嗗┑鐐村灱濞呮洜鈧熬鎷�闂備浇顕уù鐑藉极閹间降鈧焦绻濋崑顖氱秺瀹曞崬螣鐠囧樊娼梻浣风串缁蹭粙寮甸鍕仼闁告鍊戞惔銊ョ倞闁挎繂鎳庨埛澶嬬箾鐎电ǹ甯堕柟铏耿閻涱喚鈧綆鍠栫粻锝嗙節婵犲倸顏柟鏋姂濮婃椽宕ㄦ繝鍐f嫻缂備礁顑嗙敮锟犲箚閸ャ劌顕遍柡澶嬪灥閸炪劑姊洪幖鐐插姌闁告柨绉归敐鐐哄冀椤儱閰e畷鍫曟晲閸涱厸鎷ゅ┑鐐差嚟閸樠囧箠濮椻偓楠炲棝宕橀鑲╊槹濡炪倖鍔戦崹娲儊閺冣偓缁绘繈濮€閿濆棛銆愰柣搴㈣壘閹芥粌危閹扮増鏅搁柨鐕傛嫹闂傚倷鑳堕幊鎾绘偤閵娾晛鍨傞柛鎰ゴ閸亪鏌熺€电ǹ小闁绘帒锕ら埞鎴︽偐閸欏鎮欏┑鐐叉噷閸ㄥ綊婀侀梺鎸庣箓濡盯鎯屾惔銊︾厓鐟滄粓宕滃▎鎾崇疇闁归偊鍏橀弸鏃堟煙鏉堥箖妾柛瀣儔閺屾盯顢曢妶鍛€剧紓鍌氱М閸嬫捇姊绘担鐟扮亰闁绘帪绠撴俊鐢告倷閻㈢數顦梺鍝勫暙閻楀棛鐥閺屾盯骞囬娑氥€婄紓浣插亾闁跨噦鎷�闂備浇顕х花鑲╁緤婵犳熬缍栧鑸靛姇閸ㄥ倹绻濇繝鍌氼伀妞も晠鏀遍妵鍕箳閹存繃娈茬紓浣风贰閸o絽顕i崼鏇熷€烽柛顭戝亝閻濐亜鈹戦悙鑼闁搞劌澧庣划姘舵焼瀹ュ懐鍔撮梺鍛婂壃閸涱垼妲繝鐢靛Х椤d粙鍩€椤掆偓閸熷潡鍩€椤掑倹鍤€闁挎洏鍨洪幏鍛村礈閹绘帗顓块梻浣呵归張顒傛崲瀹ュ鑸归柟缁㈠枟閻撴瑩鎮楀☉娆嬬細濠⒀屽墯缁绘繈鍩€椤掍焦濯撮柛锔诲幘閹虫繈姊洪崜鑼帥闁稿鎳愮槐鐐哄焵椤掑嫭鈷戦柣鐔稿閹界娀鏌eΔ鍐ㄤ户闁瑰箍鍨归~婵嬵敄閼恒儳浜欓梻浣告惈濞诧箓鎯岄鐐床闁糕剝绋掗悡娆愩亜閹炬鍟版禒鏉戭渻閵堝棙澶勯柛鎾跺枎閻g兘鏁愰崱娆戠槇闂佸憡鍔忛弲鈺佄i鐐粹拺闁奸€涘嵆閸濈儤鎱ㄦ繝鍌ょ吋闁哄苯鐗撻獮姗€顢欓懖鈺婂悈闂備胶鎳撻悺銊у垝瀹ュ洤鍨濋柨鏇炲€归悡銉︾箾閹寸倖鎴濓耿閻楀牏绡€闁逞屽墴楠炲秹顢欓幆褍瑙︽繝鐢靛仜濡霉妞嬪海鐜绘俊銈呭暟绾惧ジ鏌¢崒娑卞劌闁稿骸绻掗埀顒冾潐閹哥ǹ螞濠靛棛鏆︽慨妯垮煐閸嬫劗绱撴担璐細鐟滅増鍨垮娲箰鎼粹€虫灆闂佺懓鍤栭幏锟�闂備浇顕уù鐑藉极閹间礁绠犻柟鎹愬煐閺嗘粍銇勯幇鍓佺暠缂佲偓閸℃ḿ绠鹃柟瀵镐紳椤忓牆鏋侀柛顐f礃閸婄數鐥鐐村婵炲吋鍔欓弻娑㈠Ω閿斿墽鐓佺紓浣稿€圭敮锟犮€佸Δ浣瑰缂佸鏅濋锔解拺閻熸瑥瀚欢鑼磼缂佹ê鐏寸€殿噮鍋婇、娆撴偩瀹€濠冪カ婵犳鍠楅妵娑㈠磻閹剧粯鐓冪憸婊堝礈濞嗘挸纾归柛婵勫劤缁€濠囨倵閿濆骸鏋熼柛搴$Ч閺屾盯寮撮妸銉ョ瑢閻熸粎澧楃敮妤呮偂閳ь剙顪冮妶鍡楃瑨闁挎洩濡囩划鍫ユ晸閿燂拷闂傚倷娴囨竟鍫熴仈缁嬫娼栧┑鐘崇閻掗箖鏌熺紒銏犳灈婵☆偅锕㈤弻锝夋偄缁嬫妫嗙紒缁㈠幐閸嬫捇姊绘担鐟邦嚋缂佸甯掗悾婵嬪箹娴e摜锛涢梺鍝勭Р閸斿酣銆呴悜鑺ョ叆闁绘洖鍊圭€氾拷:webmaster@jscj.com闂傚倷绶氬ḿ褍螞瀹€鍕;闁瑰墽绮悡鐔搞亜椤愵偄骞樼紒浣哄厴閺岋綁鏁傜捄銊х厯闂佽桨绀佺粔褰掑极閹剧粯鏅搁柨鐕傛嫹4008816886

相关文章

无相关信息
更新时间2022-09-16 10:00:13【至顶部↑】
联系我们 | 邮件: webmaster@jscj.com | 客服热线电话:4008816886(QQ同号) |  濠电姷鏁搁崕鎴犵礊閳ь剚銇勯弴鍡楀閸欏繘鏌i幇顕呮毌闁稿鎹囬悰顕€宕归鍙ョ棯婵犵數濮崑鎾绘煕閵夋垵鑻▓顐㈩渻閵堝棙顥嗘い鏂匡功閹广垽鏁撻敓锟�

付款方式留言簿投诉中心网站纠错二维码手机版

电话:
付款方式   |   给我留言   |   我要纠错   |   联系我们