计算机操作系统部分知识点总结2

2024-01-30 22:49:04

信号量解决进程同步问题

1.前趋图

前趋图是一个有向无循环图，记为DAG（Directed Acyclic Graph），用于描述进程之间执行的前后关系。

图中的每个结点可用于描述一个程序段或进程，乃至一个语句；结点间的有向边‘→’则用于表示两个结点之间存在的偏序或前趋关系。

图示含义：A必须在B开始前结束

2.前趋图练习

例题：假设某个程序段包含如下语句，画出它前趋图。

int a,b,c,d,e,f;

int t1,t2,t3,t4,t5;

s1: t1=a+b;

s2: t2=c+d;

s3: t3=e/f;

s4: t4=t1*t2;

s5: t5=t4-t3;

3.程序的两种执行方式的特征对比

4.进程间状态的转换

5.进程同步的主要任务

对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

6.进程间的两种制约关系

①间接相互制约

源于资源共享，即对资源的竞争关系，进程需要互斥访问同一资源。

②直接相互制约

源于进程合作，即协作关系，某些进程为完成同一任务需要分工协作。

7.临界资源和临界区

临界资源(Critical Resource):只允许进程互斥访问的资源。例如，打印机，共享变量…

临界区(Critical section)：进程中访问临界资源的代码段。

若能保证各进程互斥地进入自己的临界区，就可实现各进程对临界资源的互斥访问。

8.信号量机制类型

①整型信号量

定义S为一个用于表示资源数目的整型量，除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。这两个操作也被称为P、V操作。

wait(S) {

while (S<=0); //do no-op，“忙等”

S--; }

signal(S) { S++; }

存在问题: 未遵循“让权等待”的准则

②记录型信号量

在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表指针L,用于链接上述的所有等待进程。

因采用了记录型数据结构而得名：

　　 typedef struct {

int value;

struct process_control_block *list;

}semaphore;

wait (semaphore *S) {

S->value--;

if (S->value <0) block(S->list); }

signal (semaphore *S) {

S->value++;

if (S->value <=0) wakeup(S->list); }

③AND型信号量

基本思想:

将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其他所有可能为之分配的资源，也不分配给它。亦即，对若干个临界资源的分配，采取了原子操作方式：要么全部分配给进程，要么一个也不分配。

AND型信号量wait原语为Swait, 定义如下：

