实验一 进程同步和互斥.docx

《实验一 进程同步和互斥.docx》由会员分享，可在线阅读，更多相关《实验一 进程同步和互斥.docx（38页珍藏版）》请在课桌文档上搜索。

1、实验一进程同步和互斥（建议4学时）一、实验目的1 .掌握临界资源、临界区概念及并发进程互斥、同步访问原理。2 .学会使用高级语言进行多线程编程的方法。3 .掌握利用VC或JaVa语言线程库实现线程的互斥、条件竞争，并编码实现P、V操作，利用P、V操作实现两个并发线程对有界临界区的同步访问。4 .通过该实验，学生可在源代码级完成进程同步互斥方案的分析、功能设计、编程实现，控制进程间的同步、互斥关系。二、实验要求1 .知识基础：学生应在完成进程和线程及调度等章节的学习后进行。2 .开发环境与工具：硬件平台一一个人计算机。软件平台-WindOWS操作系统，vc语言或JaVa语言开发环境。3 .运用高

2、级语言VC或JaVa语言线程库及多线程编程技术进行设计实现。三、实验内容1 .实现临界资源、临界区、进程或线程的定义与创建。2 .利用两个并发运行的进程，实现互斥算法和有界缓冲区同步算法。四、实验方案指导该实验方案由以下几个关键设计项目组成：1 .并发访问出错。即设计一个共享资源，创建两个并发线程，二者并发访问该共享资源。当没有采用同步算法设计时，线程所要完成的某些操作会丢失。2 .互斥锁。并发线程使用线程库提供的互斥锁，对共享资源进行访问。3 .软件方法。设计并编程实现计数信号量、P操作函数、V操作函数，并发线程通过调用P,V操作函数实现线程的互斥。4 .同步访问多缓冲区。利用上面的软件方法

3、完成P,V操作，可实现两个线程对多缓冲区的同步访问。五、实验方案实现范例以下是对该项目中包含的部分设计功能的实现方法、实现过程、技术手段的描述，供师生参考。1 .模拟线程并发运行。假设我们使用POSix线程库，而POSIX并没有真正提供线程间的并发运行需求。我们设计的系统应支持符合RR调度策略的并发线程，每个线程运行一段时间后自动挂起，另一个线程开始运行。这样一个进程内所有线程以不确定的速度并发执行。2 .模拟一个竞争条件一一全局变量。创建两个线程tl和t2,父线程主函数main。定义两个全局变量accntl和accnt2,每个变量表示一个银行账户，初始化为0。每个线程模拟一个银行事务：将一定

4、数额的资金从一个账户转到另一个账户。每个线程读入一个随机值，代表资金数额，在一个账户上做减法，在另一个账户上做加法，用两个变量记录两个账户的收支情况。良性情况下收支应平衡，即两个全局变量之和应为0。下面是每个线程的代码：Counter=O;dotmpl=accntl;tmp2=accnt2;r=random();accntl=tmplr;accnt2=tmp2-r;counter;while(accntlaccnt2=0);printf(,%dv,counter);两个线程运行的代码相同，只要各自代码不被交叉执行，两个收支余额之和就应一直为如果线程被交叉执行，某个线程可能会读入一个旧的accn

5、tl值和一个新的accnt2值，或反，这样会导致某个值的丢失。当这种情况出现时，线程停止运行，并把出现情况的位置COImter的值）打印出来。3 .模拟一个竞争条件一一共享文件。主线程创建两个共享文件fl和f2,每个文件包含一个当前银行账户。线程使用随机数对文件进行读/写，方式同上。注意：文件在读/写过程中不要加互斥访问锁，以免不会出现交叉访问的情况。4 .测试出现一个竞争条件的时间。我们的编程环境中，一般无法支持线程的RR调度，必须编程实现两个线程间在两个赋值语句之间插入以下代码：在指定区间（比如O到1）生成一个随机数，小于一个极限值（如0.1）,调用线程自动挂起函数jield（）,自动放弃

