操作系统课程设计指导书.doc

操作系统课程设计指导 操作系统课程组 长春工业大学 前言 操作系统课程是计算机科学与技术专业、网络工程专业以及软件工程 专业的必修课，在课程体系中占有重要地位。操作系统本身具有概念抽象、 结构复杂和难于掌握的特点，要想掌握操作系统精髓，不仅要做适量的习 题，更重要的是动手设计。通过设计，可以加深对基本原理的理解，激发 学习兴趣，增强自信心。 本指导书具有以下特点： 设计题目难度和容量适中 操作系统课程在一个学期内讲完，课内的设计学时为 27。要求设计 既覆盖教学内容，又能在规定学时内做完，因此，按照操作系统的知识体 系，本书共安排 8 个设计，每位学生按照要求选择 2 个题目。本书的设计 题目难度和容量适中，能满足设计教学要求。 并发程序设计技术贯穿本书 并发程序设计技术是操作系统设计的精髓，也是当今大多数系统软件 和应用软件设计的精髓。学生在其他课程中很少有机会训练并发程序设计 能力。其它操作系统试验教材对该技术的训练也不充分，只在涉及进程同 步的设计中使用。 目目 录录 设计设计 1 1 动态异长分区内存分配与去配算法的设计动态异长分区内存分配与去配算法的设计- -最先适应算法最先适应算法.1 1.1 设计目的 .1 1.2 设计要求 .1 1.3 设计步骤 .1 1.3.1 数据结构分析.1 1.3.2 算法分析.1 1.3.3 设计并分析测试数据.2 1.3.4 程序设计.3 1.3.5 参考源代码.4 设计设计 2 2 动态异长分区内存分配与去配算法的设计动态异长分区内存分配与去配算法的设计- -最佳适应算法最佳适应算法.10 2.1 设计目的 .10 2.2 设计要求 .10 2.3 设计步骤 .10 2.3.1 数据结构分析.10 2.3.2 算法分析.11 2.3.3 设计并分析测试数据.11 2.3.4 程序设计.12 2.3.5 参考源代码.13 设计设计 3 3 动态异长分区内存分配与去配算法的设计动态异长分区内存分配与去配算法的设计- -最差适应算法最差适应算法.20 3.1 设计目的 .20 3.2 设计要求 .20 3.3 设计步骤 .20 3.3.1 数据结构分析.20 3.3.2 算法分析.21 3.3.3 设计并分析测试数据.21 3.3.4 程序设计.22 3.3.5 参考源代码.23 设计设计 4 4 采用预先分配法预防死锁的哲学家就餐问题采用预先分配法预防死锁的哲学家就餐问题.30 4.1 设计目的 .30 4.2 设计要求 .30 4.3 设计步骤 .30 4.3.1 程序结构设计.30 4.3.2 算法设计.30 设计设计 5 5 采用有序分配法预防死锁的哲学家就餐问题采用有序分配法预防死锁的哲学家就餐问题.32 5.1 设计目的 .32 5.2 设计要求 .32 5.3 设计步骤 .32 5.3.1 程序结构设计.32 5.3.2 算法设计.32 设计设计 6 6 不预防死锁情况下的哲学家就餐问题不预防死锁情况下的哲学家就餐问题.34 6.1 设计目的 .34 6.2 设计要求 .34 6.3 设计步骤 .34 6.3.1 程序结构设计.34 6.3.2 算法设计.34 设计设计 7 7 假脱机打印程序与虚拟设备假脱机打印程序与虚拟设备.36 7.1 设计目的.36 7.2 设计要求.36 7.3 数据结构分析 .37 7.4 程序结构 .37 设计设计 8 8 读者读者/ /写者问题与进程同步写者问题与进程同步.41 8.1 设计目的 .41 8.2 设计要求 .41 8.3 设计步骤 .42 8.3.1 设计测试数据.42 8.3.2 程序功能及界面设计.43 8.3.3 函数设计.44 8.3.4 参考源程序.44 操作系统课程设计候选题目操作系统课程设计候选题目.51 操作系统课程设计报告要求操作系统课程设计报告要求.53 附录附录 1 1 WINDOWSWINDOWS APIAPI.54 主要参考文献主要参考文献.61 设计设计 1 1 动态异长分区内存分配与去配算法的设计动态异长分区内存分配与去配算法的设计- -最先适应算法最先适应算法 1.11.1 设计目的设计目的 理解存储管理的功能，掌握动态异长分区内存管理中的最先适应算法。 1.21.2 设计要求设计要求 本设计要求模拟最先适应算法的分配算法和回收算法。 1.31.3 设计步骤设计步骤 1.3.11.3.1 数据结构分析数据结构分析 为了实现存储资源的分配和回收，操 作系统需要记录内存资源使用情况，即哪 些区域尚未分配，哪些区域已经分配以及 分配给哪些进程等。为此一般需要两个表， 一个为分配表, 另外一个为空闲区域表。 前者记录已经分配的区域, 后者记录着所 有当前未被进程占用的空闲区域, 如图 1- 1 所示。 显然, 没有记录于表中的区域即为已被进程所占用的非空闲区域，在实际的 操作系统中，这些区域登记在进程的 PCB 中。而 PCB 中除了关于内存资源的信息 外，还有其它大量信息。 由于本设计是对存储管理算法的模拟，所以用一个线程来代表一个进程，用 线程驻留区域表来描述线程占用的内存空间，如图 1-2 所示。 线程名称驻留区始址驻留区大小 a010 b2020 图 1-2 线程驻留区表 同时，需要一张表来记录各个线程对内存的请求信息，如图 1-3 所示。 线程名称请求大小(KB)预计驻留时间( 秒) thread_1204 thread_2105 图 1-3 内存申请表 1.3.21.3.2 算法分析算法分析 对于存储申请命令, 选取满足申请长度要求且起始地址最小的空闲区域。在 实现时, 可将系统中所有的空闲区域按照起始地址由小到大的次序依次记录于空 空闲区域首址空闲区域长度 addrsize 图 1-1 空闲区域表 闲区域表中。当进程申请存储空间时, 系统由表的头部开始查找, 取第一个满足 要求的表目。如果该表目所对应的区域长度恰好与所申请的区域长度相同, 则将 该区域全部分配给申请者。否则将该区域分割为两部分, 一部分的长度与所申请 的长度相同, 将其分配给申请者；另一部分的长度为原长度与分配长度之差, 将 其仍记录于空闲区域表中。 回收时，按回收区的首地址查询空闲区表，若有与回收区相临的空闲区，则 将其合并到相临区中，否则，把回收区按照地址从低到高的顺序插入到空闲区域 表的适当位置。 1.3.31.3.3 设计并分析测试数据设计并分析测试数据 假设初始内存布局如图 1-4，图中的起始地址以及大小都以 KB 来衡量。 起始地址0 102040708085145160180 占用者 abcde 大 小 1010203010560152020 图 1-4 初始内存布局 由图 1-4 可见，初始时共有五个线程驻留在内存，它们是 a,b,c,d,e，线程 驻留区表如图 1-5；还有五个空闲区，空闲区域表如图 1-6。 假设现在有三个线程提出内存申请，申请情况见图 1-7。经过分析我们得到 在每种分配算法下这三个线程所申请到的内存情况。图 1-8 是最先适应算法分配 情况。 线程名称驻留区始址驻留区大小 a010 b2020 c7010 d8560 e16020 图 1-5 线程驻留区表 空闲区首址空闲区长度 1010 4030 805 14515 18020 图 1- 6 空闲区域表 线程名称 请求大小 (KB) 预计驻留 时间( 秒) thread_1204 thread_2105 thread_356 图 1-7 内存申请表 线程名称驻留区始址驻留区大小 a010 b2020 c7010 d8560 e16020 thread_14020 thread_21010 thread_3605 图 1-8 最先适应算法线程驻留区表 1.3.41.3.4 程序设计程序设计 程序包含两个文件，一个是头文件 variable_partition.h，另一个是源程序 文件 variable_partition.cpp。在头文件中定义了宏、数据结构、全局变量、函 数声明，源程序中含有各个函数的实现。 在头文件中，结构体 FREEAREA、REQUIRE_MEMORY、THREAD_RESIDENCE_MEMOR Y 分别对应于图 1-1、图 1-2、图 1-3 中的一行，不同之处是为了构成链表在三个 结构体中都有前向指针。数组 init_free_area_table 对应于图 1-6，数组 init_t hread_require_memory_table 对应于图 1-5，数组 init_thread_residence_memo ry_table 对应于图 1-7，为了实现动态分配与释放，用链表重新组织空闲区域表 、线程驻留区表和内存申请表，全局变量 p_free_area_list 是空闲区链首，p_th read_require_memory_queue 是内存申请队列的队首，p_thread_residence_memo ry_list 是线程驻留区链首，tail_thread_residence_memory_list 是线程驻留区 链尾，由于线程驻留区链表被内存分配函数和内存释放函数共享，故用临界区变 量 CS_THREAD_MEMORY_LIST 来保护，同理，屏幕是所有线程共享的，所以用临界 区变量 CS_SCREEN 来保护,空闲区链表被内存分配函数和内存释放函数共享，故用 临界区变量 CS_FREEAREA_LIST 来保护。h_thread 是线程句柄数组，用来存放各 个线程的句柄。 程序共包含 12 个函数，按照作用可以将它们分成五组。 第一组包括函数 print_space()和函数 display_thread_residence_memory()， 前者用来显示若干个空格，后者用来显示线程驻留区表； 第二组共十个函数，用来实现最先适应分配法，它们的名称及功能如图 1- 9。 函数名称函数功能 FF_initialize_freearea_list初始化空闲区链表：按地址从低到高排序 FF_delete_freearea_list删除空闲区链表 FF_initialize_require_memory_list初始化内存申请链表 FF_delete_require_memory_list删除内存申请链表 FF_initialize_thread_residence_memory_list初始化线程驻留区链表 FF_delete_thread_residence_memory_list删除线程驻留区链表 FF_thread线程函数：申请内存；驻留内存；释放内存 FF_require_memory内存申请函数 FF_release_memory内存释放函数 FF()初始化函数：创建线程并等待它们结束 图 1-9 最先适应分配法的函数及其功能 1.3.51.3.5 参考源代码参考源代码 下面是部分程序的源代码清单。 头文件 variable_partition.h 的清单 #include #include #include #include #include #include #define MAX_THREAD 3 typedef struct freearea /表示空闲区域的数据结构 struct freearea *next; /指向下一个结点的指针 int start_address; /空闲区起始地址 int size; /空闲区大小 FREEAREA; typedef struct require_memory /记录线程申请内存的数据结构 struct require_memory *next; /指向下一个结点的指针 char thread_name10; /线程名 int size; /申请内存大小（以 KB 为单位） int duration; /在内存的驻留时间（以秒为单位） REQUIRE_MEMORY; typedef struct thread_residence_memory /描述线程驻留区的数据结构 struct thread_residence_memory *next; /指向下一个结点的指针 char thread_name10; /线程名 int start_address; /驻留区起始地址 int size; /驻留区大小 THREAD_RESIDENCE_MEMORY; FREEAREA init_free_area_table5= NULL,10,10, NULL,40,30, NULL,80,5, NULL,145,15, NULL,180,20 ; /测试数据：初始空闲区表 REQUIRE_MEMORY init_thread_require_memory_table3= NULL,thread_1,20,4, NULL,thread_2,10,5, NULL,thread_3,5,6 ; /测试数据：初始内存申请表 THREAD_RESIDENCE_MEMORY init_thread_residence_memory_table5= NULL,a,0,10, NULL,b,20,20, NULL,c,70,10, NULL,d,85,60, NULL,e,160,20 ;/测试数据：初始线程驻留区表 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_threadMAX_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(); /最先适应分配算法的初始化函数 源程序文件 variable_partition.cpp 的清单 #include variable_partition.h void print_space(int num) /显示若干个空格 int i; for(i=0;ithread_name); print_space(18-strlen(p-thread_name); printf(| %d,p-start_address); itoa( p-start_address, buffer, 10 ); print_space(19-strlen(buffer); printf(| %d,p-size); itoa(p-size, buffer, 10 ); print_space(17-strlen(buffer); printf(|n); p=p-next; ; printf(|-|-|-|nn); /最先适应分配法：初始化空闲区链表 FREEAREA *FF_initialize_freearea_list(FREEAREA *init_table,int num) FREEAREA *temp; FREEAREA *head=NULL; FREEAREA *tail=NULL; int i; for(i=0;istart_address=init_tablei.start_address; temp-size=init_tablei.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;ithread_name,init_tablei.thread_name); temp-size=init_tablei.size; temp-duration=init_tablei.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;ithread_name,init_tablei.thread_name); temp-start_address=init_tablei.start_address; temp-size=init_tablei.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( printf(create thread:%sn,(REQUIRE_MEMORY *)(data)-thread_name); LeaveCriticalSection( 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( /加入线程驻留区链表 tail_thread_residence_memory_list-next=temp; tail_thread_residence_memory_list=tail_thread_residence_memory_list-next; LeaveCriticalSection( /显示线程驻留区链表 EnterCriticalSection( printf(after %s %sn,(REQUIRE_MEMORY *)(data)-thread_name,get memory:); display_thread_residence_memory_list(); LeaveCriticalSection( Sleep(REQUIRE_MEMORY *)(data)-duration); /释放内存 FF_release_memory(start_address,(REQUIRE_MEMORY *)(data)-size); /最先适应分配法：内存申请函数 int FF_require_memory(int size) /请读者自己实现这段代码 /最先适应分配法：内存释放函数 void FF_release_memory(int start_address,int size) EnterCriticalSection( /请读者自己实现这段代码 LeaveCriticalSection( /最先适应分配算法的初始化程序 void FF( ) int i=0; REQUIRE_MEMORY *p; HANDLE h_threadMAX_THREAD; InitializeCriticalSection( InitializeCriticalSection( InitializeCriticalSection( 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_threa d_residence_memory_table,5); p=p_thread_require_memory_queue; while(p!=NULL) h_threadi=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(FF_thread),p,0,NULL); i+; p=p-next; ; WaitForMultipleObjects(MAX_THREAD,h_thread,TRUE,-1); /等待所有线程结束 EnterCriticalSection( printf(after all threads have finished:n); display_thread_residence_memory_list(); /显示驻留线程链表 LeaveCriticalSection( /删除各种链表 FF_delete_freearea_list(); FF_delete_require_memory_list(); FF_delete_thread_residence_memory_list(); getch(); printf(n); void main( ) FF( ); 设计设计 2 2 动态异长分区内存分配与去配算法的设计动态异长分区内存分配与去配算法的设计- -最佳适应算法最佳适应算法 2.12.1 设计目的设计目的 理解存储管理的功能，掌握动态异长分区内存管理中的最佳适应算法。 2.22.2 设计要求设计要求 本设计要求模拟最佳适应算法的分配算法和回收算法。 2.32.3 设计步骤设计步骤 2.3.12.3.1 数据结构分析数据结构分析 为了实现存储资源的分配和回收，操 作系统需要记录内存资源使用情况，即哪 些区域尚未分配，哪些区域已经分配以及 分配给哪些进程等。为此一般需要两个表， 一个为分配表, 另外一个为空闲区域表。 前者记录已经分配的区域, 后者记录着所 有当前未被进程占用的空闲区域, 如图 2- 1 所示。 显然, 没有记录于表中的区域即为已被进程所占用的非空闲区域，在实际的 操作系统中，这些区域登记在进程的 PCB 中。而 PCB 中除了关于内存资源的信息 外，还有其它大量信息。 由于本设计是对存储管理算法的模拟，所以用一个线程来代表一个进程，用 线程驻留区域表来描述线程占用的内存空间，如图 2-2 所示。 线程名称驻留区始址驻留区大小 a010 b2020 图 2-2 线程驻留区表 同时，需要一张表来记录各个线程对内存的请求信息，如图 2-3 所示。 线程名称请求大小(KB)预计驻留时间( 秒) thread_1204 thread_2105 图 2-3 内存申请表 空闲区域首址空闲区域长度 addrsize 图 2-1 空闲区域表 2.3.22.3.2 算法分析算法分析 分配时取满足申请要求且长度最小的空闲区域。在实现时, 可将系统中所有 的空闲区域按照长度由小到大的次序依次记录于空闲区域表中。与最先适应算法 相类似, 当进程申请存储空间时, 系统由表的头部开始查找, 取第一个满足要求 的表目。如果该表目所对应的区域长度恰好与所申请的区域长度相同, 则将该区 域全部分配给申请者。否则将该区域分割为两部分, 一部分的长度与所申请的长 度相同, 将其分配给申请者；另一部分即剩余部分的长度为原长度与分配长度之 差, 由于剩余部分的长度已经改变，所以应重新将其按长度从小到大的顺序插入 到空闲区域表中。 回收时，不仅要按回收区的首地址查询空闲区表，找到与回收区相临的空闲 区，将其合并到相临区中，而且要把合并后的回收区按照长度递增的顺序插入到 空闲区域表的适当位置。 2.3.32.3.3 设计并分析测试数据设计并分析测试数据 假设初始内存布局如图 2-4，图中的起始地址以及大小都以 KB 来衡量。 起