HICSC
005 进程管理:进程同步与信号量的基本概念

1、什么是进程同步?

进程同步是指在系统中对多个进程间的关系进行协调,它是对竞争资源访问的一种处理方式,用以避免一个进程长期占用资源。例如,当多个进程去争用一台打印设备时,有可能使多个进程的输出结果交织在一起,难于区分,这时,就需要进程同步机制来协调多个进程对打印设备的访问:可以先让一个进程打印完成后再让另外一个进程使用,即互斥的访问共享资源。

前面也说到,进程同步机制是对多个进程间的关系进行协调,那进程间到底存在哪些关系:

说完关系,接着来说说资源。进程可以共享系统中各种资源,很多资源一次只能供一个进程使用,我们把这样的资源称为临界资源,大多数低速的I/O设备,如打印机等都属于临界资源。此外,还有许多变量和数据也可以作为临界资源。

多个进程必须互斥的访问临界资源,我们把每个进程访问临界资源的那段代码称为临界区(critical section)。若能保证进程互斥的进入临界区,便可保证进程对临界资源的互斥访问。为此,每个进程在进入临界区之前,应当对临界资源进行检查,看它是否正被访问,只有当其未被访问时,进程便可进入临界区,并设置临界资源正在被访问的标志。我们把在临界区前面增加的一段用于上述检查的代码,称为进入区(entry section)。相应地,在临界区后面也要加上一段称为退出去(exit section)的代码,用于将临界区正被访问的标志恢复为未被访问状态。进程中除了上述几个区域之外的部分的代码,称为剩余区。这样,可把一个访问临界资源的循环进程描述如下:

while(true) {
        entry section;             // 进入区
        critical section;        // 临界区
        exit section;                // 退出区
        remainder section;    // 剩余区
}

为实现进程互斥的访问临界资源,可通过软件(管程、信号量)和硬件(中断屏蔽、硬件指令)两种不同的方式来实现。无论通过哪种方式,所有的同步机制都应遵循下面的四条原则:

2、如何实现进程同步?

常见的进程同步方式有两种:信号量管程

2.1 信号量机制

信号量(Semaphores)机制是一种卓有成效的进程同步工具。在1965年,由荷兰学者Edsger W. Dijkstra发明。在长期的应用中,信号量机制由最初的整型信号量,经历记录型信号量,进而发展为信号量集机制。

整型信号量

最初,信号量被定义为一个用于表示资源数目的整型量S。这个整型量与一般整型量不同,仅能通过两个标准的原子操作wait(S)signal(S)来访问,这两个操作也被称为P(wait)、V(signal)操作,V操作会增加信号量S的数值,而P操作则会减少它。其运作方式可描述为:

wait(S){
    while (S<=0);
    S=S-1;
}
signal(S){
    S=S+1;
}

while(true){
      wait(S);                         // 进入区
        critical section;        // 临界区
        signal(S);                    // 退出区
}

当进程试图进入临界区时,需要先运行P(wait),如果信号量S为负值,进程会被挡住,不能继续;当信号量S的值不为负时,进程可以获准进入临界区。当进程离开临界区时,将会运行V(signal),如果信号量S不为负时,先前被挡住的其他进程将可获准进入临界区。

需要注意的是,P、V是两个原子操作,因此,它们在执行时是不可中断的。亦即,当一个进程在修改某个信号量时,其他进程是不能同时对该信号量进行修改。

在wait操作时,只要信号量S≤0时,会不断地测试,这时,进程并没有释放处理机,因此,整型信号量机制并未遵循"让权等待"的机制,而是让进程陷入"忙等"状态。为了解决这一问题,出现了记录型信号量。

记录型信号量

整型信号量机制存在"忙等"现象,如何让进程不忙等?即当S≤0时,阻塞进程,放弃处理机即可。当有多个进程访问同一临界资源时,就会出现多个进程阻塞等待的情况。为此,在记录型信号量机制中,除了有一个用于代表资源数目的整型变量value以外,还增加了一个用于存放所有等待进程的链表指针L,用于链接上述的所有等待进程。记录型信号量可以大致描述为:

struct Semaphore {
        int value;
      Process *L;
} S;

// 相应地,wait和signal操作则描述为
wait(S) {
  S.value = S.value - 1;
  if(S.value < 0) {
    // 进程调用block原语,阻塞自己,放弃处理机,并插入到信号量等待链表S.L中
    add this process to S.L;
    block()
  }
}

signal(S) {
  S.value = S.value + 1;
  if(S.value <= 0) {
    // S.value+1仍然≤0,则表示信号量等待链表中,仍有等待该资源的进程阻塞
    // 故调用wakeup原语,将S.L链表中的第一个阻塞进程P唤醒
    remove a process P from S.L
    wakeup(p);
  }
}

在记录型信号量机制中,S.value的初始值表示系统中某类资源的数目,对它的每次wait操作,意味着进程请求一个单位的该类资源,则系统中该类资源数减少1个,同样地,执行signal操作,表示系统中可供分配的资源数目+1,如果S.value的初值为1,表示同时只允许一个进程访问该临界资源,此时的信号量转化为互斥信号量,可用于进程互斥。从上述的伪代码中也可以看到,记录型信号量机制遵循「让权等待」的原则。

AND型信号量

在记录型信号量机制中,如果初始值S.value=1,表示多个进程只能互斥的访问临界资源。当多个进程共享一个临界资源时,记录型信号量可以很好的解决,但有些场景,是一个进程需要先获得多个共享资源后,才能继续执行任务。假设有两个进程A、B,他们都要求访问临界资源D、E,有可能出现的情况是,进程A对资源D执行P(wait)操作后,想要继续对资源E执行P(wait)操作时,发现资源E已经被占用,无法访问,只能阻塞自己。这时,其实进程B在对资源E执行P(wait)操作后,正打算访问资源D,其大致示意图如下:

process_dead_lock

这时,进程A、B处于僵持状态,在无外力作用下,两者将一直被阻塞,此时进程A和B进入死锁状态。显然,当请求的资源越多,产生死锁的可能性就越大。而AND型信号量就是为了解决这个问题,其基本思想就是:将进程在整个运行过程中需要的所有资源,一次性全部分配给进程,带进程使用完后,再一起释放。也就是说,对若干个临界资源的分配操作,也必须采取原子操作方式:要么把进程请求的所有资源全部分配给它,要么一个也不分配。因此,我们需要在原来的wait操作中,增加一个"AND"条件,故称为AND同步,或同时wait(Simultaneous wait)操作,其定义如下:

Swait(S1,S2,...,Sn) {
    if(S1>=1 && S2>=1 && ... && Sn>=1) {
        for(int i=1; i<=n; i++) {
            Si = Si - 1;
        }
    } else {
         // 把当前进程放入等待队列,并把进程的程序计数器置于Swait操作的开始位置
         // 每一个资源Si均有一个与之关联的等待队列
         // 在进行if判断时,把第一个满足Si<1的资源称为Sx的话,那么需要把当前进程放到Sx关联的等待队列中
         ......
    }
}

Ssignal(S1,S2,...,Sn) {
    for(int i=1; i<=n; i++) {
            Si = Si + 1;
            // 将所有等待Si的进程从等待队列中取出并放入就绪队列中
            ......
    }
}

AND型信号量的原理挺好理解,需要着重注意的是,不管资源数目Sn中n有多大,Swait操作和Ssign操作都是原子的。你可能会有疑问,操作系统是如何保证这两个操作的原子性的呢?实现难度大吗?其实,大家换个思路,站在操作系统的角度来看这个问题,所有的进程和资源都是由我(OS)来管理的,我想要哪些进程访问哪些资源,哪些进程不访问哪些资源,有困难吗?就比如,资源A正被访问,我(OS)有太多办法不让其他进程来访问了,你说是吧。当然这里并不是说,实现原子操作很简单,只是想建议大家思考一个问题时,可以多转换下角度。对原子操作的实现原理感兴趣的话,可以拓展阅读:原子操作的实现原理