6、CPU,另一运行，于是导致一个数据更新的丢失。5 .互斥锁。POSIX线程库提供一个二值信号量，称为MUTEX,它可以加锁或解锁。如果已被另一个线程加上锁的MUTEX加锁，就会引发该线程被阻塞，MUTEX解锁时唤醒它。使用这些原语，很容易实现互斥进入CS（临界区）。进入CS区时加锁，离开CS区时解锁。系统负责阻塞或唤醒线程。6 .用软件方法实现互斥访问临界区。用标准编程语言设置变量的值，用线程“忙等待”实现互斥访问CS。设计两线分代码如下：intcl=0,c2=0,will_wait;pl:while(l)cl=l;will_wait=l;while(c2&(will_wait=1);*忙等待

7、*/csl;cl=O;programi;)p2:while(l)c2=l;will_wait=2;while(cl&(will_wait=2);*忙等待*/cs2;c2=0;program2;该软件方法使用三个变量cl,c2,will_wait,解决两个线程的同步问题。两个线程分别将Cl和c2设置为1,表示自己试图进入临界区，并将WilLWait分别设置为1和2,以消除任何竞争条件。通过“忙等待”循环实现线程的阻塞。当线程退出CS区时，分别将变量Cl和c2设置为0。我们可以比较互斥锁和软件方法这两种解决方法的效率。可以通过重复相同的循环次数，测量各自的执行时间，尽量减少可能的外部干扰，重复测试

8、几次，并计算平均值。Sincludeiostreamusingnamespacestd;Sincludewindows.hDWORDWINAPIThreadProcl(LPVOIDIpParameter);DWORDWINAPIThreadProc2(LPVOIDIpParameter);HANDLEhMutex;intcounter=0,accntl=0,accnt2=0,tmpl,tmp2,r;voidmain()(Printf(开始服务:n)；HANDLEhandleI=CreateThread(NULL0,ThreadProcl,NULL,0,NULL);HANDLEhandle2=C

9、reateThread(NULL,O,ThreadProc2,NULL,0,NULL);CloseHandle(handlei);CloseIIandle(handle2);HMutex=CreateMutex(NULL,FALSE,NULL);*控制主进程运行时间*/Sleep(5000);Printf(服务结束n)；/getchar();/VS2008)DWORDWINAPIThreadProcl(LPVOIDIpParameter)(while(accntlaccnt2=0)WaitForSingleObject(hMutex,INFINITE);tmpl=accntl;tmp2zzac

10、cnt2;r=rand();accntl=tmplr;accnt2=tmp2-r;counter;Printf(账户A完成转账一%d,z,counter);Sleep(100);ReleaseMutex(hMutex);)Printf(第%d次转账发生错误,counter);return0;DWORDWINAPIThreadProc2(LPVOIDIpParameter)while(accntlaccnt2=0)WaitForSingleObject(hMutex,INFINITE);tmpl=accntl;tmp2=accnt2;r=rand();accntl=tmplr;accnt2=tm

11、p2-r;counter;Printf(账户B完成转账一%d,z,counter);Sleep(100);ReleaseMutex(hMutex);)Printf(第%d次转账发生错误,counter);return0;实验二进程及其资源管理（建议4学时）一、实验目的1 .理解资源共享与互斥特性，以及操作系统管理资源的基本方法。2 .学会使用高级语言进行多线程编程的方法。3 .掌握利用VC或JaVa线程库实现一个管理器，用来实现操作系统对进程及其资源的管理功能。4 .通过该实验，学生可在源代码级完成进程及其资源管理方案的分析、功能设计、编程实现，控制进程间的同步、互斥关系。二、实验要求1 .知

