Understand OS - Process


OS Process

虽然进程可以共享系统资源,但是许多资源在同一时刻只能被一个进程共享,一次只允许一个进程共享的资源就是临界资源。临界资源的访问过程有四个部分:进入区、临界区、退出区、剩余区。

do {
    entry section;
    critical section;
    exit section;
    remainder section;
} while(true);

进程同步要求进程之间通过信号量进行等待、传递信息产生制约关系;进程互斥要求进程间遵守:空闲让进、忙则等待、有限等待、让权等待。让权等待是指当进程不能进入临界区时,应立即释放处理器防止进程忙等待。


0x01.同步与互斥原型

临界区的实现主要有硬件和软件方法。
硬件实现的一个方法是中断屏蔽法,主要通过关中断=>临界区=>开中断实现,由于CPU只有在中断中才能进行进程调度,所以屏蔽中断可以将进程内代码顺利执行完毕;而硬件方法还有另外一种TestAndSet硬件指令法。由于TestAndSet是原子操作不可再分割,从而保证了指令能在顺利执行完毕,功能如下:

bool TestAndSet(boolean *lock) {
    boolean old;
    old = *lock;
    *lock = true;
    return old;
}

软件屏蔽有几种方法:

1.单标志法

Process1() {                        Process2() {
    while(turn != 0) {                    while(turn != 1) {
        critical section;                    critical section;
        turn = 1;                            turn = 0;
        remainder section;                    remainder section;
    }                                    }
}                                    }

如果两个进程交替进入临界区,该算法能保证每次只允许一个进程进入临界区,但是当一个进程长期不再进入临界区,另一个进程就无法再进入临界区,从而违背了“空闲让进”。

2.双标志先检查法

Process1() {                        Process2() {
    while(flag[2]) {}                    while(flag[1]) {}
    flag[1] = true;                        flag[2] = true;
    critical section;                    critical section;
    flag[1] = false;                       flag[2] = false;
    remainder section;                    remainder section;
}                                    }

算法的基本思想是在每个进程访问临界区之前查看下对方是否在访问临界区,若正在访问则需要等待,否则进程进入临界区并设置临界区访问标志。双标志可以不用交替进入临界区运行,但是P1()和P2()在1时刻同时进入 while(flag[]) {} 可能会出现P1()和P2()同时进入临界区,违背忙则等待。

3.双标志后检查

process1() {                        process2() {
    flag[1] = true;                            flag[2] = true;
    while(flag[2]) {}                        while(flag[1]) {}
    critical section;                        critical section;
    flag[1] = false;                            flag[2] = false;
    remainder section;                        remainder section;
}                                    }

双标志后检查是对双标志法的改进,为了防止进程同时进入临界区,采用先置标志法 flag[i] = true; 保证了临界资源的互斥性。但是当两个进程P1()和P2()都想进入临界区同时置标志,会导致进程相互谦让都无法进入临界区,从而导致了”饥饿”。

4.Peterson算法

就在问题无法解决时候,Peterson提出了Peterson算法,既能保证符合进程同步与互斥条件又不会产生及饥饿。为了防止两个进程无尽等待,Peterson设置了turn标志,每个进程先置自己标志后再设置turn标志。那么Peterson算法究竟是什么样的呢?

process1() {                                process2() {
    flag[1] = true;                           flag[2] = true;
    turn = 2;                                 turn = 1;
    while(flag[2] && turn == 2){}            while(flag[2]  && turn == 1){}
    critical section;                        critical section;
    flag[1] = false;                         flag[2] = false;
    remainder section;                        remainder section;
}                                            }

0x02.经典同步与互斥事件

生产者与消费者

Producer && Consumer
常见问题:生产者、消费者共享一组初始为空,大小为n的缓冲区空间,只有缓冲区不满的时候,生产者才能把消息放入缓冲区,否则必须等待;只有缓冲区不空的时候,消费者才能从缓冲区取出消息;并且放入与取出必须互斥操作。

缓冲区操作必须互斥,因此在对缓冲区操作前要加锁 P(mutex); 执行完后释放锁 V(mutex); 缓冲区操作满和不满需要进程间同步通信通知,empty 和 full 用于进程间同步,当缓冲区有消息时执行 V(full); 唤醒Consumer(),当缓冲区有空位时,执行 V(empty); 唤醒Producer()。

semaphore mutex = 1;
semaphore full = 0;
semaphore empty = n;

Process Producer() {
    while(True) {
        P(empty);
        P(mutex);    //互斥操作资源加锁P(mutex);
        //produce...
        V(mutex);    //互斥操作释放资源V(mutex);
        V(full);    //进程同步通知Consumer()生产完毕
    }
}
Process Consumer() {
    while(True) {
        P(full);
        P(mutex);    //互斥操作资源加锁P(mutex);
        //consume...
        V(mutex);    //互斥操作释放资源V(mutex);
        V(empty);    //进程同步通知Producer()消费完毕
    }    
}

读写者问题

常见问题:系统文件读写,有读者和写者两个并发进程共享一个文件,当多个进程共同读取文件时不会发生问题,但读者和写者、写者和写者不能同时作用于共享文件。总结:允许多个读者读文件;一次仅一个写者写文件;写者完成之前不允许读者和写者操作文件;写者执行写之前应等待读者、写者退出。

