43313091操作系统课程设计指导书133301-133302

《操作系统课程设计》

一、课程内容及其学时分配、教学要求 (一)课程设计进度安排（课设时间为一周）：

第一天：教师讲解课程设计要求与题目，学生自愿组成小组，小组讨论选择题目、确定组员的分工，并做进度计划，及确定总体设计方案；

第二天：进行算法分析与设计，数据结构设计等，并完成部分模块编码； 第三天：编程实现算法；

第四天：测试系统，完成课程设计报告，教师安排好答辩时间及顺序； 第五天：答辩。

(二)教学要求

1、巩固和加深对处理机调度算法、进程互斥与同步、存储管理基本知识的理解，培养学生根据设计课题的需要，选用参考文献资料、查阅有关工程手册的技术数据图表、上网查阅相关文章、从网上下载相应资料等的能力，提高学生综合运用所学知识和独立解决工程问题的能力。

2、掌握用c语言或者java语言等，编程实现进程调度算法，实现内存管理，用信号量与P、V操作实现进程同步与互斥，提高学生的动手能力；并能在教师的指导下，完成设计任务。

3、通过课程设计实践，帮助学生逐步建立正确的科研观点、经济观点、全局观点。 4、初步掌握有关软件工程设计的方法、步骤，逐步熟悉开展技术设计的基本程序，为以后参与设计及研制新产品打下初步基础。

二、课程设计题目

课题一：进程调度算法。包括先到先服务算法、时间片轮转法、优先数调度算法、多级队列调度算法。模拟在单处理器情况下的进程调度，目的是加深对进程调度工作的理解，掌握不同调度算法的优缺点。

课题二：读者/写者问题与进程同步。理解临界区和进程互斥的概念，掌握用信号量和PV操作实现进程互斥的方法。要求学生用信号量和PV操作实现读者/写者问题的读者优先算法、写者优先算法和无优先算法。

课题三：哲学家就餐问题与死锁。理解死锁的概念，掌握死锁预防方法。死锁是进程并发执行过程中可能出现的现象，哲学家就餐问题是描述死锁的经典例子。

要求：在三个题目中任选一个题目完成。

三、课程设计分组

三名同学一组。

四、课程设计考核

综合考虑出勤、课设报告、程序、答辩情况。

设计题目1 进程调度算法

1.1 设计目的

进程管理是操作系统中的重要功能，用来创建进程、撤消进程、实现进程状态转换，它提供了在可运行的进程之间复用CPU的方法。在进程管理中，进程调度是核心，因为在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态，当就绪进程个数大于处理器数目时，就必须依照某种策略决定哪些进程优先占用处理器。本实验模拟在单处理器情况下的进程调度，目的是加深对进程调度工作的理解，掌握不同调度算法的优缺点。

下面回顾一下进程管理的相关内容。

1.1.1 进程控制块

为了管理和控制进程，系统在创建每一个进程时，都为其开辟一个专用的存储区，用以随时记录它在系统中的动态特性。而当一个进程被撤消时，系统就收回分配给它的存储区。通常，把这一存储区称为该进程的“进程控制块”（Process Control Block）。

由于PCB是随着进程的创建而建立，随着进程的撤消而取消的，因此系统是通过PCB来“感知”一个个进程的，PCB是进程存在的唯一标志。

随操作系统的不同，PCB的格式、大小以及内容也不尽相同。一般地，在PCB中大致应包括如下4方面的信息。

·标识信息：进程名等。

·说明信息：进程状态、程序存放位置、数据存放位置等。 ·现场信息：通用寄存器内容、控制寄存器内容、断点地址等。 ·管理信息：进程优先数、队列指针等。

1.1.2 进程控制块队列

在多道程序设计环境里，同时会创建多个进程。当计算机系统只有一个CPU时，每次只能让一个进程运行，其他的进程或处于就绪状态，或处于阻塞状态。为了对这些进程进行管理，操作系统要做三件事。 （1）把处于相同状态的进程的PCB，通过各自的队列指针链接在一起，形成一个个队列。通常有运行队列、就绪队列、阻塞队列。

（2）为每一个队列设立一个队列头指针，它总是指向排在队列之首的进程的PCB。 （3）排在队尾的进程的PCB，它的“队列指针”项内容应该为“NULL”，或一个特殊的符号，以表示这是该队的队尾PCB。

