操作系统进程同步

进程同步

两种制约关系

间接相互制约关系：同处于一个系统中的进程，必然共享着某种系统资源。所谓间接相互制约即源于这种资源共享。例如，有两个进程A和B，如果在A进程提出打印请求时，系统已将唯一的一台打印机分配给了进程B，则此时进程A只能阻塞；一旦进程B将打印机释放，才能使A进程由阻塞改为就绪状态。（进程互斥）
（就是两个进程共同竞争一个资源，当A释放了共享资源后B才能继续进行）

直接相互制约关系：这种制约源于进程间的合作。例如C进程因得不到A进程的数据而阻塞。（进程同步）
（两者是某种顺序关系，A做完B才能继续）

临界资源

临界资源：一次仅允许一个进程使用的资源。
许多物理设备，如输入机、打印机、磁带机等都具有这种性质。
软件资源，如公用变量、数据、表格、队列等也都具有这一特点。
诸进程之间应通过互斥方式，实现对临界资源的共享。

临界区

不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它进行访问。
临界区：每个进程中访问临界资源的那段代码称为临界区。
每个进程进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问。如果此刻该临界资源未被访问，进程便可进入临界区对该资源进行访问，并设置它正被访问的标志；如果此刻该临界资源正被某进程访问，则本进程不能进入临界区。

同步机制的四个准则

1. 空闲让进：当无进程处于临界区时，应允许一个请求进入临界区的进程进入临界区；
2. 忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待；
3. 有限等待：对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态；
4. 让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。

信号量机制

整型信号量

思想：定义一个整型量S，除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。

wait(S): {
				while S≤0;    /*do no-op*/
                 S--;
               }
signal(S): {
                    S++;
                  }

缺点：当s<=0时，会进入死循环，一直占用CPU，浪费资源。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。

记录型信号量

思想：用整型变量value代表资源的数目。用进程链表L来链接等待访问临界资源的进程。

记录型信号量的定义：
  typedef struct {
                     int value;
                      struct process_control_block *list;
                           }semphore;

临界资源阻塞队列：

记录型信号量的P、V操作

wait(semaphare *S)
  {
    S->value--;
    if (S->value<0)  block(S->list);
   }
signal(semphore *S)
 {
     S->value++;
     if (S->value≤0) then wakeup(S->list);
  }

说明

S->value的初值表示系统中某类资源的数目，因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，使系统中可供分配的资源数减少一个，因此S->value–；
每次执行完wait操作后，若S->value<0时，说明该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S->list中。此时S->value的绝对值表示在该信号量链表中已阻塞进程的数目。
每次执行signal操作表示资源数目加1，若加1后仍有S->value≤0时，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S->list链表中的第一个等待进程唤醒。
若S->value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。

AND型信号量

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

Swait(S1,S2,…,Sn)
{   while (TRUE)  
    { 
    if (S1≥1&&… &&Sn≥1){
     for (i=1;i<=n;i++)
          Si--;
     break;
      }
else {
     place the process in the waiting queue associated with the first Si found with Si<1, and set the program count of this process to the beginning of Swait operation
     将进程放入第一个Si<ti的等待队列中,并且将程序指针指向该进程的Swait操作开始处；
       }
   }
}

Ssginal(S1,S2,…,Sn)
  while (TRUE){
 for(i:=1;i<=n;i++){ 
    Si++;
    remove all the process waiting in the queue associated with Si into the ready queue
    将与Si 相关的等待队列中的进程移到就绪队列
   }
  }
}

信号量集

思想：若进程一次需要申请多类临界资源，则在进行临界资源分配时，先测试各类临界资源是否大于其下限值。若低于下限值，则不予分配。
以下的程序中，S为信号量，d为需求值，t为下限值。

Swait(S1,t1,d1,…,Sn,tn,dn)
   while (TRUE){
 if (S1≥t1 && … && Sn≥tn )
        for (i=1;i<=n;i++)   Si:=Si-di;
        break;
}         
else { 
        Place the executing process in the waiting queue of the first Si with Si<ti and set its program counter to the beginning of the Swait Operation.
        将正在执行的进程移入第一个Si<ti的等待队列中，并将程序指针指向该进程中Swait操作开始处
   }
 }
}

Ssignal(Si,di,…,Sn,dn)
{ while (TRUE)
    {   
       for (i=1;i<=n;i++) {
        Si:=Si+di;
        Remove all the process waiting in the queue associated with Si into the ready queue
        将与Si相关的等待队列中的所有进程移到就绪队列
     }
   }
}

信号量机制的应用

实现进程互斥

为使得多个进程能互斥地访问某临界资源，只需为该资源设置一互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。

实现前趋

技巧：后进程实现P（wait）操作，前进程实现V（signal）操作。

大家觉得有帮助的请点个赞啊????