读者写者问题-操作系统课程设计.doc

某某大学
课程设计报告

课程名称： 操作系统课程设计

设计题目： 读者写者问题
系 别： 计算机系
专 业： 计算机科学与技术
组 别： 第四组
学生姓名: 某某某 学 号:
起止日期:
指导教师:

14

目 录

1、需求分析 1
1.1 课程设计题目 1
1.2课程任务及要求 1
1.3课程设计思想 1
1.4软硬件运行环境及开发工具 2
2、 概要设计 2
2.1程序流程图 2
2.2所用原理 3
2.2.1 并发原理 3
2.2.2 互斥操作原理 4
2.2.3 面向对象编程编程原理 4
2.2.4 锁机制原理 5
2.2.5 线程的原理 6
2.2.6 读者写者问题的一般应用 6
3、 详细设计 6
4、 调试与操作说明 11
5、 课程设计总结与体会 12
6、 致谢 13
7、 参考文献 13

1、需求分析
1.1 课程设计题目
课程设计题目：读者写者问题
1.2课程任务及要求
编写程序实现读者写者算法（读_写互斥，读_读允许，写写互斥）
给出解决方案（包括说明设计实现的原理，采用的数据结构等）
画出程序的基本结构框图和流程图
分析说明每一部分程序的的设计思路
实现源代码
按期提交完整的程序代码和可执行程序
根据要求完成课程设计报告
总结
1.3课程设计思想
读者-写者问题是一个经典的并发程序设计问题。有两组并发进程：读者和写者，共享文件F，要求：
(1) 允许多个读者同时对文件执行读操作；
(2) 只允许一个写者对文件执行写操作；
(3) 任何写者在完成写操作之前不允许其他读者或写者工作；
(4) 写者在执行写操作前，应让已有的写者和读者全部退出。
单纯使用信号量不能解决此问题，必须引入计数器readcount对读进程记数。
为了有效的解决读者写者问题，需要引进读者-写者锁，允许多名读者同时以只读的方式存取有锁保护的对象；或一位写者以写方式存取有锁保护的对象。当一名或多名读者上锁后，此时形成读锁，写者将不能访问有锁保护的对象；当锁被请求者用于写操作时，形成写锁，其他进程的读写操作必须等待。

1.4软硬件运行环境及开发工具
本课程设计在windows操作系统下，使用java语言完成的。

2、 概要设计
2.1程序流程图
本系统主要有读者和写者两类对象，所以系统主要针对的是这两类对象的操作。

读者类对象的流程图如下：

图2.1 读者类对象

写者类对象的流程图如下：

图2.2 写者类对象

2.2所用原理
2.2.1 并发原理
进程的并发是指一组进程的执行在时间上重叠的，所谓的时间重叠是指一个进程执行第一条指令是在另一个进程执行完最后一条指令之前开始的。
并发的实质是处理器在几个进程之间的多路复用，并发是对有限物理资源强制行使多用户共享，消除计算机部件之间的互等现象，提高系统资源的利用率。
并发进程可能是无关的，也可能是交互的。进程的交互必须是有控制的，否则会出现不正确的计算结果。

2.2.2 互斥操作原理
互斥是指若干进程因互相争夺独占型资源而产生的竞争制约关系。
并发进程中与共享变量有关的程序段称为“临界区”，共享变量所代表的资源称为“临界资源”，临界区必须以一种相对于其他进程而言互相排斥的方式执行。如果能够保证一个进程在临界区执行时，不让另一个进程进入相同的临界区，即各进程对共享变量的访问是互斥的，那么，就不会引发与时间有关的错误。
而为了正确而有效地使用临界资源，共享变量的并发进程应遵守临界区调度的三个原则：
一次至多有一个进程进入临界区内执行；如果已有进程在临界区中，试图进入临界区的其他进程应等待；进入临界区内进程应在有限时间内退出，以便让等待队列中的一个进程进入。总结起来有三句话：互斥使用，有空让进；忙则等待，有限等待；择一而入，算法可行。

2.2.3 面向对象编程编程原理
面向对象是一种新兴的程序设计方法，或者说它是一种新的程序设计范型，其基本思想是使用对象，类，继承，封装，消息等基本概念来进行程序设计。
它是从现实世界中客观存在的事物（即对象）出发来构造软件系统，并在系统构造中尽可能运用人类的自然思维方式，强调直接以问题域（现实世界）中的事物为中心来思考问题，认识问题，并根据这些事物的本质特点，把他们抽象地表示为系统中的对象，作为系统的基本构成单位（而不是用一些与现实世界中的事物相关比较远，并且没有对应关系的其他概念来构造系统）。这可以使系统直接地映射问题域，保持问题域中事物及其相互关系的本来面貌。
本课程设计中涉及了两个对象，因此用面向对象的语言来编程是适合的。我们这次用到了Java语言。

