20201318李兴昕第十二章学习笔记

标签：李兴昕第十二章进程算法 20201318 bp 缓冲区 Unix 空闲

第十二章：块设备I/O和缓冲区管理

知识点归纳总结：

本章讨论了块设备I/O和缓冲区管理；解释了块设备I/O的原理和I/O缓冲的优点；

论述了 Unix的缓冲区管理算法，并指出了其不足之处；还利用信号量设计了新的缓冲区管理算法，以提高I/O缓冲区的缓存效率和性能；

表明了简单的PV算法易于实现，缓存效果好，不存在死锁和饥饿问题；

提出了一个比较Unix缓冲区管理算法和PV算法性能的编程方案。编程项目还可以帮助读者更好地理解文件系统中的I/O操作。

其中让我最有收获的几个部分如下：

块设备I/O缓冲区
Unix I/0缓冲区管理算法
新的I/O缓冲区管理算法
编程项目：缓冲区管理算法比较

Unix算法的缺点：

虽然Unix算法非常简单和简洁.但它也有以下缺点。

效率低下：该算法依赖于重试循环，例如，释放缓冲区可能会唤醒两组进程：需要释放的缓冲区的进程，以及只需要空闲缓冲区的进程。由于只有一个进程可以获取释放的缓冲区，所以，其他所有被唤醒的进程必须重新进入休眠状态。从休眠状态唤醒后，每个被唤醒的进程必须从头开始重新执行算法，因为所需的缓冲区可能已经存在。这会导致过多的进程切换。
缓存效果不可预知：在Unix算法中，每个释放的缓冲区都可被获取'如果缓冲区由需要空闲缓冲区的进程获取，那么将会重新分配缓冲区，即使有些进程仍然需要当前的缓冲区。
可能会出现饥饿：Unix算法基于“自由经济”原则，即每个进程都有尝试的机会，但不能保证成功，因此，可能会出现进程饥饿
该算法使用只适用于单处理器系统的休眠/唤醒操作

信号量的优点：

(1)计数信号量可用来表示可用资源的数量，例如：空闲缓冲区的数量。
(2)当多个进程等待一个资源时，信号量上的V操作只会释放一个等待进程，该进程不必重试，因为它保证拥有资源。

模拟系统的组织结构：

PV算法：

BUFFER *getblk(dev, blk)
{
    while(1)
    {
        P(free);
        if (bp in dev_list)
        {
            if (bp not BUSY)
            {
                remove bp from freelist;
                p(bp)
                return bp;
            }
            V(free);
            P(bp);
            return bp;
        }
        bp = frist buffer taken out of freelist;
        P(bp);
        if (bp dirty)
        {
            awrite(bp);
            continue;
        }
        reassign bp to (dev,blk);
        return bp;    
    } 
}

brelse(BUFFER *bp)
{
    if(bp queue has waiter){V(bp);return;}
    if(bp dirty && free queue has waiter){awrite(bp);return;}
    enter bp into (tail of) freelist; V(bp);V(free);
}

(1)缓冲区唯一性：在getblk()中，如果有空闲缓冲区，则进程不会在(1)处等待，而是会搜索dev_listc如果所需的缓冲区已经存在，则进程不会重新创建同一个缓冲区。如果所需的缓冲区不存在，则进程会使用一个空闲缓冲区来创建所需的缓冲区。而这个空闲缓冲区保证是存在的，如果没有空闲缓冲区，则需要同一个缓冲区的几个进程可能在(1)处阻塞。当在(10)处释放出一个空闲缓冲区时，它仅释放一个进程来创建所需的缓冲区。旦创建了缓冲区，它就会存在于dev_list中，这将防止其他进程再次创建同一个缓冲区。因此，分配的每个缓冲区都是唯一的。

(2)无重试循环：进程重新执行while(l)循环的唯一位置是在(6)处，但这不是重试，因为进程正在不断地执行。

(3)无不必要唤醒：在getblk()中，进程可以在(1)处等待空闲缓冲区，也可以在(4)处等待所需的缓冲区，在任意一种情况下，在有缓冲区之前，都不会唤醒进程重新运行。此外，当在(9)处有一个脏缓冲区即将被释放并且在(1)处有多个进程等待空闲缓冲区时，该缓冲区不会被释放而是直接被写入。这样可以避免不必要的进程唤醒。

(4)缓存效果：在Unix算法中，每个释放的缓冲区都可被获取。而在新的算法中，始终保留含等待程序的缓冲区以供重用一只有缓冲区不含等待程序时，才会被释放为空闲。这样可以提高缓冲区的缓存效果，

(5)无死锁和饥饿：在getblk()中、信号量锁定顺序始终是单向的，即P(free),然后是P(bp),但决不会反过来，因此不会发生死锁：如果没有空闲缓冲区，所有清求进程都将在(1)处阻塞，这意味着，虽然有进程在等待空闲缓冲区，但所有正在使用的缓冲区都不能接纳任何新用户。这保证了繁忙缓冲区最终将被释放为空闲缓冲区。因此，不会发生空闲缓冲区饥饿的情况。

PV算法的改进：

PV算法非常简单，易于实现，但是它有以下两个缺点。首先，它的缓存效果可能并非最佳。这是因为一旦没有空闲缓冲区，所有请求进程都将被阻塞在getblk()中的(1)处，即使它们所需的缓冲区可能已经存在于缓冲区缓存中了。其次，当进程从空闲列表信号量队列中唤醒时，它可能会发现所需的缓冲区已经存在，但处于繁忙状态，在这种情况下，它将在(4)处再次被阻塞。严格地说，进程被不必要地唤醒了，因为它被阻塞了两次。

标签：李兴昕,第十二章,进程,算法,20201318,bp,缓冲区,Unix,空闲
From： https://www.cnblogs.com/shady545/p/16856030.html