Ch3 多道程序与分时多任务

但是貌似很神奇的就是，他说的那个TaskContext我感觉他和本质上app是一一对应的，那他就能作为全局变量，甚至于能被多harts共享，并且我发现如果是这样的话，那之前的kernel stack我认为是和harts一一对应的貌似也需要改变，kernel stack貌似也是和app一一对应，但是其实如果app的数量是不定的，那上面说的TaskContext和kernel stack我认为可以实现成一个pool之类的东西，然后每次新开启一个app就分配一个TaskContext和kernel stack出来，然后pool当然会空和满，并且在app结束之后，他可以被回收（我看评论区说这在第五章才出现）

然后我感觉他的switch函数的思想很有意思，他只保存了被调用者保存寄存器+sp，这是因为在另一个app（进程）调用switch函数的时候，调用者保存寄存器已经在他的栈上了，相当于是这个进程睡了一觉，中途借出了被调用者保存寄存器，啊我感觉这就是操作系统比较吸引我的地方，最近在玩传送门2，这个人物切换就很有传送门的感觉

然后另一种理解就是，保存然后切换callee saved的寄存器，相当于是破坏了函数调用约定，因为你不仅没有让callee saved不变，还让他全部改变了

然后看评论区，有个人提出了多个应用程序共享同一个内核栈的想法，然后给了一个链接，有点没看懂，但是打算在第四章去看，貌似也是在栈上放了一个指针map指向不同的空间，当然我还是觉得每个app一个内核栈比较省心

然后就是分配和回收的问题，既然都说了第五章会去实现回收，那我在这里就不做这个工作了，我就单纯的弄一个Max_app_num个内存栈，同样大小的TaskContext，就是一个app一一对应一个，并且需要用const assert确保harts数量要比Max_app_num小，不然某些hart会分配不到栈

我捋一下思路：首先所有harts启动并根据hartid进行栈分配，然后load_as_trap_stack并load（初始化trap kernel stack），然后初始化TaskManager，然后分别进入app（run_next_app）执行，现在比如说有8个harts，12个程序，然后8个程序就在并行执行，这时某个程序调用yield系统调用主动舍弃cpu资源，相应的harts首先去TaskManger中找有无在休眠的app，此时很明显没有，于是对应的hart开始初始化一个游离的trap kernel stack，初始化TaskManger的对应项，然后保存TaskManger，然后直接run_next_app，从而将这个进程休眠，与此同时，可能某个程序也调用了yield，此时他就能发现存在某个休眠的程序，于是他就调用switch，做进程切换，直到所有程序全部执行完毕，

但是我发现下一章节才描述了这一过程

3.多道程序与协作式调度

多内核栈

第二章其实我已经有维护应用运行的状态了，不过仅仅只有完成或者未完成两种状态，所以可以进行状态的扩展

他的做法和我上面自己推导的有一个小小的区别，就是他会在一开始把所有的app的TaskContext都初始化好，这样在yield的时候就不会存在没有初始化的app了，即所有app都是在等待的状态，这其实很有道理

这个TaskManager的结构有点不太好确定，首先是一个num_app这个反正是不变的，所以call once初始化就好，然后就是每个Block了，每个Block肯定也是对应着每个app的，他里面有一个状态，有一个TaskContext，现在就是想需不需要给它们加锁

假设两个yield同时发生，然后也正好还剩下两个ready的app在Task里面，如果仅仅是同样的find，他们肯定返回同一个ready的位置，并期望同时修改他的状态，同时切换过去，那肯定会出问题，感觉主要就是这个状态需要加锁，想想，如果是他是atomic，仅仅只是让同时读取时进行同步，他们依然会认为他是ready的，最好的需求就是，读取发现是ready，立马禁止所有其他的读取，然后修改他为runing，然后返回这个id，这个就是锁，而且是Mutex不是RwLock，然后就是TaskContext，emmm，貌似不需要锁，他的atomic有一个fetch_update的函数，这个函数会先获取他的状态，然后应用你给的函数，比如判断是否是ready，然后进行CAS（compare and swap），即他会再次load他的状态并比较是否和之前的相同，如果相同他才会将你函数的返回值写入，否则就一直循环你这个过程，直到你函数返回None或者写入成功，然后他算是无锁并发中的一种，这也可以成功handle上述举的例子，然后假如有三个yield同时发生，会有一个全部修改失败，然后找不到ready的，于是他应该直接恢复当前app（或者检查是否有uninit的，如果有就做init并启动）

