Newer
Older
## 2. 队伍编号、队伍名
- **队伍编号**: T202410269994314
- **队伍名**: jimmycocopuf
## 3. 队伍成员、指导老师
- **队伍成员**:
- 柳絮源
- 沈超
- **指导老师**: 石亮
## 4. 项目完成情况介绍
在现代操作系统中,进程调度是一个关键组件,直接影响系统的性能和用户体验。xv6操作系统自带的调度算法是一种基于协作式调度的轮询调度算法,其核心思想是通过遍历所有进程,选择一个可运行的进程并切换到其上下文。然而,这种调度算法存在以下几个问题:
1. **缺乏公平性**
xv6的调度算法依赖于进程的主动让出CPU,可能导致某些进程长时间占用CPU,而其他进程无法获得足够的执行时间,从而引发饥饿问题。
2. **缺乏灵活性**
xv6的调度算法没有考虑进程的优先级或权重,所有进程在调度时被同等对待,无法根据进程的活跃度或重要性动态调整其执行时间。
3. **缓存命中率低**
xv6的调度算法在选择进程时没有考虑CPU关联性,可能导致进程频繁在不同CPU之间迁移,从而降低缓存命中率,影响系统性能。
4. **时间片管理不足**
xv6的调度算法没有明确的时间片管理机制,可能导致某些进程长时间占用CPU,而其他进程无法及时获得执行机会。
5. **工作量与效率的平衡不足**
xv6的调度算法缺乏对计算密集型、I/O密集型和混合型任务的区分,无法根据任务类型动态调整调度策略,导致系统整体效率不高。
为了解决传统调度算法在公平性、灵活性、缓存命中率和时间片管理方面的不足,本实验提出了一种结合**彩票调度**与**完全公平调度** (CFS) 的混合调度算法。该算法通过动态调整进程的彩票数量和虚拟运行时间(vruntime),实现了公平性与灵活性的平衡,显著提升了调度算法的性能。此外,本实验还对 **pick_process 函数**进行了优化,通过引入 CPU 关联性检查,进一步提高了缓存命中率和系统性能。
为了验证混合调度算法的有效性,本实验设计了一套**全面的测试程序`test.c`**,通过模拟计算密集型、I/O密集型和混合型任务,评估调度算法在不同任务类型下的表现。
1. **任务类型模拟**
- 计算密集型任务:执行大量CPU计算。
- I/O密集型任务:频繁进行I/O操作。
- 混合型任务:结合计算和I/O操作。
2. **性能指标测量**
- **执行时间**:每个任务从开始到结束的总时间。
- **等待时间**:每个任务在就绪队列中的等待时间。
- **系统吞吐量**:单位时间内完成的任务数量。
3. **结果分析**
- 比较混合调度算法与xv6默认调度算法在不同任务类型下的表现。
- 评估算法在公平性、灵活性和性能方面的改进。
本实验提出的混合调度算法通过结合**彩票调度**和**完全公平调度**以及对**pick_process**的优化,有效解决了xv6默认调度算法在公平性、灵活性和性能方面的问题。测试结果表明,该算法在不同任务类型下均表现出色,显著提高了系统的整体效率和用户体验。
未来工作可以进一步优化算法的实现细节,并探索在多核环境下的扩展性。
操作系统: Ubuntu-20.04.3-desktop-amd64
#### 测试实验配置:
1. 安装依赖
```bash
$ sudo apt-get install git build-essential gdb-multiarch
qemu-system-misc gcc-riscv64-linux-gnu binutils-riscv64-linux-gnu
```
2. 安装特定版本的qemu
```bash
$ sudo apt-get remove qemu-system-misc
$ sudo apt-get install qemu-system-misc=1:4.2-3ubuntu6
```
3. 在Linux环境下,执行以下命令进行测试:
```bash
$ make clean
$ make qemu
$ ./test
```
## 6. 代码的参考情况并给出链接
本项目参考了xv6操作系统的源码以及相关调度算法的论文,具体参考内容如下:
- **xv6操作系统源码**:[xv6 GitHub仓库](https://github.com/mit-pdos/xv6-public)
- **彩票调度算法**:参考了相关论文 [Lottery Scheduling: Flexible Proportional-Share Resource Management](https://www.usenix.org/legacy/publications/library/proceedings/osdi/full_papers/waldspurger.pdf)。
- **CFS调度算法**:参考了相关博客 [Linux CFS 调度器:原理、设计与内核实现](https://arthurchiao.art/blog/linux-cfs-design-and-implementation-zh/)。