操作系统:进程同步

基本概念

在 Os 中引入进程后,虽然提高了资源的利用率和系统的吞吐量,但由于进程的异步性,也会给系统造成混乱,尤其是在他们争用临界资源时。例如,当多个进程去争用一台打印机时,有可能使多个进程的输出结果交织在一起,难于区分;而当多个进程去争用共享变量、表格、链表时,有可能致使数据处理出错。进程同步的主要任务是对多个相关进程在
执行次序上进行协调,以使并发执行的诸进程之间能有效地共享资源和相互合作,从而使程序的执行具有可再现性

  • 在资源共享的情况下:保证诸进程以互斥的方式访问临界资源必须以互斥方式访问的共享资源
  • 在相互合作的关系中:进程同步的主要任务是保证相互合作的诸进程在执行次序上协调,(有些教材把这种功能称做“协调”)。相互合作的进程可能同时存在资源共享的关系。

如何实现进程互斥,需要让进程以互斥的方式进入各自的临界区,先执行进入区的代码。

人为地加一段代码。

临界资源

必须以互斥方式访问的共享资源

counter的例子:在机器语言中实现两个进程给count加一的操作

register1 = count
register1 = register1 + 1
count = register1
register2 = count
register2 = register2 + 1
count = register2

但是如果是并发执行,可能会出现下面的情况

register1 = count
register2 = count
register1 = register1 + 1
register2 = register2 + 1
count = register1
count = register2

结果就不对了。

可见,counter应该作为临界资源。多个进程必须对其进行互斥访问

临界区

在每个进程中访问临界资源的那段代码称为临界区。如果能保证诸进程互斥地进入自己的临界区,便可实现诸进程对临界资源的互斥访问。

每个进程在进入临界区之前,应先对欲访问的临界资源进行检查,看它是否正被访问。如果此刻该临界资源未被访问,进程便可进入临界区对该资源进行访问,并设置它正被访问的标志;如果此刻该临界资源正被某进程访问,则本进程不能进入临界区。

必须在临界区前面增加一段用于进行上述检查的代码,把这段代码称为进入区(entry section)。相应地,在临界区后面也要加上一段称为退出区(exit section)的代码,用于将临界区正被访问的标志恢复为未被访问的标志。

同步机制应遵守的规则

  • 空闲让进。当无进程处于临界区时,表明临界资源处于空闲状态,应允许一个请求进入临界区的进程立即进入自己的临界区,以有效地利用临界资源。
  • 忙则等待。当已有进程进入临界区时,表明临界资源正在被访问,因而其它试图进入临界区的进程必须等待,以保证对临界资源的互斥访问。
  • 有限等待。对要求访问临界资源的进程,应保证在有限时间内能进入自己的临界区,以免陷入“死等”状态。
  • 让权等待。当进程不能进入自己的临界区时,应立即释放处理机,以免进程陷入“忙等”状态。饥饿状态。

信号量机制

用某种类型的变量来表示资源包括临界资源的使用状态

对不同的临界资源必须定义不同的信号量

整型信号量

跟临界资源对应的共享变量——信号量,来标记他的可用数量(临界值为1)来控制进程等待还是继续运行

整型信号量:整形变量共享(全局变量),用他的值来标记资源使用情况>0说明有可用资源;定义一个用于互斥的整形信号量,初始化为1

/*整型信号量的wait和signal操作
思路:为必须互斥访问的Cs定义一个互斥信号量mutex,初始值为1。
然后,将Cs放在 wait(mutex)和signal(mutex)之间,当Cs可访问时,wait(mutex)才能正常结束使进程进入Cs。
这是利用信号量来实现进程互斥
*/
var s:integer;    ;s为整型信号量
wait(s){            ;用于申请资源
     while s≤0 do no-op;
     s=s-1;
}
;cs
signal(s){          //用于释放资源
	 s=s+1;
}

wait(s)和 signal(s)是两个原子操作,因此,它们在执行时是不可中断的。亦即,当一个进程在修改某信号量时,没有其他进程可同时对该信号量进行修改。此外,在 wait 操作中,对 s 值的测试和做 s:=s-1 操作时都不可中断

信号量不是临界资源,但具有临界资源的特点,可以被多个进程互斥访问。对信号量的操作必须是原子性的。(禁止套娃)

为什么不能直接把临界区定义为原子操作?

内核中临界区代码很短,若直接在执行临界区代码前关中断,效率太低

记录型信号量

在整型信号量机制中的 wait 操作,只要是信号量 s≤0,就会不断地测试。因此,该机制并未遵循“让权等待”的准则,而是使进程处于“忙等”的状态。没有释放处理机,没有放弃对CPU的使用权。

在信号量机制中,除了需要一个用于代表资源数目的整型变量 value 外,还应增加一个进程链表指针 L,用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。

#记录型信号量的数据类型 类似结构体
Type  semaphore = record
     Value:integer               //资源数量
     L:list of process           //阻塞队列
