Unit 3.4
Race Conditions and Semaphore

Presenter Notes

本节幻灯片

Relationship of Processes

  • Two types of relationship
    • Mutex
    • Synchronization
  • Solutions
    • Busy Waiting
    • Sleep and Wakeup

Presenter Notes

同步,互斥 同步是因合作进程之间协调彼此的工作而控制自己的执行速度,即因相互合作,相互等待而产生的制约关系.而互斥是进程之间竞争临界资源而禁止两个以上的进程同时进入临界区所发生的制约关系.

Race Conditions

Two processes want to access shared memory at the same time.

Presenter Notes

我们想象一个假脱机打印程序，当一个进程需要打印一个文件时，它会将该文件放在一个假脱机目录下。另一个进程负责周期性地检查是否有文件需要被打印，如果有就打印并将其在目录中删除。简单设想，脱机目录中有很多槽位，每个槽位中存放文件名，假设它们有两个共享的变量：out，指向下一个要被打印的文件；in，指向下一个空闲的槽位。如图，下一个被打印的应该是4号槽，下一个入队的应该是7号槽。 现在，假设进程A、B将把文件A、B入队，假设A先读到的信息是7，并且A将7存入自己的一个记忆变量中，而这时，系统认为已经分给了A足够的时间，于是中断A切换置进程B。进程读到的信息是7，将7存入自身的一个记忆变量中，并将int更新至8。至此B已经完成了所有的入队操作，转而去干其他的事情。当A继续执行时，它还认为应该将文件存到7号槽，于是A文件成功地覆盖住了B文件，而我们的B文件，永远都不会被打印。问题就出现了。

Critical Regions

Conditions required to avoid race condition:

  • No two processes may be simultaneously inside their critical regions.
  • No assumptions may be made about speeds or the number of CPUs.
  • No process running outside its critical region may block other processes.
  • No process should have to wait forever to enter its critical region.

Presenter Notes

临界区：即访问共享内存的程序片。也就是说，通过合理的安排，使得两个进程不可能同时处在临界区中，就能避免竞争条件。 1、如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。 2、任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。 3、进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。 4、如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。

Critical Regions

Mutual exclusion using critical regions.

Presenter Notes

进程A在T1时刻进入临界区。稍后，在T2时刻进程B试图进入临界区，但是失败了，因为另一个进程已经在该临界区内，而一个时刻只允许一个进程在临界区内。随后，B被暂时挂起直到T3时刻A离开临界区为止，从而允许B立即进入。最后，B离开（在时刻T4），回到了在临界区中没有进程的原始状态。

Mutual Exclusion with Busy Waiting

Proposals for achieving mutual exclusion:

  • Disabling interrupts
  • Lock variables
  • Strict alternation
  • Peterson's solution
  • The TSL instruction

Presenter Notes

屏蔽中断 锁变量 严格轮转法 peterson解法 TSL指令

Strict Alternation

A proposed solution to the critical region problem. (a) Process 0. (b) Process 1. In both cases, be sure to note the semicolons terminating the while statements.

Presenter Notes

共享turn变量，用来记录轮到那个进程进入临界区。 当turn=0时，只有进程0能进入临界区，进程0在离开临界区前将turn 置1，从而标志，轮到进程1进入临界区。 缺点：严格地轮换，可能导致临界区外的进程阻塞需要进入临界区的进程（例 如：当turn=0时，意味着只有进程0能进入临界区，这时如果进程0还要 100年才会进入临界区，而进程1需要马上进入，那进程1还要白白等100 年.） 总结：当一个进程比另一个进程慢了许多的情况下，不宜用这种方式

Peterson's Solution

Peterson’s solution for achieving mutual exclusion.

Presenter Notes

