lab7同步互斥实现

哲学家就餐问题描述：有五个哲学家，他们的生活方式是交替地进行思考和进餐。哲学家们公用一张圆桌，周围放有五把椅子，每人坐一把。在圆桌上有五个碗和五根筷子，当一个哲学家思考时，他不与其他人交谈，饥饿时便试图取用其左、右最靠近他的筷子，但他可能一根都拿不到。只有在他拿到两根筷子时，方能进餐，进餐完后，放下筷子又继续思考。

互斥是指某一资源同时只允许一个进程对其进行访问，具有唯一性和排它性，但互斥不用限制进程对资源的访问顺序，即访问可以是无序的。同步是指在进程间的执行必须严格按照规定的某种先后次序来运行，即访问是有序的，这种先后次序取决于要系统完成的任务需求。在进程写资源情况下，进程间要求满足互斥条件。在进程读资源情况下，可允许多个进程同时访问资源。

等待队列

用户进程或内核线程可以转入等待状态以等待某个特定事件（比如睡眠,等待子进程结束,等待信号量等），当该事件发生时这些进程能够被再次唤醒。内核实现这一功能的一个底层支撑机制就是等待队列wait_queue，需要等待事件的进程在转入休眠状态后插入到等待队列中。当事件发生之后，内核遍历相应等待队列，唤醒休眠的用户进程或内核线程，并设置其状态为就绪状态（PROC_RUNNABLE），并将该进程从等待队列中清除。

typedef  struct {
    struct proc_struct *proc;     //等待进程的指针
    uint32_t wakeup_flags;        //进程被放入等待队列的原因标记
    wait_queue_t *wait_queue;     //指向此wait结构所属于的wait_queue
    list_entry_t wait_link;       //用来组织wait_queue中wait节点的连接
} wait_t;

typedef struct {
    list_entry_t wait_head;       //wait_queue的队头
} wait_queue_t;

le2wait(le, member)               //实现wait_t中成员的指针向wait_t 指针的转化

为什么屏蔽中断？

信号量的实现需要屏蔽中断，为什么要屏蔽中断？
屏蔽中断是为了保证互斥性，屏蔽中断之后就不能对进程进行抢占了，指的当前在屏蔽中断状态下的进程不会被抢占，由于进程仍在执行，不会主动进行调度，所以就不会被调度。

信号量实现

信号量表示系统资源的数量。
等待信号量的进程需要睡眠来减少占用 CPU 的开销。
信号量数据结构：

typedef struct {
    int value;                   //信号量的当前值
    wait_queue_t wait_queue;     //信号量对应的等待队列
} semaphore_t;

最重要的信号量操作是P操作函数down(semaphore_t *sem)和V操作函数 up(semaphore_t *sem)。
具体实现信号量的P操作，首先关掉中断，然后判断当前信号量的value是否大于0。如果是>0，则表明可以获得信号量，故让value减一，并打开中断返回即可；如果不是>0，则表明无法获得信号量，故需要将当前的进程加入到等待队列中，并打开中断，然后运行调度器选择另外一个进程执行。

static __noinline uint32_t __down(semaphore_t *sem, uint32_t wait_state) {
    bool intr_flag;
    local_intr_save(intr_flag);
    if (sem->value > 0) {
        sem->value --;
        local_intr_restore(intr_flag);
        return 0;
    }
    wait_t __wait, *wait = &__wait;
    wait_current_set(&(sem->wait_queue), wait, wait_state);
    local_intr_restore(intr_flag);

    schedule();

    local_intr_save(intr_flag);
    wait_current_del(&(sem->wait_queue), wait);
    local_intr_restore(intr_flag);

    if (wait->wakeup_flags != wait_state) {
        return wait->wakeup_flags;
    }
    return 0;
}

具体实现信号量的V操作，首先关中断，如果信号量对应的wait queue中没有进程在等待，直接把信号量的value加一，然后开中断返回；如果有进程在等待且进程等待的原因是semophore设置的，则调用wakeup_wait函数将waitqueue中等待的第一个wait删除，且把此wait关联的进程唤醒，最后开中断返回。

static __noinline void __up(semaphore_t *sem, uint32_t wait_state) {
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        wait_t *wait;
        if ((wait = wait_queue_first(&(sem->wait_queue))) == NULL) {
            sem->value ++;
        }
        else {
            wakeup_wait(&(sem->wait_queue), wait, wait_state, 1);
        }
    }
    local_intr_restore(intr_flag);
}

管程和条件变量的实现

针对生产者-消费者问题

用信号量解决生产者-消费者问题时，信号量的PV操作需要分散在生产者和消费者两个不同的进程中，PV操作的配对比较困难，试图将配对的PV操作集中到一起，就是管程。

管程相当于一个隔离区，它把共享变量和对它进行操作的若干个过程围了起来，所有进程要访问临界资源时，都必须经过管程才能进入，而管程每次只允许一个进程进入管程，从而需要确保进程之间互斥。

条件变量

管程实现

管程的数据结构monitor_t：

