操作系统 进程调度算法简析

进程调度浅析荆学士2010060020027概述：•调度算法是指：根据系统的资源分配策略所规定的资源分配算法。•调度原则：•满足用户的要求：响应时间、周转时间、截止时间；•满足系统需求：系统吞吐量，处理器利用率、各类资源的平衡使用、公平性及优先级。一、先来先来先服务（FCFS）•算法总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便一直执行下去，直到该进程完成或阻塞时，才释放处理机。•先来先服务调度算法是一种最简单的调度算法；•适合于CPU繁忙型进程，而不利于I/O繁忙型的进程（未有效利用系统资源）。•非剥夺调度方式；•FCFS对短进程不公平；•FCFS常作为一种辅助调度算法，如：系统可以按照不同的优先级维护多个就绪队列，每个队列内部按照FCFS算法进行调度；•FCFS同时适合于长程、中程、短程调度。二、短进程优先算法•通过计算判断就绪就绪进程队列中哪一个进程的预期执行时间最短，或后备作业队列中哪一个或几个作业的预期执行时间最短，然后进行调度；•非剥夺调度方式；•VSFCFS：改善了系统性能，降低进程的平均等待时间，提高了系统的吞吐量；•缺陷：执行时间不易预测；可能导致长进程饥饿，对其不公平；采用非剥夺式调度方式，未考虑进程的紧迫程度，不适合于分时系统和事务处理系统。三、时间片的轮转调度算法•每次调度，把CPU分配队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个记时器发出一个时钟中断请求，该进程被停止，并被送往就绪队列末尾；依次循环；•从终端用户来看：感觉自己独占一台主机，不受其他用户影响；•进程切换将增加系统的额外开销；•剥夺调度方式；•时间片的设置：太短，进程切换频繁，降低处理器效率；太长，无法满足交互式用户对响应时间的要求。四、基于优先级的调度算法•为每一个进程定义一个优先级，优先级越高的进程将优先获得处理器的调度；•包括静态优先级和动态优先级调度算法；•动态优先级调度算法：剩余时间最短者优先；响应比高者优先。4.1静态优先级•静态优先级设置方式：重要性（系统进程一般较高）；急迫性（前台高于后台）；为了均衡系统资源的使用（兼顾计算型与I/O型作业）；进程对资源的占有程度（如短进程优先）；4.2、剩余时间最短者优先•目的：使将要结束的进程尽早结束，释放系统资源，让其它进程尽快执行；•剥夺型；•缺点：很难准确估计进程剩余时间；对长进程不公平；•进程的平均周转时间比短进程优先算法短。4.3、响应比高者优先•响应比：w表示等待时间，s表示执行时间1swsswR1swsswR•当前进程执行完毕，或需要阻塞等待某时间而释放处理器时，调度程序选择就绪队列中的响应比最大的进程执行；•缺点：很难估算进程的预期执行时间，计算进程响应比会增加系统开销。五、反馈调度算法•思想：根据进程执行历史调整调度策略；•步骤：•设置多个就绪队列，各队列优先级不同（从上而下依次降低），每个队列设置一个时间片，•新进程放入第一队列，•按照一定的调度算法执行第一队列，•若一个时间片未完成则将其插入到下一个队列等待，•仅当第一队列为空时，调度算法才开始执行第二队列，依次类推，•如果果达到最低优先级队列，仍未完成，则按该队列的调度方法进行调度，不再降级。•新进程进入第一队列，具有最高优先级。•队列内的调度算法：•时间片的轮转调度算法，响应时间。Windows；•短进程优先算法，平均周转时间，批处理系统。六、实现（FCFS）•代码：•结果截图：七、建议•1、用一个实例来比较各个调度算法；•2、用一种语言实现一个较复杂的调度算法。THANKYOU!