2016操作系统课程设计指导书v1 南京廖华答案网

2016操作系统课程设计指导书v1 下载本文

文章发布时间 : 2024/11/14 16:21:10星期四

操作系统课程设计指导书

操作系统课程组

长春工业大学 2016-10-28

前言

操作系统课程是计算机科学与技术专业以及相关专业的必修课，在课程体系中占有重要地位。操作系统本身具有概念抽象、结构复杂和难于掌握的特点，要想掌握操作系统精髓，不仅要做适量的习题，更重要的是动手设计。通过设计，可以加深对基本原理的理解，激发学习兴趣，增强自信心。

本指导书具有以下特点： ·设计题目难度和容量适中

操作系统课程在一个学期内讲完，课内的设计学时为2周54。按照操作系统的知识体系，需要安排5个设计，这就要求设计既覆盖教学内容，又能在规定学时内做完。本书的设计题目难度和容量适中，能满足设计教学要求。

·精心设计测试数据、大量使用图表

对每一个设计题目都精心设计了测试数据，并详细地分析程序在该测试数据下运行的正确结果是什么。分析的过程就是对操作系统相关知识的复习过程。在分析过程中大量使用图表，不仅帮助学生一步一步地理解教学内容，而且培养了学生利用形象化方法学习抽象内容的能力。

·并发程序设计技术贯穿本书

并发程序设计技术是操作系统设计的精髓，也是当今大多数系统软件和应用软件设计的精髓。学生在其他课程中很少有机会训练并发程序设计能力。其它操作系统试验教材对该技术的训练也不充分，只在涉及进程同步的设计中使用。

·融入软件工程思想

对于每一个设计题目，尽量采用软件工程的原理和方法来分析、设计和实现，从而锻炼学生研制大型软件的能力。

设计1：动态异长分区的存储分配与回收算法。编写一个程序，模拟操作系统对动态异长分区的存储分配与回收算法。

设计2：哲学家就餐问题与死锁。要求学生设计哲学家就餐程序，该程序能演示哲学家死锁情况，也能演示采用死锁预防方法解除死锁的情况。

设计3：假脱机打印程序与虚拟设备。设计一个程序模拟虚拟设备的工作原理。

设计4：读者写者问题与进程同步。要求给出多种解法，包括读者优先、写者优先和无优先的解法。

设计5：索引文件，计算在混合索引文件的组织方式下，一个文件的最大容量。

课程设计任务书 ................................................................................................. 1 设计1 动态异长分区的存储分配与回收算法 .............................................. 2 设计2 哲学家就餐问题与死锁 .................................................................... 24 设计3 假脱机打印程序与虚拟设备 ............................................................ 34 设计4 读者/写者问题与进程同步 ............................................................... 44 设计5 索引文件 ............................................................................................ 54 附录1 windows API ...................................................................................... 55 主要参考文献 ................................................................................................... 61

课程设计任务书

课程设计题目：资源管理软件的设计起止日期：2016.12.19-2016.12.30 设计任务及日程安排：设计地点：计算机科学与工程学院机房设计任务： 1. 分析动态异长分区的分配算法，并进行功能扩充； 2. 分析哲学家就餐问题与死锁，并进行功能扩充； 3. 分析假脱机打印程序与虚拟设备，并进行功能扩充； 4. 分析读者/写者问题，并设计新的测试数据进行测试； 5. 编程计算索引文件的最大容量。说明：第1、4题每位同学必须完成，第2、3、5题任选其二即可。日程安排：本次设计共二周时间，日程安排如下：第1-2天：分析动态异长分区的分配算法，并进行功能扩充，编写设计报告；第3-4天：完成第一个任选题的分析与功能扩充，编写设计报告；第5天：第一阶段答辩。第6-7天：分析读者/写者问题，并设计新的测试数据进行测试，编写设计报告；第8-9天：完成第二个任选题，编写设计报告；第10天：第二阶段答辩。设计报告要求： 1．每个题目编写一份设计报告，每位同学独立完成。 2．针对每个题目分析的部分给出算法流程，功能扩充的部分给出算法流程和源代码。指导教师安排：侯秀萍 140401 郑虹 140402 吕寻才 140403 焦素云 140407 1

设计1 动态异长分区的存储分配与回收算法

1.1 设计目的

理解存储管理的功能，掌握动态异长分区的存储分配与回收算法。

存储器是计算机系统中的关键资源，存储管理一直是操作系统的最主要功能之一。存储管理既包括内存资源管理，也包括用于实现分级存储体系的外存资源的管理。通常，内存与外存可采用相同或相似的管理技术，如内存采用段式存储管理，则外存也采用段式存储管理。存储管理需要完成如下功能：存储分配、存储共享、存储保护、存储扩充、地址映射。

当一个作业进入内存时，由操作系统将其变为进程,并为进程分配存储空间。进程运行结束时, 由操作系统将其所占用的存储空间收回。

不同的操作系统对内存空间的划分与分配方法是不同的，通常分为两类：静态等长分区的分配和动态异长分区的分配。静态等长分区常用于页式存储管理方式与段页式存储管理方式，存储空间被静态地划分为若干个长度相等的区域，每个区域被称作一个页面。动态异长分区常用于界地址存储管理方式与段式存储管理方式，存储空间被动态地划分为若干个长度不等的区域。

1.2 设计要求

本设计要求模拟动态异长分区的分配算法、回收算法和碎片整理算法。 1.3 设计步骤

1.3.1 数据结构分析

为了实现存储资源的分配和回收，

空闲区域首址空闲区域长度操作系统需要记录内存资源使用情况，即哪些区域尚未分配，哪些区域已经分? ? 配以及分配给哪些进程等。为此一般需

addr size 要两个表，一个为分配表, 另外一个为

? ? 空闲区域表。前者记录已经分配的区域,

后者记录着所有当前未被进程占用的空

图1-1 空闲区域表

闲区域, 如图1-1所示。

显然, 没有记录于表中的区域即为已被进程所占用的非空闲区域，在实际的操作系统中，这些区域登记在进程的PCB中。而PCB中除了关于内存资源的信息外，还有其它大量信息。

由于本设计是对存储管理算法的模拟，所以用一个线程来代表一个进程，用线程驻留区域表来描述线程占用的内存空间，如图1-2所示。

线程名称驻留区始址驻留区大小 a b

0 20 2

10 20 …… …… 图1-2 线程驻留区表

…… 同时，需要一张表来记录各个线程对内存的请求信息，如图5-3所示。

线程名称 thread_1 thread_2 …… 请求大小(KB) 20 10 …… 图1-3 内存申请表

预计驻留时间( 秒) 4 5 …… 1.3.2 算法分析

常用的动态异长分区的分配算法有：最先适应算法、最佳适应算法和最坏适应算法。

1. 最先适应算法(First Fit，FF)

对于存储申请命令, 选取满足申请长度要求且起始地址最小的空闲区域。在实现时, 可将系统中所有的空闲区域按照起始地址由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时, 系统由表的头部开始查找, 取第一个满足要求的表目。如果该表目所对应的区域长度恰好与所申请的区域长度相同, 则将该区域全部分配给申请者。否则将该区域分割为两部分, 一部分的长度与所申请的长度相同, 将其分配给申请者；另一部分的长度为原长度与分配长度之差, 将其仍记录于空闲区域表中。

回收时，按回收区的首地址查询空闲区表，若有与回收区相临的空闲区，则将其合并到相临区中，否则，把回收区按照地址从低到高的顺序插入到空闲区域表的适当位置。

2. 最佳适应算法(Best Fit，BF)

分配时取满足申请要求且长度最小的空闲区域。在实现时, 可将系统中所有的空闲区域按照长度由小到大的次序依次记录于空闲区域表中。与最先适应算法相类似, 当进程申请存储空间时, 系统由表的头部开始查找, 取第一个满足要求的表目。如果该表目所对应的区域长度恰好与所申请的区域长度相同, 则将该区域全部分配给申请者。否则将该区域分割为两部分, 一部分的长度与所申请的长度相同, 将其分配给申请者；另一部分即剩余部分的长度为原长度与分配长度之差, 由于剩余部分的长度已经改变，所以应重新将其按长度从小到大的顺序插入到空闲区域表中。

回收时，不仅要按回收区的首地址查询空闲区表，找到与回收区相临的空闲区，将其合并到相临区中，而且要把合并后的回收区按照长度递增的顺序插入到空闲区域表的适当位置。

3. 最坏适应算法(Worst Fit，WF)

