操作系统实验四-同步机构

一、实验内容二、实验目的三、实验题目四、程序代码

1.数据结构与变量2.程序设计与算法3.完整程序 五、运行结果六、实验思考七、实验感悟

  模拟实现用同步机构避免并发进程执行时可能出现的与时间有关的错误。
  实验报告要求：
  （1）实验题目。
  （2）打印源程序并附上注释。
  （3）从键盘上输入一组字符，由生产者每次读入一个字符供消费者输出。运行模拟程序，打印依次读入的字符和消费者输出的字符。
  （4）把生产者和消费者进程中的P操作、V操作都改成空操作指令，观察在两者不同步的情况下可能出现的与时间有关的错误。打印依次读入的字符和消费者输出的字符。

  进程是程序在一个数据集合上运行的过程，进程是并发执行的，也即系统中的多个进程轮流地占用处理器运行。
  我们把若干个进程都能进行访问和修改的那些变量称为公共变量。由于进程是并发执行的，所以，如果对进程访问公共变量不加限制，那么就会产生“与时间有关”的错误，即进程执行后，所得到的结果与访问公共变量的时间有关。为了防止这类错误，系统必须要用同步机构来控制进程对公共变量的访问。一般说，同步机构是由若干条原语——同步原语——所组成。本实验要求学生模拟PV操作同步机构的实现，模拟进程的并发执行，了解进程并发执行时同步机构的作用。

