用信号量机制实现的写者优先的算法如

本科实验报告实验名称：操作系统原理实验（读者写者问题）课程名称：操作系统原理实验时间：2015.10.30 任课教师：王耀威实验地点：10#102实验教师：苏京霞实验类型： 原理验证□综合设计□自主创新学生姓名：孙嘉明学号/班级：1120121474/05611202 组号：学院：信息与电子学院同组搭档：专业：信息对抗技术成绩：实验二：读者写者问题一、实验目的1.通过编写和调试程序以加深对进程、线程管理方案的理解；2.熟悉Windows多线程程序设计方法；二、实验要求在Windows环境下，创建一个控制台进程，此进程包含n个线程。

用这n个线程来表示n个读者或写者。

每个线程按相应测试数据文件（后面介绍）的要求进行读写操作。

用信号量机制分别实现读者优先和写者优先问题。

读者-写者问题的读写操作限制（包括读者优先和写者优先）1）写-写互斥：不能有两个写者同时进行写操作2）读-写互斥：不能同时有一个线程在读，而另一个线程在写。

3）读-读允许：可以有一个或多个读者在读。

读者优先的附加限制：如果读者申请进行读操作时已有另一个读者正在进行读操作，则该读者可直接开始读操作。

运行结果显示要求：要求在每个线程创建、发出读写申请、开始读写操作和结束读写操作时分别显示一行提示信息，以确定所有处理都遵守相应的读写操作限制。

测试数据文件包括 n行测试数据，分别描述创建的n个线程是读者还是写者，以及读写操作的开始时间和持续时间。

每行测试数据包括四个字段，每个字段间用空格分隔。

第1个字段为正整数，表示线程的序号。

第2个字段表示线程的角色，R表示读者，W表示写者。

第3个字段为一个正数，表示读写开始时间：线程创建后，延迟相应时间（单位为秒）后发出对共享资源的读写申请。

第4个字段为一个正数，表示读写操作的延迟时间。

当线程读写申请成功后，开始对共享资源进行读写操作，该操作持续相应时间后结束，释放该资源。

下面是一个测试数据文件的例子(在记事本手工录入数据)：1 R 3 52 W 4 53 R 5 24 R 6 55 W 5.1 3三、实验环境硬件设备：个人计算机。

附件1：学号：012081034课程设计进程同步模拟设计——读者和题目写者问题学院计算机科学与技术学院专业计算机科学与技术班级计算机科学与技术姓名指导教师2011 年 1 月19 日目录目录 (1)1 设计概述 (4)1.1问题描述： (4)1.1.1规则： (4)1.1.2读者和写者的相互关系： (4)1.2采用信号量机制 (4)1.3 C++语言程序模拟用信号量机制实现生产者和消费者问题 (5)2课程设计目的及功能 (5)2.1 设计目的 (5)2.2 设计功能： (5)3 需求分析，数据结构或模块说明(功能与框图) (5)3.1数据结构 (5)3.2模块说明 (6)3.3开发平台及源程序的主要部分 (6)3.3.1写操作的设计： (6)3.3.2读操作的设计： (7)3.3.3主函数的设计： (9)3.4 功能流程图 (12)4测试用例，运行结果与运行情况分析 (12)4.1测试用例 (12)4.2运行结果 (13)4.3运行情况分析 (14)5自我评价与总结 (15)6 参考文献 (16)课程设计任务书学生姓名：专业班级：计算机科学与技术指导教师：工作单位：计算机科学与技术学院题目: 进程同步模拟设计——读者和写者问题初始条件：1．预备内容：阅读操作系统的进程管理章节内容，对进程的同步和互斥，以及信号量机制度有深入的理解。

2．实践准备：掌握一种计算机高级语言的使用。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1．模拟用信号量机制实现读者和写者问题。

2．设计报告内容应说明：⑴课程设计目的与功能；⑵需求分析，数据结构或模块说明(功能与框图)；⑶源程序的主要部分；⑷测试用例，运行结果与运行情况分析；⑸自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他的其他方法（如果有，简要说明该方法）；v）对实验题的评价和改进意见，请你推荐设计题目。

目录摘要 (1)1．设计思想 (2)2．各模块的伪码算法 (3)3. 函数关系调用图 (5)4．程序测试结果 (6)设计总结 (9)参考文献 (10)致谢 (11)摘要本设计的读者写者问题，是指一些进程共享一个数据区。

数据区可以使一个文件、一块内存空间或者一组寄存器。

Reader进程只能读数据区中的数据，而writer进程必须与其他进程互斥地访问共享对象的同步问题。

读者写者问题可以这样的描述, 有一群写者和一群读者, 写者在写同一本书, 读者也在读这本书, 多个读者可以同时读这本书。

但是,只能有一个写者在写书, 并且,读者必写者优先,也就是说，读者和写者同时提出请求时,读者优先。

当读者提出请求时需要有一个互斥操作, 另外, 需要有一个信号量S来确定当前是否可操作。

本设计方案就是通过利用记录型信号量对读者写者问题的解决过程进行模拟演示，形象地阐述记录型信号量机制的工作原理。

