一、生产者与消费者问题简述

1. 我们知道，在计算机中可以并行多个线程，当它们之间相互合作时，必然会存在共享资源的问题，这是通过“线程同步”来解决的，而诠释“线程同步”最典型的例子就是著名的“生产者与消费者问题”。
   1. “同步”：指多个线程相互协作，共同完成一个任务，属于线程间工作步调的相互制约。
   2. “互斥”：指多个线程“分时”访问共享资源。
2. 生产者与消费者问题是描述多个线程协同工作的模型，而信号量解决了协同工作中的“同步”和“互斥”。
   
3. 生产者与消费者问题描述如下：
   1. 有一个或多个生产者、一个或多个消费者和一个固定大小的缓冲区，所有生产者和消费者共享这同一个缓冲区。生产者生产某种类型的数据，每次放一个到缓冲区中，消费者消费这种数据，每次从缓冲区中消费一个。同一时刻，缓冲区只能被一个生产者或消费者使用。当缓冲区已满时，生产者不能继续往缓冲区中添加数据，当缓冲区为空时，消费者不能在缓冲区中消费数据。
4. 生产者与消费者问题强调的是：对于有限大小的公共缓冲区，如何同步生产者与消费者的运行，以达到对共享缓冲区的互斥访问，并且保证生产者不会过度生产，消费者不会过度消费，缓冲区不会被破坏。
   1. 对这种缓冲区的破坏，要么是对缓冲区访问溢出，也就是数据存取的地址超过了缓冲区的范围；要么是缓冲区中的数据被破坏，也就是新数据把尚未读取的老数据覆盖。

二、环形缓冲区的实现

1. 缓冲区是多个线程共同使用的共享内存，因此需要保证各线程对缓冲区是互斥访问，并且不会对其过度使用，从而确保不会使缓冲区遭到破坏。也就是说，只要我们能够设计出合理的缓冲区操作方式，就能够解决生产者与消费者问题。
2. 环形缓冲区
   1. 环形缓冲区本质上依然是线性缓冲区，但其使用方式像环一样，没有固定的起始地址和终止地址，环内任何地址都可以作为起始和结束。
   2. 对于缓冲区的访问，我们提供两个指针，一个是头指针，用于往缓冲区中写数据，另一个是尾指针，用于从缓冲区中读数据。每次通过头指针往缓冲区中写入一个数据后，使头指针加 1 指向缓冲区中下一个可写入数据的地址，每次通过尾指针从缓冲区中读取一个数据后，使尾指针加1 指向缓冲区中下一个可读入数据的地址，也就是说，缓冲区相当于一个队列，数据在队列头被写入，在队尾处被读出。
   3. 用线性空间实现这种逻辑上的环形空间，只要我们控制好头指针和尾指针的位置就好了，无论它们怎样变化，始终让它们落在缓冲区空间之内，当指针到达缓冲区的上边界后，想办法将指针置为缓冲区的下边界（通常是对缓冲区大小取模），从而使头尾指针形成回路，逻辑上实现环形缓冲区。这两个指针相当于缓冲区的游标，在缓冲区空间内来回滑动。
   4. 我们的环形缓冲区是个线性队列，队列可以用线性数据结构来实现，比如数组和链表，为了简单，我们用数组来定义队列，实现环形缓冲区。
      

三、添加键盘输入缓冲区

1. 虽然我们的环形缓冲区支持多个生产者和消费者，但目前我们应用的场合非常简单，只是用在单一生产者和单一消费者的环境中，即生产者是键盘驱动，消费者是将来的shell。
2. 本节的任务是：将“在键盘驱动中处理的字符”存入环形缓冲区当中。

3.1 代码详情

ioqueue.h：头文件中定义了队列结构体

#ifndef __DEVICE_IOQUEUE_H
#define __DEVICE_IOQUEUE_H
#include "stdint.h"
#include "stdbool.h"
#include "thread.h"
#include "sync.h"

#define bufsize 64

struct ioqueue {
    /*the lock of buffer*/
    struct lock lock;

    /*if buffer is full, "producer" record which thread become sleeping.*/
    struct task_struct* producer;

    /*if buffer is empty, "consumer" record which thread become sleeping.*/
    struct task_struct* consumer;

    char buf[bufsize];  //buffer
    int32_t head;      //the head of queue
    int32_t tail;      //the tail of queue
};

void ioqueue_init(struct ioqueue* ioq);
bool ioq_full(struct ioqueue* ioq);
char ioq_getchar(struct ioqueue* ioq);
void ioq_putchar(struct ioqueue* ioq, char byte);

#endif

