操作系统原理作业（十）：ex01.pv作业

发表于   |   分类于   |     |   阅读次数   |  

题目1

1、有一个仓库，可以存放 A 和 B 两种产品，仓库的存储空间足够大，但要求：
（1）一次只能存入一种产品（A 或 B）；
（2）-N < (A 产品数量 - B 产品数量) < M。
其中， N 和 M 是正整数。试用“存放 A”和“存放 B”以及 P、 V 操作描述产品 A 与产品 B 的入库过程。
解答：
由题中的表达式可得：
B产品数量 - A产品数量 < N
A产品数量 - B产品数量 < M。
则此题意为：
（1）若只放人A产品，而不放入B产品，则A产品最多可放M-1次便被阻塞，即A进程每操作一次就应当将计数器减1（计数器初值为M-1），当计数器值为0时，进程A被阻塞；每当放入一个B产品，则可令A产品的计数器增加1，表明A产品可以多一次放入产品的机会；
（2）同理，若只放人B产品，而不放入A产品，则B产品最多可放N-1次便被阻塞，即A进程每操作一次就应当将计数器减1（计数器初值为N-1）。当计数器值为0时，进程B被阻塞；每当放人一个A产品，则可令B产品的计数器增加1，表明B产品可以多一次放入产品的机会。
由此可见，该问题是一个同步控制问题。实现其入库过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef int semaphore;  
semaphore mutex = 1;   //互斥信号量
semaphore a = M - 1；  //存放A的资源信号量，初值为M-1
semaphore b = N - 1;   //存放B的资源信号量，初值为N-1
PA:
while (true)
{
    P(&a);
    P(&mutex);
    A 入库；
    V(&mutex);
    V(&b);
}
PB:
while (true)
{
    P(&b);
    P(&mutex);
    B 入库；
    V(&mutex);
    V(&a);
}

题目2

2、桌子上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子放苹果（ apple），妈妈专向盘子中放桔子（ orange）；两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子中的苹果。请用 P、 V 操作来实现爸爸、妈妈、儿子、女儿之间的
同步与互斥关系。
解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
typedef int semaphore;
semaphore mutex = 1;    //互斥信号量, 其初值为1
semaphore empty = 2;    //记录允许向盘子中放入水果的个数，初值为2
semaphore orange = 0;   //盘子中已放入的苹果的个数，初值为0
semaphore apple = 0;    //盘子中已放入的桔子的个数，初值为0
main() 
{
    Cobegin
    {
        father      //父亲进程
        {
            while (true)
            {
                P(empty);     //减少盘中可放入的水果数
                P(mutex);     //申请向盘中取、放水果
                向盘中放苹果;
                V(mutex);     //允许向盘中取、放水果
                V(apple);     //递增盘中的苹果数
            }
        }
        mother     //母亲进程
        {
            while (true) 
            {
                P(empty);     //减少盘中可放入的水果数
                P(mutex);     //申请向盘中取、放水果
                向盘中放桔子;
                V(mutex);     //允许向盘中取、放水果
                V(orange);    //递增盘中的桔子数
            }
        }
        daughteri（i = 1, 2）    //两女儿进程
        {
            while (true) 
            {
                P(apple);       //减少盘中苹果数
                P(mutex);      //申请向盘中取、放水果
                取盘中苹果;
                V(mutex);      //允许向盘中取、放水果
                V(empty);      //递增盘中可放入的水果数
            }
        }
        sonj（j = 1, 2）         //两儿子进程
        {
            while (true) 
            {
                P(orange);      //减少盘中桔子数
                P(mutex);      //申请向盘中取、放水果
                取盘中桔子;
                V(mutex);      //允许向盘中取、放水果
                V(empty);      //递增盘中可放入的水果数
            }
        }
    }
    Coend
}

题目3