关键词：共享对象，互斥，同步，信号量1．设计思想本设计借助C语言实现进程同步和互斥的经典问题--读者写者问题，用高级语言编写和调试一个进程同步程序，以加深对进程同步机制的理解。

通过用C 语言模拟进程同步实现，加深理解有关进程同步和互斥机制的概念及P、V操作的应用。

学生通过该题目的设计过程，掌握读者、写者问题的原理、软件开发方法并提高解决实际问题的能力。

在 Windows环境下,创建一个包含n个线程的控制台进程。

用这n个线每个线程按相应测试数据文件的要求，进行读写操作。

程来表示 n 个读者或写者。

请用信号量机制分别实现读者优先和写者优先的读者-写者问题。

将所有的读者和所有的写者分别放进两个等待队列中，当读允许时就让读者队列释放一个或多个读者,当写允许时，释放第一个写者操作。

读者-写者的读写限制(包括读者优先和写者优先)1)写-写互斥,即不能有两个写者同时进行写操作；2)读-写互斥,即不能同时有一个读者在读,同时却有一个写者在写；3)读读允许,即可以有 2 个以上的读者同时读；4)读者优先附加条件：如果一个读者申请进行读操作，同时又有一个读操作正在进行读操作，则该读者可以直接开始读操作；5)写者优先附加条件：如果一个读者申请进行读操作时已经有一个写者在等待访问共享资源，则该读者必须等到没有写者处于等待状态后才能开始读操作。

《操作系统原理》课程设计任务书题目：读者-写者问题的实现学生姓名：李志旭学号：13740113 班级：_13级软件工程_题目类型：软件工程（R）指导教师：陈文娟、马生菊一、设计目的学生通过该题目的设计过程，掌握读者、写者问题的原理、软件开发方法并提高解决实际问题的能力。

二、设计任务编写程序实现读者优先和写者优先问题:读者-写者问题的读写操作限制（包括读者优先和写者优先）写-写互斥：不能有两个写者同时进行写操作读-写互斥：不能同时有一个线程在读，而另一个线程在写。

读-读允许：可以有一个或多个读者在读。

三、设计要求1.分析设计要求，给出解决方案（要说明设计实现所用的原理、采用的数据结构）。

2.设计合适的测试用例，对得到的运行结果要有分析。

3.设计中遇到的问题，设计的心得体会。

4.文档：课程设计打印文档每个学生一份，并装在统一的资料袋中，资料袋前面要贴有学校统一的资料袋封面。

四、提交的成果1. 课程设计说明书内容包括(1) 封面（学院统一印制）；(2) 课程设计任务书；(3) 中文摘要150字；关键词3-5个；(4) 目录；(5) 正文；（设计思想；各模块的伪码算法；函数的调用关系图；测试结果等）(6) 设计总结；(7) 参考文献；(8) 致谢等。

注：每一部分是单独的一章，要另起一页写。

2. 排版要求(1) 所有一级标题为宋体三号加粗（即上面写的2～8部分，单独一行，居中）(2) 所有二级标题为宋体四号加粗（左对齐）(3) 所有三级标题为宋体小四加粗（左对齐）(4) 除标题外所有正文为宋体小四，行间距为固定值22磅，每个段落首行缩进2字符(5) 目录只显示3级标题，目录的最后一项是无序号的“参考文献资料”。

3. 其他要求（班长负责，务必按照以下方式建文件夹）(1) 以班级为单位刻录光盘一张，光盘以班级命名，例如：“10级计算机科学与技术1班”；(2) 光盘内每人一个文件夹，以学号姓名命名——如“10730101 陈映霞”，内容包括任务书、设计文档。

第二章进程管理一、选择题：1、下面过于程序的描述，正确的是（C）A. 程序执行的最终结果受到外界因素的影响，跟初始条件无关B. 程序执行的最终结果跟速度有关C. 程序是按前后次序相继地进行计算机操作序列集合，是一个静态的概念；D. 程序只能通过顺序执行2、程序的顺序执行有以下特点（B）A. 顺序性、封闭性、独立性B. 顺序性、封闭性、可再现性C. 顺序性、封闭性、随机性D. 顺序性、随机性、独立性3、现代操作系统的特点（D）A. 程序的并发执行；B. 系统所拥有的资源被共享；C. 用户随机地使用系统资源；D. 以上三者都是。

4、多道程序系统中的程序执行的特点为（A）A. 独立性、随机性、资源共享性；B. 顺序性、封闭性、可再现性；C. 顺序性、封闭性、随机性；D. 顺序性、随机性、独立性；5、PCB所包含的信息中，下列说法不正确的是（D）。

A. 描述信息B. 控制信息C. 资源信息D. CPU信息6、下面哪项不属于进程的基本状态：（C）A. 阻塞状态B. 就绪状态C. 挂起状态D. 执行状态7、在单CPU系统中，任一时刻处于执行状态的进程有几个（A）A．1 B．2 C．3 D．无法判断8、就绪状态分为内存就绪和外存就绪，这种方式的好处是（A）A. 明显提高内存的利用效率B. 降低系统开销C. 降低系统复杂性D. 降低系统参数和状态转换过程9、下面说法错误的是：（D）A．就绪状态进程得到除CPU以外其他资源，只要调度得到处理机，便可立即执行B．只有处于就绪状态的进程经调度选中之后才可以进入执行状态C．处于外存就绪状态的进程只有先成为内存就绪状态后，才可执行D．从一个状态到另一个状态的转换只要使用不同的控制过程就可以实现10、关于进程状态之间的转换原因，下列说法错误的是：（D）A．由系统唤醒，进程由阻塞态进入就绪态B．因为申请某资源忙或者I/O设备忙，进程由执行态进入阻塞态C．因时间片用完，进程由执行态进入就绪态D．进程经由一段时间的等待后，可以自动由就绪态到执行态11、（）就是系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。