Swait (S1, S2, …, Sn) {

if (Si >=1 && … && Sn >= 1) {

//进程所需各项资源都能满足时

for (i = 1; i <= n; ++i) Si--;

}

else { //某些资源不够时的处理

把进程放入第一个小于1的信号量Sj的等待队列Sj.queue，并将程序计数器指向Swait的开始处；

}

AND型信号量集signal原语为Ssignal, 其定义如下：

Ssignal (S1, S2, …, Sn) {

for (i = 1; i <= n; ++i)

Si=Si++； //释放占用的资源；

把等待Si的所有进程从等待队列移至就绪队列；

}

④信号量集

信号量集机制的适用范围更广，不仅能处理前述信号量机制能处理的问题，还能处理以下情况：

1）需要一次性分配多个同类资源时

2）当资源数量低于某一下限值时，就不予以分配

对AND型信号量加以扩充，即得到更为一般化的信号量集机制：

Swait (S₁, t₁, d₁, …, S_n, t_n, d_n);

Ssignal (S₁, d₁, …, S_n, d_n);

//t_i：分配下限值，如果S_i<t_i, 不予分配

//d_i：资源需求值，分配时S_i-=d_i; 释放时S_i+=d_i;

9.经典进程同步问题

1.生产者消费者问题

问题描述：

生产者-消费者问题是对相互合作的进程之间同步问题的一种抽象，例如，在输入和计算进程间，计算进程是消费者；而在计算和打印进程间，计算进程是生产者。

int in=0, out=0;
item buffer[n];
semaphore mutex=1, empty=n, full=0;
void producer() {
	do { 
		produce an item in nextp;             
  		…
wait (empty);                                 
wait (mutex); 	
buffer(in):=nextp;	
in:=(in+1) mod n;                         
signal(mutex);                               
signal (full);                                   
	} while(TRUE);                                   
}
void consumer() {      
	do {
wait(full);
wait(mutex);
nextc:=buffer(out);
out:=(out+1) mod n;
signal(mutex);
signal(empty);
consume the item in nextc;
	}while(TRUE)
}
void main() {
	cobegin
		producer(); consumer();
	coend
}

2.哲学家进餐问题

问题描述：假设有五个哲学家，他们花费一生的时光思考和吃饭。这些哲学家公用一个圆桌，每个哲学家都有一把椅子。在桌*有一碗米饭。每个哲学家面前有一只空盘子，每两人之间放一根筷子。当一个哲学家思考时，他与其他同事不交互；当哲学家感到饥饿，就会试图拿起与他最近的两支筷子（他与邻近左、右两人之间的筷子）。当一个饥饿的哲学家拿到两支筷子时才能进餐。当吃完后，他会放下两支筷子，并再次开始思考。

解法1

semaphore chopstick[5] = {1,1,1,1,1};
semaphore  room =4;
int i;
void philosopher (int i);{
     while ⑴ {       
          think( );
          wait (room);
          wait (chopstick[i]);
          wait (chopstick [(i+l) %5]);
          eat( );
          signal (chopstick [(i+l) % 5]);
          signal (chopstick[i]);
          signal  (room);
	}
}

解法2

设chopstick[5]为5 个信号量，初值均为1
Philosopher（i）
while (1)  {
    思考；
    Swait( chopstick[i], chopstick[(i+1) % 5] )；
    进食；
    Ssignal( chopstick[i], chopstick[(i+1) % 5] )；
}

解法3

semaphore chopstick[5] = {1,1,1,1,1};
int i;
void philosopher (int i);{
     while ⑴ {  
        think( );
        if (i mod 2 ==1) {	//奇数号的哲学家必须首先拿左边的筷子
     wait(chopstick[i]);
             wait(chopstick [(i+l) %5]);
        }
        else {	//偶数号的哲学家必须首先拿右边的筷子
wait (chopstick [(i+l)% 5]);
wait (chopstick[i]);
        }
       eat( );
       signal(chopstick [(i+l) % 5]);
       signal(chopstick[i]);
}
}

3.读者写者问题

问题描述：一组读者与一组写者循环访问共享的同一个数据对象。规定：多个读者可以同时读这个数据对象，但决不允许多个写者同时对它进行写操作，也不允许读者、写者同时访问它。如何对读者、写者编程？

读者  Readers:                                   
   begin
     repeat                                    
       wait(rmutex);                                       
       if readcount=0 then wait(wmutex);                           
         readcount:=readcount+1;                               
       signal(rmutex);
           …
       执行读操作;
           …
        wait(rmutex);
        readcount:=readcount-1;
        if readcount=0 then singal(wmutex);
        singal(rmutex);
     until false;
   end
写者  Writers：
 begin
   repeat
          wait(wmutex);
          执行写操作;
          singal(wmutex);
    until false;
end

10.独木桥问题

问题描述：一条小河上有一座独木桥，规定每次只允许一人过桥。如果把每个过桥者看作一个进程，为保证安全，请用信号量操作实现正确管理。

解：为临界资源独木桥设置信号量s，初值为1

begin                                                     

semaphore s=1;                                                                          

cobegin                                                       

begin

wait(s);                                                        

过桥；

signal(s)；

end 

coend    

end

独木桥问题拓展：

问题描述：若独木桥任何时刻最多允许2人同方向过桥，如何用信号量实现同步？

int count1=count2=0; 
semaphore m0=m1=m2=1; 
semaphore room=2；
方向1的过桥者：                                              
begin 
wait(m1);
if(count1==0) wait(m0);
count1++;
signal(m1);
wait(room);                                                         
过桥；
signal(room)；
wait(m1);
count1--;
if(count1==0) signal(m0);
signal(m1);
end	
方向2的过桥者：                                              
begin 
wait(m2);
if(count2==0) wait(m0);
count2++;
signal(m2);
wait(room);                                                         
过桥；
signal(room)；
wait(m2);
count2--;
if(count2==0) signal(m0);
signal(m2);
end

进程同步类型的问题很多，具体请参照网上的其他问题。

码农公寓