12、识基础：学生应在完成对进程和线程、调度、死锁等章节的学习后进行。2 .开发环境与工具：硬件平台一一个人计算机。软件平台一一WindoWS操作系统，根据需要，任选安装VC语言、java语言或C语言开发环境。三、实验内容1 .开发一个函数，建立进程控制块和资源控制块结构，并实现相关数据结构的初始化。2 .开发一系列操作，由进程调用这些操作，达到控制进程申请或释放各种资源的目的。四、实验方案指导该实验方案由以下几个关键设计项目组成：1 .进程数据结构表示。2 .资源数据结构表示。3 .进程对资源的操作。4 .调度程序。5 .用户功能Shell界面。五、实验方案实现范例以下是对该项目中包含的设计功能的

13、实现方法、实现过程、技术手段的描述，供师生参考。1 .进程数据结构表示。使用结构类型设计实现进程PCB表，它包含以下成员：进程ID进程的唯一标识，供其他进程引用该进程；内存一一是一个指针链表，它在创建进程时已申请完毕，可用链表实现；其他资源一一表示除去内存之外的所有资源；进程状态一一包括两个数据类型，一个是状态码，另一个是状态队列链表指针；生成树一一包括两个数据类型，本进程的父进程和本进程的子进程；优先级一一供进程调度程序使用，用来确定下一个运行进程，可以设定为静态整数。2 .资源数据结构。每个资源都用一个称为资源控制块的数据结构表示。使用结构类型设计实现资源控制块RCB0资源控制块包括以下字

14、段成员:RID-资源的唯一标识，由进程引用；资源状态一一空闲/已分配；等待队列一一是被本资源阻塞的进程链表，本资源正被其他所有资源都设定为静态数据，系统启动时初始化。3 .进程管理及进程对资源的操作。进程操作及进程状态转换归纳如下：进程创建一一(无)f就绪；申请行一阻塞；资源释放一一阻塞一就绪；删除进程一一(任何状态)一(无)；就绪f运行或运行f就绪。具体实现步骤如下：(1)根据上述数据结构，用高级语言设计相应函数，分别实现创建进程、删除进程、挂起进程、唤醒进程等功能。(2)设计一个函数，实现调度程序，在每个进程操作执行完毕后，自动调用执行。(3)实现两个资源操作：申请资源和释放资源。相关参考

15、算法如下:/*分配给调/*插入一个RCB/*资源不/*记录阻塞/*指向所/*插入资源request(RID)*申请资源算法*/r=get_RCB(RID);*获取资源控制块首地址*/if(r-status=free,)/*资源可用*/r-status=,allocated,;用进程，*/insert(self-other_resources,r);指针指向进程资源链表；*/else(可用*/self-status.type=blocked,;*/self-status.list=r;请求资源的RCB*/,remove(RL,self);/*将进程从就绪队列中删除*/insert(r-waiti

16、ng_list,self);)等待队列*/scheduler();*调度程序运行选择下一个运行进程*/release(RID)/*释放资源算法*/r=get_RCB(RID);/*获取资源控制块首地址*/remove(self-other_resource,r);/*从进程资源链表中删除该资源*/if(waiting_list=NULL)r-status=,free,;*等待队列为空，置资源状态为空闲*/else/*等待队列不为空*/remove(r-waiting_list,q);/*从等待队列中移出一个进程q*/q-status.type=,ready,;*将进程q的状态设为就绪*/*进q

17、-status.Iist=RL;程q的状态指针指向就绪队列*/*insert(RL,q);进程q插入就绪队列*/scheduler();*调度程序运行选择下一个运行进程*/4 .调度程序。调度策略采用固定优先级和可剥夺优先级调度算法。即调度程序必须维护n个不同优先级的就绪队列，各就绪队列可为空，也可包含多个进程。O级进程优先级最低，nT级进程优先级最高。创建进程时就赋予了固定的优先级，并在进程的生存期内保持不变。当新进程创建或阻塞进程被唤醒时，它就被插入同级的就绪队列中。调度程序按“先来先服务”和优先级“从高到低”的方式处理就绪队列。即从最高优先级的非空就绪队列的队首选择一个进程进入运行态。这