1、系统产生死锁是指（5）。产生死锁的基本原因是（B）和（C），产生死锁的四 个必要条件是互斥条件、（D）、不剥夺条件和（E）。 A： （1）系统发生重大故障（2）若干进程同时处于阻塞状态（3）若干进程正
在等待永远不可能得到的资源（4）请求的资源数量大于系统提供的资源数量（5） 若干进程等待被其它进程所占用而又不可能被释放的资源
程创建的典型事件是（2）
A：（1）用户注册 （2）用户登录（3）用户记账
（4）用户通信
B：（1）作业录入（2）作业调度（3）进程调度 （4）中级调度
7、由系统专门为运行中的应用进程创建新进程的事件是（4）。在创建进程时，
（3）不是创建所必须的步骤。
C：（1）分配资源 （2）进行通信（3）共享资源
（4）提供服务
1、操作系统是一种（B）
A. 应用软件 B.系统软件
C.通用软件 D.工具软件
2、操作系统的（D）管理部分负责对进程进行调度
A. 存储器 B. 设备 C. 文件 D. 处理机
3、（A）要保证系统有较高的吞吐能力
A. 批处理系统 B. 分时系统
C. 网络操作系统 D 分布式操Байду номын сангаас系统
4、操作系统的基本类型主要有（C）
最低松弛度优先（LIF） 1、在三种基本类型的操作系统中，都设置了（3），在批处理系统中还应该设置 （2）；在分时系统中除了（3），通常还设置了（4）。
A，B，C（1）剥夺调度（2）作业调度 （3）进程调度（4）中级调度
2、下列算法中，（3）只能采用非抢占调度方式（2）只能采用抢占调度方式，而 其余的算法即可采用抢占方式，也可采用非抢占方式。 （1）高优先权优先法（2）时间片轮转法 （3）FCFS 调度算法 （4）短作业优先算法 3、若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙 述中错误的是（C） A. 在进程结束时能进行处理机调度 B. 创建新进程后能进行处理机调度 C. 在进程处于临界区时不能进行处理机调度 D. 在系统调用完成并返回用户态时能进行处理机调度 4、某系统正在执行三个进程 P1、P2 和 P3，各进程的计算（CPU）时间和 I/O 时 间比例如下表所示。

2022年巢湖学院计算机科学与技术专业《操作系统》科目期末试卷B（有答案）一、选择题1、若8个字（字长32位）组成的位示图管理内存，假定用户归还一个块号为100的内，存块，它对应位示图的位置为（）。

假定字号、位号、块号均从1开始算起，而不是从0开始。

A.字号为3，位号为5B.字号为4，位号为4C.字号为3，位号为4D.字号为4，位号为52、如果文件采用直接存取方法，且文件大小不固定，则应采用（）物理结构。

A.直接B.索引C.随机D.顺序3、为多道程序提供的共享资源不足时，可能会产生死锁。

但是，不当的（）也可能产生死锁。

A.进程调度顺序B.进程的优先级C.时间片大小D.进程推进顺序4、下列选项中，会导致进程从执行态变为就绪态的事件是（）。

A.执行P（wait）操作B.中请内存失败C.启动I/O设备D.被高优先级进程抢占5、若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（）。

I.若该文件的数据不在内存中，则该进程进入睡眠等待状态II.请求rcad系统调用会导致CPU从用户态切换到核心态III.read系统调用的参数应包含文件的名称A.仅I、IIB. 仅I、IIIC.仅II、IIID. I、II和III6、操作系统采用分页存储管理方式，要求（）。

A.每个进程拥有一张页表，且进程的页表驻留在内存中，B.每个进程拥有一张页表，但只要执行进程的页表驻留在内存中C.所有进程共享一张页表，以节约有限的内存空间，但页表必须驻留在内存中D.所有进程共享一张页表，只有页表中当前使用的页面必须驻留在内存中7、适合多道程序运行的存储管理中，存储保护是为了（）A.防止一个作业占用同个分区B.防止非法访问磁盘文件C.防止非法访问磁带文件D.防止各道作业相互干扰8、某时刻进程的资源使用情况见表。

此时的安全序列是（）A.P1、P2、P3、P4B. P1、P3、P2、P4C. P1、P4、P3、P2D.不存在9、在下列选项中，（）不属于操作系统提供给用户的可使用资源。

