精华内容
下载资源
问答
  • 进程同步和互斥机制

    2020-12-23 09:28:19
    本讲将介绍进程间的两种主要关系——同步互斥,然后着重讲解解决进程同步的几种机制。进程互斥是进程之间发生的一种间接性作用,一般是程序不希望的。通常的情况是两个或两个以上的进程需要同时访问某个共享变量。...

    进程同步的几种机制  转自:http://www.cnblogs.com/sonic4x/archive/2011/07/05/2098036.html

    多进程的系统中避免不了进程间的相互关系。本讲将介绍进程间的两种主要关系——同步与互斥,然后着重讲解解决进程同步的几种机制。

    进程互斥是进程之间发生的一种间接性作用,一般是程序不希望的。通常的情况是两个或两个以上的进程需要同时访问某个共享变量。我们一般将发生能够问共享变量的程序段称为临界区。两个进程不能同时进入临界区,否则就会导致数据的不一致,产生与时间有关的错误。解决互斥问题应该满足互斥和公平两个原则,即任意时刻只能允许一个进程处于同一共享变量的临界区,而且不能让任一进程无限期地等待。互斥问题可以用硬件方法解决,我们不作展开;也可以用软件方法,这将会在本讲详细介绍。

    进程同步是进程之间直接的相互作用,是合作进程间有意识的行为,典型的例子是公共汽车上司机与售票员的合作。只有当售票员关门之后司机才能启动车辆,只有司机停车之后售票员才能开车门。司机和售票员的行动需要一定的协调。同样地,两个进程之间有时也有这样的依赖关系,因此我们也要有一定的同步机制保证它们的执行次序。

    本讲主要介绍以下四种同步和互斥机制:信号量、管程、会合、分布式系统。

    一,信号量

    理解PV:

    PV操作由P操作原语和V操作原语组成(原语是不可中断的过程),对信号量进行操作,具体定义如下:

    P(S):①将信号量S的值减1,即S=S-1;

    ②如果S?0,则该进程继续执行;否则该进程置为等待状态,排入等待队列。

    V(S):①将信号量S的值加1,即S=S+1;

    ②如果S>0,则该进程继续执行;否则释放队列中第一个等待信号量的进程。

    PV操作的意义:我们用信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。

    什么是信号量?信号量(semaphore)的数据结构为一个值和一个指针,指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时,表示当前可用资源的数量;当它的值小于0时,其绝对值表示等待使用该资源的进程个数。注意,信号量的值仅能由PV操作来改变。

    一般来说,信号量S?0时,S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源,因此S的值减1;当S<0时,表示已经没有可用资源,请求者必须等待别的进程释放该类资源,它才能运行下去。而执行一个V操作意味着释放一个单位资源,因此S的值加1;若S?0,表示有某些进程正在等待该资源,因此要唤醒一个等待状态的进程,使之运行下去。

    利用信号量和PV操作实现进程互斥的一般模型是:

    进程P1              进程P2           ……          进程Pn

    ……                  ……                           ……

    P(S);              P(S);                         P(S);

    临界区;             临界区;                        临界区;

    V(S);              V(S);                        V(S);

    ……                  ……            ……           ……

    其中信号量S用于互斥,初值为1。

    使用PV操作实现进程互斥时应该注意的是:

    (1)每个程序中用户实现互斥的P、V操作必须成对出现,先做P操作,进临界区,后做V操作,出临界区。若有多个分支,要认真检查其成对性。

    (2)P、V操作应分别紧靠临界区的头尾部,临界区的代码应尽可能短,不能有死循环。

    (3)互斥信号量的初值一般为1。

    利用信号量和PV操作实现进程同步

    PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来,当信号量的值为0时,表示期望的消息尚未产生;当信号量的值非0时,表示期望的消息已经存在。用PV操作实现进程同步时,调用P操作测试消息是否到达,调用V操作发送消息。

    使用PV操作实现进程同步时应该注意的是:

    (1)分析进程间的制约关系,确定信号量种类。在保持进程间有正确的同步关系情况下,哪个进程先执行,哪些进程后执行,彼此间通过什么资源(信号量)进行协调,从而明确要设置哪些信号量。

    (2)信号量的初值与相应资源的数量有关,也与P、V操作在程序代码中出现的位置有关。

    (3)同一信号量的P、V操作要成对出现,但它们分别在不同的进程代码中。

    【例1】生产者-消费者问题

    在多道程序环境下,进程同步是一个十分重要又令人感兴趣的问题,而生产者-消费者问题是其中一个有代表性的进程同步问题。下面我们给出了各种情况下的生产者-消费者问题,深入地分析和透彻地理解这个例子,对于全面解决操作系统内的同步、互斥问题将有很大帮助。

    (1)一个生产者,一个消费者,公用一个缓冲区。

    定义两个同步信号量:

    empty——表示缓冲区是否为空,初值为1。

    full——表示缓冲区中是否为满,初值为0。

    生产者进程

    while(TRUE){

    生产一个产品;

    P(empty);

    产品送往Buffer;

    V(full);

    }

    消费者进程

    while(True){

    P(full);

    从Buffer取出一个产品;

    V(empty);

    消费该产品;

    }

    (2)一个生产者,一个消费者,公用n个环形缓冲区。

    定义两个同步信号量:

    empty——表示缓冲区是否为空,初值为n。

    full——表示缓冲区中是否为满,初值为0。

    设缓冲区的编号为1~n-1,定义两个指针in和out,分别是生产者进程和消费者进程使用的指

    ,指向下一个可用的缓冲区。

    生产者进程

    while(TRUE){

    生产一个产品;

    P(empty);

    产品送往buffer(in);

    in=(in+1)mod n;

    V(full);

    }

    消费者进程

    while(TRUE){

    P(full);

    从buffer(out)中取出产品;

    out=(out+1)mod n;

    V(empty);

    消费该产品;

    }

    (3)一组生产者,一组消费者,公用n个环形缓冲区

    在这个问题中,不仅生产者与消费者之间要同步,而且各个生产者之间、各个消费者之间还必须互斥地访问缓冲区。

    定义四个信号量:

    empty——表示缓冲区是否为空,初值为n。

    full——表示缓冲区中是否为满,初值为0。

    mutex1——生产者之间的互斥信号量,初值为1。

    mutex2——消费者之间的互斥信号量,初值为1。

    设缓冲区的编号为1~n-1,定义两个指针in和out,分别是生产者进程和消费者进程使用的指针,指向下一个可用的缓冲区。

    生产者进程

    while(TRUE){

    生产一个产品;

    P(empty);

    P(mutex1);

    产品送往buffer(in);

    in=(in+1)mod n;

    V(mutex1);

    V(full);

    }

    消费者进程

    while(TRUE){

    P(full)

    P(mutex2);

    从buffer(out)中取出产品;

    out=(out+1)mod n;

    V(mutex2);

    V(empty);

    消费该产品;

    }

    需要注意的是无论在生产者进程中还是在消费者进程中,两个P操作的次序不能颠倒。应先执行同步信号量的P操作,然后再执行互斥信号量的P操作,否则可能造成进程死锁。

    【例2】桌上有一空盘,允许存放一只水果。爸爸可向盘中放苹果,也可向盘中放桔子,儿子专等吃盘中的桔子,女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用,请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。

    分析 在本题中,爸爸、儿子、女儿共用一个盘子,盘中一次只能放一个水果。当盘子为空时,爸爸可将一个水果放入果盘中。若放入果盘中的是桔子,则允许儿子吃,女儿必须等待;若放入果盘中的是苹果,则允许女儿吃,儿子必须等待。本题实际上是生产者-消费者问题的一种变形。这里,生产者放入缓冲区的产品有两类,消费者也有两类,每类消费者只消费其中固定的一类产品。

    解:在本题中,应设置三个信号量S、So、Sa,信号量S表示盘子是否为空,其初值为l;信号量So表示盘中是否有桔子,其初值为0;信号量Sa表示盘中是否有苹果,其初值为0。同步描述如下:

    int S=1;

    int Sa=0;

    int So=0;

    main()

    {

    cobegin

    father();      /*父亲进程*/

    son();        /*儿子进程*/

    daughter();    /*女儿进程*/

    coend

    father()

    {

    while(1)

    {

    P(S);

    将水果放入盘中;

    if(放入的是桔子)V(So);

    else  V(Sa);

    }

    }

    son()

    {

    while(1)

    {

    P(So);

    从盘中取出桔子;

    V(S);

    吃桔子;

    }

    daughter()

    {

    while(1)

    {

    P(Sa);

    从盘中取出苹果;

    V(S);

    吃苹果;

    思考题:

    四个进程A、B、C、D都要读一个共享文件F,系统允许多个进程同时读文件F。但限制是进程A和进程C不能同时读文件F,进程B和进程D也不能同时读文件F。为了使这四个进程并发执行时能按系统要求使用文件,现用PV操作进行管理,请回答下面的问题:

    (1)应定义的信号量及初值:                    。

    (2)在下列的程序中填上适当的P、V操作,以保证它们能正确并发工作:

    A()                B()                  C()                 D()

    {                 {                    {                  {

    [1];                [3];                  [5];                 [7];

    read F;             read F;                read F;              read F;

    [2];                [4];                  [6];                 [8];

    }                  }                    }                  }

    思考题解答:

    (1)定义二个信号量S1、S2,初值均为1,即:S1=1,S2=1。其中进程A和C使用信号量S1,进程B和D使用信号量S2。

    (2)从[1]到[8]分别为:P(S1) V(S1) P(S2) V(S2) P(S1) V(S1) P(S2) V(S2)

    信号量机制功能强大,但使用时对信号量的操作分散,而且难以控制,读写和维护都很困难。因此后来又提出了一种集中式同步进程——管程。其基本思想是将共享变量和对它们的操作集中在一个模块中,操作系统或并发程序就由这样的模块构成。这样模块之间联系清晰,便于维护和修改,易于保证正确性。

    管程作为一个模块,它的类型定义如下:

    monitor_name = MoNITOR;

    共享变量说明;

    define 本管程内部定义、外部可调用的函数名表;

    use 本管程外部定义、内部可调用的函数名表;

    内部定义的函数说明和函数体

    {

    共享变量初始化语句;

    }

    从语言的角度看,管程主要有以下特性:

    (1)模块化。管程是一个基本程序单位,可以单独编译;

    (2)抽象数据类型。管程是中不仅有数据,而且有对数据的操作;

    (3)信息掩蔽。管程外可以调用管程内部定义的一些函数,但函数的具体实现外部不可见;

    对于管程中定义的共享变量的所有操作都局限在管程中,外部只能通过调用管程的某些函数来间接访问这些变量。因此管程有很好的封装性。

    为了保证共享变量的数据一致性,管程应互斥使用。 管程通常是用于管理资源的,因此管程中有进程等待队列和相应的等待和唤醒操作。在管程入口有一个等待队列,称为入口等待队列。当一个已进入管程的进程等待时,就释放管程的互斥使用权;当已进入管程的一个进程唤醒另一个进程时,两者必须有一个退出或停止使用管程。在管程内部,由于执行唤醒操作,可能存在多个等待进程(等待使用管程),称为紧急等待队列,它的优先级高于入口等待队列。

    因此,一个进程进入管程之前要先申请,一般由管程提供一个enter过程;离开时释放使用权,如果紧急等待队列不空,则唤醒第一个等待者,一般也由管程提供外部过程leave。

    管程内部有自己的等待机制。管程可以说明一种特殊的条件型变量:var c:condition;实际上是一个指针,指向一个等待该条件的PCB队列。对条件型变量可执行wait和signal操作:(联系P和V; take和give)

    wait(c):若紧急等待队列不空,唤醒第一个等待者,否则释放管程使用权。执行本操作的进程进入C队列尾部;

    signal(c):若C队列为空,继续原进程,否则唤醒队列第一个等待者,自己进入紧急等待队列尾部。

    【示例】

    生产者-消费者问题(有buffer)

    问题描述:(一个仓库可以存放K件物品。生产者每生产一件产品,将产品放入仓库,仓库满了就停止生产。消费者每次从仓库中去一件物品,然后进行消费,仓库空时就停止消费。

    解答:

    管程:buffer=MODULE;

    (假设已实现一基本管程monitor,提供enter,leave,signal,wait等操作)  notfull,notempty:condition; // notfull控制缓冲区不满,notempty控制缓冲区不空;

    count,in,out: integer;     // count记录共有几件物品,in记录第一个空缓冲区,out记录第一个不空的缓冲区

    buf:array [0..k-1] of item_type;

    define deposit,fetch;

    use monitor.enter,monitor.leave,monitor.wait,monitor.signal;

    procedure deposit(item);

    {

    if(count=k) monitor.wait(notfull);

    buf[in]=item;

    in:=(in+1) mod k;

    count++;

    monitor.signal(notempty);

    }

    procedure fetch:Item_type;

    {

    if(count=0) monitor.wait(notempty);

    item=buf[out];

    in:=(in+1) mod k;

    count--;

    monitor.signal(notfull);

    return(item);

    }

    {

    count=0;

    in=0;

    out=0;

    }

    进程:producer,consumer;

    producer(生产者进程):

    Item_Type item;

    {

    while (true)

    {

    produce(&item);

    buffer.enter();

    buffer.deposit(item);

    buffer.leave();

    }

    }

    consumer(消费者进程):

    Item_Type item;

    {

    while (true)

    {

    buffer.enter();

    item=buffer.fetch();

    buffer.leave();

    consume(&item);

    }

    }

    【附】有关wait和signal的语言表示

    信号量结构使用C语言表示如下:

    typedef struct {

    int value;//记录了这个信号量的值

    struct process *list;//储存正在等待这个信号量的进程

    } semaphore;

    wait()信号量部分代码如下:

    wait(semaphore *S) {

    S->value--;

    if(S->value         add this process to S->list;

    block();

    }

    }

    signal()信号量部分代码如下:

    signal(semaphore *S) {

    S->value++;

    if(S->value <= 0) {

    remove a process P from S->list;

    wakeup(P);

    }

    }

    一、The Bounded-Buffer Problem:

    full初始化为0,empty初始化为n,mutex为1

    do{

    wait(full);

    wait(mutex);

    ...

    //remove an item from buffer to nextc

    ...

    signal(mutex);

    signal(empty);

    ...

    //consume the item in nextc

    ...

    } while(TRUE);

    二、The Readers-Writers Problem:

    wrt初始化为1,readcount初始化为0,mutex为1

    写者操作:

    do{

    wait(wrt);

    ...

    //writing is performed

    ...

    signal(wrt);

    } while(TRUE);

    读者操作:

    do{

    wait(mutex);//确保与signal(mutex)之间的操作不会被其他读者打断

    readcount++;

    if(readcount == 1)

    wait(wrt);

    signal(mutex);

    ...

    //reading is performed

    ...

    wait(mutex);

    readcount--;

    if(readcount == 0)

    signal(wrt);

    signal(mutex);

    } while(TRUE);

    三、The Dining-Philosophers Problem:

    所有的chopstick[5]全部初始化为1

    do{

    wait(chopstick[i]);

    wait(chopstick[(i+1)%5]);

    ...

    //eating

    ...

    signal(chopstick[i]);

    signal(chopstick[(i+1)%5]);

    ...

    //thinking

    ...

    } while(TRUE);

    但是这个解决方案的最大问题在于它会出现死锁。所以我认为应该增加一个信号量mutex,并初始化为1:

    do{

    wait(mutex);

    wait(chopstick[i]);

    wait(chopstick[(i+1)%5]);

    signal(mutex);

    ...

    //eating

    ...

    wait(mutex);

    signal(chopstick[i]);

    signal(chopstick[(i+1)%5]);

    signal(mutex);

    ...

    //thinking

    ...

    } while(TRUE);

    这样由于确保了一位哲学家在拿起两只筷子的时间内其他哲学家不可以拿起任何一支筷子,从而破坏了死锁出现需要的四个特征中的Hold And Wait特征,从而避免了死锁的发生。

    展开全文
  • 简介进程同步是一个操作系统级别的概念,是在多道程序的环境下,存在着不同的制约关系,为了协调这种互相制约的关系,实现资源共享进程协作,从而避免进程之间的冲突,引入了进程同步。临界资源在操作系统中,进程...

    简介

    进程同步是一个操作系统级别的概念,是在多道程序的环境下,存在着不同的制约关系,为了协调这种互相制约的关系,实现资源共享和进程协作,从而避免进程之间的冲突,引入了进程同步。

    临界资源

    在操作系统中,进程是占有资源的最小单位(线程可以访问其所在进程内的所有资源,但线程本身并不占有资源或仅仅占有一点必须资源)。但对于某些资源来说,其在同一时间只能被一个进程所占用。这些一次只能被一个进程所占用的资源就是所谓的临界资源。典型的临界资源比如物理上的打印机,或是存在硬盘或内存中被多个进程所共享的一些变量和数据等(如果这类资源不被看成临界资源加以保护,那么很有可能造成丢数据的问题)。

    对于临界资源的访问,必须是互诉进行。也就是当临界资源被占用时,另一个申请临界资源的进程会被阻塞,直到其所申请的临界资源被释放。而进程内访问临界资源的代码被成为临界区。

    对于临界区的访问过程分为四个部分:

    1.进入区:查看临界区是否可访问,如果可以访问,则转到步骤二,否则进程会被阻塞

    2.临界区:在临界区做操作

    3.退出区:清除临界区被占用的标志

    4.剩余区:进程与临界区不相关部分的代码

    进程间同步和互诉的概念

    进程同步

    进程同步也是进程之间直接的制约关系,是为完成某种任务而建立的两个或多个线程,这个线程需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系来源于他们之间的合作。

    比如说进程A需要从缓冲区读取进程B产生的信息,当缓冲区为空时,进程B因为读取不到信息而被阻塞。而当进程A产生信息放入缓冲区时,进程B才会被唤醒。概念如图1所示。

    图1.进程之间的同步

    用C#代码模拟进程之间的同步如代码1所示。

    class ProcessSyn

    {

    private static Mutex mut = new Mutex();

    static void Main()

    {

    Console.WriteLine("进程1执行完了进程2才能执行.......");

    Thread Thread1 = new Thread(new ThreadStart(Proc1));

    Thread Thread2 = new Thread(new ThreadStart(Proc2));

    Thread1.Start();

    Thread2.Start();

    Console.ReadKey();

    }

    private static void Proc1()

    {

    mut.WaitOne();

    Console.WriteLine("线程1执行操作....");

    Thread.Sleep(3000);

    mut.ReleaseMutex();//V操作

    }

    private static void Proc2()

    {

    mut.WaitOne();//P操作

    Console.WriteLine("线程2执行操作....");

    mut.WaitOne();

    }

    }

    代码1.C#模拟进程之间的同步

    运行结果如图2所示。

    图2.运行结果

    进程互斥

    进程互斥是进程之间的间接制约关系。当一个进程进入临界区使用临界资源时,另一个进程必须等待。只有当使用临界资源的进程退出临界区后,这个进程才会解除阻塞状态。

    比如进程B需要访问打印机,但此时进程A占有了打印机,进程B会被阻塞,直到进程A释放了打印机资源,进程B才可以继续执行。概念如图3所示。

    图3.进程之间的互斥

    用C#模拟进程之间的互斥,这里我启动了5个线程,但同一时间内只有一个线程能对临界资源进行访问。如代码2所示。

    class ProcessMutex

    {

    private static Mutex mut = new Mutex();

    private const int numThreads = 5;

    static void Main()

    {

    for (int i = 0; i <= numThreads; i++)

    {

    Thread myThread = new Thread(new ThreadStart(UseResource));

    myThread.Name = String.Format("线程{0}", i + 1);

    myThread.Start();

    }

    Console.ReadKey();

    }

    //同步

    private static void UseResource()

    {

    // 相当于P操作

    mut.WaitOne();

    /*下面代码是线程真正的工作*/

    Console.WriteLine("{0}已经进入临界区",

    Thread.CurrentThread.Name);

    Random r = new Random();

    int rNum = r.Next(2000);

    Console.WriteLine("{0}执行操作,执行时间为{1}ms", Thread.CurrentThread.Name,rNum);

    Thread.Sleep(rNum);

    Console.WriteLine("{0}已经离开临界区\r\n",

    Thread.CurrentThread.Name);

    /*线程工作结束*/

    // 相当于V操作

    mut.ReleaseMutex();

    }

    //互斥

    }

    代码2.C#模拟进程之间的互斥

    运行结果如图4所示。

    图4.C#模拟进程互斥

    实现临界区互斥的基本方法

    硬件实现方法

    通过硬件实现临界区最简单的办法就是关CPU的中断。从计算机原理我们知道,CPU进行进程切换是需要通过中断来进行。如果屏蔽了中断那么就可以保证当前进程顺利的将临界区代码执行完,从而实现了互斥。这个办法的步骤就是:屏蔽中断--执行临界区--开中断。但这样做并不好,这大大限制了处理器交替执行任务的能力。并且将关中断的权限交给用户代码,那么如果用户代码屏蔽了中断后不再开,那系统岂不是跪了?

    还有硬件的指令实现方式,这个方式和接下来要说的信号量方式如出一辙。但是通过硬件来实现,这里就不细说了。

    信号量实现方式

    这也是我们比较熟悉P V操作。通过设置一个表示资源个数的信号量S,通过对信号量S的P和V操作来实现进程的的互斥。

    P和V操作分别来自荷兰语Passeren和Vrijgeven,分别表示占有和释放。P V操作是操作系统的原语,意味着具有原子性。

    P操作首先减少信号量,表示有一个进程将占用或等待资源,然后检测S是否小于0,如果小于0则阻塞,如果大于0则占有资源进行执行。

    V操作是和P操作相反的操作,首先增加信号量,表示占用或等待资源的进程减少了1个。然后检测S是否小于0,如果小于0则唤醒等待使用S资源的其它进程。

    前面我们C#模拟进程的同步和互斥其实算是信号量进行实现的。

    一些经典利用信号量实现同步的问题

    生产者--消费者问题

    问题描述:生产者-消费者问题是一个经典的进程同步问题,该问题最早由Dijkstra提出,用以演示他提出的信号量机制。本作业要求设计在同一个进程地址空间内执行的两个线程。生产者线程生产物品,然后将物品放置在一个空缓冲区中供消费者线程消费。消费者线程从缓冲区中获得物品,然后释放缓冲区。当生产者线程生产物品时,如果没有空缓冲区可用,那么生产者线程必须等待消费者线程释放出一个空缓冲区。当消费者线程消费物品时,如果没有满的缓冲区,那么消费者线程将被阻塞,直到新的物品被生产出来

    这里生产者和消费者是既同步又互斥的关系,首先只有生产者生产了,消费着才能消费,这里是同步的关系。但他们对于临界区的访问又是互斥的关系。因此需要三个信号量empty和full用于同步缓冲区,而mut变量用于在访问缓冲区时是互斥的。

    利用C#模拟生产者和消费者的关系如代码3所示。

    class ProducerAndCustomer

    {

    //临界区信号量

    private static Mutex mut = new Mutex();

    private static Semaphore empty = new Semaphore(5, 5);//空闲缓冲区

    private static Semaphore full = new Semaphore(0, 5);

    //生产者-消费者模拟

    static void Main()

    {

    Console.WriteLine("生产者消费者模拟......");

    for (int i = 1; i < 9; i++)

    {

    Thread Thread1 = new Thread(new ThreadStart(Producer));

    Thread Thread2 = new Thread(new ThreadStart(Customer));

    Thread1.Name = String.Format("生产者线程{0}", i);

    Thread2.Name = String.Format("消费者线程{0}", i);

    Thread1.Start();

    Thread2.Start();

    }

    Console.ReadKey();

    }

    private static void Producer()

    {

    Console.WriteLine("{0}已经启动",Thread.CurrentThread.Name);

    empty.WaitOne();//对empty进行P操作

    mut.WaitOne();//对mut进行P操作

    Console.WriteLine("{0}放入数据到临界区", Thread.CurrentThread.Name);

    Thread.Sleep(1000);

    mut.ReleaseMutex();//对mut进行V操作

    full.Release();//对full进行V操作

    }

    private static void Customer()

    {

    Console.WriteLine("{0}已经启动", Thread.CurrentThread.Name);

    Thread.Sleep(12000);

    full.WaitOne();//对full进行P操作

    mut.WaitOne();//对mut进行P操作

    Console.WriteLine("{0}读取临界区", Thread.CurrentThread.Name);

    mut.ReleaseMutex();//对mut进行V操作

    empty.Release();//对empty进行V操作

    }

    }

    代码3.使用C#模拟生产者和消费者的关系

    运行结果如图5所示。

    图5.生产者消费者C#模拟结果

    读者--写者问题

    问题描述:

    一个数据文件或记录,统称数据对象,可被多个进程共享,其中有些进程只要求读称为"读者",而另一些进程要求写或修改称为"写者"。

    规定:允许多个读者同时读一个共享对象,但禁止读者、写者同时访问一个共享对象,也禁止多个写者访问一个共享对象,否则将违反Bernstein并发执行条件。

    通过描述可以分析,这里的读者和写者是互斥的,而写者和写者也是互斥的,但读者之间并不互斥。

    由此我们可以设置3个变量,一个用来统计读者的数量,另外两个分别用于对读者数量读写的互斥,读者和读者写者和写者的互斥。如代码4所示。

    class ReaderAndWriter

    {

    private static Mutex mut = new Mutex();//用于保护读者数量的互斥信号量

    private static Mutex rw = new Mutex();//保证读者写者互斥的信号量

    static int count = 0;//读者数量

    static void Main()

    {

    Console.WriteLine("读者写者模拟......");

    for (int i = 1; i < 6; i++)

    {

    Thread Thread1 = new Thread(new ThreadStart(Reader));

    Thread1.Name = String.Format("读者线程{0}", i);

    Thread1.Start();

    }

    Thread Thread2 = new Thread(new ThreadStart(writer));

    Thread2.Name = String.Format("写者线程");

    Thread2.Start();

    Console.ReadKey();

    }

    private static void Reader()

    {

    mut.WaitOne();

    if (count == 0)

    {

    rw.WaitOne();

    }

    count++;

    mut.ReleaseMutex();

    Thread.Sleep(new Random().Next(2000));//读取耗时1S

    Console.WriteLine("读取完毕");

    mut.WaitOne();

    count--;

    mut.ReleaseMutex();

    if (count == 0)

    {

    rw.ReleaseMutex();

    }

    }

    private static void writer()

    {

    rw.WaitOne();

    Console.WriteLine("写入数据");

    rw.ReleaseMutex();

    }

    代码4.C#模拟读者和写者问题

    运行结果如图6所示。

    图6.读者写者的运行结果

    哲学家进餐问题

    问题描述:

    有五个哲学家,他们的生活方式是交替地进行思考和进餐。哲学家们公用一张圆桌,周围放有五把椅子,每人坐一把。在圆桌上有五个碗和五根筷子,当一个哲学家思考时,他不与其他人交谈,饥饿时便试图取用其左、右最靠近他的筷子,但他可能一根都拿不到。只有在他拿到两根筷子时,方能进餐,进餐完后,放下筷子又继续思考。

    图7.哲学家进餐问题

    根据问题描述,五个哲学家分别可以看作是五个进程。五只筷子分别看作是五个资源。只有当哲学家分别拥有左右的资源时,才得以进餐。如果不指定规则,当每个哲学家手中只拿了一只筷子时会造成死锁,从而五个哲学家都因为吃不到饭而饿死。因此我们的策略是让哲学家同时拿起两只筷子。因此我们需要对每个资源设置一个信号量,此外,还需要使得哲学家同时拿起两只筷子而设置一个互斥信号量,如代码5所示。

    class philosopher

    {

    private static int[] chopstick=new int[5];//分别代表哲学家的5只筷子

    private static Mutex eat = new Mutex();//用于保证哲学家同时拿起两双筷子

    static void Main()

    {

    //初始设置所有筷子可用

    for (int k = 1; k <= 5; k++)

    {

    chopstick[k - 1] = 1;

    }

    //每个哲学家轮流进餐一次

    for(int i=1;i<=5;i++)

    {

    Thread Thread1 = new Thread(new ThreadStart(Philosophers));

    Thread1.Name = i.ToString();

    Thread1.Start();

    }

    Console.ReadKey();

    }

    private static void Philosophers()

    {

    //如果筷子不可用,则等待2秒

    while (chopstick[int.Parse(Thread.CurrentThread.Name)-1] !=1 || chopstick[(int.Parse(Thread.CurrentThread.Name))%4]!=1)

    {

    Console.WriteLine("哲学家{0}正在等待", Thread.CurrentThread.Name);

    Thread.Sleep(2000);

    }

    eat.WaitOne();

    //同时拿起两双筷子

    chopstick[int.Parse(Thread.CurrentThread.Name)-1] = 0;

    chopstick[(int.Parse(Thread.CurrentThread.Name)) % 4] = 0;

    eat.ReleaseMutex();

    Thread.Sleep(1000);

    Console.WriteLine("哲学家{0}正在用餐...",Thread.CurrentThread.Name);

    //用餐完毕后放下筷子

    chopstick[int.Parse(Thread.CurrentThread.Name)-1] = 1;

    chopstick[(int.Parse(Thread.CurrentThread.Name)) % 4] = 1;

    Console.WriteLine("哲学家{0}用餐完毕,继续思考", Thread.CurrentThread.Name);

    }

    }

    代码5.C#模拟哲学家用餐问题

    运行结果如图7所示。

    图8.哲学家问题运行结果

    总结

    本文介绍了进程的同步和互斥的概念,临界区的概念,以及实现进程同步互斥的方式,并解决了3种实现同步的经典问题,并给出了相应的C#模拟代码。操作系统对于进程的管理是是计算机编程的基础之一,因此掌握这个概念会使你的内功更上一层。

    展开全文
  • 进程的同步和互斥

    2021-06-05 20:52:11
    1. 进程的同步   我们把异步环境下的一组并发进程因直接制约而互相发送消息、进行互相合作、互相等待,使得各进程按一定的速度执行的过程称为进程间的同步。具有同步关系的一组并发进程称为合作进程,合作进程间...

    1. 进程的同步

      我们把异步环境下的一组并发进程因直接制约而互相发送消息、进行互相合作、互相等待,使得各进程按一定的速度执行的过程称为进程间的同步。具有同步关系的一组并发进程称为合作进程,合作进程间互相发送的信号称为消息或事件。

    以下为简单示例:
    在这里插入图片描述



    2. 进程的互斥

      两个或两个以上的进程,不能同时进入关于同一组共享变量的临界区域,否则可能发生与时间有关的错误,这种现象被称作进程互斥· 也就是说,一个进程正在访问临界资源,另一个要访问该资源的进程必须等待。

    以下为简单示例:
    在这里插入图片描述



    3. 进程间制约关系

      在多道程序环境下,系统中各进程以不可预测的速度向前推进,进程的异步性会给系统造成混乱,造成了结果的不可再现性。为防止这种现象,异步的进程间推进受到二种限制:

    (1)资源共享关系
      多进程共享资源,例如各进程争用一台计算机,这时各进程使用这台打印机时有一定的限制。如各进程随意使用打印机,会造成打印机结果交织在一起难以区分。所以必须由系统统一分配,每次只允许一个进程使用一段时间打印机,等该进程使用完毕后再将打印机分配给其它进程。这种使用原则称为互斥使用。 互斥关系是一种间接制约关系。

    (2)相互合作关系
      在某些进程之间还存在合作关系,例如一个程序的输入、计算、打印三个程序段作为三个进程并发执行,由于这三个进程间存在着相互合作的关系,即先输入再计算、最后再打印的关系,所以这三个进程在并发执行时推进序列受到限制,要保证其合作关系正确,进程间这种关系称为同步关系。同步关系是一种直接制约关系。




    结束语:我们可以用热情去感染他人,同样也可以让热情感染我们。多与那些对生命充满活力、机警而又相当清醒的人交往,会激发出你热情的火花的。

    展开全文
  • 本文主要讲述了操作系统中同步和互斥这两个概念,并说明了操作系统中是如何实现同步和互斥的。除此之外,本文还重点讲述了线程进程的概念。


    在讲同步和互斥之前,需要先熟悉一些计算机相关的基础概念

    计算机基础知识

    进程和线程

    • 进程(Process),顾名思义就是正在执行的应用程序,是软件的执行副本。而线程是轻量级的进程。

    • 进程是分配资源的基础单位。而线程是程序执行的基本单位。

    每一种应用,比如游戏,执行后是一个进程。但是游戏内部需要图形渲染、需要网络、需要响应用户操作,这些行为不可以互相阻塞,必须同时进行,这样就设计成线程。现代的CPU以多线程为主,如下内容也主要是说多线程,我们讲的调度更多的也是线程的调度。

    计算机的资源

    我们经常讲操作系统需要分配资源,最重要的 3 种资源是:计算资源(CPU)内存资源文件资源。计算机的CPU是有限的,而需要执行的任务往往有多个,CPU无法同时执行所有的任务,只能挨个执行,这就相当于是给任务(线程)分配了计算资源,得到了计算资源的任务就可以被执行。文件资源比如计算机中存储的文件是文件资源。

    归根到底不管是计算机的组成还是操作系统,都面临着资源有限,而使用资源的任务(用户)却非常多,如何合理的安排资源,使得任务都能得到更好的执行,不管是线程和进程的设计也好,还是计算机的三级存储结构也好,都是在权衡利弊以及成本的基础上,为了更好的统筹规划资源而设计出来的。

    内核

    操作系统的内核

    在这里插入图片描述

    用户态和内核态

    在这里插入图片描述

    内核线程和用户线程

    线程设计出来后,因为只被分配了计算资源(CPU),因此被称为轻量级进程。被分配的方式,就是由操作系统调度线程。操作系统创建一个进程后,进程的入口程序被分配到了一个主线程执行,这样看上去操作系统是在调度进程,其实是调度进程中的线程。

    这种被操作系统直接调度的线程,我们也成为内核级线程。另外,有的程序语言或者应用,用户(程序员)自己还实现了线程。相当于操作系统调度主线程,主线程的程序用算法实现子线程,这种情况我们称为用户级线程。Linux 的 PThread API 就是用户级线程,KThread API 则是内核级线程。

    进程的开销比线程大在了哪里?

    以Linux为例:Linux 中创建一个进程自然会创建一个线程,也就是主线程。创建进程需要为进程划分出一块完整的内存空间,有大量的初始化操作,比如要把内存分段(堆栈、正文区等)。创建线程则简单得多,只需要确定 PC 指针和寄存器的值,并且给线程分配一个栈用于执行程序,同一个进程的多个线程间可以复用堆栈。因此,创建进程比创建线程慢,而且进程的内存开销更大。

    线程的同步和互斥

    什么是同步,什么是互斥?

    同步:线程同步并不是说线程同时运行,而是让线程按照一定的顺序执行,使得最后的数据能达到同步。考虑这么一个场景,教室里很多学生,每个学生都在说话,七嘴八舌的,一片混论。如果这些同学挨个起来发言,或者是是以一个组为单位来发言 ,就会显得井然有序,大家也都能听到他们在说什么。同理,多线程的情况下,如果不加以控制,多个线程一起对数据进行添加或者是修改,数据会异常混论,就像是七嘴八舌的声音一样。我们写程序的目的,无非就是为了处理数据,处理数据的输入和输出,如果最后得到的输出不受你的控制,这个程序还有什么用?

    互斥:有一些资源,比如:打印机。一次只能被一个线程访问,不允许多个线程同时访问,这种资源叫做临界资源。因此一个线程在访问这种资源的时候,其它线程不能访问,这就叫做互斥。【临界区:访问临界资源的那一段代码就叫做临界区。线程只有先进入临界区的才能访问到临界资源。】

    一般来说:要实现同步,就得先实现互斥。比如上面同步中所举的那个场景,我们要让学生挨个起来发言,就得先保证一个同学发言的时候,其它同学不要发言,这就是一种互斥

    操作系统实现同步的方式

    1. 使用互斥量(Mutex):采用互斥对象机制,只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个,所以可以保证公共资源不会被多个线程同时访问。比如Java中的synchronized关键词和各种Lock都是这种机制。

    2. 使用信号量(Semphares) :它允许同一时刻多个线程访问同一资源,但是需要控制同一时刻访问此资源的最大线程数量

    什么是信号量呢?可以看一下如下的例子

    考虑有两个函数up和down。uplock增 1,downlock减 1。当 lock 为 0 时,如果还在down这个函数里,那么会自旋。

    其中的cas是指CPU中的原子操作其伪代码形式可以这样表示:cas(&oldValue, expectedValue, targetValue)。比如我们要执行a++;假设a的初值为0,则可以这么写cas(&a, 0, 1),表示什么意思呢?先去存储a的地址空间中取出a的值,如果a的值是0,我就执行更新操作,使得a的值变为1,然后再写回去,否则不更新a的值。为什么执行一个a++都要这么麻烦呢?为的就是再多线程并发的情况下防止其它线程更改a的值

    up(&lock){
      while(!cas(&lock, lock, lock+1)) { }
    }
    
    down(&lock){
      while(!cas(&lock, lock, lock - 1) || lock == 0){}
    }
    

    考虑到多线程的情况下执行下面这个程序

    int lock = 2;
    down(&lock);
    // 临界区
    up(&lock);
    

    如果只有一个线程在临界区,那么lock等于 1,第 2 个线程还可以进入。 如果两个线程在临界区,第 3 个线程尝试down的时候,会陷入自旋锁。当然我们也可以用其他方式来替代自旋锁,比如让线程休眠。

    lock初始值为 1 的时候,这个模型就是实现互斥(mutex)。如果 lock 大于 1,那么就是同时允许多个线程进入临界区。这种方法,我们称为信号量(semaphore)

    1. 使用事件(Event) : 比如Wait/Notify:通过通知操作的方式来保持多线程同步。

    操作系统实现互斥的方法:

    • 软件实现互斥的方法
    1. 单标志法:设置一个公共的整形变量:turn。比如turn = 1则表示运行1这个进程进入临界区获得临界资源,其它线程则不允许进入。

    2. 双标志法先检查:每个线程在进入临界区访问临界资源之前,先查看临界资源是否正在被访问,若正在被访问,该线程需要进行等待;若临界资源没有被访问,该线程则进入临界区访问临界资源。我们可以设置一个标志数组flag[],flag[i] = true,则表示i这个线程在访问临界资源,flag[i] = false则表示该线程没有访问临界资源。当i线程检测到没有其它线程在访问临界资源时,则进入临界区,并将flag[i]设置为true。

      可能出现的问题:两个线程同时进入临界区。因为线程是先查看有没有其它线程在访问临界资源,然后在没有其它线程访问临界资源时再进入临界区访问临界资源,这两个步骤间是有一定的时间间隔的。考虑两个线程T1和T2。T1先检查有没有线程没有访问临界资源,检查结果发现,没有其它线程访问临界资源,于是准备进入临界区访问临界资源,T1正准备进入却还没有进入的时候。【发生这样原因除了是因为执行的过程中存在时间间隔,还有个原因就是可能会发生线程切换】T2也开始检查有没有线程访问临界资源,检查结果发现没有线程访问临界资源,于是T2也开始准备进入临界区访问临界资源。这下好了,T1和T2都检测到没有其它线程在访问临界资源,于是,都进入了临界区,很显然违背了互斥。

    3. 双标志法后检查:双标志法先检查是先检测临界资源的状态,然后再设置自己的标志。双标志后检查则相反:若一个线程准备访问临界资源,先将自己的标志位设置为true,然后再检查其它的线程的标志位,若检测到其它某个线程的标志位为true,则该线程等待,否则进入临界区。

      可能出现的问题:导致饥饿状态,没有一个线程能进入临界区。考虑两个线程T1和T2。T1准备访问临界资源,于是将自己的标志位设置为true。在T1还未开始检测其它线程的状态时,T2刚好也准备访问临界资源,于是T2也赶紧将自己的标志位设置为true。这下好了,这两个线程检查是否有其它线程访问临界资源的时候,都能检查到对方的标志位为true,这两个线程就这样僵持着,互相都无法访问临界资源

    4. Peterson(彼得森)算法:除了用一个flag[]数组来标志线程是否在访问临界资源或者是是否正准备访问临界资源,还设置了一个公共变量turn。

      伪代码如下:

      考虑两个线程i和j。
      在这里插入图片描述
      首先考虑3的那种情况。首先是i线程准备访问临界资源,于是将自己的标志位设置为true。然后呢,i线程假设此刻是j线程在访问临界区,于是将true设置为j。就在此时,j线程也准备访问临界资源,于是将自己的标志位设置为true,j线程也同样做了一个假设,假设此刻是i线程在访问临界区,于是把true的值设置为了i。最终,true的值变成了i。紧接着i线程开始在while循环中判断条件了,flag[j] == true成立,但是turn的值已经被j线程设置为了i,于是turn == j不成立,因此该循环条件不满足,i线程不执行该循环,i线程成功进入到临界区,避免了双标志法后检查产生的饥饿问题。

    • 硬件实现方法
    1. 中断屏蔽方法

      当一个线程获得了CPU的计算资源时,除非发生中断,否则,是不会发生线程切换的。我们的计算机能同时运行多个程序,并不是说这些程序同时获得了CPU的计算资源,而是CPU在不停地切换线程或者是进程,比如先执行A线程,执行了一会以后,然后对A线程发起中断请求,A线程被中断了,然后交出了运行权,接着发生线程切换。然后CPU又赶紧去执行B线程。B线程执行了一会有切换到其它线程。CPU的运算速度非常快,很短的时间内就能执行大量的代码,而线程切换的速度又非常快,所以给我们造成了一种程序在并行执行的现象。

      一个线程准备访问临界资源时,先屏蔽中断,屏蔽了中断就意味着这样该线程不会被中断,某种程度上就意味着该线程是独占CPU了,其它线程不会被得到执行,只有当该线程执行完毕,再开启中断以后,其它线程才可能得到执行。

    2. 硬件指令方法

      在计算机中,有一些指令是原子级的指令,也就是说指令在执行的过程中,不会发生线程切换而导致执行过程被中断。比如TAS(Test and Set),CAS(Compare and Swap)。回想我们用软件实现互斥的方法的时候,比如双标志检查法,不管是先检查还是后检查。都存在着被打断的问题。比如T1线程先检测,发现没有其它线程使用临界资源,正当T1准备进入还没有进入的时候,T2线程却来捣乱了,偷偷将一些标志位给发生了改变。由于T1已经检测过了,所以它以为一切正常,继续执行,殊不知有些内容已经被修改了。如果我们把T1检测是否有其它线程使用中断,如果没有,将自己的值设置为true,否则,继续轮询这些操作封装成一个原子过程,也就是T1在执行这些代码的时候,一气呵成的执行完毕,不允许其它线程插进来捣乱,就不会发生同时进入临界区或者是发生饥饿的现象了。

    参考
    《王道操作系统考研复习指导》

    展开全文
  • 9.9 积分湖南农业大学信息科学技术学院学生实验报告姓名: 年级专业班级— 日期2008年11月25日 成绩 操作系统实验名称进程同步和互斥实验类型课程名称【实验目的、要求】(1) 通过编写程序实现进程同步和互斥,掌握...
  • 匿名用户1级2018-09-01 回答线程之间的同步和互斥解决的问题是线程对共同资源进行访问。Posix有两种方式:信号量和互斥锁;信号量适用同时可用的资源为多个的情况;互斥锁适用于线程可用的资源只有一个的情况1、互斥...
  • 南昌大学操作系统实验报告二编程模拟进程间的同步和互斥1南 昌 大 学 实 验 报 告-( 2) 编 程 模 拟 进 程 间 的 同 步 互 斥学生姓名: 张皓然 学 号: 5501215001 专业班级: 本硕 151 实验类型: 验证 综合 ...
  • 进程同步和互斥

    2020-12-23 09:28:14
    在描述一个程序时,我们总是认为内部有一个“小人”,可以按程序所规定的步骤来执行程序。然而,在实际的系统中并不是这样。正如之前所讲,即使在程序中所描述的一条简单语句,也是由多条执行...互斥一组并发进程...
  • 3、熟悉在Linux环境下,利用lockf()系统调用完成临界区的互斥。内容及步骤:一、进程创建等待(1)进程等待对fork1程序进行修改,让父进程等待并检查子进程的退出状态。Wait.c子进程的结束状态返回后存于stat...
  • 同步和互斥是进程之间的两种常见关系,本文浅析之
  • 同步其实已经实现了互斥,所以同步是一种更为复杂的互斥互斥是一种特殊的同步。 所谓互斥,就是不同线程通过竞争进入临界区(共享的数据硬件资源),为了防止访问冲突,在有限的时间内只运行其中之一独占性的...
  • 虽然临界区同步速度很快,但却只能用来同步本进程内的线程 EnterCriticalSection()(定义在WinBase.h中)LeaveCriticalSection() CCriticalSection类Lock()UnLock() 互斥量 比临界区复杂。因为使用互斥不仅仅.....
  • 1.同步和互斥同步(直接制约关系):指的是完成同一任务的伙伴进程间,因需要协调它们的工作而等待、传递信息等。(z(进程1)m(进程2)需要完成买东西的任务,z把钱给了m,m才能去买东西。) 互斥(间接制约...
  • 用信号量解决同步和互斥问题的思路: 步骤: 1)信号量的设置 2)给信号量赋予初值(常用的互斥和同步信号量值的大小) 3)P,V操作安排的位置(其中P的顺序不能颠倒,V的顺序任意) 注意区分: 1)公用信号量,互斥时使用的信号...
  • 解决同步互斥问题的一些案例:一个吃水果问题。问题描述:桌上有一只盘子,每次只能放一个水果,爸爸专向盘中放苹果,妈妈专向盘中放桔子,儿子专等吃盘里的桔子,女儿专等吃盘里的苹果。只要盘子空,则爸爸或妈妈...
  • 操作系统实验报告-基于线程的编程技术一、实验目的要求二、实验方法与步骤(需求分析、算法设计思路、流程图等)三、实验原始纪录(源程序、数据结构等)四、实验结果及分析(计算过程与结果、数据曲线、图表等)...
  • 定义缓冲区大小为10,三个生产者线程,两个消费者线程,linux下利用互斥和状态变量实现生产者和消费者模型 c++代码 #include <pthread.h> #include <queue> #include <stdio.h> #include <...
  • 前言 Spring 5 于 2017 年 9 月发布了通用版本 (GA),它标志着自 2013 年 12 月以来第一个主要 Spring Framework 版本。它提供了一些人们期待已久的改进,还采用了一种全新的编程范例,以反应式...Throwthrows的区别
  • 互斥:当线程处于临界区并访问共享资源时,其他线程将不会访问相同的共享资源。 锁 :对资源加上一种保护机制,使得外部程序无法进行访问。对应的反向操作称之为解锁。 死锁:两个或以上的进程,进程之间相互...
  • 同步 为了共享资源与相互合作而在执行次序上的协调 互斥 ...简而言之就是互斥其实也是一种特殊的同步 同步是总体都是在协调,而互斥是在出现了问题之后才去考虑怎么协商进程使得最后不出现问题 ...
  • 二、同步和互斥问题 三、如何实现同步 四、如何实现互斥 笔记: 一、线程 1、什么是线程: (1)线程是轻量级的进程 (2)线程存在于进程内,不能独立存在 (3)线程参与CPU调度,进程是系统资源分配最小单位,线程...
  • 线程互斥 线程同步
  • 进程同步和互斥的联系 进程与进程之间存在两种制约关系,同步和互斥 同步是由于并发进程之间需要协调完成相同一个任务,而引起的联系,比如2个人一起去打球,要完成这个任务,要1个人先把球带过来,另外1个人才能打...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 175,892
精华内容 70,356
关键字:

同步和互斥