README.md

# 模块实验创新-基于FDU-OS的实时调度实现 

**分支介绍**
- MF-lazy(主分支)
- RMS-lss(未使用懒标记)
- Base(课程架构的基础，可进行课程lab的测试)

在课程框架(框架以及完成的任务写在后面)的基础上，尝试实现了RTOS的部分内容，主要有如下内容：

- proc结构体中加入优先级，周期，运行时间等与实时相关的属性
- 实现RMS调度，选择周期最短的进程
- 实现临界资源结构体，并使用Ceiling解决优先级反转的问题
- 实现了多重队列，引入懒标记机制，优化访问次数。

为了简化系统，我们采用了多核独立的方式实现，即每个CPU核独自享有一个调度队列，他们之间只有CR是共享的。

## proc 结构体
位于./src/kernel/proc.h中
```c
typedef struct Proc {
    bool killed;
    bool idle;
    int pid;//可被回收复用
    int exitcode;
    int wait_time;
    int prim_priority; // 任务原始优先级
    int true_priority; // 任务的真实优先级
    int current_time ;//当前时间，用来重启任务
    int period;        //任务周期
    int exec_time;     // 需要的执行时间
    int execed_time;  // 已执行时间
    enum procstate state;
    Semaphore childexit;
    SpinLock plock;//进程锁，猛猛加锁，解决并发问题
    ListNode children;
    ListNode ptnode;
    ListNode crnode;//CR资源链表
    struct Proc *parent;
    struct schinfo schinfo;
    struct pgdir pgdir;
    void *kstack;
    UserContext *ucontext;
    KernelContext *kcontext;
} Proc;

```
在原有的基础上，新增优先级，分为原始优先级和真实优先级，进程在获取临界资源时优先级会发生变化，释放时需要还原优先级，所以需要两个优先级来维护。

current_time用于记录当前进程的时间，每隔period时间就重启一次。exec_time时间为预测的需要执行时间，execed_time为已执行时间，如果大于exec_time则放到完成队列等待重启。

crnode，考虑到任务可能需要获取多个临界资源，所以用一个链表来维护。

## RMS调度

位于./src/kernel/sched.c

在进程初始化时，传入需要运行时间(exec_time)以及周期(period)进行初始化，模拟RTOS中预测运行时间的行为。

以MAX(20-period/100,0)作为优先级，分配进入对应的队列，多重队列总共25级，其中0到20为实时部分，-4到-1为非实时的(本项目中暂未使用，未来可整合在一起)

调度时，从优先级为20的队列开始寻找，如果不为空，则进入队列后选取第一个进程，在其完成之前不会选择其他进程，除非被高优先级抢占了。

由于课程架构中每个进程享有固定长度的时间片，且时间片耗尽后进行下一次调度，所以在这种情况下，RMS会出现抢占的情况，即上一个低优先级任务时间片耗尽了，但没完成，又到了高优先级任务的新周期，这时候高优先级就会抢占低优先级的cpu资源。

运行效果：

![RMS-preemption](./images/preemption.png)

可以看到高优先级的进程一旦准备就绪，会立刻进行抢占。(这是使用懒标记后的演示图)

## 临界资源

```c
typedef struct CR {
    SleepLock lock;        // 睡眠锁
    ListNode node;
    int priority;           // 资源的优先级
    int cid;              // 资源的ID
} CR;
```

在内核初始化20个临界资源,并让子进程尝试获取。基于此实现了Ceiling的算法以解决优先级反转的问题，为了简单起见，所有CR资源的Ceiling优先级都设置为最高(20)，每个进程在获取CR资源后，其`true_priority`临时提升为CR的Ceiling优先级，这样有两个好处：

1. 可以解决优先级反转的问题，不会出现高优先级等待低优先级的问题

2. 在进程切换时，保证让获取CR的进程较为优先，让其尽早完成，释放CR锁，避免频繁切换导致频繁获取释放CR。

在获取和释放时需要将进程放入对应的优先级队列

运行效果：

![CR](./images/CR.png)

可以看到一个低优先级的任务(14)先获取了CR资源，优先级提升为(20)，这时一个高优先级任务(18)也要获取CR资源，但必须要等待低优先级完成，如果没有Ceiling，就导致了优先级反转，使用Ceiling解决了这个问题。

## 带有懒标记的多重队列


实现多重队列的动机是减少进程切换时对调度队列的访问次数，但我们发现在RTOS直接使用多重队列其实并没什么用，因为每次切换必须更新current_time，这要求无论如何遍历所有的进程。

