精华内容
下载资源
问答
  • 进程互斥指当一个进程访问某临界资源时,另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束,释放该资源之后,另一个进程才能去访问临界资源。 对逻辑资源的互斥访问,可以在逻辑上分为如下...

    一段时间内只允许一个进程使用的资源称为临界资源,许多物理设备(如摄像头、打印机等)都属于临界资源,此外还有很多许多变量、数据、内存缓冲区都属于临界资源。
    对临界资源必须互斥的进行。互斥,也称为间接制约关系。进程互斥指当一个进程访问某临界资源时,另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束,释放该资源之后,另一个进程才能去访问临界资源。
    对逻辑资源的互斥访问,可以在逻辑上分为如下的四个部分:
    进入区:负责检查是否可以进入临界区,若可进入,则应***设置正在访问临界资源的标志***;
    临界区访问临界资源的那段代码,也被称为“临界段”;
    退出区:负责解除正在访问临界资源的标志(可以理解为“解锁”);
    剩余区:做其他处理。
    进入区和退出区是负责实现互斥的代码段。
    为了实现对临界资源的互斥访问,同时保证系统的整体性能,需要遵循以下原则:

    1. 闲则让进:临界区空闲时,可以允许一个请求进入临界区的进程立即进入临界区;
    2. 忙则等待:当已有进程进入临界区时,其他试图进入临界区的进程必须等待;
    3. 有限等待:对请求访问的进程,应保证能在有限时间内进入临界区(保证不会饥饿);
    4. 让权等待:当进程不能进入临界区时,应立即释放处理机,防止进程忙等待

    进程互斥的软件实现:

    1.单标志法:

    两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就说每个进程进入临界区的权限只能被另一个进程赋予。

    int turn=0;
    P0 进程:
    while(turn!=0);    1 //进入区
    cirtical section;  2 //临界区
    turn=1;            3 //退出区
    remainder section; 4 //剩余区
    P1进程:
    while(turn!=1);    5 //进入区
    critical section;  6 //临界区
    turn=0;            7 //退出区
    remainder section; 8 //剩余区
    

    turn的初值为0,即刚开始只允许0号进程进入临界区。
    若P1先上处理机,则会一直卡在5。直到P1的时间片用完,发生调度,切换P0上处理机运行。代码1不会卡住P0,P0可以正常访问临界区,在P0访问临界区期间即使切换为P1,P1仍会卡在5,只有P0在退出区将turn改为1后,P1才能进入临界区。
    该算法可以实现:同一时刻最多只允许一个进程访问临界区
    turn表示当前允许进入临界区的进程号,而只有当前允许进入临界区的进程访问了临界区之后,才会修改turn的值。也就是说,对于临界区的访问,一定是按p0->p1->p0->p1这样轮流访问。
    但如果P0一直不访问临界区,则turn一直为0,那么虽然此时临界区空闲,但是并不允许P1访问,单标志法存在的主要问题是:违背“空闲让进”原则

    2.双标志先检查法:

    算法思想:设置一个布尔型数组flag[],数组中各个元素用来标记各进程想进入临界区的意愿,比如"flag[0]=true"意味着0号进程现在想进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区,如果没有,则把自身对应的标志flag[i]设为true,之后开始访问临界区。

    bool flag[2];//表示进入临界区意愿的数组
    flag[0]=false;
    flag[1]=false;//刚开始设置为两个进程都不想进入临界区
    P0进程:
    while(flag[1]);     1
    flag[0]=true;       2
    critical section;   3
    flag[0]=false;      4
    remainder section;
    P1进程:
    while(flag[0]);     5//如果此时P0想进入临界区,P1就一直循环等待
    flag[1]=true;       6//标记为P1进程想要进入临界区
    critical section;   7//访问临界区
    flag[1]=false;      8//访问完临界区,修改标记为P1不想使用临界区
    reminder section;
    

    但如果1和2之间有别的代码,5和6之间有别的代码,导致访问的时候1和2不连续,5和6不连续,而是按照1 5 2 6 3 7…的顺序执行,P0和P1将同时访问临界区,因此双标记先检查的主要问题是:违反“忙则等待”原则。
    进入区的“检查”和“上锁”两个处理不是一气呵成的。

    3.双标志后检查法:

    算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”,但是这两个操作又无法一气呵成,因此导致了两个进程同时进入临界区的问题。因此,人们又想到先“上锁”后“检查”的方法来避免上述的问题。

    bool flag[2];//表示进入临界区意愿的数组
    flag[0]=false;
    flag[1]=false;//刚开始设置为两个进程都不想进入临界区
    P0进程:
    flag[0]=true;       1
    while(flag[1]);     2
    critical section;   3
    flag[0]=false;      4
    remainder section;
    P1进程:
    flag[1]=true;       5//标记为P1进程想要进入临界区
    while(flag[0]);     6//如果此时P0想进入临界区,P1就一直循环等待
    critical section;   7//访问临界区
    flag[1]=false;      8//访问完临界区,修改标记为P1不想使用临界区
    reminder section;
    

    若按照1 5 2 6的顺序执行,P0和P1均无法进入临界区,因此,双标志后检查法虽然解决了“忙则等待”的问题,但又违背了“空闲让进”和“有限等待”原则,会因各进程都长期无法访问临界资源而产生“饥饿”现象。

    4.Peterson算法:

    算法思想:双标志后检查法中,两个进程都想睁着进入临界区,但是谁也不让谁,最后谁都无法进入临界区,可以让进程尝试“孔融让梨”,主动让对方优先使用临界区。

    bool flag[2];//表示进入临界区意愿的数组
    flag[0]=false;
    flag[1]=false;//刚开始设置为两个进程都不想进入临界区
    int turn=0;
    P0进程:
    flag[0]=true;       1//表明自己想进入临界区
    turn=1;             2//但又表示可以优先让对方进入临界区
    while(flag[1]&&turn==1);     3//123属于进入区
    critical section;   4
    flag[0]=false;      5
    remainder section;
    P1进程:
    flag[1]=true;       6
    turn=0;             7
    while(flag[0]&&turn==0);     8
    critical section;   9//访问临界区
    flag[1]=false;      10//访问完临界区,修改标记为P1不想使用临界区
    reminder section;
    

    可以看一下123和456的访问组合来判断是否会出现双标志检查法的问题。
    123 456 P0先执行;1 6 2 3 7 8P1先执行;1 2 6 7 8 3P0先执行

    硬件实现:

    中断屏蔽方法:
    利用“开/关中断指令”实现(与原语的实现思想相同,即在某进程开始访问临界区到结束访问为止都不允许被中断,也就是不能发生进程切换,因此也不可能发生两个进程同时访问临界区的情况)。
    关中断:关中断后不允许当前进程被中断,也必然不会发生进程切换。
    开中断:直到当前进程访问完临界区,再执行开中断指令,才有可能有别的进程上处理机并访问临界区。
    优点:简单、高效
    缺点:不适用于多处理机,只适用于操作系统内核进程,不适用于用户进程(因为开/关中断指令只能运行在内核态,这组指令如果能让用户随便使用会很危险)。
    TestAndSet指令
    简称TS指令,也有地方称为TestAndSetLock指令或TSL指令。
    TSL指令是用硬件实现的,执行的过程不允许被中断,只能一气呵成。相比于软件实现的方法,TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。优点:实现简单,无需像软件实现方法那样严格的检查是否会有逻辑漏洞。
    缺点:不满足“让权等待”原则,暂时无法进入临界区的进程会占用CPU并循环执行TSL指令,从而导致“忙等”。
    Swap指令
    Swap指令是用硬件实现的,执行的过程不允许被中断,只能一气呵成,以下是用C语言描述的逻辑:

    //Swap 指令的作用是交换两个变量的值
    Swap(bool *a,bool *b)
    {
    bool temp;
    temp=*a;
    *a=*b;
    *b=temp;
    }
    //以下是用Swap指令实现互斥的算法逻辑
    //lock表示当前临界区是否被加锁
    bool old=true;
    while(old==true)
    {
    Swap(&lock,&old);
    }
    //临界代码段...
    lock=false;
    //剩余代码段...
    

    逻辑上看Swap和TSL并无太大差别,都是先记录下此时临界区是否已经被上锁(记录在old变量上),再将上锁标记lock设置为true,最后检查old,如果old为false则说明之前没有别的进程对临界区上锁,则可跳出循环,进入临界区。

    信号量机制实现进程互斥:

    设置互斥信号量mutex,初值为1

    //信号量机制实现互斥
    semaphore mutex=1;
    P1()
    {
    P(mutex);
    //临界区代码
    V(mutex);
    }
    P2()
    {
    P(mutex);
    //临界区代码
    V(mutex);
    ...
    }
    
    展开全文
  • 进程同步 进程同步 :直接制约关系,为了完成某种任务,建立两个或者多个进程,这些...进程互斥 之前我们学过 两种资源共享方式 1.互斥共享方式 2.同时共享方式 我们把一个时间段内只允许一个进程使用的资源成为临界.

    在这里插入图片描述

    进程同步

    进程同步 :直接制约关系,为了完成某种任务,建立两个或者多个进程,这些进程因为需要在某些位置上协调他们的工作次序而产生
    制约关系。进程之间直接制约关系就是源于它们之间的合作

    举个例子
    在之前我们学习进程通信的时候,其中有一个管道通信
    其中包括两个步骤,一个是写数据,一个是读数据
    但是在实际应用中必须按照 写数据在先 读数据在后的顺序执行

    这就是进程同步所要讨论的内容

    进程互斥

    之前我们学过 两种资源共享方式 1.互斥共享方式 2.同时共享方式

    我们把一个时间段内只允许一个进程使用的资源成为临界资源
    许多物理设备(摄像头 打印机)都属于临界资源,此外还有许多变量,数据,内存缓冲区等都属于临界资源

    对于临界资源的访问 必须互斥地执行

    进程互斥 当一个进程访问某些临界资源的时候,另一个想要访问该临界资源的进程必须等待
    当前访问两将诶资源的进程访问结束,释放该资源之后,另一个进程才能去访问临界资源

    在这里插入图片描述
    进入区负责检查是否可进入临界区 若可进入,则应设置正在访问临界资源的标志
    临界区 访问临界资源的那段代码
    退出区负责接触正在访问临界资源的标志(解锁)
    剩余区做其他处理

    临界区是进程中访问临界资源的代码段
    进入区和退出区是负责实现互斥的代码段

    为了实现临界资源的互斥访问,同时保证系统整体性能,需要遵循下面几条原则
    **1.空闲让进 临界区空闲时,可以允许一个请求进入临界区的进程立即进入临界区
    2.忙则等待 当已有进程进入临界区时,其他驶入进入临界区的进程必须等待
    3.有限等待,对于请求访问的进程,应保证有闲时间内进入临界区(防止产生饥饿的情况)
    **
    4.让权等待,当进程不能进入临界区的时候 应立即释放处理机 防止进程忙等待

    进程互斥的软件实现方法

    在这里插入图片描述

    单标志法

    下面我给出一段代码

    int turn=0;//turn表示当前允许进入临界区的进程号
    
    po进程
    while (turn!=0);
    critical section;
    turn =1;
    remainder section;
    
    p1进程
    while(turn!=1);   //进入区
    critical section ;//临界区
    turn=0;			  //退出区
    remainder section;//剩余区
    

    可以看到turn初值为0 刚开始的时候只允许0号进程进入临界区
    若p1先上处理机运行 则一直会卡在while( turn != 1 )
    直到时间片用完,发生调度 切换p0上处理机运行

    代码while( turn != 0) 不会卡主p0正常访问临界区,在P0访问临界区器件及时切换回P1,
    P1依然会卡在while(turn != 1);
    之后再P0退出区将turn修改为1之后P1才能进入临界区

    因此该算法可以实现”同一时刻最多之循序一个进程访问临界区“

    turn表示允许当前进入临界区的进程号,但是只有当前允许进入临界区的进程在访问了临界区之后,才会修改turn的值
    也就是说 对于临界区的访问 必须按P0 P1 P0 P1……这样的顺序执行的
    这种方式带来的问题是 如果此时允许进入临界区的是P0,而P0一直不访问临界区
    那么虽然此时临界区处于
    空闲状态
    但是不允许P1的访问

    这就违背了空闲让进的原则 这就是单标志法所存在的主要问题

    双标志先检查法

    双标志法的思想是 设置一个bool的数组flag[] 数组中各个元素用来标记各个进程想要进入临界区的意愿
    比如flag[0]=true 这就表示0号进程现在想要进入临界区,每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区
    如果没有,那自身对应的flag修改为true 之后便访问临界区

    bool flag[2];//表示进入临界区意愿的数组
    flag[0]=false;
    flag[0]=false;
    P0进程
    while(flag[1]);//如果此时P1想进入临界区 P0就一直循环等待
    flag[0]=true;//标记P0想进入临界区
    critical section;//进入临界区
    flag[0[=false;//访问临界区结束 修改P0为不想使用临界区
    remainder section
    
    P1进程
    while(flag[0]);
    flag[1]=true;
    critical section;
    flag[1]=false;
    remainder section;
    

    上述代码中大家看注释应该也可以理解

    但是存在的问题就是P1和P0同时进入临界区

    原因在于:如果两个进程并发执行 进入区的“检查”和“上锁”两个处理不是一气呵成的,“检查”之后“上锁”可能发生了进程切换
    通俗点说就是只要我换的够快 我就可以混进去

    所以双标志先检查法的主要问题是违反了“忙则等待”的原则

    双标志后检查法

    双标志先检查法的改版 前一个算法的问题是先检查后上锁 但是两个进程无法一气呵成 导致了可能两个进程同时进入临界区的问题
    于是人们想到的先上锁 后检查的方法来避免上述问题

    bool flag[2];//表示进入临界区意愿的数组
    flag[0]=false;
    flag[0]=false;
    P0进程
    flag[0]=true;//标记P0想进入临界区
    while(flag[1]);//如果此时P1想进入临界区 P0就一直循环等待
    critical section;//进入临界区
    flag[0[=false;//访问临界区结束 修改P0为不想使用临界区
    remainder section
    
    P1进程
    flag[1]=true;
    while(flag[0]);
    critical section;
    flag[1]=false;
    remainder section;
    

    但是这次虽然解决了两个进程同时进入的问题
    但是 又违背了空闲让进 和 有限等待的原则会导致长期无法访问临界区产生饥饿的现象
    两个进程都想争着进入临界区,但是互不相让 最后谁都无法进入临界区
    有点鹬蚌相争的意思

    Peterson算法

    这个算法超级超级厉害 很多人看了直呼内行
    我们可以理解为孔融让梨的故事 (来自东方的神秘力量)
    在前边几个算法中两个进程互不想让 最后争的头破血流 要不都进去了 要不都进不去
    这个算法很完美的 避开了所有的问题 主动让对方进入临界区

    bool flag[2];//表示进入临界区的意愿 初始值都是false
    int turn=0;//turn表示优先让那个进程进入临界区
    P0进程
    flag[0]=true;//P0进程想进入临界区
    turn=1;//让梨 表示可以先让对方进入临界区
    while(flag[1]==true && turn==1);//如果对方想进 并且自己表示谦让对方就一直循环下去
    //如果对方不想进 咱们就进去
    critical section;
    flag[0]=false;
    remainder section;
    
    P1进程
    flag[1]=true;
    turn=0;//表示可以让对方先进
    while(flag[0]==true && turn==0);
    critical section;
    flag[1]=false;
    remainder section;
    
    

    如果并发进行 并且两个都想要进入 但是他们又互相谦让怎么办呢?
    我们可以把它说成串行执行的 然后最后一个谦让的 后进入
    不知道我这样说大家能不能明白(我尽力了)

    举个有味道的例子
    看完这个例子我想大家指定明白了 要是还没有明白老夫也无能为力了(狗头)

    有一天你和舍友都想去上厕所(大号) 但是厕所只有一个空位
    你虽然想上厕所 但是出于礼貌 你和舍友说要是着急你先上吧(谦让)
    但是你的舍友不想上 那么理所应当的你就上了
    这是最最基本的一种情况

    假如你俩同时都想上大号
    你虽然想上厕所 但是出于礼貌 你和舍友说要是着急你先上吧(谦让)
    你的舍友也是个通情达理之人
    舍友说:你要是想上你先上吧(谦让)
    舍友的这次谦让把你高兴坏了
    然后你就去上了(这就是两个进程并行执行,并且同时想进入的例子)
    可以看出来最后一个谦让的 就是后上的
    但是也能看出来你和舍友也只是表面兄弟(手动狗头)
    这次我真的尽力了

    Peterson算法用软件方式解决了进程互斥问题
    遵循了空闲让进 忙则等待 有限等待的三个原则
    但是依然未遵循让权等待的原则
    讲个笑话:这个算法是Peterson在上厕所时想出来的(手动狗头)

    这篇博客就介绍这么多吧 希望对大家有所帮助

    展开全文
  • 进程互斥硬件实现方法 中断屏蔽方法 利用“开/关中断指令”实现(与原语的实现思想相同,即在某进程开始访问临界区到结束访问为止都不允许被中断,也就不能发生进程切换,因此也不可能发生两个同时访问临界区的情况...

    进程互斥硬件实现方法

    中断屏蔽方法

    利用“开/关中断指令”实现(与原语的实现思想相同,即在某进程开始访问临界区到结束访问为止都不允许被中断,也就不能发生进程切换,因此也不可能发生两个同时访问临界区的情况)

    a3bfe31b70b15011ca3816d8bf27da2a.png

    TestAndSet指令

    img

    Swap指令

    img

    展开全文
  • 实现进程互斥方法

    2020-03-23 11:15:31
    (OS)实现互斥方法 一、软件方法(3种): ①单标记法:该算法设置一个公用整型变量turn,用于指示被允许进入临界区的进程编号,即若turn=0,则允许P0进程进入临界区。该算法可确保每次只允许一个进程进入临界区。...

    (OS)实现互斥的方法

    一、软件方法(3种):

    ①单标记法:该算法设置一个公用整型变量turn,用于指示被允许进入临界区的进程编号,即若turn=0,则允许P0进程进入临界区。该算法可确保每次只允许一个进程进入临界区。
    ②双标志法先检查法:该算法的基本思想是在每一个进程访问临界区资源之前,先查看一下临界资源是否正被访问,若正被访问,该进程需等待;否则,进程才进入自己的临界区。为此,设置了一个数据flag[i],如第i个元素值为FALSE,表示Pi进程未进入临界区,值为TRUE,表示Pi进程进入临界区。
    ③双标志法后检查法:算法二是先检测对方进程状态标志后,再置自己标志,由于在检测和放置中可插入另一个进程到达时的检测操作,会造成两个进程在分别检测后,同时进入临界区。为此,算法三釆用先设置自己标志为TRUE后,再检测对方状态标志,若对方标志为TURE,则进程等待;否则进入临界区。
    ④Peterson算法:为了防止两个进程为进入临界区而无限期等待,又设置变量turn,指示不允许进入临界区的进程编号,每个进程在先设置自己标志后再设置turn 标志,不允许另一个进程进入。这时,再同时检测另一个进程状态标志和不允许进入标志,这样可以保证当两个进程同时要求进入临界区,只允许一个进程进入临界区。

    二、硬件方法(3种):

    ①中断屏蔽方法(关中断):当一个进程正在使用处理机执行它的临界区代码时,要防止其他进程再进入其临界区访问的最简单的方法是:禁止一切中断发生,或称之为屏蔽中断、
    ②TestAndSet指令:这条指令是原子操作,即执行该代码时不允许被中断。其功能是:读出指定标志后把该标志设置为真。
    ③ Swap 指令:该指令的功能是交换两个字(字节)的内容,逻辑同TSL。

    三、信号量:利用PV 操作实现互斥

    四、管程:利用管程可以更方便地实现进程互斥,且互斥由编译器负责实现。

    以上内容引自-王道考研
    王道考研-操作系统






    to be continued
    how
    2020/3/23

    展开全文
  • 进程互斥的硬件实现方法
  • 进程互斥的软件实现方法
  • 实现进程互斥的硬件方法 中断禁用 单处理器系统中进程在进入临界区前禁用中断,离开临界区后启用中断,这样保证进程在临界区时不会被打断,不会被抢占 while (true){ //禁用中断 //临界区 //启用中断 //其他部分...
  • 2.3.2进程互斥的软件实现方法 知识总览 1.单标志法
  • 实现进程互斥的软件方法 Peterson算法 #include<stdio.h> #include<stdlib.h> #include<pthread.h> #define true 1 #define false 0 typedef int bool; bool flag[2]; int turn; void procedure0...
  • 2.3.3进程互斥的硬件实现方法 知识总览 1.中断屏蔽方法 2.Test and Set指令 3.Swap指令 4.总结
  • 进程同步与进程互斥

    2020-06-25 12:28:48
    进程同步和进程互斥概念进程互斥的软件实现方法单标志法双标志先检查法双标志后检查法Peterson算法进程互斥的硬件实现方法中断屏蔽方法TestAndSet指令Swap指令 概念 进程具有异步性的特征,异步性是指各并发执行的...
  • 2.3.2. 进程互斥的软件实现方法 文章目录2.3.2. 进程互斥的软件实现方法1.知识总览2.单标志法3.双标志先检查法4.双标志后检查法5. perterson算法6. 知识回顾 1.知识总览 2.单标志法 3.双标志先检查法 4.双标志后...
  • 单标志法 ...特点:可以实现互斥进程是轮流访问的,违背了空闲让进的原则 双标志先检查法 检查和上锁是分开的,不是原子操作,可能会发生进程切换。 双标志后检查法 peterson算法 ...
  • 进程互斥

    2017-05-06 08:25:51
    等待这一资源就要在操作系统实现互斥:当一个进程正在使用资源的时候,其他希望使用该资源的程序必须等待,当该进程使用完并释放资源后,才允许其他进程去访问此资源,我们称这种进程之间的互相制约关系叫做互斥。...
  • 进程同步和进程互斥进程同步和进程互斥进程互斥的软件实现方法单标志法双标志先检查法双标志后检查法Peterson算法进程互斥的硬件实现方法 进程同步和进程互斥 进程同步: 1.并发性带来了异步性,又是需要通过进程...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,724
精华内容 1,089
关键字:

进程互斥方法