模拟PV操作同步机构，且用PV操作解决生产者——消费者的问题。
(1) PV操作同步机构，由P操作原语和V操作原语组成，它们的定义如下:
P操作原语P(s):将信号量s减去1,若结果小于0,则执行原语的进程被置成等待信号量s的状态。
V操作原语V(s): 将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程。
(2)生产者-消费者问题
假定有一个生产者和消费者，生产者每次生产一件产品，并把生产的产品存入共享缓冲器以供消费者取走使用。消费者每次从缓冲器内取出一件产品去消费。禁止生产者将产品放入已满的缓冲器内，禁止消费者从空缓冲器内取产品。假定缓冲器内可同时存放10件产品。那么，用PV操作来实现生产者和消费者之间的同步。
(3)进程控制块PCB
为了记录进程执行时的情况、以及进程让出处理器后的状态、断点等信息，每个进程都有一个进程控制块PCB。在模拟实验中，假设进程控制块的结构如图1。其中进程的状态有:运行态、就绪态、等待态和完成态。当进程处于等待态时，在进程控制块PCB中要说明进程等待原因(在模拟实验中进程等待原因为等待信号量 s 1 s_1 s1​或 s 2 s_2 s2​。当进程处于等待态或就绪态时，PCB 中保留了断点信息，一旦进程再度占有处理器则就从断点位置继续运行;当进程处于完成状态，表示进程执行结束。

(4)处理器的模拟
  计算机硬件提供了一组机器指令，处理器的主要职责是解释执行机器指令。为了模拟生产者和消费者进程的并发执行，我们必须模拟一组指令和处理器职能。
  模拟的一组指令见图2,其中每条指令的功能由一个过程来实现。用变量PC来模拟“指令计数器”，假设模拟的指令长度为1，每执行一条模拟指令后， PC加1，指出下一条指令地址。使用模拟的指令，可把生产者和消费者进程的程序表示为图3的形式。定义两个一维数组PA[5]和SA[5],每一个PA[i]存放生产者程序中的一条模拟指令执行的入口地址；每个SA[i]存放消费者程序中的一条模拟指令执行的入口地址。于是模拟处理器执行条指令的过程为： 取出PC之值， 按PA[PC] 或SA[PC]得模拟指令执行的入口地址，将PC之值加1，转向由入口地址确定的相应的过程执行。

(5)程序设计
  本实验中的程序由三部分组成:初始化程序、处理器调度程序、模拟处理器指令执行程序。各部分程序的功能及相互间的关系由图4至图7指出。
  初始化程序:模拟实验的程序从初始化程序入口启动，初始化工作包括对信号量S1、S2赋初值，对生产者、消费者进程的PCB初始化。初始化后转向处理器调度程序，其流程如图4。
  处理器调度程序:在计算机系统中，进程并发执行时，任一进程占用处理器执行完一条指令后就有可能被打断而让出处理器由其他进程运行。故在模拟系统中也类似处理，每当执行一条模拟的指令后，保护当前进程的现场，让它成为非运行状态，由处理器调度程序按随机数再选择一个就绪进程占用处理器运行。处理器调度程序流程见图5.
  模拟处理器指令执行程序：按“ 指令计数器”PC之值执行指定的过程，且PC加1指向下一条指令。模拟处理器指令执行的程序流程见图6和7。
  另外，为了使得模拟程序有一个结束条件，在图6中附加了“生产者运行结束”的条件判断，模拟时可以采取人工选择的方法实现。图7给出了P (S)和V (S)模拟指令执行过程的流程。其他模拟指令的执行过程已在图4-2中指出。

总体流程

处理器调度流程

处理器执行流程（实验指导书有误！）

PV操作流程（实验指导书有误！！！）

struct PCB {//进程控制块
    string name;//进程名
    int status;  // 1 就绪,  2 等待,3 完成,0 正在运行
    int waitreason;//等待原因
    int breakingpoint;//断点
};

  因为本问题有且只有一个生产者进程，有且只有一个消费者进程，所以不需要用到队列等数据结构。只需一个指针指向当前运行的进程。

PCB producer;//生产者进程
PCB consumer;//消费者进程
PCB* currp;//当前进程

  本程序需要两个信号量，分别为s1和s2。
  s1值<0时，表示缓冲区已经放满了，生产者不能再放数据了。S2值>=0,表示有数据，可以让消费者去拿数据。

int s1;//信号量：生产者可以往缓冲区放物品
int s2;//消费者可以从缓冲区拿，生产者有物品

  同样的，也需要缓冲区。缓冲区命名为B，与图2是一致的。缓冲区的长度为10。设置指针in为生产者放的位置，out为消费者拿的位置。Char变量c为生产者生产的字符，变量x为消费者消费的字符。

int in;//生产者放的位置
int out;//消费者拿的位置
char B[10];
char c;//生产者生产的字符
char x;//消费者消费的字符

  Pc为程序计数器，指向生产者或消费者当前在运行哪条程序。生产者需要运行的程序地址在pa数组中，消费者运行的程序地址在sa数组中。“地址”并非真正的地址，在后文的算法说明中会体现，算法会读出“地址”之值，利用case语句根据“地址”值决定执行哪条指令。

int pc;
int pa[5];//生产者的程序
int sa[5];//消费者程序

  在主程序中，整体流程为：先初始化，后进行处理机运行。

int main() {
    	init();
   		cpuwork();
    	return 0;
}

  init()函数进行初始化。在初始化时，先初始化信号量，再初始化当前生产者和消费者指向的缓冲区的位置0。初始化生产者进程和消费者进程的状态。初始化程序的“地址”。

void init() {
    s1 = 10;
    s2 = 0;//初始化信号量
    out = 0;
    in = 0;//初始化生产者与消费者在缓冲区放的商品的位置
    producer.name = "producer";
    producer.status = 1;
    producer.waitreason = 0;
    producer.breakingpoint = 0;//pcb状态为就绪，断点为0

    consumer.name = "consumer";
    consumer.status = 1;
    consumer.waitreason = 0;
    consumer.breakingpoint = 0;//pcb状态为就绪，断点为0
    currp = &producer;//将现行进程设置为生产者进程
    pc = 0;//pc=0
    for (int i = 0; i <= 4; i++) {
        pa[i] = i;
        sa[i] = i;//初始化生产者程序与消费者程序
    }
}

  P操作根据信号量值决定当前状态是被阻塞，并设置断点，或者是程序能够继续就绪运行。

void p(int& s, int p, PCB* pcb) {
    s = s - 1;
    cout << "mutex s" << p<status = 2;//等待状态
        pcb->waitreason = p;//等待的信号量是p
        cout << pcb->name << " begins waiting!n";
    }
    else {
        cout << pcb->name << " doesn't need waiting!n";
        pcb->status = 1;//将调用p(s)的进程置为就绪
    }
}

  V操作根据信号量值决定是否要将等待当前信号量的进程设置为就绪。需要说明的是，判断条件是s<=0,而不是s<0。指导书有误

