Skip to content

Latest commit

 

History

History
167 lines (101 loc) · 10.1 KB

OS_EXAM_2017_FINAL.md

File metadata and controls

167 lines (101 loc) · 10.1 KB

OS_EXAM_2017_FINAL

  1. lab2: 小晖需要了解x86的内存大小与布局，页机制，页表结构等。硬件模拟器提供了 128MB的内存，并设定一个页目录项（PDE）占用(3.1)个Byte，一个页表项（PTE）占用(3.2)个 Byte。在lab2中可通过(3.3)和(3.4)两种方式获取系统内存大小，并且由于空闲的RAM空间不连续，所以bootloader简化处理，从物理内存地址(3.5)起始填充ucore os kernel的代码段和数据段。在ucore建立完页表并进入页模式后，ucore代码段的起始物理地址对应的虚拟地址为(3.6)

    4；4；BIOS中断调用；直接探测；0x0010 0000；0xC010 0000

  2. lab3: 小彤发现ucore在完成页机制建立后，内核某内存单元的虚拟地址va为 0xC2345678，且此时硬件模拟器模拟的的cr3寄存器的值为0x221000，则此va对应的页目录表的起始物理地址是(4.1)，此va对应的PDE的物理地址是(4.2)。如果一个页（4KB/页）被置换到了硬盘某8个连续扇区（0.5KB/扇区），该页对应的页表项（PTE）的最低位--present 位应该为(4.3) ，表示虚实地址映射关系不存在，而原来用来表示页帧号的高(4.4)位，恰好可以用来表示此页在硬盘上的起始扇区的位置（其从第几个扇区开始）。

    4KB一页，4B一页表项

    0xC2345678 = 1100 0010 00 | 11 0100 0101 | 0110 0111 1000

    pde index = 11 0000 1000 = 0x308

    pte index = 11 0100 0101 = 0x345

    offset = 0x678

    4.1 页目录表起始地址：0x0022 1000

    4.2 pde addr = 0x221000 + 0x308 << 2 = 0x0022 1C20（一页4B 故<<2）

    4.3 present = 0

    4.4 用高 32-12 = 20位表示（len - offset）

  3. lab4: 小颖在理解进程管理中，仔细分析了ucore源码中的进程控制块数据结构(5.1)，且其中的关键域（也称field，字段）数据结构(5.2)用于保存被中断打断的运行现场，关键域数据结构(5.3)用于进行进程/线程上下文切换的保存与回复。

    proc_struct；trap_frame；context

  4. lab5: 小辰对用户进程的创建有了更深入的了解：用户进程在用户态下执行时，CS 段寄存器最低第两位的值为(6.1)。当ucore os kernel建立完毕第一个用户进程的执行环境后，通过执行x86机器指令(6.2)后，将从内核态切换到用户态，且将从用户进程的第一条指令处继续执行。当用户进程执行sys_exit系统调用后，ucore会回收当前进程所占的大部分资源，并把当前进程的状态设置为(6.3)。

    用户态CS端RPL值为3（ring 3）；IRET；ZOMBIE

  5. lab6: 小磊通过阅读代码，了解了ucore的调度框架和RR调度算法等，体会到调度本质上体现了对(7.1)资源的抢占，操作系统通过(7.2)来避免用户态进程长期运行，并获得控制权。

    CPU；时钟中断；

  6. lab7: 小航发现课本中阐述的同步互斥原理对实现细节简化了很多。在ucore中，通过利用x86机器指令(8.1)简洁地实现了入临界区代码，通过利用x86指令(8.2)简洁地实现了出临界区代码。通过分析ucore中管程的数据结构，可知道ucore中的管程机制是基于(8.3)机制和(8.4)机制来实现的。

    CLI；STI；信号量；等待队列；

  7. lab8: 小行了解到ucore中的文件系统架构包含四类主要的数据结构， (9.1)：它主要从文件系统的全局角度描述特定文件系统的全局信息。 (9.2)：它主要从文件系统中单个文件的角度描述了文件的各种属性和数据所在位置。 (9.3)：它主要从文件系统的文件路径的角度描述了文件路径中的特定目录。 (9.4)： 它主要从进程的角度描述了一个进程在访问文件时需要了解的文件标识，文件读写的位置，文件引用情况等信息。

    Superblock（超级块）；inode （索引节点）；dentry（目录项）；file（文件）

    从ucore操作系统不同的角度来看，ucore中的文件系统架构包含四类主要的数据结构，它们分别是：

    • 超级块（SuperBlock）：它主要从文件系统的全局角度描述特定文件系统的全局信息。它的作用范围是整个OS空间。
    • 索引节点（inode）：它主要从文件系统的单个文件的角度描述了文件的各种属性和数据所在位置。它的作用范围是整个OS空间。
    • 目录项（dentry）：它主要从文件系统的文件路径的角度描述了文件路径中的特定目录。它的作用范围是整个OS空间。
    • 文件（file）：它主要从进程的角度描述了一个进程在访问文件时需要了解的文件标识，文件读写的位置，文件引用情况等信息。它的作用范围是某一具体进程。

  8. LFU是最近最不常用页面置换算法(Least Frequently Used)，小白听到两个LFU定义的说法，有些糊涂：

    1. 采用LFU算法的OS在碰到进程访问的物理内存不够时，换出进程执行期内被访问次数最少的内存页，当此页被换出后，其访问次数n会被记录下来，当此页被再次访问并被换入时，此页的访问次数为n+1。
    2. 采用LFU算法的OS在碰到进程访问的物理内存不够时，换出进程执行期内被访问次数最少的内存页，当此页被换出后，其访问次数清零，当此页被再次访问并被换入时，此页的访问次数为1。

    请问你认为那种LFU的定义是正确的？请分别回答第一种/第二种LFU定义是否有Belady 异常现象。如没有，请给出证明，如有，请给出会引起Belady异常现象的的页数/页帧数设置以及访问序列。

    第一种相当于维护了一个很大的访问次数栈，栈中的页按访问次数排序，顶端N个页和最近访问页面驻留在内存中，因此本质是栈算法。第二种会有Belady。

  9. 小明为更好理解lab8，设计了一个简化文件系统Xiao Miang File System, 简称 xmfs。

    xmfs的系统调用接口包括：

    • mkdir() - 创建一个新目录
    • creat() - 创建一个空文件
    • open(), write(), close() - 打开文件，写文件，关闭文件
    • link() - 对文件创建一个硬链接（ hard link）
    • unlink() - 对文件取消一个硬链接 (如果文件的链接数为0，则删除文件）
    • 注意：通过 write()对文件写一个数据buffer时，常规文件的最大size是一个 data block，所以第二次写（写文件的语义是在上次写的位置后再写一个data block）会报错（文件大小满了）。如果data block 也满了，也会报错。

    xmfs在硬盘上的总体组织结构如下：

    • superblock：记录可用inode数量，可用data block数量
    • inode bitmap：已用/空闲inode的分配图（基于bitmap）
    • inodes：inode的存储区域
    • data bitmap：data block的分配图（基于bitmap）
    • data：data block的存储区域

    xmfs的关键数据结构--inode数据结构如下：

    • inode：包含3个fields（file type，data block addr of file content，reference count）,用list表示：
    • file type: f -> 常规文件： regular file, d -> 目录文件： directory
    • data block addr of file content: -1 -> file is empty
    • reference count: file/directory 的引用计数，注意directory的引用计数是指在此目录中的inode的个数
    • 注意：比如，刚创建的一个空文件inode：[f a:-1 r:1]，一个有1个硬链接的文件inode：[f a:10 r:2]

    xmfs的关键数据结构--数据块（data block）结构如下：

    • 一般文件的内容表示：只是包含单个字符的 list，即占一个 data block，比如['a'], ['b'] .....
    • 目录的内容表示：多个两元组（name, inode_number）形成的list，比如，根目录 [(.,0) (..,0)]，或者包含了一个'f'文件的根目录[(.,0) (..,0) (f,1)]。
    • 注意：一个目录的目录项的个数是有限的。block.maxUsed = 32
    • 注意：data block 的个数是有限的,为fs.numData
    • 注意：inode 的个数是有限的,为fs.numInodes

    完整xmfs文件系统的参考实例：

    fs.ibitmap: inode bitmap 11110000 fs.inodes: [d a:0 r:5] [f a:1 r:1] [f a:-1 r:1] [d a:2 r:2] [] ... fs.dbitmap: data bitmap 11100000 fs.data: [(.,0) (..,0) (y,1) (z,2) (x,3)] [u] [(.,3) (..,0)] [] ...

    对上述xmfs参考实例的解释：有8个inode空间,8个data blocks.其中，根目录包含5个目录项，“.”，“..”，“y”，“z”，“x”。而“y”是常规文件,并有文件内容，包含一个data block，文件内容为“u”。“z”是一个空的常规文件。“x”是一个目录文件，是空目录。

    如果xmfs初始状态为： inode bitmap 10000000 inodes [d a:0 r:2] [] [] [] [] [] [] [] data bitmap 10000000 data [(.,0) (..,0)] [] [] [] [] [] [] []

    在执行了系统调用mkdir("/t")后，xmfs的当前状态为： inode bitmap 11000000 inodes [d a:0 r:3] [d a:1 r:2] [] [] [] [] [] [] data bitmap 11000000 data [(.,0) (..,0) (t,1)] [(.,1) (..,0)] [] [] [] [] [] []

    请问接下来的4个状态变化所对应系统调用是什么？ 要求回答格式象上面“mkdir("/t")”一样。

    （1） inode bitmap 11100000 inodes [d a:0 r:4] [d a:1 r:2] [f a:-1 r:1] [] [] [] [] [] data bitmap 11000000 data [(.,0) (..,0) (t,1) (y,2)] [(.,1) (..,0)] [] [] [] [] [] []

    （2） inode bitmap 11100000 inodes [d a:0 r:4] [d a:1 r:3] [f a:-1 r:2] [] [] [] [] [] data bitmap 11000000 data [(.,0) (..,0) (t,1) (y,2)] [(.,1) (..,0) (c,2)] [] [] [] [] [] []

    （3） inode bitmap 11100000 inodes [d a:0 r:4] [d a:1 r:3] [f a:2 r:2] [] [] [] [] [] data bitmap 11100000 data [(.,0) (..,0) (t,1) (y,2)] [(.,1) (..,0) (c,2)] [o] [] [] [] [] []

    （4） inode bitmap 11110000 inodes [d a:0 r:5] [d a:1 r:3] [f a:2 r:2] [d a:3 r:2] [] [] [] [] data bitmap 11110000 data [(.,0) (..,0) (t,1) (y,2) (v,3)] [(.,1) (..,0) (c,2)] [o] [(.,3) (..,0)] [] [] [] []

    1. create("/y")
    2. link("/y", "/t/c")
    3. fd=open("/y"), write(fd), close(fd)
    4. mkdir("/v")