2)读-写互斥,即不能同时有一个读者在读,同时却有一个写者在写
3)读读允许,即可以有2个以上的读者同时读
将所有的读者与所有的写者分别放进两个等待队列中,当读允许时就让读者队列释放一个或多个读者,当写允许时,释放第一个写者操作。读者写者问题的定义如下:有一个许多进程共享的数据区,这个数据区可以就是一个文件或者主存的一块空间;有一些只读取这个数据区的进程(Reader)与一些只往数据区写数据的进程(Writer),此外还需要满足以下条件:1)任意多个读进程可以同时读这个文件;2)一次只有一个写进程可以往文件中写;3)如果一个写进程正在进行操作,禁止任何读进程度文件。我们需要分两种情况实现该问题:
一设计概述
所谓读者写者问题,就是指保证一个writer进程必须与其她进程互斥地访问共享对象的同步问题。
读者写者问题可以这样的描述,有一群写者与一群读者,写者在写同一本书,读者也在读这本书,多个读者可以同时读这本书,但就是,只能有一个写者在写书,并且,读者必写者优先,也就就是说,读者与写者同时提出请求时,读者优先。当读者提出请求时需要有一个互斥操作,另外,需要有一个信号量S来当前就是否可操作。
信号量机制就是支持多道程序的并发操作系统设计中解决资源共享时进程间的同步与互斥的重要机制,而读者写者问题则就是这一机制的一个经典范例。
与记录型信号量解决读者—写者问题不同,信号量机制它增加了一个限制,即最多允许RN个读者同时读。为此,又引入了一个信号量L,并赋予初值为RN,通过执行wait(L,1,1)操作,来控制读者的数目,每当有一个读者进入时,就要执行wait(L,1,1)操作,使L的值减1。当有RN个读者进入读后,L便减为0,第RN+1个读者要进入读时,必然会因wait(L,1,1)操作失败而堵塞。对利用信号量来解决读者—写者问题的描述如下:

中国地质大学（武汉）2017年度第学期期末考试《操作系统原理》课程试卷答案班级 _______________ 学号 _____________ 姓名 ______________一、选择题（本大题共40分，每小题2分）1、在现代操作系统中引入了（ D ），从而使并发和共享成为可能。

A.单道程序B. 磁盘C. 对象D.多道程序2、( B )操作系统允许在一台主机上同时连接多台终端，多个用户可以通过各自的终端同时交互地使用计算机。

A.网络B.分布式C.分时D.实时3、从用户的观点看，操作系统是（ A ）。

A. 用户与计算机硬件之间的接口B.控制和管理计算机资源的软件C. 合理组织计算机工作流程的软件D.计算机资源的的管理者4、当CPU处于管态时，它可以执行的指令是（A ）。

A. 计算机系统中的全部指令B. 仅限于非特权指令C. 仅限于访管指令D. 仅限于特权指令5、用户在程序中试图读取某文件的第100个逻辑块时，使用操作系统提供的（ A ）接口。

A. 系统调用B.图形用户接口C.原语D.键盘命令6、下列几种关于进程的叙述，（ A ）最不符合操作系统对进程的理解？A.进程是在多程序并行环境中的完整的程序。

B.进程可以由程序、数据和进程控制块描述。

C.线程是一种特殊的进程。

D.进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

7、当一个进程处于（ B ）状态时，称其为等待（或阻塞）状态。

A. 它正等待中央处理机B. 它正等待合作进程的一个消息C. 它正等待分给它一个时间片D. 它正等待进入内存8、一个进程释放一种资源将有可能导致一个或几个进程（ D ）。

A.由就绪变运行B.由运行变就绪C.由阻塞变运行D.由阻塞变就绪9、下面关于线程的叙述中，正确的是（ C ）。

A.不论是系统支持线程还是用户级线程，其切换都需要内核的支持。

B.线程是资源的分配单位，进程是调度和分配的单位。

“读者-写者”算法的讨论和改进作者：宋锦华李伟来源：《中小企业管理与科技·上旬刊》2011年第05期摘要：读者与写者问题是操作系统中的经典进程同步问题之一，文章利用操作系统中的信号量及信号量上的P、V操作，按照教学的方法和思路对传统的读者-写者算法进行了探讨，并将算法加以改进，实现了写者优先功能，同时保证多个并发进程在执行过程中的正确性。

关键词：读者与写者操作系统信号量1 相关概念1.1 利用信号量解决进程间的制约关系多道程序设计环境下，系统中同时执行多个作业进程，这些进程同时共享和竞争系统中的资源，因此必然存在一定的制约关系。

进程间的这些制约关系可分为互斥与同步两种。

互斥即：一个进程对系统中的共享变量或临界资源进行操作时，为了保证它和系统中其它进程的正确执行，不允许其它进程同时对这些共享变量和临界资源进行操作。

同步指：一个进程运行到了某一点时，需要等待其它进程完成某种操作或发来信息，才能继续运行。

那么，如何来控制进程间的互斥和同步，使它们正确运行呢？利用信号量以及信号量上的P、V操作能够很好的解决进程间的互斥与同步关系，从而保证进程的正确执行。

对于互斥来说，假定设置信号量为S，那么，将S的初值设为1，在临界区之前安排P(S)操作，临界区之后安排V(S)操作即可。

对于同步来说，信号量S的初值设为0，在请求同步点安排P(S)操作，在准备同步条件点安排V(S)操作即可。

本文讨论的是操作系统中很经典的进程同步问题之一——读者写者问题。

1.2 传统的读者写者问题一批数据被多个并发进程共享使用。