typedef struct monitor{
    semaphore_t mutex;      // the mutex lock for going into the routines in monitor, should be initialized to 1
    // the next semaphore is used to 
    //    (1) procs which call cond_signal funciton should DOWN next sema after UP cv.sema
    // OR (2) procs which call cond_wait funciton should UP next sema before DOWN cv.sema
    semaphore_t next;        
    int next_count;         // the number of of sleeped procs which cond_signal funciton
    condvar_t *cv;          // the condvars in monitor
} monitor_t;

条件变量的数据结构：

typedef struct condvar{
    semaphore_t sem;     // the sem semaphore is used to down the waiting proc, and the signaling proc should up the waiting proc
    int count;       　    // the number of waiters on condvar等待在条件变量上的进程的个数
    monitor_t * owner;     // the owner(monitor) of this condvar
} condvar_t;

用信号量实现的条件变量：（条件变量是管程中的一部分）
条件变量wait、signal操作：当前线程需要的条件不满足，就让当前线程睡眠（睡眠就是执行wait），如果当前线程需要的条件满足了，另一个进程会执行signal操作（将睡眠的进程唤醒）
wait:等在该条件变量上的进程数+1，将自己放到等待队列中，释放管程的互斥访问权，执行调度，当被唤醒时再重新加锁
signal：如果有另外的线程等在这个条件变量上，而这个条件满足了，把等在这个条件变量上的线程从等待队列里移出来放到就绪队列唤醒它，然后等在该条件变量上的线程数-1，

cv.count++;
if(monitor.next_count > 0)
   sem_signal(monitor.next);
else
   sem_signal(monitor.mutex);
sem_wait(cv.sem);
cv.count -- ;

如果进程A执行了cond_wait函数，表示此进程等待某个条件Cond不为真，需要睡眠。因此表示等待此条件的睡眠进程个数cv.count要加一。接下来会出现两种情况。
情况一：如果monitor.next_count如果大于0，表示有大于等于1个进程执行cond_signal函数且睡了，就睡在了monitor.next信号量上，因此需要唤醒等待队列Ｓ中的一个进程B；然后进程A睡在cv.sem上。如果进程A醒了，则让cv.count减一
情况二：如果monitor.next_count如果小于等于0，表示目前没有进程执行cond_signal函数且睡着了，那需要唤醒的是由于互斥条件限制而无法进入管程的进程，所以要唤醒睡在monitor.mutex上的进程。然后进程A睡在cv.sem上，如果睡醒了，则让cv.count减一

if( cv.count > 0) {
   monitor.next_count ++;
   sem_signal(cv.sem);
   sem_wait(monitor.next);
   monitor.next_count -- ;
}

首先进程B判断cv.count，如果不大于0，则表示当前没有执行cond_wait而睡眠的进程，因此就没有被唤醒的对象了，直接函数返回即可；如果大于0，这表示当前有执行cond_wait而睡眠的进程A，因此需要唤醒等待在cv.sem上睡眠的进程A。由于只允许一个进程在管程中执行，所以一旦进程B唤醒了别人（进程A），那么自己就需要睡眠。故让monitor.next_count加一，且让自己（进程B）睡在信号量monitor.next上。如果睡醒了，这让monitor.next_count减一。

条件变量的实现：

经典同步问题

1、生产者-消费者问题

信号量解决：
缓冲区是个临界区


fullbuffers：缓冲区中资源个数
emptybuffers：缓冲区中空闲个数
mutex：二进制信号量
生产者：检查空闲个数，空闲个数大于0才进去，空闲个数小于0我就等待。二进制信号量mutex保证互斥访问缓冲区。生产完以后，执行fullbuffers的v操作，如果没有消费者在等待从缓冲区拿资源，那缓冲区资源数直接加1，如果有消费者在等待，则唤醒消费者
消费者：检查资源个数，资源个数大于0才进去，消费者拿完资源后，空闲数+1，如果有生产者在等待空闲位置，则唤醒生产者。

管程解决：

条件变量搭配互斥锁使用，互斥锁实现管程的互斥访问权。
假设缓冲区满了，生产者进入条件等待。释放管程的互斥访问权。调度消费者执行。消费者进来后，缓冲区不为0，从缓冲区中取出资源。由于缓冲区不为满了，可以唤醒生产者了，生产者继续执行，生产一个资源。然后看有没有线程等在notempty上，发现没有，不用执行操作。
用管程实现，可以把PV操作都集中到一个模块里面，简化和降低同步机制的实现难度。

2、哲学家就餐问题

信号量解决

正常情况下，肯定没问题，拿一个叉子等另一个。极端情况下，五个哲学家一块执行了，但是也是有人拿左边有人拿右边，不会行成环路，就不会造成死锁了。

管程解决

取筷子：探测左右邻居，如果左右邻居都不处于吃的状态，那么他就可以吃。否则，它等待。
放筷子：探测左右邻居，如果左右邻居有一个可以处于吃，则让那个可以吃的吃，唤醒那个吃的人让他取筷子。

3、读者-写者问题