《操作系统课程设计课件题目.ppt》由会员分享，可在线阅读，更多相关《操作系统课程设计课件题目.ppt（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、基于软件互斥算法的临界区进基于软件互斥算法的临界区进程互斥的模拟实现程互斥的模拟实现 功能要求(1)互斥算法选择界面互斥算法选择界面要求对Dekker、Peterson、Lamport、Eisenburg/Mcguire4个软件解决互斥的算法进行模拟实现。(2)运行结果（界面）运行结果（界面）根据选择的软件互斥算法，能动态显示2个或多个并发进程对临界区的互斥执行信息，包括处于临界区内的进程和要进入临界区的进程。具体细节实现（1）根据界面选择相应的软件互斥算法，（2）能任意创建2个或多个并发进程实现对临界区的互斥执行；（3）对于每个进入临界区进程的执行，可以用显示信息进行模拟；（4）每个进入临界
2、区的进程在临界区内要滞留一个随机产生的时间段 Dekker互斥算法是由荷兰数学家T.Dekker给出的第一个正确实现互斥的软件算法，算法针对两个进程P0和P1定义的两个数据结构：int flag2;/初值为0 int turn;/初值为0或1算法：Dekker互斥算法P0:do flag0=1;while flag1 do if(turn=1)flag0=0;while turn=1 do skip;flag0=1;Dekker互斥算法 临界区 turn=1;flag0=0;其余代码 while(1)Dekker互斥算法P1:do flag1=1;while flag0 do if(turn=
3、0)flag1=0;while turn=0 do skip;flag1=1;Dekker互斥算法 临界区 turn=0;flag1=0;其余代码 while(1)Peterson算法思想：算法整队两个进程，应用与Dekke算法相似的两个数据结构 int flag2;/初值为0 int turn;/初值为0或1Peterson算法P0:do flag0=1;turn=1;while flag1&turn=1do skip;临界区 flag0=0;while(1);Peterson算法P1:do flag1=1;turn=0;while flag0&turn=0do skip;临界区 flag1
4、=0;while(1);Lamport面包店算法面包店算法算法思想算法思想：算法的基本思想源于顾客在面包店中购买面包：算法的基本思想源于顾客在面包店中购买面包时的排队原理。设置一个发号者，按时的排队原理。设置一个发号者，按0,1,2,发号。想进发号。想进入临界区（面包店）的进程先抓号，抓到号之后按由小到入临界区（面包店）的进程先抓号，抓到号之后按由小到大的次序依次进入大的次序依次进入。Problem:两个进程可能抓到相同的号。两个进程可能抓到相同的号。Why?为保证抓到不同的号，需要互斥机制。为保证抓到不同的号，需要互斥机制。Resolution:若抓到相同的号，按进程编号由小到大依次若抓到相
5、同的号，按进程编号由小到大依次进入。进入。Definition:(a,b)(c,d)iff(ac)or(a=c and bd)Lamport面包店算法面包店算法算法需要以下两个数据结构 int choosingn;int numbern;前者表示进程是否正在抓号choosingi=1表示进程正在抓号，否则为0，其初值为0.后者用来表示进程抓到号码，初值也为0.算法描述方便需要定义以下表示方法(a,b)(c,d),如果 ac or(a=c and bd)成立。Lamport面包店算法面包店算法doPi 进入进入：1.choosingi=1;2.numberi=maxnumber0,numbern
6、-1+1;3.choosingi=0;4.for(j=0;jn;j+)5.While choosingj skip;6.While(numberj0)&7.(numberj,j)(numberi,i)skip8.(1)P0抓到1未赋值(2)P1抓到1进入临界区(3)P2抓到2进入临界区 Lamport面包店算法面包店算法(Cont.)临界区；临界区；numberi=0；while(1);变量变量choosing的作用：的作用：P0：抓到：抓到1;P1：抓到：抓到1;正确次序：正确次序：P0，P1，P2P2：抓到：抓到2;可能按可能按P1,P2,P0次序进入次序进入！Eisenberg/Mcgu
7、ire算法算法enum flagn(idle,want_in,in_cs);初值初值idle int turn;/in the range of(0,n-1);初始任意初始任意0 i turnn-1先于先于i先于先于iflagi=idle:进程进程Pi不想进入临界区不想进入临界区flagi=want_in:进程进程Pi想进入临界区想进入临界区flagi=in_cs:进程进程Pi想进入或已进入临界想进入或已进入临界区区Eisenberg/Mcguire算法算法Pi进入进入:do do flagi=want_in;j=turn;While(j!=i)if(flagj!=idle)j=turn;else j=(j+1)%n;flagi=in_cs;j=0;While(jn)&(j=i flagj!=in_cs)j+;while(j!=n);turn=i;Eisenberg/Mcguire算法算法Pi离开：离开：j=(turn+1)%n;While(flagj=idle)j=(j+1)%n;turn=j;flagi=idle;while(1)CS