其中一些进程只要求读数据，因此称为“读者”，一些进程会对数据进行修改，称为“写者”。

多个读者共同工作时，访问不会有问题，但是读者和写者共同访问或者写者和写者共同修改数据时，就有可能会出错，导致错误的访问结果。

因此，关于读者和写者的读写限制，可以分为这样三条：①写-写互斥，即不能有两个写者同时对数据进行写操作。

P 、V一、生产者--消费者问题（采用信号量机制）Consumer Producer P(empty);P(mutex);//进入区 one unit --> buffer;V(mutex);V(full);//退出区P(full);P(mutex);//进入区 one unit <-- buffer;V(mutex);V(empty);//退出区full 是"满"数目,初值为0,empty 是"空"数目,初值为N 。

实际上,full + empty == N;mutex 用于访问缓冲区时的互斥,初值是1;每个进程中各个P 操作的次序是重要的：先检查资源数目,再检查是否互斥――否则可能死锁;Var mutex,empty,full:semaphore:=1,n,0; buffer:array[0,.....n-1];in,out:integer:=0,0; begin parbegin 生产者：beginrepeat生产一个产品nextp; P(empty); P(mutex);将产品输入到buffer 中buffer[in]:=nextp; in=(in+1)mod n; V(mutex); V(full); until false; end; 消费者：beginrepeat P(full); P(mutex);从buffer 中取一个产品 nextc=buffer[out]; out:=(out+1) mod n; V(mutex); V(empty); until false; end;parend; end;三、读者--写着问题（采用信号量机制） 第一类：读者优先如果读者来：1）无读者、写者,新读者可以读2）有写者等,但有其它读者正在读,则新读者也可以读3）有写者写,新读者等 如果写者来：1）无读者,新写者可以写2）有读者,新写者等待3）有其它写者,新写者等待Wmutex 表示"允许写",初值是1。

InitializeCriticalSection()
实验三 页式虚拟存储管理中地址转换和缺页中断
一、实验目的 1．深入了解页式存储管理如何实现地址转换； 2．进一步认识页式虚拟存储管理中如何处理缺页中断。 二、实验内容及要求 编写程序完成页式虚拟存储管理中地址转换过程和模拟缺页中断的处理。 实验具体包括： 首 先对给定的地址进行地址转换工作，若发生缺页则进行缺页中断处理，然后再进行地址转换；最 后编写主函数对所作工作进行测试。 假定主存 64KB，每个主存块 1024 字节，作业最大支持到 64KB，系统中每个作业分得主存块 4 块。 三、提示与讲解 页式存储管理中地址转换过程很简单，假定主存块的大小为 2n 字节，主存大小为 2m’字节， 逻辑地址 m 位，则进行地址转换时，首先从逻辑地址中的高 m-n 位中取得页号，然后根据页号查 页表，得到块号，并将块号放入物理地址的高 m’-n 位，最后从逻辑地址中取得第 n 位放入物理 地址的低 n 位就得到了物理地址。 地址转换是由硬件完成的，实验中使用软件程序模拟地址转换过程。实验中假定主存 64KB， 每个主存块 1024 字节， 即 n=10， m’=16， 物理地址中块号 6 位。 块内地址 10 位； 作业最大 64KB， 即 m=16，逻辑地址中页号 6 位，页内地址 10 位。 在页式虚拟存储管理方式中， 作业信息作为副本放在磁盘上， 作业执行时仅把作业信息的部 分页面装入主存储器，作业执行时若访问的页面在主存中，则按上述方式进行地址转换，若访问 的页面不在主存中，则产生一个缺页中断，由操作系统把当前所需的页面装入主存储器后，再次 执行时才可以按上述方法进行地址转换。 页式虚拟存储管理方式中页表除页号和该页对应的主存块号外， 至少还要包括存在标志 （该 页是否在主存），磁盘位置（该页的副本在磁盘上的位置）和修改标志（该页是否被修改过）。 在实验中页表可用数组模拟，页表数据结构的定义为： #define n 32 struct { int lnumber; int flag; int pnumber; int write; int dnumber; }page[n]; （1） //页号 //表示该页是否在主存，“1”表示在主存，“0”表示不在主存 //该页所在主存块的块号 //该页是否被修改过，“1”表示修改过，“0”表示没有修改过 //该页存放在磁盘上的位置，即磁盘块号 //页表定义 根据当前执行指令中逻辑地址的页号查页表，判断该页是否在主存中，若该页标 志为“0”，形成缺页中断。中断装置通过交换 PSW 让操作系统的中断处理程序 占用处理器； （2） 操作系统处理缺页中断的方法就是查主存分配表，找一个空闲主存块；若无空闲 块，查页表，选择一个已在主存的页面，把它暂时调出主存。若在执行过程中该 页被修改过，则需将该页信息写回磁盘，否则不必写回。 //实验中假定的页表长度

操作系统原理实验报告实验名称：操作系统姓名： XXX学号： xxxxxxxxxx班级： xxx指导老师： xxx一、实验内容在Windows2000环境下，创建一个控制台进程，此进程包含n个线程。

用这n个线程来表示n个读者或写者。

每个线程按相应测试数据文件(后面有介绍)的要求进行读写操作。