但同时我们注意到很多低优先级的任务其实不需要频繁的更新当前时间，只需要在被使用时更新，得知当前时间以及判断是否超时即可。鉴于我们尝试的是软实时操作系统，假设是任务miss不会有什么严重后果，所以这个想法应该是可行的。

因此为调度队列引入了一个懒标记Lazy，以及一个完成任务的队列complete，并类似的引入comLazy和comReady标签，后者记录了完成队列中进程最短还有多久就绪。

在time-handler中进行更新时，依旧从高向低遍历多重队列，如果不为空，则进入该级队列，遍历当中的所有进程，假设级别为level，则更新公式为：
$$
current = (current +elapse+rqLazy[level])\%period
$$
​	其中current为进程当前时间，elapse为时间片长度，rqLazy是每一级的懒标记,period是该进程的周期。

​	更新完这一级后，向下更新懒标记：
$$
rqLazy[level-1]=\left \{
\begin{aligned}
&rqLazy[level-1]+rqLazy[level]+elapse& level>0\\
& 0&else
\end{aligned}
\right.
$$
随后将$rqLazy[level]$置为0

在此之前，还需要检查comReady和comLazy，如果前者小于等于后者，则需要遍历complete，使用Lazy进行更新，与rq是类似的。

### 效果

这是没有使用lazy前的，多重队列每次handler的平均访问次数：

![withoutLazy](./images/withoutLazy.png)

使用lazy后：

![Lazy](./images/MQwithLzy.png)


访问次数是原始值的**29.73%**，效果显著，且没有破坏调度的逻辑。

## 运行方法

输入make qemu即可

测试文件在./src/test/rbtree_test.c

最后，由于时间所限，没有将实时的部分与课程中的lab整合在一起，所以在MF-lazy和RMS-lss分支无法进行课程lab中的测试。

# 遇到的问题

1. time_handler

每次进程切换，都需要更新所有进程的当前时间current_time，以及当前进程的已运行时间等相关属性，但由于课程架构trap_return的入口固定为user_proc_test,无法正常使用cpu的timer，鉴于本项目仅测试一部分模块，于是在sched内部使用`Insched_timer_handler`用于模拟时间片，也能起到测试的作用。

2. RTOS的测试问题

由于实时任务需要每隔一段时间就重启，所以测试基本使用while死循环，同时在while内部使用`sleep`(让cpu空转的函数)来模拟任务运行，sleep后显示的进行进程切换，代表该任务已用完一个时间片，以此来进行调度测试。

3. 更新时间的并发问题

课程框架中的调度队列是多核共享的，这样实现管理起来比较简洁。但实时任务需要更新current_time，且每个cpu核进行进程切换时都会更新，如果只有一个调度队列，将会导致current_time被多次更新。为了解决这个问题，我们采用多核独立的思路，使用多个调度队列，让每个核独占一个调度队列，以确保时间的正确更新。

4. 使用多重队列获取CR时page fault

之前的版本中CR使用的是睡眠锁，进入睡眠后运行时间应该不会增加，但错误的增加了运行时间，使得进程在睡眠中也能完成，因此会进入complete完成队列，在后续被唤醒时，`activate`会将整个完成队列插入到调度队列中，导致page fault。现在的版本解决了这个问题，使用自旋锁忙等，这样避免了进程命名在等待，却还会认为在执行任务。

# 未来改进方向

1. 解决时钟中断问题。

2. 为临界资源增加一个data buf，使得任务可以通过这块区域进行数据共享。 

3. 将本项目的实时部分与课程lab整合在一起，可以作为一个拓展的模块。

4. 更好的测试方式，比如在给定的一个任务序列以及CR获取序列，其调度顺序应该是固定的，可以检验这个来验证调度算法的正确性。考虑到性能，可以用在handler中访问队列的平均次数来衡量，也可以进行测试，比如规定需要小于多少。



以下是FDU-OS的课程框架

# OS-24Fall-FDU
Lab repository for OS Fall 2024 at Fudan University

这是复旦大学 2024 年秋季学期《操作系统（H）》课程的配套实验内容。我们将建立一个基于 ARM 架构的简易教学操作系统。

[实验文档](https://osh.fducslg.com)

暂定的实验内容将包括：

* 引导 Booting
* 内存管理
* 进程管理
* 多核管理
* 中断与异常、缺页处理
* 块设备驱动
* 文件系统
* IPC
* Shell

Reference:

- [去年的实验](https://github.com/FDUCSLG/OS-23Fall-FDU/)

- [Arm® Architecture Reference Manual](https://cs140e.sergio.bz/docs/ARMv8-Reference-Manual.pdf)
- [Arm® Instruction Set Reference Guide](https://ipads.se.sjtu.edu.cn/courses/os/reference/arm_isa.pdf)
- [ARM Cortex-A Series Programmer’s Guide for ARMv8-A](https://cs140e.sergio.bz/docs/ARMv8-A-Programmer-Guide.pdf)
- [ARM GCC Inline Assembler Cookbook](https://www.ic.unicamp.br/~celio/mc404-s2-2015/docs/ARM-GCC-Inline-Assembler-Cookbook.pdf)
- [ucore step-by-step](https://1790865014.gitbook.io/ucore-step-by-step/)
- [ucore实验指导书](https://chyyuu.gitbooks.io/ucore_os_docs/content/)


# 各部分的实现：
    基于学校课程的架构，完成了以下内容（独立编写的部分会在文档中说明）：
## 内存管理
位于./src/mem.c中

实现了一个基于链表和块划分的简单的物理内存分配器。使用Slab分块管理内存,实现函数包括
- kinit
- kalloc_page、kfree_page
- get_allocator_index
- kalloc
- kfree

### 运行结果

评测指标为使用物理页数，以下为连续三次测试的结果。

![lab1-result](./images/lab1-result.png)


## 内核进程

- ./src/aarch64/switch.S
- ./src/aarch64/trap.S
- ./src/kernel/proc.c
- ./src/kernel/sche.c中

实现了如下图所示的进程状态转换逻辑的内核进程部分。

![lab2-trans](./images/lab2-trans.png)

调度算法为FIFO。

### 运行结果

主要测试是否能正确exit和wait：

![lab2-result](./images/lab2-result.png)

## 用户进程

该部分同时完成了页表的相关操作,通过中断进入用户态。

- ./src/kernel/pt.c
- ./src/aarch64/trap.S
- ./src/kernel/proc.c 中新增kill

调度算法是绝对公平的调度,选取等待时间最长的进程（即最先进入队列的）

### 运行结果

测试了页表的功能，以及用户进程

![lab3-vmresult](./images/vmtest.png)
![lab3-user](./images/user_proctest.png)

以上部分测试，可在./src/kernel/core.c,解注释掉kernel_entry的一系列test后，输入make qemu进行测试。

kalloc_test似乎随着课程框架的更新，没有加入编译，无法正确定位。

## 文件系统

只提供接口，使用mock方法进行测试

- ./src/fs/cache.c
- ./src/fs/inode.c

### 运行结果

![lab5-result](./images/OS_lab5.png)
![lab6-result](./images/lab6-result.png)

# 日志

## RMS新增 12.8

### 测试

测试写在rbtree_test.c中，由于无法触发时钟中断，只能人为的使用sched进行中断，并进行timer的更新

### proc新增

可在proc.h中看新增的属性

### RT系列的初始化

proc.c中RT开头的便是新增的初始化函数

### 调度队列

改为多个cpu独自享有一个调度队列，对rq和rqlock做了一些修改

### 调度策略

目前使用的是RMS

## 12.12 新增

### CR资源

加了一下CR资源，在想怎么加入到测试中，测试优先级反转的问题，可能需要先实现简单的fork，否则单核上没有等待

### EDF实现

简单修改了一下priority以及Inschedtime_handler中的更新逻辑，支持EDF调度，可抢占了。


### 后续

实现一个简单的多重反馈队列，RT优先级可离散化到0到20之间。完成优先级反转的测试及使用相关算法(Ceiling和继承)

## RMS新增 12.15

### fork和vm的deep_copy

由于要测试优先级，所以需要在多核上运行，由于调度队列是单独的，所以尝试使用fork，写了下发现不行，页表错误，感觉debug要很久随放弃，采用了更简单的实现方法：

简单修改一下start_proc函数，让其允许传入cpu id参数以决定在哪个cpu上启动(


fork在proc.c中，deep_copy_vm在pt.c中

## 12.16 新增

### 简单的CR实现以及Ceiling实现


## 12.18 新增

多重反馈队列和RMS(因为EDF的优先级是动态的，使用多重队列毫无意义)

后续再做的话就是优化一下队列吧，因为现在还是需要每个时间片去遍历所有进程去更新时间，可以引入一个lazy标签来优化。