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 关联性检查,进一步提高了缓存命中率和系统性能。
本实验提出的混合调度算法通过结合**彩票调度**、**完全公平调度**和**强化学习**,以及对**pick_process**的优化,有效解决了xv6默认调度算法在公平性、灵活性和性能方面的问题。测试结果表明,该算法在不同任务类型下均表现出色,显著提高了系统的整体效率和用户体验。
### 测试环境:
- 虚拟机:VMware Workstation 16 Pro
- 操作系统: Ubuntu-20.04.3-desktop-amd64
$ 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
```
## 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/)。
- **强化学习**:参考了相关书籍 [Reinforcement Learning: An Introduction](http://incompleteideas.net/book/the-book-2nd.html)。