Let's create something!

I. Page Table

1. Page table的作用

【简洁版】

• 隔离user process，给每个process分配4GB内存【假象，至于到底怎么分配，交给kernel】
• 提供 CPU 可识别的 physical address

【详细版】

• 在没有 page table 之前，processes 如果想在memory中执行，必须做好process isolation。一个方案是为每个process 分配一段“大小合适的”内存，这样的缺点是：
  • 首先，分配的内存必须连续；否则还需要 page table
  • 其次，多大才算“大小合适”，因为process在加载之前无法预知它会使用多少内存
• 另一种方案是：将内存划分成很小的“页”，按需使用；这样解决了“大小合适”的问题，但仍然存在内存必须连续的问题（否则会引起内存侵扰）
• 最后的方案是：page table。建立虚拟内存，对于32bit机器而言：
  • 给每个process的内存都是4GB[0x00000000~0xffffffff]
  • 同时kernel在每个processz的PCB中都维护一个 page table
    提供给 CPU 可操作的 physical address
  • 一般情况下不知直接采用一级 page table，即将所有 4GB 的vaddr映射到 4GB的physical addr，占空间太大了！！【page table在memory中， kernel 1GB的address space中】

2. 代码分析 - Weenix

Weenix 中 page table 实际上由 pagedir struct (pagetable.c)负责维护，结构如下：

1
2
3
4
5
6
7
8
9
10

struct pagedir {
        pde_t      pd_physical[PT_ENTRY_COUNT];
        uintptr_t *pd_virtual[PT_ENTRY_COUNT];
};


int pt_map(pagedir_t *pd, uintptr_t vaddr, uintptr_t   
           paddr, uint32_t pdflags, uint32_t ptflags)

将指定的 virtual addr 与 physical addr

1. 每一个 vaddr 都由唯一对应两个表的index： pagedir table index、page table index
   • pagedir index = (vaddr>>12) / PAGE_ENTRY_CNT
   • pagetable index = (vaddr>>12) % PAGE_ENTRY_CNT
   • 注意：pagedir table中存的是 [index1: pagetable physical addre]的entry
   • 注意：page table中存的才是[index2:physical addr]的entry
   • 这样就建立起 vaddr 的 Two-Level translation system；
     先通过 pagedir table 找到 page table，在查到对应 physical addr
2. pagedir：
   • 由 PCB 维护一个指针指向该 page directory table
   • 从pagedir开始，逐级查找到该 process的address space对应的physical address
3. pd_physical[i]：
   • 由 (vaddr>>12) / PAGE_ENTRY_CNT 计算出vaddr所对应的 pagedir table中的entry
   • 该 entry 中维护一个指针指向下级 page table的 physical address；即vaddr所在的page table
4. *pd_virtual[i]：
   • 由(vaddr>>12) % PAGE_ENTRY_CNT计算出vaddr对应的 page table 中的entry
   • 该 entry 维护中vaddr 对应的 physical addr

II. Page fault

1. page fault handler 具体步骤

page fault 是由MMU检测到的硬件中断，由kernel处理；当一个进程发生缺页中断的时候，进程会陷入(trap)内核态，执行以下操作：

1. 检查要访问的虚拟地址是否合法
2. 查找/分配一个物理页
3. 填充物理页内容（读取磁盘，或者直接置0，或者啥也不干）
4. 建立映射关系（虚拟地址到物理地址）
5. 重新执行发生缺页中断的那条指令

2. 代码分析 - page fault handler

1
2
3
4
5
6
7

void handle_pagefault(uintptr_t vaddr, uint32_t cause)

输入：vaddr【导致发生缺页中断的 vaddr】 
     cause【page fault的原因】
        + write on RDONLY
        + write on Reserved, etc.
输出：void

1. 检查该 vaddr 真的是cur_proc 地址空间中的使用的 addr 么?
   • vmarea = vmmap_lookup(curproc->p_vmmap, ADDR_TO_PN(vaddr))
   • if == NULL，表明地址空间中就没有 任何一个 region用到该地址，返回Error
2. 至此，获得了该 vaddr 所属的 vmarea；
   • 获得vmarea的目的，是为了获得该vaddr实际对应的mmobj
   • 只有通过vmmap_lookup()找出“幕后主使”，才能够进行后续往物理内存中加载内容
   • 比如只有找出该vaddr对应的vmarea，继而找到vnode(即对应的file)，才能知道该往内存中读入什么！！
   • user process 程序操作的全是vaddr，不知道该vaddr实际对应的是什么；但是查询到该vaddr page 所属的 mmobj就知道该往物理内存中读入什么了
3. 注意特殊情况：forwrite，这会引起有意思的 Copy_On_Write
4. 重要的一步：往physical page加载mmobj，并更新page table with (vaddr：paddr)
   • 通过调用 pframe_lookup(vmarea, pageNum, fw, *pframe),找该vmarea下的pframe
   • 实际上vmarea不直接管理pframe，而是vmarea对应的mmobj管理；继而内部调用 vmarea—>mmobj 的 lookuppage()
   • mmobj 调用pframe_get()寻找是否有相应的 pframe 对应于 mmonj&pageNum
   • 如果有：直接返回；
   • 如果没有：进入“无中生有”这一步：
     • 创建 pframe 结构体，获得physical address。 通过：pframe_alloc(mmobj,pagenum)
       1. 这一步会调用 page_alloc() 申请到物理内存physical address
       2. 至此vaddr有了与之对应的物理内存，但还未载入vaddr对应的内容
     • 调用 pframe_fill()往刚申请到的physical addr中载入vaddr对应的内容
       1. 这一步调用 mmobj->ops->fillpage(obj,pf)由vaddr对应的mmobj向物理内存载入内容
       2. 实际上如果是disk，会调用read_block()进入硬件过程；后续还会通过DMA(direct memory access)直接将disk中的内容读入到内存
     • 至此，mmobj的幕后人物：vnode / file 的内容成功读入到 page frame 中