在单CPU系统中，任何时刻都只有一个进程处于运行状态，因此运行队列中只能有一个PCB；系统中所有处于就绪状态的进程的PCB排成一队，称其为“就绪队列”。一般地，就绪队列中会有多个进程的PCB排在里面，它们形成处理机分配的候选对象。如果就绪队列里没有PCB存在，则称该队列为空；所有处于阻塞状态进程的PCB，应该根据阻塞的原因进行排队，每一个都称为一个“阻塞队列”。比如等待磁盘输入/输出进程的PCB排成一个队列，等待打印机输出进程的PCB排成一个队列等。所以，系统中可以有多个阻塞队列，每个阻塞队列中可以有多个进程的PCB，也可以为空。

1.1.3 进程调度算法

进程调度算法用于确定就绪队列中的哪一个进程即将获得CPU。常用的进程调度算法有先来先服务法、时间片轮转法、优先数法等。

1．先来先服务调度算法

先来先服务调度算法的基本思想是：以到达就绪队列的先后次序为标准来选择占用处理机的进程。一个进程一旦占有处理机，就一直使用下去，直至正常结束或因等待某事件的发生而让出处理机。采用这种算法时，应该这样来管理就绪队列：到达的进程的PCB总是排在就绪队列末尾；调度程序总是把CPU分配给就绪队列中的第一个进程使用。

2．时间片轮转法

时间片轮转调度算法的基本思想是：为就绪队列中的每一个进程分配一个称为“时间片”的时间段，它是允许该进程运行的时间长度。在使用完一个时间片后，即使进程还没有运行完毕，也要强迫其释放处理机，让给另一个进程使用。它自己则返回到就绪队列末尾，排队等待下一次调度的到来。采用这种调度算法时，对就绪队列的管理与先来先服务完全相同。主要区别是进程每次占用处理机的时间由时间片决定，而不是只要占用处理机就一直运行下去，直到运行完毕或为等待某一事件的发生而自动放弃。

3．优先数调度算法

优先数调度算法的基本思想是：为每一个进程确定一个优先数，进程就绪队列按照优先数排序。

如何确定进程的优先数（也就是进程的优先级）？可以从如下几个方面考虑。 （1）根据进程的类型。系统中既有系统进程，又有用户进程。系统进程完成的任务是提供系统服务，分配系统资源，因此，给予系统进程较高的优先数能够提高系统的工作效率。 （2）根据进程执行任务的重要性。重要性和紧迫性高的进程应当被赋予较高的优先级。 （3）根据进程程序的性质。一个CPU繁忙的进程，由于需要占用较长的运行时间，影响系统整体效率的发挥，因此只能给予较低的优先数。一个I/O繁忙的进程，给予它较高的优先数后，就能充分发挥CPU和外部设备之间的并行工作能力。 （4）根据对资源的要求。系统资源有处理机、内存储器和外部设备等。可以按照一个进程所需资源的类型和数量，确定它的优先数。比如给予占用CPU时间短或内存容量少的进程以较高的优先数，这样可以提高系统的吞吐量。 （5）根据用户的请求。系统可以根据用户的请求，给予它的进程很高的优先数，作“加急”处理。

4． 多级队列调度算法

多级队列调度算法也称多级反馈队列调度算法，它是时间片调度算法与优先数调度算法的结合。实行这种调度算法时，系统中将维持多个就绪队列，每个就绪队列具有不同的调度级别，可以获得不同长度的时间片。例如，系统维持N个就绪队列，第1级就绪队列中进程的调度级别最高，可获得的时间片最短，第N级就绪队列中进程的调度级别最低，可获得的时间片最长。

具体的调度方法是：创建一个新进程时，它的PCB将进入第1级就绪队列的末尾。对于在第1级到第N-1级队列中的进程，如果在分配给它的时间片内完成了全部工作，那么就撤离系统；如果在时间片没有用完时提出了输入/输出请求或要等待某事件发生，那么就

