实验3--读者-写者问题与进程同步

1 实验 3 读者 写者问题与进程同步 3 13 1 实验目的实验目的 理解临界区和进程互斥的概念 掌握用信号量和 PV 操作实现进程互斥的方法 3 23 2 实验要求实验要求 在 linux 环境下编写一个控制台应用程序 该程序运行时能创建 N 个线程 或者进程 其中既有读者线程又有写者线程 它们按照事先设计好的测试数据进行读写操作 请用信 号量和 PV 操作实现读者 写者问题 读者 写者问题的描述如下 有一个被许多进程共享的数据区 这个数据区可以是一个文件 或者主存的一块空间 比如一个数组或一个变量 甚至可以是一组处理器寄存器 有一些只读取这个数据区的 进程 reader 和一些只往数据区中写数据的进程 writer 以下假设共享数据区是文件 这些读者和写者对数据区的操作必须满足以下条件 读 读允许 读 写互斥 写 写互 斥 这些条件具体来说就是 1 任意多的读进程可以同时读这个文件 2 一次只允许一个写进程往文件中写 3 如果一个写进程正在往文件中写 禁止任何读进程或写进程访问文件 4 写进程执行写操作前 应让已有的写者或读者全部退出 这说明当有读者在读文 件时不允许写者写文件 对于读者 写者问题 有三种解决方法 1 读者优先 除了上述四个规则外 还增加读者优先的规定 当有读者在读文件时 对随后到达的 读者和写者 要首先满足读者 阻塞写者 这说明只要有一个读者活跃 那么随后而来的 读者都将被允许访问文件 从而导致写者长时间等待 甚至有可能出现写者被饿死的情况 2 写者优先 除了上述四个规则外 还增加写者优先的规定 即当有读者和写者同时等待时 首先 满足写者 当一个写者声明想写文件时 不允许新的读者再访问文件 3 无优先 除了上述四个规则外 不再规定读写的优先权 谁先等待谁就先使用文件 3 33 3 实验步骤 3 3 1 算法分析 1 错误的解法 有同学认为 可以将文件视为临界资源 使用临界资源的代码就构成临界区 为了对 临界区进行管理 只需设置一个互斥信号量 r w w 读或者写之前执行 P r w w 之后 执行 V r w w 即可 从而得到图 3 1 所示的 算法描述 图 3 1 错误的解法 semaphore r w w 1 reader P r w w 读文件 V r w w writer P r w w 写文件 V r w w 2 该方法虽然能满足读 写互斥和写 写互斥 但是不满足读 读允许 只要有一个读 者在读文件 其他的读者都被阻塞了 可见 单纯使用互斥信号量不能解决读者 写者问题 还需要引入计数器对读者进行记 数 2 读者优先 如何纠正上述解法中存在的错误呢 其实 对于相继到达的一批读者 并不是每个读者都需要执行 P r w w 和 V r w w 在这批读者中 只有最先到达的读者才需要执行 P r w w 与写者竞争对文件的访问权 若执行 P r w w 成功则获得了文件的访问权 其他的读者可直接访问文件 同理 只有最 后退出临界区的读者需要执行 V r w w 来归还文件访问权 为了记录正在读文件的一批读者的数量 需要设置一个整型变量 readercount 每一个 读者到达时都要将 readercount 加 1 退出时都要将 readercount 减 1 由于只要有一个读者在读文件 便不允许写者写文件 所以 仅当 readercount 0 时 即尚无读者在读文件时 读者才需要执行 P r w w 操作 若 P r w w 操作成功 读者便可 去读文件 相应地 readercount 1 同理 仅当在执行了 readercount 减 1 操作后其值为 0 时 才需要执行 V r w w 操作 以便让写者写文件 又因为 readercount 是一个可被多个 读者访问的临界资源 所以应该为它设置一个互斥信号量 readercount mutex 每个读者在 访问 readercount 之前执行 P readercount mutex 之后执行 V readercount mutex 通过上述分析得到图 3 2 所示的算法描述 其中的数字表示语句对应的行号 图 3 2 读者优先算法 01 semaphore r w w 1 02 semaphore readercount mutex 1 03 int readercount 0 04 reader 05 P readercount mutex 06 if readercount 0 P r w w 07 readercount 08 V readercount mutex 09 读文件 10 P readercount mutex 11 readercount 12 if readercount 0 V r w w 13 V readercount mutex 14 15 16 writer 17 P r w w 18 写文件 19 V r w w 20 3 写者优先 通过增加信号量并修改上述程序可以得到写者优先算法 为了实现写者优先算法 需 要将写者和读者分开排队 并且第一个读者和其它读者也要分开排队 这样就需要三个队 列 一个是写者排队的地方 另一个是第一个读者排队的地方 第三个是其它读者排队的 地方 相应地需要设置三个信号量 r w w first reader wait 和 reader wait 当一个写者 声明想写文件时 可以让新的读者中的第一个到 first reader wait 上排队等待 当有读者阻 塞在 first reader wait 上时 让其它读者阻塞在 reader wait 上 当有一个写者在写文件时 其它写者到 r w w 上排队 只要有活跃的写者或者写者队列不为空 则阻塞新到达的读者 为了记录已经发出声 明的写者数量 需要设置一个整数 writercount 以表示声明要写文件的写者数目 由于只 3 要有一个写者到达 就不允许读者去读 因此仅当 writercount 0 表示无写者声明写时 写者才需要执行 P first reader wait 操作 若操作成功 写者便可以执行 P r w w 去竞争写 文件权利 其它写者不需要再向读者声明 可以直接执行 P r w w 去竞争写文件权利 同 理仅当写者在执行 writercount 减 1 操作后其值为 0 时 才需要执行 V first reader wait 操 作 以便唤醒第一个被阻塞的读者去读文件 又因为 writercount 是一个可被多个写者访问 的临界资源 所以 应该为它设置一个互斥信号量 writer mutex 4 无优先 除了在读者优先时需要的信号量 r w w 和 readercount mutex 之外 还需要设置一个信 号量 wait 供读者和写者排队 读者和写者都排在 wait 队列上 若有读者在读文件 则第一 个写者阻塞在 r w w 上 其它的写者和读者阻塞在 wait 上 若有一个写者在写文件 则其 它写者和读者都阻塞在 wait 上 无优先的算法描述如图 3 3 所示 图 3 3 无优先算法 01 semaphore r w w 1 02 semaphore wait 1 03 semaphore readercount mutex 1 04 int readercount 0 05 reader 06 P wait 07 P readercount mutex 08 if readercount 0 P r w w 09 readercount 10 V readercount mutex 11 V wait 12 读文件 13 P readercount mutex 14 readercount 15 if readercount 0 V r w w 16 V readercount mutex 17 18 writer 19 P wait 20 P r w w 21 写文件 22 V r w w 23 V wait 24 3 3 2 程序功能及界面设计程序功能及界面设计 该程序采用简单的控制台应用程序界面 在主界面上显示程序的功能 该程序的功能 如下 1 演示读者优先算法 2 演示写者优先算法 3 演示无优先算法 4 退出 3 3 3 函数设计函数设计 实现读者 写者问题的源程序名称是 reader and writer cpp 该程序共包括 10 个函数 这些函数可以分成 4 组 各组包含的函数及其功能如图 3 4 组别包括函数函数功能 一main 显示主菜单 接收用户的选择并执行相应的功能 二 RF reader thread RF writer thread reader first 读者优先算法的读者线程函数 读者优先算法的写者线程函数 读者优先算法的初始化函数 创建 10 个线程并等待它们结束 4 三 WF reader thread WF writer thread writer first 写者优先算法的读者线程函数 写者优先算法的写者线程函数 写者优先算法的初始化函数 创建 10 个线程并等待它们结束 四 FIFO reader thread FIFO writer thread first come first serverd 无优先算法的读者线程函数 无者优先算法的写者线程函数 无者优先算法的初始化函数 创建 10 个线程并等待它们结束 图 3 4 函数功能简述 程序开始部分定义了宏 MAX THREAD 表示程序中创建的线程数 还定义了测试数 据的结构体 TEST INFO 该结构体包含三个数据项 线程名称 提出请求的时刻 操作持 续时间 接着定义了全局变量 这些全局变量的作用如下 数组 test data 保存了 10 个线程的测试数据 整数 read count 记录一段时间内同时对文件进行读操作的线程数 整数 write count 记录一段时间内提出写操作请求的线程数 该整数只在写者优先算法 中使用 CS DATA 是临界区变量 用来保护文件 实现对文件的读 写互斥和写 写互斥 相当于算法描述中的 r w w 互斥体 h mutex read count 用来保护整数 read count 以保证多个读者对 read count 的互斥访问 互斥体 h mutex write count 用来保护整数 write count 以保证多个写者对 write count 的互斥访问 该互斥体只在写者优先算法中使用 互斥体 h mutex first reader wait 和 h mutex reader wait 只在写者优先算法中使用 当 有写者在写文件时 提出读请求的第一个读者阻塞在 h mutex first reader wait 上 其余的 读者阻塞在 h mutex reader wait 上 互斥体 h mutex wait 只在无优先算法中使用 当文件被使用时 后继的读请求和写请 求依次阻塞在 h mutex wait 上 3 3 4参考源程序参考源程序 3 3 4 1 Linux 下的参考源程序 编译命令 1 gcc reader and writer cpp o reader and writer o lcurses lpthread 程序清单 2 include include include include include define MAX THREAD 10 typedef struct char thread name 3 unsigned int require moment unsigned int persist time TEST INFO TEST INFO test data MAX THREAD r1 0 15 5 r2 1 15 w1 3 3 r3 4 2 w2 5 6 w3 6 10 r4 7 8 r5 9 2 w4 10 18 w5 12 2 int read count 0 int write count 0 pthread mutex t CS DATA pthread mutex t h mutex read count pthread mutex t h mutex write count pthread mutex t h mutex reader wait pthread mutex t h mutex first reader wait pthread mutex t h mutex wait void RF reader thread void data char thread name 3 strcpy thread name TEST INFO data thread name sleep TEST INFO data require moment pthread mutex lock read count if read count 1 pthread mutex lock pthread mutex unlock printw s thread name refresh sleep TEST INFO data persist time pthread mutex lock read count if read count 0 pthread mutex unlock pthread mutex unlock return 0 void RF writer thread void data sleep TEST INFO data require moment pthread mutex lock printw s TEST INFO data thread name refresh sleep TEST INFO data persist time pthread mutex unlock return 0 void reader first 6 int i 0 pthread t h thread MAX THREAD printw reader first require sequence for i 0 i MAX THREAD i printw s test data i thread name printw n printw reader first operation sequence refresh pthread mutex init for i 0 i MAX THREAD i if test data i thread name 0 r pthread create else pthread create for i 0 ithread name sleep TEST INFO data require moment pthread mutex lock pthread mutex lock read count if read count 1 pthread mutex lock pthread mutex unlock pthread mutex unlock printw s thread name refresh sleep TEST INFO data persist time pthread mutex lock read count if read count 0 pthread mutex unlock pthread mutex unlock return 0 void FIFO writer thread void data sleep TEST INFO data require moment pthread mutex lock 7 pthread mutex lock printw s TEST INFO data thread name refresh sleep TEST INFO data persist time pthread mutex unlock pthread mutex unlock return 0 void first come first served int i 0 pthread t h thread MAX THREAD printw FCFS require sequence for i 0 i MAX THREAD i printw s test data i thread name printw n printw FCFS operation sequence refresh pthread mutex init for i 0 i MAX THREAD i if test data i thread name 0 r pthread create else pthread create for i 0 ithread name sleep TEST INFO data require moment pthread mutex lock pthread mutex lock pthread mutex lock read count if read count 1 pthread mutex lock pthread mutex unlock pthread mutex unlock pthread mutex unlock printw s thread name refresh sleep TEST INFO data persist time 8 pthread mutex lock read count if read count 0 pthread mutex unlock pthread mutex unlock return 0 void WF writer thread void data sleep TEST INFO data require moment pthread mutex lock if write count 0 pthread mutex lock write count pthread mutex unlock pthread mutex lock printw s TEST INFO data thread name refresh sleep TEST INFO data persist time pthread mutex unlock pthread mutex lock write count if write count 0 pthread mutex unlock pthread mutex unlock return 0 void writer first int i 0 pthread t h thread MAX THREAD printw writer first require sequence for i 0 i MAX THREAD i printw s test data i thread name printw n printw writer first operation sequence refresh pthread mutex init for i 0 i MAX THREAD i if test data i thread name 0 r pthread create else pthread create for i 0 i MAX THREAD i pthread join h thread i NULL printw n refresh int main int argc char argv char select 9 bool end false initscr while end clear refresh printw n printw