同步互斥lab

复旦早餐王问题

• Q1：关系分析。请写出题目中存在的互斥和同步的关系

  • 首先是是老板和老板娘这两种进程的关系，是互斥的
  • 其次是两个队列中消费者的关系，是互斥而非同步的，即没有某种依赖关系，而是对于篮子的访问时相互排斥的
  • 最后是老板和老板娘作为生产者和消费者之间的进程关系，是同步的，即存在某种关系的

• Q2：上述关系可以抽象为几个进程？请写出伪代码表示

  可以抽象为两个生产者，两个消费者进程队列

  • 代码设计：首先窗口设置为有界缓冲区（用一个变量content来表示篮子）

    • 其次，采取信号量的方式，需要信号量sem_content来实现所有进程对于content的访问的相互互斥（mutual exclusion）
    • 还有还需要信号量Egg和Pancake来实现消费者和生产者之间的对于可以吃的鸡蛋灌饼/煎饼的数量的同步

    int content;       //表示篮子的空间，0表示没有东西，1表示煎饼果子，2表示鸡蛋灌饼
    
    semaphore sem_content; //用来对共享资源content的访问加锁，防止因为线程的并发对数据读写的影响
    semaphore Egg,Pancake; //用来实现生产者消费者对于鸡蛋灌饼和煎饼果子的数目的同步
    //####### initialization ########
    sem_content.count = 1;       //只有一个进程能访问这个篮子
    Egg.count = Pancake.count = 0;   //刚开始的时候篮子里面并没有东西
    void producer_male()   //生产煎饼果子
    {
        while (1)
        {
            wait(sem_content); 
            if (sem_content == 0 && content == 0) //篮子中没有东西
            {
                content = 1;
            }
            else
            {
                //do nothing
            }        
            signal(sem_content);
            signal(Egg);
        }
    }
    
    void producer_female()   //生产鸡蛋灌饼
    {
        while (1)
        {
            wait(sem_content);
            if(sem_content == 0 && content == 0)
            {
                content = 2;
            }
            else
            {
                //do nothing
            }
            signal(sem_content);
            signal(Pancake);
        }
        
    }
    
    void consumer_Egg()   //消费鸡蛋灌饼的，由于是一直在排队，所以简化为while循环，用一个进程来代替
    {
        while(1)
        {
            wait(Egg);   //如果篮子里面没有鸡蛋灌饼，就进行阻塞，直到出现了鸡蛋灌饼为止
            wait(sem_content);
            if(sem_content == 0 && content = 2)
            {
                content = 0;
            }
            else
            {
                //do nothing
            }
            signal(sem_content)
        }
    }
    
    
    void consumer_Pancake()  //消费煎饼果子的
    {
        while (1)
        {
            wait(Pancake);
            wait(sem_content);
            if(sesm_content == 0 && content = 1)
            {
                content = 0;
            }
            else
            {
                //do nothing
            }
            signal(sem_content);
        }
        
    }

小小打印店

在了解完题目之后，我认为这题属于是典型的理发店模型，但是进行了简化，典型的理发店模型除了排队的队列以外，还允许等待的顾客站着等待，而这里则不同，是属于排队队列没有空位就会离开；同时还简化了收费的模型

• Q1：关系分析。请写出题目中存在的互斥和同步的关系

  • 首先，在这里面我将打印机设计为了一个进程，那么需要mutual这个信号量来实现正在打印的这个同学与其他等待的进程之间的互斥

  • 其次，在这里还有一个是打印机与同学之间的同步关系，打印机进程发现没人打印的时候会进行sleep，而同学必须先发送一个request，然后打印机才开始打印，并且在之后也是打印机要先发送信号说明打印机打印已经完成，之后打印的同学才能离开，画了一张简单的图来说明关系

    