进入相应的阻塞队列里等待。在所等待的事件出现时，仍回到原队列末尾，参与下一轮调度（也就是每个队列实行先来先服务调度算法）；如果用完了时间片还没有完成自己的工作，那么只能放弃对CPU的使用，降到低一级队列的末尾，参与那个队列的调度。对位于最后一个队列里的进程，实行时间片轮转调度算法。

整个系统最先调度1级就绪队列；只有在上一级就绪队列为空时，才去下一级队列调度。当比运行进程更高级别的队列中到达一个进程（可以肯定，在此之前比运行进程级别高的所有队列全为空）时，系统将立即停止当前运行进程的运行，让它回到自己队列的末尾，转去运行级别高的那个进程。

可以看出，多级队列调度算法优先照顾I/O繁忙的进程。I/O繁忙的进程在获得一点CPU时间后就会提出输入/输出请求，因此它们总是被保持在1、2级等较前面的队列中，总能获得较多的调度机会。对于CPU繁忙的进程，它们需要较长的CPU时间，因此会逐渐地由级别高的队列往下降，以获得更多的CPU时间，它们“沉”得越深，被调度到的机会就越少。但是，一旦被调度到，就会获得更多的CPU时间。

1.2 设计要求

1.2.1 界面要求

实验要求采用简单的控制台界面，包括一级功能菜单，如图1-1所示。

图1-1 界面要求

1.2.2 功能要求

实验应该包括以下功能：

1. 运行先来先服务进程调度算法； 2. 运行时间片轮转进程调度算法； 3. 运行优先数进程调度算法；

4. 运行多级反馈队列进程调度算法； 5. 显示就绪进程队列； 6. 显示运行进程队列； 7. 显示阻塞进程队列； 8. 创建新进程；

9. 10. 11. 12. 阻塞进程； 唤醒进程； 删除进程； 退出程序。

1.3 设计步骤

1.3.1 总体设计

确定程序包含多少个模块，每个模块有哪些功能、包括哪些函数，模块之间的调用关系如何。由于本实验并不复杂，所以只用一个模块实现。要求宏、数据结构、全局变量和函数原型放在头文件中，而函数实现放在源文件中。假设头文件名为process_schedule.h，源程序文件名为process_schedule.cpp。实验中用到的主要数据结构是进程控制块，其结构如图1-2所示。实验中用到1个宏和8个全局变量，如图1-3所示。实验中用到的主要函数有10个，如图1-4所示。

数据项 next process_name process_number process_start_moment process_need_time process_time_slice process_priority 作用 前向指针，指向下一个进程控制块，用来构成进程队列 进程名称 进程号，当进程有相同名称时，用来区分进程 进程启动时刻 进程要求运行时间 时间片 优先数 图2-2 进程控制块

全局变量名称 作用 MAX_PROCESS 程序最多能处理的进程数 process_number pcb_table pcb_run pcb_free pcb_ready pcb_ready_rear pcb_blocked 存放下一个被创建进程的进程号 进程控制块表 进程运行队列头指针 进程空闲队列头指针 进程就绪队列头指针 进程就绪队列尾指针 进程阻塞队列头指针 pcb_blocked_rear 进程阻塞队列尾指针 图2-3 宏和全局变量

函数名称 main 作用 初始化进程队列，并管理主菜单命令

init_pcb_table display_process_queue create_process block_process_by_name wakeup_process FCFS RR HPF MFBQ 初始化进程空闲队列 以表格的形式显示进程队列 创建进程 阻塞进程 唤醒进程 先进先出进程调度算法 时间片轮转进程调度算法 优先数进程调度算法 多级反馈队列进程调度算法 图2-4 函数名称及作用

1.3.2 详细设计及实现

1. 头文件

头文件中含有图1-2、图1-3和图1-4的内容。

#include #include #include #include #include

#define MAX_PROCESS 10

int process_number=0; //下一个可用的进程编号

typedef struct pcb{

struct pcb *next; //下一个进程控制块指针 char process_name[20]; //进程名 int process_number; //进程编号 int process_start_moment; //进程启动时刻 int process_need_time; //要求运行时间 int process_time_slice; //时间片 int process_priority; //优先数

}PCB; //自定义数据类型：进程控制块 PCB pcb_table[MAX_PROCESS]; //进程控制块表