保证不对读者做限制,必须要对写者加锁,而何时加锁呢?需要根据读者数量做判断,当读者读以前数量为0时候,需要对写者加锁,当读者退出时候发现读者数为0,则需要释放写者锁。对于读者对 count 以及 mutex 锁的操作,需要加 P(mutex); 读者互斥锁。由上面分析可知写者处于弱势,优先权低,为了解决这个问题,引入 write_first 保证读者和写者公平竞争。

int count = 0;                //记录读者数
semaphore mutex = 1;        //对count、write锁操作互斥
semaphore write = 1;        //写进程
semaphore write_first = 1;    //写优先
Process Writer() {
    while(True) {
        P(write_first);    //读者优先
        P(write);            //读写者互斥
        //writing...
        V(write);
        V(write_first);
    }
}
Process Reader() {
    while(True) {
        P(write_first);    //读者优先
        P(mutex);            //对count、write锁操作互斥
        if(count == 0) P(write);    //读者只有一个,对写者上锁
        count++;                        //读者数+1
        V(mutex);
        V(write_first);
        //reading...
        P(write_first);
        P(mutex);        //对count、write锁操作互斥
        count--;        //读者数-1
        if(count == 0) V(write);    //读者只有一个,对写者解锁
        V(mutex);
        V(write_first);
    }
}

双向读写者问题

Crossing the bridge

常见问题:单向通行的桥,不允许双向交汇但允许同向而行并且显示单向一次最多 max_size 通行量。这个问题由读写者引申而来,读者 && 写者都必须互斥操作,并且限制了同时操作数量。作为对称处理,需要同时对东向、西向进程设立锁,并且记录当前用户数以方便为对方设置锁。

int east_count = 0;
int west_count = 0;
semaphore meast = 1;    //互斥操作east数据
semaphore mwest = 1;    //互斥操作west数据
semaphore mutex = 1;    //east与west只允许一方向
semaphore max_size = n;//单方向最大通行量

Process east(int i) {
    P(meast);            //互斥操作east数据
    if(east_count == 0) P(mutex);    //对于第一次获得锁方向
    east_count++;
    V(meast);
    P(max_size);        //单方向最大通行量同步
    //acrossing the bridge
    V(max_size);
    P(meast);
    east_count--;
    if(east_count == 0) V(mutex);    //对于最后一次占用锁
    V(meast);
}
Process west(int i) {
    P(mwest);            //互斥操作east数据
    if(west_count == 0) P(mutex);    //对于第一次获得锁方向
    west_count++;
    V(mwest);
    P(max_size);    //单方向最大通行量同步
    //acrossing the bridge
    V(max_size);
    P(mwest);
    west_count--;
    if(west_count == 0) V(mutex);    //对于最后一次占用锁
    V(mwest);
}

哲学家就餐问题

Philosopher dining
常见问题:一张桌子上有5个哲学家,每两个哲学家中间放一根筷子,哲学家只有两件事:吃饭、思考。如果哲学家拿到左右手两根筷子就吃饭,进餐完毕后保持思考,如果一根筷子在旁边哲学家手里,只能等待。

试想,当哲学家都同时拿起左手边的筷子,等到他们想拿右手边的筷子却已被拿走,系统进入死锁。如何让一个哲学家拿到左右两根筷子而不造成死锁或者饥饿现象?(1)让他们同时拿左右两根筷子(2)对每个哲学家动作做规定,当哲学家抢占到抢筷子是加互斥锁,阻止其他哲学家抢占筷子。

semaphore mutex = 1;
semaphore chopsticks[5] = {1, 1, 1, 1, 1};//筷子序号
Process P(int i) {    //哲学家ID=0,1,2,3,4
    do {
        P(mutex);    //保证仅有一个抢占,防止死锁
        P(chopsticks[i]);    //获取左手筷子
        P(chopsticks[(i + 1) % 5]);    //获取右手筷子
        V(mutex);
        //eating...
        V(chopsticks[i]);    //释放左手筷子
        V(chopsticks[(i + 1) % 5]);    //释放右手筷子
        //thinking...
    } while(True);
}

吸烟者问题

常见问题:有3个吸烟者,A有纸张+烟草,B有纸张+胶水,C有烟草+胶水,当且仅当他们拥有纸张+烟草+胶水才能制作香烟吸烟。进程提供者无限随机提供三种物品中的一种,仅当吸烟者吸完烟,供应者受到信号才提供资源。

供应者与吸烟者是同步关系,由于供应者无法同时提供资源,供应者提供资源是一个互斥操作。

int random;                //随机数
semaphore finish = 0;        //抽烟结束同步信号
semaphore resource1 = 0;    //纸张+烟草
semaphore resource2 = 0;    //纸张+胶水
semaphore resource3 = 0;    //烟草+胶水
Process Offer() {            //资源提供者
    while(True) {
        random = rand();    //获取随机数
        if(random % 3 == 0) //根据随机数提供资源
            V(resource1);
        else if(random % 3 == 1) 
            V(resource2);
        else if(random % 3 == 2) 
            V(resource3);
        //offering...
        P(finish);
    }
}
Process User1() {        //有烟草
    while(True) {
        P(resource2);    //等待纸张+胶水
        //smoking...
        V(finish);
    }
}
Process User2() {        //有纸张
    while(True) {
        P(resource3);    //等待烟草+胶水
        //smoking...
        V(finish);
    }
}
Process User1() {        //有胶水
    while(True) {
        P(resource1);    //等待纸张+烟草
        //smoking...
        V(finish);
    }
}



本文出自 夏日小草,转载请注明出处:http://homeway.me/2017/01/13/understand-os-process-mutex-and-synchronization/

  • by 小草

2017-01-13

Fork me on GitHub