进程同步概念

并发进程在执行次序上的协调，以达到有效的资源共享和相互合作，使程序执行有可再现性。

进程间的关系

资源共享关系：（进程间接制约）需互斥地访问临界资源。
相互合作关系：（进程直接制约）

临界资源：一次仅允许一个进程访问的资源，引起不可再现性是因为临界资源没有互斥访问
临界区：每个进程中访问临界资源的那段代码称为临界区，要保证进程互斥的进入自己的临界区，才能实现对临界资源互斥的访问

repeat
  entry section
  critical section
  exit section
until false

要访问临界资源首先要检查，是否可以访问，可以则进入自己的临界区。完成之后要退出..

信号量机制

记录型信号量

S.value记录系统中某资源的数目

procedure wait(s)
var s: semaphore
begin
s.value:=s.value –1;
if s.value <0 them block (S,L) //自己进入阻塞状态
end
procedure signal (S)
var s:semaphone
begin
s.value:=s.vaule+1
if s.value<=0 then wakeup(s.L)//唤醒阻塞状态的一个进程
end

AND型信号量，要么全分配，要么一个也不分配

死锁：在无外力作用下的一种僵持状态。当进程需要多个共享资源时，因为不同进程的并发执行，有可能造成死锁..

进程互斥

只要设置信号量mutex的初值为1即可

var mutex: semaphore:=1
    begin
    parbegin
        process1:begin
                repeat
                   wait(mutex);
                   critical setion
                   signal(mutex);
                   remainder section
                until false;
                end
process2: begin
               repeat
                  wait(mutex);
                   critical setion
                   signal(mutex);
                   remainder section
                until false;
                  end
parend

生产者-消费者问题

当然两个wait可以合并成swait这个AND信号量来替代。
mutex（1）：使诸进程互斥地访问n个缓冲区。
empty（n）full（0）：空、满缓冲区数量。

Var mutex,empty,full:semaphore:=1,n,0;  buffer:array[0,1,…,n-1] of item;
    in, out: integer: =0,0;
    begin
        parbegin
producer:  begin
repeat
            Produce an item in nextp;
            wait(empty);//还有空位才进入下面的临界区
            wait(mutex);//互斥的进入缓冲区
            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);
              Consumer the item in nextc;
Until false;
end
parend

哲学家进餐问题

以下这段代码有两个问题：首先，可能造成死锁，5个人分别拿到了一只叉子。其次，wait和signal没有成对嵌套。

Var chopstick: array[0, …, 4] of semaphore;
Repeat
    wait(chopstick[i]);
    wait(chopstick[(i+1)mod 5]);
    …
   eat
    …
   signal(chopstick[i]);
   signal(chopstick[(i+1)mod 5]);
    …
   think;
Until false

改进的方法：增加一个资源信号量room，只允许4个人同时去申请叉子，那么肯定有至少一个人可以拿到两个叉子。

Var chopstick: array[0, …, 4] of semaphore 1;
      room：4
Repeat
    wait(room);
    wait(chopstick[i]);
    wait(chopstick[(i+1)mod 5]);
    …
   eat
    …
   signal(chopstick[(i+1)mod 5]);
   signal(chopstick[i]);
   signal(room);
    …
   think;
Until false

改进方法：用AND信号量

读者写者问题