5. 最后调用 pt_map(curproc->pdir, vaddr, pt_virt_to_phys(pf_addr),...)将 (vadd:paddr)写到 page table 中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

【实质】

 virtualAddr <=> pframe <=> physicalAddr
      |            |             |
     user        kernel     physical mem
      |            |             |
      3G    1G=2^20*2^12=4K <==> 4G
       \_ _ _ _ _ _ _ _ _ _ _ _ _／
       
+ 任何一块物理内存都由一个对应的pframe指向,并管理；
+ pframe本身为virtual address；甚至其内部与phsical page
  直接关联的 pf_addr也是 virtual address。But why?**  
+ 实际上:
    - 1page = 4KB = 2^12 Byte
    - physical mem(32bit): 4GB=2^32 Byte
    - pframe #: 2^32 / 2^12 = 2^20 
    - kernel address space: 1GB = 2^20
    - 也就是说：使用pframe分配物理内存的话，
              kernel pframes正好与physical pages形成对应
    - 因此：在pframe创建之时(即对应物理内存征用之时)，
      只需要做一个简单的加减法就可以！
      因为 kernel 1G [c0000000~ffffffff],对应4GB；
      那么减去的 delta=c0000000（该值需要再调整）

fork( ) in Kernel

跟read()一样: 都是user process调用kernel syscall，trap into kernel，在interrupt handler中指明interrupt routine，最终由kernel代为执行任务；

具体在kernle中要做的工作有以下几步：

1. 创建新的 PCB,newProc = proc_create()
2. 拷贝address space,vmmap_copy(newProc)
   • 拷贝 vmmap(address space)的vmarea(只初步copy memory area):
     newProc->p_vmmap = vmmap_clone(curproc->p_vmmap);
   • 拷贝每个vmarea对应的mmobj, from curproc
     • 两个process的vmarea是一一对应的，遍历copy
     • 首先获得即将要拷贝的curproc的第一个vmarea
     • 从newProc的第一个vmarea开始，执行copy：
       curproc->vmarea->vma_obj
     • 更新vma_obj的refcount
     • 判断要该vmarea是否为Private,执行shadow copy
       1. if private，执行shadow copy
       2. 并且要新vmarea插入到bottom_mmobj->mmo_vmas之后
3. 清除 curproc 的pageTable 以及TLB缓存(必须在thread copy之前)
   • 因为curproc的pageTable也会被copy(在thread copy的时候)
     若不重新映射pageTable的话，两个process的vaddr会映射同一paddr
   • 既然pageTable需要重新映射，那么TLB也需要重新缓存新映射
4. 创建新thread，拷贝cur thread内容，包括 register、stack、pageTable
   • 拷贝parent的TCB到新的TCB：kth_new,kth_new = kthread_clone(curthr)
   • 设置所属process，kth_new->kt_proc = newProc
   • 将新thread插入到process的“线程链”之后
   • 更新register信息（包括page table信息）
     • 其实pageTable是给CPU使用的(以下可看出)
     • kt_ctx.c_pdptr = newProc->p_pagedir
     • kt_ctx.c_eip = (uint32_t)userland_entry
     • kt_ctx.c_esp = fork_setup_stack(regs,kth_new->kt_kstack)
     • kt_ctx.c_kstack = (uintptr_t) kth_new->kt_kstack
     • kt_ctx.c_kstacksz = DEFAULT_STACK_SIZE
5. 拷贝file system的内容
   • 拷贝curProc的file-descriptor-table
   • 注意这里是拷贝的 fd table的内容，并非 open-connection-table
   • 因为fd-table很大：NFILES，遍历拷贝
     • 如果 p->p_files[i] != NULL，表明对应实际open-file
     • 还需要更新该open-file的refcount
6. 拷贝p_cwd，并更新p_cwd的refcount:p->p_cwd = curproc->p_cwd;
   • 注意：这里的p_cwd在proc_creat()的时候复制了一遍了
   • 同时也要考虑p_cwd=NULL的情况如何处理
7. 设置 heap segment 的break，与 curproc 的一致
8. 将新thread加入到 run queue 中
9. 设置 parent proc的fork()返回值：newProc->p_pid

I. Virtual memory & File system

1. file可以直接映射进memory，更快，但无cache。

2. 从disk读取文件有两种方法：read() and mmap()

• read():
  • user process： 系统调用read()，trap into kernel
  • kernel： 执行interrupt handler，调用do_read()；继而调用 file system的 read() 指令
  • kernel space：读入的内容放到 kernel address space
  • user space： kernel 将内容copy到 user address space
• mmap():
  • user process：系统调用mmap()，trap into kernel
  • kernel ：执行interrupt handler，调用 do_mmap()；继而调用 file system 的 mmap() 指令
  • user space： kernel 直接将 file 映射到 user address space中

3. file system 中的 vnode 结构体：

