【操作系统】第六章 进程同步

时间：2021-05-11 12:21:08

6.1背景

关于前面讨论过的共享内存问题，为了让它能够存储BufferSize个元素，我们修改其代码，如下。
生产者：

while (true) {

    /* produce an item in nextProduced */

    while (counter == BUFFER SIZE)

    ; /* do nothing */

    buffer[in] = nextProduced;

    in = (in+l) % BUFFER_SIZE;

    counter++;
}

消费者：

while (true) {

    while (counter == 0)

    ; /* do nothing */

    nextConsumed = buffer [out];

    out = (out + 1) % BUFFER_SIZE;

    counter--;

/* consume the item in nextConsumed */
}

乍一看，消费者和生产者代码都正确，但是当这两段代码并发执行的时候就有问题了。并发时，两个进程会同时操作counter.这就会导致竞争条件。从而出现错误。为了避免这样的错误，同一时间我们只能允许一个进程操作counter。

6.2临界区问题

临界区就是一个代码段，在这部分代码段中，会改变共同变量、共同表等东西。所以我们需要有这样一个机制，用来保证一个进程进入临界区，没有其他进程被允许在临界区内执行。
每个进程必须请求进入其临界区，实现这一请求的代码段称为进入区，临界区之后可有退出区。其他代码·段称为剩余区。
临界区问题的解答必须满足以下三个要求：

  • 互斥，如果进程 p i 在其临界区内执行，那么其他进程不能在临界区内执行。
  • 前进，若没有进程在临界区执行，那么选择需要进入临界区的进程进入临界区执行。
  • 有限等待:每个需要进入临界区的进程，都必须有机会进入。

有两种办法解决操作系统内的临界区问题：抢占内核与非抢占内核。
非抢占内核比较简单，因为同一时刻只有一个进程在内核模式，不会发生竞争条件。而抢占内核就不同了。

6.3Peterson算法

  • peterson算法适用于两个进程在剩余区和临界区交替执行。为了方便以下用 p i 表示一个进程，用 p j 表示另一个进程。
    【操作系统】第六章 进程同步
  • peterson算法需要在两格进程之间共享两个数据项： int turn； boolean flag[2];.
  • turn表示哪个进程可以进入其临界区，数组flag[i]表示哪个进程想要进入临界区。
  • 分析上面的算法，当flag[j]为真，说明另一个进程也要进入临界区，turn==j有有两种情况，第一说明另一程序还没有执行到改变turn的这一步，但此时flag[j] = true,说明它已经执行了改变turn的上面的那句，那么下一步马上就要执行turn = i这步了，这样一来，这边的i进程马上就可以进入临界区开始执行。在临界区执行的这段时间flag[i] = true,并且刚刚turn也修改为i,所以进程j不可能进入临界区，而当这边的进程离开临界区的时候，flag[i]就会被设置为false,这样另一进程就可以进来了。
  • 课本中关于这个算法的证明：
    • 互斥：
      • 首先，如果两个进程想要同时进入临界区，那么必须同时满足，flag[i] = flag[j] = false或者turn = i。但是当一个进程在临界区执行的时候，它的flag[i]=true,并且turn不可能同时为两个值。满足互斥。

6.4硬件同步

  • 对于单处理器环境，临界区问题可以简单地加以处理：在修改临界区变量时要禁止中断的出现，这样就能确保当前指令序列的执行不会被中断。这种方法通常为非抢占内核所采用。
  • 这种方法在多处理器系统中是不可行的。由于要将消息传递给所有处理器，这样会很费时，会降低系统效率。
  • 所以现代操作系统提供提供了特殊硬件指令，来原子的修改字的内容或交换两个字的内容。可以用这些指令来简单地解决这些问题。
    举例：
    TestAndSet()指令会原子的执行。
    其定义如下：
boolean TestAndSet(boolean *target){
    boolean rv = *target;
    *target =true;
    return rv;
}

使用TestAndSet的互斥实现：将lock初始化为false.

do{
    whiel(TestAndSet(&lock));
    //临界区
    *lock = false;
    //退出区
}while(true);
  • 与TestAndSet相似的Swap方法操作两个数据。
    其定义如下：
void Swap(boolean *a, boolean* b)
{
    boolean temp = *a;
    *a = *b;
    *b = temp;  
}

实现互斥的方法如下：其中key为局部变量：,lock为全局变量，初始化为false。

do{
    key =true;
    while(key == true)
        Swap(&key, &lock);
        //临界区
    lock = false;
    //退出区
}while(true);
  • 上述两个算法解决了互斥问题，但是没有解决有限等待问题。
    下面的算法满足临界区问题的三个条件：用到的数据结构均初始化为false。
boolean waiting[n];
boolean lock;

算法如下：

do {
    waiting[i] = TRUE;
    key=TRUE;
    while (waiting[i] && key)
        key=TestAndSet(&1ock);
    waiting[i] = FALSE;
    // critical section
    j=(i+1)%n;
    while ((j != i) && !waiting[j])
        j = (j+ 1)% n;
    if (j== i)
        lock = FALSE;
    else
        waiting[j] = FALSE;
    // remainder section
}while (TRUE);

解析：
上述算法在执行过程中，当waiting[i]和key有一个为假时才会进入临界区，也就是说，第一个到达的进程进去以后lock马上变为真，那么其他进程必须等待，当已经进去的进程完成任务以后，他会去查找一个正在等待进入临界区的进程，如果此时只有一个进程，那么将lock释放，允许进入。如果找到了一个正在等待进入临界区的进程，那么将它的waiting置为false，它就可以进去了。

6.5信号量

wait()和signal()
其定义如下：

wait(s)
{
    while(s<=0);
    s--;
}

signal(s)
{
    s++;
}

上述两条语句都是原子语句。每句必须不可分的执行。

6.5.1用法

互斥锁的实现：
mutex初始化为1。

do{
    waiting(mutex);
    //临界区
    signal(mutex);
    //退出区
}while(true);

6.5.2实现

这里定义的信号量主要的缺点是忙等待。就是说当一个进程位于其临界区内时，其他进程必须在其进入代码中连续循环，来等待信号量。忙等待浪费了CPU时钟。
这种信号量也称为自旋锁。自旋锁有其优点，不需要进行上下文切换，由于上下文切换会花费大量时间，所以在等待时间较短时，自旋锁节省了大量上下文切换的时间。自旋锁在多处理器系统中比较常用，一个进程阻塞，其他进程可在临界区内执行。
为了克服忙等待，设置一个链表，当一个进程在循环等待时，将其加入等待队列。
具体实现如下：
定义一个结构体：
typedef struct{
int value;
struct process* list;

} samephore;

wait(samephore * s)
{
    s->value--;
    if(s->value <0)
    {
        add this process to s->list;
        block();
    }
}

signal(samephore *s)
{
    s->value++;
    if(s->value <= 0)
    {
        remove a process P from s->list;
        wakeup(p); 
    }
}

block（）是挂起调用它的操作。
wakeup(p)是重新唤起阻塞进程P的执行。
这种实现中信号量的值可以为负，此时它的绝对值表示等待信号量的进程的个数。

实验：经典同步问题之读者写者问题

里面有实验报告和源码，直接戳这里

标签：

相关文章