cfs调度算法原理(一)

实验一 模拟实现进程调度算法(4学时)

①、实验目的

a、进程调度是处理机管理的核心内容。观察、体会操作系统的进程调度方法，并通过一个简单的进程调度模拟程序的实现，加深对进程控制块、进程队列、进程调度算法，进程切换的理解，并体会和了解各种调度算法的具体实施办法。

b、提高实际动手编程能力，为日后从事软件开发工作打下坚实基础。

②、实验内容

a、设计进程控制块PCB表结构，模拟实现进程调度算法：FIFO，静态优先级调度，时间片轮转调度，短进程优先调度算法，多级反馈队列调度。（实现静态优先级调度算法、短进程优先调度算法）。

b、编写一个进程调度程序模拟程序。模拟程序只对PCB进行相应的调度模拟操作，不需要实际程序。

c、由用户输入（可通过文件输入）进程名、进程状态、进程运行时间和进程优先级等数据。

③、实验要求

a、使用模块化设计思想来设计。

b、给出主函数和各个算法函数的流程图。

c、学生可按照自身条件，随意选择采用的算法，（例如：采用冒泡法编写程序，实现短进程优先调度的算法）。

d、进程调度程序模拟程序只对PCB进行相应的调度模拟操作，不需要实际程序。

④、运行结果

a、给出进程的调度模拟操作排序结果。

⑤、提示

a、每个进程可有三个状态，并假设初始状态为就绪状态。

b、为了便于处理，程序中的进程运行时间以纳秒为单位计算。

C、各进程的优先级或轮转时间数以及进程需运行的纳秒数的初始值均由用户给定。

d、在优先级算法中，采用静态优先级。在时间片轮转算法中，采用可变时间片，由用户给定。

e、对于遇到优先级一致的情况，采用FIFO策略解决。

f、输入：进程流文件（文本文件），其中存储的是一系列要执行的进程，每个进程包括四个数据项：进程名 进程状态(1就绪 2等待 3运行) 所需时间 优先级(0级最高)。

g、输出：进程执行流 等待时间 平均等待时间。

⑥、分析与讨论

a、各种进程调度算法的异同？

实验五 进程调度（1）优先数调度算法

实验目的

进程调度是处理器管理的核心内容。本实验要求用高级语言编写和调试一个简单的进程调度程序，通过本实验加深对进程控制块、进程队列等概念的了解，掌握优先数调度算法和时间片调度算法的具体实施方法。

实验类型

综合性实验

预习要求

已完成进程管理理论课程的学习，了解进程、进程调度的基本概念以及典型进程调度算法的基本思想。

实验设备与环境

PII以上电脑一台，已经安装VC++、GCC或其他C语言编译环境

实验原理

操作系统是计算机系统中必不可少的系统软件。它是计算机系统中各种资源的管理者和各种活动的组织者、指挥者。进程调度解决了竞争处理器的问题。进程调度程序按照某种调度算法从就绪队列中选择一个进程，让它占用处理器。或者说，进程调度程序把处理器分配给了一个被选中的进程。所以，有时也把进程调度程序称为“处理器调度”程序。

在优先数调度算法方面：不同的系统确定优先数的方法可以不同，但一般都从任务的紧迫性和系统效率等方面考虑。例如，让系统进程的优先数大于用户进程的优先数，重要计算问题的进程优先数大于一般计算问题的进程优先数，交互式作业进程的优先数大于批处理作业进程的优先数等。

实验任务

设计一个程序,根据不同的调度算法模拟操作系统对进程的调度。

动态优先级法

1、 设计进程控制块PBC表结构，分别适用优先数调度算法 2、 PBC结构通常包括以下信息：进程名、进程优先数、轮转时间片、进程的CPU时间，进程状态等。根据调度算法不同，PCB结构可作适当的调整。

3、 建立进程队列。对不同的算法编制不同的入链程序。