用信号量机制分别实现读者优先和写者优先的读者-写者问题。

读者-写者问题的读写操作限制(包括读者优先和写者优先):1)写-写互斥，即不能有两个写者同时进行写操作。

2)读-写互斥，即不能同时有一个线程在读，而另一个线程在写。

，3)读-读允许，即可以有一个或多个读者在读。

读者优先的附加限制:如果一个读者申请进行读操作时已有另一个读者正在进行读操作，则该读者可直接开始读操作。

写者优先的附加限制:如果一个读者申请进行读操作时已有另一写者在等待访问共享资源，则该读者必须等到没有写者处于等待状态后才能开始读操作。

运行结果显示要求:要求在每个线程创建、发出读写操作申请、开始读写操作和结束读写操作时分别显示一行提示信息，以确定所有处理都遵守相应的读写操作限制。

二、实验目的在Windows2000环境下，创建一个控制台进程，此进程包含n个线程。

用这n 个线程来表示n个读者或写者。

每个线程按相应测试数据文件(后面有介绍)的要求进行读写操作。

用信号量机制分别实现读者优先和写者优先的读者-写者问题。

三、实验原理1).读者优先读者优先指的是除非有写者在写文件，否则读者不需要等待。

所以可以用一个整型变量read_count记录当前的读者数目，用于确定是否需要释放正在等待的写者线程(当read_count=O时，表明所有的读者读完，需要释放写者等待队列中的一个写者)。

每一个读者开始读文件时，必须修改read_count变量。

因此需要一个互斥对象mutex来实现对全局变量read_count修改时的互斥。

另外，为了实现写-写互斥，需要增加一个临界区对象write。

收稿日期:2003-03-13作者简介:符广全(1966)),男,山东费县人,临沂师范学院讲师.读者-写者问题的写者优先算法符广全(临沂师范学院计算机与信息科学系,山东临沂276005)摘 要:分析了操作系统中读者-写者这个经典进程同步问题,对读者优先的算法加以改进,探讨了用信号量实现的写者优先的算法.关键词:信号量;互斥;同步;算法中图分类号:TP316 文献标识码:A 文章编号:1009-6051(2003)06-0135-02并发是现代操作系统的重要特征,进程的并发大大提高了系统效率,但也带来了不确定因素.因此,并发系统中处理好进程的互斥与同步至关重要.信号量机制是解决进程互斥与同步问题的重要工具,其应用很多而又复杂、常易出错,是操作系统原理学习中的重点与难点之一.信号量(semaphore)是荷兰计算机科学家Dijkstra 在1965年提出的一个同步机制,对信号量只能进行Wai t(S)、Signal(S)两个原语操作.信号量及Wait(S)、Si gnal(S)原语描述如下:type Semaphore=recordvalue:integer; L:pointer to PCB; end Wai t(S):S.value:=S.value-1; if S.value<0then beginInsert(C ALLER,S.L); Block(CALLER); endSignal(S):S.value:=S.value+1;if S.value<=0 then beginRemove(S.L,id); Wakeup(id); end其中Insert 、Block 、Remove 、Wakeup 均是系统提供的过程.读者-写者问题是一个用信号量实现的经典进程同步问题.在系统中,一个数据集(如文件或记录)被几个并发进程共享,其中有些进程要求读数据集,而另一些进程要求写或修改数据集.我们把只要求读的进程称为/读者0,其他进程称为/写者0,把此类问题称为/读者-写者0问题(Reader -Writers Problem).在这类问题中,我们允许多个读者同时读此数据集,但绝不允许一个写者和其他进程(读者或写者)同时访问此数据集,因为这将违反Bernstein 条件,破坏数据的完整性、正确性.解决此问题的最简单的方法是:当没有写进程正在访问共享数据集时,读进程可以进入访问,否则必须等待.操作系统的教材中一般都给出了不考虑写者优先的共享算法.在这种算法中,只要有读者不断到来,写者就要持久地等待,直到所有的读者都读完且没有新的读者到来时写者才能写数据集,是一种读者优先的算法.在此我们要对此算法改进,探讨一种实现写者优先的算法.在这个算法中,我们要实现的目标是:首先,要让读者与写者之间以及写者与写者之间要互斥地访问数据集,其次,在无写进程到来时各读者可同时访问数据集;在读者和写者都等待时访问时写者优先.我们将用两个不同的互斥信号量分别实现读者与写者间的互斥及各写者进程间的互斥:以互斥信号量Wmutex 实现各写者间的互斥,用互斥信号量Rmutex 实现各读者与写者间的互斥;设置两个整型变量Wcount 和Rcount 分别记录等待的写者数和正在读的读者数,因Wcount 、Rcount 都是共享变量,因此还要设置两个互斥信号量Mut1和Mut2以实现进程对这两个变量的互斥访问.用信号量机制实现的写者优先的算法如下:Var Mut1,Mut2,Wmu tex ,Rmutex:Semaphore;Rcount,Wcount:integer;第25卷 第6期临沂师范学院学报2003年12月Vol.25No.6Journal of Linyi Teachers .College Dec.2003Mut1:=Mut2:=Wmu tex:=Rmutex:=1; Rcount:=Wcount:=0;beginparbeginwriteri:beginWai t(Mut1);Wcount:=Wcount+1;If Wcount=1then Wait(Rmutex);Signal(Mut1);Wai t(Wmutex);写数据集;Wai t(Mut1);Wcount:=Wcount-1;If Wcount=0then Si gnal(Rmutex);Signal(Wmutex);Signal(Mut1);end Readeri:beginWait(Mu t1);Signal(Mut1);Wait(Mu t2);Rcount:=Rcount+1;If Rcount=1then Wait(Rmutex);Signal(Mut2);读数据集;Wait(Mu t2);Rcount:=Rcount-1;If Rcount=0then Signal(Rmutex);Signal(Mut2);endcoendend正访问者等待者(a)W1R1R2W2W3R3(b)R1W1R2R3W2W3图1正访问者与等待者次序算法分析:假设有诸多读者R1、R2、R3,及诸多写者W1、W2、W3,都要访问数据集,对以下几种情况下的优先、互斥情况分析如下:(1)当写者先到达进入数据集访问,其后到达的次序如图1(a)所示.因第1个写者W1访问数据集前要执行Wait(Rmutex),第1个读者R1等待在信号量Rmutex上,其他的读者等待在信号量Mut2上;第2、第3写者W2、W3等待在信号量Wmutex上,Wcount=3.W1写完后唤醒写者W2、W3,写者得以先于读者访问;最后的写者访问完成后唤醒第1个读者R1,R1唤醒R2后去访问数据集,随后R3被唤醒,R2、R3可与R1同时访问数据集.(2)当读者正访问数据集,又有诸多读者到来而无写者到来时诸读者可共同读数据集.(3)当读者正访问数据集,又有诸多读者和写者到来时(如图1(b)所示),写者能优先于诸读者访问数据集.此时,第1个写者W1等待在信号量Rmutex上,这时的第二、第三读者R2、R3不能进入临界区与R1共同访问数据集,而是等待在信号量Mut1上,第2、第3写者W2、W3也等待在信号量Mut1上;一旦R1完成后,唤醒第1个写者W1去访问数据集,W1访问数据集之前它将唤醒R2,继而R3、W2、W3会被唤醒,R2会重新被阻塞在信号量Rmutex上,R3被阻塞在信号量Mut2上,W2、W3会重新被阻塞在信号量Wmutex上;第1个写者W1访问完后,先唤醒写者W2、W3,最后一个写者完成后才唤醒读者R2、R3,因此,写者W2、W3会优先于读者R2、R3去访问数据集.需要说明的是,进程并发是系统中常见而且复杂的问题,信号量在进程的互斥、同步等方面有广泛的应用,但实现的方法也并不仅限于信号量机制.用信号量解决读者-写者问题,实现写者优先的算法不止一种,在此仅作抛砖引玉,与读者共商榷.参考文献:[1]汤子瀛,杨成忠,哲凤屏.计算机操作系统[M].西安:电子科技大学出版社,1996.[2]屠祁,屠立德.操作系统基础.北京:清华大学出版社,2000.Writer Priority Calculation of the Reader-Writer ProblemFU Guang-quan(Department of Computer and Information Science,Linyi Teachers.College,Linyi Shandong276005,China)Abstract:Not only the classic process synchronization)))Reader-Writer Problem is analyzed,but also the method to improve Reader Priority calcula tion is provided in this article.At the sa me time,the realization of Writer Priority calculation by using semaphore is also discussed.Key words:semaphore;mutual repellency;synchronization;calculation136临沂师范学院学报第25卷。