PCB *pcb_run=NULL; //进程运行队列头指针 PCB *pcb_free=NULL; //进程空闲队列头指针 PCB *pcb_ready=NULL; //进程就绪队列头指针 PCB *pcb_ready_rear=NULL; //进程就绪队列尾指针 PCB *pcb_blocked=NULL; //阻塞队列头指针 PCB *pcb_blocked_rear=NULL; //阻塞队列尾指针

void init_pcb_table( ); //初始化进程控制块表 void print_space(int num); //显示若干个空格 void display_process_queue(PCB *queue); //显示进程队列

PCB *create_process( ); //创建进程函数,成功时返回新创建进程的PCB,失败时返回NULL。

void block_process_by_name( ); //阻塞指定名称的进程。 void wakeup_process( ); //唤醒进程

void FCFS( ); //先来先服务进程调度算法 void RR( ); //时间片轮转进程调度算法

void HPF( ); //优先数进程调度算法

void MFBQ( ); //多级反馈队列进程调度算法

2. 主函数main

主函数用来初始化进程队列，显示菜单，接收用户输入的菜单选项，并根据用户的选项执行相应的功能。其处理流程如下： main( ){

初始化进程控制块表； while(1){

显示菜单； 输出提示信息；

接收用户输入的选项，如果输入不是数字1~8或者字母a~d则重新输入； switch(选项){ case ?1?： 调用先来先服务进程调度算法； break； case ?2?： 调用时间片轮转进程调度算法； break； case ?3?： 调用优先数进程调度算法； break； case ?4?： 调用多级反馈队列进程调度算法； break； case ?5?： 显示就绪进程队列； break； case ?6?： 显示阻塞进程队列； break； case ?7?： 显示运行进程队列； break； case ?a?： 调用创建进程函数； break； case ?b?： 调用删除进程函数； break； case ?c?： 调用阻塞进程函数； break； case ?d?： 调用唤醒进程函数； break； case ?8?： 返回； } }

返回；

}

说明：通常用循环语句和多分支语句实现菜单。while语句实现菜单的循环选择，switch语句实现功能分支，只有当用户输入数字8时，才会跳出循环，结束程序的执行，输入其它

合法数字或者字符时，程序将执行对应的功能，并在执行完功能后，重新显示菜单，供用户做下一步选择。

main函数的源代码如下：

#include \ //包含头文件 int main(int argc,char *argv[ ]){ char select; //存放用户选择的菜单项 init_pcb_table( ); //初始化进程控制块表 while(1){ printf(\ MENU-------------|\\n\ //显示菜单项 printf(\ 1:first come first served |\\n\ printf(\ 2:round robin |\\n\ printf(\ 3:highest priority first |\\n\ printf(\ 4:multi_level feedback queue |\\n\ printf(\ 5:display ready process queue |\\n\ printf(\ 6:display blocked process queue |\\n\ printf(\ 7:display running queue |\\n\ printf(\ a:create a process |\\n\ printf(\ b:delete a process |\\n\ printf(\ c:block a process |\\n\ printf(\ d:wakeup a process |\\n\ printf(\ 8:exit |\\n\ printf(\ printf(\ //输出提示信息 do{ select=(char)getch( ); //接收用户的选项 }while(!((49<=select&&select<=56)||(97<=select&&select<=100))); system(\ //清屏 switch(select){ //由选项控制程序功能 case '1': FCFS( ); break; case '2': RR( ); break; case '3': HPF( ); break; case '4': MFBQ( ); break; case '5': printf(\ ready queue\\n\ display_process_queue(pcb_ready); break; case '6': printf(\ blocked queue\\n\ display_process_queue(pcb_blocked); break; case '7': printf(\ running queue\\n\ display_process_queue(pcb_run); break; case 'a': create_process( ); break; case 'b': break;

}

