操作系统课程设计--用多线程同步方法解决睡眠理发师问题(Sleeping-Barber-Problem).doc

题目: 用多线程同步方法解决睡眠理发师问题（Sleeping-Barber Problem)
初始条件：
1． 操作系统：Linux
2． 程序设计语言：C语言
3. 设有一个理发师，5把椅子（另外还有一把理发椅），几把椅子可用连续存储单元。
要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
1．技术要求：
1）为每个理发师／顾客产生一个线程，设计正确的同步算法
2）每个顾客进入理发室后，即时显示“Entered” 及其线程自定义标识，还同时显示理发室共有几名顾客及其所坐的位置。
3）至少有10个顾客，每人理发至少3秒钟。
4）多个顾客须共享操作函数代码。

2． 设计说明书内容要求：
1)设计题目与要求
2)总的设计思想及系统平台、语言、工具等。
3）数据结构与模块说明（功能与流程图）
4）给出用户名、源程序名、目标程序名和源程序及其运行结果。（要注明存储各个程序及其运行结果的主机IP地址和目录。）
5）运行结果与运行情况
（提示: (1)连续存储区可用数组实现。
(2)编译命令可用：　cc -lpthread -o 　目标文件名　　源文件名
(3)多线程编程方法参见附件。）

1设计题目与要求
1.1 设计题目
用多线程同步方法解决睡眠理发师问题（Sleeping-Barber Problem)
1.2 设计要求
1.2.1 初始条件
（1）操作系统：Linux
（2）程序设计语言：C语言
（3）设有一个理发师，5把椅子（另外还有一把理发椅），几把椅子可用连续存储单元。
1.2.2 技术要求
（1）为每个理发师／顾客产生一个线程，设计正确的同步算法
（2）每个顾客进入理发室后，即时显示“Entered” 及其线程自定义标识，还同时显示理发室共有几名顾客及其所坐的位置。
（3）至少有10个顾客，每人理发至少3秒钟。
（4）多个顾客须共享操作函数代码。
2 总体设计思想及开发环境与工具
2.1 总体设计思想
题目中要求描述理发师和顾客的行为，因此需要两类线程barber()和customer ()分别描述理发师和顾客的行为。其中，理发师有活动有理发和睡觉两个事件；等待和理发二个事件。店里有固定的椅子数，上面坐着等待的顾客，顾客在到来这个事件时，需判断有没有空闲的椅子，理发师决定要理发或睡觉时，也要判断椅子上有没有顾客。所以，顾客和理发师之间的关系表现为：
（1）理发师和顾客之间同步关系：当理发师睡觉时顾客近来需要唤醒理发师为其理发，当有顾客时理发师为其理发，没有的时候理发师睡觉。
（2）理发师和顾客之间互斥关系：由于每次理发师只能为一个人理发，且可供等侯的椅子有限只有n把，即理发师和椅子是临界资源，所以顾客之间是互斥的关系。
（3）故引入3个信号量和一个控制变量：
ⅰ控制变量waiting用来记录等候理发的顾客数，初值为0；
ⅱ信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为0；
ⅲ信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为1； ⅳ信号量mutex用于互斥，初值为1
2.2 多线程编程原理
此次在Linux下进行多线程编程需要用到pthread_create和pthread_join这两个函数。
2.2.1 创建一个线程
pthread_create用来创建一个线程，原型为：
extern int pthread_create((pthread_t *__thread, __const pthread_attr_t *__attr,void *(*__start_routine) (void *), void *__arg))
第一个参数为指向线程标识符的指针，第二个参数用来设置线程属性，第三个参数是线程运行函数的起始地址，最后一个参数是运行函数的参数。函数thread不需要参数时，最后一个参数设为空指针。第二个参数设为空指针时，将生成默认属性的线程。创建线程成功后，新创建的线程则运行参数三和参数四确定的函数，原来的线程则继续运行下一行代码。
2.2.2 等待一个线程结束
pthread_join用来等待一个线程的结束，函数原型为：
extern int pthread_join __P ((pthread_t __th, void **__thread_return));
第一个参数为被等待的线程标识符，第二个参数为一个用户定义的指针，它可以用来存
储被等待线程的返回值。这个函数是一个线程阻塞的函数，调用它的函数将一直等待到被
等待的线程结束为止，当函数返回时，被等待线程的资源被收回。
2.2.3 信号量
（1）函数sem_init（）用来初始化一个信号量，函数原型为：
extern int sem_init __P ((sem_t *__sem, int __pshared, unsigned int __value));
sem为指向信号量结构的一个指针；pshared不为０时此信号量在进程间共享，否则只能为当前进程的所有线程共享；value给出了信号量的初始值。
（2）函数sem_post( sem_t *sem )用来增加信号量的值。
当有线程阻塞在这个信号量上时，调用这个函数会使其中的一个线程不在阻塞，选择机制同样是由线程的调度策略决定的。
（3）函数sem_wait( sem_t *sem )被用来阻塞当前线程直到信号量sem的值大于0，解除阻塞后将sem的值减一，表明公共资源经使用后减少。函数sem_trywait ( sem_t *sem )是函数sem_wait（）的非阻塞版本，它直接将信号量sem的值减一。
2.3 伪码实现
difine n 5； //为顾客准备的椅子数为5
semaphore mutex=1； //用于互斥
semaphore customers=0；//等候理发的顾客数
semaphore barbers=1；//正在等候顾客的理发师数
int waiting=0； //等候理发的顾客数
//理发师线程
void barber()
{
while(true) //判断有无顾客
{
wait(customers); //若无顾客,理发师睡眠
wait(mutex); //互斥
waiting--; //等候顾客数少一个
signal(mutex); //释放临界资源
signal(barber); //理发师去为一个顾客理发
cut_hair; //正在理发
}
}
//顾客线程
void customer()
{
wait(mutex); //互斥
if (waiting<n) //如果有空椅子，则等待
{
waiting++; //等候顾客数加1
signal(mutex); //释放临界资源
signal(customers); //如果理发师睡觉，唤醒理发师
wait(barber); //理发师在理发, 顾客等候
get_haircut; //顾客坐下等理发师
}
else
signal(mutex); //店里人满了,顾客离开
}
}
2.4 开发环境与工具
系统平台：LINUX环境
实现语言：C语言
开发工具：NANO编辑器
3数据结构与模块说明
3.1 数据结构
通过分析课程设计要求，定义以下的数据:
sem_t mutex,customers,barbers; //design three semaphores: mutex,customer,barbers
int waiting=0; //the number of waiting customers
int chair[5];
3.2程序模块说明
3.2.1主函数模块
主函数流程图如下：

