Skip to content

Latest commit

 

History

History
142 lines (65 loc) · 8.11 KB

OS_EXAM_2020.md

File metadata and controls

142 lines (65 loc) · 8.11 KB

OS_exam

2020

  1. 为了形成临界区，在单核机器上可以使用关中断，在多核机器上可以使用自旋锁。在单核机器中使用自旋锁可以吗?为什么?

    非抢占：单核状态下，当一个进程（或线程）使用自旋锁，在没有执行完毕之前没有其他的进程抢占临界资源，时间片到了仍旧是当前进程继续执行。故自旋锁没有意义

    抢占式：单核状态下，获取自旋锁后可能会发生中断，若中断处理程序去访问自旋锁所保护的资源，则会发生死锁。因此在自旋锁使用前关中断，退化至非抢占状态。

  2. 为了形成临界区，在单核机器上可以使用关中断，在多核机器上可以使用自旋锁。 请回答下列问题。在多核机器上使用关中断可以吗?为什么?

    多核cpu关中断仅对该cpu有效，其他cpu仍旧可以访问共享内存，故使用关中断不可以。

  3. 什么是孤儿进程?

    一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。

  4. 什么是僵尸进程？

    一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵尸进程。

  5. 请描述在何种情况下有进程会成为孤儿进程

    子进程死亡需要父进程来处理，那么意味着正常的进程应该是子进程先于父进程死亡。当父进程先于子进程死亡时，子进程死亡时无父进程处理，最终将被系统（init）回收。

  6. 请描述在何种情况下有进程会成为僵尸进程

    子进程先于父进程退出后，子进程的PCB需要其父进程释放，但是父进程并没有释放子进程的PCB（没有wait或waitpid）来获取子进程的状态信息，子进程的PCB依旧保存在系统中。

  7. 在多处理机调度中，就绪任务队列的维护有两种策略: 单队列:使用无锁数据结构，维护一个全局队列 多队列:每个核有一个自己的局部队列 这两种方案相比，分别有什么好处和不足?(回答字数 150 字)

    TBD

  8. 在多处理机调度中，就绪任务队列的维护有两种策略: 单队列:使用无锁数据结构，维护一个全局队列 多队列:每个核有一个自己的局部队列 提出一种新的改进方案，避免这两种方案各自的不足之处。(回答字数 150 字)

    TBD

  9. 由于内核实现代码的错误，导致内核在执行缺页(page fault)处理例程(响应用户进程导致的第一次缺页异常)的过程中再次(第二次)发生缺页异常。假定该内核其他部分编程正确且支持内核态中断。请描述第二次缺页异常产生之后的内核执行过程，以及从第一次缺页异常产生后开始的整个过程中内核栈变化和寄存器的状态变化的情况。(回答字数200字)

    TBD

  10. 假定在一台装有类 UNIX 通用操作系统的单核计算机上，任意一个中断从产生到响应处理结束，耗时 1 ms;OS 调度算法是时间片轮转调度算法，调度时间片为 100 ms ;时钟中断周期 10 ms;系统中有 3 个处于就绪态的进程。一个程序从十点整开始运行，恰好 60,000 ms 后运行结束，在运行过程中产生了 6,100 次中断。该程序的实际占用 CPU 的真实运行时间是否可以计算得出?若可以， 给出计算过程和具体结果(单位 ms ，保留整数);若不可以，给出理由。(回答字数 150 字)

    TBD

  11. 关于局部页面替换算法:最优算法(OPT)/先进先出算法(FIFO)/最近最久未使用算法 (LRU)/时钟(clock)页面置换算法。请问，什么是 Belady 现象?在上述四种算法中，哪些算法可能存在 Belady 现象?(回答字数100字)

    Belady现象：在分页式虚拟存储器管理中，发生缺页时的置换算法采用某些算法时，如果对一个进程未分配它所要求的全部页面，可能出现分配的物理页面数增加,缺页率反而升高的异常现象。

    FIFO会产生Belady现象，Clock在某些情况下会退化至FIFO同样导致Belady现象。

  13. 请问，设一个页面访问序列为 0,1,4,2,3,4,1,0,3,2，且物理页帧中最多能容纳 4 个页面， 初始时物理页帧为空，请用FIFO 算法进行模拟，给出每一次访问的情况以及访问后物理页帧 的状态，最终给出总缺页次数。

    总缺页：6

  14. 请问，设一个页面访问序列为 0,1,4,2,3,4,1,0,3,2，且物理页帧中最多能容纳 4 个页面， 初始时物理页帧为空，请用 LRU 算法进行模拟，给出每一次访问的情况以及访问后物理页帧 的状态，最终给出总缺页次数。

    总缺页：7

  15. 请问，从应用程序和操作系统在通用 CPU 上实际运行的角度看，如果操作系统采用 LRU 页面 置换算法，那相比于采用 FIFO 页面置换算法，其在整体系统执行效率上的结果上一定更好 吗?说明理由。(回答字数 150 字)

    LRU算法性能好，但是系统开销大；FIFO开销小但可能会产生Belady现象。由于LRU根据最近最久未访问换出页面，当实际运行的程序存在局部性，则LRU较FIFO算法执行效率较好；反之没有局部性，则LRU算法不如FIFO。

  16. 用 TestAndSet 原子指令，实现自旋锁。请用类 C 伪码形式补全下面代码中的 lock 结构和 获取锁lock_acquire()、释放锁lock_release() 函数。

    struct lock{
  bool locked;
};
struct lock spin;