18、样的调度策略很容易导致饥饿，进程出现。因为对进程q来说，只有当优先级高于自己的所有进程都运行完毕，或都进入阻塞状态时，它才能得到运行权。为了简化调度程序，我们假定系统中至少有一个进程处于就绪态。为确保这一点，设计一个特殊进程init,该进程在系统初始化时自动创建，并赋予最低优先级O级。init进程有两个作用：充当闲逛进程，该进程运行时不申请任何资源，以免被阻塞；作为第一个被创建的进程，它没有父进程，可创建比自己优先级高的其他进程。所以init进程是进程生成树的根进程。采用优先级策略的调度程序的常见结构知下所示：scheduler()(找出最高优先级进程p；If(self-prioritypri

19、ority)self-status.type!=,running,self=nil)preempt(p,self);*调度进程p,替换当前进程self*/每当任一进程的操作执行完毕，必须执行进程调度程序，它是当前运行进程的一部分。进程调用该函数，后者决定该进程是继续执行还是被其他进程剥夺运行权。作出判断的依据是：是否存在高优先级进程P，如果存在，P将剥夺Self的运行权。当前进程的运行权被剥夺的情况有以下两种：当前进程刚刚完成release（操作，由此被唤醒进程的优先级可能高于当前进程。当前进程刚刚完成Create()操作，新创建进程的优先级可能高于当前进程。在以下两种情况下，新挑选的进程必须

20、剥夺当前进程的运行权：当前进程刚刚完成reques()操作，并且申请的资源timeout则当前进程的状态就改为“阻塞”；或者由于分时运行进程的需要，调度程序被一个timeout操作调用运行。在timeout操作中当前进程的状态改为“就绪”。在上述情况中，当前进程的状态都不是“运行”。所以当前进程必须停止运行，此时就绪队列中最高优先级的进程P得到执行。当进程刚刚完成destroy操作，进程自己删除自身，它的PCB表不再存在。此时调度程序被执行，从就绪队列中选出最高优先级的进程P，并令其执行。剥夺操作包括以下工作：将选中的最高优先级进程P的状态改为“运行。如果当前进程依然存在且没CPU,则将其状态

21、改为“就绪”，以便随后能得到执行。最后，进行上下文切换，保留当前CPU的各个寄存器值，放入PCB表。装入中选进程P的寄存器值。本实现方案没有对实际的CPU进行访问来保存或恢复寄存器的值，因此上下文切换的任务只是将正在运行进程的名字显示在终端屏幕上。从这一点可以认为，用户终端屏幕开始扮演当前运行进程功能的角色。5 .用户shell界面。为RCB试和演示管理器的CPU能，本方案设计开发一个shell界面，它可以重复接受终端输入的命令，唤醒管理器执行相应的功能，并在屏幕上显示结果。使用上述系统，终端就能展示当前进程。只要输入一个命令，就中断当前进程序的执行，ShelI界面调用进程资源管理器中的函数F

22、,并传递终端输入的参数。该函数执行后将改变PCB、RCB及其他数据结构中的信息。当调度程序执行时，决定下一个要运行的进程，并改变其状态值。保存当前进程的CPU各寄存器值(虚拟CPU),然后恢复中选进程的值。调度程序将系统状态信息显示在屏幕上，提示下一步操作。特别地，它始终提示正在运行的进程是什么，即终端和键盘正在为哪个进程服务。另外，函数F也可能返回一个错误码，shell也将它显示在屏幕上。shell命令的语法格式规定如下：命令名参数例如，执行命令行“crAl”时将调用对应的管理器函数create(A,1),即创建一个名为A、优先级为1的进程。同理，命令“rq令将调用函数request(R)执