然后就是TaskContext需要什么包裹，按理来说的话，在修改TaskContext之前，必然需要使用find来找到一个ready，然后用这个index去读取对应的context，然后修改自己的context，但是这其实依赖了这个行为，但是这个依赖并没有语言的保证，意味着容易使用错误的index，但是感觉其实没必要做一些其他的工作损失性能，仅仅让他只能被一个函数访问就可以了

这个确定之后，就是整个trap过程，首先fast trap只会保存一些a，t之类的寄存器，然后进入yield syscall处理函数，但是这个其实是需要陷入完整路径函数的，于是保存所有通用寄存器（除gp），进入真正的处理函数之后，保存task context，并恢复新的task context，即switch函数实现换栈，switch函数返回依然可以再恢复用户态的所有寄存器

然后大概有三个地方会启动程序运行

首先就是一开始的时候，所有harts启动他们的第一个程序运行
然后就是yield的时候，切换程序运行
之后就是出现不可恢复异常的时候或者调用exit的时候，需要启动一个新程序运行

所以我要TaskManager提供几个方法suspend_current_and_run_next ，exit_current_and_run_next，run_next_at_boot，run_next_at_trap，前两个内部都会调用最后一个，最后一个内部会调用_switch，去寻找一个ready的并切换

所以本质上就是后两个函数，首先实现第一个，第一个要做的就是首先确定要运行的程序，然后依然是可以使用find，来找到一个ready的程序然后返回，有app_id，就可以初始化hart local的app_info，然后可以初始化user stack，可以初始化sepc，stvec，sstatus，然后sret

然后就是第二个函数，首先也是find找到下一个需要ready的程序，然后调用switch，这其实要求是把所有上下文全部保存在flowContext里面，这样才能在切换之后恢复比如说sepc之类的东西

然后要注意的点是switch函数不能被标记为naked，因为我们依赖编译器帮我们保存一些caller saved reg

感觉大脑里需要有三个图，第一个图是当前在cpu里面的寄存器的图，包括gpr，csr等等，然后想象sp的箭头指向第二图，kernel stack图，他上面是hart context，下面是trap_context，然后第三个就是task context的图，实际上他本质上就是在trap时用taskcontext换掉trap的gpr，并设置新的csr，然后此时sp自然就会指向新的kernel stack，然后最后恢复再用flowcontext换掉user的gpr，实现狸猫换太子，然后换掉之后会出现，新的kernel stack的hart context的某些值也需要换新，比如说app info这些就不说了，最主要的是hartid需要换新，我之前把tp寄存器设置为指向了原来kernel stack，于是在换掉之后他依然指向原来kernel stack，所以可以拿出tp的值里面的hartid，然后设置新的kernel stack的hartid，但是又有一个新问题，我如何知道新的kernel stack的hartcontext的位置呢？能否在taskcontext里面新加一个tp的位置，在switch之后依然能成功获得hartcontext

所以基本分为

task gpr恢复（此时换新kernel stack）
新hart context初始化
设置新的sepc，sscratch（即user stack）
flowcontext的恢复

然后就整个换新了

