操作系统——实现读者写者问题的相对公平

    科技2025-04-07  14

    读者—写者问题

    而这种情况往往与实际应用需求相背。请认真分析、研究读者-写者问题,给出对读者和写者都较为公平的同步解决方案。要求写出分析过程,写出使用的信号量及进程描述伪代码,并详细解释给出的解决方案。

    原代码: semaphore rw=1; //实现互斥,即写者不能与其他进程同时运行 int count=0; //读者在读的数量,使读者可以一起读 semaphore mutex=1; //使count互斥,防止死锁

    void reader(){ while(1){ p(mutex); if(count0) p(rw); count++; v(mutex); 读操作…; p(mutex); count–; if(count0); v(rw); v(mutex); } }

    void writer(){ while(1){ p(rw); 写操作…; v(rw); } }

    原代码的问题是,如果有连续的读者进程,那么写者进程就一直在p(rw)处等待,所以该算法对写者进程并不公平,我认为可以添加一条规则,使算法对读者和写者进程达到相对的公平。即先到先得,如果一个进程正在执行,那么谁最先来等待谁就可以先得到CPU。

    改进后的代码: semaphore rw=1; int count=0; semaphore mutex=1; semaphore w=1;

    void reader(){ while(1){ p(w); p(mutex); if(count0) p(rw); count++; v(mutex); v(w); 读操作…; p(mutex); count–; if(count0); v(rw); v(mutex); } }

    void writer(){ while(1){ p(w); p(rw); 写操作…; v(rw); v(w); } }

    改进之后,对写者和读者进程都是相对公平的,CPU都会分配给等待时间更长的进程。 例如,如果是 读者-写者-读者,那么在第一个读者读的过程中,写者会在p(w)处加锁,并在p(rw)处等待,所以第二个读者进程会卡在p(w)处直到写者进程结束。这样就解决了写者“饿死”的问题,实现了相对的公平。

    Processed: 0.013, SQL: 8