读者写者问题中写者优先算法的实现1. 简介读者写者问题是指多个线程（读者线程和写者线程）同时访问共享资源（如文件、数据库等）时可能发生的同步问题。

当多个线程同时读取共享资源时，不会产生冲突，但是当一个线程将共享资源写入时，其他线程不能读取或写入相同的资源，否则可能引发数据不一致的问题。

因此，需要一种合理的调度算法来解决读者写者问题。

其中，写者优先算法是一种常用的调度算法，它保证当有写者等待时，任何新到达的读者都必须等待。

只有当没有写者在等待时，读者才能获得对共享资源的访问权限。

本文将详细介绍写者优先算法的实现。

2. 写者优先算法实现原理写者优先算法的目标是尽快处理写者线程的请求，以保证共享资源的可用性和数据的一致性。

在写者优先算法中，当有写者线程请求访问共享资源时，读者线程需要等待，直到没有写者线程在等待为止。

这样可以保证写者线程尽快获得对资源的访问权限，以便进行写入操作。

具体实现写者优先算法的方法可以通过使用信号量和互斥锁来实现。

其中，互斥锁用于保证在任意时刻只能有一个线程访问共享资源，而信号量则用于控制写者线程和读者线程的访问权限。

3. 写者优先算法的实现步骤下面是使用写者优先算法解决读者写者问题的实现步骤：3.1 初始化信号量和互斥锁首先，需要初始化两个信号量和一个互斥锁，分别用于控制读者线程的访问权限、写者线程的访问权限和互斥访问共享资源。