23、行。以下显示说明ShelI界面的交互内容(假定进程A的优先级为1,并且正在运行)。由开始的行视为ShelI的输固结果。提示符后面是提示用户输入的命令。*processAisrunningcrB2*processBisrunningcrC1* processBisrunning* reqRl* processBisblocked;processAisrunning6.进程及资源管理器的升级版。可对上述基本型进程功能资源管理器进行功能扩展，使管理器能够处理时钟到时中断和I/O处理完成中断。(1)相对时钟到时中断。假设系统提供一个硬件时钟。周期性产生一个时钟到时中断。引发调用函数timeout()的

24、执行。(2)110处理完成中断。使用名为IO的资源表示所有的I/O设备。该资源的RCB由以下两部分组成：IOWaiting_list(3)扩展Shel1。显示当前运行进程，并添加一个系统调用request_100o终端也能表示硬件，用户能够模拟两种类型的中断：时钟到时、I/O完成处理。为了实现以上功能，必须添加新的SheII命令，调用以下三个系统调用：request_IO(),10_competion,timeout()。实验三存储管理(建议4学时)一、实验目的1 .掌握内存管理的基本功能和分区法内存分配的基本原理。2 .学会Linux操作系统下使用c语言函数和系统调用进行编程的方法。3 .利

25、用C语言设计实现分区法内存分配算法。4 .验证无虚存的存储管理机制。二、实验要求1 .学生应完成如下章节的学习：进程和线程、调度、存储管理。2 .安装LinUX操作系统，使用C语言编程，调用相关系统调用进行设计实现。三、实验内容1 .创建空闲存储管理表和模拟内存。2 .设计并实现一个内存分配程序，分配策略可以分别采用最先适应算法、最佳适应算法和最坏适应算法等，并评价不同分配算法的优劣。3 .提供一个用户界面，利用它用户可输入不同的分配策略。4 .进程向内存管理程序发出申请、释放指定数量的内存请求，内存管理程序调用对应函数，响应请求。四、实验方案指导该实验方案由以下几个关键设计项目组成。1 .设

26、计实现一个空闲分区表。2 .设计实现模拟内存。考虑实现的便利，本方案不访问真正的内存。定义一个字符数组Charmmmem_size或使用LimIX系统调用mm=malloc(meni_size),用来模拟内存。利用指针对模拟内存进行访问。3 .设计一组管理物理内存空间的函数。用户接口由以下三个函数组成：voidmrequest(intn)申请n个字节的内存空间。如申请成功，则返回所分配空间的首地址；如不能满足申请，则返回空值。voidmm_release(void*p)释放先前申请的内存。如果释放的内存与空闲区相邻，则合并为一个大空闲区；如果与空闲区不相邻，则成为一个单独的空闲区。void*m

27、m_init(intmem_size)内存初始化。返回mm指针指向的空闲区。4 .设计实现不同策略的内存分配程序。对于采用不同分配策略的内存管理程序，从以下两个方面进行调度程序性能的比对：内存利用率以及找到一个合适的分配空间所需查找的步骤。设置一个模拟实验。分别构建一个随机生成的请求与释放队列。释放队列中的操作总是得到满足，队列总为空；请求队列的操作能否被满足，取决于空闲区能否满足申请的空间大小。若不能满足，则该操作在队列中等待相应释放操作唤醒。请求队列采用FlFO管理，以避免饥饿现象的发生。内存管理程序应对内存初始化，随机设定内存空间的占有、空闲情况，随机设定申请和释放的操作队列。调用释放操

28、作开始运行，调用申请操作，如能满足，则分配空间，否则等待释放操作唤醒。下面给出一个模拟内存管理的程序框架(伪码形式)。可对性能数据指标进行统计。*设定*设定请求空间/*调用请求操作/*请求成/*统计内/*释放/*调用for(i=0;isim_step;i)模拟程序执行次数*/do循环调用请求操作，直到请求不成功*/getsizenofnextrequest;大小*/mm_request(n);*/while(requestsuccessful);功，循环继续*/recordmemoryutilization;存使用率*/selectblockptoberelease;某空间P*/release

