computer-science - 比较单处理器与多处理器的公平性

Question

保护命令循环结构

do
Condition ⇒ Command
...
Condition ⇒ Command
od

涉及非确定性选择，如文中所述。与潜在的非确定性计算相关的一个重要理论概念是公平性。如果一个循环无限重复，那么一个公平的非确定性选择最终必须选择每个保护为真的命令。例如，在循环中

do
true ⇒ x := x+1
true ⇒ x := x-1
od

这两个命令都有始终为真的守卫。x := x+1重复执行而不执行是不公平的x := x-1。
大多数语言实现旨在提供公平性，通常通过提供有界形式。例如，如果有受n保护的命令，则实现可以保证每个启用的命令将在循环中的每个2n或多次中至少执行一次。 但是，因为数字or是依赖于实现的，程序员应该只假设每个带有保护的命令最终都会被执行。3n
2n3ntrue

在单处理器语言实现还是在多处理器上更容易提供公平性？

Answer 1

Most languages have a serial model of execution, like machine code, not executing each statement in parallel with arbitrary ratios of executions. For example in C,

  for (int i=0; i<10 ; i++){
     if (true) puts("hello");
     if (true) puts("world");
  }

You'll always get output like

hello
world
hello
world

in that order.

---

Fair (or at least non-starving) thread-level parallelism is pretty easy on single or multi-core machines, with pre-emptive multi-tasking. Most languages with a thread model are designed around pre-emptive thread scheduling, where one thread running an infinite loop (even with no system calls) won't starve other threads.

多核很难实现正确的操作系统（例如，您需要锁定，而不仅仅是禁用中断），但确实允许同时运行更多线程。