Skip to content

Latest commit

 

History

History
166 lines (95 loc) · 11.4 KB

OS_EXAM_2018_FINAL.md

File metadata and controls

166 lines (95 loc) · 11.4 KB

OS_EXAM_2018_FINAL

  1. 运行在内核态的内核线程共享操作系统内核态中的一个页表。对

  2. 操作系统处于安全状态，一定没有死锁;操作系统处于不安全状态，可能出现死锁。

    答：×。处于安全状态是指系统能按某种顺序如<P1,P2,…,Pn>(称<P1,P2,…Pn>序列为安全序列)，来为每个进程分配其所需资源，直到最大需求，使每个进程都可顺序完成。 如果处于安全状态，但不按照安全序列来分配资源，也可能进入死锁状态。

  3. 80386取指地址是base+eip，base是隐藏寄存器，初始化为0xffff0000，eip初始化为0xfff0，故执行的第一条指令是0xfffffff0。√。根据ucore_docs P106:

  4. 由于符号链接(软链接)实际上是一类特殊的文件，它的内容就是其所指向的文件或目录的路径，所以符号链接可以指向一个不存在的文件或目录。

    答： 对。文件的符号链接（SYMLINKD），如没有参数指定，则创建文件的符号链接，删除文件链接不影响目标文件，且创建链接时允许目标文件不存在；目录的符号链接（SYMLINKD） /D该参数可以创建目录的符号链接，删除目录链接不会影响目标目录，且创建链接时允许目标目录不存在；

  5. 文件系统中，用于存储“文件访问控制信息”的合理位置是文件分配表。

    答： ×。应该是文件控制块FCB。

  6. 在ucore for x86-32中，子进程通过sys_exit()执行进程退出时，ucore kernel会先释放子进程自身内核堆栈和进程控制块等，再唤醒父进程(或initproc)，最后执行iret返回。

    答：×。子进程的内核栈和进程控制块是由父进程帮忙收回的。

  7. 在完成lab1的过程中，了解到在80386保护模式下，如果产生了外部中断，CPU需要开始保存当前被打断的执行现场，以便于将来恢复被打断的程序继续执行。这需要利用栈来保存相关现场信息，即依次压入当前被打断控制流涉及到的(__17.1 __)、(__17.2 __)、(__17.3 __)等具体的硬件信息。

    通用寄存器，EFLAGS，CS，EIP等

  8. 在完成lab2的过程中，需要了解x86-32的内存大小与布局，页机制，页表结构等。硬件模拟器提供了128MB的物理内存，如ucore kernel需要通过页表管理整个128MB的物理内存，则页表总共需要占用(__18.1 __)KB的内存空间。

    答：128。一个页面4KB，共有128MB/4KB=2^15 个页面，也就是2^15 个页表项，每个页表项占4B，故需要2^15 *4B =128KB的内存空间。（页面大小4KB，页表项4B）

  9. 在完成lab3的过程中，ucore操作系统在页机制基础上，并利用异常机制建立了虚存管理策略与机制。在产生页面访问错误异常时，CPU直接把表示页访问异常类型的值(简称页访问异常错误码，errorCode)保存在(__19.1 __)中。ucore通过 x86-32CPU 中的(__19.2 __)寄存器 可以获得发生页面访问错误异常时的线性地址。

    中断栈；CR2

  10. 在完成lab4/5的过程中，了解到操作系统管理内核线程或用户进程的一个关键数据结构是 (__20.1 __)，其中包含了(__20.2 __)，用于进程/线程切换涉及的保存与恢复进程/线程上下文，还包含了(__20.3 __)，用于用户态/特权态切换涉及被中断/异常打断的执行上下文。

    proc_struct；struct context context；struct trapframe* tf；

    进程控制块；进程上下文信息；中断栈的指针；

  11. 在完成lab6的过程中，小强发现执行测试时调度过程的显示结果很不稳定，通过与同学交流， 发现是由于自己在windows中建立了一个virtualbox虚拟机环境，在virtualbox虚拟机环境下， 再执行qemu模拟器导致ucore的实际上执行时间变动很大。为减少这种变动，小强采取了 (__21.1 __)【不超过20个字】的方法，改善了此问题，并取得了稳定的实验结果。

    make run-priority

  12. 在完成lab7的过程中，小强发现本实验主要通过建立(__22.1 __)机制来完成信号量机制，主要通过建立(__22.2 __)机制来完成管程机制，且此管程的实现采用的是Mesa、Hoare、Brinch Hanson 三种语义方式中的(__22.3 __)语义方式。

    屏蔽中断；等待队列（条件变量）；

    Hoare管程低效（进程A执行signal，会唤醒进程B，而导致进程A睡眠，符合Hoare这种语义方式。）

    Hansen管程：当前执行进程更优先，效率更高。

    相比Hoare管程，Mesa对条件变量至少多了一次额外的检测，但是不需要进程的切换，且对等待进程在notify之后何时运行没有任何限制，所以Mesa管程比Hoare管程要简单高效些

  13. 在完成lab8的过程中，小强发现ucore设计了文件系统抽象层–(__23.1 __)，它提供一个统一 的文件系统操作界面和编程接口，可支持不同的具体文件系统。在对具体文件系统SFS的分析过程中，小强发现SFS在硬盘上的主要内容包括(__23.2 __)，记录了所在硬盘的扇区总数量和未用扇区数量;还有(__23.3 __)，记录了已用扇区和未用扇区的位置;(__23.4 __)记录了根目录的内容。

    VFS；superblock；freemap；root-dir inode；

  14. 现有一个RAID磁盘阵列，包含6个磁盘，每个磁盘大小都是2TB，最大写入速度 200 MB/s， 最大读取速度 250 MB/s 的硬盘。用它们分别组成RAID级分别为0、1和5。假设在理想情况下(无中断、异常、预先缓存等外在干扰因素等)，请回答下列问题。 A) 用它们组成的RAID0阵列的总可用空间为 (__24.1 __)，最大写入速度为 (__24.2 __)， 最大读取速度为 (__24.3 __); B) 用它们组成的RAID1阵列的总可用空间为 (__24.4 __)，最大写入速度为 (__24.5 __)，最大读取速度为 (__24.6 __); C) 用它们组成的RAID5阵列的总可用空间为 (__24.7 __)，最大写入速度为 (__24.8 __)，最大读取速度为 (__24.9 __)。

    A. 12TB；1200MB；1500MB；

    B. 6TB；600MB；1500MB；

    C. 10TB；1000MB；1250MB；

  15. 假定在X86-32平台上的ucore的虚拟存储系统中，采用4KB页大小和二级页表结构。请补全功 能为通过虚拟地址找到对应的页表项的get_pte()函数。

    可能需要用到的函数有: page2pa() 获取物理页对应的物理地址; page2ppn() 获取物理页对应的物理页号; pa2page() 获取物理页号对应的物理页数据结构指针;

    page2kva() 获取物理页对应内核虚拟地址;

    kva2page() 从内核虚拟地址获取物理页数据结构指针;

    可能用到的宏有: memset(p,v,n) 对指定地址p开始的长度为n的内存区域进行赋值v

    PDX(la) 虚拟地址la对应的页目录项序号; KADDR(pa) 物理地址pa对应的内核虚拟地址; PADDR(kva) 虚拟地址kva对应的物理地址; PTE_P:存在标志位 PTE_W:可修改标志位 PTE_U:用户可访问标志位

    pte_t *get_pte(pde_t *pgdir, uintptr_t la, bool create){
    pde_t *pdep = __25.1 __;	// (1) find page directory entry
    if(!*pdep & __25.2 __){		// (2) check if entry is not present
       struct Page *page;
       // (3) check if creating is needed, then alloc page for page table
       if(!create || (page = alloc()) == NULL){	
           return NULL;
       }
       set_page_ref(page,1);				// (4) set page reference
       uintptr_t pa = __25.3 __;		// (5) get linear address of page
       memset(__25.4 __,0, PGSIZE);	// (6) clear page content using memset
       *pdep =__25.5 __;						// (7) set page directory entry's permission
		}
    return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)];	// (8) return page table entry
}

