1.处理机调度的基本概念：

　　在多道程序环境下，内存中存在的进程数目往往大于处理机的数目，因此，需要通过处理机的调度，动态地将 CPU 按照某种算法分配给处于就绪状态的一个进程。

　　书上 P85 页有这样的一段描述：

　　在多道程序系统中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。在多道批处理系统中，一个作业从提交到获得处理及执行，直至作业运行完毕，可能需要经历多级处理机调度。

　　一个作业从提交开始，往往要经历三级调度：高级调度、中级调度、低级调度。

　　上面依次写的调度顺序与书中写的（高级、低级、中极）稍有不符，是因为我更偏向于这样的既定顺序。中级调度实际上也可以称为交换调度，它的作用是：在内存和外存对换区之间按照给定的策略选择进程交换，也为了解决内存紧张问题，提高内存的利用率和系统吞吐量。书中的编排顺序让我觉得中级调度是后来才引入的制度，我也没有百度到，再根据下图的信息我就暂时这样认为吧。

　　以上对于调度有了简单的理解，那么引起进程调度的因素有哪些呢？

以下内容均摘自《计算机操作系统》学习指导与题解 P71 ：

1）正在执行的进程正常终止或异常终止。

2）正在执行的进程因某种原因而阻塞。具体包括：

　　●　提出 I/O 请求后被阻塞；

　　●　在调用 wait 操作时因资源不足而阻塞；

　　●　因其他原因执行 block 原语（理解为进程阻塞命令）而阻塞等。

3）在引入时间片的系统中，时间片用完。

4）在抢占调度方式中，就绪队列中某进程的优先权变得比当前正在执行的进程高，或者有优先权更高的进程进入就绪队列。

2.CPU 调度（进程调度）的直观想法：

　　调度其实可以说得很简单，就是在就绪队列中有一堆进程，我们究竟应该选择谁来执行的问题。我们可以举一些生活中一些实际需要调度的地方，比如银行中：

　　1）考虑第一种调度策略：谁先进入，就先调度谁。

　　这样做的好处是简单有效，谁排在第一个就先调度谁，很简单也很公平，但是随之而来的一个问题：如果一个只是想简单询问业务的人应该怎么办呢？这个人只是想问一个问题，让他排队或许会显得有些不公平，也有些不如意，所以基于这一点思考又有第二种策略。

　　2）任务短的可以适当优先。

　　这个策略呢就是短任务，也就是简单询问业务的人可以适当的优先，但是呢，你怎么知道这个人会询问多长的时间呢，如果这个人询问的时间越来越长怎么办？所以又要适当的降低他的优先级，伴随的另一个问题是：如果客户占用的时间长是因为银行需要用户填写一张很长的表，又该怎么办呢？因为客户是一个短任务，而且询问时间很短，但是银行又要求用户填写很长的表，那降低他的优先级又显得他很吃亏，这样也不太合适。

　　实际银行所用的调度系统呢，肯定比我这里所讨论和臆想的要复杂得多，这里只是对调度本身进行了简单的讨论，那么总结关于 CPU 调度的话题，是没有穷尽的，我们只需要关心，面对一个实际的操作系统中的各项进程，我们应该怎样调度，用怎样的算法相对合适，相对的合理。

3.如何设计调度算法：

　　上面对调度这个问题进行了简单的讨论，在这里想对算法这个问题也进行一个简单的讨论：

　　1）什么样的调度算法算是一个好的算法：

　　对比银行的调度系统，为什么说它好呢，是因为客户感到满意，那么衡量调度算法的好坏就在于是否让我们操作系统中的各项进程满意。怎样才能让进程满意呢？进程就是一段程序执行，而这段程序是由上层用户交给系统的，那么怎样让上层用户满意呢，那就是一个字：快。时间复杂度是衡量一个程序的执行一个很重要的指标，所以最核心的问题还是时间。这里所说的时间有：①周转时间：即从任务进入到任务结束所用的时间；②响应时间：从操作发生到响应，例如点击一次鼠标；③吞吐量（系统内耗时间）：完成的任务量。所以要让进程满意，就要让这些个时间变短。

　　这里只是提及一下，不做深入了解，看到一个关于系统内耗时间减小的有趣描述：比如你进了银行做了出纳，你总不能不干活一顿唠嗑，对吧。

　　2）怎样做到合理：

　　操作系统中做 CPU 调度最关键的是需要折中还有综合。

　　在操作系统中有很多各种类型的任务，它们的关注点不同，譬如前台任务和后台任务：前台任务关注响应时间，而后台任务关注周转时间。这很容易理解，我把前台任务简单的理解为正在播放的 PPT，把后台任务简单的理解为一个计算器，那么正在播放的 PPT 最重要的就是响应的速度，你不能点一下播放要等很久才切换到下一张，这样首先给用户的体验就非常差，而后台执行的计算器不用在乎这个，只关心整个程序计算的时间，即周转时间。