ioqueue.c：文件中定义了对环形键盘缓冲区的各类操作函数

#include "ioqueue.h"
#include "interrupt.h"
#include "global.h"
#include "debug.h"
#include "stdbool.h"

void ioqueue_init(struct ioqueue* ioq) {
    lock_init(&ioq->lock);
    ioq->producer = ioq->consumer = NULL;
    ioq->head = ioq->tail = 0;
}

static int32_t next_pos(int32_t pos) {  //next position in ioqueue.
    return (pos + 1) % bufsize;
}

bool ioq_full(struct ioqueue* ioq) {
    ASSERT(intr_get_status() == INTR_OFF);  //ioqueue is public space, so we must make sure the interrupt is close when we operating.
    return next_pos(ioq->head) == ioq->tail;
}

static bool ioq_empty(struct ioqueue* ioq) {
    ASSERT(intr_get_status() == INTR_OFF);
    return ioq->head == ioq->tail;
}

/*make producer or consumer to waite*/
/*pay attention: "struct task_struct** waiter" is pointed to ioqueue->producer or ioqueue->consumer.*/
static void ioq_wait(struct task_struct** waiter) {
    ASSERT(*waiter == NULL && waiter != NULL);
    *waiter = running_thread();
    thread_block(TASK_BLOCKED);
}

/*wakeup the waiter*/
static void wakeup(struct task_struct** waiter) {
    ASSERT(*waiter != NULL);
    thread_unblock(*waiter);
    *waiter = NULL;
}

/*consumer get one character from ioqueue*/
char ioq_getchar(struct ioqueue* ioq) {
    ASSERT(intr_get_status() == INTR_OFF);

    while(ioq_empty(ioq)) {
        /*using lock will have effect in situation of more consumers and more producers, 
        not only one consumer and producer.*/
        lock_acquire(&ioq->lock);
        ioq_wait(&ioq->consumer);
        lock_release(&ioq->lock);
    }

    char byte = ioq->buf[ioq->tail];
    ioq->tail = next_pos(ioq->tail);

    if(ioq->producer != NULL) {
        wakeup(&ioq->producer);
    }

    return byte;
}

/*producer write one Byte to ioqueue*/
void ioq_putchar(struct ioqueue* ioq, char byte) {
    ASSERT(intr_get_status() == INTR_OFF);

    while(ioq_full(ioq)) {
        lock_acquire(&ioq->lock);
        ioq_wait(&ioq->producer);
        lock_release(&ioq->lock);
    }

    ioq->buf[ioq->head] = byte;
    ioq->head = next_pos(ioq->head);

    if(ioq->consumer != NULL) {
        wakeup(&ioq->consumer);
    }
}

keyboard.c：ioq_putchar()函数将处理后的键盘输入字符存入环形键盘缓冲区

//略
if(cur_char != 0) {  //we use keymap[0] to occupy place.
            if(ioq_full(&kbd_buf) != true) {
                put_char(cur_char);
                ioq_putchar(&kbd_buf, cur_char);
            }
            return;
        }
//略

四、生产者与消费者实例测试

1. 实例测试设计内容大致如下：
   1. 一位生产者
      1. 由键盘中断驱动，且生产者位于主线程中。
      2. 键盘中断使得输入的字符存储到 “环形键盘缓冲区kbd_buf[]” 中。
      3. 当缓冲区存满后，再产生键盘中断将不做任何处理直接返回。
   2. 两位消费者
      1. 由时钟中断驱动，消费者位于新创建的两个独立线程中。
      2. 消费者访问 “环形键盘缓冲区kbd_buf[]” 。
         1. 如果 “环形键盘缓冲区kbd_buf[]” 不为空，则输出信息(包含该独立线程标识)；
         2. 如果 “环形键盘缓冲区kbd_buf[]” 为空，则进入等待；
            1. 第一个发现 “环形键盘缓冲区kbd_buf[]” 为空的线程得到 “环形键盘缓冲区kbd_buf[]” 的锁，同时将自身PCB指针保存在waiter中，并将自身换下进程；
            2. 第二个发现 “环形键盘缓冲区kbd_buf[]” 为空的线程会由于无法得到 “环形键盘缓冲区kbd_buf[]” 的锁，因此只好将自己加入到 “环形键盘缓冲区kbd_buf[]” 的锁的阻塞队列中等待锁的持有者释放锁后唤醒自己并将自己换下处理器。
            3. 此时主线程上处理器运行while(1);，等待键盘输入，且由于两个独立线程此时都不在thread_ready_list中，因此主线程始终被换上换下处理器。
2. 具体测试代码请读者自行编程实现练习，以串联和巩固自线程创建以来的知识点。