2.2.4 锁机制原理
为了解决读者和写者之间的同步互斥问题，在本课程设计中要用到Java中的锁机制，这样会给编程带来很大的方便。
多线程同步的实现最终依赖锁机制。我们可以想象某一共享资源是一间屋子，每个人都是一个线程。当A希望进入房间时，他必须获得门锁，一旦A获得门锁，他进去后就立刻将门锁上，于是B,C,D...就不得不在门外等待，直到A释放锁出来后，B,C,D...中的某一人抢到了该锁（具体抢法依赖于JVM的实现，可以先到先得，也可以随机挑选），然后进屋又将门锁上。这样，任一时刻最多有一人在屋内（使用共享资源）。 Java语言规范内置了对多线程的支持。对于Java程序来说，每一个对象实例都有一把“锁”，一旦某个线程获得了该锁，别的线程如果希望获得该锁，只能等待这个线程释放锁之后。获得锁的方法只有一个，就是synchronized关键字。
1． 用锁操作原语实现互斥
为解决进程互斥进人临界区的问题，可为每类临界区设置一把锁，该锁有打开和关闭两种状态，进程执行临界区程序的操作按下列步骤进行：
①关锁。先检查锁的状态，如为关闭状态，则等待其打开；如已打开了，则将其关闭，继续执行步骤②的操作。
②执行临界区程序。
③开锁。将锁打开，退出临界区。
2．WAIT，NOTIFY，NOTIFYALL操作原语
信号量的初值可以由系统根据资源情况和使用需要来确定。在初始条件下信号量的指针项可以置为0，表示队列为空。信号量在使用过程中它的值是可变的，但只能由WAIT，SIGNAL操作来改变。设信号量为S，对S的WAIT操作记为WAIT（S），对它的SIGNAL操作记为SIGNAL（S）。
WAIT（S）：顺序执行以下两个动作：
1）信号量的值减1，即S=S－1；
2）如果S≥0，则该进程继续执行；
如果 S＜0，则把该进程的状态置为阻塞态，把相应的WAITCB连人该信号量队列的末尾，并放弃处理机，进行等待（直至其它进程在S上执行SIGNAL操作，把它释放出来为止）。
SIGNAL（S）：顺序执行以下两个动作

2.2.5 线程的原理
线程是进程中的实体，一个进程可以拥有多个线程，一个线程必须有一个父进程。线程不拥有系统资源，只有运行必须的一些数据结构；它与父进程的其它线程共享该进程所拥有的全部资源。线程可以创建和撤消线程，从而实现程序的并发执行。一般，线程具有就绪、阻塞和运行三种基本状态。

2.2.6 读者写者问题的一般应用
读者写者是典型的并发程序设计问题，它的方法可以普遍用于多线程的同步互斥问题，对于共享资源出现的问题做出了很好的解决，使得事物并发的效率更高，类似的问题还有生产者-消费者问题，理发师问题等等。

3、 详细设计

本次课程设计采用的是java语言编写，所以要用到类，包括读者类和写者类，它们都是继承的线程Thread类，在主程序中创建类对象（读者对象和写者对象），用线程来实现并发
读者类对象和写者类对象的公共属性包括：
private static final int NAP_TIME=5;
private int readerCount;
private int writerCount;
private boolean dbReading;
private boolean dbWriting;
通过NAP_TIME调整线程随机休息时间
通过readercount和writercount来记录读者和写者线程的个数
通过dbreading和dbwriting来判断读者和写者的状态，
其中读者是靠判断writercount>0来实现读写互斥的，同时允许读读同步；
而写者是靠判断dbreading=true||dbwriting=true来实现读写互斥和写写互斥的。
读写等待是随机的，运用的是math.random()函数

