一些构想

内存的虚拟化，cpu的虚拟化，程序的分段，加载，动态链接，状态机的执行，从我们在文本编辑器中按照一定的语义敲下一些ascii字符，到执行时的转化为状态机变化。（环境变量，path，应用程序是什么）
剥离一些外围知识后，纯粹的编程语言是什么（cs61a），在那种抽象模型下解释java，纯粹的java是什么，再补充java的细节。最后简短的介绍python。
静态调度，动态调度，多线程的三个问题，解决方案，锁是什么，如何实现，锁-条件变量-信号量-生产者消费者（互斥与同步），最后从并发到IO多路复用，如何理解java的多线程中相关概念。
介绍MYsql的相关概念
前面处理了c代码从文本到程序执行的全过程，进一步梳理java代码的从文本到执行的全过程

other

tmux ： https://www.ruanyifeng.com/blog/2019/10/tmux.html
Ctrl+b %：划分左右两个窗格。
Ctrl+b "：划分上下两个窗格。

Project N

M1 pstree

常用系统命令：https://www.cyberciti.biz/tips/top-linux-monitoring-tools.html
语言的问题：csapp中，大量的时间被花费来阅读理解我们需要干什么上了。
目的：
实现pstree命令、附带 -v -p -n 三个选项及之间的组合、
20241104：
是在不想干，那就先实现-v 参数的内容，从简单的做起。too easy, 好过在家打游戏到11点。不过忘了之前的多窗口管理与linux的可视化。
不去主动安排时间，就会被时间安排！
今晚至少没有打游戏，great，明天呢？
1.完善参数解析。标记位：v，p，n; done.
2.git 管理代码 stupid conten tracer… haha
3.c语言，实现一个树状结构 done
4.获取进程id，及parent，塞进树里。done
其他：对树状结构读取并输出。
20241105:
明日：
1.进一步明确树的结构，是否真的需要link 不需要
2.树结构的排序
3.进程填满树 done
4.makefile 文件
5.h 头文件 done
20241106:
明日： Critical 将进程信息正确的放到树中，我需要了解下c语言版本的数据结构。这是一个纯oj题。
//一些奇怪的待查明的东西：
```
while((entry = readdir(dir))!= NULL) {
  if (entry -> d_type == DT_DIR) {
      if (entry -> d_name[0] >= '0' && entry -> d_name[0] <='9') {
        //获取内部结构相关内容
        FILE *fp;
        char line[256];
        char ppid_s[8];
        char name[128];
        char path[128];
        char *pid_s = entry ->d_name;

        for (int i = 0; i < strlen(path); i++) {
          path[i]= '\0';
        }
        strcat(path, "/proc/");
        strcat(path, pid_s);
        strcat(path, "/status");

        fp = fopen(path, "r");
        while (fgets(line, sizeof(line), fp) != NULL)
        {
          if (strncmp(line, "Name:", 5) == 0) {
            sscanf(line, "Name:   %s", name);
          }
          if (strncmp(line, "PPid:", 5) == 0) {
            sscanf(line, "PPid:   %s", ppid_s);
            break;
          }
        }
        pid_t pid = atoi(pid_s);
        pid_t ppid = atoi(ppid_s);
        char *pname = (char *)malloc(sizeof(char) *128);
        strcpy(pname, name);
        process *cur = create_process(pid, pname);
        insert_tree(root, cur, ppid);

        fclose(fp);

      }
  }
}
```
path变量 stack 中？不会在每次循环时重新建立？
c语言中声明数组时需要额外初始化吗？还是声明的时候就已经初始化了？
Ouch, 24-11-10 19:18，终于初步完成pstree，淦！完全不想再去弄第二个实验了，第二周的课程也不想去完成了。

L0

什么是abstructmachine？今晚需要完成到什么程度？现在没什么状态。回家洗个澡再战（即使房间里几乎没有效率哭）
–很明显，没有再战。
首先需要我们理解AbstractMachine，并在其环境中实现一些库函数。然后在这个环境中开始我们的小game。
20241122:12.18 great 总算跑起来了，能看到一个图形界面。
20241124:16.30 总算实现了画面的移动。不过完全没理解absmachine的图形输出。puts 倒是可以输出字符串。