- 对应一个电脑文件系统中的一个 file
- 其中还有一个 mmobj vn_mmobj 结构体： 是该file到address space 中的映射。 mmobj 包含：
    + mmo_operations
        - lookuppage：根据[mmobj:page#], 找对应的 pframe
        - fillpage：将 disk file 内容加载到 pframe
        - dirtypage：将该 mmobj 指定的 pframe 设置为 dirty
        - cleanpage：将该 mmobj指定的 pframe 清楚
        - ref
        - put
    + mmo_refcount
    + mmo_resident_pages
- vnode 为抽象的 inode，来实现 polymophism。也有与file 相关的 operations：
    + read
    + write
    + mmap(): 注意这个mmap 是vnode层面的function；**实际上返回的是 vnode->vn\_mmobj; 而这个vn\_mmobj则是通过上述的fillpage()实际将 disk 中的数据加载进 pframe**

II. vmmap.c

1. vmmap_lookup

1
2
3

vmarea_t * vmmap_lookup(vmmap_t *map, uint32_t vfn)

Find the vm_area that vfn(virtual frame number) lies in

2. vmmap_map

1
2
3
4
5
6
7
8
9
10
11

vmmap_map(vmmap_t *map, vnode_t *file, 
          uint32_t lopage, uint32_t npages, 
          int prot, int flags, off_t off, 
          int dir, vmarea_t **new)
- map 为cur process 的地址空间
- file 为被映射到虚拟内存的 vnode/shadow/anonymous obj
- lopage、npages 指明从地址空间的什么具体位置开始映射、映射长度
- prot、flag、off 指明 vmarea 的 read/write、public/private、 vmarea的起始地址
- new 为接收 映射file到虚拟内存的 mapped\_file\_obj 的指针

【注意】该函数被 system API:do_mmap()调用；完成

将指定的 file(anonymous／shadow) 映射map到该进程的“地址空间”address space中；经历一下步骤：

1. 现在cur_proc的地址空间中开辟一块 vmarea

   • if lopage=0: 开辟一个新的 vmarea
   • if lopage!=0: 如果该位置已经被别的vmarea占用，那么删除就的vmarea

2. 对刚获得的 vmarea 赋值：

   • newvma->vma_start = lopage;
   • newvma->vma_end = lopage + npages;
   • newvma->vma_off = ADDR_TO_PN(off);
   • newvma->vma_prot = prot;
   • newvma->vma_flags = flags;
   • list_link_init(&newvma->vma_plink);
   • list_link_init(&newvma->vma_olink);

3. 创建 mmobj（这是 vmarea 存在的意义）

   • if file==NULL: mmobj为新创建的 anonymous obj;
     mmobj = anon_create();
   • if file!=NULL: mmobj为从vnode读入的 mmobj;
     file->vn_ops->mmap(file, newvma, &mmobj);
   • 判断是否需要创建 shadow obj
     if MAP_PRIVATE & flags != 0 需要在 mmobj内部创建 shadow obj

4. 将mmobj 链接到 vmarea上；newvma->vma_obj = mmobj;

5. 将vmarea 插入到 cur_proc 的 地址空间 map 中

3. vmmap_remove()

1

int vmmap_remove(vmmap_t *map, uint32_t lopage, uint32_t npages)

1. 删除虚拟内存/virtual address 中的对应的 mmobj
2. 并删除相应 page table entry，相当于释放物理内存

4. vmmap_is_range_empty

1

int vmmap_is_range_empty(vmmap_t *map, uint32_t startvfn, uint32_t npages)

判断指定的一段pages 在否在虚拟内存中未被占用

5. vmmap_read

1

int vmmap_read(vmmap_t *map, const void *vaddr, void *buf, size_t count)

从 cur_proc 当前地址空间map中指定的vaddr开始，读取“内存”中大小为count的内容到指定的 “内存”buf 中（因为这里的“内存”是虚拟内存，必须要借助pframe_lookup()读取physical memory的值）

1. 循环执行以下步骤，直到读取字节数 达到count 数量；
   • 注意：因为count 是字节数，而 address space 中以 page 为单位；并且page之间并非一直连续，是由 vmarea 链接而成；因此需要遍历 地址空间逐个vmarea、逐个page 读取
2. 在 address space 中查找 start vaddr所属的 vmarea
3. 获得该 vmarea 中所包含的 pages
4. 循环读取所有 pages，memcpy到指定buf
   • 调用pframe_lookup() 找到 virtual page 的 physical page
   • 注意1：如果之前并没有 mapped physical address；那么会调用pframe_get() 即刻map一个physical address
   • 注意2: 这里的 physical address 并非真正的，而依然是存在kernel address space 的 virtual address
   • 调用 memcpy()将对应的pframe中的内容copy到指定的buf中去
   • 注意3:因为memcpy()是C语言库函数，这里实际上还是“virtual address”之间的内容拷贝。很有可能在memcpy()实现了“virtual address to physical address”的转换
5. 直到该vmarea所有pages都copy完
   • if count 未满足，则跳到下一个vmarea继续拷贝
   • if count 满足，则退出

Useful Link

Credit goes to:
https://blog.csdn.net/gfgdsg/article/details/42709943

Notice: page-granularity

All memory in virtual memory address space are page-based. It is the smallest unit of granularity, including the Heap segment in the following.

Virtual Memory Allocation (2 ways):

1. brk() on Heap segment
2. mmap() mapped_file segment, between Heap and Stack

Usually user process calls malloc() to invoke kernel
system calls brk() or mmap() to get a virtual memory. Which one will be executed depends on requesting memory size(128KB is the line)

• size<128KB, kernel calls brk() to assign virtual memory on Heap to user process
  • BAD: only be sequentially assign and free, like Stack
  • GOOD: can be used as cache ()
• size>128KB, kerel calls mmap() to get a piece of memory between Heap and Stack to user process
  • GOOD: can independently assign and free (flexible)
  • BAD: repeately causing page_fault to involve physical memory (CPU costly)

System API：do_brk( )

1
2
3
4
5
6
7
8

int do_brk(void *addr, void **ret)

设置 process 地址空间中Heap Segment的break，即Heap的“堆顶”。  
- malloc()、free()均会调用该API，增加、减小heap break
- malloc()时向高地址增加; free()时向低地址减小

输入： addr 要更新的break地址； ret 更新后的break地址
输出：0-成功

1. 如果 addr == NULL，返回当前 brk
2. 判断 addr 的合法性：与 proc_start_brk比较，不能比他还小
3. 处理 addr 与 proc_brk 在 page_not_aligned 的情况；并获得old proc_brk所在 virtual area 的最后一页 end_page
   • addr : newvfn (new virtual frame number)
   • curproc->p_brk: oldvma->vma_end
   • if(newvfn > oldvma->vma_end): 对应于malloc()
   • if(newvfn < oldvma->vma_end): 对应于free()
4. 最后更新两个量：
   • oldvma->vma_end = newvfn;
   • curproc->p_brk = addr;

I. An Example: read( )

1. User space: User process makes read() system call
2. Interrupt: This will trap into kernel by software interrupt
3. System API: Kernel executes its interrupt handler, in which sys_read() API will be called
   • copy_from_user() the read_args(fd/buff/…)
   • page_alloc() a temporary buffer
   • call do_read(), and copy_to_user() the read bytes
   • page_free() that buffer
   • return the number of bytes actually read, or if anything goes wrong
4. File system API: Specific file system function do_read() will be executed.
   • 注意：do_read()是 file system 的 system call

II. System API for file operation

1. System Read API

1
2
3
4
5
6

int sys_read(read_args_t *arg)

kernel “读”操作的API，自此由kernel执行一系列“读”相关的操作

输入：arg，包含了user process read()的所有参数
输出：实际读出的字节数

1. 作为 interrupt routine 被调用；发生于 user process read() leading to trap as software interrupt into kernel 的时候
2. copy_from_user() 读取 user process read()的传入参数
3. 在 kernel address space 分配一块buffer，作为临时接收数据的区域
4. 调用 file system 的 do_read()，从 disk 中 读取数据到 buffer
5. copy_to_user(),将buffer 中读取到的数据 copy 到 user address space（低地址空间 0xc0000000 - 0xc0000000）
6. page_free(),将 buffer 释放
7. 根据 file system 读取的结果，返回ERROR 或者 读取的字节数

2. System Write API

1
2
3
4
5
6

int sys_write(write_args_t *arg)

kernel “写”操作的API，自此由kernel执行一系列“写”相关的操作

输入：arg，包含了user process write()的所有参数
输出：实际写入的字节数

1. 在kernel address space 开辟临时buffer，读取放置user 要写的数据
2. 从 user address space 拷贝 read() 输入参数，包括要写的数据
3. 调用 file system 的do_write()操作， write to disk
4. 释放 kernel address space 的临时 buffer
5. 返回ERROR 或者 写入的字符数

3. System Get Directory Entry

1
2
3
4
5
6
7
8

int do_getdent(int fd, struct dirent *dirp)

对目录文件的操作，比如：
- 获得位于指定字节数位置的子目录entry
- 显示某个文件夹下所有子目录名称、大小等信息

输入：fd(要读取的文件指针)、dirp(目标dir entry的容器)
输出：count_bytes

1. copy_from_user()从 user address space 读取参数到 kernel address space（从而知道用户都想干些啥？）
2. 循环调用 do_getdent() 以及 copy_to_user()，直到达到user process 指定的 字节数目
   • do_getdent() 调用 file system API 读取目录，并将结果放在 dir 中
   • copy_to_user()将 dir 中的信息 copy 到 user address space 中去；这样就会在用户的 fd 下逐渐显示出读入的 sub dir entry 的名字、大小等信息
   • 读入的 count_bytes >= user_args.count 时，跳出循环
3. 返回实际读取到的目录所占字节数 count_bytes

4. Other System APIs related to File System

1
2
3
4
5
6
7
8
9
10
11

int sys_close(int fd)
int sys_dup(int fd)
int sys_dup2(const dup2_args_t *arg)
int sys_mkdir(mkdir_args_t *arg)
int sys_rmdir(argstr_t *arg)
int sys_unlink(argstr_t *arg)
int sys_link(link_args_t *arg)
int sys_rename(rename_args_t *arg)
int sys_chdir(argstr_t *arg)
int sys_lseek(lseek_args_t *args)
int sys_open(open_args_t *arg)

以上的 system API 都与 file system 有关。都经过以下过程：

1. User process makes system call: read()
2. Traps into kernel as software interrupt: interrupt handler
3. Kernel execute corresponding API: sys_read()
4. Copy from user address space parameters into kernel address space
5. Ask File System to complete relavent operation: do_read()
6. Copy to user address space with the result at kernel address space

III. Other System API related to Virtual Memory System

1
2
3
4
5
6
7
8
9

int sys_munmap(munmap_args_t *args)
void *sys_mmap(mmap_args_t *arg)
pid_t sys_waitpid(waitpid_args_t *args)
void *sys_brk(void *addr)
void sys_sync(void)
int sys_stat(stat_args_t *arg)
int sys_fork(regs_t *regs)
int sys_execve(execve_args_t *args, regs_t *regs)
int sys_kshell(int ttyid)

这些函数与“用户态” Process/ Thread/ Virtual Memory 的操作有关：

1. 由 user process 发起的 system call： wait()
2. 经过software interrupt trap into kernel
3. kernel 在调用相应的 system API，代替 user process 执行任务: sys_waitpid()
4. 交给“进程系统” Process& Memory System，来具体处理任务：do_waitpid()

VI. Interrupt handler for syscalls

1
2
3
4
5

void syscall_handler(regs_t *regs)

很重要的一个函数：
1. 使“用户态”程序在 make syscall 的时候，进入“内核态”
2. 根据 syscall_number，调用相应的 system API

Why do we need page frame?

实际 page frame 只是 kernel 的一个 struct，用于：

1. 记录：由其包含的 physical page 地址（其实还是virtual addr）
2. 记录：该page 所属的 memeory object(即 vm_area_struct/bss… 所指向的)；以及该page 的 page_num
3. 第一条“由其包含”表明了，OS需要一个结构体来管理所“征用”的physical page，这个结构体就是 page frame
4. 注意：page frame 中的page 不一定都在 physical memory 中，也有可能被 page out 到了 disk。前者称为 resident page。

1. pframe_init()

使用物理内存之前的准备工作，开机时？

初始化与 pframe 有关的量：

• alloc_list
• pinned_list
• pframe_allocator
• pageout deamon

2. pframe_shutdown（）

停止使用物理内存之后的清理工作，关机时？

• 停止 pageout deamon
• 清理及 free 所有 page

3. pframe_get_resident（）

获得“驻足内存的pframe”，based on mmobj & pagenum; 如果pframe 不再内存中，返回NULL

4. pframe_alloc（）

为 mmobj、pagenum 指定的 page 分配物理内存

5. pframe_lookup（）

实际上就是执行 pframe_get()，

6. pframe_get（）

#参见page\_fault():
https://caomingkai.github.io/2018/04/18/VM-Page-Table-Page-Fault-Hander/

根据 ‘mmobj & pagenum’ 得到 pframe

• 如果物理内存中已有该page，直接返回
• 如果物理内存中没有该page，allocate 新的，并（有可能从disk）fill 进内容

1. 先判断由 ‘mmobj & pagenum’ 指明的pframe 是否存在于内存中，by calling pframe_get_resident()
   • 如果存在，继续判断 pframe 是否 busy（因为有可能被 pageout deamon 操作）
     • if busy 则 sleep；醒来时再回到第1步，判断pframe是否存在于物理内存中
     • if not busy，直接返回 pframe
   • 如果不存在，则创建新的pframe
     • 先判断是否需要启动 pageout deamon 释放部分物理内存，需要的话就唤醒 deamon
     • 然后分配pframe空间， pframe_alloc(o,pagenum)；注意返回值ERROR
     • 再向刚获得的pframe中添加内容， pframe_fill()；注意返回值ERROR

7. pframe_migrate（）

将pframe 移到父节点；缩短 shadow object tree 的高度（在某个mmobj被清除的时候）

8. pframe_fill（）

调用 specific mmobj 的 fillpage() 真正实现将外部数据读入物理内存

9. pframe_pin（）

对该 pframe 锁定 pin down，防止被 pageout

1. 判断该 pframe 的 pf_pincount 是否为“0”
   • 如果==0，表明该 pframe page 在 allo_chain上
     • 从原来 chain 卸下来
     • nallocated–
     • 加入 pinned_chain 中
     • npinned++
     • pf->pf_pincount++
   • 如果 != 0，表明该 pframe page 已经在 pinned_chain上了
     • 只需要 pf->pf_pincount++ 即可

10. pframe_unpin（）

将该 pframe 解锁，向 pageout deamon 开放

1. 首先更新 pf_pincount： pf_pincount–;
2. 判断该 pframe 的 pf_pincount 目前是否为“0”
   • 如果==0，那么
     • 从 pinned_chain 中卸下来
     • npinned–
     • 加入 alloc_chain 中
     • nallocated++
   • 如果 !=0, 那么啥也不做

11. pframe_dirty（）

对 pframe（仅指file_obj，shadow、anony 无法pageout）进行更改之前，将该page设置为 DIRTY，待 pageout deamon 回收的时候检查到DIRTY时，会将page的内容更新到 disk 上

1. 题意：

• 给n个任务 1～k；
• 以及 task dependency array A、B；其中 [Ai,Bi] - bi先完成，才能做ai；
• 同时规定：每个task顶多只能依赖一个task
• 问：最多可以完成的任务数

2. 分析

虽然任务的dependency可能成环(1-2-3-4-1),但有第三条可知：
每个任务最多出现在1个“环”里，表明该“环”上的任务有一个不可能完成，但可以完成(环任务数-1)的任务
对于没有出现在环中的任务，这些任务都能够执行完

因此，相当于根据 A、B，找 number of dependency cycle，
那么最多可以完成的任务数就是：总任务数 - 环数

3. Union Find Class

Union Find Summary: https://workflowy.com/s/HdnT.nwWuWS1F7W

如何找有多少环？:Union-Find.isConnected()

• 对每个 task dependency 进行 union
• union 之前调用 isConnected() 检查是否已连通(表明该[ai,bi]会导致“环”)
• 累加 每次isConnected() 结果为 True 的情况
• isConnected() 有几次为 True，就存在几个“环”

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
29
30
31
32
33
34
35
36
37
38
39
40
41

// weighted quick UF

class UnionFind{
	int [] p;
	int [] w;
	int numOfCycles ;
	
	public UnionFind(int N){
		p = new int[N];
		w = new int[N];
		numOfCycles = 0;
		for( int i = 0; i < N; i++ )
			p[i] = i;
	}

	void union(int a, int b ){
		int pa = find(a);
		int pb = find(b);
		if( pa == pb ){
			numOfCycles++;
		}else{
			if( w[pa] < w[pb] ){
				p[pb] = pa;
				w[pa] += w[pb];
			}else{
				p[pa] = pb;
				w[pb] += w[pa];
			}
		}
	}


	int find(int a){
		while( p[a] != a ){
			p[a] = p[p[a]];
			a = p[a];
		}
		return a;
	}
}

4. Solution

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
29
30
31
32
33
34

class TaskMaster{
	public static int maxTasks(int n, int[] a, int[] b ){
		int ret = 0;
		int size = a.length;
		UnionFind UF = new UnionFind(n);
		
		for( int i = 0; i < size; i++ ){
			UF.union(a[i]-1,b[i]-1);
		}
		int numOfCycles = UF.numOfCycles;
		ret = n - numOfCycles;
		return ret;
	}

	public static void main( String[] args ){
		// int n = 8;
		// int[] a = {2,3,4,1,5,8,7};
		// int[] b = {1,2,3,4,6,7,8};

		// int n = 4;
		// int[] a = {2,3,4,1};
		// int[] b = {1,2,3,4};

		// int n = 2;
		// int[] a = {};
		// int[] b = {};

		int n = 2;
		int[] a = {2};
		int[] b = {1};

		System.out.println(maxTasks(n, a, b ));
	}
}

方法一：Priority Queue

0. O(nlogn)
1. 前后两个窗口差别只有两个数，尽量用到上一个窗口的信息
2. 上一个窗口的头部元素从窗口元素集剔出，加入下一个窗口的尾部元素；形成新的窗口元素集
3. 想办法从“窗口元素集”中找最大值==> priority queue 最合适

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
        if( nums == null || nums.length == 0 )
            return new int[0];
        
        int len = nums.length;
        int[] ret = new int[len-k+1];
        PriorityQueue<Integer> pq = new PriorityQueue<>(k, Collections.reverseOrder());
        
        for( int i = 0; i < len; i++ ){
            if( i >= k ){
                ret[i-k] = pq.peek();
                pq.remove(nums[i-k]);
            }
            pq.add(nums[i]);
        }
        ret[len-k] = pq.peek();
        
        return ret;
    }
}

