Skip to content
This repository has been archived by the owner on Feb 4, 2022. It is now read-only.

Latest commit

 

History

History
152 lines (122 loc) · 6.4 KB

第二章-共享调度器设计与实现.md

File metadata and controls

152 lines (122 loc) · 6.4 KB

共享调度器设计与实现

在内核态和用户态共享任务资源,实现对任务的统一调度。

1 共享调度器的设计思路

在飓风内核中,共享调度器中黑盒调度任务池资源,同时为内核和用户提供一系列的数据接口,实现任务资源在内核态和用户态两者之间的统一调度。

调度元数据

共享调度器中的调度单元是任务的元数据,大致包含以下部分:

  • hart_id: 运行该任务的硬件线程编号(处理核的ID)
  • address_space_id: 地址空间编号
  • task_repr: 任务指针,由所在的地址空间解释为任务
  • state: 任务状态

hart_id是为多核场景下的预留位,每一个任务只能被一个核占。

address_space_id指示这个任务的地址空间编号,地址空间的概念可以参考文章地址空间与进程

task_repr是任务元数据中最重要的成员,它可以理解为“任务的表示”,更具体也可以理解为“任务的指针”。task_repr只有在它属于的地址空间里面才能被“解释”。所谓解释,就是任务指针通过正确的虚实地址转换得到正确的任务结构体,比如像下面这样:

struct KernelTask<T> {
    inner: T
}
unsafe fn get_task<T>(task_repr: usize) -> Arc<KernelTask<T>> {
    Arc::from_raw(task_repr as *mut _)
}

如果task_repr在其他地址空间尝试被解释,那么很可能会触发缺页异常,就算可以被解释,解释出来的数据也是不对的。这得益于指令集设计上地址空间隔离的作用,可以实现一定的安全性保障。

state标记这个任务的状态,至少会有两种状态的存在:就绪与睡眠。就绪状态的任务表示该任务的某个阶段已经准备好可以进一步执行;睡眠状态的任务表示该任务需要等待一些数据或者其他任务的完成,处于等待状态。

就绪状态的任务可以被共享调度器弹出交给内核和用户运行,睡眠状态的任务只有被唤醒之后才能转成就绪状态,然后被进一步执行。

集成接口

共享调度器向内核和用户提供统一的一系列接口:

接口名称 参数 返回值 作用
add_task 核ID,地址空间编号,任务指针 bool 添加任务
peek_task 一个调用参数为地址空间编号,返回值为bool的函数指针 任务的表示/没有醒着的任务/所有任务已完成 返回下一个任务的指针,不弹出任务
delete_task 任务指针 bool 删除参数指定的任务
set_task_state 任务指针,状态 () 改变指定任务的状态

note: 在后续开发过程中可能会增加或减少某些接口。

2 共享调度器的实现

以二进制包的形式编译

共享调度器目前以二进制包的形式编译出elf文件,然后通过objcopy工具转换成二进制文件,直接烧写到内存里面。

共享调度器之所以以这种方式呈现,是因为在内核态和用户态两个不同的地址空间都需要访问共享调度器,这就需要在内核和用户页表上分别映射共享调度器所使用到的内存空间。而使用二进制包方式编译可以方便内核和用户进行对共享调度器的地址映射。

元数据的实现

先介绍一些相关的数据结构实现:

/// 任务的表示(指针)
///
/// 该结构可以在正确的地址空间里解释成为任务
struct TaskRepr(usize);

/// 地址空间编号
struct AddressSpaceId(u16);

/// 任务的状态
enum TaskState {
    /// 就绪状态,可以被执行器执行
    Ready = 0,
    /// 睡眠状态
    ///
    /// 一个任务通常被执行器进行`poll`操作后返回`Pending`而被设置为睡眠状态,
    /// 需要被唤醒后才能再次被执行器执行
    Sleeping = 1
}

共享调度器调度的元数据以以下结构体呈现:

struct TaskMeta {
    /// 核的编号
    hart_id: usize,
    /// 地址空间编号
    ///
    /// 内核地址空间编号是0,用户地址空间编号从1开始增长
    address_space_id: AddressSpaceId,
    /// 任务指针,由所在地址空间解释
    task_repr: TaskRepr
}

调度器实现

共享调度器的实现中调度算法和调度对象是相互独立的,这里实现了一个先进先出轮转任务调度器

/// 常量泛型参数`N`表示调度器的容量
struct RingFifoScheduler<T, const N: usize> {
    ring: RingQueue<T, N>, // 容量为`N`的循环队列
    current: Option<T>
}

然后将TaskMeta填到泛型参数T里面,再加上自旋锁保证数据一致性和提供内部可变性,就得到了共享调度器的类型:

/// 调度对象为[`TaskMeta`],容量为400的共享调度器
type SharedScheduler = Mutex<RingFifoScheduler<TaskMeta, 400>>;

Rust里面常量泛型的语法可以参考这篇文章

使用static语法实现全局的共享调度器:

static SHARED_SCHEDULER: SharedScheduler = Mutex::new(RingFifoScheduler::new());

共享调度器会被放到数据段,内核或用户从这个地址取得共享调度器。

接口的实现

共享调度器目前实现了以下接口:

/// 给共享调度器添加任务
pub unsafe extern "C" fn shared_add_task(
    shared_scheduler: NonNull<()>,
    hart_id: usize,
    asid: AddressSpaceId,
    task_repr: TaskRepr,
) -> bool { todo!() }
/// 从共享调度器中找到下一个任务
pub unsafe extern "C" fn shared_peek_task(
    shared_scheduler: NonNull<()>,
    should_switch: extern "C" fn(AddressSpaceId) -> bool,
) -> TaskResult { todo!() }
/// 删除一个共享调度器中的任务
pub unsafe extern "C" fn shared_delete_task(
    shared_scheduler: NonNull<()>,
    task_repr: TaskRepr,
) -> bool { todo!() }
/// 设置任务的状态
pub unsafe extern "C" fn shared_set_task_state(
    shared_scheduler: NonNull<()>,
    task_repr: TaskRepr,
    new_state: TaskState,
) { todo!() }

由于具体实现篇幅太长,这里不详细描述,有兴趣的朋友请参考代码

TODO

  • 更丰富的工程学上的稳定接口
  • 更高效,包含优先级的调度算法
  • 更精确的内存管理