在阅读并实现lab4 chapter1(https://rcore-os.github.io/rCore_tutorial_doc/chapter4/part1.html)的时候,关于内存初始化我有一个困惑,
for i in (1..(self.m << 1)) { self.a[i] = 1; }
for i in (1..self.n) { self.a[self.m + i] = 0; }
for i in (1..self.m).rev() { self.a[i] = self.a[i << 1] & self.a[(i << 1) | 1]; }
第一行先把整颗完全二叉树初始化;
第二行把叶节点置为可用;
第三行bottom-up逐层更新。
这里可看到,n的语义是total number,m语义是最下一层最左边的那个叶节点。
我的问题来自第二行,range from 1 to n。两个疑虑,第一个是它不从最左边的那个节点开始mark,它从m的右兄弟开始更新。因为 m必为二的幂次(偶数),m+1必为奇数,在以1为根的完全二叉树中,奇数为右子树。
第二个疑虑就是这样只能拍下 n-1个数,假如我真的进来一个二的幂次,这样会有一个page提前不可用。
这是与 self.offet = l-1 想配合的。我在想,假如
self.offset = l;
...
for i in (0..self.n) { self.a[self.m + i] = 0; }
会不会更好理解,更能排满一些