方法二：单调队列 / Monotonic Queue / Deque

0. O(n) - 每个元素顶多 add to／remove from queue，共2次
1. 上一个方法在从窗口元素集找最大 O(logn),继续优化只能为 O(1)
2. 想办法维护一个与窗口区对应的“有序数据结构”
3. 进入下一个窗口前，上一个窗口对应的 potential_max queue 是有序的
4. 进入下一个窗口后，
   • 如果第一个 potential_max 仍然在新窗口范围内；
     该peotential_max不需要从 queue中删除，仍然有可能是后边窗口的max
   • 如果第一个 potential_max 不在新窗口范围内；
     该value就不是potential max了，而是 definitely_not_possible_max for later windows

5. 窗口末尾新加入的元素：

   • 如果值比 potential_max_queue 中的最后一个 potential_max_value 小，
     那么该值与之前的值都有可能是后边窗口的max
   • 如果值比后边的“某一段”potential_max values 都大，
     表明“那一段”potential values 因为更大新元素的加入，由 potential 变为 never_possible_max
   • 直接删除“那一段” potential values，并将该值插入到 queue之后

6. 【小结】：potential_max_queue 的维护有4点：

   • 维护这么一个“单调队列”目的：某个window的max，就是其对应 petential_max_queue 中的第一个元素
   • 头部 potential_max_value 在当前window下是否valid，是否需要删除；
   • 头部 potential_max_value 是否valid，实际是根据其 index来判断的，因此在queue中维护的实际是 index
   • 新加入的元素是否应该加入potential max queue，加入到哪里

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

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
        if( nums == null || nums.length == 0 )
            return new int[0];
        
        int len = nums.length;
        int[] ret = new int[len-k+1];
        Deque<Integer> dq = new LinkedList<>();
        
        for( int i = 0; i < len; i++ ){
            // check head items of the potential_max_queue
            if( !dq.isEmpty() && dq.peekFirst() < i-k+1 )
                dq.removeFirst();
            
            // handle new item
            while( !dq.isEmpty() && nums[dq.peekLast()] < nums[i] ){
                dq.removeLast();
            }
            dq.addLast(i);
            
            // update ret values
            if(i-k+1 >= 0)
                ret[i-k+1] = nums[dq.peekFirst()];
        }
        return ret;
    }
}