程序要求达到的运行效果：在设置好进程数量、调度算法后，系统能按设定的参数运行，并在屏幕上交替显示就绪队列和完成队列的进程名等信息。

实验步骤和方法

1、 数据结构设计：

PCB结构：

name 进程名

第1页 共6页

实验报告

学院（系）名称：计算机与通信工程学院

姓名 学号 专业 计算机科学与技术

班级 2009级3班 实验项目 实验一：处理机调度算法的实现

课程名称 操作系统 课程代码 0668036

实验时间 2011 年11月17日 第3、4节

2011 年11月21日 第7、8节

2011 年11月24日 第3、4节 实验地点 软件实验室7-216

批改意见 成绩

教师签字：

实验内容：

1． 设定系统中有五个进程，每一个进程用一个进程控制块表示。

2． 输入每个进程的“优先数”和“要求运行时间”。

3． 为了调度方便，将五个进程按给定的优先数从大到小连成就绪队列。用一单元指出队列首进程，用指针指出队列的连接情况。

4． 处理机调度总是选队首进程运行。采用动态优先数算法，进程每运行一次优先数就减“1”，同时将运行时间减“1”。

5． 若某进程运行时间为零，则将其状态置为“结束”,且退出队列。

6． 运行所设计程序，显示或打印逐次被选中进程的进程名，以及进程控制块的动态变化过程。

实验要求：

1． 详细描述实验设计思想、程序结构及各模块设计思路；

2． 详细描述程序所用数据结构及算法；

3． 明确给出测试用例和实验结果；

4． 为增加程序可读性，在程序中进行适当注释说明；

5． 认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等；

6． 实验报告撰写要求结构清晰、描述准确逻辑性强；

7． 实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。

第2页 共6页

【实验过程记录（源程序、测试用例、测试结果及心得体会等）】

程序运行代码如下：

#include

#include

#include

struct PCB{//定义进程控制块PCB，包括进程的名字，优先运行数，运行时间

char name[20];

int pri;

cfs公平调度算法解读

CFS（Completely Fair Scheduler）是Linux内核中的一种公平调度算法，它的目标是实现对多个进程的公平调度，确保每个进程都能够公平地获得CPU的使用权。CFS算法的设计理念是基于时间片的概念，通过动态调整时间片的长度来实现公平调度。

CFS算法的核心思想是将CPU的使用权分配给进程的虚拟运行时间（virtual runtime）最小的进程。虚拟运行时间是一个相对概念，它表示进程在理想情况下应该获得的CPU时间。CFS算法通过不断地更新进程的虚拟运行时间，使得每个进程都能够按照其应有的比例获得CPU的使用权。

CFS算法的实现主要依赖于红黑树这种数据结构。红黑树是一种自平衡的二叉查找树，它能够在O(log n)的时间复杂度内完成插入、删除和查找操作。CFS算法将所有的进程按照虚拟运行时间的大小顺序插入到红黑树中，每次选择虚拟运行时间最小的进程来执行。

CFS算法通过动态调整时间片的长度来实现公平调度。时间片的长度取决于进程的优先级和进程的虚拟运行时间。优先级较高的进程会获得较长的时间片，而虚拟运行时间较小的进程也会获得较长的时间片。这样一来，优先级较高的进程和虚拟运行时间较小的进程都能够更频繁地获得CPU的使用权，从而实现了公平调度。

CFS算法还引入了一个概念叫做“实时性”。实时性是指进程在一段时间内获得CPU的使用权的比例。CFS算法通过不断地调整时间片的长度，使得每个进程的实时性都能够接近其应有的比例。这样一来，每个进程都能够在一定程度上满足其对CPU的需求，从而实现了公平调度。

CFS算法的公平性是相对的，它并不能保证每个进程都能够完全公平地获得CPU的使用权。因为在实际情况下，还有其他因素会影响进程的运行，比如I/O操作、中断处理等。但是CFS算法能够尽量地保证每个进程都能够按照其应有的比例获得CPU的使用权，从而实现了相对公平的调度。