但是我发现我的代码貌似还有bug，具体来说是我的每一个hart一开始是用hartid来选一个kernel stack，但是kernel stack原本的设计是和app id一一对应的，这会导致可能一开始3号hart用了3号kernel stack，运行了4号app，但是在init的时候，3号app的task context中的sp是指向3号kernel stack的，所以只要有人切换到一开始的3号，那就会存在两个hart在同一个kernel stack里面，不过这里可能并没有问题其实，怎么说呢，由于她们是顺序选app的，所以app一定会被顺序选到，即8个hart必定选到前8个app，这样前8个app的task context其实是无效的，假设之前的4号app yield了，此时他会把4号的taskcontext的sp记录指向3号，之后切换到4号app的时候，他都会用3号kernel stack，所以他们在一开始实际上却是也是一一绑定的，只是不是序号一一对应，脑子里想一个图，最上面是8hart，中间是10个app的task context，下面是15个kernel stack，所以这个bug应该不存在，并且他依赖我的find是顺序find，因为本质上他最后会更新一一对应的关系

然后对于退出当前应用运行下一个应用，完全可以在fast-trap做处理，只要最后恢复整个flowcontext就可以

不过话说为啥需要这么复杂，我忽然有点忘记为啥需要多个内核栈了，为啥不能在yield的时候直接替换hartcontext。然后设置sepc即可

确实是不需要多个内核栈，我用fast trap的这个栈结构可以弄一个更优雅的方式

单内核栈

md写了两天的多内核栈，突然怀疑一开始的动机了，然后发现单内核栈是低复杂度并且性能更高的解法（他不需要做task context的切换）

具体来说，就是首先把hartContext中app相关的东西拿出来，抽象出一个app context（包括flowContext和一些app info），然后严格遵循一个hart对应一个kernel stack，一个hart对应一个hartcontext，一个hart对应一个trapcontext，一个app对应一个app context，一个app对应一个task control block

明确上述的对应关系之后，当一个hart find一个app去执行的时候，如果找到了，就意味着他和一个app做了绑定，这个绑定体现在kernel stack中的trap context，可以保存对应flow context的指针，flow context在app context里面，意味着能找到app info，那就能知道app id，知道app id就能得到task control block，但是其实我可以把这三者全部放一起，因为他们都是和app一一对应的

然后我想让task control block（tcb）包含task status，flow context，app info等信息，然后希望能把他做成可以分配的，但是这意味着还需要回收，还是有点麻烦的，于是我打算先暂时硬编码，用下标代表app id

写出来之后运行发现出现诡异错误（smp为1的时候出现异常指令），难受了一整天，打了一整天的游戏，然后第二天发现估计是爆栈了，我发现很诡异，不太像是爆栈，但是增加了栈大小确实又没问题了，就无比的诡异，好吧，确实是爆栈，我watch了一下，确实爆了

然后竟然smp=1的时候一次过了，虽然貌似每次yield的时候都选到了同一个，因为我是从头开始找的，把它标记为ready之后再找肯定还是找到他自己

所以我设计了一个优先级系统，就是如果切换的时候，会把自己的优先级标为low，然后去选择的时候，就没有那么大概率的选到自己，然后如果选到的不是自己，就会在之后把它变成high优先级的ready，这就可以实现不断的切换

但是之后出现了一个有意思的并发问题，就是这个如果不是选到自己，就把他的优先级改成ready high，这会修改他的状态，如果别人选择到他了，把它改成了running，那就会覆盖他的running，解决方法就是，在改成ready high的时候用cas，不过我感觉其实所有的原子store都应该变成cas（暴论）不过从running变成其他的状态倒是也不需要cas

然后成功了，有一个奇怪的地方，我xtask记录了每次qemu运行的时间，我发现不管我smp 1-8，运行时间几乎没有什么区别

4.分时多任务系统与抢占式调度

一开始挺顺利的，但是只是开多核，就有一个应用程序会panic，他panic的位置很有意思，是在一个console的位置，这有点引起我的注意