分配时取满足申请要求且长度最大的空闲区域。在实现时, 可将系统中所有的空闲区域按照长度由大到小的次序依次记录于空闲区域表中。当进程申请

存储空间时, 取第一个表目。如果该表目所对应的区域长度恰好与所申请的区域长度相同, 则将该区域全部分配给申请者。否则将该区域分割为两部分, 一部分的长度与所申请的长度相同, 将其分配给申请者；另一部分即剩余部分的长度为原长度与分配长度之差, 由于剩余部分的长度已经改变，所以应重新将其按长度递减的顺序插入到空闲区域表中。

回收时，不仅要按回收区的首地址查询空闲区表，找到与回收区相临的空闲区，将其合并到相临区中，而且要把合并后的回收区按照长度递减的顺序插入到空闲区域表的适当位置。

1.3.3 设计并分析测试数据

假设初始内存布局如图1-4，图中的起始地址以及大小都以KB来衡量。

起始地址 0 占用者大小

80 85

145 160 180

a 10

b 20

c 10

d 60

e 20

图1-4初始内存布局

由图1-4可见，初始时共有五个线程驻留在内存，它们是a,b,c,d,e，线程驻留区表如图1-5；还有五个空闲区，空闲区域表如图1-6。

假设现在有三个线程提出内存申请，申请情况见图1-7。经过分析我们得到在每种分配算法下这三个线程所申请到的内存情况。图1-8是最先适应算法分配情况，图1-9是最佳适应算法分配情况，图1-10是最坏适应算法分配情况。

空闲区首址空闲区长度线程名称驻留区始址驻留区大小 10 10 a 0 10 40 30 b 20 20 80 5 c 70 10 145 15 d 85 60 180 20 e 160 20 图1- 6 空闲区域表图1-5 线程驻留区表线程名称驻留区始址驻留区大小请求大小预计驻留线程名称 a 0 10 (KB) 时间( 秒) b 20 20 thread_1 20 4 c 70 10 thread_2 10 5 d 85 60 thread_3 5 6 e 160 20 图1-7 内存申请表 thread_1 40 20 thread_2 10 10 thread_3 60 5

4 图1-8 最先适应算法线程驻留区表

线程名称驻留区始址驻留区大小线程名称驻留区始址驻留区大小 a 0 10 a 0 10 b 20 20 b 20 20 c 70 10 c 70 10 d 85 60 d 85 60 e 160 20 e 160 20 thread_1 180 20 thread_1 40 20 thread_2 10 10 thread_2 180 10 thread_3 80 5 thread_3 145 5 图1-9最佳适应算法线程驻留区表图1-10最坏适应算法线程驻留区表

1.3.4 程序设计

程序包含两个文件，一个是头文件variable_partition.h，另一个是源程序文件variable_partition.cpp。在头文件中定义了宏、数据结构、全局变量、函数声明，源程序中含有各个函数的实现。

在头文件中，结构体FREEAREA、REQUIRE_MEMORY、THREAD_RESIDENCE_MEMORY分别对应于图1-1、图1-2、图1-3中的一行，不同之处是为了构成链表在三个结构体中都有前向指针。数组init_free_area_table对应于图1-6，数组init_thread_require_memory_table对应于图1-5，数组init_thread_residence_memory_table对应于图1-7，为了实现动态分配与释放，用链表重新组织空闲区域表、线程驻留区表和内存申请表，全局变量p_free_area_list是空闲区链首，p_thread_require_memory_queue是内存申请队列的队首，p_thread_residence_memory_list是线程驻留区链首，tail_thread_residence_memory_list是线程驻留区链尾，由于线程驻留区链表被内存分配函数和内存释放函数共享，故用临界区变量CS_THREAD_MEMORY_LIST来保护，同理，屏幕是所有线程共享的，所以用临界区变量CS_SCREEN来保护,空闲区链表被内存分配函数和内存释放函数共享，故用临界区变量CS_FREEAREA_LIST来保护。h_thread是线程句柄数组，用来存放各个线程的句柄。

程序共包含25个函数，按照作用可以将它们分成五组。

第一组是主函数main()，其作用是显示主菜单并根据用户的选择执行相应功能；

第二组包括函数print_space()和函数display_thread_residence_memory()，前者用来显示若干个空格，后者用来显示线程驻留区表；

第三组共十个函数，用来实现最先适应分配法，它们的名称及功能如图1-11。函数名称 FF_initialize_freearea_list FF_delete_freearea_list FF_initialize_require_memory_list FF_delete_require_memory_list FF_delete_thread_residence_memory_list FF_thread FF_require_memory FF_release_memory FF() 函数功能初始化空闲区链表：按地址从低到高排序删除空闲区链表初始化内存申请链表删除内存申请链表删除线程驻留区链表线程函数：申请内存；驻留内存；释放内存内存申请函数内存释放函数初始化函数：创建线程并等待它们结束图1-11 最先适应分配法的函数及其功能

FF_initialize_thread_residence_memory_list 初始化线程驻留区链表

第四组共六个函数，用来实现最佳适应分配法，它们的名称及功能如图5-12。函数名称 BF_initialize_freearea_list BF_thread BF_require_memory BF_release_memory BF_insert_freearea BF() 函数功能初始化空闲区链表：按长度递增排序线程函数：申请内存；驻留内存；释放内存申请一段内存，成功时返回起始地址，失败时返回空释放一段内存将空闲区按大小递增的次序插入到空闲区链表中初始化函数：创建线程并等待它们结束图1-12 最佳适应分配法的函数及其功能

第五组共六个函数，用来实现最坏适应分配法，它们的名称及功能如图5-13。

函数名称 WF_initialize_freearea_list WF_thread WF_require_memory WF_release_memory WF_insert_freearea WF() 函数功能初始化空闲区链表：按长度递减排序线程函数：申请内存；驻留内存；释放内存申请一段内存，成功时返回起始地址，失败时返回空释放一段内存将空闲区按大小递减的次序插入到空闲区链表中初始化函数：创建线程并等待它们结束图1-13 最坏适应分配法的函数及其功能

1.3.5 参考源代码

下面是完整的程序清单。

头文件 variable_partition.h 的清单

#include #include #include #include #include #include

#define MAX_THREAD 3

#define BF_initialize_require_memory_list FF_initialize_require_memory_list #define WF_initialize_require_memory_list FF_initialize_require_memory_list #define BF_initialize_thread_residence_memory_list FF_initialize_thread_residence_memory_list

#define WF_initialize_thread_residence_memory_list FF_initialize_thread_residence_memory_list

#define WF_delete_freearea_list FF_delete_freearea_list #define BF_delete_freearea_list FF_delete_freearea_list

#define WF_delete_require_memory_list FF_delete_require_memory_list #define BF_delete_require_memory_list FF_delete_require_memory_list #define WF_delete_thread_residence_memory_list FF_delete_thread_residence_memory_list

#define BF_delete_thread_residence_memory_list FF_delete_thread_residence_memory_list

