1.进程调度的功能
记录系统中所有进程的状态、优先数和资源的需求情况
确定调度算法。决定将CPU分配给哪个进程及多长时间
分配处理机给进程
2.进程调度方式
非抢占式 ：直到进程完成或因为某时间而不能运行时，才将CPU分配给其他进程 。通常用在批处理系统中。主要优点是简单、系统开销小
抢占式 ：当一个进程正在执行，系统可以基于某种策略剥夺CPU给其他进程。剥夺的原则有：优先权原则、短进程优先原则和时间原则。主要用于分时系统和实时系统，以便及时响应各进程请求
３．引进进程调度的时机
正在执行的进程正确完成／由于错误终止运行（陷阱和中断）
执行的进程提出I/O请求，等待其完成
分时系统中，进程时间片用完
按照优先级调度时，有更高的优先级进程变为就绪时（抢占方式）
发生阻塞（执行的进程执行了wait、阻塞原语和唤醒原语时）
４．进程调度算法的评价准则
１）面向系统的调度性能准则
吞吐量 处理及利用率 各个设备的均衡利用
２）面向用户的调度性能准则
周转时间 响应时间 截止时间 公平性 优先级
３）调度算法本身的调度性能准则
易于实现 执行开销比
多级反馈队列算法（多列轮转法）
设置多个就绪队列，分别赋予不同的优先级，队列１的优先级最高，其他逐渐降低，每队列分配不同的时间片，规定优先级越低时间片越长
（１）新进程就绪后，先投入队列１的末尾，按FCFS算法调度（先进先出调度算法，按进程进入就绪队列的先后次序，分派cpu，当前进程占用cpu，知道执行完或阻塞，才出让cpu（非抢占方式），在进程唤醒后（如i/o操作完成），并不立即恢复执行，通常等到当前进程出让cpu），（２）若一个时间片未能执行完，则降低投入到队列２的末尾，（３）以此类推，降低到最后的队列，则按时间片轮转算法（通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率。将就绪进程按FCFS原则，排成一个队列，每次调度时cpu分派给队首进程，执行一个时间片，时间片结束时，暂停当前进程的执行，将其送到队尾，并通过cpu现场切换执行当前队首进程。进程可以未使用完一个时间片，就让出cpu，比如阻塞）直到调度完成。（４）进程由于等待事件而放弃cpu后，进入等待队列，一旦等待的事件发生，回到原来的就绪队列。
仅当较高优先级的队列为空，才调度较低优先级的队列中进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，被抢先的进程被投入到原队列末尾
为适应一个进程在不同的时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级
CPU调度过程
保存现场：顺序保存，最后一步保存PSW（程序状态）
选择要运行的程序
如果没有就绪进程，系统会安排一个闲逛进程（idle），没有其他进程时，该进程一直运行，在执行过程中可接受中断
恢复现场：最后一步恢复选中进程的PSW
闲逛进程——idle进程
idle 进程，也就是0号进程，不参与schedule机制，当系统中没有任何进程可以调度（就绪队列为空），cpu会进入该进程。多cpu系统中每个cpu一个idle。
void cpu_idle (void)
{
…
while (1) {
void (*idle)(void) = pm_idle;
if (!idle)
idle = default_idle;
while (!current->need_resched)
idle();
schedule();
…
}
内核初始化后，所有core都会进入该函数。pm_idle为电源管理idle函数不讨论。
所以使用
`default_idle`。
#define safe_halt() __asm__ __volatile__("sti; hlt": : :"memory")进入default_idle后，会执行hlt, 也就是硬件停机，处于该状态时cpu不能执行任何指令，只有通过中断请求才能唤醒。
中断函数中设置need_resched就会进入schedule又开始正常进程调度。否则继续idle。
系统空闲进程，一般优先级最低，系统没事干的时候就执行它。实际上在某些系统会在idle中处理一些内存回收之类的事情。其存在的原因是为了让调度器有事情做，要不然所有的进程全挂起了调度器会很郁闷的。
产生死锁的原因：
１）竞争资源引起死锁
永久性资源：可以给多个进程多次使用（可再用资源）——剥夺兴资源（CPU，内存），非剥夺性资源（磁带机、打印机）
临时性资源：只可使用一次的资源（可消耗性资源）；如信号量，中断信号，同步信号
２）进程推进顺序不当
对资源采取“申请——分配——使用——释放”模式，由于推进不当两进程都要申请对方的资源
进程争夺资源有可能产生死锁，但不一定就会死锁，其取决于进程推进的速度和对资源的请求的顺序。死锁是一种与时间有关的错误
产生死锁的必要条件：
１）互斥条件：一个资源每次只能给一个进程使用
２）不可剥夺条件：资源申请者不能强行的从资源占有者中夺取资源，资源只能由占有者资源释放
３）请求和保持条件：在申请新的资源的同时保持对原有资源的占有
４）循环等待条件：存在一个进程—等待资源环形链
死锁的预防
预防死锁的方法是破坏死锁的四个必要条件之一
死锁的避免
允许进程动态的申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统从安全状态向不安全状态转换，便可将资源分配给进程；否则不分配资源，进程必须阻塞等待。从而避免发生死锁
避免死锁的实质是使系统不进入不安全状态