void lock_acquire(struct lock* spin){
  while(!TestAndSet(spin->locked));
  return;
}

void lock_release(struct lock* spin){
  while(TestAndSet(spin->locked)){
    spin->locked = false;
    break;
  }
  return;
}

  17. 使用 FetchAndAdd 原子指令原语可实现一种 ticket lock，类 C 伪码形式的代码如下。 试分析这种锁与自旋锁相比有何优势? (回答字数 150 字)

    排队等待，不会饥饿

  18. 21-22.(共 4 分)

    假定在某基于二级页表的虚拟页式存储，具有 4GB 物理内存的 32 位计算机系统下，32 位虚 拟地址从高到低被划分如下， 10 位页目录序号、10 位页表序号和 12 位页内偏移。页目录 和页表大小均为 4096 字节，页目录项和页表项大小为 4 字节。使用自映射方式组织页表。 本题表述中，用 flags 表示页表/页目录项的各种标志位，占低 12 位，且 CPU 不基于 flags的信息来判断某项是页表项还是页目录项。要求回答中所有地址均使用用十六进制表 示，如 0x1edc8000。

    假定页目录起始物理地址是 0x1edc8000，并且物理地址 0x1edc8ff0 (=0x1edc8000+1020*4) 开始的页目录项是自映射项。则此处自映射项的内容是 ________________________ ___ | flags，该自映射项的虚拟地址是________________________ ____?

    0x1edc8000 = 0001 1110 1011 1010 1000 0000 0000 0000

    0x1edc8ff0 = 0001 1110 1011 1010 1000 1111 1111 0000

    内容 : 0x1edc8 | flag

    虚拟地址：??

    23-24.(共 4 分)

    假定在某基于二级页表的虚拟页式存储，具有 4GB 物理内存的 32 位计算机系统下，32 位虚 拟地址从高到低被划分如下， 10 位页目录序号、10 位页表序号和 12 位页内偏移。页目录 和页表大小均为 4096 字节，页目录项和页表项大小为 4 字节。使用自映射方式组织页表。 本题表述中，用 flags 表示页表/页目录项的各种标志位，占低 12 位，且 CPU 不基于 flags的信息来判断某项是页表项还是页目录项。要求回答中所有地址均使用用十六进制表 示，如 0x1edc8000。

    假定虚拟地址 0x8af4b000 映射到物理地址 0x01572000，则位于虚拟地址 _______________________ ___ 的页表项内容应该是 0x01572000 | flags。位于 0xff1bc500 的页表项，它指向的页的虚拟地址起始于 _______________________ ___。

  19. asd