3、有一个理发师，一把理发椅和 N 把供等候理发的顾客坐的椅子。如果没有顾客，则理发师便在理发师椅子上睡觉；当一个顾客到来时，必须唤醒理发师进行理发；如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，他就坐下来等，如果没有空椅子，他就离开。为理发师和顾客各编一段程序（伪代码）描述他们的行为，要求不能带有竞争条件。
解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
typedef int semaphore;
semaphore mutex = 1;     //互斥信号量，初值为1.
semaphore wait = 0;      //等待服务的顾客数
semaphore barbers = 0;   //等待顾客的理发师数
int custNum = 0;         //等待的顾客(还没理发的)
Costumer()
{
    while (true)
    {
        P(mutex);              //申请理发
        if (custNum > 0)
        {
            if (custNum < N)    //若等待人数小于N
            {
                V(mutex);      //释放进程等待
                CustNum++;   //增加等待人数
            }
            else               //若等待人数超过N
            {
                V(mutex);      //释放进程等待
                离开;
            }
        }
        else                   //若目前无人等待
        {
            V(mutex);          //释放进程等待
            V(barbers);         //如果必要的话，唤醒理发师
            理发;
            离开;
            P(mutex);          //要求进程等待
            custNum--;        //顾客人数减1
            V(mutex);          //释放进程等待
            V(wait);            //等待人数减1
        }
    }
}
Barber() 
{
    while (true)
    {
        P(mutex);              //要求进程等待
        if (custNum == 0)       //目前无顾客
        {
            V(mutex);          //释放进程等待
            P(barbers);         //理发师睡觉　　
        }
        else
        {
            V(mutex);          //释放进程等待
            理发;
        }
    }
}

题目4

4、吸烟者问题。三个吸烟者在一间房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴。供应者有丰富的货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。供应者将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西（随机地）在桌面上，然后唤醒另一个吸烟者。试为吸烟者和供应者编写程序解决问题。
解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
typedef int semaphore;
semaphore S = 1;       //供应者
semaphore S1 = 0, S2 = 0, S3 = 0;    //三个吸烟者
bool flag1 = true, flag2 = true, flag3 = true;  //三种吸烟原料
Apply()           //供应者
{
    while (true)
    {
        P(S);
        取两样香烟原料放桌上,由flagi标记;
        if (flag2 && flag3)        //供纸和火柴
            V(S1);              //唤醒吸烟者一
        else if (flag1 && flag3)    //供烟草和火柴
            V(S2);              //唤醒吸烟者二
        else                    //供烟草和纸
            V(S3);              //唤醒吸烟者三
    }
}
Smoker1()           //吸烟者一
{
    while (true)
    {
        P(S1);
        取原料;
        做香烟;
        V(S);        //唤醒供应者
        吸香烟;
    }
}
Smoker2()           //吸烟者二
{
    while (true)
    {
        P(S2);
        取原料;
        做香烟;
        V(S);        //唤醒供应者
        吸香烟;
    }
}
Smoker3()           //吸烟者三
{
    while (true)
    {
        P(S3);
        取原料;
        做香烟;
        V(S);        //唤醒供应者
        吸香烟;
    }
}

题目5

5、面包师问题。面包师有很多面包和蛋糕，由 n 个销售人员销售。每个顾客进店后先取一个号，并且等着叫号。当一个销售人员空闲下来，就叫下一个号。请分别编写销售人员和顾客进程的程序。
解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
typedef int semaphore;
semaphore buyer = 0;           //顾客人数
semaphore seller = n;          //销售人员数
semaphore mutex_s = 1;         //用于销售人员的互斥信号量
semaphore mutex_b = 1;         //用于顾客的互斥信号量
int count_s = 0;               //记录取号的值
int count_b = 0;               //记录叫号的值
void Buy()                     //顾客进程
{
    进店;
    P(mutex_b);        //取号
    count_b++;
    V(mutex_b);
    V(buyer);
    P(seller);         //等待叫号
    买面包;
    离开;
}
void Sell()
{
    while (true) 
    {
        P(buyer);
        P(mutex_s);     //叫号
        count_s++;
        叫编号为count_s的顾客;
        V(mutex_s);
        V(seller);
    }
}

题目6