M2

start 创建并开始执行、wait 类似join、yield切换。main函数的执行也是一个协程。
状态机：指令+状态
1.如何在程序中实现状态的保存（有哪些状态，如何保存，如何恢复）
2.如何在程序中实现指令的追踪
哪些状态：stack + 寄存器（被调用者保存的寄存器）
指令追踪：%rip
直接保存寄存器！
20241203 ：1.setjmp/longjmp & GDB 调试；2.abstractmachine 的stack_switch_call (x86.h)；3.GCC-Inline-Assembly-HOWTO；4.c inline；5.ABI 对对齐的要求；
20241214，上述除了第五点都做完了，可是实验进度为0…
Step1:以当前的背景知识，尽可能的细化分解。
1.已文档中示例作结构
2.co_start
1.分配空间，初始化结构体
2.需要一个容器，保存所有的结构体
3.新创建的协程不会立即执行，而是调用 co_start 的协程继续执行，调用start的协程如何表示？何时被初始化？它的状态机模型是什么？
3.co_wait
1.判断目标协程的状态：
CO_DEAD：free。什么情况下状态会流转到 dead？
OTHER：什么都不做，yield
2.main main函数天然的属于一个协程？如何实现
4.co_yield
5.如何将main函数与协程体系结合起来？
1.main中调用了wait后，如何确保main函数还是有可能继续被执行？ – main = 协程，wait中yield后，main依旧保留在协程数组中，后续还是可能继续被执行。
2.因为mian是协程，那么main的co结构体何时被创建呢？ –main可以被默认初始化，或第一次调用start时初始化。
6.状态流转：
1.创建后：CO_NEW
2.调用stack_switch_call第一次执行后：CO_RUNNING
3.调用wait后：CO_WAITING
4.程序执行结束后：CO_DEAD – 如何判断程序执行结束？maybe debug
Step2:just do it！
1.init main协程，放在第一次调用create的时候。
2.完成start 操作, 仅仅初始化结构体
3.实现wait操作
4.全文最重要的操作了：yield的实现！ 12.05 吃个饭
20241214:迈出了重要的一步：神秘的Segmentation Fault ！还好实验手册有提及（指引的重要性！）

16.01 今天先溜了。ABI对齐与查看编译出的的汇编代码。gcc -I.. -m64 -Werror -g newtest.c ../co.c -DLOCAL_MACHINE
fuck，15日15.19，终于简单的调试正确了！ABI关于对齐的相关要求没有弄出个所以然，大概理解为调用内核的相关方法时要求16字节对齐。一路不停的调试源码，最终如提示所言，segment fault 时 rsp指针没有对齐，也如提示所言，调用call前是对齐的，call之后就不对齐了！更如提示所言需要深入理解stack_switch_call!报错时rsp指针多了8个字节，故传参时-8字节，而原因则非常简单：call调用方法时需要8字节的空间存储返回时地址！！！故调用stack_switch_call 时的rsp 指针不能16字节对齐，需要多出来8字节！fuck！debug了快3小时。
虽然没有报错了，可测试程序只输出了a，没有输出b,即我们的切换失败了…
一番鼓捣，成功实现了切换，现在的麻烦在于，如何在方法运行结束时将状态更新为dead？
18.54 现在的问题是返回值。
todo：
1. 返回值与stack frame。 2. 在我们的整个协程体系，画出stack frame图！哪些是骚操作在一个frame里面用我们自己的stack调来调去？哪些是老老实实开了一个新的stack frame？
16日，终于可以返回了，但返回后执行就报错了。也没有理解返回后的汇编代码。去保存寄存器的思路可能有问题，难道需要手动汇编，保存所有的call save寄存器？状态机，interesting！
17日：fuck！fuck！终于初步调试通了！hard，worth！