信号量集

记录型信号量机制中,wait(S)或者signal(S)操作仅能对信号量进行加减1操作,意味着每次仅能获得或释放1个单位的某类临界资源。而当一次需要N个某类临界资源时,便要进行N次wait(S)操作,显然很低效。在有些场景下,当资源数量低于某个值时,便不再分配,所以,在每次分配之前,都需要先判断资源数量是否足够。为解决上述问题,可以对AND型信号量机制加以扩充,形成了一般化的信号量集机制。

Swait操作和Ssignal操作可作如下描述,其中S为信号量,D为需求值,T为下限值

Swait(S1,D1,T1,...,Sn,Dn,Tn) {
    if(S1>T1 && ... && Sn>Tn) {
        for(int i=1; i<=n; i++) {
            Si = Si-Di;
        }
    }else {
        // 同AND型信号量,阻塞当前进程,并把它放到首次满足Si<Ti的资源关联的等待队列中
        // 并设置进程的程序计数器到Swait的开始位置
    }
}

Ssignal(S1,D1,...,Sn,Dn) {
  for(int i=1; i<=n; i++) {
            Si = Si+Di;
        // 同AND型信号量,将所有等待Si的进程从等待队列中取出并放入就绪队列中
        }
}

需要注意的是,这里包含一个隐含条件,也就是D≤T的,还有这里的下限值,并不是说分配完资源后,剩余的数目为T,而是指,只有大于T就可以分配。透过上面的定义,变换S、D、T的取值,会得到以下2种特殊的情况。

在书中原文,其实还有一种特殊情况,即Swait(S,D,D),即D=T,这种情况下,即允许每次申请D个资源,当资源数少于D时,不予分配。但我实在看不出来,它有什么特殊的。

3、拓展:信号量与互斥锁区别?

有这样一种观点:互斥锁是信号量=1的特例。这里有一个形象的例子来描述这种观点。

在一栋房子里面,有一间厕所,这间厕所最多只能容纳一个人,里面有人的时候,其他人就不能进去。一个防止他人进入的简单方法,就是在门口加一把锁。先到的人锁上门,后到的人看到门上有锁,就在门口排队,等锁打开再进去,这就是所谓的"互斥锁",即 Mutual exclusion,缩写Mutex,用来防止多个进程或者线程访问临界资源。

房子里面还有其他房间可以容纳多个人,比如客厅,但毕竟容纳的人数是有限,这里用N来表示,当人数大于N的时候,多出来的人还是只能在外面等着。我们可以扩展上面的方法,在门口挂N把钥匙,进去的人取一把,出来的人把钥匙挂回原处。后到的人发现墙上没有钥匙就只能等待。这种方法就叫做"信号量",即Semaphore

因此,我们是不是可以认为:Mutex是Semaphore的一种特例?

虽然互斥锁可以用信号量来实现,但两者无论在概念还是应用场景上,均有很大不同,可以说是两个完全不同的概念。

信号量是一种同步机制,用于协调进程或者线程间执行的逻辑顺序,其实质是进程或者线程的调度,而锁是用来保护共享资源的,是服务于资源的。比如有A、B两个线程,线程B执行到某处时,需要等待线程A完成某些任务后,再往下执行,这一过程中,并不一定会锁住某些资源。而互斥锁则是"锁住某一个资源"的概念,在锁定期间,其他线程无法对保护的数据进行操作。

虽然信号量可以当做锁来用,但不能认为这两者之间有什么特殊的关系,更不能说其中一种是另外一种的特例。这也给了我们一些启示:信号量和互斥锁的使用场景并不一致,因此,个人并不建议使用信号量来实现互斥锁,虽然下一篇我会讲怎么实现。

封面图:Sergey Pesterev on Unsplash

Comments

Post a Message

人生在世,错别字在所难免,无需纠正。

提交评论