互斥和同步-读者/写者问题

读者/写者问题

问题定义:

存在一个多进程共享的数据区,该数据区可以是 一个文件或者一块内存或者一组寄存器, 有些进程reader只读取该数据区中的数据, 有些进程writer只往数据区写数据

  • 满足条件

    1. 任意数量的读进程可以同时读该文件
    2. 一次只有一个写进程可以写文件
    3. 若一个写进程正在写文件,则禁止任何进程读文件

  • 综上即: 读进程不需要排斥其他进程,而写进程需要排斥其他所有进程

一般互斥解决方案

  1. 因为读进程 和 写进程 都要访问 数据区,那么将 进程访问 数据区的部分声明为一个临界区，

  • 缺点:

    • 假设共享区是一个图书馆目录,普通用户访问目录查找书,管理员可以修改目录,
    1. 一般情况下,每次访问目录都相当于访问临界区，且用户每次又只能访问一个目录, 导致延迟过高,

读者优先 的解决方案

  • 思路:

  1. 信号量 wsem 用于实施互斥(writesemaphore), 当写进程正在访问共享数据区时,其他进程不能访问,

  2. 同时读进程也通过wsem实施互斥，

    • 读者优先:

      1. 没有一个读进程在执行时, 第一个试图读的读进程在wsem上等待

      2. 当已经存在至少一个读进程时, 随后的读进程无需等待,可直接进入

  3. readcount用于记录读进程的数量

  4. 信号量x用于确保readcount被正确更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*program readers and writers*/
int readcount;
semaphore x = 1,wsem = 1;
void reader() {
    while (true) {
        semWait(x); //信号量x 保证readcount 操作安全
       	readcount++;
        if (readcount == 1)
            semWait(wsem); // 第一个试图读的进程需要等待 wsem (写进程可能在执行)
        semSignal(x);   //更行x
        
        READUNIT();   //读操作
        
        semWait(x); //再次修改readcount
        readcount--;
        if (readcount == 0)
            semSignal(wsem); // 此时没有读进程了, 增加信号量wsem 
        semSignal(x);
    }
}
void writer() { //写进程互斥只由 信号量wsem决定
    while (true) {
        semWait(wsem);
        WRITEUNIT();
        semSignal(wsem);
    }
}
void main() {
    readcount = 0; //更新读进程的个数
    parbegin(reader,writer);
}

写者优先 的解决方案

  • 读者优先的问题:

    当一个读进程开始访问数据区时，只要至少有一个读进程正在读，那么为该进入的读进程 保留 数据区的控制权, 导致写进程可能处于饥饿状态

  • 目的是解决 写进程可能处于饥饿的状态

  • 思路

    • 信号量rsem: 至少有一个写进程准备访问数据区时，用于禁止所有的读进程.
      *  0 : 有写进程,即 **写进程准备访问数据区**
*  1 : 无准备访问数据区的 写进程,
    • 变量 writecount: 控制rsem的设置
    • 信号量y:类似x: 控制writecount的修改
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*program readers and writers*/
int readcount,writecount;
semaphore x=1,y=1,z=1,wsem=1,rsem=1;
void reader() {
    while(true) {
        semWait(z);
        //rsem信号决定 1. rsem=0 新的读进程不能访问数据区 2. rsem=1 读进程可以访问数据区
        semWait(rsem); //由rsem信号决定 新的读进程 能不能访问数据区
        semWait(x);

        readcount++;
        if (readcount == 1)
            semWait(wsem);

        semSignal(x);
        semSignal(rsem);
        semSignal(z);

        READUNIT();

        semWait(x);

        readcount--;
        if (readcount == 0)
            semSignal(wsem);

        semSignal(x);
    }
}
void writer() {
    while(true) {
        semWait(y);
        
        writecount++;
        if (writecount == 1)
            semWait(rsem); //检测rsem情况 告诉读进程 写进程即将访问数据区
        // rsem=0 等待读进程执行完后 写进程开始访问数据区 rsem=1 此时数据区无进程
      
        semSignal(y);
        semWait(wsem); // wsem信号量控制读/写进程间的互斥
        WRITEUNIT();
        semSignal(wsem);
        semWait(y);
        writecount--;
        if (writecount == 0)
            semSignal(rsem); //
        semSignal(y);
    }
}
void main() {
    readcount = writecount = 0;
    parbegin(reader,writer);
}
  • rsem的作用(个人理解)
    1. rsem是为写进程而定义的, 在wsem提供 读/写进程互斥的基础上 .又通过rsem信号量提供: 当一个写进程准备进入数据区时, 保证新的读进程阻塞(不能进入数据区) 且写进程 等待已有的读进程退出数据区
信号量z的作用
  • 由于可能有多个读进程都在等待rsem信号量,通过信号量z使得等待rsem信号量的队列改成在信号量z上排队，那么每次只有一个只读进程在rsem上排队

消息传递实现写进程的优先权 的解决方案

  • 流程:

    • 一个访问共享数据区的控制进程,其他访问该数据区的进程给控制进程发送消息请求,
    1. 若请求同意,会接收到控制进程发送的应答消息OK,并通过finished消息表示访问完成.
    2. 控制进程有3个信箱,接收对应的消息,finished,writerequest,readrequest
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    void reader(int i) {
    	message rmsg;
    	while (true) {
    		rmsg = i;
    		send(readrequest,rmsg); //发送地址:readrequest
    		receive(mbox[i],rmsg); //来源地址:mbox[i],
    		READUNIT();
    		rmsg = i;
    		send(finished,rmsg); //发送写完成的消息
    	}
    }
    void writer(int j) {
    	message rmsg;
    	while (true) {
    		rmsg = j;
    		send(writerequest,rmsg); // 第一次请求写的消息
    		receive(mbox[j],rmsg); //接收控制进程的同意消息
    		WRITEUNIT();
    		rmsg = j;
    		send(finished,rmsg); //发送 写操作 完成消息
    	}
    }
    void controller() {
    	while (true) {
            if (count > 0) {
                // 在处理 写 消息之前, 先处理所有的finished请求
                if (!empty(finished)) {
                   	receive();
                    count++;
                }
                else if (!empty(writerequest)) {
    				receive(writerequest,msg);
                    writer id = msg.id;
                    count  = count - 100;
                }
                else if (!empty(readrequest)) {
    				receive(readrequest,msg);
                    count--;
                    send(msg.id,"OK");
                }
            }
            if (count == 0) {
            	send(writer id,"OK");
                receive(finished,msg);
                count = 100;
        	}
        	wihle (count < 0) {
            	receive(finished,msg);
                count++;
        	} 
        }
    }

  • 流程分析

    1. count初始化为大于可能的读进程数的最大值.假设为100, 对读请求消息操作数为1,对写请求操作数为-100
    • count > 0说明没有读进程在等待,且可能有读进程发出的finished消息未处理,然后再处理写请求的消息,最后处理读请求的消息
    • count == 0，写进程发送给控制进程请求消息后收到OK，并且又发送finished给控制进程表示完成,然后控制进程恢复count = 100
    • count < 0 , 写进程发出一个请求消息,那么要消除所有读进程,提供receive(finished,msg).