void v(int& s, int p, PCB* pcb) {
    s = s + 1;
    if (s <= 0) {
        if (producer.waitreason == p)
            producer.status = 1;
        else if (consumer.waitreason == p)
            consumer.status = 1;//将一个等待s信号量的进程置为就绪
        if (currp->name == "producer")
            cout << "consumer released!";
        else
            cout << "producer released!";
    }

    pcb->status = 1;//将调用V(s)的进程置为就绪
}

  在处理机调度时，若有多个就绪进程，随机选择一个就绪进程置为运行态。把pcb断点值赋值，并对该进程进行运行。

while (1) {
        currp->breakingpoint = pc;//当前进程pcb断点为pc
        if (consumer.status != 1 && producer.status != 1)
            return;//无就绪进程
        if (consumer.status == 1 && producer.status == 1) {
            srand(time(NULL));//随机选择一个就绪进程
            int randnum = rand() % 2;
            if (randnum >= 1)
                currp =& consumer;
            else
                currp =& producer; 
        }
        else if (consumer.status == 1)
            currp = &consumer;
        else if(producer.status==1)
            currp = &producer;

        currp->status = 0;//将现行进程改为运行态
        pc = currp->breakingpoint;//现行进程pcb断点值赋值给pc
        exec();
    }

  在处理器执行当前正在运行的程序时，利用程序计数器选择当前进程指令“地址”i，通过“地址”i找到需要运行的指令j。之后，程序计数器指向下一条地址。利用case语句，根据j值执行对应指令。指令如图3所示。每条指令的内容如图2所示。可以发现，对于每条指令，在程序中的执行与图表要求执行的语句是一致的。

void exec() {//模拟处理器指令执行
    int i = pc;
    int j;
    int curq;
    cout << "current process " << currp->name << endl;
    if (currp->name == "producer") {//现行进程为生产者？
        j = pa[i];
        curq = 0;
    }
    else {
        j = sa[i];
        curq = 1;
    }
    pc = i + 1;
switch (j) {//按j转向各模拟指令对应的过程
    case 0:
        if (curq == 0) {//produce
            char pronum;
            cout << "please produce a char";
            cin >> pronum;
            c = pronum;
            cout << "produced!";
            currp->status = 1;
        }
        else
            p(s2, 2, currp);//p(s2)
        break;
    case 1:
        if (curq == 0)
            p(s1, 1, currp);//p(s1)
        else {//GET
            cout << "get goods!";
            x = B[out];
            out = (out + 1) % 10;
            cout << x << endl;
            currp->status = 1;
        }
        break;
    case 2:
        if (curq == 0) {//PUT
            cout << "put goods!";
            B[in] = c;
            in = (in + 1) % 10;
            cout << c << endl;
            currp->status = 1;
        }
        else
            v(s1, 1, currp);//V(s1)
        break;
    case 3:
        if (curq == 0)//V(s2)
            v(s2, 2, currp);
        else {//consume
            cout << "goods consumed!";
            cout << x << endl;
            currp->status = 1;
        }
        break;
    case 4://goto 0
        pc = 0;
        currp->status = 1;
        cout << "goto 0!";
        break;
    }
    if (producer.status != 3) {//模拟时采用人工选择的办法实现“生产者运行结束”的判断
        cout << "Has producer finished?Y/N";
        char st;
        cin >> st;
        if (st == 'Y')
            producer.status = 3;
    }
    return;
}

