操作系统第二章作业

本文总阅读量次

第二章作业

版权声明

  • 版权声明：本文为AYXYJ原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
    本文链接：链接地址

  • 版权声明：本文为qq_33583069原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
    本文链接：链接地址

正文

  1. 利用信号量机制来解决任意前驱图所描述的并发执行的过程。（前趋图可自行设计）
1
2
3
4
5
6
7
8
9
10
11
var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;
begin
Cobegin
begin S1;signal(a);signal(b);end;
begin wait(a);s2; signal(c); signal(d); end;
begin wait(b);s3; signal(e); end;
begin wait(c);s4; signal(f); end;
begin wait(d);s5; signal(g); end;
begin wait(e);wait(f);wait(g);s6; end;
Coend
end
  1. 图书馆阅览室问题

    问题描述：假定阅览室最多可同时容纳100个人阅读，读者进入时，必须在阅览室门口的一个登记表上登记，内容包括姓名. 座号等，离开时要撤掉登记内容。用P、 V操作描述读者进程的同步算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var mutex,res:semaphore;
mutex:=1; res:=100;

Procedure reader(readerID);
{
	P(res);
	P(mutex);
	registrationInformation(readerID);
	V(mutex);
	reading();
	P(mutex);
	cancelRecord(readerID);
	V(mutex);
	V(res);
}
  1. 吃水果问题

    问题描述：桌上有一只盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，则爸爸或妈妈可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出四人之间的同步关系，并用PV操作实现四人正确活动的程序。

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
var mutex,empty,orange,apple:Semaphore;
mutex = 1; empty = 1; orange = 0; apple = 0;

Cobegin
{
　　 father                    //父亲进程
    {
　　　　while (true)
       {
　　　　　　　　   P(empty);
                P(mutex);
                向盘中放苹果;
                V(mutex);
                V(apple);
        }
    }
    mother                    //母亲进程
    {
　　　　while (true)
       {
　　　　　　　　　 P(empty); 
                P(mutex);
                向盘中放桔子;
                V(mutex);
                V(orange);
        }
    }
    daughter                  //女儿进程
    {
　　　　while (true)
       {
　　　　　　      P(apple);
                P(mutex);
                取盘中苹果;
                V(mutex);
                V(empty);
        }
    }
    son                            //儿子进程
    {
　　　　while (true)
       {
                P(orange);
                P(mutex);
                取盘中桔子;
                V(mutex);
                V(empty);
        }
    }
}
Coend
  1. 理发师问题(Dijkstra  1965)

    问题描述：一个理发店由一个有几张椅子的等候室和一个放有一张理发椅的理发室组成。若没有要理发的顾客，则理发师就去睡觉；若一顾客走进理发店且所有的椅子都被占用了，则该顾客就离开理发店；若理发师正在为人理发，则该顾客就找一张空椅子坐下等待；若理发师在睡觉，则顾客就唤醒他，设计一个协调理发师和顾客的程序。

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
var mutex,Wait,barbers:Semaphore;
var custNum:Int;
mutex = 1; Wait = 0; babers = 0;
custNum = 0;

Costumer()
{
　　while(true)
　　{
        P(mutex);
        if(custNum>0)
　　　　　{
            if(custNum<N)
　　　　　　　{
                V(mutex);
                CustNum++；
            }
　　　　　　　else 
　　　　　　　　{
                V(mutex);
                离开;
             }
　　　　　}
　　　　else
　　　　{
            V(mutex);
            V(barbers);
            理发;
            离开;
            P(mutex);        
            custNum--;      
            V(mutex);       
            V(wait);        
　　　　}
　　}
}

Barber()
{
　　while(true)
　　{
        P(mutex);            
        if(custNum ==0)    　　　　 
        {
            V(mutex);        
            P(barbers);        　　     
        }
　　　　else
　　　　{
            V(mutex);        
            理发;
　　　　}
　　}
}
  1. 司机—售票员问题

设公共汽车上，司机和售票员的活动分别是：

司机 售票员
启动车辆 上下乘客
正常行驶 关车门
到站停车 售票
开车门
上下乘客

在汽车不断到站，停车，行驶过程中，请描述这两个活动的同步关系。（售票员通过关车门控制司机启动车辆；司机通过到站停车控制售票员开车门）。

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
var door,stop:Semaphore;
door = 0; stop = 0;

void conductor()
{
	while(true)
	{
        上下乘客;
		关车门;
		signal(door);
		售票;
		wait(stop);
		开车门;
        上下乘客;
	}
}
void driver()
{
	while(true)
	{
		wait(door);
		正常行驶;
		signal(stop);
	}
}
  1. 对哲学进餐问题给出两种（第1、 3）解决死锁方法的程序描述。
  • 方案一

    至多允许有四位哲学家同时去拿左边的筷子，然后在允许拿右边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能同时释放他用过的两只筷子，从而使更多的哲学家能够进餐

  • 方案二

    仅当哲学家的左，右两只筷子均可用时，才允许他拿起筷子进餐

  • 方案三

    规定奇数号的哲学家先拿起他左边的筷子，然后再去拿他右边的筷子；而偶数号的哲学家则先拿起他右边的筷子，然后再去拿他左边的筷子。按此规定，将是1、2号哲学家竞争1号筷子，3、4号哲学家竞争3号筷子。即五个哲学家都竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一个哲学家能获得两支筷子而进餐

  1. 用P、V操作来实现receive 原语:( 参见教材 p80-81)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//R:接收进程名,b:欲接收信息所在内存地址
//s-b=n; s-m=0; b-mutex=1; m-mutex=1;
Receive(R,b)
Cobegin
Begin
    根据R找发送进程;
    如果没有找到
        return error;
    申请空缓冲区P(s-b);
    p(b-mutex);
    清空缓冲区;
    把消息从b处复制到空缓冲区;
    V(b-mutex);
    P(m-mutex);
    Receive程序查找其消息缓冲区，将第一个消息缓冲区中内容，消息，正文，长度，发送到接收区b;
    V(m-mutex);
    V(s-m);
End
Coend