操作系统 第二章作业本(含答案).doc

第二章作业

第一次作业：

1. 进程有哪三种基本状态？进程在三种基本状态之间转换的典型原因是什么？

答： 三种基本状态：就绪状态、执行状态、阻塞状态。
（1）就绪状态→执行状态：进程分配到CPU资源（进程调度）；
（2）执行状态→就绪状态：时间片用完
（3）执行状态→阻塞状态：I/O请求
（4）阻塞状态→就绪状态：I/O完成

2. 在Linux系统中运行下面程序，最多可产生多少个进程？画出进程家族树。
main()
{
fork();
fork();
fork();
}

答：最多可以产生7个进程。
其家族树为：

3. 试从动态性、并发性和独立性上比较进程和程序。
答：
1) 动态性是进程最基本的特性，可表现为由创建而产生，由调度而执行，因得不到资源而暂停执行，以及由撤销而消亡，因而进程由一定的生命期；而程序只是一组有序指令的集合，并存放于某种介质上，其本身并不具有运动的含义，因而是静态的； 
2) 并发性是进程的重要特征，同时也是OS的重要特征。引入进程的目的正是为了使其程序能和其它建立了进程的程序并发执行，而程序本身（没有建立PCB）是不能并发执行的；
3)  独立性是指进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。凡未建立PCB的程序，都不能作为一个独立的单位来运行。

4. 分析下列代码的功能：

答：
sleep_on实现进程的睡眠过程；
wake_up实现进程的唤醒过程。

第二次作业：

1. 同步机制应该遵循哪些基本准则？你认为整型信号量机制遵循了同步机制的哪些基本准则？
答：
同步机制应遵循四个基本准则： 
a. 空闲让进：当无进程处于临界区时，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。 
b. 忙则等待：当已有进程进入临界区时，其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。 
c. 有限等待：对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。
d. 让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。 
整型信号量机制使进程处于“忙等”状态，并未遵循“让权等待”的准则；而记录型信号量机制则完全遵循了同步机构的四条准则。

2. 使用信号量实现下面的前趋图。

答：
Var a,b,c,d,e,f,g,h:semaphore:=0,0,0,0,0,0,0,0;
begin
parbegin
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);s6; signal(h); end;
begin wait(f);wait(g);wait(h);s6; end;
parend
end

3. 我们为某临界资源设置一把锁W，当W=1时表示关锁；当W=0时表示锁已打开，试写出开锁和关锁原语，并利用它们去实现互斥。
答：整型信号量：
lock(W): while W=1 do no-op
W:=1;
unlock(W): W:=0;
记录型信号量：
lock(W): W:=W+1;
if(W>1) then block(W, L)
unlock(W): W:=W-1;
if(W>0) then wakeup(W, L)
例子：
Var W:semaphore:=0；
begin
repeat
lock(W);
critical section
unlock(W);
remainder section
until false;
end

4. 桌子上有一个空盘子，允许存放一只水果，爸爸可以向盘中放苹果，妈妈向盘子中放橘子，女儿专门吃盘子中的苹果，儿子专门吃盘子中的橘子。规定当盘子空的时候一次只能放一只水果，请用信号量实现他们之间的同步与互斥关系。
答：
S, S1, S2 :semaphore=1,0,0;
Process Father:
Begin:
L1: P(S);
Put Apple;
V(S1)；
End；
Process Mother:
Begin:
L2: P(S);
Put Orange;
V(S2)；
End；
Process Son:
Begin:
L3: P(S2);
Get Orange;
V(S)；
End；
Process Daughter:
Begin:
L4: P(S1);
Get Apple;
V(S)；
End；
5. 用信号量解决“独木桥”问题：同一个方向行人可连续过桥，当某一方向有人过桥时，另一个方向的行人必须等待；当某一方向无人过桥时，另外方向的行人可以过桥。
（1）本问题中有哪些同步或互斥关系？
（2）给出两个方向任一行人通过该独木桥的同步算法。

答：
将独木桥的两个方向分别标记为A和B；并用整形变量countA和countB分别表示A、B方向上已在独木桥上的行人数，初值为0；再设置三个初值都1的互斥信号量：SA用来实现对countA的互斥访问，SB用来实现对countB的互斥访问，mutex用来实现两个方向的行人对独木桥的互斥使用。则具体描述如下： 
Var SA,SB,mutex:semaphore:=1,1,1;    
CountA,countB:integer:=0,0:  
begin 
parbegin  
process A:
begin  
wait(SA); 
if(countA=0) then wait(mutex); countA:=countA+1; signal(SA); 过独木桥； wait(SA); 
    countA:=countA-1; 
    if (countA=0) then signal(mutex); signa(SA); 
                  end 
process B: 
begin  
wait(SB); 
if(countB=0) then wait(mutex); countB:=countB+1; 
signal(SB); 
过独木桥； wait(SB); 
    countB:=countB-1; 
    if (countB=0) then signal(mutex); 
signa(SB); 
end 
parend 
end

6. （选做）设有两个生产者进程A、B和一个销售者进程C，他们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售者销售；销售者每次循环从仓库中取出一个产品销售。如果不允许同时入库，也不允许边入库边出库，而且要求生产A产品和B产品的件数满足以下关系：
-n≤A的件数－B的件数≤m
其中n，m是正整数，但对仓库中A产品和B产品的件数无上述要求，请用信号量机制写出A，B，C三个进程的工作流程。
7. （选做）简述linux的管道通信机制、共享存储器通信机制、消息缓冲通信机制。