typedef struct freearea{ //表示空闲区域的数据结构 struct freearea *next; //指向下一个结点的指针 int start_address; //空闲区起始地址 int size; //空闲区大小 }FREEAREA;

typedef struct require_memory{ //记录线程申请内存的数据结构 struct require_memory *next; //指向下一个结点的指针 char thread_name[10]; //线程名 int size; //申请内存大小（以KB为单位） int duration; //在内存的驻留时间（以秒为单位） }REQUIRE_MEMORY;

typedef struct thread_residence_memory{ //描述线程驻留区的数据结构 struct thread_residence_memory *next; //指向下一个结点的指针 char thread_name[10]; //线程名 int start_address; //驻留区起始地址 int size; //驻留区大小 }THREAD_RESIDENCE_MEMORY;

FREEAREA init_free_area_table[5]={ //测试数据：初始空闲区表 {NULL,10,10}, {NULL,40,30},

{NULL,80,5}, {NULL,145,15}, {NULL,180,20} };

REQUIRE_MEMORY init_thread_require_memory_table[3]={ //测试数据：初始内存申请表

{NULL,\ {NULL,\ {NULL,\};

//测试数据：初始线

程驻留区表

THREAD_RESIDENCE_MEMORY init_thread_residence_memory_table[5]={ {NULL,\ {NULL,\ {NULL,\ {NULL,\ {NULL,\};

FREEAREA *p_free_area_list=NULL; //空闲区链首

REQUIRE_MEMORY *p_thread_require_memory_queue=NULL; //内存申请队列队首

THREAD_RESIDENCE_MEMORY *p_thread_residence_memory_list=NULL; //线程驻留区链首

THREAD_RESIDENCE_MEMORY *tail_thread_residence_memory_list=NULL; //线程驻留区链尾

CRITICAL_SECTION CS_THREAD_MEMORY_LIST; //保护线程驻留区链表的临界区

CRITICAL_SECTION CS_SCREEN; //保护屏幕的临界区

CRITICAL_SECTION CS_FREEAREA_LIST; //保护空闲区链表的临界区

HANDLE h_thread[MAX_THREAD]; //线程句柄数组

void print_space(int num); //输出若干个空格

void display_thread_residence_memory_list(); //显示线程驻留区表

//最先适应分配法的函数

FREEAREA *FF_initialize_freearea_list(FREEAREA *init_table,int num); //初始化空闲区链表

void FF_delete_freearea_list(); //删除空闲区链表

REQUIRE_MEMORY *FF_initialize_require_memory_list(REQUIRE_MEMORY *init_table,int num);

//初始化

内存申请链表

void FF_delete_require_memory_list(); //删除内存申请链表

THREAD_RESIDENCE_MEMORY *FF_initialize_thread_residence_memory_list

(THREAD_RESIDENCE_MEMORY *init_table,int num); //初始化线程驻留区链表

void FF_delete_thread_residence_memory_list(); //删除线程驻留区链表 void FF_thread(void *data); //线程函数

int FF_require_memory(int size); //内存申请函数 void FF_release_memory(int start_address,int size); //内存释放函数

void FF(); 的初始化函数

//最佳适应分配算法的函数

void BF_thread(void //线程函数

int BF_require_memory(int size); 内存申请函数

void BF_release_memory(int start_address,int size); 内存释放函数

void BF_insert_freearea(FREEAREA *free_node); 结点插入函数 void //初始化程序

void BF_initialize_freearea_list(FREEAREA *init_table,int num); 化空闲区链表

//最坏适应分配算法的函数

void WF_thread(void //线程函数

void WF_insert_freearea(FREEAREA *free_node); 点插入函数

void WF_initialize_freearea_list(FREEAREA *init_table,int num); 空闲区链表

int WF_require_memory(int size); 存申请函数

void WF_release_memory(int start_address,int size); 存释放函数 void //初始化程序

源程序文件 variable_partition.cpp 的清单

#include \int main(int argc,char *argv[]){ char select; while(1){ printf(\ printf(\ 1:first fit allocation |\\n\ printf(\ 2:best fit allocation |\\n\ printf(\ 3:worst fit allocation |\\n\ printf(\ 4:exit |\\n\

//最先适应分配算法*data); // // //空闲区BF(); //初始*data); //空闲区结 //初始化 //内 //内WF(); printf(\ printf(\ do{ select=(char)getch(); }while(select!='1'&&select!='2'&&select!='3'&&select!='4'); system(\ switch(select){ case '1': FF(); break; case '2': BF(); break; case '3': WF(); break; case '4': return 0; } printf(\ getch(); system(\ } return 0; }

void print_space(int num){ //显示若干个空格 int i; for(i=0;i

void display_thread_residence_memory_list(){ //显示驻留线程链表 THREAD_RESIDENCE_MEMORY *p; char buffer[20];

p=p_thread_residence_memory_list; printf(\ printf(\ printf(\ while(p!=NULL){

printf(\ print_space(18-strlen(p->thread_name)); printf(\ itoa( p->start_address, buffer, 10 ); print_space(19-strlen(buffer)); printf(\ itoa(p->size, buffer, 10 );

print_space(17-strlen(buffer)); printf(\ p=p->next; };

printf(\}

//最先适应分配法：初始化空闲区链表

FREEAREA *FF_initialize_freearea_list(FREEAREA *init_table,int num){ FREEAREA *temp;

FREEAREA *head=NULL; FREEAREA *tail=NULL; int i;

for(i=0;i

temp=(FREEAREA *)malloc(sizeof(FREEAREA)); temp->start_address=init_table[i].start_address; temp->size=init_table[i].size; temp->next=NULL; if(head==NULL) head=tail=temp; else{ tail->next=temp; tail=tail->next; } };

return head; }

//最先适应分配法：删除空闲区链表 void FF_delete_freearea_list(){ FREEAREA *temp; temp=p_free_area_list; while(temp!=NULL){ temp=p_free_area_list->next; free(p_free_area_list); p_free_area_list=temp; } p_free_area_list=NULL; }

//最先适应分配法：初始化内存申请链表 REQUIRE_MEMORY *FF_initialize_require_memory_list(REQUIRE_MEMORY *init_table,int num){

REQUIRE_MEMORY *temp;

REQUIRE_MEMORY *head=NULL; REQUIRE_MEMORY *tail=NULL; int i;

for(i=0;i

temp=(REQUIRE_MEMORY *)malloc(sizeof(REQUIRE_MEMORY)); strcpy(temp->thread_name,init_table[i].thread_name); temp->size=init_table[i].size; temp->duration=init_table[i].duration; temp->next=NULL; if(head==NULL) head=tail=temp; else{

tail->next=temp; tail=tail->next; } };

return head; }

//最先适应分配法：删除内存申请链表 void FF_delete_require_memory_list(){ REQUIRE_MEMORY *temp; temp=p_thread_require_memory_queue; while(temp!=NULL){ temp=p_thread_require_memory_queue->next; free(p_thread_require_memory_queue); p_thread_require_memory_queue=temp; } p_thread_require_memory_queue=NULL; }

//最先适应分配法：初始化线程驻留区链表 THREAD_RESIDENCE_MEMORY

*FF_initialize_thread_residence_memory_list(THREAD_RESIDENCE_MEMORY *init_table,int num){

THREAD_RESIDENCE_MEMORY *temp;

THREAD_RESIDENCE_MEMORY *head=NULL; THREAD_RESIDENCE_MEMORY *tail=NULL; int i;

for(i=0;i

temp=(THREAD_RESIDENCE_MEMORY

*)malloc(sizeof(THREAD_RESIDENCE_MEMORY));

strcpy(temp->thread_name,init_table[i].thread_name); temp->start_address=init_table[i].start_address; temp->size=init_table[i].size; temp->next=NULL; if(head==NULL) head=tail=temp; else{ tail->next=temp; tail=tail->next; } };

tail_thread_residence_memory_list=tail; return head; }

//最先适应分配法：删除线程驻留区链表

void FF_delete_thread_residence_memory_list(){ THREAD_RESIDENCE_MEMORY *temp=p_thread_residence_memory_list; temp=p_thread_residence_memory_list; while(temp!=NULL){ temp=p_thread_residence_memory_list->next; free(p_thread_residence_memory_list);

p_thread_residence_memory_list=temp; } p_thread_residence_memory_list=NULL; }

//线程：申请内存，驻留一段时间，释放内存 void FF_thread(void *data){ int start_address=-1; THREAD_RESIDENCE_MEMORY *temp; EnterCriticalSection(&CS_SCREEN); printf(\ LeaveCriticalSection(&CS_SCREEN);

while(1){ //申请内存 start_address=FF_require_memory(((REQUIRE_MEMORY *)(data))->size); if(start_address>=0) break; else Sleep(1000); } temp=(THREAD_RESIDENCE_MEMORY

*)malloc(sizeof(THREAD_RESIDENCE_MEMORY));

strcpy(temp->thread_name,((REQUIRE_MEMORY *)(data))->thread_name); temp->start_address=start_address; temp->size=((REQUIRE_MEMORY *)(data))->size; temp->next=NULL; EnterCriticalSection(&CS_THREAD_MEMORY_LIST); //加入线程驻留区链表 tail_thread_residence_memory_list->next=temp; tail_thread_residence_memory_list=tail_thread_residence_memory_list->next; LeaveCriticalSection(&CS_THREAD_MEMORY_LIST); //显示线程驻留区链表 EnterCriticalSection(&CS_SCREEN); printf(\%s %s\\n\*)(data))->thread_name,\memory:\ display_thread_residence_memory_list(); LeaveCriticalSection(&CS_SCREEN); Sleep(((REQUIRE_MEMORY *)(data))->duration); //释放内存 FF_release_memory(start_address,((REQUIRE_MEMORY *)(data))->size); }

//最先适应分配法：内存申请函数 int FF_require_memory(int size){ int start_address=-1; FREEAREA *p; FREEAREA *p_next; EnterCriticalSection(&CS_FREEAREA_LIST); p=p_next=p_free_area_list; while(p_next!=NULL){

if(size==p_next->size){ //刚好满足要求，删除空闲区结点 start_address=p_next->start_address; if(p_next==p_free_area_list) p_free_area_list=p_next->next; else p->next=p_next->next; free(p_next); break; } else if(sizesize){ //分割空闲区结点 start_address=p_next->start_address; p_next->start_address+=size; p_next->size-=size; break; } else { p=p_next; p_next=p_next->next; } }

LeaveCriticalSection(&CS_FREEAREA_LIST); return start_address; }

//最先适应分配法：内存释放函数

void FF_release_memory(int start_address,int size){ EnterCriticalSection(&CS_FREEAREA_LIST); //请读者自己实现这段代码 LeaveCriticalSection(&CS_FREEAREA_LIST); }

//最先适应分配算法的初始化程序 void FF(){ int i=0;

REQUIRE_MEMORY *p;

HANDLE h_thread[MAX_THREAD]; InitializeCriticalSection(&CS_THREAD_MEMORY_LIST); InitializeCriticalSection(&CS_FREEAREA_LIST); InitializeCriticalSection(&CS_SCREEN); printf(\最先适应分配算法\\n\

p_free_area_list=FF_initialize_freearea_list(init_free_area_table,5);

p_thread_require_memory_queue=FF_initialize_require_memory_list(init_thread_require_memory_table,3);

p_thread_residence_memory_list=FF_initialize_thread_residence_memory_list(init_thread_residence_memory_table,5); p=p_thread_require_memory_queue; while(p!=NULL){

h_thread[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(FF_thread),p,0,NULL);

i++; p=p->next; };

WaitForMultipleObjects(MAX_THREAD,h_thread,TRUE,-1); //等待所有线程结束 EnterCriticalSection(&CS_SCREEN); printf(\ display_thread_residence_memory_list(); //显示驻留线程链表 LeaveCriticalSection(&CS_SCREEN); //删除各种链表 FF_delete_freearea_list(); FF_delete_require_memory_list(); FF_delete_thread_residence_memory_list(); getch(); printf(\}

//最佳适应分配算法的线程：申请内存，驻留一段时间，释放内存 void BF_thread(void *data){ int start_address=-1; THREAD_RESIDENCE_MEMORY *temp; EnterCriticalSection(&CS_SCREEN); printf(\ LeaveCriticalSection(&CS_SCREEN); //申请内存 while(1){ start_address=BF_require_memory(((REQUIRE_MEMORY *)(data))->size); if(start_address>=0) break; else Sleep(1000); } temp=(THREAD_RESIDENCE_MEMORY

*)malloc(sizeof(THREAD_RESIDENCE_MEMORY));

strcpy(temp->thread_name,((REQUIRE_MEMORY *)(data))->thread_name); temp->start_address=start_address; temp->size=((REQUIRE_MEMORY *)(data))->size; temp->next=NULL; EnterCriticalSection(&CS_THREAD_MEMORY_LIST); //加入线程内存驻留区链表 tail_thread_residence_memory_list->next=temp; tail_thread_residence_memory_list=tail_thread_residence_memory_list->next; LeaveCriticalSection(&CS_THREAD_MEMORY_LIST); //显示线程内存驻留区链表 EnterCriticalSection(&CS_SCREEN); printf(\%s %s\\n\*)(data))->thread_name,\memory:\ display_thread_residence_memory_list(); LeaveCriticalSection(&CS_SCREEN); Sleep(((REQUIRE_MEMORY *)(data))->duration);

//释放内存 BF_release_memory(start_address,((REQUIRE_MEMORY *)(data))->size); }

//最佳适应分配算法的内存申请函数 int BF_require_memory(int size){ int start_address=-1; FREEAREA *p; FREEAREA *p_next; EnterCriticalSection(&CS_FREEAREA_LIST); p=p_next=p_free_area_list; while(p_next!=NULL){ if(size==p_next->size){//刚好满足要求，删除空闲区结点 start_address=p_next->start_address; if(p_next==p_free_area_list) p_free_area_list=p_next->next; else p->next=p_next->next; free(p_next); break; } else if(sizesize){//分割空闲区结点 start_address=p_next->start_address; p_next->start_address+=size; p_next->size-=size; p->next=p_next->next; BF_insert_freearea(p_next); break; } else { p=p_next; p_next=p_next->next; } }

LeaveCriticalSection(&CS_FREEAREA_LIST); return start_address; }

//最佳适应分配算法的内存释放函数

void BF_release_memory(int start_address,int size){ //请读者自己实现这段代码 }

//最佳分配算法的空闲区结点插入函数

void BF_insert_freearea(FREEAREA *free_node){ FREEAREA *p;

FREEAREA *p_next; if(p_free_area_list==NULL) p_free_area_list=free_node;

else{ p_next=p=p_free_area_list; while(p_next!=NULL&&p_next->sizesize){ p=p_next; p_next=p_next->next; } if(p_next==NULL) //应插入到尾部 p->next=free_node; else if(p==p_next){ //应插入到头部 free_node->next=p; p_free_area_list=free_node; } else{ //应插入到p与p_next之间 free_node->next=p_next; p->next=free_node; } } }

//最佳适应分配法：初始化空闲区链表

void BF_initialize_freearea_list(FREEAREA *init_table,int num){ FREEAREA *temp; int i;

for(i=0;i

temp=(FREEAREA *)malloc(sizeof(FREEAREA)); temp->start_address=init_table[i].start_address; temp->size=init_table[i].size; temp->next=NULL; BF_insert_freearea(temp); } }

//最佳分配算法的初始化程序 void BF(){ int i=0;

REQUIRE_MEMORY *p;

BF_initialize_freearea_list(init_free_area_table,5);

p_thread_require_memory_queue=BF_initialize_require_memory_list(init_thread_require_memory_table,3);

p_thread_residence_memory_list=BF_initialize_thread_residence_memory_list(init_thread_residence_memory_table,5);

p=p_thread_require_memory_queue; while(p!=NULL){

h_thread[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(BF_thread),p,0,NULL);

i++;

p=p->next; };

//等待所有线程结束

WaitForMultipleObjects(MAX_THREAD,h_thread,TRUE,-1); //显示驻留线程链表 EnterCriticalSection(&CS_SCREEN); printf(\ display_thread_residence_memory_list(); LeaveCriticalSection(&CS_SCREEN); //删除各种链表 FF_delete_freearea_list(); FF_delete_require_memory_list(); FF_delete_thread_residence_memory_list(); getch(); printf(\}

//最坏适应分配算法的线程：申请内存，驻留一段时间，释放内存 void WF_thread(void *data){ int start_address=-1; THREAD_RESIDENCE_MEMORY *temp; EnterCriticalSection(&CS_SCREEN); printf(\ LeaveCriticalSection(&CS_SCREEN); //申请内存 while(1){ start_address=WF_require_memory(((REQUIRE_MEMORY *)(data))->size); if(start_address>=0) break; else Sleep(1000); } temp=(THREAD_RESIDENCE_MEMORY

*)malloc(sizeof(THREAD_RESIDENCE_MEMORY));

strcpy(temp->thread_name,((REQUIRE_MEMORY *)(data))->thread_name); temp->start_address=start_address; temp->size=((REQUIRE_MEMORY *)(data))->size; temp->next=NULL; EnterCriticalSection(&CS_THREAD_MEMORY_LIST); //加入线程内存驻留区链表 tail_thread_residence_memory_list->next=temp; tail_thread_residence_memory_list=tail_thread_residence_memory_list->next; LeaveCriticalSection(&CS_THREAD_MEMORY_LIST); //显示线程内存驻留区链表 EnterCriticalSection(&CS_SCREEN); printf(\%s %s\\n\*)(data))->thread_name,\memory:\ display_thread_residence_memory_list();

LeaveCriticalSection(&CS_SCREEN); Sleep(((REQUIRE_MEMORY *)(data))->duration); //释放内存 WF_release_memory(start_address,((REQUIRE_MEMORY *)(data))->size); }

//最坏分配算法的空闲区结点插入函数

void WF_insert_freearea(FREEAREA *free_node){ FREEAREA *p;

FREEAREA *p_next; if(p_free_area_list==NULL) p_free_area_list=free_node; else{

p=p_next=p_free_area_list; while(p_next!=NULL&&free_node->sizesize){ p=p_next; p_next=p_next->next; } if(p_next==NULL) //应插入到尾部 p->next=free_node; else if(p==p_next){ //应插入到头部 free_node->next=p; p_free_area_list=free_node; } else{ //应插入到p与p_next之间 free_node->next=p_next; p->next=free_node; } } }

//最坏适应分配法：初始化空闲区链表

void WF_initialize_freearea_list(FREEAREA *init_table,int num){ FREEAREA *temp; int i;

for(i=0;i

temp=(FREEAREA *)malloc(sizeof(FREEAREA)); temp->start_address=init_table[i].start_address; temp->size=init_table[i].size; temp->next=NULL; WF_insert_freearea(temp); } }

//最坏适应分配算法的内存申请函数 int WF_require_memory(int size){ int start_address=-1; FREEAREA *p_next; EnterCriticalSection(&CS_FREEAREA_LIST); p_next=p_free_area_list; if(size==p_free_area_list->size){//刚好满足要求，删除空闲区结点

start_address=p_next->start_address; p_free_area_list=p_free_area_list->next; free(p_next); } else if(sizesize){//分割空闲区结点 start_address=p_next->start_address; p_next->start_address+=size; p_next->size-=size; p_free_area_list=p_free_area_list->next; WF_insert_freearea(p_next); } LeaveCriticalSection(&CS_FREEAREA_LIST); return start_address; }

//最坏适应分配算法：内存释放函数

void WF_release_memory(int start_address,int size){ //请读者自己实现这段代码 }

//最坏适应分配算法的初始化程序 void WF(){ int i=0;

REQUIRE_MEMORY *p;

WF_initialize_freearea_list(init_free_area_table,5);

p_thread_require_memory_queue=WF_initialize_require_memory_list(init_thread_require_memory_table,3);

p_thread_residence_memory_list=WF_initialize_thread_residence_memory_list(init_thread_residence_memory_table,5);

p=p_thread_require_memory_queue; while(p!=NULL){

h_thread[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(WF_thread),p,0,NULL);

i++; p=p->next; };

//等待所有线程结束

FF_delete_freearea_list(); FF_delete_require_memory_list(); FF_delete_thread_residence_memory_list(); getch(); printf(\}

1.3.6 测试程序

|-----------------------------------| | 1:first fit allocation | | 2:best fit allocation | | 3:worst fit allocation | | 4:exit | |-----------------------------------| select a function(1~4):

图1-14 主菜单

图1-14是程序运行时显示的主界面。输入数字1，将运行最先适应算法，运行结果见图1-15；输入数字2，将运行最佳适应算法，运行结果见图1-16；输入数字3，将运行最坏适应算法，运行结果见图1-17；输入

数字4，程序结束。

|-------------------|--------------------|------------------| | thread_name | start_address(kB) | size(KB) | |-------------------|--------------------|------------------| | a | 0 | 10 | | b | 20 | 20 | | c | 70 | 10 | | d | 85 | 60 | | e | 160 | 20 | | thread_1 | 40 | 20 | | thread_2 | 10 | 10 | | thread_3 | 60 | 5 | |-------------------|--------------------|------------------|

图1-15 最先适应算法的运行结果

|-------------------|--------------------|------------------| | thread_name | start_address(kB) | size(KB) | |-------------------|--------------------|------------------| | a | 0 | 10 | | b | 20 | 20 | | c | 70 | 10 | | d | 85 | 60 | | e | 160 | 20 | | thread_1 | 180 | 20 | | thread_2 | 10 | 10 | | thread_3 | 80 | 5 | |-------------------|--------------------|------------------|

图1-16 最佳适应算法的运行结果

|-------------------|--------------------|------------------| | thread_name | start_address(kB) | size(KB) | |-------------------|--------------------|------------------| | a | 0 | 10 | | b | 20 | 20 | | c | 70 | 10 | | d | 85 | 60 | | e | 160 | 20 | | thread_1 | 40 | 20 | | thread_2 | 180 | 10 | | thread_3 | 145 | 5 | |-------------------|--------------------|------------------|

图1-17 最坏适应算法的运行结果

程序的执行结果与预期的一致，证明程序设计是正确的。 1.4 功能扩充

参考源程序中没有实现最先适应算法、最佳适应算法和最坏适应算法的内存释放函数，请读者自己实现这些函数，特别要注意相邻空闲区的合并。

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

2.1 设计目的

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

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

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

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

2.2 设计要求

利用多线程技术编写哲学家就餐程序，使之在运行时能演示产生死锁的情况，也能演示采用死锁防止方法后不产生死锁的情况。

程序要采用简单的控制台界面，运行后在屏幕上显示功能菜单，列出该程序具有的功能，供用户选择，用户选择功能后应该转到相应的处理程序。程序应该包括以下功能：

（1）演示死锁现象；

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

2.3.1 程序结构设计

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

这五个线程句柄来实现同步。

该程序共有7个函数，这些函数可以分成4组。各组包含的函数及其功能如表2-1所示。

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

三四 2.3.2 算法设计

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

{

while(1){

随机等待一段时间；

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

放下右边筷子；

} }

（2）ordered_allocation_philosopher函数

{

while(1){

随机等待一段时间；

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

放下编号较大的筷子；

} }

（3）pre_allocation_philosopher函数

{

while(1){ 提示等待左边筷子；提示等待右边筷子；同时申请左边和右边两根筷子；提示正在进餐；

随机等待一段时间；

放下左边筷子；

放下右边筷子；

} }

（4）deadlock函数

{

为每根筷子创建一个互斥信号量；

创建五个可能产生死锁的哲学家线程；等待五个哲学家线程结束； }

其他的初始化函数与deadlock()的算法相同，只不过在创建线程时使用不同的线程函数。

在windows中可以用系统调用WaitForMultipleObjects()同时申请两份资源，具体解法如下所示。

#define N 5

typedef enum{thinking, hungry, eating}status; status state[N]; semaphore self[N];

semaphore mutex = 1;

void test(int i) {

if((state[i] == hungry)&&

(state[(i-1)%N] != eating)&& (state[(i+1)%N] != eating)){ state[i] = eating; V(self[i]); } }

void pick_chopsticks(int i) {

P(mutex);

state[i] = hungry; test(i); V(mutex);

P(self[i]);

}

void put_chopsticks(int i) {

P(mutex);

state[i] = thinking; test((i-1)%N); test((i+1)%N); V(mutex);

}

void philosopher(int i) {

while(1){ think();

pick_chopsticks(i); eat();

put_chopsticks(i); }

void main {

int i;

for(i=0;i<5;i++){

state[i] = thingking; self[i].value = 0;

} }

在上述程序中, 自定义数据类型status用来枚举哲学家的状态，数组state用来存放五个哲学家的状态，由于该数组是全局变量，所以用信号灯变量mutex实现对它的互斥访问。信号量数组self包含五个元素，每个元素的初始值皆为0，当第i号哲学家不具备进食条件时，会将自己阻塞在信号量self[i]上。函数test用于测试i号哲学家是否具备进食的条件。i号哲学家可以进食必须同时满足以下条件：i号哲学家饥饿，左边哲学家不在进食，右边哲学家不在进食。

2.3.3 参考源代码

2.3.3.1 windows下的参考源程序

#include #include #include #include #include #include #include

#define MAX_PHILOSOPHERS 5 //待测试的哲学家数 #define ZERO 48 //数字0的ASCII码 #define DELAY rand()%

HANDLE h_mutex_chopsticks[MAX_PHILOSOPHERS]; //互斥体数组，每根筷子需要一个互斥体

int thread_number[MAX_PHILOSOPHERS]={0,1,2,3,4};

//会产生死锁的哲学家线程

int deadlock_philosopher(LPVOID data){ int philosopher_number=*(int *)(data); //哲学家编号 for(;;) { srand( (unsigned)time( NULL ) * ( philosopher_number+ 1) ); Sleep(DELAY); printf(\\is waiting chopstick \ WaitForSingleObject(h_mutex_chopsticks[philosopher_number], INFINITE); printf(\\got chopstick \ Sleep(DELAY/4); printf(\\is waiting chopstick \

WaitForSingleObject(h_mutex_chopsticks[((1+philosopher_number)%MAX_PHILOSOPHERS)], INFINITE); printf(\\got chopstick \ printf(\\is eating.\

Sleep(DELAY); ReleaseMutex(h_mutex_chopsticks[philosopher_number]); printf(\\released chopstick \

ReleaseMutex(h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS]); printf(\\released chopstick \ Sleep(DELAY); } // end for return 0;

}

//死锁时的初始化程序 void deadlock(){ int i=0; HANDLE h_thread[MAX_PHILOSOPHERS]; printf(\可能出现死锁的哲学家就餐问题\\n\ for(i=0;i

//通过按序分配资源预防死锁的哲学家线程

int ordered_allocation_philosopher(LPVOID data){ int philosopher_number=*(int *)(data); for(;;) { srand( (unsigned)time( NULL ) * ( philosopher_number+ 1) ); Sleep(DELAY); if(philosopher_number==MAX_PHILOSOPHERS-1){ printf(\\is waiting chopstick \

WaitForSingleObject(h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS], INFINITE);

Sleep(DELAY/4); printf(\\is waiting chopstick \ WaitForSingleObject(h_mutex_chopsticks[philosopher_number], INFINITE); } else{ printf(\\is waiting chopstick \ WaitForSingleObject(h_mutex_chopsticks[philosopher_number], INFINITE); Sleep(DELAY/4); printf(\\is waiting chopstick \

WaitForSingleObject(h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHE

RS], INFINITE); } printf(\

Sleep(DELAY); printf(\\is releasing chopstick \ ReleaseMutex(h_mutex_chopsticks[philosopher_number]); printf(\\is releasing chopstick \

ReleaseMutex(h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS]); Sleep(DELAY); } // end for return 0; }

//通过按序分配资源预防死锁的初始化程序 void ordered_allocation(){ int i=0; HANDLE h_thread[MAX_PHILOSOPHERS]; printf(\可能出现死锁的哲学家就餐问题\\n\ for(i=0;i

//通过资源预分配法预防死锁的哲学家线程 int pre_alloction_philosopher(LPVOID data){ int philosopher_number=*(int *)(data); HANDLE h_mutex_leftandright_chopsticks[2]; h_mutex_leftandright_chopsticks[0]=h_mutex_chopsticks[philosopher_number];

h_mutex_leftandright_chopsticks[1]=h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS]; for(;;) {

srand( (unsigned)time( NULL ) * ( philosopher_number+ 1) ); Sleep(DELAY); printf(\\is waiting chopstick \ printf(\\is waiting chopstick \ WaitForMultipleObjects(2, h_mutex_leftandright_chopsticks, TRUE, INFINITE); printf(\ Sleep(DELAY); printf(\\is releasing chopstick \ ReleaseMutex(h_mutex_chopsticks[philosopher_number]); printf(\\is releasing chopstick \

ReleaseMutex(h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS]); Sleep(DELAY); } // end for return 0; }

//通过资源预分配法预防死锁的初始化程序 void pre_alloction(){ int i=0; HANDLE h_thread[MAX_PHILOSOPHERS]; printf(\可能出现死锁的哲学家就餐问题\\n\ for(i=0;i

//主程序

int main(int argc,char *argv[]){ char select; while(1){ printf(\ printf(\ 1:deadlock |\\n\

printf(\ 2:non_deadlock by ordered allocation |\\n\ printf(\ 3:non_deadlock by pre_allocation |\\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': deadlock(); break; case '2': ordered_allocation(); break; case '3': pre_alloction(); break; case '4': return 0; } printf(\ getch(); system(\}

return 0;

}

2.3.4 测试程序

图2-2 程序主界面图2-3 死锁情况

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

2.4 不足与改进

该程序虽然能防止死锁，但是可能存在饿死现象，请读者改进程序使之既没有死锁，也没有饿死现象。

设计3 假脱机打印程序与虚拟设备

3.1 设计目的

理解虚拟设备的工作原理，理解守护程序的概念。图3-1表示假脱机打印程序的工作原理。

服务器端

打印请求队列

服务器端服务器端服务器端客户端打印打印打印打印请求打印文件打印机请求程序程序请求接收程序请求

图3-1 假脱机程序工作原理

在网络环境下，连在网络服务器上的打印机要为多个终端服务，每个终端上的用户都可以通过客户端程序向服务器发送打印请求，服务器端的打印请求接收程序接收来自客户端的打印请求，并将该请求存放到磁盘上的打印请求队列中，由服务器端的假脱机打印程序在CPU空闲时从打印请求队列中取出请求信息，并将文件输出到打印机中。这种工作方式不是将文件直接输出到打印机，而是先将待打印的文件缓存到磁盘上，然后立即返回用户程序，从而缩短了用户响应时间，为用户提供了虚拟的快速打印机。这里的磁盘缓存空间就是虚拟设备。服务器端的打印请求接收程序和打印程序都是守护程序，即从开机后就一直运行的程序。 3.2 设计要求

利用多线程技术编写假脱机打印程序，并设计测试数据以验证程序的正确性。

1、界面要求：

程序采用简单的控制台界面，运行后在屏幕上显示功能菜单，列出该程序具有的功能，供用户选择。

2、功能要求：

（1）发送打印请求；

（2）查看假脱机打印队列；（3）打印文件；（4）退出。

用户选择功能后应该转到相应的处理程序，并在需要时显示程序的执行结

果。

若用户选择（1）则提示用户输入待打印的文件名称，程序接收输入后将打印请求传送到打印队列中，并回到主菜单；

若用户选择（2）则在屏幕上列出打印队列情况，提示按任意键回到主界面；若用户选择（3）则打印队首的文件，显示所打印的文件名称，按任意键回到主界面；

若用户选择（4）则退出程序的执行。 3.3 数据结构分析

字段名称作用

file_name 文件名称

file_size 文件大小（以KB为单位）

图3-2 FILE_INFO结构体的成员及其作用

需要两个数据结构，

一个FILE_INFO用来描述打印请求，包括文件名称和文件大小，如图3-2所示。另一个数据结构SPOOL用来描述打印请求队列，如图3-3所示。图3-4描述了程序运行时刻结构体SPOOL的内容。

spool_count 3 字段名称作用 spool_in 3 spool_count 记录打印队列中的文件个数 spool_out 0 记录下一个打印请求存放的 spool_in spool_queue[0] sever 4KB 位置 spool_queue[1] client 3KB 记录下一个被打印文件的位 spool_out spool_queue[2] myfile 7KB 置 spool_queue[3] spool_queue 打印请求队列（用数组实现） spool_queue[4] 图3-3 SPOOL结构体的成员及其作用图3-4 SPOOL结构体快照 3.4 程序结构

1、线程划分

为了模拟假脱机打印程序，需要三个线程，主线程用于显示主菜单，接收用户的功能选择，显示打印队列情况；打印请求接收/发送线程接收用户的打印请求，并将打印请求存放到打印请求队列；打印线程用来从打印队列中取文件并将其输出到屏幕。

2、线程互斥要求

三个线程都需要通过控制台终端与用户交互，因此对终端的使用要互斥，以免屏幕混乱（用互斥体h_screen_mutex实现）；三个线程都要访问打印请求队列，因此对它要进行互斥操作（用互斥体h_spool_mutex实现）；

3、同步要求

主线程与打印请求接收/发送线程要同步，当用户选择功能（1）时，主线程

要通知打印请求接收/发送线程开始接收用户请求（用初始值为0的信号量h_print实现），然后主线程要等待打印请求接收/发送线程发来接收完毕的信号（用初始值为0的信号量h_sendthread_to_mainthread实现）；

主线程要与打印线程同步，当用户选择功能（3）时，主线程要通知打印线程开始打印文件（用初始值为0的信号量h_semaphore_spool实现），然后主线程要等待打印线程发来打印完毕的信号（用初始值为0的信号量h_spoolthread_to_mainthread实现）；

（注意：在实际的系统中，打印线程不会等待用户从控制台发命令才开始打印，而是只要有打印请求且CPU空闲就循环不停地打印文件，直至打印队列为空，这时打印线程睡眠。本设计这样做是为了避免打印队列迅速变空。）

请求接收/发送线程和打印线程要同步，当打印队列为空时打印线程阻塞，直到请求接收/发送线程将新的请求放入队列；当打印队列满时，请求接收/发送线程阻塞，直到打印线程打印完一个文件空出新位置才能将其唤醒。这两个线程的同步遵循生产者/消费者模型，同步信号量为h_spool_empty和h_spool_full，前者跟踪空位置，后者跟踪打印请求。

4、函数设计

为了简化程序设计，我们只考虑单机环境，而且将打印请求队列存放在内存中，而不是存放在磁盘中，另外用屏幕输出模拟实际的打印机输出。该程序包括三个线程：主线程模拟客户端程序，sendthread线程模拟打印请求接收程序，spool_thread线程模拟打印程序。

该程序使用以下全局变量：

spool_buffer是打印请求队列，互斥体h_spool_mutex用来实现对spool_buffer的互斥访问，互斥体h_screen_mutex用来实现对终端的互斥访问，h_send和h_spool_thread分别是打印请求接收/发送线程和打印线程的句柄，h_semaphore_spool和h_spoolthread_to_mainthread是主线程和打印线程之间的同步信号量，h_print和h_sendthread_to_mainthread是主线程和打印请求接收/发送线程之间的同步信号量，h_spool_full和h_spool_empty是打印线程和打印请求接收/发送线程之间的同步信号量。

该程序共有五个函数，它们的名称及作用如图3-5所示。函数名称 sendthread spool_thread print_space 作用接收用户的打印请求并将其发送到打印请求队列中从打印请求队列中取待打印文件并将其输出到屏幕上显示若干个空格 list_spool_queue 列出打印队列 main 创建线程，初始化信号量，显示主菜单，根据用户选择执行相应功能图3-5 假脱机打印程序包括的函数及其作用

下面给出每个函数的算法描述。

（1）list_spool_queue函数 {

申请打印队列互斥使用权P(h_spool_mutex)；申请屏幕互斥使用权P(h_screen_mutex)；清屏；

显示打印队列中当前请求个数；显示表头；

对请求队列中的每一个请求

{在屏幕上输出待打印文件名称以及大小}；释放打印队列互斥使用权V(h_spool_mutex)；释放屏幕互斥使用权V(h_screen_mutex)； }

（2）sendthread函数 {

while(1){

等待主线程发送唤醒信号直到用户选择“发送打印请求功能”P(h_print)；申请屏幕互斥使用权P(h_screen_mutex)；

清屏；

提示并接收用户输入文件名称；

释放屏幕互斥使用权V(h_screen_mutex)；产生随机数作为文件大小；

申请打印队列中的空闲位置P(h_spool_empty)；

申请打印队列互斥使用权P(h_spool_mutex)；将请求放入打印队列当前位置；调整位置指针至下一位置；

释放打印队列互斥使用权V(h_spool_mutex)；通知打印线程多了一个打印请求V(h_spool_full)；唤醒主线程继续画主菜单V(h_sendthread_to_mainthread)； } }

（3）spool_thread函数 {

while(1){

等待主线程发送唤醒信号直到用户选择“打印文件功能”P(h_semaphore_spool)；等待直到sendthread线程发来打印请求P(h_spool_full)；

申请打印队列互斥使用权P(h_spool_mutex)；申请屏幕互斥使用权P(h_screen_mutex)；将打印队列中的文件数减1；在屏幕上输出正在打印的文件名称；

回收该位置（置文件名称为空白，文件大小为0）；下调打印指针；

释放屏幕互斥使用权V(h_screen_mutex)；释放打印队列互斥使用权V(h_spool_mutex)；

通知sendthread线程多了一个空位置V(h_spool_empty)；唤醒主线程继续画主菜单V(h_spoolthread_to_mainthread)；

} }

（4）main函数 {

创建两个互斥体；创建六个同步信号量；创建两个线程； while(1){

申请屏幕互斥使用权P(h_screen_mutex)；显示主菜单；接收用户功能选择；清屏；

释放屏幕互斥使用权V(h_screen_mutex)；根据功能选择进行分支{

选择了功能1：

唤醒发送线程允许其发送请求到打印队列V(h_print)；等待发送线程发送完打印请求P(h_sendthread_to_mainthread)；跳出循环；选择了功能2：

显示打印队列；跳出循环；选择了功能3：

唤醒打印线程允许其打印文件V(h_semaphore_spool)；等待打印线程打印完文件P(h_spoolthread_to_mainthread)；跳出循环；选择了功能4：

返回；

} }

}

3.5 测试程序

程序运行的主界面如图3-6所示，输入1后，提示你键入文件名称，你键入文件名称后，程序提示你按任意键回到主菜单，如图3-7所示，回到主菜单后，再选择1两次，分别输入文件名称为file2.ext和file3.cpp，然后回到主菜单，选择2，显示打印请求队列如图3-8所示。按任意键后回到主菜单，选择3打印一个文件，如图3-9所示。按任意键后回到主菜单，选择2打印请求队列，如图3-10所示，可见请求队列中已经少了一个待打印文件了。按任意键后回到主菜单，选择4，结束程序的执行。

图3-6 主菜单

图3-7 发送请求界面

图3-8打印请求队列

图3-9 打印文件界面

图3-10 打印一个文件后的请求队列

3.6参考源代码

3.6.1 windows下的参考源程序

#include #include #include #include #include

#define MAX_SPOOL 5 // 打印请求队列大小，最多能存放五个请求 #define DELAY rand()0 // 用随机数产生文件大小，以KB为单位

typedef struct{ char file_name[200]; int file_size; }FILE_INFO; typedef struct{ int spool_count; int spool_in; int spool_out; FILE_INFO spool_queue[MAX_SPOOL]; }SPOOL;

SPOOL spool_buffer;

HANDLE h_spool_mutex; HANDLE h_screen_mutex;

HANDLE h_send; // 发送线程的句柄 HANDLE h_semaphore_spool;

HANDLE h_spoolthread_to_mainthread; HANDLE h_sendthread_to_mainthread;

HANDLE h_spool_thread; // 打印线程的句柄 HANDLE h_spool_full; HANDLE h_spool_empty; HANDLE h_print;

DWORD WINAPI sendthread(LPVOID lpParameter) // 打印请求接收/发送线程的线程函数 { FILE_INFO file_info; while(1) { WaitForSingleObject(h_print,INFINITE); WaitForSingleObject(h_screen_mutex,INFINITE); system(\ printf(\ scanf(\ ReleaseMutex(h_screen_mutex); srand( (unsigned)time( NULL ) ); file_info.file_size=DELAY; WaitForSingleObject(h_spool_empty,INFINITE); WaitForSingleObject(h_spool_mutex,INFINITE); spool_buffer.spool_count++; spool_buffer.spool_queue[spool_buffer.spool_in]=file_info; spool_buffer.spool_in=(spool_buffer.spool_in+1)%MAX_SPOOL; ReleaseMutex(h_spool_mutex); ReleaseSemaphore(h_spool_full,1,NULL); ReleaseSemaphore(h_sendthread_to_mainthread,1,NULL); } }

void print_space(int num){ //显示若干个空格 int i; for(i=0;i

void list_spool_queue() //列出打印请求队列 { char buffer[10]; WaitForSingleObject(h_spool_mutex,INFINITE); WaitForSingleObject(h_screen_mutex,INFINITE); system(\ printf(\ printf(\ spool queue \\n\ printf(\ printf(\ | filesize(KB) |\\n\ printf(\ for(int i=0;i

print_space(36-strlen(spool_buffer.spool_queue[i].file_name)); printf(\ itoa(spool_buffer.spool_queue[i].file_size,buffer,10); print_space(12-strlen(buffer)); printf(\ } printf(\ ReleaseMutex(h_spool_mutex); ReleaseMutex(h_screen_mutex); }

DWORD WINAPI spool_thread(LPVOID lpParameter) // 打印线程的线程函数 { while(1) { WaitForSingleObject(h_semaphore_spool,INFINITE); WaitForSingleObject(h_spool_full,INFINITE); WaitForSingleObject(h_spool_mutex,INFINITE); WaitForSingleObject(h_screen_mutex,INFINITE); spool_buffer.spool_count--; printf(\a file

spool:\\nfilename:%s\\n\ strcpy(spool_buffer.spool_queue[spool_buffer.spool_out].file_name,\ spool_buffer.spool_queue[spool_buffer.spool_out].file_size=0; spool_buffer.spool_out=(spool_buffer.spool_out+1)%MAX_SPOOL; ReleaseMutex(h_screen_mutex); ReleaseMutex(h_spool_mutex); ReleaseSemaphore(h_spool_empty,1,NULL);

ReleaseSemaphore(h_spoolthread_to_mainthread,1,NULL); } return 0; }

int main(int argc,char *argv[]){ // 主程序 char select; h_send=CreateThread(NULL,0,sendthread,NULL,0,NULL); h_spool_thread=CreateThread(NULL,0,spool_thread,NULL,0,NULL); h_spool_mutex=CreateMutex(NULL,FALSE,NULL); h_screen_mutex=CreateMutex(NULL,FALSE,NULL); h_spool_full=CreateSemaphore(NULL,0,MAX_SPOOL,NULL); h_spool_empty=CreateSemaphore(NULL,MAX_SPOOL,MAX_SPOOL,NULL); h_print=CreateSemaphore(NULL,0,1,NULL); h_semaphore_spool=CreateSemaphore(NULL,0,1,NULL); h_sendthread_to_mainthread=CreateSemaphore(NULL,0,1,NULL); h_spoolthread_to_mainthread=CreateSemaphore(NULL,0,1,NULL); WaitForSingleObject(h_screen_mutex,INFINITE); while(1){

printf(\ printf(\ 1:send a print request |\\n\ printf(\ 2:list spool queue |\\n\ printf(\ 3:print a file in spool |\\n\ printf(\ 4:exit |\\n\ printf(\ printf(\ do{ select=(char)getch(); }while(select!='1'&&select!='2'&&select!='3'&&select!='4'); system(\ ReleaseMutex(h_screen_mutex); switch(select){ case '1': ReleaseSemaphore(h_print,1,NULL); WaitForSingleObject(h_sendthread_to_mainthread,INFINITE); break; case '2': list_spool_queue(); break; case '3': ReleaseSemaphore(h_semaphore_spool,1,NULL); WaitForSingleObject(h_spoolthread_to_mainthread,INFINITE); break; case '4': return 0; } WaitForSingleObject(h_screen_mutex,INFINITE); printf(\ getch(); system(\ ReleaseMutex(h_screen_mutex); } return 0; }

3.7 不足与改进

不足之处是：当打印队列已经为空，而用户仍然在主菜单中选择打印文件时，打印线程被永久阻塞，程序无法回到主菜单，也就无法通过发送打印请求将其唤醒。请读者改进之。

另外，读者可以利用套接字编程接口将该程序移植到网络环境下。

设计4 读者/写者问题与进程同步

4.1 设计目的

理解临界区和进程互斥的概念，掌握用信号量和PV操作实现进程互斥的方法。

4.2 设计要求

在windows环境下编写一个控制台应用程序，该程序运行时能创建N个线程，其中既有读者线程又有写者线程，它们按照事先设计好的测试数据进行读写操作。请用信号量和PV操作实现读者/写者问题。

读者/写者问题的描述如下：

有一个被许多进程共享的数据区，这个数据区可以是一个文件，或者主存的一块空间，甚至可以是一组处理器寄存器。有一些只读取这个数据区的进程（reader）和一些只往数据区中写数据的进程（writer）。以下假设共享数据区是文件。这些读者和写者对数据区的操作必须满足以下条件：读—读允许；读—写互斥；写—写互斥。这些条件具体来说就是：

（1）任意多的读进程可以同时读这个文件；（2）一次只允许一个写进程往文件中写；（3）如果一个写进程正在往文件中写，禁止任何读进程或写进程访问文件；（4）写进程执行写操作前，应让已有的写者或读者全部退出。这说明当有读者在读文件时不允许写者写文件。

对于读者-写者问题，有三种解决方法： 1、读者优先

除了上述四个规则外，还增加读者优先的规定，当有读者在读文件时，对随后到达的读者和写者，要首先满足读者，阻塞写者。这说明只要有一个读者活跃，那么随后而来的读者都将被允许访问文件，从而导致写者长时间等待，甚至有可能出现写者被饿死的情况。

2、写者优先

除了上述四个规则外，还增加写者优先的规定，即当有读者和写者同时等待时，首先满足写者。当一个写者声明想写文件时，不允许新的读者再访问文件。

3、无优先

除了上述四个规则外，不再规定读写的优先权，谁先等待谁就先使用文件。 4.3 设计步骤

4.3.1 设计测试数据

为了验证算法的正确性，需要

线程名称申请时刻持续使用时间设计测试数据，并对测试数据进行\0 15 分析，总结出在该组测试数据下，\1 15 程序应该得到什么结果，然后运行\3 3 程序，将程序运行结果与分析结果\4 2 相比较，如果二者一致，则可认为

程序是正确的。 \5 6 作者设计的测试数据如图4-1\6 10 所示，包括10个线程，其中有5个\7 8 读者线程r1~r5，另外5个是写者线\9 2 程w1~w5。读者线程r1在时刻0提\10 18 出读请求，如果请求得到允许，r1\12 2 将用15秒的时间读文件；写者线程

w3在时刻6提出写请求，如果请求得到允许，w3将用10秒的时间写文件。从表中可以看出，10个线程提出请求的次序是：r1,r2,w1,r3,w2,w3,r4,r5,w4,w5。 1、读者优先算法

线程实际读写文件顺序为：r1,r2,r3,r4,r5,w1,w2,w3,w4,w5。执行情况见图4-2。

图4-2 线程的运行状况图4-1 测试数据线程名称 \\\\\\\\\\

申请时刻 0 1 4 7 9 3 5 6 10 12

持续时间 15 15 2 8 2 3 6 10 18 2

开始操作时刻 0 1 4 7 9 16 19 25 35 53

结束操作时刻 15 16 6 15 11 19 25 35 53 55

2、写者优先算法

线程实际读写文件顺序为：r1,r2,w1,w2,w3,w4,w5,r3,r4,r5。执行情况见图4-3。

图4-3 线程的运行状况线程名称 \\\\\\\\\\

申请时刻 0 1 3 5 6 10 12 4 7 9

持续时间 15 15 3 6 10 18 2 2 8 2

开始操作时刻 0 1 16 19 25 35 53 55 55 55

结束操作时刻 15 16 19 25 35 53 55 57 63 57

3、无优先算法

线程实际读写文件顺序为：r1,r2,w1,r3,w2,w3,r4,r5,w4,w5。执行情况见图4-4。

图4-4 线程的运行状况线程名称 \\\\\\\\\\

申请时刻 0 1 3 4 5 6 7 9 10 12

持续时间 15 15 3 2 6 10 8 2 18 2

开始操作时刻 0 1 16 19 21 27 37 37 45 63

结束操作时刻 15 16 19 21 27 37 45 39 63 65

4.3.2 程序功能及界面设计

该程序采用简单的控制台应用程序界面，在主界面上显示程序的功能。该程序的功能如下：

1. 演示读者优先算法； 2. 演示写者优先算法； 3. 演示无优先算法；

4. 退出。 4.3.3 函数设计

实现读者/写者问题的源程序名称是reader_and_writer.cpp。该程序共包括10个函数。这些函数可以分成4组。各组包含的函数及其功能如图4-5。组别一 main() RF_reader_thread() 二 RF_writer_thread() reader_first() WF_reader_thread() 三 WF_writer_thread() writer_first() FIFO_reader_thread() 四 FIFO_writer_thread() first_come_first_serverd() 包括函数函数功能显示主菜单，接收用户的选择并执行相应的功能。读者优先算法的读者线程函数读者优先算法的写者线程函数读者优先算法的初始化函数：创建10个线程并等待它们结束写者优先算法的读者线程函数写者优先算法的写者线程函数写者优先算法的初始化函数：创建10个线程并等待它们结束无优先算法的读者线程函数无者优先算法的写者线程函数无者优先算法的初始化函数：创建10个线程并等待它们结束图4-5 函数功能简述

程序开始部分定义了宏MAX_THREAD，表示程序中创建的线程数。还定义了测试数据的结构体TEST_INFO，该结构体包含三个数据项：线程名称；提出请求的时刻；操作持续时间。接着定义了全局变量，这些全局变量的作用如下：

数组test_data保存了10个线程的测试数据；

整数read_count记录一段时间内同时对文件进行读操作的线程数；

整数write_count记录一段时间内提出写操作请求的线程数，该整数只在写者优先算法中使用；

CS_DATA是临界区变量，用来保护文件，实现对文件的读—写互斥和写—写互斥（相当于算法描述中的r_w_w）；

互斥体h_mutex_read_count用来保护整数read_count，以保证多个读者对read_count的互斥访问；

互斥体h_mutex_write_count用来保护整数write_count，以保证多个写者对write_count的互斥访问，该互斥体只在写者优先算法中使用；

互斥体h_mutex_first_reader_wait和h_mutex_reader_wait只在写者优先算法中使用，当有写者在写文件时，提出读请求的第一个读者阻塞在h_mutex_first_reader_wait上，其余的读者阻塞在h_mutex_reader_wait上；

互斥体h_mutex_wait只在无优先算法中使用，当文件被使用时，后继的读请求和写请求依次阻塞在h_mutex_wait上。

4.34 参考源程序

#include

Word文档下载：2016操作系统课程设计指导书v1.doc

搜索更多:2016操作系统课程设计指导书v1