29、(p);释放操作*/以上程序由主循环控制固定次数的模拟步骤。每次循环，程序完成如下处理步骤：内循环尽可能多地满足内存请求，请求内存大小值随机生成。一旦请求失败，挂起内存管理程序，直至释放操作被执行。此时进行系统内存利用率的统计、计算，随机挑选一个内存分配空间完成释放操作。本次主循环执行完毕，开始下一次循环。需要在程序中完成以下设计：确定请求分配空间大小，统计性能数据，选择一个内存区释放。实验四页面置换算法（建议4学时）一、实验目的1 .掌握内存管理基本功能和请求分页式管理的基本原理以及页面置换算法。2 .学会在LinUX操作系统下使用C函数和系统调用的编程方法。3 .掌握利用C语言设计实现不同

30、置换策略的页面置换算法。4 .验证虚存存储管理机制及其性能。对于生成的引用串，计算、比对不同页面置换算法的缺页率。二、实验要求1 .学生应完成如下章节的学习：进程和线程、调度、存储管理。2 .安装LinUX操作系统，使用C语言编程，利用相关系统调用实现设计。三、实验内容1 .创建空闲存储管理表、模拟内存、页表等。2 .提供一个用户界面，用户利用它可输入不同的页面置换策略和其他附加参数。3 .运行置换程序，输出缺页率结果。四、实验方案指导熟悉页面置换算法及其实现，了解计算机系统性能评价方法，编制页面置换算法的模拟程序。方案设计重点提示如下。1 假定系统有固定数目的内存块F,物理块号依次为0F-I

31、o进程的大小为P页，其逻辑页号依次为0PT。随机生成一个引用串RS,即从0PT组成的整数序列。定义一个整型数组intMF表示所有物理块，如果Mi=n,表示逻辑页n存放在物理块i中。2 .生成引用串。用随机数方法产生页面走向，页面走向长度为L3 .根据页面走向，分别采用FlFO和LRU算法进行页面置换，设计一个函数自动统计缺页率。4 .假定可用内存块和页表长度（进程的页面数）分别为m和ko初始时，进程的页面都不在内存。5 .参考其他设计项目，将不同置换算法设计实现为函数，能在界面上方便调用执行。实验五进程调度（建议4学时）一、实验目的1 .掌握进程调度程序的功能和调度程序采用的调度算法。2 .学

32、会在LinUX操作系统下使用C函数和系统调用的编程方法。3 .掌握利用C语言设计实现不同调度策略的进程调度算法。4 .验证不同进程调度算法对性能的影响。二、实验要求1 .学生应完成如下章节的学习：进程和线程、调度。2 .安装LinUX操作系统，使用C语言编程，利用相关系统调用完成设计实现。三、实验内容1 .定义、初始化进程数据结构及其就绪队列。2 .提供一个用户界面，用户利用它可输入不同的分配策略及相关参数。3 .设计实现调度程序，调用下面的功能函数。4 .设计函数，实现计算平均周转时间，实现不同调度算法。四、实验方案指导关键设计内容如下，供参考。1 .用C语言的结构类型及其链表，完成PCB表

33、数据结构设计，并动态生成一组进程组成的就绪队列链表。每个进程都由PCB记录运行时间，优先级、到达系统时间等数据。也可根据需要，自行添加不同调度算法需要的数据。2 .设计实现不同调度算法的函数，如先来先服务法、短作业优先法、优先级法等。设计一个函数，计算出这组进程的平均周转时间。3 .设计总控函数，实现进程调度程序。根据用户界面的输入，调用相应的调度算法，实现进程调度，计算调度性能指标。实验六银行家算法（建议4学时）一、实验目的1 .理解死锁概念、银行家算法及安全性检测算法。2 .学会在LinUX操作系统下使用C语言函数和指针进行编程的方法。3 .掌握利用C语言设计实现银行家算法的基本过程。4

