"Process Synchronization 1 IPC(Interprocess communication) 协作的进程需要 IPC 三种 IPC 模型 进程通信可以通过 shared memory 共享内存 pipe 管道 message passing 消息传递 Message passing 建立一个 co .."

操作系统复习笔记(三)——Process synchronization

Process Synchronization 1

三种 IPC 模型

进程通信可以通过

Message passing

直接通信,对称寻址 Direct communication-symmetric addressing

直接通信,非对称寻址

直接通信的缺点:必须知道对方的名字,局限了模块化

间接通信

每个 mailbox 都有独立 id
一条链路连接多个进程

IPC synchronization

Non-blocking 和 blocking receive 是最常见的

IPC buffering

link 的消息队列容量

Critical-Section Problem 临界区问题

对于共享数据的并行访问可能导致数据的不一致

Race condition 竞争条件

多个进程同时访问操作文件,最终结果取决于最后执行的指令
为了避免竞争条件,并行的进程必须是 mutual exclusion 互斥的

互斥

The critical-section problem

每个进程拥有的操作共享数据的代码称为 critical section 临界区。要保证当一个进程执行时它的临界区代码时,其他进程不能执行临界区代码

解决方案: 在执行之前加点条件,判断能否执行,执行完毕后解锁

do{
    entry section   // 执行前判断
        crical section
    exit section    // 执行完毕后解锁
        reminder section
}

解决临界区问题需要满足

例 火车问题

前提

有两列相向而行的火车需要在某个地点占用同一段铁轨,如何保证两车进入不会相撞,且两车都能正常运行

算法 1 交替进入
int turn;
turn=i  //Pi 可以进入

Pi

do {
    while(turn!=i);
    /* critical section */
    turn=j;
    /* remainder section */
} while(1);

满足互斥,但不满足前进原则(只有一辆车运行的情况下)

算法 2 flag each process 给每个进程都标记
boolean flag[2];
flag[i]=true;

Pi

do {
    flag[i]=true;
    while(flag[j]); // 空循环等待 j
    /* critical sectioon */
    flag[i]=false;
    /* remainder */
} while(1);

如果两个同时刻到,那么都进不去,不满足 Bounded waiting

算法 3 1 和 2 的组合
do {
    flag[i]=true;
    turn=j; // 先把机会让给另外一个
    while(flag[j] && turn==j);  // 如果另外一个也到了,就空循环等待
    /* critical section */
    flag[i]=false;
    /* remainder section */
} while(1);

三个要求都满足

Process Synchronization 2

Synchronization tools for IPC

Synchronization hardware 硬件同步

很多系统提供了硬件对于临界区代码的支持

现代计算机提供了特别的 原子的 (atomic) 硬件指令

TestAndSet Instruction 检查和修改指令 自旋锁

方法:

boolean TestAndSet(boolean *target) {
    boolean rv=*target;
    *target=true;
    return rv;
}

初始化:

boolean lock=false;

执行时:

do{
    while(TestAndSet(&lock));
    //critical section
    lock=false;
    //remainder section
}

Swap Instruction

操作两个数据,与指令 TestAndSet 一样原子执行

void Swap(boolean *a,boolean *b) {
    boolean temp=*a;
    *a=*b;
    *b=temp;
}

初始化:

boolean lock=false;

执行时:

do {
    key=true;
    while(key==true)
        Swap(&lock, &key);
    //critical section
    lock=false;
    //remainder
} 

Semaphores 信号量

Dijkstra 提出 信号量 一个整形变量,只能通过两个标准原子操作:

wait(s):

while(s<=0)
;   //no-operation
s--;

signal(s):

s++

在 wait()和 signal() 操作中,对信号量的修改必须是原子的,即当一个进程修改信号量值时,不能有其他进程同时修改同一信号的值

初始化:

int matex=1;

Critical section of n processes

do {
    wait(mutex);
    //critical section
    signal(mutex);
    //remainder section
} while(1);

两种类型的信号量

信号量实现的分析

主要缺点是 忙等待 (busy waiting)