程序代码如下：
class Database
{/*读者写者公用的资源Database类*/
private static final int NAP_TIME=5;
private int readerCount; /*记录当前的读者个数*/
private int writerCount; /*记录当前的写者个数*/
private boolean dbReading; /*显示是否有读者在读*/
private boolean dbWriting; /*显示是否有写者在写*/
public Database() {/*构造函数*/
super();
readerCount=0;
writerCount=0;
dbReading=false;
dbWriting=false;
// TODO Auto-generated constructor stub
}

public static void napping()
{
int sleepTime=(int)(NAP_TIME * Math.random());
try{
Thread.sleep(sleepTime*1000);
}
catch(Exception e){
e.printStackTrace();
}
}
public synchronized int startRead(){
while(writerCount>0){ /*如果有写者在写，那么读者进行等待*/
try{
System.out.println("reader is waiting");
wait();
}
catch(Exception e){
System.out.println(e.toString());
e.printStackTrace();
}
}
++readerCount;
if(readerCount==1){ /*如果有读者读，则设置读状态为true*/
dbReading=true;
}
return readerCount;

}
public synchronized int endReading(){
--readerCount;
if(readerCount==0){ /*如果没有有读者读，则设置读状态为false*/
dbReading=false;
}
notifyAll(); /*释放所有等待的线程*/
System.out.println("one reader is done reading. Count="+readerCount);
return readerCount;
}

public synchronized void startWriting(){
++writerCount;
while(dbReading==true||dbWriting==true)
{/*如果有读者在读或者有写者在写，那么写者进行等待*/
try{
System.out.println("Writer is waiting");
wait();
}
catch(Exception e){
System.out.println(e.toString());
}

}
dbWriting =true; /*有写者在写，则设置写状态为true*/
}
public synchronized void endWriting(){
--writerCount;
/*由于每次只有一个写者在写，所以结束写操作后写者个数一定为0*/
dbWriting=false; /*没有写者写，则设置写状态为false*/
System.out.println("one writer is done writing. Count="+writerCount);

notifyAll(); /*释放所有等待的线程*/
}

}

class Reader extends Thread
{ /*建立读者类*/
private Database server;
private int readerNum;
public Reader(int r,Database db) {
super();
readerNum=r;
server=db;
}
public void run(){
int c;
while(true){
System.out.println("reader "+readerNum+" is sleeping");
Database.napping();
System.out.println("reader "+readerNum+" wants to read");
c=server.startRead();

System.out.println("reader "+readerNum+" is reading. Count="+c);
Database.napping();
c=server.endReading();
System.out.println("It is reader "+readerNum+" who has done reading according to count="+c);

}
}

}

class Writer extends Thread
{ /*建立写者类*/
private Database server;
private int writerNum;

public Writer(int w,Database db) {
super();
writerNum=w;
server=db;

}
public void run(){
while(true){
System.out.println("Writer "+writerNum+" is sleeping");
Database.napping();
System.out.println("Writer "+writerNum+" wants to write");
server.startWriting();

System.out.println("Writer "+writerNum+" is writing");
Database.napping();
server.endWriting();

System.out.println("It is Writer "+writerNum+" who has done writing .");

}

}
}

public class DatabaseServer {
public DatabaseServer() {
super();
}

public static void main(String[] args) {
Database db=new Database();
/*建立四个读者对象和两个写者对象*/
Reader r1=new Reader(1,db);
Reader r2=new Reader(2,db);
Reader r3=new Reader(3,db);
Reader r4=new Reader(4,db);
Writer w1=new Writer(1,db);
Writer w2=new Writer(2,db);

r1.start();
r2.start();
r3.start();
w1.start();
r4.start();
w2.start();

}
}

4、 调试与操作说明

由于读写等待是随机的所以可能出现多中情况，读写的顺序可能会不一样，以下是几种不同的运行结果：

图4.1 读者写者结果一

上图中的结果说明：按照读者1、读者2、读者3、写者1、读者4、写者2……的顺序进入，最终的执行结果按写者1、写者2、读者2、4、3、1……的顺序进行。

图4.2 读者写者结果二

上图中的结果说明：按照读者1、读者3、读者2、写者1……的顺序进入，最终的执行结果按读者3、读者1、写者2……的顺序进行。

5、 课程设计总结与体会

通过集体的努力，这次课程设计基本上可以完成功能了，读_写互斥，读_读允许，写写互斥能够实现了，但是还存在一些不足的地方，比如不能够实现读者优先或者写者优先，可能出现长时间等待的情况，在这次课程设计后，我们会继续努力将功能完善。
这次我们的收获就是懂得了使用Java这样的面向对象的语言来实现线程同步互斥问题，知道了Java中的锁机制，这对以后的编程有很大的帮助，同时也进一步加深了对操作系统这类问题的理解。

6、 致谢

感谢一学期来老师给我们的教导，让我们对操作系统有了整体的理解，这对我们以后的学习有很大的帮助，对于这次课程设计，老师也给了我们充分的支持和理解，是您对我们的指导帮助我们能够顺利的完成这次课程设计。

7、 参考文献

[1] 费翔林,骆斌. 操作系统教程(第4版)[M]. 北京: 高等教育出版社, 2009.
[2] 李尊朝,苏军.Java语言程序设计(第二版)[M].中国铁道出版社,2008.

指导教师评语：

指导教师签名： 年 月 日

成绩评定
项 目
权重
成绩
1、设计过程中出勤、学习态度等方面
0.1

2、设计技术水平
0.4

3、安全程度及可操作程度
0.2

4、设计报告书写及图纸规范程度
0.3

总 成 绩

教研室审核意见：

教研室主任签字： 年 月 日
教学院（系）审核意见：

主任签字： 年 月 日