34、.验证银行家算法对于避免死锁的作用。二、实验要求1 .学生应完成如下章节的学习：进程和线程的调度。死锁。2 .安装LinUX操作系统，使用C语言编程完成设计实现。三、实验内容1 .定义并初始化进程及其资源数据结构。2 .提供一个用户界面，用户利用它可动态输入进程和资源种类等相关参数3 .设计实现安全状态检测和银行家死锁避免算法的功能函数。四、实验方案指导以如下几组初始数据为例，设计相应程序，判断下列状态是否安全。1.3个进程共享12个同类资源状态a下：allocation=(1,4,5),max=(4,4,8)o判断系统是否安全。状态b下:allocation=(1,4,6),max=(4,6

35、,8)0判断系统是否安全。2.5个进程共享多类资源状态C下：判断系统是否安全？若安全，给出安全序列。若进程2请求(0,4,2,0),可否立即分配?分配矩阵最大需求矩阵可用资源矩阵0012520001210001354063200141750实现方案的主要作是如何输入，如何初始数据，如何调用对应功能函数，如何输出结果。下面给出一个实现方案，供参考。1 .开发一个交互程序，首先从文件中读入系统描述信息，包括进程的数目、资源的种类和数量、每个进程的最大资源请求。程序自动根据文件内容创建一个当前系统描述例如，每类资源的数目用维数组Rm描述，田为资源的种类。每个Rj记录资源Rj的数量。进程的最大需求矩阵

36、用Pnm表示，Pilj记录进程Pi对资源Rj的最人需求。分配矩阵和请求矩阵可使用二维数组表示。2 .用户输入一个请求，格式类似：resquest(i,j,k),或released,j,k),在这里，i表示进程Pi,j表示资源Rj,k是申请/释放的数量。对每一个请求，系统回应是满足要求还是拒绝分配。3 .设定一个申请和释放序列，无任何检测和避免死锁的算法，分配会导致死锁。4 .设定一个申请和释放序列，按照安全性算法进行设计，回应系统是否安全。然后实现银行家算法，确保没有死锁的分配。实验七磁盘调度算法(建议4学时)一、实验目的1 .理解文件读/写基本原理和磁盘调度算法的作用。2 .学会在Linux

37、操作系统下使用C语言函数和指针进行编程的方法。3 .利用C语言设计实现不同磁盘调度算法，如FlF0,SSTF,SCAN等算法。4 .验证不同磁盘调度算法对性能的影响。二、实验要求1 .学生应完成如下章节的学习：进程和线程、调度、存储管理、I/O管理。2 .安装LinUX操作系统，使用C语言编程完成设计实现。三、实验内容1 .设计一个函数，其功能是动态创建I/O请求队列及其相关参数，如磁道号等。2 .提供一个用户界面，用户可输入不同的分配策略以相关参数。3 .设计相应程序计算平均移臂距离。四、实验方案指导实现本实验的关键内容如下，供参考。1 .实现电梯算法。2 .实现FlFO,SSTF算法。3

38、.写一个驱动程序，测试不同的算法。设置多次循环，每次循环中，驱动程序随机调用函数request(n)和release()0如果执行request(n),系统会将n转换成T之间的一个随机值，T是磁盘的磁道数。对每种算法，计算平均移臂距离。实验八设备处理程序设计(建议4学时)一、实验目的1 .理解设备处理程序的一般设计过程，加深对缓冲和中断概念的理解。2 .学会在Linux操作系统下使用C语言编程与有关进程的系统调用方法。3 .掌握利用C语言设计实现键盘缓冲区的读/写操作的方法。4 .验证键盘缓冲区和中断处理程序是否同步。二、实验要求1 .学生应完成如下章节的学习：进程和线程、调度、存储管理、I/