#include 
#include 
#include 
#include 
#include 
using namespace std;
struct PCB {//进程控制块
    string name;//进程名
    int status;  // 1 就绪,  2 等待,3 完成,0 正在运行
    int waitreason;//等待原因
    int breakingpoint;//断点
};
PCB producer;//生产者进程
PCB consumer;//消费者进程
PCB* currp;//当前进程
int s1;//信号量：生产者可以往缓冲区放物品
int s2;//消费者可以从缓冲区拿
char c;//生产者生产的字符
char x;//消费者消费的字符
int pc;//程序计数器
int in;//生产者放的位置
int out;//消费者拿的位置
int pa[5];//生产者的程序
char B[10];//拿
int sa[5];//消费者程序
void init() {
    s1 = 10;
    s2 = 0;//初始化信号量
    out = 0;
    in = 0;//初始化生产者与消费者在缓冲区放的商品的位置
    producer.name = "producer";
    producer.status = 1;
    producer.waitreason = 0;
    producer.breakingpoint = 0;//pcb状态为就绪，断点为0

    consumer.name = "consumer";
    consumer.status = 1;
    consumer.waitreason = 0;
    consumer.breakingpoint = 0;//pcb状态为就绪，断点为0
    currp = &producer;//将现行进程设置为生产者进程
    pc = 0;//pc=0
    for (int i = 0; i <= 4; i++) {
        pa[i] = i;
        sa[i] = i;//初始化生产者程序与消费者程序
    }
}
void p(int& s, int p, PCB* pcb) {
    s = s - 1;
    cout << "mutex s" << p<status = 2;//等待状态
        pcb->waitreason = p;//等待的信号量是p
        cout << pcb->name << " begins waiting!n";
    }
    else {
        cout << pcb->name << " doesn't need waiting!n";
        pcb->status = 1;//将调用p(s)的进程置为就绪
    }
}
void v(int& s, int p, PCB* pcb) {
    s = s + 1;
    if (s <= 0) {
        if (producer.waitreason == p)
            producer.status = 1;
        else if (consumer.waitreason == p)
            consumer.status = 1;//将一个等待s信号量的进程置为就绪
        if (currp->name == "producer")
            cout << "consumer released!";
        else
            cout << "producer released!";
    }

    pcb->status = 1;//将调用V(s)的进程置为就绪
}
void printstate() {//打印当前状态
    cout << "*************************************************n";
    cout << "current process" << currp->name << endl;
    cout << "producer breakingpoint" << producer.breakingpoint << endl;
    cout << "producer status" << producer.status << endl;
    cout << "producer waitreason" << producer.waitreason << endl;
    cout << "consumer breakingpoint" << consumer.breakingpoint << endl;
    cout << "consumer status" << consumer.status << endl;
    cout << "consumer waitreason" << consumer.waitreason << endl;
    cout << "*************************************************n";
}
void exec() {//模拟处理器指令执行
    int i = pc;
    int j;
    int curq;
    cout << "current process " << currp->name << endl;
    if (currp->name == "producer") {//现行进程为生产者？
        j = pa[i];
        curq = 0;
    }
    else {
        j = sa[i];
        curq = 1;
    }
    pc = i + 1;
switch (j) {//按j转向各模拟指令对应的过程
    case 0:
        if (curq == 0) {//produce
            char pronum;
            cout << "please produce a char";
            cin >> pronum;
            c = pronum;
            cout << "produced!";
            currp->status = 1;
        }
        else
            p(s2, 2, currp);//p(s2)
        break;
    case 1:
        if (curq == 0)
            p(s1, 1, currp);//p(s1)
        else {//GET
            cout << "get goods!";
            x = B[out];
            out = (out + 1) % 10;
            cout << x << endl;
            currp->status = 1;
        }
        break;
    case 2:
        if (curq == 0) {//PUT
            cout << "put goods!";
            B[in] = c;
            in = (in + 1) % 10;
            cout << c << endl;
            currp->status = 1;
        }
        else
            v(s1, 1, currp);//V(s1)
        break;
    case 3:
        if (curq == 0)//V(s2)
            v(s2, 2, currp);
        else {//consume
            cout << "goods consumed!";
            cout << x << endl;
            currp->status = 1;
        }
        break;
    case 4://goto 0
        pc = 0;
        currp->status = 1;
        cout << "goto 0!";
        break;

    }

    if (producer.status != 3) {//模拟时采用人工选择的办法实现“生产者运行结束”的判断
        cout << "Has producer finished?Y/N";
        char st;
        cin >> st;
        if (st == 'Y')
            producer.status = 3;
    }
    return;
}
void cpuwork() {
    while (1) {
        currp->breakingpoint = pc;//当前进程pcb断点为pc
        if (consumer.status != 1 && producer.status != 1)
            return;//无就绪进程
        if (consumer.status == 1 && producer.status == 1) {
            srand(time(NULL));//随机选择一个就绪进程
            int randnum = rand() % 2;
            if (randnum >= 1)
                currp =& consumer;
            else
                currp =& producer; 
          
        }

        else if (consumer.status == 1)
            currp = &consumer;
        else if(producer.status==1)
            currp = &producer;

        currp->status = 0;//将现行进程改为运行态
        pc = currp->breakingpoint;//现行进程pcb断点值赋值给pc
        exec();
    }
}
int main() {
    init();
    cpuwork();
    return 0;
}

  本部分对应实验报告要求中的第（3）部分：从键盘上输入一组字符，由生产者每次读入一个字符供消费者输出。运行模拟程序，打印依次读入的字符和消费者输出的字符。

  开始时生产者与消费者都是处于就绪态。系统随机选择了消费者处于现行进程。消费者执行P( s 2 s_2 s2​)操作，将自己阻塞并等待 s 2 s_2 s2​信号。

  只有生产者就绪，选择生产者作为现行进程，生产者正确地生产了一个字符”c”。

  只有生产者就绪，选择生产者作为现行进程，生产者正确地将生产完毕的字符放入缓冲区供消费者去消费。

  生产者执行V操作， s 2 s_2 s2​信号量表示生产者告诉消费者能从缓冲区取物品。生产者将消费者进程释放。

  以此类推，生产者完成第一个字符的生产后，跳转回第一个程序过程produce，并生产第二个字符b。

  消费者在被唤醒后处于就绪态。当随机选择进程选择到消费者时，消费者正确地取得了生产者生产的第一个字符”c”。

  消费者正确地将字符”c”消费掉。

  与此同时，生产者正确地放入第二个生产的字符”b”。


  生产者生产完”b”后，将自己置为完成态。生产者正确地完成了所有的生产。此时消费者执行剩下的过程，正确地取得了生产者的第二个字符”b”，并正确地消费掉。
  综上所述，实验题目被正确地实现了。生产者依次读入字符，消费者按顺序依次输出字符。

  本部分对应实验报告要求第（4）部分：把生产者和消费者进程中的P操作、V操作都改成空操作指令，观察在两者不同步的情况下可能出现的与时间有关的错误。打印依次读入的字符和消费者输出的字符。
  言而简之，两者在不同步的情况下可能出现与时间有关的错误。不仅有消费者会出现错误，而且生产者也会出现错误。


  实验要求中，不允许消费者在空缓冲器内取产品。若将P( s 2 s_2 s2​)改为空操作，则消费者不检测 s 2 s_2 s2​信号量。 s 2 s_2 s2​信号量本身含义是生产者是否允许消费者从缓冲器取产品。若缓冲器为空，则生产者不允许消费者取产品。由于P操作被改为空操作，所以消费者进行了不被允许的操作，从空缓冲区取产品。但缓冲区为空，消费者没有取得任何商品。而且消费者错误地消费了并没有取得到的商品。这就是消费者会产生的错误。

  实验要求中，也不允许生产者将产品放入已满的缓冲器内。缓冲器buffer的大小为10。若按图5的处理器程序调度流程，每次随机选择现行进程，其实触发这一类错误的概率不大。但为了故意触发这一类错误，我们将流程图与代码稍加修改，每次不是随机选择现行就绪进程而是手动从键盘输入选择现行就绪进程。

  缓冲区长度为10，放满了10个字符分别为a、b、c、d、e、f、g、h、i、j。生产者生产完毕第11个字符k字符。若P( s 1 s_1 s1​)不为空操作，则生产者在生产完字符后就会检测缓冲区剩余空间已为0。则生产者不能将刚生产出的k放入缓冲区，则必须等待消费者把先一个字符拿到并消费掉。但由于P( s 1 s_1 s1​)被改为空操作，所以生产者在执行put过程时就会发生错误。

  如图21。生产者因为没有P( s 1 s_1 s1​)，缓冲器内原本的a字符在没有被消费者消费掉的情况下被生产者新生产上去的k字符覆盖。因为生产者生产完字符后执行 i n in in= ( i n + 1 ) m o d    10 (in+1) mod 10 (in+1)mod10,而 i n in in表示生产者生产商品所指向的地址。所以生产者在生产完10个商品后地址又指向0，a被覆盖，发生与时间有关的错误。