/*
25.1 : &pgdir[PDX(la)]
25.2 : PTE_P
25.3 : page2pa(page)
25.4 : KADDR(pa)
25.5 : pa | PTE_P | PTE_W | PTE_U
*/

  16. (18分)假定某文件系统采用多级索引分配的方法，普通文件的索引节点(inode)中包括一个 占8字节的文件长度字段和15个占4字节的数据块指针(即块号)。其中，前12个是直接索引块(direct block)的指针，第13个是1级间接索引块(indirect block)指针，第14个是2级间接 索引块(doubly indirect block)指针，第15个是3级间接索引块(triply indirect block)指针。 间接索引块中连续存放占4字节的数据块指针。数据块以及间接块的大小为4KB。请回答下列问题。

    A) 计算该文件系统理论上能够支持的单个文件最大长度。

    4KB / 4B = 1K个指针

    (12 + 1K + 1M + 1G) * 4KB ~= 4TB

    B) 假设读取磁盘上一个块需要1ms，块缓存机制只缓存文件的索引节点，并且所有需要的索引节点都已加载到缓存;不缓存数据块以及间接索引块;读取文件操作不会发生写入操作，访问内存的时间忽略不计。计算从头到尾读取一个8MB(即2048块)文件 需要的时间。

    2048块文件 = 12个直接索引 + 1024个一级间接 + 1012个二级索引（二级指向一级）

    耗时：2048 * 1ms + 0（直接索引缓存） + 1 * 1024（一个一级） + 2 * 1024 （读一个二级再读一个一级） = 5096ms

    12个直接索引已在缓存中，2048块其中有1024块属于一级间接索引指向的块中，1012块在二级间接索引的第一个索引指向的块中。2048块读取首先需要2048ms，再加上读取一级间接索引和二级间接索引分别需要1024ms和1012*2ms（因为不缓存间接索引块，所以每次都要从磁盘中先去读间接索引块，才能再去找数据块），总共需要5096ms。

    C) 假设读取磁盘上一个块需要1ms，块缓存机制缓存文件的索引节点、数据块和间接索引块，并且所有需要的索引节点都已加载到缓存;开始时缓存没有加载任何数据块或者间接块;读取文件操作不会发生写入操作，访问内存的时间忽略不计。计算从头到尾读取一个8MB(即2048块)文件需要的时间。

    与B的区别在于：“块缓存机制缓存文件的索引节点、数据块和间接索引块”。所以不需要反复从磁盘中去读间接块的内容，只要读过一次，间接块就会被缓存。所以时间为2048+3=2051ms。

  17. 设lab6中使用Stride调度算法，取BIGSTRIDE=100，假定各个进程的stride初始化为0。 (注:lab6中的stride(32位整数，当前总共走了多少) 和pass (32位整数，每一次走多少 pass= BIGSTRIDE/priority, 100>priority>1)的含义和论文原文含义相反)请回答下列问题。 A) 如果不考虑进程stride的值的溢出，那么对于任意两个进程A、B的stride值SA和SB，应当恒有abs(SA-SB) ≤ (__1 __) ，为什么? B) 考虑到abs(SA-SB)这一性质，假设stride值存在溢出，可将stride值的更新变为: stride = (stride + BIGSTRIDE/priority) mod n 那么，只要n> (__2 __) ，那么stride算法就可以正常运行，为什么?

    A.PASS_MAX

    如何证明 STRIDE_MAX – STRIDE_MIN <= PASS_MAX？

    • 假如该命题不成立，则可以知道就绪队列在上一次找出用于执行的进程的时候，假如选择的进程是P，那么存在另外一个就绪的进程P'，并且有P'的stride比P严格地小，这也就说明上一次调度出了问题，这和stride算法的设计是相违背的；因此通过反证法证明了上述命题的成立；

    BIGSTRIDE