1218:试了下测试样例，手动编译可以正常，make test 就会段错误…

1219:still fuck！没想到最后如此简单…
之前陷入到callee saved 寄存器的坑里去了。两个薄弱点：寄存器 & 寄存器地址指向的值，stack frame结构！最后竟然如此简单！！！陷了十几个小时的坑！
1223:以为结束了吗？NO，直至今日还在处理问题。现在一个非常麻烦的点在于：main yield执行第一个协程后，在第一个协程的方法中yield执行第二个协程时，此时switch方法的rsp指针如何设置？

co_wait 有一点挑战。不考虑资源回收，两个测试用例已经可以正常调通了。这里的资源回收应该要参考常见的垃圾回收机制。需要维持一个图。
1224:64位的通了后，还需要额外了解32位。32位的堆栈结构。
1225:总是以为懂了，事实确是并不懂，以为64位没问题了，结果打开debug就报错…，32位也始终调不通。卡了很久，每次静下来画下stack 以执行流，总能有新的收获。需要一个指针，表明是那个coroutine调用了stack switch，这样方法返回时新的co_yield就能setjmp 保存到正确的协程里。这样资源回收也简单了。花了太多时间了，许多都是低效的垃圾时间，即使上班期间的几个小时完整时间段。后续需要参考其他的协程实现！
0101:核心在调度，64位的通了，32位的一直有问题，需要进一步了解32位的结构。tmd去掉debug 32位还是64位都没问题…不能再卡了，毕竟不是所有值得的事都必须要做好…给自己一个理由。

todo一个实验报告（总结）
补一下之前画的理解多个携程之间co_yield调用时的stack状态图。

L1 pmm

physical memory management
Absmachine 中在给出了heap.start~heap.end 一段可用的内存区域，我们需要实现kallooc & kfree函数
1. 对于大小为s的内存请求，实际分配 2^i^ 其中 2^i^ >= s。easy java参考hashmap中的实现
2. 没有足够的空间分配内存时，返回NULL 3. 直接拒绝超过16MB的请求 4. 无需强制初始化申请的空间，也可以初始化为0（how to do？） 5. 满足并发的请求 6. 性能优化-区间树？正确性与伸缩性 7. 实现klib
20240105 todo：
1.实验导读-框架&makefile 稍微详细的过了一遍，没太明白makefile的执行顺序。
2.框架执行 -need 实现printf
3.测试框架的搭建 -简单copy
next todo：
0.测试框架的实验 & printf的实现 & abs 再次导读
1.阅读书中关于内存管理的部分 0106-done
2.阅读csapp中关于内存管理的部分，尤其是伙伴系统
3.尝试设计本次实验中的内存管理数据结构

实验阅读材料

No.17
空闲列表= 任何堆上管理空闲空间的数据结构
1.首先介绍了在一块完整的内存空间上，进行内存分配与空闲列表在其上的具像。
2.管理空闲空间的策略：
最优、最差、首次、下次
分离空闲链表（https://www.grayxu.cn/2020/02/21/Slab/）
伙伴系统
other
glibc 的 malloc:https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/comment-page-1/

测试框架

如2025-02-04 所记录：
1.测试框架是否需要AM & Klib ？
2.测试框架的代码是否需要运行在qemu上？（是否需要生成镜像）
我们测试的对象是什么：pmm.c中的 kalloc 与 kfree，都是对从操作系统申请过来的一大批内存空间进行管理
好像并不能完全的抛开am与 klib 因为pmm中的初始化会用到heap，os中的代码会用到putch。
1.直接在我们test中的am.h 中添加上述依赖？
2.我们的项目也接入am？
在生成test可执行文件时也链接上am，会报错
```
/usr/bin/ld: /learn/os/os-workbench-2022/LAB/kernel/../abstract-machine/am/build/am-x86_64-qemu.a(trap64.o): relocation R_X86_64_32S against symbol `__am_panic_on_return' can not be used when making a PIE object; recompile with -fPIE
/usr/bin/ld: failed to set dynamic section sizes: bad value
```
最终解决方案
```
test: git
  gcc -no-pie $(shell find src/ -name "*.c") \
        $(shell find test/ -name "*.c") \
        -Iframework -Itest -DTEST -lpthread \
        -I$(AM_HOME)/am/include -DARCH_H=\"$(AM_HOME)/am/include/arch/$(ARCH).h\" \
        $(AM_HOME)/am/build/am-$(ARCH).a\
        -o build/test 
  @build/test