end
/*记录型信号量的wait(s)和signal(s)操作*/
procedure wait(s)
    var s:semaphore
        begin
            s.value=s.value-1;
            if s.value<0 then  //说明原先的资源数为0
                block(s.L)
        end
procedure signal(s)
    var s:semaphore
        begin
            s.value=s.value+1;    //释放一个资源
            if s.value <= 0 then  //如果等待队列里有阻塞的进程,唤醒一个进程 
                wakeup(s.L)      //说明原先的资源数是小于0的,释放一个之后还等于0,意味着需要唤醒进程
        end

上述代码如何做到让权等待:

对它的每次 wait 操作,意味着进程请求一个单位的该类资源,使系统中可供分配的该类资源数减少一个,因此描述为 s.value:=s.value-1;当 s.value<0 时,表示该类资源已分配完毕,因此进程应调用 block 原语,进行自我阻塞放弃处理机,并插入到信号量链表s.L 中。

每次signal操作,如果释放一个资源,资源数还没有大于0,说明等待队列里有阻塞的进程。

经典同步问题

生产者消费者模型

生产者进程生产消息,并将消息提供给消费者进程消费。为使生产者进程和消费者进程能并发执行,在它们之间设置了一个具有n个缓冲区的缓冲池,生产者进程可以将它所生产的消息放入一个缓冲区中,消费者进程可以从一个缓冲区中取得一个消息消费。任意两个进程必须以互斥的方式访问公共缓冲池。当缓冲池空时,消费者进程必须等待;当缓冲池装满消息时,生产者进程必须等待

一共有两个进程,生产者进程和消费者进程,他们之间是互斥的关系。这道题的临界资源是缓冲区。必须先生产后消费。

信号量:

  • mutex用于实现对公共缓冲池的互斥,初值为1

  • empty空缓冲区的个数,n

  • full装有产品的缓冲区数,0

semaphore mutex=1;
semaphore empty=N;
semaphore full=0
//生产者
Producer:
 begin
	repeat
	produce an item in nextp;
	wait(empty);
	wait(mutex);//wait操作不能颠倒,如果有了临界区的访问权,空缓冲区数又为空,就会出现死锁
	buffer(in):=nextp;
	in:=(in+1)mod n
	signal(mutex);
	signal(full);
	until false;
end
//消费者
Consumer:
  begin
     repeat
     wait(full);//申请非空缓冲区
     wait(mutex);//申请公共缓冲池的访问权
     nextc:=buffer(out);//取出
     out:=(out+1)mod n;
     signal(mutex);
     signal(empty);
     consume item in nextc;//消费数据
     until false; 
end

这是实现相互合作的一个模板

读者写者问题

一个数据文件或记录,可被多个进程共享,我们把只要求读该文件的进程称为“Reader进程”,其他进程则称为“Writer 进程”。允许多个进程同时读一个共享对象,因为读操作不会使数据文件混乱。但不允许一个 Writer 进程和其他 Reader 进程或 Writer 进程同时访问共享对象,因为这种访问将会引起混乱。

设置信号量:

  • readcount对进入共享区的读进程计数
  • rmutex用于对多个进程共享的变量readcount互斥
  • wmutex 用于实现读/写互斥,写/写互斥

要实现写的时候,读写互斥比较简单

writer:
 begin
  repeat
  wait(wmutex);
  writing operation
  signal(wmutex);
 end

读进程:

read:
 begin:
  repeat
  wait(rmutex);
  if readcount == 0 then wait(wmutex);//让第一个读进程加锁
  readcount++
  signal(rmutex);
  reading file
  wait(rmutex);
  readcount--;
  if readcount == 0 then signal(wmutex);//让最后一个读进程解锁
  signal(rmutex);
 end

多个读进程要使readcount+1,所以需要将readcount加锁。

哲学家就餐

如果保证只有四个人拿筷子,就不会出现死锁

https://blog.csdn.net/speedme/article/details/17597373

repeat 
wait(mutex);//拿筷子的人的个数
wait(chopstick[i]);
wait(chopstick[(i+1)mod 5]);
eat;
signal(chopstick[i]);
signal(chopstick[(i+1)mod 5]);
signal(mutex);
think;
until false;

练习题

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

定义信号量,由于三个都是互斥的:

  • mutex三个进程的互斥信号量
  • odd(P_1)(P_3)同步信号量奇数的个数
  • even(P_1)(P2)同步信号量偶数的个数
  • empty同步信号量空缓冲区的个数
semaphore mutex=1;
semaphore odd=0,even=0;
semaphore empty=N;
main()
cobegin{
Process P1
while(True){
    number=produce();
	wait(empty);
    wait(mutex);
	put();
	signal(mutex);
	if number%2 == 0
	signal(even);
    else 
	signal(odd);
}
Process P2
while (true){
      wait(odd);
      wait(mutex);
	  getodd();
	  signal(mutex);
      signal(empty);
 	  countodd();
}
Process P3
while (true){
     wait(even);
     wait(mutex);
	 geteven();
     signal(mutex);
     signal(empty);
     counteven();
}
}coend

原文地址:https://www.cnblogs.com/smallocean/p/13094008.html