　　还有就是各种类型的任务的目标不同，这就会导致调度的时候可能会出现一些矛盾。

　　这些的不同就需要操作系统在调度过程中进行折中和综合，这让操作系统调度变得复杂。

4.一些调度算法的简单了解：

　　1)先来先服务算法（FCFS）：First Come First Served

选择最先进入就绪队列的进程投入执行。

　　2)短作业优先（SJF）：Shortest Job First

选择就绪队列中估计运行时间最短的进程投入执行。

　　3)优先级调度算法（PSA）：

系统根据进程的紧迫程度赋予每个进程的一个优先权，并选择就绪队列中优先权最高的进程投入执行。

一个故事：1973年关闭的 MIT 的 IBM 7094 时，发现有一个进程在 1967 年提交但一直未执行。

　　4)高响应比优先调度算法（HRRN）：

该算法实际上是一种动态优先权调度算法，它以相应比作为作业或进程的动态优先权。

相应比 = 响应时间/要求服务时间 = （等待时间 + 要求服务需时间）/ 要求服务时间

　　5)时间片轮转发（RR）：

时间片是指一个较小的时间间隔，通常为 10 ms ~ 100 ms。在简单的轮转算法中，系统将所有的就绪队列中的进程按 FIFO 规则排成一个队列，将 CPU 分配给队首进程，且规定它最多只能连续执行一个时间片，若时间片用完时进程仍未完成，也必须将其插入就绪队列末尾，并把 CPU 交给下一个进程。

　　6)多级队列调度算法：

将系统中不同类型或者性质的就绪进程固定分配到不同的就绪队列中，每个就绪队列可采用自己的调度算法；而在队列之间，通常采用固定优先权的抢占调度方式。

　　7)多级反馈队列调度算法（FB）：这里不作论述。

5.一个实际的 schedule 函数：

　　上面论述了在 CPU 调度中一个比较重要的主题就是折中和综合。这里对一个实际的调度函数 schedule 进行一个简单的研究：

 1 void Schedule(void)    //在kernel/sched.c中
 2 {
 3     while(1){
 4         c = -1;    next = 0;    i = NR_TASKS;
 5         p = &task[NR_TASKS];
 6         while(--i){ if((*p->state == TASK_RUNNING && (*p)->counter>c)
 7             c = (*p)->counter , next = i;    }
 8         if(c) break;    //找到了最大的counter
 9         for(p=&LAST_TASK;p>&FIRST_TASK;--p)
10             (*p)->counter = ((*p)->counter>>1) 
11                                         + (*p)->priority;}
12         switch_to(next);}

第4行作初始化，没什么讲的。

第5行，将 p 设置成 PCB 块的末尾。

第6行，讲 p 序列从后往前移，判断，如果进程的状态为 TASK_RUNNING 就绪状态且 p 的时间片不为0，那么就把 c 设置为当前的时间片大小，通过这样的 while 循环就找到了最大的 counter 时间片，这据说是典型的优先级算法。

第9行，for 循环遍历了所有的进程让所有进程的 counter 都变为了 counter 的初值加上它本身折半的数值，让 I/O 的优先级上来。

这里就只能简单的分析一下了，由此简单的了解就能体会到操作系统的复杂性。

6.死锁的基本概念：

　　书上 P65 有死锁的形成有详细描述：

　　如下图所示的系统，有一台打印机 R1 和一台读卡机 R2，供进程 P1 和 P2 共享。假定 P1 已占用打印机 R1，P2 已占用读卡机 R2。此时，若 P2 继续要求打印机，P1 要求读卡机，则 P1 和 P2 之间便会形成僵局，它们都在等待着对方释放出自己所需要的资源，但同时又不可能释放出自己已占用的资源，从而进入死锁状态。

　　死锁：一个进程集合中的每一个进程都在等待只能由该集合中的其他进程才能引发的事件，那么该组进程进入死锁状态（Deadlock）。

　　产生死锁的原因：

　　1）竞争资源。当系统中供多个进程共享的资源不足，而这些资源又属于不可抢占资源时，将引起进程对资源的竞争而产生死锁。

　　2）进程推进顺序非法。进程在运行过程中具有异步性特征，如果它们之间的推进顺序不当，也同样会导致进程产生死锁。

　　产生死锁的必要条件：

　　1）互斥条件。进程所竞争的资源必须被互斥使用。

　　2）请求与保持条件。当前已拥有资源的进程，仍能申请新的资源，而且，当该进程因新的资源被其他进程占用而阻塞时，它对自己已活的的资源仍保持不放。

　　3）不剥夺条件。进程已获得的资源，只能在使用完时自行释放，而不能被抢占。

　　4）环路等待条件。存在一个至少包含两个进程的循环等待链，链中的每个进程都正在等待下一个进程所占有的资源。

处理及制度与死锁的学习报告