这可以通过如下代码实现：mutex = Semaphore(1) # 互斥锁，用于控制对共享资源的互斥访问reader_count = Semaphore(1) # 读者数量，用于控制读者线程的访问权限writer_count = Semaphore(1) # 写者数量，用于控制写者线程的访问权限3.2 编写读者线程代码读者线程的代码如下所示：def reader():# 读者线程的入口函数while True:writer_count.acquire() # 获取写者数量的访问权限reader_count.acquire() # 获取读者数量的访问权限# 读者线程访问共享资源reader_count.release() # 释放读者数量的访问权限writer_count.release() # 释放写者数量的访问权限3.3 编写写者线程代码写者线程的代码如下所示：def writer():# 写者线程的入口函数while True:writer_count.acquire() # 获取写者数量的访问权限reader_count.acquire() # 获取读者数量的访问权限mutex.acquire() # 获取互斥访问共享资源的权限# 写者线程访问共享资源mutex.release() # 释放互斥访问共享资源的权限reader_count.release() # 释放读者数量的访问权限writer_count.release() # 释放写者数量的访问权限3.4 启动线程最后，需要创建并启动多个读者线程和写者线程，以测试写者优先算法的实现。

操作系统试题精选（2）1．填空（10分）。

①操作系统是计算机系统中的一个（），它管理和控制计算机系统中的（）。

②进程是一个程序对某个数据集的（）。

③缓冲区由（）和（）组成。

2．（10分）描述操作系统中使用公用缓冲池时的数据块插入缓冲队列的输入过程。

3．（10分）程序段main（argc，argv）{......}中包含了过程调用copy（old，new），过程copy（old，new）又进一步调用库函数write（）。

库函数write（）则调用系统调用write（）来完成相应的写操作。

画出UNIX系统中该程序执行时的用户栈和核必栈的参数变化图。

4．（10分）比较段式管理和页式管理的特点。

5．（10分）文件系统采用多重索引结构搜索文件内容。

设块长为512字节，每个块号长3字节，如果不考虑逻辑块号在物理块中所占的位置，分别求二级索引和三级索引时可寻址的文件最大长度。

6．（每小题5分，共30分）名词术语解释①进程状态②快表③目录项④系统调用⑤设备驱动程序⑥微内核7．填空（每小题1分，共10分）①如果系统中有n个进程，则在等待队列中进程的个数最多可为（）个。

②在操作系统中，不可中断执行的操作称为（）。

③如果系统中所有作业是同时到达的，则使作业平均周转时间最短的作业调度算法是（）。

④如果信号量的当前值为-4，则表示系统中在该信号量上有（）个等待进程。

⑤在有m个进程的系统中出现死锁时，死锁进程的个数k应该满足的条件是（）。

⑥不让死锁发生的策略可以分为静态和动态的两种，死锁避免属于（）。

⑦在操作系统中，一种用空间换取时间的资源转换技术是（）。

⑧为实现CPU与外部设备的并行工作，系统引入了（）硬件机制。

⑨中断优先级是由硬件规定的，若要调整中断的响应次序可通过（）。

⑩若使当前运行进程总是优先级最高的进程，应选择（）进程调度算法。

8．问答题（每小题15分，共30分）①消息缓冲通信技术是一种高级通信机制，由Hansen首先提出。

读者写者问题实验报告1.实验目的：掌握读者写者问题的基本概念和操作实现方法。

2.实验原理：（1）读者写者问题：1.读者优先：若读者进程正在读文件，写者进程需等待。

2.写者优先：若写者进程正在写文件，读者进程需等待。

3.公平竞争：读写者进程均有机会访问文件。

（2）进程同步：1.信号量：能够同步进程的执行，性能较好。

2.互斥量：能够同步进程的执行，提供了更细粒度的控制。

3.条件变量：让进程能够进行相互之间的协作。

3.实验内容：（1）依照读者写者问题的操作实现方法，采用信号量机制，编写读者进程和写者进程。

（2）测试不同读者写者优先级下程序的执行情况。

4.实验步骤：（1）设计程序架构：1.使用信号量实现读者写者访问文件的同步操作；2.设计Readers和Writers两个类分别实现读者和写者进程的操作。

（2）实现程序：1.编写读者进程，在进程对文件进行读操作之前使用信号量P操作，读取完成后使用信号量V操作；2.编写写者进程，在进程对文件进行写操作之前使用信号量P操作，写入完成后使用信号量V操作；3.设计信号量的初始值，以实现不同读者写者优先级下程序的执行情况。

（3）测试程序：在有多个读者进程和多个写者进程的情况下，测试不同读者写者优先级下程序的执行情况。

5.实验结果：（1）读者优先：读者优先的情况下，不管读者进程和写者进程的数量如何设置，读者总是有后进先出的机会访问文件。

（2）写者优先：写者优先的情况下，不管读者进程和写者进程的数量如何设置，写者总是有先进先出的机会访问文件。

（3）公平竞争：公平竞争的情况下，读者或写者进程均有机会访问文件。

6.实验结论：（1）在实现读者写者问题的过程中，需要采用进程同步技术来确保进程之间的正确协作。

（2）信号量提供了一种较为有效的进程同步机制，能够满足读者写者问题的操作需求。

（3）采用不同的优先级设置，可以使读者写者进程之间实现不同的访问策略，进而实现不同的访问效果。