Preface

1. dir_namev() 没有处理如下情况：
   • extra slashes： paths_equal(“1/2/3”, “1///2///3///“);

vfstest_main

1. int makedirs(const char *dir)

   • 对传入的 绝对路径：dir，逐级建立相应的directory

2. int getdent(const char *dir, dirent_t *dirent)

   • what： 读取 dir 下的第一个非 ./.. 的entry
     • 有的话，存到 dirent，返回 1
     • 没有的话， 返回 0
   • 先调用open(dir) 得到 fd
   • 然后调用getdents(fd, dirent)依次读取该dir 下的 entries
   • 将该dir下：除了”.”以及”..”的第一个entry读出来，读到dirent
     • 如果有其它 entry，那么关闭fd，返回 1
     • 如果只有 “.” “..”， 那么关闭fd，返回 0

3. int removeall(const char *dir)

   • what:
     • 将 dir 下的所有 files 以及 sub-files 全部unlink
     • 删除 本 dir
     • 将cur_proc 置为 “..”

4. void vfstest_start(void)

   • what
     • 随机生成 root_dir 的名字，并mkdir 该dir
     • 注意这只是 vfs_test 的root dir

5. void vfstest_term(void)

   • what：Terminates the testing environment
   • 调用 removeall (root_dir) 将vfstest 过程中所有文件／目录（包括 root_dir 自己)删除