诶不对，我悟了，我现在每次遇到这种很难受的bug，我就开始摆烂，然后赖床睡觉，打游戏，然后再重新来看，就一瞬间知道问题在哪了：我的sys exit这个syscall的实现是在exit中换context，这时，exit本来不应该存在返回值的，但是我现在把exit的返回值也赋值给a0了，但是现在的这个a0不是原来的a0了，是已经换掉的新的context的a0，所以就不应该接受他的返回值

5.统计时间（练习）

扩展内核，能够统计每个应用执行后的完成时间：用户态完成时间和内核态完成时间。

之前第二章也有一个统计时间的练习，但是已经烂完了，所以正好修一下，我感觉他的每个练习都比较有意思

我感觉我的思路是第一次进入用户态时开始计时，重新回到内核态时停止计时，然后开始内核态的计时，在出内核态时停止内核态的计时开始用户态的计时，一直往复

我看一下他标答的思路，啊我忽然发现我忘记考虑任务切换了，他有一个停表的概念，我感觉还挺好用的，但是他的停表概念相当于只有一个api，他没有两者匹配的概念，就容易搞混，我打算弄一个新的类型，然后他只提供start和end的api，然后他会自动记录两个api统计之间的时间，然后我打算把这个类型就叫做停表stopwatch，然后他的内部会检查是否匹配，就类似于括号匹配，一个start必定对应一个end

6.支持浮点程序

** 编写浮点应用程序A，并扩展内核，支持面向浮点应用的正常切换与抢占。

浮点还有一些寄存器需要保存或许？我对于浮点部分完全不了解，我之前写cpu也没有写过浮点部分，所以我打算去学一下

感觉就是要把f0-f32全部保存，然后fcsr进行保存

但是写完之后一直报错，有点摸不着头脑，后来发现原来是fsd指令触发了异常指令异常，原来是sstatus中的FS需要是1才行

然后可以实现为，只有FS是dirty的时候才保存，然后恢复的时候，把FS变成clean

7.统计任务切换的开销

编写应用程序或扩展内核，能够统计任务切换的大致开销

不知道这是要我统计什么，摆了

8.内核态响应中断，并支持内核任务的抢占式切换

扩展内核，支持在内核态响应中断

这个感觉有点意思

中断三种，时钟，软，外部，需要响应哪些中断呢？貌似现在就一个时钟中断

然后关键点有两个

判断trap来自内核还是用户，通过读取sstatus的spp字段，这个字段是previous privilege的意思
如果是内核trap，在trap的开头和结尾不能换栈

既然不能换栈，还需要进行判断，就需要拿出一个额外的寄存器，我打算使用gp寄存器

不过貌似我如果不能换栈会有一些问题，我是在栈上放了一个指向上下文的指针，如果不换栈意味着会把之前的内核上下文覆盖掉之前的用户上下文，所以说其实trap要讲究空入空出，即每次trap，必须进入一个空的stack

lv1跳入lv0

嵌套trap那就意味着每次打开中断时都需要至少分配一个陷入栈，如果将用户的控制流称为lv0，第一次陷入的叫做lv1，然后之后的所有嵌套可以被叫做lv2，在boot前，kernel保证不会打开中断，然后他将当前使用的陷入栈放进sscratch，然后跳入lv0，之后跳回来，换栈，用户的栈进入sscratch，在开头和结尾都会有一个exchange，这没问题

lv1跳入lv2

准备跳入

lv1跳入lv2: 但是现在可能会存在lv1到lv2的跳入，幸好，这个时机我是可以掌控的（即sie的设置我是可以掌控的），于是，每次我需要打开sie的时候，我需要使用alloc分配一个free trap stack，保存当前用户栈到trap_context（开一个新的字段叫做psscratch），然后将新的stack load到sscratch中

没有跳入

如果没有中断之类的发生，到最后需要将psscratch换到sscracth，然后free掉这个stack

跳入但是返回相同的lv1

假如有中断发生，就会换入新的stack，此时他进入的fast_handler完全可以在我之前就设置为专门用来处理kernel trap的fast_handler版本，此时会保存之前kernel控制流的一些寄存器，然后进入一些简单的处理，然后从fast_handler返回，最终换栈，然后重新进入之前kernel控制流trap的那条指令执行，然后接上没有跳入的处理流程