6、桌上有一空盘，运行存放一只水果，爸爸可向盘中放苹果，也可放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘中空时一次只能放一个水果供吃者取用，用P、V原语实现爸爸儿子和女儿3个并发进程的同步。
解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
typedef int semaphore;
semaphore S = 1;      //S 表示盘子是否为空；
semaphore Sa = 0;     //Sa 表示盘中是否有苹果；
semaphore Sb = 0;     //Sb 表示盘中是否有桔子；
Father()              //父亲进程
{
    while (true)
    {
        P(S);
        将水果放入盘中;
        if (放入的是桔子)
            V(Sb);
        else
            V(Sa);
    }
}
Son()                  //儿子进程
{
    while (true)
    {
        P(Sb);
        从盘中取出桔子;
        V(S);
        吃桔子;
    }
}
Daughter()             //女儿进程
{
    while (true)
    {
        P(Sa);
        从盘中取出苹果;
        V(S);
        吃苹果;
    }
}

题目7

7、写者优先的读者－－写者问题。读者-写者问题为数据库访问建立了一个模型。例如,一个系统,其中有许多竞争的进程试图读写其中的数据,多个进程同时读是可以接受的,但如果一个进程正在更新数据库,则所有的其他进程都不能访问数据库，即使读操作也不行。写者优先是指当一个写者到达时，将阻止其后面的读者进入数据库，直到其离开为止。
解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
typedef int semaphore;
semaphore mut1 = 1, mut2 = 1, wmutex = 1, fmutex = 1;   //互斥信号量
int rcount = 0, wcount = 0;     //读写者人数
Writer()                        //写者进程
{
    while (true)
    {
        P(mut1);
        wcount = wcount + 1;
        if (wcount == 1)
            P(fmutex);          //如有读者，则写者阻塞在此处
        V(mut1);
        P(wmutex);
        写;
        V(wmutex);
        P(mut1);
        wcount = wcount - 1;
        if (wcount == 0)
            V(fmutex);
        V(mut1);
    }
}
Reader()                        //读者进程
{
    while (true)
    {
        P(mut2);
        rcount = rcount + 1;
        if (rcount == 1)
            P(fmutex);
        V(mut2);
        读;
        P(mut2);
        rcount = rcount - 1;
        if (rcount == 0)
            V(fmutex);
        V(mut2);
    }
}

题目8

8、在天津大学与南开大学之间有一条弯曲的小路，这条路上每次每个方向上只允许一辆自行车通过。但其中有一个小的安全岛 M，同时允许两辆自行车停留，可供两辆自行车已从两端进入小路的情况下错车使用。如图所示。

下面的算法可以使来往的自行车均可顺利通过。其中使用了4个信号量，T代表天大路口资源，S代表南开路口资源，L代表从天大到安全岛一段路的资源，K 代表从南开到安全岛一段路的资源。程序如下，请在空白位置处填写适当的 PV 操作语句，每处空白可能包含若干个 PV 操作语句。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
begin
    t:=1;s:=1;l:=1;k:=1;
    cobegin
    从天大到南开的进程
        begin
            ______(1)______
            通过 L 路段;
            进入安全岛 M；
            ______(2)______
            通过 K 路段
            ______(3)______
        end
    从南开到天大的进程
        begin
            略，与“从天大到南开的进程”相反。
        end
    coend
end

解答：
(1) P(t); P(l);
(2) V(l); P(k);
(3) V(k); V(t);

题目9

9、三个进程 P1、P2、P3 互斥使用一个包含N(N>0)个单元的缓冲区。P1每次用 produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用 getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用 geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动,并说明所定义信号量的含义。要求用伪代码描述。
解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
P1()
{
    while (true)
    {
        X = produce();      //生成一个数
        P(empty);           //是否有空单元格
        P(mutex);           //进入临界区
        Put();
        if (X % 2 == 0)
            V(s2);          //如果是偶数，向P3发出信号
        else
            V(s1);          //如果是奇数，向P2发出信号
        V(mutex);           //离开临界区，释放互斥信号量
    }
}
P2()
{
    while (true)
    {
        P(s1);              //收到P1发送来的信号，已产生奇数
        P(mutex);           //进入临界区
        getodd();
        countodd():=countodd() + 1;
        V(mutex);
        V(empty);           //离开临界区，释放互斥信号量
    }
}
P3()
{
    while (true)
    {
        P(s2);              //收到P1发送来的信号，已产生偶数
        P(mutex);           //进入临界区
        geteven();
        counteven() := counteven() + 1;
        V(mutex);
        V(empty);           //离开临界区，释放互斥信号量
    }
}

坚持原创技术分享，您的支持将鼓励我继续创作！

热评文章