```
链接了AM，同时添加 -no-pie，管他呢，本地能运行…

todo：
还需要对框架进一步理解：为什么ARCH用的默认的，也可以运行，没有使用native，klib 是在哪里控制的呢？
1.因为原本的项目包含了klib，不包含stdio，test 则包含了stdio，没有klib
2.native 使用的glibc 而非klib 是在哪里控制？只看到了没有定义native才会生成相关替代方法。如何做到不生成替代就使用glibc？答案：似乎是包含了额外的platform.h文件。

实现

做了一堆的东西可就是没有正式的开始实验😂
在csapp中通过宏直接操作内存地址，构建空闲链表，实现分配，合并等操作，此次计划采取伙伴系统，同时简单一点，使用结构体而非直接的内存地址操作。
分配的时候我们可以不断的向小划分直至达到一个合适的块。并将划分的空闲块放入空闲列表。
难点在于释放时的合并：
1.如何确定当前空闲块的伙伴块？
有点fancy的算法：当前块的地址^大小 = 伙伴块地址。
2.合并时，需要将当前块&所有的伙伴块从空闲队列中移除。
伙伴系统需要内存对齐….
需要在test中对malloc分配的内存进行对齐…

20250210 22.20:这会儿可太高兴了，被一个问题卡住了，终于解决了，都准备今晚摆烂放弃了

在处理一下并发，完成任务近在咫尺！！！
在前面jyy，提到，数据结构没有问题的情况下，影响效率的最大问题一般在于锁的颗粒度。
一般建议，给每个cpu分配一段地址空间，但此时还没有理解thread-os，没有理解qemu及abs中关于cpu的部分。故现在还是所有cpu处理同一段地址空间。
1.free要不要加锁？
2.颗粒度控制在伙伴系统的层级还是伙伴系统的节点？如何实现？
首先需要分析，不加锁，kalloc与kfree有哪些问题：
空闲列表：
分配：
1.去空闲列表找：找到了就试着加锁，加锁成功才能用，失败就继续找？
2.不合适会涉及拆分，将会在不同层级空闲列表，新增：需要在层级加锁？不然节点丢失了。
释放：
1.找伙伴：这一步不必担心并发，因为伙伴都是唯一的
2.如果伙伴是空闲的，需要去对应层级空闲列表找伙伴，找到就移除：需要对前后节点加锁？
3.将合并后的节点放入对应层级空闲列表：也是需要对涉及的节点加锁。
对链表最细的操作就是在节点加锁，凡是涉及到节点的操作都加锁，锁太多影响效率？
还是每一层一把锁，读取&操作都需要先获取锁，颗粒度比方法层面细，也没那么麻烦。

M3:spref
```
strace --absolute-timestamps=format:unix,precision:ns ./a.out 
strace --relative-timestamps=us ./a.out 
strace -T ./a.out
strace --syscall-times=ns ./a.out
```
fork 与管道：
管道作为物理资源，创建后即使fork，也只存在一个，但文件描述符子进程会继承父进程的。
正则表达式的补充：
操作数+操作符
操作符：连接+或+闭包
闭包>连接>或
操作数：字符集
1.字符集的描述符：
· 表示任意字符
[] 表示括号内字符的任意一个
^ 匹配开头，后面跟 [] 则表示非
$ 匹配结尾
2.闭包的简写
+表示重复 1/n
？表示重复 0/1
{} 表示重复的具体次数/范围
3.转义
\
\s 任意空白字符
\t tab

转行

L2 kmt

概念：
idle线程，操作系统最低优先级线程，没有任务可调度时执行。
cte_init(os->trap) 指定了os->trap 是唯一的中断处理程序，所有处理器的中断都会调用该方法
简短的过了一遍，因为甚至都没有尝试去理解，还瞌睡了几次。
1.输出，大致的执行过程与相关函数的作用。
开启中断，注册中断处理程序，运行初始化，每个处理器运行run，然后被中断，此时系统变成中断处理程序。
2.调试os-thread，并理解absmachine下，的这一系列流程。
3.调试xv-6，理解xv6多线程的部分。
os->init 单处理器
os->run 每个处理器都会执行
带着疑问去调试thread-os，毕竟我们做的是加强版的thread-os:
1.cte_init干了什么？mpe_init有干了什么？
2.中断时absmachine干了什么？1.将寄存器保存到堆栈，2.执行os->trap，3.将os->trap返回的context加在进入寄存器
开始调试thread-os：
太久没有碰abs了，先-nb输出，这里又涉及到美化 Make file 导读
```
#!/bin/bash
make ARCH=x86_64-qemu
qemu-system-x86_64 -drive format=raw,file=build/threados-x86_64-qemu -s -S -nographic
```
```
target remote 127.0.0.1:1234
symbol-file build/threados-x86_64-qemu.elf
```
成功进行GDB调试
0.5成功了vscode调试，无法step进入absm的方法…
只能看汇编…
thread-os：
1.注册中断处理程序：跳到当前cpu的下一个task
2.初始化task
3.
boot 到 _start_c 到 main
最开始只有一个处理器，mpe_init 启动了其他处理器，其他cpu 都跳转到0x7c00，最终所有cpu都走到_start_c，主cpu已经将其他标记为ap cpu，其他cpu会跳转到各自的入口，然后xchg(&ap_ready, 1) 最终主cpu与ap cpu 都运行到user-entry。
然后cpu各自中断，调用同一个中断处理程序。不停的与task交互。线程级别的并发。自始至终系统只有一个地址空间。
更完整的流程：(这一部分更应该是属于对absm的理解)
1.固件将512字节加载到内存
2.0x7c00 开始执行boot程序（boot/start.S）
3.boot 会跳转到 load_kernel（boot的main.c将elf文件从磁盘加载进入内存，并设置entry（qemu的_start在qemu/strat.S））
4._strat会跳转到 _start_c, _start_c 初始化boot cpu 然后 stack_switch_call，切换stack，执行main函数
5.mpe_init：启动剩余cpu，均从0x7c00 ->_start -> _start_c ->__am_othercpu_entry -> 切换stack，交换ap_ready=1，调用user_entry (开启中断，然后中断)
6.所有cpu定时中断，调用__am_irq_handle，调用 user_handler
7.需要设置中断处理表IDT，中断发生后，cpu会依据中断号去查找对应的中断处理程序
现在我们已经投入了不少时间去理解abstruct machine，接下来开始理解并细化需求，同时找到并参考xv6的实现
注意：截止到目前，我们没有启动虚拟内存的相关部分，故此时所有cpu均是访问相同的地址空间。
1.整理中断与spinlock的关系？如何管理当前cpu的所有spinlock？
2.semaphore与中断的关系？sem需要有一个task的队列来管理哪些应该被唤醒
och，xv6没有线程！
task 应该有哪些内容？
20250418:我说注册怎么一个debug循环就报错：

申请了8个字节，调用next就跑到了0x5 哪儿去了…然后诡异的无限中断…

旧的问题刚去，新的问题又来？ debug是一种修行🫠
20250422:运行一段时间后就诡异重启，我放弃了… 似乎与context的保存有关系，rsp指针会运行一段时间后某次trap发生变化，然后某一次中断运行后就会重启… 还是先试着调试一下设备相关的代码

flag

todo： 2025年必须要完成剩下的L3与M4&M5

操作系统_实验记录

一些构想

other

Project N

M1 pstree

L0

M2

L1 pmm

实验阅读材料

测试框架

实现

M3:spref

L2 kmt

flag