迷你操作系统中不同信号量的就绪队列的优点和缺点

Question

在操作系统中，我们最初有一个线程就绪队列，请注意只有一个队列。为什么每个信号量有不同的队列会更好？优点和缺点可能与效率、复杂性或其他方面有关。

Answer 1

好的，要回答这个问题，请参阅我的答案 关于这里的另一个问题，关于“Linux 时分进程还是线程？”，让我们从这里使用 x86 处理器和 C 代码的假想内核的结构继续下去......我已经修改了这个结构以考虑信号量的帐户

struct regs{
  int eax, ebx, ecx, edx, es, ds, gs, fs, cs, ip, flags;
  struct tss *task_sel;
}

struct mem_loc{
   int *phys_mem_begin;
   int *phys_mem_end;
   int *semaphores;
}
struct thread{
    struct regs *regs;
    struct mem_loc *memlocTracker;
    int parent_id;
    struct thread *next;
}
struct task{
   struct regs *regs;
   struct mem_loc *task_mem;
   int *filehandles;
   int priority;
   int *num_threads;
   int quantum;
   int duration;
   int start_time, end_time;
   int parent_id;
   struct thread *task_thread;
     /* ... */
   struct task *next;
}

struct queue_ready{
   struct task *task_id;
   struct queue_ready *next;
}

在那里，我认为这看起来更好，对吧，相对于上面链接的我之前的答案，让我们看看当涉及队列时会发生什么，现在，看看这个 queue_ready 结构，现在，假设该结构中有一个由内核设置的任务，更准确地说，是一个 queue_ready 的链表，这是基于 priority 字段的code>task 结构本身，优先级为1，例如准备执行。

让我们看一个基于 C 的虚构调度器，如下所示，好吧，它可能很蹩脚并且容易受到挑剔，但先把它放在一边，集中精力讨论问题的方面......

static void scheduler(void){
 struct queue_ready *rdy_sched;

 while(1){

   for (rdy_sched = head_queue_ready; 
        rdy_sched != NULL; 
        rdy_sched = rdy_sched->next){

     if (time >= rdy_sched->task_id->start_time + rdy_sched->task_id->quantum){

        save_cpu_task_state(&task_reg->regs);

        save_mem_task_state(&rdy_sched->task_id->task_mem);

     }else{
       struct regs *task_reg = rdy_sched->task_id->regs;

       struct mem_loc *mem_task = rdy_sched->task_id->task_mem;

       load_cpu_task_state(task_reg);

       load_mem_task_state(mem_task);

       jmp_and_exec_cpu_task(task_reg->cs, task_reg->ip);

       save_cpu_task_state(&rdy_sched->task_id->regs);

       if (rdy_sched->task_id->num_threads > 0){

         struct thread *threads = rdy_sched->task_id->task_thread;

         while (threads->next != NULL){

           struct regs *thread_reg = threads->regs;

           load_cpu_thread_state(thread_reg);

           if (threads->memlocTracker->semaphores){

             /* House keeping in relation to semaphores */
             lock_memory(threads->memlocTracker);

             jmp_and_exec_cpu_thread(thread_reg->cs, thread_reg->ip);

             save_cpu_thread_state(&thread->regs);

             unlock_memory(threads->memlocTracker);

           }else{

             jmp_and_exec_cpu_thread(thread_reg->cs, thread_reg->ip);

             save_cpu_thread_state(&thread->regs);
           }
         }
       }
     }
   }
 }
}

内核的调度器看起来过于复杂，但是事实并非如此，我在代码中遗漏的唯一遗漏是优先级......现在可以在讨论OP问题时忽略它。

让我们分解一下这个调度程序函数 scheduler...但首先快速浏览一下并解释一下 scheduler 函数中使用了哪些函数：

• “load_cpu_task_state”和“load_cpu_thread_state” - this加载CPU寄存器的状态，为了简洁起见，它们分别用于任务和线程。
• 'load_mem_task_state' 和 'save_mem_task_state' - 分别加载和保存内存状态，可能从磁盘上的 phys_mem_begin 和 phys_mem_end 字段指定的页面加载和保存上述任务的 mem_loc 结构。为了简洁起见，这将加载所述任务拥有的所有内存，包括线程。
• 'jmp_and_exec_cpu_task' 和 'jmp_and_exec_cpu_task' - 这会导致内核发出魔法，跳转到所述任务的 regcs 和 ip 寄存器> 结构，对于线程来说也是相同的。
• 'save_cpu_task_state' 和 'save_cpu_thread_state' - 这会导致内核分别保存任务和线程的 CPU 寄存器的状态。
• 'lock_memory' 和 'unlock_memory' - 这是为了使用即将发挥作用的信号量锁定内存区域...

现在，调度程序将永远运行，并迭代任务的链接列表，需要检查任务是否已运行一段时间并超过量子量，例如20毫秒。然后它保存 cpu 状态和内存状态（可能保存到磁盘上的分页文件中），准备继续执行列表中的下一个任务。

如果还有剩余时间，它会加载任务的 CPU 寄存器并加载内存（可能从页面），然后跳转到最后一个指令指针和代码段所在的位置（分别为 ip 和 cs），然后任务恢复。

如果该任务有线程，它将迭代线程链表，加载CPU寄存器，并跳转到代码以恢复线程执行，然后保存CPU寄存器。

现在，事情变得有点棘手，尤其是在这个玩具操作系统中，如何管理信号量！呃呵呵，看起来操作系统开发人员的头疼得很厉害......

我想如果内存部分被锁定，信号量将是非NULL，并且会被请求信号量的用户态代码中的运行时管理器，它将锁定内存以防止线程践踏数据，并跳转到所述线程的代码中，并在该线程的持续时间完成时解锁它并保存线程的状态CPU寄存器...

结论：

这是我基于此的结论，至于支持我的事实，我无法，因为这个理论已经被详尽地讲授，检验在无数书籍的显微镜下，从美国的大学，一直到新西兰的大学，这是我的观察和理解，正如你从这段代码中看到的，复杂性和负担开发人员在编码时，不仅仅是那个，施加的约束，设计决策 - 硬件和软件。

在这种情况下管理信号量要复杂得多，要回答是否有更多可用的队列，就像我努力将其保留在一个队列queue_ready，内存使用、磁盘使用方面的成本因素最重要的是，随着内核必须跟踪那些发挥作用的缓解因素，时间使用量也会增加，另一个同样重要的因素是有多少优先级，因此在我看来，为不同的信号量准备一个就绪队列是不是一个可行的选择。

Answer 2

我假设您有一个单处理器系统（拥有多个处理器可能会影响就绪队列的数量）。

您的就绪队列中有什么？我见过的大多数就绪队列都包含所有准备运行的线程的列表。这当然与系统中的所有线程不同。如果此模型符合您的设置，我建议坚持使用单个就绪队列。当涉及到调度或选择下一个要运行的线程时，您只需检查一个队列，而不必担心该队列中的挂起任务。

每个信号量有一个挂起队列也可能是值得的。挂起队列将跟踪所有正在等待信号量的线程。由于线程正在等待，它还没有准备好，并且不在就绪队列中。

这样做有助于将处于相似状态的线程保持在一起。因此，当您必须搜索这些列表时，您可以将开销降至最低。

希望这有帮助。