6. 宏函数：test_assert(expr, fmt, args…)

   • what:
     • expr应该是 true；
     • otherwise，打印format信息，以及后续的参数

7. 宏函数：syscall_success(expr)

   • what：
     • expr所对应的测试的代码 should fail；

8. 宏函数：syscall_fail(expr, err)

   • what：
     • expr所对应的测试的代码 should fail；即 -1 == (expr)
     • 并且，返回的错误代码应该跟此处传入的err一致

9. 宏函数：create_file(file)

   • what:
     • 用于测试“成功打开open”、“成功关闭close” file;
     • 【注意】创建 file，不是 dir
     • 调用 open(file, O_RDONLY|O_CREAT)
     • 生成相应 fd

10. 宏函数：read_fd(fd, size, goal)

    • what：
      • 用于测试 read() 是否能够从文件fd：
      • 1-读取指定 size 的内容到buf
      • 2-读取的内容无误： buf与goal 一致

11. 宏函数：test_fpos(fd, exp)

    • what：
      • 用于测试 fd 对应 f_pos 目前应该出在 exp 指示的位置

12. vfstest_stat()

    • what : 测试 do_stat()
    • 涉及函数：
      • mkdir
      • chdir
      • open
      • write
      • close

13. vfstest_mkdir()

    • what : 测试 mkdir()
    • 涉及函数：
      • mkdir
      • chdir
      • rmdir
      • unlink