• Q2：上述关系可以抽象为几个进程？ 并写出伪代码描述。

  • 分为两个进程，打印机进程以及同学进程

  • 设计文档

    • 首先，用max_capacity来表示空闲的余量，初始化为n+1（等待区最多有n个位置，打印区1个），用信号量waiting来表示当前的等待区的余量，初始化为n

    • 其次，采取信号量mutual的方式来实现同学进程对于打印位置这一共享资源的互斥访问

    • 用信号量request和finish来实现打印机进程和同学进程之间的同步

      信号量	wait operation	signal operation
      max_capacity	student waits for a space	the printing student finish and leabe
      waiting	student waits for a spacec in the waiting queue	the first waiting student is going to execute the printing job
      mutual	the student waits that the resource to print	the student finish printing and the resource can be use
      request	the print process sleep until the resource is occupied	the printing student signals the printer to print
      finish	the student wait until the printer finish printing job	the printer signals the student printing job is finish

    • 同时我引入了waiting_on_line（）函数，在这里仅仅表示在队列中排队的过程，因为waiting这个信号量只是说在等待进入到waiting的队列中，但是实际上还需要等待前面的student进程打印完才行

    • 同上，引入printing_job（）函数来说明打印机进程完成打印的过程

    //######### Initialization #########
    semaphore mutual.count = 1;    // only one student process can enter the resource
    semaphore max_capacity.count = n + 1;
    semaphore waiting.count = n;
    semaphore request.count = 0;
    semaphore finish.coount = 0;
    
    void student()
    {
        wait(max_capacity); //进入打印店
        wait(waiting);         //开始排队
        waiting_on_line();
        signal(waiting);      //排队结束，准备访问对应的resource
        wait(mutual);         //对于访问的resource实现互斥
        signal(request);      //唤醒打印机进程来进行打印
        wait(finish);         //等待结束中
        signal(mutual);
    }
    
    void printer()
    {
        while (ture)
        {
            wait(request);    //等待唤醒，否则处于阻塞状态（休眠）
            printing_job();   //进行打印工作
            signal(finish);   //打印完了之后通知等待的学生打印工作完成
        }
        
    }

哲学家就餐问题

• 问题描述：

  ​ 由Dijkstra提出并解决的哲学家就餐问题是典型的同步问题。该问题描述的是五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替的进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。

• 解决思路：

  首先是异步和同步的区别，参考blog：同步和异步的区别及优缺点

  在这里不同的哲学家可以干不同的事情，采用异步的方式，用线程的方式来实现，最为基本的解决思路就是通过信号量来实现对筷子使用的互斥

  void philosopher (void* arg) {
      while (1) {
          think();
          hungry();
          pthread_mutex_lock(&chopsticks[left]);
          pthread_mutex_lock(&chopsticks[right]);
          eat();
          pthread_mutex_unlock(&chopsticks[left]);    
          pthread_mutex_unlock(&chopsticks[right]);
      }
  }

  但是可以发现，会引起死锁问题，当每一个哲学家都拿起了自己右/左边筷子的时候，会发现由于hold and wait，会引发死锁问题，开始考虑对于死锁问题的解决

  • 所以，在这里想到了的方法是限制哲学家同时拿一个方向上（如：左边）的筷子的人数数量，设置为4，这样当编号为4的哲学家想要拿左边编号为4的筷子的时候就进行了阻塞，此时编号为3的哲学家可以拿起右边的筷子进行吃饭

    具体代码附在后面（philosopher.c），运行截图如下

    

    #include "philosopher.h"
    
    void *philosopher(void *philosopherNumber) {
    	int i = (int) philosopherNumber;
    	while (1) {
    		think(i);       //the philosopher[i] start to think
    		//the philosopher[i] stop thinking
    		printf("Philosopher %d is hungry now\n",i);
    		pickUp(i);     //pick up the chopstick
    		eat(i);        //如果能执行到这一步而不阻塞在pickUp（），就说明已经获得了左右两根筷子，可以开始吃饭了
    		putDown(i);
    	}
    }
    
    void think(int philosopherNumber) {
    	int sleepTime = rand() % 3 + 1;
    	printf("Philosopher %d will think for %d seconds\n", philosopherNumber, sleepTime);
    	sleep(sleepTime);
    }
    
    void pickUp(int philosopherNumber) {
    	// request chopsticks
        //give the stick a sem and wait
    	sem_wait(&num);
    	pthread_mutex_lock(&chopsticks[philosopherNumber]);
    	pthread_mutex_lock(&chopsticks[((philosopherNumber + 1) % 5)]);
    }
    
    void eat(int philosopherNumber) {
    	int eatTime = rand() % 3 + 1;
    	printf("Philosopher %d will eat for %d seconds\n", philosopherNumber, eatTime);
    	sleep(eatTime);
    }
    
    void putDown(int philosopherNumber) {
    	// release chopsticks
        //signal() the chopstick
    	pthread_mutex_unlock(&chopsticks[philosopherNumber]);
    	pthread_mutex_unlock(&chopsticks[((philosopherNumber + 1) % 5)]);
    	sem_post(&num);
    }

提交说明

1，2相应的code在breakfast.cpp和print.cpp文件中，3的可执行文件为a.out