39、O管理。2 .安装LinUX操作系统，使用C语言和相关系统调用，编程完成设计实现。三、实验内容1 .主程序实现键盘读/写、键盘中断处理程序。2 .可修改缓冲区数目，运行此程序。四、实验方案指导1 .将主程序看成消费者进程，将中断程序看成生产者进程，两者通过什么方法取缗d步？其数据结构是什么？2 .当缓冲区数目分别为2,5,10时，运行此程序，是否发生输入字符没有被显示携情况（加快输入速度）？为什么？若在主程序显示字符子程序中加入一段延迟程序，对整个程序有何影响？和问题）k=A讨论，并做实验。以上设计方案供读者选择。两个程序的流程为图AT所示。是否图A-I键盘缓冲区读/写与中断处理程序的同步实验

40、九文件系统（建议4学时）一、实验目的1 .理解并实现文件的构造、命名、存取、使用、保护等功能，加深对文件操作、文件存储的理解。2 .掌握文件系统的功能，通过数据结构定义文件系统，并完成相应操作。3 .学会在Linux操作系统下使用C语言编程和有关文件的系统调用的方法。4 .掌握利用C语言设计实现文件读/写等操作的方法。5 .验证文件存储空间管理功能，验证磁盘调度算法的实现。二、实验要求1 .用C语言中链表结构模拟定义I节点数据结构及其相关数据块数据结构。2 .设计函数，实现随机大小的文件的磁盘空间分配，并显示分配结果。3 .设计函数，实现文件指定磁盘空间的查找，并显示结果。三、实验内容1 .设

41、计一个用户界面，用户可输入不同的参数，表示运行不同的函数功能。如空闲存错空间、磁盘调度分配策略等。2 .设计一个函数，实现空闲存储空间的管理。3 .设计一个函数，实现I节点方式的文件存储。4 .设计多个函数，实现按不同调度策略计算平均移臂距离。四、实验方案指导空闲存储空间的管理与实现。以成组链接法为例，编程模拟实现磁盘空闲区的管理。空闲块成组链接如图6-22所示。有以下几个关键实验步骤：(1)用c语言链表结构自动生成以上空闲块成组链接表。(2)设计实现空闲块成组链接法空闲块分配函数，函数功能是对超级块进行以下操作：重复进行栈深减1操作，取出磁盘块号。当栈深为1时，堆栈当前指针指向本组第一块，即

42、正好取(3)一个组的组长盘块号，将其内容写入堆栈，重复栈深减1的操作，继续分配磁盘块。（3）设计实现空闲块成组链接法空闲块释放函数，函数功能是对超级块进行以下操作：重复进行栈深加1操作，存入磁盘块号。当栈深为50时,此时又释放一个磁盘块，并将当前栈中内容写入该磁盘块（组长），并将栈深设定为1,堆栈的第一个索引位置（0）填入该磁盘块块号，它是新一组的组长块。此时如继续释放，进行栈深加1操作存入磁盘块号（1）。（4）随机对成组链表初始化，调用分配函数或回收函数，输出成组链表结果。验证分配和回收的正确性。读者可能会问：一个文件在存储设备上如何存放？采用哪种存取方法？文件的存储分配涉及以下三个问题：创建新文件时，是否一次性分配所需的最大空间？为文件分配的空间是否连续？为了记录分配给各个文件的磁盘空间，应该使用何种数据结构来记录？已知每个文件有一个I节点，其中列出了文件属性和文件分配的各块号，存放物理块号的方式如下：开始的10个磁盘块号放在I节点中（直接块），对于稍大的文件，I节点中有一个一次间接地址，指向存放磁盘块地址的磁盘块（间接块），如果文件更大，I节点中有一个二次间接地址，指向一次间接地址块，再由它们指向存放磁盘块地址的盘块。如图6-19所示。