14. vfstest_chdir()

    • what : 测试 mkdir()
    • 涉及函数：
      • mkdir
      • chdir
      • stat

15. vfstest_paths()

    • what :

      • 测试 directory path 的各种 “edge cases”
      • 主要函数paths_equal(p1,p2)

    • paths_equal(p1,p2)

      • 传入的 char* str，满足 p1 == p2
      • 首先调用 makedirs(p1)，逐级创建 二者对应的 dir
      • 调用 stat(p1) 、stat(p2) 比对二者的信息
    • 涉及函数：
      • mkdir
      • chdir
      • stat
      • open

16. vfstest_fd()
    • what : 测试 fd：file descriptor
    • how:
      • read/write/close/getdents/dup nonexistent file descriptors
      • dup2 has some extra cases since it takes a second fd
      • if the fds are equal, but the first is invalid or out of the allowed range
      • dup works properly in normal usage
      • dup2 works properly in normal usage
      • dup2-ing a file to itself works
      • dup2 closes previous file
      • 如果dup2传入的fd是已在使用中的,
        会首先关闭该fd对应的open_conn，
        然后将该fd赋给新的 open_conn
    • 涉及函数：
      • mkdir
      • open
      • read
      • write
      • lseek
      • getdents
      • dup
      • dup2
      • close
      • chdir

17. vfstest_memdev()
    • what :
      • 测试 /dev/null 以及 /dev/zero 的读写
    • /dev/null，或称空设备，被称为比特桶或者黑洞。
      是一个特殊的设备文件，它丢弃一切写入其中的数据
      但报告写入操作成功；读取它则会立即得到一个EOF
    • /dev/zero，当你读它的时候，它会提供无限的空字符(NULL)
      可以将数据写入 /dev/zero 文件，但实际上不会有任何影响；
      不过一般我们还是使用 /dev/null 来做这件事
    • 涉及函数：
      • mkdir
      • chdir
      • rmdir
      • unlink

