操作系统课程设计课件 题目2

基于软件互斥算法的临界区进程互斥的模拟实现

功能要求(1)互斥算法选择界面要求对Dekker、Peterson、Lamport、Eisenburg/Mcguire4个软件解决互斥的算法进行模拟实现。(2)运行结果（界面）根据选择的软件互斥算法，能动态显示2个或多个并发进程对临界区的互斥执行信息，包括处于临界区内的进程和要进入临界区的进程。

具体细节实现（1）根据界面选择相应的软件互斥算法，（2）能任意创建2个或多个并发进程实现对临界区的互斥执行；（3）对于每个进入临界区进程的执行，可以用显示信息进行模拟；（4）每个进入临界区的进程在临界区内要滞留一个随机产生的时间段

Dekker互斥算法是由荷兰数学家T.Dekker给出的第一个正确实现互斥的软件算法，算法针对两个进程P0和P1定义的两个数据结构：

intflag[2];//初值为0

intturn;//初值为0或1算法：Dekker互斥算法P0:do{flag[0]=1;whileflag[1]doif(turn=1){flag[0]=0;whileturn==1doskip;flag[0]=1;}Dekker互斥算法临界区

turn=1;flag[0]=0;

其余代码

}while(1)Dekker互斥算法P1:do{flag[1]=1;whileflag[0]doif(turn=0){flag[1]=0;whileturn==0doskip;flag[1]=1;}Dekker互斥算法临界区

turn=0;flag[1]=0;

其余代码

}while(1)Peterson算法思想：算法整队两个进程，应用与Dekke算法相似的两个数据结构

intflag[2];//初值为0

intturn;//初值为0或1Peterson算法P0:do{flag[0]=1;turn=1;whileflag[1]&&turn==1doskip;临界区flag[0]=0;}while(1);Peterson算法P1:do{flag[1]=1;turn=0;whileflag[0]&&turn==0doskip;临界区flag[1]=0;}while(1);Lamport面包店算法算法思想：算法的基本思想源于顾客在面包店中购买面包时的排队原理。设置一个发号者，按0,1,2,…,发号。想进入临界区（面包店）的进程先抓号，抓到号之后按由小到大的次序依次进入。Problem:两个进程可能抓到相同的号。Why?

为保证抓到不同的号，需要互斥机制。Resolution:

若抓到相同的号，按进程编号由小到大依次进入。Definition:(a,b)<(c,d)iff(a<c)or(a=candb<d)Lamport面包店算法算法需要以下两个数据结构

int

choosing[n];

int

number[n];

前者表示进程是否正在抓号choosing[i]=1表示进程正在抓号，否则为0，其初值为0.后者用来表示进程抓到号码，初值也为0.算法描述方便需要定义以下表示方法

(a,b)<(c,d),如果

a<cor(a=candb<d)成立。Lamport面包店算法do{Pi进入：1.choosing[i]=1;2.number[i]=max{number[0],…,number[n-1]}+1;3.choosing[i]=0;4.for(j=0;j<n;j++){5.Whilechoosing[j]{skip;}6.While(number[j]<>0)&&7.(number[j],j)<(number[i],i){skip}8.}

(1)P0抓到1未赋值(2)P1抓到1进入临界区(3)P2抓到2进入临界区Lamport面包店算法(Cont.)临界区；

number[i]=0；}while(1);变量choosing的作用：P0：抓到1;P1：抓到1;正确次序：P0，P1，P2P2：抓到2;

可能按P1,P2,P0次序进入！Eisenberg/Mcguire算法enum

flag[n](idle,want_in,in_cs);初值idle

int

turn;//intherangeof(0,n-1);

初始任意0

i

turnn-1先于i先于iflag[i]=idle:进程Pi不想进入临界区flag[i]=want_in:进程Pi想进入临界区flag[i]=in_cs:进程Pi想进入或已进入临界区Eisenberg/Mcguire算法Pi进入:do{do{

flag[i]=want_in;j=turn;While(j!=i)if(flag[j]!=idle){j=turn};else{j=(j+1)%n};

flag[i]=in_cs;j=0;While((j<n)&&(j==i∣∣flag[j]!=in_cs))