// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc(). (The exception is when
// initializing the allocator; see kinit above.)
void
kfree(void *pa)
{
struct run *r;
if(((uint64)pa % PGSIZE) != 0 || (char*)pa < kernel_end || (uint64)pa >= PHYSTOP)
panic("kfree");
// Fill with junk to catch dangling refs.
memset(pa, 1, PGSIZE);
r = (struct run*)pa;
acquire(&kmem.lock);
r->next = kmem.freelist;
kmem.freelist = r;
kmem.npage++;
release(&kmem.lock);
}
// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void)
{
struct run *r;
acquire(&kmem.lock);
r = kmem.freelist;
if(r) {
kmem.freelist = r->next;
kmem.npage--;
}
release(&kmem.lock);
if(r)
memset((char*)r, 5, PGSIZE); // fill with junk
return (void*)r;
}
// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void)
{
struct run *r;
acquire(&kmem.lock);
r = kmem.freelist;
if(r) {
kmem.freelist = r->next;
// 这里必然是初次分配，所以减少空闲页数，并设置引用计数为 1
kmem.freepages--;
kmem.refcnt[pa2index((uint64)r)] = 1;
}
release(&kmem.lock);
if(r)
memset((char*)r, 5, PGSIZE); // fill with junk
return (void*)r;
}
kfree
kfree() 负责释放物理内存。
这里不再直接无脑回收到 freelist：
根据物理地址拿到 idx；
检查 refcnt[idx] >= 1，否则 panic（说明逻辑有 bug）；
refcnt[idx]--；
如果减完后仍 > 0，说明还有别的 PTE 在用这页，直接返回，不真正回收；
只有减到 0 时，才把这页挂回 freelist，并 freepages++。
// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc(). (The exception is when
// initializing the allocator; see kinit above.)
void
kfree(void *pa)
{
struct run *r;
if(((uint64)pa % PGSIZE) != 0 || (char*)pa < kernel_end || (uint64)pa >= PHYSTOP)
panic("kfree");
// 首先解析物理地址，并转换为 refcnt 索引
uint64 addr = (uint64)pa;
int idx = pa2index(addr);
// 获取锁，并检查引用计数是否大于 0
// 若引用计数小于 1，则 panic
// 若引用计数大于 0，则递减引用计数，并返回
// 若引用计数等于 0，则说明这是最后一次引用，可以真正释放物理页，填充垃圾值，并重新挂回 freelist
acquire(&kmem.lock);
if(kmem.refcnt[idx] < 1)
panic("kfree");
kmem.refcnt[idx]--;
if(kmem.refcnt[idx] > 0){
release(&kmem.lock);
return;
}
// Fill with junk to catch dangling refs.
memset(pa, 1, PGSIZE);
r = (struct run*)pa;
r->next = kmem.freelist;
kmem.freelist = r;
kmem.freepages++;
release(&kmem.lock);
}
hart 0 init done
Starting test program: test_mem_cow
Target type: COW
init: starting test_mem_cow
testing output size:539, contents:
Testing Copy-on-Write
Initial physical pages: 43
Physical pages after initialization: 44 (should be +1)
PhPhysical pages afteysical pages after fork: 57
Physicalr fork: 56
pages before child read: 57
Child read sum: 522240
Physical pages after child read: 57 (should be same)
Physical pages after child write: 58 (should be increased)
wait status:0
Parent read sum: 522240
Physical pages after child exit: 44 (should be same as before read)
Physical pages after parent write: 44 (should be same)
Copy-on-Write Test Completed Successfully
init: process pid=2 exited
init: test execution completed, starting judger
Judger: Starting evaluation
Test1 output:
Testing Copy-on-Write
Initial physical pages: 43
Physical pages after initialization: 44 (should be +1)
PhPhysical pages afteysical pages after fork: 57
Physicalr fork: 56
pages before child read: 57
Child read sum: 522240
Physical pages after child read: 57 (should be same)
Physical pages after child write: 58 (should be increased)
wait status:0
Parent read sum: 522240
Physical pages after child exit: 44 (should be same as before read)
Physical pages after parent write: 44 (should be same)
Copy-on-Write Test Completed Successfully
TEST 1 PASSED
SCORE: 1
init: judger completed
LAZY
make run_test TYPE=LAZY
得到输出：
hart 0 init done
Starting test program: test_mem_lazy_allocation
Target type: Lazy Allocation
init: starting test_mem_lazy_allocation
testing output size:309, contents:
Testing Lazy Allocation
Initial physical pages: 43
Physical pages after sbrk: 43 (should be same as initial)
Physical pages after first access: 44 (should be +1)
Physical pages after mid access: 45 (should be +2)
Physical pages after last access: 46 (should be +3)
Lazy Allocation Test Completed Successfully
init: process pid=2 exited
init: test execution completed, starting judger
Judger: Starting evaluation
Test2 output:
Testing Lazy Allocation
Initial physical pages: 43
Physical pages after sbrk: 43 (should be same as initial)
Physical pages after first access: 44 (should be +1)
Physical pages after mid access: 45 (should be +2)
Physical pages after last access: 46 (should be +3)
Lazy Allocation Test Completed Successfully
TEST 2 PASSED
SCORE: 1
init: judger completed
// kernel/include/proc.h
struct proc {
// ...
#ifdef SCHEDULER_RR
int timeslice;
int slice_remaining;
#endif
#ifdef SCHEDULER_PRIORITY
int priority;
#endif
#ifdef SCHEDULER_MLFQ
int priority;
int ticks_used;
int eval_ticks;
int cpu_ticks;
int sleep_ticks;
int base_priority;
#endif
// ...
};
// in usertrap()
// give up the CPU if this is a timer interrupt.
if(which_dev == 2)
yield();
// in kerneltrap()
// give up the CPU if this is a timer interrupt.
if(which_dev == 2 && myproc() != 0 && myproc()->state == RUNNING) {
yield();
}
因此，最终的输出可以如下所示（但实现不同具体的数也可能不同，助教文档里要求最高优先级的 I/O 密集型进程（P2）应最先完成，而最低优先级的 CPU 密集型进程（P1）应最后完成）：
Testing MLFQ Scheduler - Basic
MLFQ Scheduler Process 2 with initial priority 1 and final priority 1 completed
MLFQ Scheduler Process 5 with initial priority 3 and final priority 1 completed
MLFQ Scheduler Process 4 with initial priority 5 and final priority 1 completed
MLFQ Scheduler Process 3 with initial priority 2 and final priority 20 completed
MLFQ Scheduler Process 1 with initial priority 10 and final priority 20 completed
MLFQ with Priorities Test Completed
fstat 系统调用本身没有啥变化，不过测试样例是在 Linux 标准下编译的，所以它的 struct stat 和 xv6-k210 现有的有些出入。
这里只需要仿照 Linux 的标准，增加一个 kstat 结构体即可，然后基本上也就是按照字面意思填填字段就行了：
// kernel/include/stat.h
struct kstat {
uint64 st_dev;
uint64 st_ino;
uint st_mode;
uint32 st_nlink;
uint32 st_uid;
uint32 st_gid;
uint64 st_rdev;
unsigned long __pad;
long int st_size;
uint32 st_blksize;
int __pad2;
uint64 st_blocks;
long st_atime_sec;
long st_atime_nsec;
long st_mtime_sec;
long st_mtime_nsec;
long st_ctime_sec;
long st_ctime_nsec;
unsigned __unused[2];
};
// Per-process state
struct proc {
struct spinlock lock;
// p->lock must be held when using these:
enum procstate state; // Process state
struct proc *parent; // Parent process
void *chan; // If non-zero, sleeping on chan
int killed; // If non-zero, have been killed
int xstate; // Exit status to be returned to parent's wait
int pid; // Process ID
// these are private to the process, so p->lock need not be held.
uint64 kstack; // Virtual address of kernel stack
uint64 sz; // Size of process memory (bytes)
pagetable_t pagetable; // User page table
pagetable_t kpagetable; // Kernel page table
struct trapframe *trapframe; // data page for trampoline.S
struct context context; // swtch() here to run process
struct file *ofile[NOFILE]; // Open files
struct dirent *cwd; // Current directory
char name[16]; // Process name (debugging)
int tmask; // trace mask
};
// 页表操作 API
int mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm);
void vmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free);
pte_t *walk(pagetable_t pagetable, uint64 va, int alloc);
mappages 是一个更底层的映射函数，它将一段给定的虚拟地址 va 映射到一段给定的物理地址 pa。它不负责分配物理内存，只负责在页表中建立映射关系。
hart 0 init done
// 前略
init: starting sh
========== START test_wait ==========
This is child process
wait child success.
wstatus: 0
========== END test_wait ==========
init: starting sh
========== START test_waitpid ==========
This is child process
waitpid successfully.
wstatus: 3
========== END test_waitpid ==========
init: starting sh
========== START test_clone ==========
Child says successfully!
clone process successfully.
pid:12
========== END test_clone ==========
init: starting sh
========== START test_fork ==========
child process.
parent process. wstatus:0
========== END test_fork ==========
init: starting sh
========== START test_execve ==========
I am test_echo.
execve success.
========== END main ==========
init: starting sh
========== START test_getppid ==========
getppid success. ppid : 1
========== END test_getppid ==========
init: starting sh
========== START test_exit ==========
exit OK.
========== END test_exit ==========
init: starting sh
========== START test_yield ==========
I am child process: I am child process: 21. iteration 1.
I am child process: 22. iteration 2.
20. iteration 0.
I am child process: 21. iteration 1.
I am child process: 20. iteration 0.
I am child process: 21. iteration 1.
I am child process: 22. iteration 2.
I am child process: 20. iteration 0.
I am child process: 21. iteration 1.
I am child process: 22. iteration 2.
I am child process: 21. iteration 1.
I am child process: 22. iteration 2.
I am child process: 20. iteration 0.
I am child process: 22. iteration 2.
I am child process: 20. iteration 0.
========== END test_yield ==========
init: starting sh
========== START test_gettimeofday ==========
gettimeofday success.
start:836, end:911
interval: 75
========== END test_gettimeofday ==========
init: starting sh
========== START test_sleep ==========
sleep success.
========== END test_sleep ==========
// 用于 sys_times 系统调用所定义的结构体
// ref: https://man7.org/linux/man-pages/man2/times.2.html
struct tms {
long tms_utime; // 用户态时间，user time
long tms_stime; // 系统态时间，system time
long tms_cutime; // 子进程用户态时间，child user time
long tms_cstime; // 子进程系统态时间，child system time
};
Form Closure（形闭合）：这是一种纯粹基于几何的定义。指的是接触点（contact points）形成了一个 “笼子”，将物体完全包住。在不移动接触点的情况下，物体从几何上无法从这个 “笼子” 中逃逸。可以认为这是一种最理想、最稳固的包裹式抓取接触状态。其不依赖于摩擦力。
Force Closure（力闭合）：这个概念考虑了接触点的力和摩擦力。它指的是，虽然接触点可能没有形成几何上的 “笼子”，但通过在这些接触点上施加适当的力（利用摩擦力），可以抵抗施加在物体上的任意方向的力（force）和力矩（torque）。换句话说，只要夹爪（或手指）能提供足够大的力，理论上就能抵抗任何外来的扰动，或者能让物体产生任意方向的加速度和角加速度。其依赖于摩擦力。
而如果对于某一旋转表达方式，存在这种 Ground Truth 监督信号的跳变，神经网络为了拟合这种跳变点，就会导致其权重矩阵 $W$ 出现一些很大的参数，造成数值不稳定性的同时，为之消耗大量的注意力，大部分的训练过程都去拟合这种跳变而不是其他占比更多、更泛用的部分，这是非常不好的。并且这一过程是 Loss 无关的，是由于选择了不好的表达方式造成的本质性问题。
$$
\begin{aligned}
w &= \frac{\sqrt{\text{tr}(R)+1}}{2} \
x &= \frac{R_{32}-R_{23}}{4w} \
y &= \frac{R_{13}-R_{31}}{4w} \
z &= \frac{R_{21}-R_{12}}{4w}
\end{aligned}
$$
