一､DeadLock 成立條件
DeadLock 成立有4個必要條件(4個條件要都成立才會有Deadlock)1.Mutual exclusion
資源在同一時間只能有一個process使用
2.Hold & wait
process佔用資源同時又取等待其它process的資源
3.No preemption
process不能為了得到它想要的資源而把原來持有該資源的主人趕走
4.Circular waiting
P1(R1) > P2(R2) > P3(R3) > P1(R1)
二､範例程式
1.範例程式解說以下是一個c#範例程式，當人要存取資源時，會先檢查是否發生Circular waiting，進而避免Deadlock的發生。
假設有三個人x y z 可存取三個資源a b c
指令:[person] [action] [resource]
[person] 人
[action] 動作，access=存取資源，release=釋放資源
[resource] 資源，有a b c 可選擇
2.情境
例: x access a 就是x存取a資源
情境1:
x access a
y access a
y access b
x access b <-deadlock
y access a
y access b
x access b <-deadlock
情境2:
x access a
y access b
z access c
x access b
y access c
z access a <-deadlock
3.範例程式碼 
x access a
y access b
z access c
x access b
y access c
z access a <-deadlock
using System;
using System.Collections.Generic;
namespace ConsoleApplication1
{
class Resource
{
//private string name;
//private Person owner;
//private List reqList;
public string Name{ get; set; }
public Person Owner { get; set; }
public List ReqList { get; set; }
public Resource(string name)
{
Name = name;
Owner = new Person("");
ReqList = new List();
}
public void print()
{
Console.WriteLine("--資源: "+Name+"--");
Console.WriteLine("主人: " +Owner.Name);
Console.Write("排隊: ");
foreach(Person p in ReqList)
{
Console.Write(p.Name+" ");
}
Console.WriteLine();
}
}
class Person
{
//private string name;
//private List reqList;
public string Name { get; set; }
public List ReqList { get; set; }
public Person(string name)
{
Name = name;
ReqList = new List();
}
public void print()
{
Console.WriteLine("--角色: "+Name+"--");
Console.Write("排隊: ");
foreach (Resource r in ReqList)
{
Console.Write(r.Name + " ");
}
Console.WriteLine();
}
}
class Program
{
static Dictionary resourceList;
static Dictionary personList;
static bool circle(Person person, Person original)
{
foreach (Resource r in person.ReqList)//r為此人要求存取的某個資源
{
Person p = r.Owner;//此資源的主人
//Console.WriteLine("person="+person.Name+" original="+original.Name+" p="+p.Name);
if (p.Name == original.Name)//物件雖被存取，且主人為原來提出請求的人，迴圈成立
{
Console.WriteLine(p.Name == original.Name);
return false;
}
else if (p.Name == "")//物件沒被存取，不構成迴圈
{
return true;
}else if (p.ReqList.Count == 0)///物件雖被存取，但主人無要求其它資源，仍不構成迴圈
{
return true;
}
else//物件被存取，且主人有要求其它資源，但主人也不是原先提出的人，circle遞迴
{
return circle(p,original);
}
}
return true;//requestList沒有項目可排入等待列
}
static void doAction(Person person, string action, Resource resource)
{
if (action == "access")//------存取------
{
if (resource.Owner.Name == "")//成功存取
{
resource.Owner = person;
Console.WriteLine(person.Name + "成功存取" + resource.Name + "資源");
}
else if (resource.Owner.Name == person.Name)
{
Console.WriteLine(person.Name + "已存取過" + resource.Name + "資源了!");
}
else if (circle(resource.Owner, person))//等候存取
{
person.ReqList.Add(resource);
resource.ReqList.Add(person);
Console.WriteLine(person.Name + "等候存取" + resource.Name + "資源");
}
else//無法存取
{
Console.WriteLine("未防止dead lock，"+person.Name + "無法存取" + resource.Name + "資源!");
}
}
else if (action == "release")//-----釋放-----
{
Console.WriteLine(person.Name + "成功釋放" + resource.Name + "資源");
if (resource.Owner.Name == person.Name)//是資源主人才可釋放該資源
{
if (resource.ReqList.Count > 0)//在排隊的可以進場
{
resource.Owner = resource.ReqList[0];
resource.ReqList.RemoveAt(0);
personList[resource.Owner.Name].ReqList.Remove(resource);
Console.WriteLine(resource.Owner.Name + "成功存取" + resource.Name + "資源");
} else//沒人排隊
{
resource.Owner = new Person("");
}
}
else//不是資源主人
{
Console.WriteLine(person.Name + "不是" + resource.Name + "資源的主人");
}
}
else//-----兩者皆非-----
{
Console.WriteLine("action請填寫access或release");
}
}
static void inf()
{
Console.WriteLine("輸入方式:");
Console.WriteLine("[person] [action] [resource]");
Console.WriteLine("[person] 代表人");
Console.WriteLine("[action] 代表動作，access=存取資源，release=釋放資源");
Console.WriteLine("[resource] 代表資源，有a b c 可選擇");
Console.WriteLine("例: x access a 就是x存取a資源");
}
static void list()
{
Console.WriteLine("---------------");
foreach (KeyValuePair r in resourceList)
r.Value.print();
foreach (KeyValuePair p in personList)
p.Value.print();
Console.WriteLine("---------------");
}
static void Main()
{
resourceList = new Dictionary() { {"a", new Resource("a") }, { "b", new Resource("b") }, {"c", new Resource("c") } };
personList = new Dictionary() { { "x", new Person("x") }, { "y", new Person("y")}, { "z", new Person("z") } };
inf();
Console.WriteLine("請輸入指令\nhelp: 輸入格式問題\nlist: 列出清單\nexit: 離開");
string cmd;
while(true)
{
Console.Write(">");
if((cmd = Console.ReadLine()) == "exit"){
break;
}
if (cmd == "help"){
inf(); continue;
}
if (cmd == "list") {
list(); continue;
}
string[] strarr = cmd.Split(' ');
string p = strarr[0];
string action = strarr[1];
string r = strarr[2];
Person person = personList[p];
Resource resource = resourceList[r];
doAction(person, action, resource);
list();
}
}
}
}
沒有留言:
張貼留言