读者-写者问题的写者优先算法1
需积分: 0 196 浏览量
2022-08-03
11:40:15
上传
评论
收藏 20KB PDF 举报
作者简介
：
王俊杰（
１９８７－
） ， 女， 山东潍坊人， 华中师范大学计算机科学系硕士研究生， 研究方向为软件测试、操作系统进程。
读者—写者问题的写者优先算法
王俊杰
（
华中师范大学 计算机科学系， 湖北 武汉
４３００７９）
摘 要： 分析了操作系统中读者
－
写者问题这一进程同步互斥问题， 给出了两种信号量实现的写者优先算法。
关键词： 信号量； 写者优先； 互斥； 共享资源
中图分类号
：
ＴＰ３１２
文献标识码：
Ａ
文章编号：
１６７２－ ７８００（２００８
）
０２－ ０１４２－ ０３
０
前言
在系统中， 许多进程常常需要共享资源， 而这些资源往往
要求排它性的使用
， 因此进程间需要互斥地使用这些资源。用
常规的程序来实现进程之间同步、互斥关系需要复杂的算法，
而且还会造成“忙等待”， 浪费
ＣＰＵ
资源。
为此
， 著名的荷兰计算机科学家
Ｄｉｊｋｓｔｒａ
把互斥的关键含
义抽象成信号量
（Ｓｅｍａｐｈｏｒｅ）
概念， 并引入在信号量上的
Ｐ
、
Ｖ
操
作作为同步原语。
１
读者
－
写者问题及定者优先算法
读者
－
写者问题是一个信号量实现的经典的进程同步互斥
问题。在系统中， 很多竞争的进程试图读写一个数据集中的数
据。多个进程同时读数据是可以接受的， 但是如果一个进程正
在写数据
， 而其它所有进程不能访问该数据， 那么对于写者优
先问题， 就是要求读者写者同时访问时， 写者优先。但是多数教
材给出的是类似下面的程序。
各信号量的含义如下
：
Ｗｃｏｕｎｔ
用于记录正在等待的写者的个数的整型变量， 初
值为
０
；
Ｒｃｏｕｎｔ
用于记录正在读的读者个数的整型变量， 初值为
０
；
Ｗｍｕｔｅｘ：
用于写计数的互斥信号量
，
初值为
１
；
Ｒｍｕｔｅｘ：
用于读计数的互斥信号量
，
初值为
１
；
Ｒｅａｄ：
用于写进程对读进程的互斥
，
初值为
１
；
Ｗｒｉｔｅ：
用于读进程对写进程互斥和写进程之间的互斥
，
初
值为
１
。
写者：
ｂｅｇｉｎ
ｐ（ｗｍｕｔｅｘ）；
ｗｃｏｕｎｔ ：＝ ｗｃｏｕｎｔ ＋１；
ｉｆ（ｗｃｏｕｎｔ＝＝１）
ｔｈｅｎ ｐ（ｒｅａｄ）；
ｖ（ｗｍｕｔｅｘ）；
ｐ（ｗｒｉｔｅ）；
写数据集
ｖ（ｗｒｉｔｅ）；
ｐ（ｗｍｕｔｅｘ）；
ｗｃｏｕｎｔ ：＝ ｗｃｏｕｎｔ － １ ；
ｉｆ（ｗｃｏｕｎｔ＝＝０）
ｔｈｅｎ ｖ（ｒｅａｄ）；
ｖ（ｗｍｕｔｅｘ）；
ｅｎｄ
读者：
ｂｅｇｉｎ
ｐ（ｒｅａｄ）；
ｐ（ｒｍｕｔｅｘ）；
ｒｃｏｕｎｔ ：＝ ｒｃｏｕｎｔ ＋１；
ｉｆ（ｒｃｏｕｎｔ＝＝１）
ｔｈｅｎ ｐ（ｗｒｉｔｅ）；
ｖ（ｒｍｕｔｅｘ）；
ｖ（ｒｅａｄ）；
读数据集
ｐ（ｒｍｕｔｅｘ）；
ｒｃｏｕｎｔ ：＝ ｒｃｏｕｎｔ － １；
ｉｆ（ｒｃｏｕｎｔ＝＝０）
ｔｈｅｎ ｖ（ｗｒｉｔｅ）；
ｅｎｄ
算法分析： 假设有诸多读者
Ｒ１，Ｒ２，Ｒ３
……及诸多写者
Ｗ１，
Ｗ２，Ｗ３
……都要访问数据集， 对以下几种情况的优先、互斥情
况分析如下
：
（
１
） 当写者先到达进入数据集访问， 其先到达的次序为
软 件 导 刊
Ｓｏｆｔｗａｒｅ Ｇｕｉｄｅ
第
７
卷 第
２
期
２００８
年
２
月
Ｖｏｌ．７ Ｎｏ．２
Ｆｅｂ． ２００８
评论0