#### 进程调度

Minix3使用的多级调度算法。具体过程是：先找到优先级最高的非空的队列，然后选择顶头的进程开始执行。`IDLE`进程在最低优先级队列里，且始终是处于就绪的状态，这就保证没有其它进程时至少还有一个进程可以跑。

初始状态下，时钟和系统任务在第1级，拥有最高的权限。设备驱动在第2级。服务进程在第3级。用户进程在更低的层级，但可以通过`nice`命令来调整。

时钟任务用于监控所有进程的时间。

任务、驱动程序和服务程序除非被阻塞，否则应该是一直运行的，它们会有大的时间片。它们如果运行的太久，也是可能被抢占的，这种机制可以防止有问题的高优先级进程锁死系统。

调度器管理着16个就绪队列。数组`rdy_head`保存了每个就绪队列的头，而数组`rdy_tail`保存了每个就绪队列的尾。

每个队列上使用的是轮转调度算法。时间片用完的进程会调度到队列的末尾，时间片没用完但被阻塞的进程再唤醒时会放在队列的顶头。

#### 驱动程序注册中断的过程

1. 一个用户态的、由中断驱动的设备驱动程序，当它需要注册一个中断处理例程时，会向系统任务发出`sys_irqctl`调用。
2. 系统任务再调用`put_irq_handler`。但是在中断例程的字段里保存的将是系统任务所在内核空间的`generic_handler`的地址，而不是驱动程序所在用户空间的中断处理例程的地址。
3. `generic_handler`用钩子结构体里的进程号字段定位此驱动程序在`priv`表里的入口，此中断在驱动程序的挂起中断位图里的对应位会置1。
4. `generic_handler`向驱动程序发一个通知。此通知被识别为来自HARDWARE，驱动程序的挂起中断位图也包含在此消息里。
5. 钩子结构体里的policy字段决定中断是立即打开还是保持关闭。如果是保持关闭，则驱动程序还需要发出一个内核调用`sys_irqenable`来开打中断。

#### 系统任务

驱动和服务程序是从内核中独立出来的若干进程，它们不能像内核函数那样自由，不能进行实际的I/O，也不能操作内核表。

那么驱动和服务程序怎么和内核交互呢？答案是内核向它们提供一组服务。这些服务对普通用户是不可见的，驱动和服务程序通过这些服务进行实际的I/O，操作内核表等。

系统任务的工作就是就是接收上层(驱动和服务程序)对内核服务的请求并执行它们。上层的进程由于在用户态，无法访问内核里的数据结构，但系统任务可以。

系统任务的主程序在做完必要的初始化后就会进入一个循环。在循环里，它获取消息，发给合适的服务例程，然后发送一个回复。主文件`system.c`里有一些的通用支持函数，但处理内核调用是在`kernel/system`目录下进行的。

#### read系统调用在整个系统里的流程

1. 用户进行`read`调用，其实就是向文件系统发了一个消息。

2. 文件系统检查缓存区看有没有它需要的块，如果没有则向磁盘驱动程序发消息来把它需要的块加载到缓存区。

   > 磁盘驱动程序的流程：
   >
   > 向系统任务发消息要求执行I/O指令。系统任务回复ACK消息。磁盘中断发生，系统任务向等待中的驱动程序报告此消息。驱动程序向系统任务发消息，要求把数据复制到文件系统的缓存区。系统任务发送回复消息。磁盘驱动程序向文件系统发消息报告数据已就绪。

3. 文件系统向系统任务发消息，告诉它把块复制给用户进程。

4. 系统任务向文件系统回复消息。文件系统向用户回复消息。

#### 时钟任务

时钟任务有点像驱动程序，也是由中断来驱动的，但它即不是块设备也不是字符设备。时钟的接口并不是`/dev`目录下的某个文件，事实上用户空间的进程是不能直接访问时钟的。用户空间的进程想要访问时钟任务只能通过系统任务才行。时钟任务进行在内核空间，可以访问内核里所有的函数和数据。