18. vfstest_write()
    • what :
      • 测试 在不同位置 f_pos 的 write() 操作
      • 测试 lseek()
    • test_assert(lseek(fd, 0, SEEK_END) == (NUM_CHUNKS-1) * CHUNK_SIZE + (int)strlen(str)
      • 返回的 f_pos在文件尾，但并不是 (NUM_CHUNKS) * CHUNK_SIZE
      • 因为每个chunk中，内容只占strlen(str)部分，应该为：
      • (NUM_CHUNKS-1) * CHUNK_SIZE + (int)strlen(str)
    • 涉及函数：
      • mkdir
      • chdir
      • lseek
      • write
      • close

19. vfstest_infinite()
    • what :
      • 申请一个 很大的 buf空间
      • 持续向 dev/null 中写，一直写到爆；
        即写入字节数的返回值<= 0
      • 持续从 dev/zeor 中读NULL，一直读到爆；
        即读入字节数的返回值<= 0
    • 涉及函数：
      • mkdir
      • open
      • read
      • write
      • close

20. vfstest_open()
    • what :
      • 测试 open()
      • 测试 close()
      • 测试 unlink()
    • how:
      • Accepts only valid combinations of flags
      • Cannot open nonexistent file without O_CREAT
      • Cannot write to readonly file
      • Cannot read from writeonly file
      • Cannot close non-existent file descriptor
      • Lowest file descriptor is always selected
      • Cannot unlink a directory
      • Cannot unlink a non-existent file
      • Cannot open a directory for writing
      • File descriptors are correctly released when a proc exits
    • 涉及函数：
      • mkdir
      • chdir
      • open
      • write
      • unlink
      • stat
      • close

21. vfstest_read()
    • what : 测试 do_read()
    • how:
      • Can read and write to a file
      • cannot read from a directory
      • Can seek to beginning, middle, and end of file
      • O_APPEND works properly
    • 涉及函数：
      • mkdir
      • chdir
      • open
      • read
      • write
      • lseek
      • close

22. vfstest_getdents()

    • what :
      • 测试 do_getdent() 读取dir目录的entries的情况

    • 涉及函数：

      • mkdir
      • chdir
      • open
      • close
      • do_getdent

    • 问题：vfstest_getdents()这个函数：
      在dir01中建立了一个目录、一个文件，
      为啥getdents(fd, dirents, 4 sizeof(dirent_t))
      返回值是4 sizeof(dirent_t)呀？

    • 答案：
      • 每个目录下还有 ‘.’ 以及 ‘..’ ，所以是4个！
    • 会调用 user process 的 getdents()
    • 继而调用 ksys_getdents(fd, *dirp, count)：
      • 将fd代表的directory目录下所有的entries读取出来，
      • 结果按顺序放到dir中，直到读入的信息达到指定的count
      • 返回实际读到的字节数(就是所有entries构成的dir)

faber_fs_thread_test

1. 检查 argc， 要求在执行faber_fs_thread_test()的时候，必须带参数

   • if ( argc == 1 ) { // 打印错误 }

2. 如果满足，即 argc>1；再检查输入的参数:n

   • if sscanf() != 1, 表明argv中的参数没有输入正确，
     • lim = 1
   • if sscanf() == 1，表明argv中的参数正确输入了
     • 即告知该程序：我想要开辟几个进程／线程
     • 然后只需要检测一下，lim不超过上下限即可
   • sscanf()
     • dtm =”Saturday March 25 1989” );
     • int n = sscanf( dtm, “%s %s %d %d”, weekday, month, &day, &year )
     • 将dtm的data，按照format的形式，赋值给后边的变量
     • 返回值：一共赋值了几个变量。此处 n = 4
       • snprintf()
     • BUFLEN = 256
     • char tname[BUFLEN]; 定义了一个字符数组，最大程度256
     • snprintf(tname, BUFLEN, “thread%03d”, i);
     • 会将”thread%03d”与i 构成的字符串写道 tname 中
     • snprintf 中 BUFLEN 指定了tname接受的最大字符数

3. 开辟 lim 个进程／线程 make_dir

   • name：” thread k “
   • 每个进程／线程 执行：make_dir_thread()
4. do_waitpid()等待所有的线程结束
   • if rv<0 : 打印 pid + rv + err_info
   • else : 打印 pid + rv
   • 至此所有的 make_dir_thread 进程／线程 终结了
5. 再开辟 lim 个进程／线程 clean_dir
   • name: “ clean_dir_thread k “
   • 每个进程／线程 执行 clean_dir_thread()
     • 如果上次 all passed，kthread_create最后参数为：NULL
     • 如果上次有未 passed，kthread_create最后参数为：1
   • do_waitpid()等待当前线程结束，打印信息
6. 最后删除所有的 lim 个dir
   • 根据前几次的 pass 值
   • 如果全部删除成功， 打印成功
   • 如果有未删除的，打印失败

make_dir_thread

1. 该线程创建一个目录： /dir00k
2. 然后在每个目录中创建 20 个file：
   • /dir00n/test000 ～ /dir00n/test019
   • 调用 do_open(O_CREAT)的方式创建新文件
     • 如果有错误，直接返回 err_val
   • 调用 do_write()向每个文件中写 “look！”
   • 调用 do_close()关闭该文件

clean_dir_thread

1. 该线程会删除 arg1 指定的目录(/dir00k)下的所有files
2. arg2的值由 make_dir_thread的执行结果确定
   • Arg2 == 0 means directory should exist.
   • Arg2 == 1 means if directory does not exist,
     don’t treat it as error.
     • 尝试性的删除 make_dir_thread 创建的 file
3. 调用 f=do_open()打开 该 dir
   • 如果该dir未打开，并且 Arg2 == 1，该线程退出 with rv=0
   • 如果 Arg2 == 0，该线程退出 with rv=f
4. 调用 do_getdent() 挨个handle 每个 entry
   • 跳过 “.” , “..” entry
   • 拼接其要删除的file 的绝对路径
   • 调用 do_unlink(file_path) 删除该file 的连接
     • 如果删除成功， 置got_one = 1; 跳出
     • 关闭该 fd 的open_conn

faber_directory_test

0. 与faber_fs_thread_test区别在于：
   • 第一个
     所有mk_dir_threads成功之后，回收threads；
     再创建rm_dir_threads，成功后，回收threads
   • 第二个
     mk_dir_thread 与 rm_dir_thread 混合执行
     然后同时等待这两类thread的终结
1. 该函数创造“成对的进程／线程”
   • proc_1 name: “ thread k “
   • proc_2 name: “ rmthread k “
2. 每次 iteration
   • 创建一个 thread， 并运行之
   • 创建一个 rmthread，并运行之

3. 调用 do_waitpid() 等待所有子进程结束

   • 如果某个进程返回rv < 0 , 打印：pid + rv + err_info
   • 如果某个进程返回rv ==0 , 打印：pid + rv

4. 循环删除所有 directory

   • do_rmdir(tname)

rm_dir_thread

1. 该线程创建一个目录： /dir00k
2. 然后删除目录中名字为：“/dir00n/test000” 的file
   • /dir00n/test000 ～ /dir00n/test019
   • 调用 do_open(O_CREAT)的方式创建新文件
     • 如果有错误，直接返回 err_val
   • 调用 do_write()向每个文件中写 “look！”
   • 调用 do_close()关闭该文件

BIOS(code stored on ROM)

At BIOS session, several tasks are executed:

1. Power-on self test (POST), making suring: memory, disk,screen,ect. are in good condition
   • so it knows where to load the boot program( on DISK)
   • also prepare memory(run process) and disk(boot program)
2. Load and transfer control to boot program
3. Provide drivers for all devices,

Boot(code stored on DISK)

1. Set up stack, clear BSS, uncompress kernel, then transfer control to Kernel

2. Idle process(pid=0) is created; set up initial page tables, turn on address translation

3. Initialize rest of kernel

   • create vfs_root_vnode
   • set the “cwd” of idle/init process
   • make the null, zero, and tty devices using “mknod”
     • “/dev”
     • “/dev/null” “/dev/zero”,
     • “/dev/tty0” “/dev/tty1”
   • create the “init” process(pid=1),
     which is the ancestor of all other user processes
   • invoke the scheduler

Kernel(code stored on disk)

1. Now the File System is ready to use
2. Also need to execute other configuration