操作系统概念 --- 读书笔记第6章：进程同步

男娘i 2022-05-31 09:49 235阅读 0赞

6.1 临界区问题

假设有n个进程Pi，每一个进程都一个代码段称为**临界区**，在该区中可能改变共同变量、更新一个表、写一个文件等等，这个就是临界区。

临界区需要满足下面三项要求：  
\- **互斥（Mutual Exclusion）**：也即一个进程在临界区执行，其他的进程不允许进去执行。  
\- **前进（Progress）**：如果当前需要有进程去临界区执行，同时临界区没有进程在执行，可以选择一个进程去临界区执行，这个选择不可以无限推迟。  
\- **有限等待（Bounded Waiting）**：从一个进程请求进入临界区开始，到请求被允许结束，其他进程允许进入临界区的次数有上限，也即不可以无限的等待。

6.2 信号量 Semaphore

信号量多用于进程间的同步与互斥，简单说一下信号量的工作机制，可以直接理解成计数器（当然其实加锁的时候肯定不能这么简单，不只只是信号量了），信号量会有初值（>0），每当有进程申请使用信号量，通过一个P操作来对信号量进行-1操作，当计数器减到0的时候就说明没有资源了，其他进程要想访问就必须等待（具体怎么等还有说法，比如忙等待或者睡眠），当该进程执行完这段工作（我们称之为临界区）之后，就会执行V操作来对信号量进行+1操作。

这里有一个**自旋锁**的概念：  
何谓自旋锁？它是为实现保护共享资源而提出一种锁机制。其实，自旋锁与互斥锁比较类似，它们都是为了解决对某项资源的互斥使用。无论是互斥锁，还是自旋锁，在任何时刻，最多只能有一个保持者，也就说，在任何时刻最多只能有一个执行单元获得锁。但是两者在调度机制上略有不同。对于互斥锁，如果资源已经被占用，资源申请者只能进入睡眠状态。但是自旋锁不会引起调用者睡眠，如果自旋锁已经被别的执行单元保持，调用者就一直循环在那里看是否该自旋锁的保持者已经释放了锁，”自旋”一词就是因此而得名。

6.3 经典同步问题

6.3.1 有限缓冲问题 （生产者消费者模型）

问题是这样的，在一个有限的缓冲池中，有生产者负责生产缓冲，有消费者负责消费缓冲。信号量mutex提供对缓冲池的互斥访问，信号量empty和full表示对空缓冲项和满缓冲项的个数，empty初始化为n，full初始化为0，那么生产者消费者模型如下：

下面是生产者代码

do {
        ...
        //produce an new item 
        ...
    
        wait(empty);
        wait(mutex);
        ...
        //add en item to buffer
        ...
        signal(mutex);
        signal(full);
    
    }while(true);

下面是消费者代码

do {
    
        wait(full);
        wait(mutex);
        ...
        //remove en item to buffer
        ...
        signal(mutex);
        signal(empty);
    
        ...
        //consume an  item 
        ...
    }while(true);

6.3.2 读者写者问题

问题是这样的，数据库的并发读没有问题，但是并发读写或者写写就存在数据不一致问题在，这个问题是这样解决的

信号量mutex和wrt均初始化为1，计数器readcount初始化为0，mutex用于更新readcount的互斥访问，readcount用于表示有多少个读者，wrt供写者作为互斥信号，它仅仅供第一个读者和最后一个读者使用，读者写者代码如下：

下面是写者代码：

do
    {
        wait(wrt);
        ...
        //write
        ...
        signal(wrt);
    }while(true);

下面是读者代码

do
    {
        wait(mutex);
        readcount++;
        if(readcount==1)
            wait(wrt);
        signal(mutex);
    
        ...
        //read
        ...
    
        wait(mutex);
        readcount--;
        if(readcount==0)
            signal(wrt);
        signal(mutex);
    
    }while(true);

6.3.3 哲学家进餐问题

问题描述是这样的，有5个哲学家围在一个圆桌吃饭，每两个哲学家之间有一根筷子，哲学家可以思考和吃饭，吃饭的时候必须使用邻近的两根筷子，吃完饭之后继续思考。

一个简单的解决方法就是每一根筷子使用一个信号量表示，chopstick\[5\],并且都初始化为1，那么对于第i个哲学家的代码如下：

do
    {
        wait(chopstick[i]);
        wait(chopstick[(i+1)%5]);
    
        ...
        //eat
        ...
    
        signal(chopstick[i]);
        signal(chopstick[(i+1)%5]);
    
        ...
        //think
        ...
    }while(true);

这个答案虽然可以保证没有两个哲学家同时使用一根筷子，但是可能会造成死锁，比如所有的哲学家都拿起左边的筷子，所以这个答案应该舍弃，

下面是哲学家进餐问题的管程解决方案：  
哲学界其实有三种状态，thinking、eating和hungry，所以对于5个哲学家有state\[5\]个状态表示，同时还有一个condition self\[5\]来表示哲学家饥饿而且拿不到筷子的时候可以延迟自己。

筷子分布使用管程dp来控制，每一个哲学家进餐之前必须调用操作pickup(),这个可能挂起哲学家进程，在成功完成该操作之后哲学家才可以进餐，接着就可以调用putdown()，并开始思考，如下

do
    {
        dp.pickup();
        ......
        //eatubg
        ......
        dp.putdown();
    }while(true)

下面是使用信号量来实现管程，对于每一个管程都有一个信号量mutex(初始化为1)。进程在进入管程之前必须要执行wait(mutex)，离开管程之后必须要执行signal(mutex)。  
代码如下

monitor dp
    {
        enum {eat,hungry,think} state[5];
        condition self[5];
    
        void pickup(int i)
        {
            state[i]=hungry;
            test(i);
            if(state[i]!=eat)
                self[i].wait();
        }
    
        void putdown(int i)
        {
            state[i]=think;
            test((i+1)%5);
            test((i+4)%5);
        }
    
        void test(int i)
        {
            if(state[(i+1)%5]!=eat && state[i]==hungry && state[(i+4)%5]!=eat)
            {
                state[i]=eat;
                self[i].signal();
            }
        }
    
        void init()
        {
            for(int i=0;i<5;i++)
                state[i]=think;
        }
    
    }