跳入但是返回不同的lv1

这就很有意思了，也就是他练习的最后一个任务，扩展内核，支持在内核运行的任务（简称内核任务），并支持内核任务的抢占式切换。

暂时不去想这个，这个确实是有点棘手

lv2跳入lv2

即所谓的一直嵌套，即lv2->lv3->lv4等等，但是其实仔细想想，每次跳入前一定能保证，psscratch是之前的栈，这就像一个链表，你只要每次能返回到psscratch的栈上，就能一直嵌套，所以他们是自洽的，即你只需要知道一个链表的末尾即可，我如果有一个全局的管理器，我也只需要保存每个末尾即可

上述说的psscratch就是flow_context中的sp，但是还有一个部分也会使用这个sp，就是在任务切换的时候，任务切换会保存当前的sscratch到flow_context的sp，然后将切换的新进程的sp替换到sscratch，我在想，如果我在一开始就保存这个sscratch，然后每次在最后都从sp中拿sscratch恢复，会不会让整个过程变得更简单，因为如果我想在fast_trap就打开嵌套trap，那就意味着确实需要一开始就保存，然后我把嵌套trap做成一个feature

实现的时候有一个尴尬的事情是在哪里free掉这个设置的栈呢

我打算做一个fast_handler的wrap，来最终能捕获他的返回值，如果直接返回掉，就相当于要返回了，所以此时end，然后设置时间之类的事情

之后出了一些真的写的时候出现了一些问题，并且更改了一些思路，具体来说是

在开启了nested trap这个feature之后，会在一开始保存sepc和sscratch到pc和sp，然后在最后面恢复，这要求其中的所有操作不要直接操作sepc和sscratch，需要操作ctx中的pc和sp，然后添加一个trap end函数，他会在rust trap handler到汇编之间做一个桥梁，他会把nested trap准备的sscratch换成sp，然后drop掉分配的sscratch，然后做一个时间记录的操作，并且他会在这里做sscrathc和sepc的恢复（如果需要switch的话），这个考量是因为，所有的状态恢复应该在最后恢复，然后他应该和fastresult和entireresult绑定

然后确实很容易出现死锁的问题，具体体现在，如果在打印的时候nested trap，会导致console的锁造成死锁，所以在nested trap中不能打印，不能尝试拿锁

但是如果一直嵌套的话，容易一直在里面出不去，然后最后爆堆

9.简单阅读linux代码

旅行了一趟，花了2周多的时间，现在回来，很多东西都有些忘记了，所以打算先做这个任务，来复健一下

从文档推荐的entry.S开始

我直接丢给gemini帮我分析了

然后我注意到linux是使用的多内核栈的方式，我很疑惑于是去问ai，我才发现我之前的所有都想错了，单内核栈有一个最大的缺点，就是在内核中运行时没有办法切换用户程序，这或许会导致内核在disk read的时候需要很长时间，并且还没有办法释放cpu资源，因为只有一个内核栈，他必须要完成当前任务才能切换

但是我实现了nested trap，但是nested trap是为了解决kernel本身的一些异常不能在kernel进行的时候做切换

所以我在想，在kernel中由于其他任务而切换到其他应用程序的唯一方法貌似就是换栈

构想：

在yield的时候，内核不会被因为切换任务打断（因为本上内核就在做切换的事情）内核在换完flow context指针之后，直接load新的flow context到gpr然后普通的sret就好，只是如果内核在做不是切换任务的工作时（比如其他sysycall）需要切换的时候，那就只能换栈，因为需要保存其他工作的上下文

之后对我现在的进度来说，我应该去看一眼linux的栈结构，于是我问了gemini

linux和我的栈结构比较相似，只是我的参考了fast-trap的结构，但是我们的tp都指向task control block/task struct

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28