什么是"临界区算法"中的进展和有限等待？

Question

请考虑以下代码

  //proces i:                             //proces j:

  flag[i] = true;                         flag[j] = true;
  turn = j;                               turn = i;
  while(flag[j] == true && turn==j);       while(flag[i] == true && turn == i);

  <critical section>                      <critical section>

  flag[i] = false;                        flag[j] = false;

  <remainder section                      <remainder section>

我确信上面的代码将满足互斥属性,但我不确定以下内容

1. 究竟是什么progress意思？并且上述代码是否满足它,上述代码要求严格交替执行临界区.这被认为是progress？

2. 从我所看到的上面的代码不保留进程进入临界区的次数的任何信息,这是否意味着上述代码不满足bounded waiting？

Answer 1

Progress意味着该进程最终会做一些工作 - 这可能不是这种情况的一个例子是低优先级线程可能被高优先级线程抢占和回滚.一旦您的流程到达他们的关键部分,他们就不会被抢占,所以他们会取得进步.

Bounded waiting意味着该过程最终将获得对处理器的控制 - 这可能不是这种情况的一个示例是当另一个进程在关键部分中具有非终止循环而没有线程被中断的可能性时.如果关键部分终止,你的代码就会等待,而余数部分不会重新调用进程的关键部分(否则进程可能会继续运行其关键部分,而其他进程无法获得对处理器的控制).

Answer 2

1. 进程的进展意味着进程不会进入死锁状态,因此,它们的执行会独立进行!实际上,在任何时刻,只有一个进程i或进程j将执行其关键段代码,因此,将保持一致性!因此,在给定的代码中正在成功地讨论和满足这两个过程的进展.

2. 接下来,此特定代码用于仅运行一次的进程,因此,它们将不会再次到达其临界区代码.它是单个执行过程.

有界等待表示在进程请求进入其关键部分之后且在该请求被授予之前,允许其他进程进入其关键部分的次数必须存在绑定.

这段特殊的代码与有限等待无关,而且只是流程只执行一次的琐碎案例!