精华内容
下载资源
问答
  • 互斥算法
    2021-09-09 19:52:14

    Chap 1

    1.1互斥算法

    进程vs线程

    • 计算机需要能够同时执行多个任务
    • 可以并行执行,也可以在执行过程中反复切换任务,或者两者混合执行
    • 重量级进程有自己的代码、数据内存(全局变量和堆空间)和执行堆栈(局部变量和方法调用的激活记录)
      • 进程可以独立运行,提供对外部资源(如文件)的访问是协调的(如由操作系统)
    • 一个线程的执行(轻量级进程)共享代码和数据内存,但有自己的执行堆栈
      • 线程可以在同一代码的不同点运行
      • 需要仔细协调对全局变量/字段的访问(共享状态),以避免竞争条件
    • 不同的应用程序通常在不同的进程中执行,但在应用程序中,线程通常用于执行多个任务
      • 操作系统需要时间在进程之间上下文切换(必须保存/恢复进程状态每个开关)
      • 在线程之间切换比在进程之间切换快得多

    原子操作

    • 一个原子操作,保证一个线程在一瞬间完全执行

    • 没有其他线程可见的中间状态

    • 不是很明显什么操作是原子的,比如x++不是原子的,因为它可能变成多个机器指令

      LOAD R,x
      INC R
      STORE R,x
      
    • 每个线程都有自己的执行堆栈,所以使用相同寄存器变量R的两个线程没有问题(它们在交换线程时被保存/恢复)

    非原子操作期间的线程交换

    • 如果线程通过非原子操作进行交换,可能会发生“奇怪的事情”(竞态条件)

    • 如果一个线程试图读取一个全局变量/字段,而另一个线程正在更改它的值,读取的值取决于线程交换执行时的精确时间

      • 场景1:线程A开始执行x++,但线程B在线程A存储新值之前读取了x(线程B获得了原始值)

        LOAD R,x
        INC R
        							LOAD R,x
        STORE R,x
        
      • 场景2:线程A执行x++,然后线程B随后读取x(线程B获得增量值)

        LOAD R,x
        INC R
        STORE R,x
        							LOAD R,x
        

    更新丟失

    • 当两个线程修改相同的共享状态时,也会发生更糟糕的“奇怪的事情”

    • 示例:线程A执行x++,而线程B也执行x++

      • 场景1:线程A执行x++然后线程B执行x++ (x加2)

        LOAD R,x
        INC R
        STORE R,x
        							LOAD R,x
        							INC R
        							STORE R,x
        
      • 场景2:线程A开始执行x++,但是线程B在线程A存储新值之前读取了x (x只加1)

        LOAD R,x
        INC R
        							LOAD R,x
        							INC R
        							STORE R,x
        STORE R,x
        
    • 被称为“更新丟失问题”

      • 即使多个线程执行代码来更新共享状态,有时只出现一些更新

      • 调试可能非常具有挑战性

      • 示例代码LostUpdate

        /**
           A class that demonstrates the lost update problem in concurrency
           by creating two threads that concurrently try to increment x
           each a total of ITERATIONS times.
           Sometimes the final value of x is not 2*ITERATIONS
        */
        
        public class LostUpdate implements Runnable
        {
           private int x;
           private static final int ITERATIONS = 20000000; // multiple of 10
           
           public LostUpdate()
           {  x = 0;
           }
           
           // repeatedly increment the value of x 
           public void run()
           {  System.out.println("Thread " + Thread.currentThread()
                 + " started with x = " + x);
              int loopIterations = ITERATIONS/10;
              for (int i=0; i<loopIterations; i++)
              {  x++; x++; x++; x++; x++; x++; x++; x++; x++; x++;
              }
              System.out.println("Thread " + Thread.currentThread()
                 + " finishing with x = " + x); 
           }
           
           public static void main(String[] args)
           {  // create two concurrent threads
              LostUpdate lostUpdate = new LostUpdate();
              Thread threadA = new Thread(lostUpdate);
              Thread threadB = new Thread(lostUpdate);
              threadA.start();
              threadB.start();
              try
              {  // wait for both threads to finish
                 threadA.join();
                 threadB.join();
              }
              catch (InterruptedException e)
              {  System.out.println("Interrupted " + e);
              }
              System.out.println("The final value of x is " + lostUpdate.x);
           }
        }
        
        

    临界区代码 Critical Sections of Code

    • 临界区是一个代码块,一次只能由一个线程执行
    • 临界区有访问或更新共享状态的代码
    • 互斥是指线程想要访问一个或多个使用相同共享状态的临界区
    • 强制线程在临界区段内执行代码之前获取锁
    • 在任何时刻,只有一个线程可以持有
    • 当线程不再需要在临界区段内执行代码时,线程必须释放锁
    • 互斥锁与共享状态相关
    • 每个共享状态可能有自己的锁,控制访问或更新共享状态的任何临界区

    互斥算法的软件方法

    互斥算法

    • ***互斥算法***是一种实现互斥的算法

      • 大大多数互斥锁算法会延迟“Acquire-Lock”中的线程,直到它被允许访问
      • 互斥锁算法在如何正确工作方面非常微妙
    • 如何不写互斥算法(因为它并不总是保证互斥对于线程t,使用一个名为***exclude***的布尔标志

      **Incorrect-Acquire-Lock(t)**
      1 while exclude do
      2 delay
      3 exclude <- true
      
      **Incorrect-Release-Lock(t)**
      1 exclude <- false
      
    • 简单地使用布尔标志可能无法进行测试,并且设置标志可能不是原子的

      • 一个线程可能完成while循环,然后在它设置exclude之前切换到另一个线程

    Dekker的算法:单标志法

    Dekker 's Algorithm是第一个正确处理(仅)两个线程的互斥的算法:

    • 为每个线程维护一个请求标志,当线程请求锁时设置该标志

    • 维护一个优先级变量,以指示在平局情况下,两个线程中接下来应该访问哪个线程

      **Dekker-Acquire-Lock(t)**
      1 s <- the other thread than t
      2 requested[t] <- true
      3 while requested[s] do
      4 if priority = s then
      5 requested[t] <- false
      6 while priority = s do
      7 delay
      8 requested[t] <- true
      
      **Dekker-Release-Lock(t)**
      1 s <- the other thread than t
      2 priority <- s 3 requested[t] <- false
      
      • 两个线程都可以并发调用Dekker-Acquire-Lock,但只有一个线程会返回
      • 另一个线程将延迟while循环,直到第一个线程调用Dekker-Release-Lock

    皮特森算法/Peterson Algorithm

    • Peterson算法简化了Dekker算法

      • 为每个线程维护一个请求的标志字段,该字段在线程请求锁时设置
      • 维护一个回合变量来控制在平局情况下下一个线程必须等待
    • 在变量回合中利用竞争条件

      **Peterson-Acquire-Lock(t)**
      1 s <- the other thread than 
      2 requested[t] <- true
      3 turn <- t 4 while turn = t and requested[s] do
      5 delay
      
      **Peterson-Release-Lock(t)**
      1 requested[t] <- false
      
    • 可以修改为也工作在两个以上的线程(过滤算法)

      • 每个线程都将进入更高的级别,以便最终获得锁

    兰波特面包店算法/ Lamport’s Bakery Algorithm

    • Lamport的bakery算法可以处理任意数量的线程

      • 每个想要访问的线程被分配一个数字
      • 数量增加,因为请求(但可能不是唯一的,如果竞争条件)
      • 线程的最低数字是下一个给定的访问权限
      • 每个线程有一个唯一的Id,以防领带
      • 为每个线程维护选择标志,以确保当前线程选择数字时不会提供锁
      Lamport-Acquire-Lock(t)
      1 choosing[t] <- true
      2 assign a number to thread t one larger than currently assigned maximum
      3 choosing[t] <- false
      4 for each thread s do
      5 while choosing[s] do
      6 delay
      7 while (num[s]≠0 and num[s]<num[t]) or
      (num[s]=num[t] and Id[s]<Id[t]) do
      8 delay
      Lamport-Release-Lock(t)
      1 num[t] <- 0
      

    互斥锁算法的硬件辅助

    • 许多进程支持测试和设置指令

      • 硬件保证是原子的
      • 将内存位置设置为新值,返回原来的值
    • 原子测试和设置操作有助于创建简单的互斥锁算法

      • 维护排除标志
      TestAndSet-Acquire-Lock(t)
      1 while TestAndSet(exclude, true) do
      2 delay
      TestAndSet-Release-Lock(t)
      1 TestAndSet(exclude, false)
      

    线程旋转、阻塞和等待

    • 最简单的延迟线程的方法是让它旋转(忙等待)时间
      • 线程在有处理器时间的时候反复检查条件,看看是否可以继续
        一旦线程有条件,它就会进行
      • 但是如果条件持续失败很长时间,线程会浪费处理器时间
    • 最好让线程块阻塞(睡眠)
      • 线程检查条件,如果不能进行,就放弃当前的时间片,这样其他线程就可以使用处理器时间
      • 将再次检查条件时,下一次分配的时间片
    • 最好但更复杂的解决方案可能是让线程等待
      • 线程检查条件,如果不能进行,它放弃当前的时间片,并被放入一个等待集
      • 线程不能做任何事情,没有得到处理器时间,直到它被从等待集删除
      • 需要与另一个线程协调,该线程可以通知自己何时从等待集中删除

    更多reference

    互斥:https://en.wikipedia.org/wiki/Mutual_exclusion

    Leslie Lamport的面包店算法论文:http://lamport.azurewebsites.net/pubs/bakery.pdf

    更多相关内容
  • 传统的验证方法难以保证分布式K互斥算法的有效性和安全性,为解决这一问题,并且给出了进一步的研究,文中提出一种基于概率模型检测器PRISM的方法,对Kerry Raymond的分布式K互斥算法进行形式化建模与分析验证。...
  • 操作系统的实验课设,实现Dekker,Lamport,Peterson,Eisenberg进程互斥访问临界区算法,使用java语言完成,可以动态显示进程访问临界区时各个进程的状态
  • #资源达人分享计划#
  • 2.13 互斥 要求 空闲让进:若空闲,申请即进 忙则等待:只允许临界区存在一个进程,若忙碌,区外等待 有限等待:进程等待的时间是有限的,不会造成死锁、饥饿 让权等待:进程不能在临界区长时间阻塞等待某事件 以上...

    2.13 互斥

    要求
    • 空闲让进:若空闲,申请即进
    • 忙则等待:只允许临界区存在一个进程,若忙碌,区外等待
    • 有限等待:进程等待的时间是有限的,不会造成死锁、饥饿
    • 让权等待:进程不能在临界区长时间阻塞等待某事件
    • 以上类比生活中任何公共资源都可,如公用电话

    2.13.1 互斥:软件方法

    思路
    1. 在进入区设置标志来判断是否有进程在临界区
    2. 若临界区已有进程,则循环等待
    3. 进程离开临界区后在退出区修改标志
    第一代:轮换使用临界区

    每个进入临界区的进程的权限只能被另一个进程赋予

    int turn=0;
    
    //进程P0
    do{
    	while(turn!=0);//进入区
    	P0代码;//退出区
    	turn=1//退出区
    }while(true)
    
    //进程P1
    do{
    	while(turn!=1)//进入区
    	P1代码;//临界区
    	turn=0;//退出区
    }while(true)
    

    严格轮换,实现了互斥访问
    违反了空闲让进的原则:比如turn=1时,临界区空,但P1无法进入

    第二代:设置临界区状态标志

    进入之前看有没有其他进程要进入,没有则将自己的状态置为true

    boolean flag[2]={false,false}//该全局变量标志临界区空闲与否
    
    //进程P0
    do{
    	while(flag[1]);//进入区
    	flag[0]=true;//进入区
    	P0代码;//临界区
    	flag[0]=false;//退出区
    }while(true)
    
    //进程P1
    do{
    	while(flag[0]);//进入区
    	flag[1]=true;//进入区
    	P1代码;//临界区
    	flag[1]=false;//退出区
    }while(true)
    	
    

    违反了忙则等待原则:假设CPU先将时间片分给P0,然后P0判断flag[1]=false跳出循环向下执行,这时CPU又将时间片分给 P1,P0尚未执行到置flag[0]=true;P1判断flag[0]=false跳出循环向下执行,两者都将进入临界区
    注意:while(flag[1]);这一句表明:当flag[1]=true时停在这一句,flag[1]=false时跳出循环执行下一句,P0即进入临界区

    第三代:表明使用临界区的状态

    先亮明状态,再循环等待

    boolean flag[2] = {false, false};//共享的全局变量
    
    //进程P0
    do {
        flag[0] = true;    //进入区
        while (flag[1]) ;//进入区
        进程P0的临界区代码; //临界区
        flag[0] = false;   //退出区
        进程P0的其它代码     //剩余区
    } while (true)
    
    //进程P1
    do {
        flag[1] = true;    //进入区
        while (flag[0]) ;//进入区
        进程P1的临界区代码; //临界区
        flag[1] = false;   //退出区
        进程P1的其它代码     //剩余区
    } while (true)
    

    违反了空闲让进原则:CPU先将时间片分给P0,然后P0置flag[0]=true,这时CPU又将时间片分给 P1,P1置flag[1]=true;那么接下来两者都在while循环处等待对方清零,都无法进入临界区,形成死锁

    第四代:表明使用临界区的态度+谦让

    预先表明想进入临界区,但为了防止死锁,在进入临界区前会延迟一段时间

    boolean flag[2] = {false, false};//共享的全局变量
    
    //进程P0
    do {
        flag[0] = true;                 
        while (flag[1])  {              
            flag[0] = false;
             <随机延迟一小段时间>//谦让
            flag[0] = true;
        }
        进程P0的临界区代码; //临界区
        flag[0] = false;   //退出区
        进程P0的其它代码     //剩余区
    } while (true)
    
    //进程P1
    do {
        flag[1] = true;                  
        while (flag[0]) {                
            flag[1] = false; 
            <随机延迟一小段时间>//谦让
          flag[1] = true;
        }
        进程P1的临界区代码; //临界区
        flag[1] = false;   //退出区
        进程P1的其它代码     //剩余区
    } while (true)
    

    可能会活锁,过分谦让,长时间僵持:CPU先将时间片分给P0,然后P0置flag[0]=true,这时CPU又将时间片分给 P1,P1置flag[1]=true;接下来CPU先将时间片分给P0,P0发现flag[1]=true;进入while循环,先将flag[0]清零,再挂起一段时间,重新置位flag[0],查看flag[1]是否仍为1,若是则继续清零等待,重复这个过程,监听flag[1]的变化;同理,P1可能会与P0默契地进行同样的活动,两者同时监听,同时挂起,形成活锁,可能随时间自动解除

    Dekker互斥算法

    由于前一种算法活锁的原因是只监听了对方的flag,这时添加一个只能由对方改变的信息turn即可
    在这里插入图片描述

    boolean flag[2] = {false, false};      //共享的全局变量
    int turn = 1;                          //共享的全局变量
    
    //进程P0
    do {
        flag[0] = true;              //进入区
        while (flag[1]) {
           if (turn == 1)  {
               flag[0] = false;
               while  (turn == 1) ;  //等待
               flag[0] = true;
            }
         }                           //进入区
        进程P0的临界区代码;           //临界区
        turn = 1;
        flag[0] = false;             //退出区
        进程P0的其它代码               //剩余区
    } while (true)
    
    //进程P1
    do {
        flag[1] = true;              //进入区
        while (flag[0]) {
           if (turn == 0)  {
               flag[1] = false;
               while  (turn == 0) ;  //等待
               flag[1] = true;
            }
         }                           //进入区
        进程P1的临界区代码;           //临界区
        turn = 0;
        flag[1] = false;             //退出区
        进程P1的其它代码               //剩余区
    } while (true)
    
    

    在预先表明态度+谦让的基础上改进了谦让机制:
    P1在退出临界区时会置turn=0;P0退出临界区会将turn置为1
    这样一来,可以在监听对方flag时知道对方是否已经退出临界区,而不是等待一段随机时间,我认为这时重新尝试将自己的flag置为true是更好的做法,不会产生活锁

    Peterson互斥算法

    与dekker算法的区别:不是在退出时而是在进入前将turn改变

    boolean flag[2] = {false, false};    //共享的全局变量
    int turn;                            //共享的全局变量
    
    //进程P0
    do {
        flag[0] = true;                //进入区
        turn = 1;                      //进入区
        while (flag[1] && turn == 1) ; //进入区
        进程P0的临界区代码;             //临界区
        flag[0] = false;               //退出区
        进程P0的其它代码          	   //剩余区
    } while (true)
    
    进程P1
    do {
        flag[1] = true;                       //进入区
        turn = 0;                             //进入区
        while (flag[0] && turn == 0) ; 	      //进入区
        进程P1的临界区代码;           		  //临界区
        flag[1] = false;                      //退出区
        进程P1的其它代码                   	  //剩余区
    } while (true)
    
    

    假设P0进程先置自己的flag为true,改变turn=1,此时有一个while循环,当P1的flag=false时,说明P1还没有运行到置flag=true的行,可以继续进入临界区,或当turn=0时,这时说明P1执行后转而执行P0,P0此时在turn行,但P0无法进入临界区,因为此时flag[0]=true,而此时P0可以无视flag[1]=true的条件而继续进入临界区

    评价软件互斥方法
    1. 不能解决忙等问题(使用while监听方法),效率低
    2. 进程互斥使用临界资源困难,难以控制两个以上进程的互斥
    3. 算法设计时容易死锁或互斥失败
    展开全文
  • 1. 分布式互斥算法的概念 分布式互斥算法,就是在分布式系统中,通过某种消息传递算法来决定,控制哪个进程可以访问临界区资源。 如何去评价分布式互斥算法是否达到了这个目的呢?于是就定义出了三个算法指标: ME1...

    1. 分布式互斥算法的概念

    分布式互斥算法,就是在分布式系统中,通过某种消息传递算法来决定哪个进程可以访问临界区资源(如CPU等)。

    如何去评价分布式互斥算法是否达到了这个目的呢?于是就定义出了三个算法指标:

    • ME1 安全性
      至多一个进程在使用临界区,不会有多个进程同时在临界区执行;
    • ME2 活性
      不会发生死锁、饿死现象;
    • ME3 公平性
      进程顺序执行(FIFO),先到先进。

    能满足这三个条件的算法,就是一个良好的分布式互斥算法。

    2. Lamport 算法

    某个进程 p i p_i pi 请求临界区时,会先向所有其他进程发送请求 R e q u e s t ( t i , p i ) Request(t_i,p_i) Request(ti,pi),其他进程将这个请求保存到本地请求队列里。

    其他进程(接收到请求的进程)如果收到了一个请求,那么会按请求中打上的时间戳 t i t_i ti将请求加入到本地请求队列里,然后返回一个 R e p l y ( t j ) Reply(t_j) Reply(tj) t j t_j tj是指进程 p j p_j pj 收到进程 p i p_i pi 请求时的时间戳。

    p i p_i pi 发送了请求以后进程就等啊等啊,直到:

    1. 进程 p i p_i pi 收到了所有其他进程返回的 R e p l y ( t ∗ ) Reply(t_*) Reply(t),显然 t ∗ > t i t_*>t_i t>ti,因为其他进程一定是在接收到 p i p_i pi 请求后才打的时间戳(我发了消息后,对方才会回复的消息);
    2. 此时本地请求队列里 t i t_i ti在队头,其他 t ∗ t_* t t i t_i ti后面。

    那么此时进程 p i p_i pi 就可以进入临界区执行了。在进程 p i p_i pi 退出临界区时从本地队列里删掉自己的请求 R e q u e s t ( t i , i ) Request (t_i,i) Request(ti,i),再带着时间戳发一个 R e l e a s e Release Release广播,通知所有队列都可以删掉请求了。

    Lamport算法起作用的基础很明显是要满足M3的,也即请求的存储要求FIFO,如果非FIFO的话,连续发两个请求返回值的顺序可能就会乱了。

    如下图:
    下面的进程在时刻 2 2 2给请求A打了一个时间戳,在时刻 4 4 4给请求B打了一个时间戳,但回复B却优先与回复A返回,进程不满足进入临界区的条件,算法就卡死在这里了。
    在这里插入图片描述

    3. Ricart-Agrawala 算法

    Lamport 算法的不足之处在于:

    • 没有申请临界区资源的其他进程是没必要知道申请了临界区资源的进程是否释放( R e l e a s e Release Release操作)了临界区资源的。

    所以 R e p l y Reply Reply操作没必要进行的太早,早回复了也进不去临界区,因此不如等到 R e l e a s e Release Release 后在 R e p l y Reply Reply

    针对上述问题,提出了Ricart-Agrawala 算法进行了改进。

    首先,某个进程 p i p_i pi 请求临界区时,还是会先向所有其他进程广播请求 R e q u e s t ( t i , p i ) Request(t_i,p_i) Request(ti,pi),其他进程将这个请求保存到本地请求队列里。

    其他进程(接收方)收到请求时:

    • 如果自己没有请求临界区,也没有在临界区执行,那就直接 R e p l y Reply Reply
    • 如果自己正在请求临界区,但是接收方发出的请求的时间戳大于请求消息的时间戳时,也直接 R e p l y Reply Reply
    • 如果不是上述两种情况,也就是说,接收方收到这个请求消息之后,发现自己需要比这个请求更早的进入临界区,那就先不对它 R e p l y Reply Reply,而是记录本地的一个数组 R D [ p i ] = 1 RD[p_i]=1 RD[pi]=1,表示延迟回复进程 p i p_i pi 一个请求。

    同样的,一个进程只有在收到其他所有进程的 R e p l y Reply Reply后,才能进入临界区执行。退出临界区时要按照 R D RD RD数组中的记录,将延迟的 R e p l y Reply Reply发送出去。

    可以看出来,Ricart-Agrawala 算法去掉了 R e l e a s e Release Release 消息,也就是说,当一个进程退出临界区之后,通知其他进程可以进入临界区的信号不再特意通过一个 R e l e a s e Release Release信号去通知了,而是通过补全延迟的 R e p l y Reply Reply信号使其他进程满足进入临界区的条件(此时上一个进程已经释放了临界区资源),然后直接进入临界区就可以了。

    4. 算法分析

    对于Lamport 算法和Ricart-Agrawala 算法来说,最重要的区别就是Ricart-Agrawala 算法在退出临界区时不再发出 R e l e a s e Release Release消息。下面我们分别来证明一下这两个算法满足了ME1、ME2、ME3。

    1. ME1
      Lamport:如果两个进程 p i p_i pi p j , ( i ≠ j ) p_j,(i\neq j) pj,(i=j)能同时进入临界区,那么这两个进程必须已经互相向对方发送了 R e p l y Reply Reply消息。但是,因为 < t i , p i > <t_i, p_i> <ti,pi>对是在队列中排序的,所以 R e p l y Reply Reply一定是有先后顺序的,只有当某个进程从临界区退出时广播了 R e l e a s e Release Release信号后,另一个进程才能进入临界区。
      Ricart-Agrawala:如果两个进程 p i p_i pi p j , ( i ≠ j ) p_j,(i\neq j) pj,(i=j)能同时进入临界区,那么这两个进程必须已经互相向对方发送了 R e p l y Reply Reply消息。但是,因为 < t i , p i > <t_i, p_i> <ti,pi>对是在队列中排序的,所以 R e p l y Reply Reply一定是有先后顺序的,只有当某个进程从临界区退出后才会发送之前延迟的 R e p l y Reply Reply信号,另一个进程才能获得 R e p l y Reply Reply进入临界区。
    2. ME2
      Lamport:假设进程 p i p_i pi 在临界区中执行完毕,那么在它离开临界区时,会广播 R e l e a s e Release Release信号,该信号相当于通知其他进程临界区已被释放,此时新的进程就可以进入临界区,无死锁。
      Ricart-Agrawala:假设进程 p i p_i pi 在临界区中执行完毕,那么在它离开临界区时,会发送被延迟的 R e p l y Reply Reply信号,其他进程得到 R e p l y Reply Reply信号后就满足了进入临界区的条件,便可以进入临界区执行,无死锁。
    3. ME3
      Lamport:进程 p i p_i pi 先广播了进入临界区的请求 r i r_i ri,然后进程 p j p_j pj 又广播了进入临界区的请求 r j r_j rj。在理想条件下,会先处理 p i p_i pi 的请求,再处理 p j p_j pj 的请求。但由于消息传递有延迟, p j p_j pj 的请求可能会先于 p i p_i pi 的请求到达服务器,所以服务器会先处理 p j p_j pj 的请求。
      Ricart-Agrawala:进程 p i p_i pi 先广播了进入临界区的请求 r i r_i ri,然后进程 p j p_j pj 又广播了进入临界区的请求 r j r_j rj。假如 p j p_j pj先进入了临界区,则说明 r j r_j rj 的时间戳大于 r i r_i ri,这与事实相悖。因为Ricart-Agrawala算法会通过 r i r_i ri r j r_j rj 的时间戳来判断应该立即 R e p l y Reply Reply还是延迟 R e p l y Reply Reply,这样就可以确保先发送的请求 r i r_i ri 先得到 R e p l y Reply Reply进入临界区。
    展开全文
  • 经典互斥算法1

    2022-08-04 12:55:07
    摘要本文用较为轻松的方式介绍了几个经典的互斥算法:Dekker 算法、Dijkstra 提出的算法、Peterson 算法和面包店算法,并简单地给出了每一个算法
  • 进程互斥原则模板: (1)互斥性 枚举所有情况,一个进程进入临界区后,另一个进程不能进入临界区 ...Dekker互斥算法 int flag[2]; int turn; P0:do{ flag[0] = 1; while flag[1] do if(turn == 1){ flag[0] =.

    进程互斥原则模板:
    (1)互斥性
    枚举所有情况,一个进程进入临界区后,另一个进程不能进入临界区
    (2)进展性
    枚举一个进程要求进入临界区后,能够进入临界区和多个进程要求进入临界区后,能有一个进入临界区
    (3)有限等待性
    一个进程离开临界区后,不会让该进程再度进入临界区,而是让其他进程也能够进入临界区

    Dekker互斥算法

    int flag[2];
    int turn;
    
    P0:do{
    	flag[0] = 1;
    	while flag[1] do
    		if(turn == 1){
    			flag[0] = 0;
    			while turn == 1 do
    				skip;
    			flag[0] = 1;
    		}
    	临界区
    	turn = 1;
    	flag[0] = 0;
    	其余代码 
    }while(1);
    
    P1:do{
    	flag[1] = 1;
    	while flag[0] do{
    		if(turn == 0){
    			flag[1] = 0;
    			while turn == 0 do
    				skip;
    			flag[1] = 1;
    		}
    	}
    	临界区
    	turn = 0;
    	flag[1] = 0; 
    }while(1);
    

    (1)考虑互斥性:
    假设P0进入临界区,flag[0] = 1,P1欲进入临界区必定处于外层while循环忙式等待,满足互斥性
    (2)考虑进展性:
    若只有一个进程想进入临界区,假定为P0,则flag[1] = 0,P0结束外层while循环进入临界区。
    若两个进程都想进入临界区,那么turn必定满足其中一个if条件,假设满足turn == 0,那么将flag[1]置为0,P1进入内层while循环忙式等待,而P0获得处理器资源后,由于flag[1] = 0,故退出外层while循环,进入临界区,满足进展性。
    (3)考虑有限等待性:
    假设P0处于临界区中,P1执行entry section代码试图进入临界区,P0离开临界区时,turn = 1,flag[0] = 0。
    若在P1判断外层while循环之前,P0没有再次提出进入临界区,那么P1在外层while循环判断flag[0]条件不成立,进入临界区。
    若在P1判断外层while循环之前,P0再次提出进入临界区,但此时turn = 1,P0会将flag[0]置为0进入忙式等待,直至P1进入并离开临界区。因而在P0再度进入临界区之前,必能获得进入临界区的机会,满足有限等待性。

    Peterson互斥算法

    int flag[2];
    int turn;
    
    P0:do{
    	flag[0] = 1;
    	turn = 1;
    	while flag[1] && turn == 1 do
    		skip;
    	临界区
    	flag[0] = 0;
    	其余代码 
    }while(1);
    
    P1:do{
    	flag[1] = 1;
    	turn = 0;
    	while flag[0] && turn == 0 do
    		skip;
    	临界区
    	flag[1] = 0;
    	其余代码 
    }while(1);
    

    (1)考虑互斥性:
    假设P0进入临界区,此时分为三种情况
    (a)flag[1]不满足 (b)turn == 1不满足 (c)二者均不满足
    对于a,则说明此时P1还未请求进入临界区,若在之后P1请求进入临界区时,将turn赋值为0的操作后执行
    对于b,则说明将turn赋值为0操作后执行
    对于c,要求flag[1] = 0 且 turn = 0不可能实现,因为这要求P1未进入entry section而又将turn赋值为0。
    可能的ab两种情况时,P0处于临界区,故flag[0] = 1,又turn = 0,因此P1将在while循环处执行忙式等待,满足互斥性。
    (2)考虑进展性
    若只有一个进程想进入临界区,假定为P0,flag[1] = 0,跳出while循环进入临界区
    若两个进程都想进入临界区,只能满足turn = 0或turn =1两种情况,因此必定有一个结束while循环进入临界区,满足进展性。
    (3)考虑有限等待性
    若P0离开临界区,则flag[0] = 0
    若在P1判断外层while循环之前,P0没有再次提出进入临界区,那么P1在外层while循环判断flag[0]条件不成立,进入临界区。
    若在P1判断外层while循环之前,P0再次提出进入临界区,那么此时必定执行turn = 1, P0进入忙式等待,P1必定能进入临界区,满足有限等待性。

    Lamport面包店算法

    int choosing[n];	//choosing[i] = 1表示进程i正在抓号,否则为0
    int number[i];		//number[i]为0表示进程i没有抓号,否则为正整数,初始为0
    (1) (a,b) < (c,d) 如果 a < c or (a = c and b < d)成立
    (2) max{a0,a1,...an-1}的值为一个正整数k,对于所有i(0 <= i <= n-1), k >= ai 
    do{
    	choosing[i] = 1;
    	number[i] = max{number[0],number[1],...,number[n-1]} + 1;
    	choosing[i] = 0; 
    	for(j = 0; j < n; j++){
    		while(choosing[j])
    			skip;
    		while(number[j] != 0 && (number[j],j) < (number[i],i))
    			skip;
    	}
    	临界区
    	number[i] = 0;
    	其余代码 
    }while(1);
    

    (1)考虑互斥性:
    对于进程Pi,满足条件所抓号码为number[i],且对于其它想进入临界区的进程Pj有(number[i],i) < (number[j],j)。当Pi进入临界区后,其它进程将在第一个或第二个while处忙式等待,满足互斥性。
    (2)考虑进展性:
    当有多个进程竞争进入临界区时,有两种情况
    (a)一个进程抓到最小号码 (b)若干个进程抓到最小号码
    对于a,抓到最小号码的进程进入临界区
    对于b,抓到最小号码且编号最小的进程进入临界区 因此满足进展性
    (3)考虑有限等待性
    因为竞争进程按照先进先出的次序进入临界区,而且进程数量有限,因此进程不会无限期地等待进入临界区,满足有限等待性。

    展开全文
  • 2、分布式互斥算法 即如何让分布式系统里面的程序互斥的访问临界资源。 注:以下算法实现方式,暂不考虑超时等其他影响因素 【1】集中式算法 基本实现方式:引入一个协调者程序,每个程序在需要访问临界资源时,...
  • 使用 Roucairol 和 CarvalhoÕs 的分布式互斥算法实现互斥服务。 您的服务应该向应用程序提供两个函数调用:cs-enter 和 cs-leave。 第一个函数调用 cs-enter 允许应用程序请求开始执行其临界区的权限。 函数调用是...
  • 这种实现进程同步互斥具有很高的效率但是会造成系统负担过大。 ..... 关中断; 临界区; 开中断; ..... 二、单标志方法 该算法设置一个公用整型变量tum, 用于指示被允许进入临界区的进程编号,即若turn = 0, 则允许凡...
  • 为在全分布系统中实现对称的分布式互斥,需要设计出对称的分布式互斥算法。通过证明循环请求集与松弛循环差集的等价性,将求取包含任意数量节点的分布式系统对称请求集的问题转化为求取任意数量节点集合的松弛差集...
  • 我们一起看看有哪些类型的分布式互斥算法。 1、集中式算法 在集中式算法中,一般需要一个协调者。每个程序在访问临界资源的时候,需要先给协调者发送一个请求。如果当前临界资源没有使用者,则授权该程序使用该资源...
  • 操作系统之互斥算法

    2020-04-27 17:22:07
    Dekkel互斥算法 flag表示是否想进入临界区,turn表示轮到谁 int flag[2]; (init 0) int turn; (0 or 1) P0: do{ flag[0]=1; while(flag[1]) if(turn==1){ flag[0]=0; wh...
  • 关于分布式系统进程互斥算法的研究.doc
  • 一个理发店,由一间等候室W和一间工作室B组成,理发店环境和运作示意图如下图所示。顾客可以从外面大街上进入W,等候理发。两个房间的入口是并排的且共享一扇日本式可...2)请用P、V操作写出这些进程的同步控制算法
  • 经典互斥算法.pdf

    2021-11-25 06:58:13
    经典互斥算法.pdf
  • 分布式系统进程互斥算法的研究与改进.docx
  • 雷蒙兹树基于分布式互斥算法 使用基于Raymonds树的分布式互斥算法实现互斥服务。每个进程或节点都包含两个单独的模块-一个模块实现应用程序(请求并执行关键部分),一个模块实现互斥算法(坐标关键)所有进程的部分...
  • Maekawa 算法用于在分布式系统中实现互斥。 实现了原始算法的所有特征。 该算法是用Java实现的。 主要设计决策:分布式系统中的进程/节点被视为线程。 然后节点可以异步进入临界区。 但是进程进入 CS 的时间是按照...
  • Dekker互斥算法是由荷兰数学家Dekker提出的一种解决并发进程互斥与同步的软件实现方法。
  • 分布式系统进程互斥算法的分析与改进.pdf
  • 分布式系统中的互斥算法

    千次阅读 2016-11-02 15:34:04
    两层结构的分布式令牌环算法是适用于多个节点网络的互斥算法,它将分布式算法和令牌环算法的优点集于一身,大大提高了算法性能上的优势。本算法把整个广域网系统组织成的两层逻辑结构:局域网是第一个层次,每个局域网...
  • 分布式互斥算法解析

    千次阅读 2020-04-09 16:48:30
    文章目录引言集中式算法分布式算法基于请求的算法基于令牌的算法总结 ...保证任何给定时刻只允许一个进程或者给定的进程去执行临界区的算法称为互斥算法. 传统的单机达到互斥的方法有互斥锁,条件变...
  • aosProj2 使用Roucairol和Carvalho的分布式互斥算法实现互斥服务
  • 摘要 互斥能有效解决分布式系统中的资源申请的相互冲突并实现资源共享本文 首先简要介绍了分布式异步系统中互斥算法的一些基本要求及评价标准并介绍 单令牌环算法和双令牌环算法的算法思想及存在的不足分析了双令牌...
  • PETERSON互斥算法解析

    千次阅读 2019-09-19 10:06:55
    对于互斥算法,主要有两种,一种是DEKKER算法,另一种是PETERSON算法,这一篇主要来说PETERSON算法。 相比于DEKKER算法,PETERSON算法也解决了互斥访问问题,并且不需要像DEKKER算法一样强制轮流访问,可以正常的...
  • 分布式系统进程互斥算法的研究与改进

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 86,943
精华内容 34,777
关键字:

互斥算法