时钟驱动程序应包含的功能：

1. 维护一天中的时间。

   在每一次时钟滴嗒，只要给一个计数器执行递增操作即可。

2. 防止某些进程运行太长时间。

   当进程开始的时候，调度程序就给一个计数器初始化一个值。时钟驱动让这个计数器递减。当递减到0时，时钟驱动调用调度程序来运行其它进程。

3. 统计CPU使用率。

   最精确的方法是使用第二个计数器；一个不太精确但更简单的方法是，在进程表里记录时钟滴嗒。

4. 处理从用户进程来的`alarm`系统调用。

   进程可以要求操作系统在一段时间间隔后给它发warning。这个warning一般是信号、中断、消息等之类的东西。一个使用`alarm`的例子是，网络里的包在超时后必须重发。

   时钟驱动程序必须从一个物理时钟上模拟出多个虚拟时钟。

5. 为系统它自己的某些部分提供看门狗计时器。

   时钟驱动管理看门狗计时器的机制和管理用户信号是一样的。唯一不同的是，当计时器触发时，不是产生信号，而是执行一个由调用者提供的例程。

6. 概要分析、监控和收集统计数据。

   驱动程序检查当前时程是否在进行概要分析，若是则计算当前程序计数器的bin号(一段地址范围)，然后对该bin值加1.

#### alarm系统调用在整个系统里的流程

1. 用户进程发出alarm系统调用，请求设置一个alarm。
2. 进程管理器处理此请求。具体是设置一个计时器，并把该计时器插入到计时器列表中。
3. 当计时器列表里第一个计时器超时的时候，进程管理器要求系统任务向它发一个通知。
4. 要执行的例程在进程管理器的地址空间，在执行完后，会向用户进程发一个信号。

#### 总结

操作系统提供了顺序程序并行执行的概念模型。进程之间通过进程间通信原语进行通信，这些原语可以保证没有两个进程能在同时进到临界区。通过执行进程间通信原语还可以改变进程状态(进行态、就绪态、阻塞态)。

进程间通信原语可以用来解决生产者－消费者问题、哲学家就餐问题、读者－写者问题。即使有了这些原语，也要小心避免错误和死锁。还介绍了一些调度算法，如轮转调度、优先级调度、多级队列、策略驱动的调度等。

消息用于进程间通信，它是不缓存的，所以只有在接收者正在等待它的时候`send`才能成功。同样地，只有在消息可用的情况下`receive`才能成功。只要这两者有一个不成功，调用者都将阻塞。`notify`原语是消息的非阻塞补充。如果向没有在等待结果的接收者发`notify`，则会对一个位进行设置，在稍后完成`receive`后会触发通知。

描述了当用户进行`read`系统调用，消息流的过程。

中断可能引发进程切换。当进程被中断，会在进程表里创建一个栈，重启进程所需的信息被放到这个新栈上。要想重启这个进程，则需要把栈指针指向进程表，恢复寄存器的值，执行`iretd`指令。调度器决定栈指针指向哪个进程表。

内核执行的时候也会发生中断。如果内核执行的时候发生了异常，使用的是内核栈而不是进程表里的栈。当中断完成后，会重启一个进程。

Ｍinix3使用的多优先级队列算法。系统进程一般在最高优先级队列，用户进程在较低的优先级队列，但优先级分配的基础是process-by-process。一个陷到无尽循环里的进程优先级会降低，直到其它进程得到运行的机会才恢复其优先级。`nice`命令也可以改变进程的优先级。进程之间则是轮转运行的，当然每个进程的时间片可能是不一样的。然而，被阻塞的进程会放进队列的顶头，这是为了快速响应I/O。设备驱动和服务程序的时间片比较大，因为期望它们运行。然而，系统进程运行太久也是可以被抢占的。

内核镜像里包含了系统任务，系统任务会帮助用户空间的进程和内核通信。时钟任务也是在内核里的，它不是传统意义上的设备驱动，因为用户空间的进程不能访问时钟但可以访问设备。