case 'c': block_process_by_name( ); break; case 'd': wakeup_process( ); break; case '8': return 0; } printf(\ getch( ); system(\}

return 0;

有了头文件和主函数就可以编译、链接并运行程序，测试程序的主菜单是否正常工作。现在运行程序，可以看到程序仅仅显示一个主菜单，如果你选择1~7和a~e项对应的功能，该程序不会有所反应，因为你还没有编写相关的功能函数。如果你选择8，则程序终止执行。这说明主菜单能正常工作。此后，你可以每实现一个函数就测试程序是否正确，如果不正确则修改这个函数，直到它正确为止；如果正确，则实现下一个函数。如此每次实现一个函数，直到所有函数都正确实现，直到整个程序能正确执行。 3. 进程控制块表的初始化函数init_pcb_table( )

该函数用来给进程控制块表即数组pct_table赋初值，并且将数组元素从头到尾串成链表，形成进程空闲队列。每个数组元素的初值为：进程名为空字符串，进程启动时刻为0，要求运行时间为0，时间片为0，优先数为0。初始化完成后的进程控制块表如图1-5所示。

数组 进程 进程 启动 要求 指针 时间片 优先数 下标 名称 编号 时刻 时间 pcb_free 0 0 0 0 0 0

1 0 0 0 0 0

2 0 0 0 0 0

…… 0 0 0 0 0

9 null 0 0 0 0 0

图1-5 初始进程空闲队列 void init_pcb_table( ) { int i=0; pcb_free=&pcb_table[0]; pcb_table[MAX_PROCESS-1].next=NULL;

pcb_table[MAX_PROCESS-1].process_number=0; pcb_table[MAX_PROCESS-1].process_start_moment=0;

pcb_table[MAX_PROCESS-1].process_need_time=0; pcb_table[MAX_PROCESS-1].process_time_slice=0; pcb_table[MAX_PROCESS-1].process_priority=0; strcpy(pcb_table[MAX_PROCESS-1].process_name,\ for(i=0;i

pcb_table[i].process_start_moment=0; pcb_table[i].process_need_time=0;

pcb_table[i].process_time_slice=0; pcb_table[i].process_priority=0;

strcpy(pcb_table[i].process_name,\

} }

4. 进程队列输出函数display_process_queue( )

该函数有一个输入参数用来指明要显示的进程队列的对首。

在vc++6.0的控制台程序中不能直接控制光标，要想显示整齐的表格，需要自己设计相关函数，我们设计一个print_space( )函数用来输出若干个空格，以便对齐文本。

void print_space(int num){ int i; for(i=0;i

//以表格的形式显示由queue指出的进程队列

void display_process_queue(PCB *queue) { PCB *p=queue; //用来遍历进程队列的指针 char buffer[10]; //将整数转换成字符串时用到的缓冲区 printf(\ //显示表头 printf(\ | number | start | need | slice | priority |\\n\ printf(\ while(p!=NULL){ //显示队列中的每个节点 printf(\ printf(\ //显示进程名称 print_space(23-strlen(p->process_name)); //右边用空格补齐 printf(\ printf(\ //显示进程号 itoa(p->process_number,buffer,10); //整数转换成字符串 print_space(8-strlen(buffer)); printf(\ printf(\ //显示进程启动时刻 itoa(p->process_start_moment,buffer,10); print_space(6-strlen(buffer)); printf(\ printf(\ //显示进程要求运行时间 itoa(p->process_need_time,buffer,10); print_space(5-strlen(buffer)); printf(\ printf(\ //显示时间片 itoa(p->process_time_slice,buffer,10); print_space(6-strlen(buffer)); printf(\ printf(\ //显示优先数 itoa(p->process_priority,buffer,10); print_space(10-strlen(buffer)); printf(\ p=p->next; //指针下移一个节点 }

do{ select=(char)getch(); }while(select!='1'&&select!='2'&&select!='3'&&select!='4'); system(\ switch(select){ case '1': deadlock(); break; case '2': ordered_allocation(); break; case '3': pre_alloction(); break; case '4': return 0; } printf(\ getch(); system(\}

return 0;

}

3.3.4 测试程序

图3-2 程序主界面

图3-3 死锁情况

程序运行的主界面如图32所示，输入1后，可以看到屏幕输出一些提示信息后就不再更新了，程序也停止不动了，这说明发生了死锁，如图3-3所示。分析提示信息可以了解死锁的详情，即每个哲学家都得到了左边的筷子，又都在等待右边的筷子。按ctrl+c终止程序。重新运行程序，输入2或者3，可以看到屏幕一直更新提示信息，说明没有死锁发生，程序将一直运行下去，要想结束程序必须按ctrl+c。

(LPTHREAD_START_ROUTINE)(FIFO_writer_thread), &test_data[i],0,NULL);

} WaitForMultipleObjects(MAX_THREAD,h_thread,TRUE,-1); printf(\}

//写者优先时的读者线程

void WF_reader_thread(void *data){ char thread_name[3]; strcpy(thread_name,((TEST_INFO *)data)->thread_name); Sleep(((TEST_INFO *)data)->require_moment*1000); WaitForSingleObject(h_mutex_reader_wait,-1); WaitForSingleObject(h_mutex_first_reader_wait,-1); WaitForSingleObject(h_mutex_read_count,-1); read_count++; if(read_count==1) EnterCriticalSection(&CS_DATA); ReleaseMutex(h_mutex_read_count); ReleaseMutex(h_mutex_first_reader_wait); ReleaseMutex(h_mutex_reader_wait); printf(\ Sleep(((TEST_INFO *)data)->persist_time*1000); WaitForSingleObject(h_mutex_read_count,-1); read_count--; if(read_count==0) LeaveCriticalSection(&CS_DATA); ReleaseMutex(h_mutex_read_count); }

//写者优先时的写者线程

void WF_writer_thread(void *data){ Sleep(((TEST_INFO *)data)->require_moment*1000); WaitForSingleObject(h_mutex_write_count,-1); if(write_count==0) WaitForSingleObject(h_mutex_first_reader_wait,-1); write_count++; ReleaseMutex(h_mutex_write_count); EnterCriticalSection(&CS_DATA); printf(\ Sleep(((TEST_INFO *)data)->persist_time*1000); LeaveCriticalSection(&CS_DATA); WaitForSingleObject(h_mutex_write_count,-1); write_count--; if(write_count==0) ReleaseMutex(h_mutex_first_reader_wait); ReleaseMutex(h_mutex_write_count); }

//写者优先时的初始化程序 void writer_first(){ int i=0; HANDLE h_thread[MAX_THREAD]; printf(\写优先申请次序：\ for(i=0;i

printf(\

printf(\写优先操作次序：\

InitializeCriticalSection(&CS_DATA);

for(i=0;i

(NULL, 0,

(LPTHREAD_START_ROUTINE)(WF_reader_thread), &test_data[i],0,NULL);

else h_thread[i]=CreateThread

(NULL, 0,

(LPTHREAD_START_ROUTINE)(WF_writer_thread), &test_data[i],0,NULL);

} WaitForMultipleObjects(MAX_THREAD,h_thread,TRUE,-1); printf(\}

//主程序

int main(int argc,char *argv[]){ char select; while(1){ printf(\ printf(\ 1:reader first |\\n\ printf(\ 2:first come first served |\\n\ printf(\ 3:writer first |\\n\ printf(\ 4:exit |\\n\ printf(\ printf(\ do{ select=(char)getch(); }while(select!='1'&&select!='2'&&select!='3'&&select!='4'); system(\ switch(select){ case '1': reader_first(); break; case '2': first_come_first_served(); break; case '3': writer_first(); break; case '4': return 0; } printf(\ getch(); system(\ } return 0; }

2.3.5 测试程序

程序开始界面如下：

这是程序的主菜单，输入1运行读者优先演示部分，输入2运行无优先演示部分，输入3运行写者优先演示部分，输入4退出程序的执行 ，回到DOS命令提示符。

输入1之后，将看到程序缓慢运行（运行约一分钟），等到所有线程都运行结束后，屏幕输出如下：

屏幕第一行给出申请访问文件的次序，第二行给出实际读写文件的次序。可以看出程序的运行结果与预期的一致，当读者和写者都等待使用共享文件时，优先选择读者运行。这证明程序是正确的。同学们还可以设计其它的测试数据来运行该程序。

在此状态下，按任意键将回到主菜单。在主菜单中输入2，同样会看到程序缓慢运行（运行约一分钟），等到所有线程都运行结束后，屏幕输出如下：

可见，当读者和写者都等待使用共享文件时，按照谁先等待谁先运行的原则选择线程。在此状态下，按任意键将回到主菜单。在主菜单中输入3，同样会看到程序缓慢运行（运行约一分钟），等到所有线程都运行结束后，屏幕输出如下：

可见，当读者和写者都等待使用共享文件时，优先选择写者运行。在此状态下，按任意键将回到主菜单。在主菜单中输入4，结束程序的运行。

设计题目3 哲学家就餐问题与死锁

3.1 设计目的

理解死锁的概念，掌握死锁预防方法。

死锁是进程并发执行过程中可能出现的现象，哲学家就餐问题是描述死锁的经典例子。假设有几位哲学家围坐在一张餐桌旁，桌上有吃不尽的食品，每两位哲学家之间摆放着一根筷子，筷子的个数与哲学家的数量相等，每一位哲学家要么思考，要么等待，要么拿起左右两根筷子进餐。本实验假设有五个哲学家和五根筷子，它们的编号都是从0到4。 如果每位哲学家都拿起左边的筷子，就会发生死锁。

为了防止死锁，可以采用资源预分配法或者资源按序分配法。资源预分配法是指进程在运行前一次性地向系统申请它所需要的全部资源，如果系统当前不能够满足进程的全部资源请求，则不分配资源, 此进程暂不投入运行，如果系统当前能够满足进程的全部资源请求, 则一次性地将所申请的资源全部分配给申请进程。资源按序分配法是指事先将所有资源类全排序, 即赋予每一个资源类一个唯一的整数，规定进程必需按照资源编号由小到大的次序申请资源。

在哲学家就餐问题中，要采用资源预分配法只需让每个哲学家同时申请左右两根筷子。要采用资源按序分配法只需规定每个哲学家先申请左右两根筷子中编号小的筷子，再申请编号大的筷子。

3.2 设计要求

利用多线程技术编写哲学家就餐程序，使之在运行时能演示产生死锁的情况，也能演示采用死锁防止方法后不产生死锁的情况。 程序要采用简单的控制台界面，运行后在屏幕上显示功能菜单，列出该程序具有的功能，供用户选择，用户选择功能后应该转到相应的处理程序。程序应该包括以下功能：

（1）演示死锁现象；

（2）通过资源按序分配法防止死锁； （3）通过资源预分配法防止死锁； （4）退出。

3.3 设计步骤

3.3.1 程序结构设计

程序需要六个线程，主线程用于显示主菜单，接收用户的功能选择；五个哲学家线程用于模拟哲学家的活动，即不停地思考、饥饿、进食。相邻的两个哲学家线程需要共享他们中间的同一根筷子，因此对每一根筷子的使用要互斥，用互斥体数组h_mutex_chopsticks来实现。主线程创建五个哲学家线程后要等待所有哲学家结束，用线程句柄数组h_thread来表示五个线程，主线程通过等待这五个线程句柄来实现同步。

该程序共有7个函数，这些函数可以分成4组。各组包含的函数及其功能如图3-1所示。 组别 一 二 main() deadlock_philosopher() deadlock() ordered_allocation_philosopher() ordered_allocation() pre_allocation_philosopher() pre_allocation() 包括函数 函数功能 显示主菜单，接收用户的选择并执行相应的功能。 演示死锁情况的哲学家线程函数 初始化函数：创建五个哲学家并等待它们结束 通过按序分配法防止死锁的哲学家线程函数 初始化函数：创建五个哲学家并等待它们结束 通过预先分配法防止死锁的哲学家线程函数 初始化函数：创建五个哲学家并等待它们结束 图3-1 函数及其功能

三 四

3.3.2 算法设计

下面给出主要函数的算法描述。 （1）deadlock_philosopher函数

{

while(1){

随机等待一段时间；

提示等待左边筷子； 申请左边筷子； 随机等待一段时间； 提示等待右边筷子； 申请右边筷子； 提示正在进餐； 放下左边筷子；

放下右边筷子；

} }

（2）ordered_allocation_philosopher函数

{

while(1){

随机等待一段时间；

提示等待左右两边编号较小的筷子； 申请编号较小的筷子； 随机等待一段时间； 提示等待左右两边编号较大的筷子； 申请编号较大的筷子； 提示正在进餐； 放下编号较小的筷子；

放下编号较大的筷子；

} }

（3）pre_allocation_philosopher函数

{

while(1){ 提示等待左边筷子； 提示等待右边筷子；

本文来源：https://www.bwwdw.com/article/t8zd.html