进程调度算法与task_struct结构体

进程是实现多个程序并发执行，以提高资源利用率和系统吞吐量。

进程两个基本属性：1.进程是一个可拥有资源的独立单元。2.进程是一个课独立调度和分派的基本单元。

进程调度是操作系统中必不可少的一种调度。

一.进程调度的任务

（1）保存处理机的现场信息。如程序技术器、多个通用寄存器中的内容等。

（2）按算法选择进程

 (3)把处理器分配给进程

二.进程调度机制

（1）排队器。将系统中的所有就绪进程按照一定的策略排成一个或多个队列。

（2）分派器。负责将选定的进程从就绪队列中取出。

（3）上下文切换器。进程切换的过程中会进行上下文的切换。

三.进程调度算法

1.轮转调度算法

是一种基于时间片的轮转调度算法。

（1）基本原理：将所有的就绪进程按先来先服务策略排成一个就绪队列，系统设置每隔一定时间产生一次中断，把CPU分配给队首进程，并执行一个时间片。

（2）进程切换时机：1.如果一个时间片没有完成，程序就已经完成，应立即将它从就绪队列删除，再执行队首程序。2.如果一个时间片已经完成而程序还没有完成，将该程序放在就绪队列的末尾。

（3）时间片的确定：略大于一次交互所需要的时间

2.优先级调度算法

把处理机分配给就绪数列中优先级最高的进程。这种算法也可以分为两种：

（1）非抢占式优先级调度算法：该算法规定，一旦把处理机分配给就绪数列中优先级最高的进程后，该进程便一直执行下去。

 (2)抢占式优先级调度算法：把处理机分配给就绪数列中优先级最高的进程后，若中间出现了更高优先级的进程，处理机就会去处理优先级更好的进程。

3.多队列调度算法

该算法将系统中的进程就绪队列从一个拆分到若干个，将不同类型的进程固定分配在不同的就绪队列，不同的就绪队列实施不同的调度算法。

4.多队列反馈队列调度算法

原理:首先设置多个就绪队列，每个队列的优先级不同，第一个队列的优先级最高，以此类推；然后，使每个队列采用先来先服务调度算法，每个进程运行一个时间片，如果在一个时间片中进程未完成，就将该进程放在下一个队列的尾部等待；进程的调度是按队列优先级调度的，

5.基于公平原则的调度算法

（1）保证调度算法

它向用户的保证不是优先级的保证，而是性能的保证，一种是处理机分配的公平性，有n个相同类型的进程同时进行，保证每个进程都获得相同处理机时间的1/n。

（2）公平分享调度算法

这种算法是为每个用户的分配的处理机时间相同或时间比例相同，每个用户又按其的进程为单位。

四.实时系统的调度算法

1.实现实时调度的基本条件

（1）就绪时间

（2）开始截止时间和完成截止时间

（3）处理时间

（4)资源要求

（5）优先级

2.非抢占式调度算法

（1）非抢占式轮转调度算法

该算法规定，一旦把处理机分配给就绪数列中优先级最高的进程后，该进程便一直执行下去。直到进程完成，再调度下一个进程。

（2）非抢占式优先调度算法

该算法根据优先级排成一个队列。

3.抢占式调度算法

（1）基于时钟中断的抢占式轮转调度算法

在实时任务到达后，如果它的优先级高于当前任务的优先级，这时并不立即抢占处理机，而是等到时钟中断发生后，才将处理机分给新的进程。

（2）立即抢占的优先级调度算法

在实时任务到达后，如果它的优先级高于当前任务的优先级，这时立即抢占处理机。

4.最早截止时间优先算法

该算法根据任务的截止时间确定任务的优先级，任务的截止时间越早，优先级越高。

5.最低松弛度优先算法

该算法在确定任务的优先级时，根据的是任务的紧急程度，最低松弛度是根据进程必须完成时间与其本身的运行时间和当前时间之差所确定的。松弛度越低，优先级越高。

task_struct结构体的介绍参考下面网站：

http://blog.sina.com.cn/s/blog_65403f9b0100gs3a.html

进程调度算法与task_struct结构体