忙等待

当一个进程位于其临界区内时,其他想进入临界区的进程必须连续循环等待,浪费了 CPU 时钟。也称为自旋锁。

解决方法

为了克服忙等待,可以使用阻塞并放入等待队列的操作。通过 wakeup() 来重新执行

定义一个新结构

typedef struct {
    int value;
    struct process *List;
} semaphore;

新的信号量操作定义

wait(semaphore *S){
    S.value--;
    if(S.value<0) {
        block();    //add this process to S.List
    }
}

signal(semaphore *S) {
    S.value++;
    if(S.value<=0) {
        wakeup(P);  //remove a process P from S.List
    }
}

Bounded-Buffer Problem 可用计数信号量来解决

Deadlock and Starvation 死锁与饥饿

Critical Regions 临界域

一种高层同步结构

Monitor 管程

另一种高层同步结构

比信号量更高的抽象。或者说并没有这种实体存在于系统或编程语言中, 更多的是一种机制,一种解决方法,但是编程语言和操作系统都提供了实现管程的重要部件条件变量

管程就是管理一组共享变量的程序。主要有一下几部分组成

mutex // 一个互斥锁,任何线程访问都必须先获得 mutex

condition // 一个或者多个,每个条件变量都包含一个等待队列

balabala // 共享变量及其访问方法

特点

类型

实现

管程类型提供了一组由程序员定义的、在管程内互斥的操作

monitor monitor-name {
    shared variable declarations
    procedure body P1() {   }
    procedure body Pn() {   }
    {initialization code}
}

同一时刻管程内只有一个进程在活动,因此不需显式地编写同步代码

条件变量

为了让进程在管程内等待,必须声明一些 condition 类型的变量,即条件变量

条件变量两种操作

condition

注意

这里的 wait 和 P 操作是不一样的,最大的不同就是他一定会将自己阻塞同时释放锁。而 signal 如果没有等待线程相当于一个空操作。而且 numWaiting 不可能为负数

Process Synchronization 3

一些经典的同步问题

1. 读写者问题

前提条件

  1. 写者、读者互斥访问文件资源。
  2. 多个读者可以同时访问文件资源。
  3. 只允许一个写者访问文件资源。

两种情况

1. 读者优先
2. 写者优先

如果一个写者等待访问对象,那么不会有新读者开始读操作

读者优先的实现

初始化变量

BINARY_SEMAPHORE wrt=1;
BINARY_SEMAPHORE mutex=1;
int readcount=0;

Reader:

do {
    wait(mutex);    //Allow 1 reader in entry
    readcount=readcount+1;
    if(readcount==1)
        wait(wrt);  //1st reader locks writer
    signal(mutex);
        //reading operation
    wait(mutex);
    readcount=readcount-1;
    if(readcount==0)
        signal(wrt);    //last reader frees writer
    signal(mutex);
}

Writer:

do {
    wait(wrt);
        //writing operation
    signal(wrt);
}

写者优先的实现

初始化变量

BINARY_SEMAPHORE read=1;    // 使有写者进行操作时读者等待
BINARY_SEMAPHORE file=1;    // 使文件操作互斥
BINARY_SEMAPHORE mutex1=1;  // 使改变 readcount 的方法互斥
BINARY_SEMAPHORE mutex2=1;  // 使改变 writecount 的方法互斥
int readcount=0;
int writecount=0;

Reader:

do {
    wait(read); // 等待直至读者队列没有阻塞,即全部写者都退出,同时自身进入后再次上锁,使后来的读者等待,因为接下来要进行一系列互斥的操作
    wait(mutex1);
    readcount++;
    if(readcount==1)    // 第一个读者进入
        wait(file);     // 后来的写者无法操作文件,但对后来的读者的文件操作不造成影响
    signal(mutex1);
    signal(read);   // 释放
        //read operation
    wait(mutex1);
    readcount--;
    if(readcount==0)
        signal(file);
    signal(mutex1);
}

Writer:

do {
    wait(mutex2);
    writecount++;
    if(writecount==1)   // 第一个写者进入
        wait(read); // 阻塞读者队列
    signal(mutex2);
    wait(file);
        //write operation
    signal(file);
    wait(mutex2);
    writecount--;
    if(writecount==0)   // 最后一个写者退出
        signal(read);   // 释放读者队列
    signal(mutex2);
}

哲学家进餐问题

前提条件

5 个哲学家围着桌子吃饭,筷子只有 5 枝,分别在每个哲学家的左手边和右手边。哲学家必须得到两只筷子才能吃饭,要使每个哲学家都能吃到饭,该如何调度

解决方法

只有左右两只筷子都可用时,才允许一个哲学家拿起它们

管程实现

void philosopher(int i) {   // 主方法
    while(true) {
        thinking();
        dp.pickup(i);
        eating();
        dp.putdown(i);
    }
}

monitor dp {
    enum{thinking,hungry,eating} state[5];
    condition self[5];
    void pickup(int i) {
        state[i]=hungry;    // 设置本人为饥饿状态
        test[i];    // 测试左右两个人是否在吃
        if(state[i]!=eating)    // 如果需要等待
            self[i].wait();     // 进入等待,在 pickup 方法处阻塞
    }
    void putdown(int i) {
        state[i]=thinking;
        test((i+4)%5);      
        test((i+1)%5);  // 本人放下筷子后,状态发生了变化,测试左右两个是否等待吃,如有,则给他们开始吃的机会(但也不一定能马上开始吃)
    }
    void test(int i) {
        if((state[(i+4)%5]!=eating) && (state[i]==hungry) && (state[(i+1)%5]!=eating)) {    // 如果左右两个人并没有在吃,而且自己处于饥饿状态
            state[i]=eating;    // 设置状态为 eating
            self[i].signal();   // 释放 pickup 方法,在 philosopher 方法中下一步将执行 eating 操作
        }
    }
    initializationCode() {
        for(int i=0;i<5;i++)
            state[i]=thinking;
    }
}

生产者消费者问题

前提条件

一个生产者,一个消费者,库存有限,如何能持续生产

解决思路

对于生产者,如果缓存是满的就去睡觉。消费者从缓存中取走数据后就叫醒生产者,让它再次将缓存填满。若消费者发现缓存是空的,就去睡觉了。下一轮中生产者将数据写入后就叫醒消费者。

不完善的解决方案会造成“死锁”,即两个进程都在“睡觉”等着对方来“唤醒”。

伪代码

初始化变量:

semaphore mutex=1; // 临界区互斥信号量
semaphore empty=n;  // 空闲库存空间
semaphore full=0;  // 库存初始化为空

生产者进程:

producer ()
{
    while(1)
    {
        produce an item in nextp;  // 生产数据
        P(empty);  // 获取空闲库存单元
        P(mutex);  // 进入临界区.
        add nextp to buffer;  // 将数据放入缓冲区
        V(mutex);  // 离开临界区, 释放互斥信号量
        V(full);  // 库存数加 1
    }
}

消费者进程:

consumer ()
{
    while(1)
    {
        P(full);  // 获取库存数单元
        P(mutex);  // 进入临界区
        remove an item from buffer;  // 从库存中取出数据
        V (mutex);  // 离开临界区,释放互斥信号量
        V (empty) ;  // 空闲库存数加 1
        consume the item;  // 消费数据
    }
}

  • B3log

    B3log 是一个开源组织,名字来源于“Bulletin Board Blog”缩写,目标是将独立博客与论坛结合,形成一种新的网络社区体验,详细请看 B3log 构思。目前 B3log 已经开源了多款产品:PipeSoloSymWide 等,欢迎大家加入,贡献开源。

    2405 引用 • 3795 回帖 • 623 关注
  • 操作系统
    7 引用 • 10 回帖
  • 笔记
    151 引用 • 358 回帖
  • 进程
    10 引用
感谢    关注    收藏    赞同    反对    举报    分享
回帖    
请输入回帖内容...