3.2.2 理发师模块
理发师模块函数流程图如下：

3.2.3 顾客模块
顾客模块函数流程图如下：

源程序代码
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<pthread.h>
#include<semaphore.h>
#include<fcntl.h>
#include<errno.h>
#define n 5 //the shop have five chairs

//design three semaphores: mutex,customer,barbers
sem_t mutex,customers,barbers;
int waiting=0; //the number of waiting customers
int chair[5];
void * barber();
void * customer(void *arg);

int main(int argc,char *argv[])
{
//create 10 semaphores and one Barber semaphore
pthread_t Customer_id[10],Barber_id;
int i;
sem_init(&mutex,0,1); //init mutex semaphore to 1
sem_init(&customers,0,0);//init semaphore customers to 0
sem_init(&barbers,0,1);

for(i=0;i<5;i++)
pthread_create(&Barber_id,NULL,(void*)barber,NULL);
for (i=0;i<10;i++)
pthread_create(&Customer_id[i],NULL,(void*)customer,(void*)(i+1));
for (i=0;i<10;i++)
pthread_join(Customer_id[i],NULL);
for(i=0;i<5;i++)
pthread_join(Barber_id,NULL);
return 0;
}

//creat barber pthread
void * barber()
{
int i;
int next;
//wait(customers),if no customers,barber sleeping
sem_wait(&customers);
sem_wait(&mutex); //wait(mutex)
waiting--; //the numer of waiting reduce one
for(i=0;i<5;i++)
{
if (chair[i]!=0)
{
next= chair[i];
chair[i]=0;
break;
}
}
printf("The barber is cutting %dth customer's hair\n",next);
sleep(3);
sem_post(&mutex);
sem_post(&barbers);
}

//creat customer pthread
void * customer(void *arg)
{
int i;
sem_wait(&mutex); //wait(mutex) if(waiting<n)
if(waiting<n)
{

waiting++; //the numer of waiting plus one
for(i=0;i<5;i++)
{
if (chair[i]==0)
{
chair[i]=(int)arg;
break;
}
}

printf("***************************************************\n");
printf("Entered:Number %d customer comes,and sits at %d chair \n",(int)arg,(i+1));
printf("There are %d customer on the chair\n",waiting);
printf("The customers' location are:");
for(i=0;i<5;i++)
printf("%d ",chair[i]);
printf("\n");

sleep(1);
sem_post(&mutex); //signal(mutex)
sem_post(&customers); //signal(customers)
sem_wait(&barbers); //wait(barbers)
}
else
{
printf("Number %d comes,there are no chairs,the customer %d is leaving\n",(int)arg,(int)arg);
sem_post(&mutex);
}
}

5.2.1 编辑，编译和运行的过程图

\

5.2.2 错误部分截图

5.2.3 正确运行结果图
第一次运行结果如下图：

第二次运行结果如下图：

第三次运行结果如下图；

6调试记录
6.1调试记录
周一因有培训与课设时间冲突，故没有上机操作，查阅了相关书籍，并在网上查找了相关资料，了解了linux多线程编程的原理，应注意的问题，及一些常用命令
周二先设计出了该程序的伪代码即其wait、signal操作。然后，根据其要求进行编程，由于使用的是多线程编程，开始进行编译的时候，编译命令输入错误，没有输入-lpthread，程序总是出现错误。同时，创建线程函数时，由于对其格式输入错误导致程序无法运行。例如sb.c，sb1.c等都为本次调试时的程序。
周三主要是不断的调试并完善程序。程序可以运行，但与要求总有些不符，故不断的进行修改，并对其输出的格式进行完善，使其输出看起来美观一些，容易观察一些。例如s.c，b.c等程序为此次调试结果。
周四主要是在原有代码的基础上，使程序更完整些。并进行结果的截图，开始设计并编写课程设计报告。
6.2自我评析和总结
通过本次编程我熟悉了linux 下的多线程编程和信号量实现wait、signal操作的全过程，对同步和互斥问题也有了更深一步的理解，同时，也使我对linux编程有了更多的了解，在很多方面，它与在windows下编程有着很大的不同，对与多线程来说更方便一些。
设计过程中也遇到不少困难，尤其是对于多线程的实现，结果总是不如想象中完美。比如其顾客编号的输出有时会不按顺序，输入有点乱。另外，有时，输出结束后，程序仍无法结束，必须强制性关闭终端才可以结束程序，这是本程序的一个不足之处。
在本次课程设计中我深深感觉到自己掌握的知识还远远不够，我明白光是知道书本上的知识是远远不够的，一定要把理论知识和实践结合起来。同时，要多多学习linux的操作。