高级操作系统

苗付友老师的课程资源链接

代课PPT列表（答案仅供参考）
  1. 2007.3.21: 分布式系统同步（续）
    2. 作业：3.10、3.11、3.16、3.20、3.24
    3.10 假设两个进程同时发现协调者死亡，并且它们都决定使用bully（欺负）算法进行选举。将会发生什么情况？
    答：
    1、 bully（欺负）算法是由Garcia-Molina（1982）提出的，当一个进程发现协调者不再响应请求时，它就发起选举。进程P负责选举如下：
    1. P向所有号码比它大的进程发送选举（ELECTION）消息；
    2. 若无人响应，P获胜成为协调者；
    3. 若有号码比它大的进程响应，响应者接管，P的工作完成。
    2、 不妨设系统中有8个进程（0~7）。一开始，进程7是协调者。假设在某个时刻进程7死亡，不再响应请求。进一步假设，进程4和进程5同时发现进程7死亡，并且进程4和进程5同时发起选举。那么： ......
    3.11 在图3-12中，我们有两个ELECTION（选举）消息同时循环。但对它们都没有什么不利的影响，如果消灭其中的一个会更好。设计一个算法来实现这个想法而不影响基本的选举算法的运行。
    答：
    1、 图3-12中的选举采用的是环算法。
    假设所有的进程是按物理或逻辑排序的，每个进程都知道谁是它的后继者。当任何一个进程发现协调者不再起作用时，它就发起选举。
    1. 构造一个包含它自身进程号的选举消息发送给它的后继者。如果后继者失败，消息将绕过后继者，到达后继者的后继者，或者再下一个，直到找到一个运行进程。
    2. 一旦某个后继接收到选举消息，就将自己的进程号加入到消息表中，并将消息接着往后传递。
    3. 最后，消息到达了始发者的手中，始发者接收到包括自己进程号的消息后，将消息的类型转化为协调者消息，该消息将再一次绕环运行，向所有的进程通知谁是协调者（在成员列表中进程号码最大的那个）和环成员。
    4. 当协调者消息循环一周后，再次到达始发者，始发者将该消息去掉，每个进程恢复工作。
    2、 在图3-12中，进程2和5同时发现协调者进程7失效，并且各自成立一个选举消息沿环发送，最终，两条消息都将沿环运动，进程2和进程5分别将它们转化成协调者消息，消息中有完全一样的成员，相互顺序也相同，当两条消息再环绕一周时，都被去掉，有多余的消息没有坏处，最多是浪费了一点带宽。
    3、 考虑消灭其中的一个。
    提示：原则上，可以消灭其中的任意一个。例如，可以在一个选举消息到达某个发起者时，由该发起者判断这个消息是否应该继续。要注意的是，不要让两个（或者更多）的消息都被去除。 ……
    3.16 在写前日志中，旧值和新值都被存储于日志中，只存储新值可以吗？存储旧值的好处是什么？
    答：
    1、 写前日志是一种常用的实现事务的方法，有时也称为计划列表。使用这种方法时，文件将真正修改，但是在改动任何块之前，将一条记录写入稳定存储器的写前日志中，以判断是哪一个事务在进行修改操作，哪一个文件的哪一块被改动了，旧值和新值分别是什么。只有当日志成功的写入之后才可以进行文件的修改。
    2、 我的答案。可以只存储新值。任何一个旧值都曾经作为一个新值在写前日志中出现过。可以通过往前查找写前日志，确定相对于某个新值而言的旧值。
    3、 我的答案。由于写前日志的规模可能会很庞大，在写前日志中进行搜索将会及其费时，因此保留旧值可以提高滚回和崩溃后修复的效率。
    3.20 乐观并发控制与使用时间戳，哪一个更严格呢？为什么？
    答：
    1、 乐观并发控制是一种控制并发运行的多个事务的一种方法。
    乐观并发控制的基本思想是：尽管放心去做你想做的，不用在意他人正在做什么。如果有问题出现，那么以后再考虑吧。
    乐观并发控制的算法将记录下哪些文件曾经被读写过。在某个事务提交的时候，算法将检测其他的事务以判断本事务开始后它的文件是否被其他事务修改过。如果被修改过，那么本事务将被中止。如果没有修改过，那么本事务就可以提交。
    2、 时间戳是一种完全不同于乐观并发控制的算法。
    该算法在一个事务开始做BEGIN_TRANSACTION的时候给它分配一个时间戳，通过使用Lamport的算法，我们可以确保时间戳是唯一的。系统中的每个文件都拥有一个相关的读取时间戳和写入时间戳，以判断哪个已提交的进程最近一次读取或写入过该文件。如果事务都很短小而且在时间间隔上都比较大，那么一般来说当一个文件试图访问某个文件时，该文件的读写时间戳将低于当前事务的时间戳，这种次序意味着事务正在以正确的顺序进行处理，一切正常。当次序不正确的时候，就表明一个晚于当前事务开始的事务试图插入、访问文件并提交。这种情况意味着当前事务开始得过早了，因此需要中止。
    3、 乐观并发控制与时间戳相比，两者都是乐观的。但是两者的细节完全不同。乐观并发控制算法希望并发事务不要使用同一个文件。但时间戳算法并不介意并发事务是否使用同一个文件，只要编号小的事务总是先执行就可以了。
    从这个意义上看，乐观并发控制算法中，事务提交的条件更为严格，而时间戳算法的事务提交的条件更宽松。
    3.24 一个其事务时间戳为50的进程需要一个事务时间戳为100的进程的资源。如下各情况：
    (a)Wait-die（等-死）
    (b)Wound-Wait（伤-等）会怎样呢？
    答：
    1、 等-死算法和伤-等算法都是预防死锁的方法。
    其中，等-死算法中，当较老的进程想得到一个被新进程占用的资源时，老进程将等待；而当较新的进程想得到一个被老进程占用的资源时，新进程将被中止。
    而在伤-等算法中，当较老的进程想得到一个被新进程占用的资源时，老进程将抢占新进程的资源，使得新进程受到伤害；而当较新的进程想得到一个被老进程占用的资源时，新进程将等待。
    2、 本题中的情况是，老进程（时间戳为50）想得到一个被新进程（时间戳为100）占用的资源，
    1，若采用等-死算法，则老进程将等待新进程。
    2，若采用伤-等算法，则老进程将抢占新进程的资源。
  2. 2007.4.4: 处理器分配
    3. 作业：4.12、4.16
    4.12 以处理机1为基准处理机，计算图4-13中的响应率。如何分配进程，以使平均响应率达到最小？
    答：
    1、 响应率计算公式为在一台机器上运行一个进程的时间除以这个进程在一个无负载的标准处理机上运行时应该花的时间。
    2、 提示：本题需要计算不同情况下的平均响应率，然后再进行比较。
    4.16 当某个分布式系统过载时，系统进行m个尝试，以寻找一个空闲的工作站来减轻其负载。一个工作站有k个进程的概率符合泊松分布：
    P(k)= λke-λ
    ———
    k!
    		 (λ为每个工作站的平均进程数)
    计算过载工作站在m次请求内能够找到空闲工作站的概率（即k=0）。
    计算在m=3，λ=1，2，3，4时的结果。
    答： 提示：将k=0代入公式，可以得到一次就找到空闲工作站的概率，即P(0)，（与λ相关）
    2次找到的概率为：第一次没有找到，第二次才找到，即（1-P(0))×P(0)
    ...
    本题要求m次请求内（理解为，含第m次），包含1次就找到、2次才找到、3次才找到、...、m次才找到等m种情况，因此所求概率为这m种情况的概率之和。
  3. 2007.4.18: 分布式路由算法（1）
    4. 作业：《分布式系统设计》p134第5题、第6题
    第5题 在4维立方中，设源节点为0000，组播集合是{0110，0100，1100，0010，1111}。请利用Lan的基于树的贪婪算法给出一个组播树。
    答：
    1、 Lan的基于树的贪婪算法应用于超立方时，每个节点（包括源节点）在收到包含目标节点地址列表的消息后，就会把自己的地址和目标地址相比较。如果发现匹配，消息的一个拷贝将被送往本地的处理器。如果组播集合非空，当前节点决定把目标列表中的地址转发到哪些邻居。
    维度顺序是由目标节点的相对二进制地址来决定的。在n位地址的每一位中，都有一个计数器。计数器的内容代表了相应维度的信息。具有最大计数器值得那一维将被选中。所有在这一位为1的目标将被转发到这一维上的那个邻居。在剩余的目标中，将利用下一个被选中的维度重复上述步骤。当剩余的组播集合为空时，这一过程就结束了。
    2、 考虑4维立方，设源节点为0000，组播集合是{0110，0100，1100，0010，1111}
    相对二进制地址为{0110，0100，1100，0010，1111}，由此：
    0  1  1  0
    0  1  0  0
    1  1  0  0
    0  0  1  0
    +1  1  1  1
    2  4  3  1
    计数器为{2，4，3，1}
    因此，

    1.1，0000-->0100：{0010，0000，1000，1011}计数器{2，0，2，1}
    1.2，0000-->0010：{0000}

    2.1，0100-->1100：{0000，0011}计数器{0，0，1，1}
    2.2，0100-->0110：{0000}

    3.1，1100-->1110：{0001}计数器{0，0，0，1}


    4.1，1110-->1111：{0000}
    第6题 设一个6×6的网格分成了两个子网（一个低信道子网和一个高信道子网）。请对以下组播给出它们的路由路径：
    s=（4，5）和d={（1，2），（2，4），（3，1），（5，4），（6，5）}
    s=（2，4）和d={（1，1），（2，3），（3，3），（4，4），（5，5）}
    s=（3，1）和d={（2，1），（3，1），（4，4），（5，4），（6，6）}
    答：
    1、 本题涉及到基于路径的组播。该方法的基本思路是：首先建立一个哈密尔顿回路，然后根据这个回路将组播集合转发出去。如果有一个邻居位于目标前面，但距离目标更近，那么就可以抄近路。算法如下：
    1. 在给定的网格或超立方上建立哈密尔顿回路。
    2. 将哈密尔顿回路上的节点排序。这个顺序起始于源节点，并且包含所有的目标节点。这样哈密尔顿回路就被分割成了哈密尔顿路径
    3. 对于每个中间节点，如果它是目标节点中的一个，那么它将保留消息的一个拷贝，这个目标节点的地址也将被删除。将消息和目标列表传给一个邻居。这个邻居必须在当前节点之前（按顺序），离下一个目标更近，并且仍然在这个目标之前（或者就是这个目标）。
    当使用双向链接时，只需要一个哈密尔顿路径即可（而不是哈密尔顿回路）。这个路径为系统中所有的节点定义了一个顺序。在整个顺序中，每个节点都被赋予一个值r。哈密尔顿路径的定义如下：两个节点在路径中相邻当且仅当这两个节点的r值之差的绝对值为1。
    2、 本题涉及到一个6×6的网格，为进行组播，需要建立一个哈密尔顿路径。然后根据这个哈密尔顿路径建立的节点顺序，整个网格可以分成两个子网，一个包括从低序节点到高序节点的链接（高信道网络）；另一个包含从高序节点到低序节点的链接（低信道网络）。
    在两个子网中，除了哈密尔顿路径上的链接之外，其他链接（叫做近路）也包含在其中。
    目标依据它们与源的相对位置也分两个子集。一个子集将沿着高信道网络传送，而另外一个将沿着低信道网络传送。
    为了将消息沿着最短路径传送，将采用如下的路由函数：
    假定使用高信道网络。v和d（r(v)
  4. 如果d是v的一个邻居，那么消息将直接转发到d；
  5. 否则，选择一个满足下式的v的邻居u：
    r(u)=max{r(w):r(w)<r(d)，w是v的一个邻居}
    6. 低信道网络的路由函数可以类似地定义。
    3、 在本题中，一旦建立好高、低信道网络，只需要正确定位源和目标节点的位置，然后按照上述路由函数进行路由即可。
  6. 2007.4.25: 分布式路由算法（3）
    7. 作业：《分布式系统设计》p163第2题、p164第9题、P165第14题
    第2题 给出一个有出错节点{0001，0011，1000，1010，1111}的4维立方：
    1. 确定每个节点的安全等级。
    2. 证明如果源节点是安全的，那么存在一条从源到任何一个目标的正确的哈密尔顿路径。（提示：根据源和目标之间的距离进行归纳）
    3. 说明如何使用安全等级将一个信息从节点1110路由到0000。
    答：
    1、 在n维超立方中，设S(a)=k是节点a的安全等级，则称a是k-安全的。一个失效节点是0-安全的，安全等级最低，而n-安全的节点（也叫安全节点）的安全等级最高。如果k≠n，那么一个k-安全的节点就是不安全的。
    设（S0，S1，S2，...，Sn-1），0≤Si≤n，是n维立方中节点a的邻居节点的安全等地的非递减安全状态序列，那么节点a的安全状态定义如下：
    1. 如果（S0，S1，S2，...，Sn-1）≥（0，1，2，...，n-1），那么S(a)=n;
    2. 否则，如果（S0，S1，S2，...，Sk-1）≥（0，1，2，...，k-1）∧(Sk=k-1)，那么s(a)=k。
    2、 在本题中，可以按照上述定义，在n-1轮重复后所有节点的安全等级和非递减安全状态序列都达到稳定状态，从而可以确定各个节点的安全等级。
    3、 证明。
    4、 使用安全等级进行单播路由的方法为：
    首先计算引导向量：取源和目标的异或。
    根据引导向量，在首选节点中找到安全等级最高的一个节点，将引导向量的相应维的值复位为0后，和消息一起发送到这个节点上。
    ...
    第9题 给定一个8×8网格，有8个出错节点（2，4），（2，6），（3，5），（3，3），（3，7），（4，4），（4，6），（5，5）：
    1. 根据两种安全/非安全节点的定义，找出所有的出错块。
    2. 根据活跃/非活跃节点的概念，找出覆盖所有出错节点的直角凸多边形。
    3. 找出一个覆盖所有出错节点的分离的直角凸多边形的集合。要求这些直角凸多边形的大小的总和是最小的。
    答：
    1、 基本的安全节点/非安全节点的定义如下：
    1. 所有的错误节点都是不安全的。所有的非错误节点开始时都是安全的。
    2. 如果一个非错误节点有两个或两个以上的非安全邻居，那么它的状态就变为非安全的。
    2、 扩展的安全节点/非安全节点的定义如下：
    1. 所有的错误节点都是不安全的。所有的非错误节点开始时都是安全的。
    2. 如果一个非错误节点在两个维度上都有错误的或者非安全的邻居，那么它的状态就变为非安全的。
    3. 结果同上
    3、 活跃/非活跃节点的定义如下：
    1. 所有的错误节点都是非活跃的，所有安全节点都是活跃的。
    2. 一个非安全节点开始的时候是非活跃的，但是如果它有两个或两个以上的活跃邻居，那么就可以称为是活跃的。
    第14题 考虑一个4维立方中的组播，s=1001，d={1110，0100，1101}，和一个出错节点集合{0000，0101，0111}。
    1. 根据SLBM建立一个组播树。
    2. 根据MSLBM建立一个组播树。
    3. 按照所用的流量步数对上述两个组播树进行比较。
    答：
    1、 本题涉及到超立方中的容错组播问题。
    可以使用安全等级在超立方中进行组播。
    在本题中，首先根据出错信息为4维立方中的节点确定安全等级。
    2、 SLBM中，维度优先级由邻居的安全等级确定，安全等级越高，优先级越高。当优先级相同时，在SLBM中，随机确定优先顺序；而在MSLBM中，根据地址总和的值决定，当还冲突时，才随机。
    3、 根据上述说明，分别建立SLBM和MSLBM的组播树，并比较。
Edited by xlanchen@ustc.edu.cn
Advanced Operating System, Spring 2007