a、进程0通过调用enter_region()进入临界区，此时1也想调用enter_region() 来进入临界区，但interested[0]为TRUE，因此被while循环挂起，当进程0出临 界区时调用leave_region()，将interested[0]设为FALSE，进程1即可及时进入临界 区。 b、当进程0在调用enter_region()过程的任意时刻被中断，进程1进入临界区 后进程0再次进行时，依然会被挂起。（实际上while循环体中的两条判断句就 保证了，当一个进程在临界区中时，另一个想进入临界区的进程必然会被挂起）。

The TSL Instruction

Entering and leaving a critical region using the TSL instruction.

Presenter Notes

TSL（test and set lock）,是十分适合多处理器计算机实现互斥的硬件支持。它会 在一个进程进入临界区时，锁住内存总线，从而禁止其他CPU在本指令结束之前 访问内存。 对于TSL指令，本文之做简单的原理性描述（虽然老师上课讲的比较详细），想进 一步了解关于TSL指令，可以看一下书中本节内容，有详细阐述。

The XCHG Instruction

Entering and leaving a critical region using the XCHG instruction.

Presenter Notes

用XCHG指令进入和离开临界区

Semaphore

  • Semaphore
    • 1965 E. W. Dijkstra
  • PV operations
    • Atomic operations: very quick and uninterruptable
    • Also known as down/up or wait/signal operations
  • Semaphore can be operated by PV operation only.
    • The only exception is the initialization.
    • Even read the value is prohibited

Presenter Notes

Semaphore是一件可以容纳N人的房间，如果人不满就可以进去，如果人满了，就要等待有人出来。对于N=1的情况，称为binary semaphore。一般的用法是，用于限制对于某一资源的同时访问。

Semaphore

  • What’s is semaphore?
    • An integer variable
    • In sleep and wakeup, with a process waiting queue (first in first out)
  • Variable range has different definitions:
    • Whole integer (sleep and wakeup)
      • Positive: the number of resources available
      • Zero: no resource available, no waiting process
      • Negative: the number of processes waiting to use the resources
    • Zero and positive integer (busy waiting)
      • Positive: the number of resources available
      • Zero: no resource available
    • Zero and One only (mutex)
      • Binary semaphores

Presenter Notes

semaphore只是用来记录有多少个线程正在使用他（他并没有互斥的性质，他可以被多个线程拥有），他只是维护一个引用计数，任何线程都可以在任何时刻Release他，造成的结果就是semaphore的引用计数减1 应该这样说，任何时刻，你都不知道具体是哪个线程处于运行状态。semaphore的作用不仅仅是在于实现互斥，它只是说，任何时刻，最多只有这个semaphore指定的最大数量的线程可以获得这个semaphore。什么时候释放和这个semaphore无关，释放了，只不过是semaphore的计数减一，其他线程有机会获得这个semaphore。

---

PV in Sleep and Wakeup

P (Semaphore s)
{
    s=s-1;
    if (s<0)
    {
        added to the semaphore's queue and sleep;
    }
}

V (Semaphore s)
{
    s=s+1;
    if (s<=0)
    {
        wakeup the waiting process in the semaphore's queue;
    }
}

PV sleep and wakeup demo

PV sleep and wakeup demo

PV sleep and wakeup demo

PV sleep and wakeup demo

PV sleep and wakeup demo

PV sleep and wakeup demo

PV sleep and wakeup demo

PV sleep and wakeup demo

PV sleep and wakeup demo

PV sleep and wakeup demo

PV sleep and wakeup demo

PV sleep and wakeup demo

PV in Busy Waiting

P (Semaphore s)
{
    while (!s>0)
    {
        yield the CPU; 
    }
    s--;
}

V (Semaphore s)
{
    s++;
}

PV busy waiting demo

PV busy waiting demo

PV busy waiting demo

PV busy waiting demo

PV busy waiting demo

PV busy waiting demo

Reference

  • Chapter 2: Processes and threads, Modern Operating Systems . Forth Edition, Andrew S. Tanenbaum

results matching ""

    No results matching ""