没有合适的资源?快使用搜索试试~ 我知道了~
1. 根据题目要求完成add_ready_thread函数,实现向ready队列末尾加入一个处于就绪状态线程结构 2. 根据题目要求完成schedule函数,实
资源推荐
资源详情
资源评论
操作系统调度算法编程实验
目录
操作系统调度算法编程实验
目录
实验一、简单ready队列调度算法
一、概述
二、实验原理
2-1. 先到先服务(FCFS)调度算法
2-2. deque的使用
2-3. 实验程序的模拟思路
三、设计实现
3-1. 程序说明
3-2. 测试说明
3-3. 提交说明
实验二、引入idle线程和完成语义的线程调度
一、概述
二、实验原理
2-1. idle线程
2-2. 线程运行结束语义
三、设计实现
3-1. 程序说明
3-2. 测试说明
3-3. 提交说明
实验三、引入阻塞和唤醒语义的线程调度
一、概述
二、实验原理
2-1. 阻塞语义
2-2. 唤醒语义
三、实验设计
3-1. 程序说明
3-2. 测试说明
3-3. 提交说明
实验四、基于时间片轮转的线程调度
一、概述
二、实验原理
2-1. 时钟中断
2-2. 时间片轮转调度
三、实验设计
3-1. 程序说明
3-2. 测试说明
3-3. 提交说明
实验五、多级反馈队列调度算法
一、概述
二、实验原理
2-1. 多级反馈队列调度算法
三、实验设计
3-1. 程序说明
3-2. 测试说明
四、提交说明
实验一、简单ready队列调度算法
一、概述
本实验要求同学们在题目提供的C++标准库deque(双端队列)作为ready队列的基础上,按题目要求完
成相应函数的代码实现,在本地自测通过后提交到码图系统中,系统自动评分后取得相应题目的分数。
通过本实验可帮助同学们理解和掌握操作系统中线程的先到先服务的调度算法的基本原理,同时熟悉码
图系统“混合编译型”题目的答题和提交流程。
本实验需完成下列任务:
1. 根据题目要求完成add_ready_thread函数,实现向ready队列末尾加入一个处于就绪状态线程结构
体对象指针的操作。
2. 根据题目要求完成schedule函数,实现从ready队列头部取出一个处于就绪状态的线程结构体指针
的操作。
3. 通过题目提供的测试用例,必要时也可自己编写测试用例,验证所写代码的正确性和健壮性。自测
无误后提交到码图系统进行自动评测并获得相应的分数。
二、实验原理
2-1. 先到先服务(FCFS)调度算法
在非抢占式系统中,先到先服务算法比较自然。使用一个 FIFO(先进先出)队列即可满足要求:所有处
于就绪状态的线程构成一个队列,最先进入队列的线程获得处理器执行权,等到放弃处理器执行权时,
又回到队列尾部,下一个线程继续执行。新的线程进入到队列时被添加到队列尾部。此算法较为简单且
易于实现,但本身性能不佳,一般会作为其他调度算法的局部策略被加以使用。
2-2. deque的使用
在本实验中,我们统一使用C++标准库中的deque容器作为队列使用。
vector容器是单向开口的连续内存空间,deque则是一种双向开口的连续线性空间。所谓的双向开口,
意思是可以在头尾两端分别做元素的插入和删除操作,当然,vector容器也可以在头尾两端插入元素,
但是在其头部操作效率奇差,无法被接受。
deque容器和vector容器最大的差异,一在于deque允许使用常数项时间对头端进行元素的插入和删除
操作。二在于deque没有容量的概念,因为它是动态的以分段连续空间组合而成,随时可以增加一段新
的空间并链接起来。换句话说,像vector那样“旧空间不足而重新配置一块更大空间,然后复制元素,再
释放旧空间”这样的事情在deque身上是不会发生的。也因此,deque没有必须要提供所谓的空间保留
(reserve)功能。
在实际开发中,deque常用操作如下:
size():取队列中元素的个数
push_back(T elem):向队列尾部添加一个元素
front():返回队列头部的一个元素(注意:该操作不将其从队列头部删除)
pop_front():从队列头部弹出一个元素
当需要完成从队列头部取一个元素的操作时,一般首先调用front获取到该元素,然后再调用pop_front
进行弹出。
2-3. 实验程序的模拟思路
本实验为了控制难度,并不需要同学们真的完成线程的上下文切换,而仅仅需要同学们实现调度算法。
因此,实验程序中进行了一系列的简化:
1. 简化的线程控制块
同学们在操作系统课程中已经了解和掌握了线程控制块TCB的作用,真实操作系统的线程控制块往
往是很复杂的,而本实验由于只需对线程调度算法进行模拟,因此对线程控制块进行了精简。详细
的描述请参3-1-1中描述。
2. ready队列
为了控制实验难度,本实验中使用了C++标准库中的deque双端队列作为ready队列,而无需同学
们自行实现队列数据结构。详细的描述请参3-1-2中描述。
3. 简化的执行表示
线程获得CPU执行权并正被执行是一个较难描述的过程,在本实验中将其抽象为了一个全局指针
current_thread。当某个线程TCB的指针赋值给current_thread,在本实验中即代表该线程获得了
CPU执行权。详细的描述请参3-1-3中描述。
三、设计实现
3-1. 程序说明
请根据要求完成thread_student.cpp中以下两个函数的代码,并提交到码图系统进行评分。
1. void add_ready_thread(thread* ready_thread):向ready队列中添加一个新的线程对象指针。
2. void schedule():实现调度算法,按“先到先服务”的算法调度ready队列中的线程,选取合适的线
程对象指针放入current_thread全局变量中。
本实验为了控制难度,并不需要同学们真的完成线程的上下文切换,而仅仅需要同学们实现调度算法。
因此,实验程序中进行了一系列的简化。为确保顺利完成实验并获得相应的分数,请仔细阅读以下实验
说明:
1. 同学们在操作系统课程中已经学习了进程控制块PCB和线程控制块TCB等概念,在本实验中对其进
行了简化。线程控制结构体被简化为了只包含线程ID信息的结构体thread,在头文件thread_hdr.h
中已经定义好了,请同学们不要再重复定义该结构,也不要修改该结构,否则可能导致编译不通过
而无法获取到分数。thread_student.cpp已经包含(include)了thread_hdr.h头文件,可以直接使用
该结构:
2. 本题目使用C++标准库中的deque<thread*>表示ready队列,ready队列已经在测试代码中定义过
了,名为ready_queue,请同学们使用该队列而不要重新定义新的队列,否则可能导致编译不通过
而无法获取到分数。thread_student.cpp已经包含了thread_hdr.h头文件,可以直接使用该变量:
3. 本题目使用thread*类型的全局变量current_thread表示当前被调度算法选中(即模拟正在被CPU
执行的线程)。current_thread已经在测试代码中定义过了,请同学们不要再在代码中定义了,否
则会造成编译不通过。在本题中,同学们将调度算法选中的线程结构的指针赋值给current_thread
即表示算法选中该线程进行执行。
3-2. 测试说明
在完成thread_student.cpp中的add_ready_thread和schedule函数后,大家可以在本地自行测试以
下,也可以在thread_tester代码中自行增加一些测试用例,对一些边界条件和情况进行测试。需要注意
的是,这部分测试代码仅用于保证add_ready_thread和schedule函数的正确性,在提交到码图评测打分
时,不需要提交这部分测试代码。
作为范例,在thread_tester.cpp中提供了一个基础的测试用例:
typedef struct _thread {
unsigned int id;
} thread, * pthread;
typedef std::deque<pthread> thread_queue;
extern thread_queue ready_queue;
extern thread* current_thread;
bool test_two_thread()
{
实际在码图测评系统中,包含有更多、更详细的测试用例,如果程序在提交后只拿到部分分数,请注意
思考边界条件和细节。
3-3. 提交说明
在提交代码时,请只提交包含如下内容的源文件,不要提交thread_hdr.h以及thread_tester.cpp,否则
会导致不通过编译而无法得分。若提交后仅拿到部分分数,请仔细阅读题目要求并确认实现细节特别是
边界条件。本题提交的代码样例如下:
再次强调,在提交代码时,请不要提交thread_hdr.h以及thread_tester.cpp中的代码,也不要提交
main函数。
实验二、引入idle线程和完成语义的线程调度
current_thread = NULL;
ready_queue.clear();
// 向ready队列中加入一个线程
thread thread1 = { 1 };
thread thread2 = { 2 };
add_ready_thread(&thread1);
add_ready_thread(&thread2);
// 进行切换时,将current_thread切换为thread1
schedule();
if (current_thread != &thread1 || ready_queue.size() != 1)
{
return false;
}
// 进行切换时,将current_thread切换为thread1
schedule();
if (current_thread != &thread2 || ready_queue.size() != 1)
{
return false;
}
return true;
}
int main()
{
bool ret = test_two_thread();
std::cout << ret << std::endl;
return 0;
}
#include "thread_hdr.h"
void add_ready_thread(thread* ready_thread)
{
// 相应的代码实现
}
void schedule()
{
// 相应的代码实现
}
剩余22页未读,继续阅读
资源评论
牛站长
- 粉丝: 23
- 资源: 299
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功