README.md 12.4 KB
Newer Older
勇敢牛牛队's avatar
勇敢牛牛队 committed
# proj134-CFS-based-userspace-scheduler
勇敢牛牛队's avatar
勇敢牛牛队 committed



## Getting started

To make it easy for you to get started with GitLab, here's a list of recommended next steps.

Already a pro? Just edit this README.md and make it your own. Want to make it easy? [Use the template at the bottom](#editing-this-readme)!

## Add your files

- [ ] [Create](https://docs.gitlab.com/ee/user/project/repository/web_editor.html#create-a-file) or [upload](https://docs.gitlab.com/ee/user/project/repository/web_editor.html#upload-a-file) files
- [ ] [Add files using the command line](https://docs.gitlab.com/ee/gitlab-basics/add-file.html#add-a-file-using-the-command-line) or push an existing Git repository with the following command:

```
cd existing_repo
git remote add origin https://gitlab.eduxiji.net/202311664111498/proj134.git
git branch -M main
git push -uf origin main
```

## Integrate with your tools

- [ ] [Set up project integrations](https://gitlab.eduxiji.net/202311664111498/proj134/-/settings/integrations)

## Collaborate with your team

- [ ] [Invite team members and collaborators](https://docs.gitlab.com/ee/user/project/members/)
- [ ] [Create a new merge request](https://docs.gitlab.com/ee/user/project/merge_requests/creating_merge_requests.html)
- [ ] [Automatically close issues from merge requests](https://docs.gitlab.com/ee/user/project/issues/managing_issues.html#closing-issues-automatically)
- [ ] [Enable merge request approvals](https://docs.gitlab.com/ee/user/project/merge_requests/approvals/)
- [ ] [Automatically merge when pipeline succeeds](https://docs.gitlab.com/ee/user/project/merge_requests/merge_when_pipeline_succeeds.html)

## Test and Deploy

Use the built-in continuous integration in GitLab.

- [ ] [Get started with GitLab CI/CD](https://docs.gitlab.com/ee/ci/quick_start/index.html)
- [ ] [Analyze your code for known vulnerabilities with Static Application Security Testing(SAST)](https://docs.gitlab.com/ee/user/application_security/sast/)
- [ ] [Deploy to Kubernetes, Amazon EC2, or Amazon ECS using Auto Deploy](https://docs.gitlab.com/ee/topics/autodevops/requirements.html)
- [ ] [Use pull-based deployments for improved Kubernetes management](https://docs.gitlab.com/ee/user/clusters/agent/)
- [ ] [Set up protected environments](https://docs.gitlab.com/ee/ci/environments/protected_environments.html)

***

# Editing this README

When you're ready to make this README your own, just edit this file and use the handy template below (or feel free to structure it however you want - this is just a starting point!). Thank you to [makeareadme.com](https://www.makeareadme.com/) for this template.

## Suggestions for a good README
Every project is different, so consider which of these sections apply to yours. The sections used in the template are suggestions for most open source projects. Also keep in mind that while a README can be too long and detailed, too long is better than too short. If you think your README is too long, consider utilizing another form of documentation rather than cutting out information.

## Name
勇敢牛牛队's avatar
勇敢牛牛队 committed
Our project is named ”Brave Cow“,the full name is Xi'an University of Posts and Telecommunications, Brave Bull Team, Proj134。We are three graduate students from Xi'an University of Posts and Telecommunications, working hard like cows to overcome difficulties
勇敢牛牛队's avatar
勇敢牛牛队 committed

## Description
勇敢牛牛队's avatar
勇敢牛牛队 committed
ghOSt是一种用户态的调度框架,它利用Linux内核提供的CFS调度器来实现任务的调度,并使用了一些技术手段(如Golang中的协程)来优化调度性能。同时,ghOSt还支持在运行时动态地修改CPU时间配额和优先级等调度参数,以及将这些参数委托给其他进程或者容器执行。
勇敢牛牛队's avatar
勇敢牛牛队 committed
基于CFS且兼容cpu cgroup的用户态调度框架,需要考虑以下几个方面:
勇敢牛牛队's avatar
勇敢牛牛队 committed
1. 如何利用Linux内核提供的CFS调度器进行任务调度。
2. 如何处理CPU资源隔离和限制的问题,以保证任务调度的可控性和安全性。
3. 如何实现任务调度策略的灵活配置和管理。

在ghOSt的设计中,第一个问题已经得到了解决,因为它直接使用了CFS调度器来进行任务调度。第二个问题,ghOSt采用了类似于Docker和Kubernetes中的CPU cgroup技术,将CPU资源隔离和限制分配给不同的进程或者容器。第三个问题可以通过ghOSt提供的API和命令行工具来实现。
勇敢牛牛队's avatar
勇敢牛牛队 committed

## Badges
勇敢牛牛队's avatar
勇敢牛牛队 committed

## Visuals
勇敢牛牛队's avatar
勇敢牛牛队 committed

## Installation
勇敢牛牛队's avatar
勇敢牛牛队 committed
- 资源:
  - ghOSt-kernel:https://github.com/google/ghost-kernel
  - ghOSt-userspace:https://github.com/google/ghost-userspace

- 环境:Ubuntu20.04,核心数尽量配大一点 比如8
- 安装需要的工具
  - sudo apt update
  - sudo apt install git fakeroot build-essential ncurses-dev xz-utils libssl-dev bc flex libelf-dev bison dwarves zstd

编译安装ghost内核:

- 进入`ghost-kernel`,切换到root用户`sudo su`
- make menuconfig
- 后会在当前目录生成一个隐藏文件.config,对它进行如下修改
  将CONFIG_SYSTEM_TRUSTED_KEYS="debian/canonical-certs.pem"修改为CONFIG_SYSTEM_TRUSTED_KEYS="" (vi编辑器下可以通过/进行查找)
  添加CONFIG_SCHED_CLASS_GHOST=y
- 编译:make -j $(nproc)
- make modules_install
- 安装内核:make install
- 修改gurb
  - ubuntu20.04默认情况下,开机看不到grub界面,也就无法选择进入新编译好的内核。因此需要修改/etc/default/grub文件,将其中的“GRUB_TIMEOUT_STYLE=hidden”注释掉,以显示grub界面;CMDLINE设置为text;并且将GRUB_TIMEOUT修改成“GRUB_TIMEOUT = 30”,以留出30秒时间让用户选择进入哪个内核:
- 重启之后,选择ghOSt的内核进行启动即可

使用ghost用户空间组件

- 首先安装Bazel(谷歌常用的代码构建工具,类似于make,但bazel效率更高、更敏捷)
  - https://bazel.build/install/ubuntu?hl=zh-cn
- 编译/构建调度器:比如说:bazel build -c opt fifo_per_cpu_agent #构建每个CPU的FIFO调度器
- 启动代理:bazel-bin/fifo_per_cpu_agent --ghost_cpus 0-1可以启动相应的代理
- bazel-bin文件夹中,运行它可以测试相应ghOSt调度器
勇敢牛牛队's avatar
勇敢牛牛队 committed

## Usage
勇敢牛牛队's avatar
勇敢牛牛队 committed

## Support
勇敢牛牛队's avatar
勇敢牛牛队 committed
281954501@qq.com
勇敢牛牛队's avatar
勇敢牛牛队 committed

## Roadmap
勇敢牛牛队's avatar
勇敢牛牛队 committed

## Contributing
勇敢牛牛队's avatar
勇敢牛牛队 committed
ghOSt利用CFS进行任务调度的原理:

原理如下:

1. 首先,ghOSt会创建一个专门的线程来作为调度线程,该线程会循环遍历待执行任务列表(ready queue)和已执行任务列表(run queue)。
2. 在遍历过程中,调度线程会根据CFS调度算法的规则,选择并执行下一个应该被调度的任务。具体来说,CFS调度算法会根据任务的虚拟运行时间(virtual runtime)和权重等参数,计算出每个任务应该占用CPU资源的比例,并按照这个比例分配CPU时间片。
3. 为了优化调度性能和灵活性,ghOSt还引入了一些技术手段。例如,它会使用Golang中的协程(goroutine)来实现任务的轻量级切换,避免了频繁地进行线程上下文切换;另外,它还支持在运行时动态地修改CPU时间配额和优先级等调度参数,以及将这些参数委托给其他进程或者容器执行。

具体操作如下:

下面是ghOSt利用CFS进行任务调度的具体操作:

1. ghOSt首先需要创建自己的进程,并在此进程中调用sched_setscheduler()函数将调度策略设置为SCHED_FIFO或SCHED_RR。
2. 接下来,ghOSt会创建一个或多个线程,并使用pthread_setschedparam()函数将线程的调度策略设置为SCHED_OTHER。
3. 在这些线程中,ghOSt会定期地调用sched_yield()函数,以便将CPU时间片让给其他进程或线程。
4. 当ghOSt需要执行另一个进程时,它会使用setcontext()函数将当前上下文保存到堆栈中,并加载新进程的上下文。
5. 在新进程上下文中,ghOSt会使用sched_setaffinity()函数将进程绑定到特定的CPU核心上,然后再次使用pthread_setschedparam()函数将进程的调度策略设置为SCHED_OTHER。
6. 接下来,ghOSt会通过sigaltstack()函数创建一个新的信号堆栈,并使用sigaction()函数注册一个信号处理程序,以便在发生预定的事件(如时间到期、IO完成等)时通知ghOSt。
7. 最后,当ghOSt需要结束当前进程并返回到上一个进程时,它会使用setcontext()函数将堆栈中保存的上下文恢复,并继续执行之前的进程。

.c代码演示了ghOSt如何利用CFS进行任务调度的具体实现过程。

在.c示例代码中,我们首先创建了一个新进程,并在子进程中进行任务调度。具体来说,我们通过调用sched_setaffinity()函数将子进程绑定到第一个CPU核心上,并使用sched_setscheduler()函数将其调度策略设置为SCHED_OTHER。接着,我们使用pthread_create()函数创建一个新线程,并在其中不断调用sched_yield()函数以让出CPU时间片。

在父进程中,我们也使用sched_setscheduler()函数将其调度策略设置为SCHED_OTHER,并通过kill()函数向子进程发送SIGUSR1信号。当子进程接收到该信号时,它会调用预注册的信号处理程序sig_handler()函数,并进行相应的操作。

处理CPU资源隔离和限制:
勇敢牛牛队's avatar
勇敢牛牛队 committed

勇敢牛牛队's avatar
勇敢牛牛队 committed
CPU cgroup 是 Linux 内核提供的一种机制,用于将进程分组并限制它们的 CPU 使用率。在 ghOSt 中,每个用户进程都会被分配到一个独立的 cgroup 中,这样就可以对每个用户进程进行资源隔离和限制。
勇敢牛牛队's avatar
勇敢牛牛队 committed

勇敢牛牛队's avatar
勇敢牛牛队 committed
具体而言,当一个新用户进程创建时,ghOSt 会创建一个与该进程关联的 CPU cgroup,并将该进程加入到该 cgroup 中。然后,ghOSt 根据这个进程的运行时间、优先级等信息动态地调整该 cgroup 的 CPU 时间片配额,以达到对进程的资源管理目的。

此外,在 ghOSt 中,为了避免因为 CPU 资源不足而导致用户进程响应延迟或阻塞,还引入了 CPU 预留机制。通过预留 cgroup 的 CPU 时间片配额,确保重要进程能够及时响应,从而提高系统的可用性和稳定性。

设计自己的调度策略和API:

设计一个支持动态调整CPU时间配额和优先级的策略,并实现相应的API和命令行工具。具体来说,您需要定义调度组件的数据结构,包括组件ID、CPU时间配额、优先级等字段,并提供增加、删除、修改组件等API。另外,为了方便使用,还要实现命令行工具,供用户直接调用。

流程如下:

1. 首先,ghOSt将整个CPU时间分成若干个时间片(time slices),并将这些时间片分配给不同的进程或线程。默认情况下,所有进程或线程共享相等数量的时间片。
2. 当某个进程或线程需要更多的CPU时间时,它可以向ghOSt请求更多的时间片。例如,如果某个线程正在执行一个重要任务,但它的CPU时间配额用完了,那么它可以请求更多的时间片以完成任务。
3. ghOSt会根据请求的合理性和当前系统的负载情况来决定是否批准该请求。如果系统处于高负载状态,那么请求可能会被拒绝,以便其他进程可以获得更多的CPU时间。
4. 此外,ghOSt还可以根据进程或线程的优先级来动态调整它们的CPU时间配额。例如,如果某个线程的优先级较高,那么它可以获得更多的CPU时间,以便它能够更快地完成任务。

基于以上思路,我们可以设计一个类似的线程池,支持动态调整CPU时间配额和优先级

这里主要是使用了ghost当中的一些API,ghost 调度类提供了一系列 API 接口,用于在用户空间中实现灵活的进程调度和管理。

下面是 ghost 调度类提供的一些主要 API 接口:

![image-20230605234158767](E:/%E6%96%B0%E5%BB%BA%E6%96%87%E4%BB%B6%E5%A4%B9%20(2)/image-20230605234158767.png)

这些 API 可以让应用程序开发者更好地控制任务的调度和资源分配,使得应用程序可以更有效地利用系统资源并提高性能。同时,这些 API 的存在也让 Ghost 调度器更加灵活和可扩展,可以适应不同的工作负载类型和需求。
勇敢牛牛队's avatar
勇敢牛牛队 committed

## Authors and acknowledgment
勇敢牛牛队's avatar
勇敢牛牛队 committed
我们这个团队
勇敢牛牛队's avatar
勇敢牛牛队 committed

## License

勇敢牛牛队's avatar
勇敢牛牛队 committed
## Project status
1. 在用户空间中实现成熟的Linux调度策略,例如CFS等,并保持与内核态相同的调度精度和可控性。
2. 兼容cpu cgroup机制,使得用户态调度框架能够有效地与Linux系统中的其他组件协同工作。
3. 提供高效的调度方案,以确保系统响应时间和吞吐量都能得到最大化的提升。
4. 支持多种不同的调度算法和策略,以便用户可以选择最适合其需求的解决方案。
5. 提供友好的API和命令行工具,以方便用户管理和监控调度器的运行状态。