0

问题来了：每个进程可能处于不同的状态，不同的事件会导致进程从一种状态转移到另一种状态；这可以使用状态图来表示。使用状态图来解释如何实现挂起队列信号量。[10 分]

我的图表是正确的，还是我误解了这个问题？ http://i.imgur.com/dC5RG6o.jpg

据我了解，挂起队列信号量维护一个阻塞进程列表，当当前进程完成其关键部分时，从中（可能随机）选择一个进程来解除阻塞。因此状态图中的等待状态。

suspend_queue_semaphore 的伪代码。

struct suspended_queue_semaphore
{
  int count;
  queueType queue;
};
void up(suspended_queue_semaphore s)
{
  if (s.count == 0)
  {
    /* place this process in s.queue /*
    /* block this process */
  }
  else
  {
    s.count = s.count - 1;
  }
}
void down(suspended_queue_semaphore s)
{
  if (s.queue is not empty)
  {
    /* remove a process from s.queue using FIFO */
    /* unblock the process */
  }
  else
  {
    s.count = s.count + 1;
  }
}
4

1 回答 1

1

是进程的状态图还是信号量，你说的是哪个信号量。在最简单的信号量中：一个二进制信号量（即只能运行一个进程），带有操作 wait() 即请求访问共享资源和 signal() 即完成访问资源。

进程的状态图除了开始和终止状态外，只有两种状态：排队 (Q) 和运行 (R)。状态图将是：

开始 = 等待。CAN_RUN
CAN_RUN = 挂起.QUEUED + 运行.RUNNING
排队=运行。运行
运行 = 信号。结束

信号量有两种状态 Empty 和 Full 信号量的状态图是：

开始 = 空
空 = 等待。RUN_PROCCESS + RUN_PROCESS
RUN_PROCESS = run.FULL
FULL = signal.EMPTY + wait.SUSPEND_PROCESS
SUSPEND_PROCESS = 挂起.FULL

编辑：修复了状态图的符号（很抱歉我的流程演算生锈了）并添加了内部流程 CAN_RUN、SUSPEND_PROCESS 和 RUN_PROCESS；内部消息运行和挂起。

说明：该进程调用“等待”方法（在您的伪代码中）并进入 CAN_RUN 状态，从那里它可以开始 RUNNING 或根据是否收到“运行”或“暂停”消息而成为排队。如果 QUEUED，它可以在收到“运行”消息时开始运行。如果 RUNNING 它在完成之前使用“信号”（在您的伪代码中）。

信号量开始 EMPTY，如果它得到一个“等待”它进入 RUN_PROCESS 发出一个“运行”消息并变为 FULL。一旦 FULL，任何进一步的“等待”都会将其发送到 SUSPEND_PROCESS 状态，在该状态下它会向进程发出“暂停”。当收到“信号”时，它会返回 EMPTY 并且它可以保留在那里或根据队列是否为空再次进入 RUN_PROCESS（我没有对这些内部状态进行建模，也没有将队列建模为系统。 )

于 2013-05-08T05:13:58.373 回答