操作系统介绍

有三个主要部分：虚拟化（virtualization）、并发（concurrency）、持久性（persistence）

题目

一、（共10分）操作系统的设计目标有哪些？

  • 抽象性：对硬件资源进行抽象，提供统一接口，简化程序开发；
  • 并发性：支持多个程序同时运行，提高系统吞吐；
  • 虚拟化：如虚拟内存、虚拟 CPU，使用户感觉拥有独占资源；
  • 资源管理与调度：高效分配 CPU、内存、磁盘等资源，提升资源利用率；
  • 安全与保护：防止程序互相干扰，保护用户数据；
  • 用户友好性：提供简洁易用的接口和良好的使用体验。

六、（ 共 10 分）UNIX 系统采用了一种非常有趣的创建新进程的方式，即通过一对系统调用：
fork()和 exec()，解释说明 fork()和 exec()的作用（5 分），以 UNIX 的 Shell 为例说明为什么设
计这两个系统调用（5分）。

  • fork()创建一个和父进程几乎相同的子进程，除了PID等一些信息不同其它完全一样。
  • exec()用新的程序替换掉当前程序执行的内容，不改变其PID等信息。
    UNIX SHELL启动一个新程序的时候，先通过fork()创建一个子进程，再通过exec()加载并执行用户命令，这样父进程（shell）仍能工作，分离设计提供灵活性。

七、操作系统虚拟化CPU的机制是受限直接执行，为了实现这个机制，例举的硬件提供了哪些支持？简要说明操作系统如何利用硬件来实现LDE。
硬件

  • 模式划分：被划分为用户态和内核态
  • 中断机制：支持外设中断和系统调用陷入内核态。
  • 定时器中断：防止单一进程长时间占用CPU资源，实现抢占功能。
  • 内存保护机制：通过页表和地址空间隔离来保护内核
  • 指令限制：一些特权指令如（I/O）只能被内核态执行。

操作系统可以将进程调度执行化为内核态以及用户态，用户态不能执行一些特权指令比如I/O，必须通过陷阱表的陷阱指令陷入内核态，并提供了从陷入返回指令回到用户态。操作系统还提供了中断机制，防止单一进程过度占用资源，而导致其他进程出现饥饿。结合内存保护，防止非法访问内核或其他进程内存区域，从而实现虚拟化CPU且保证系统安全和稳定。还有上下文切换，通过寄存器保存当前进程的值，然后读取另一个进程的寄存器所存储的值进行运行。

1.三态：运行、就绪、阻塞
2.错误，进程在一个时刻只能处于一种状态。
3.错误，单核情况下，操作系统和进程需要通过时间片轮转轮流使用CPU，不会同时运行，操作系统也是一个程序。

程序运行

正在运行的程序会做一件非常简单的事情：从内存中读取指令，解码，并执行它，然后接着执行下一条指令。
总结为Fetch 、 Decode 、 Execute

操作系统可以让程序共享内存、与设备交互、运行的更容易，操作系统确保系统既易于使用、又正确高效运行。为了做到这一点，采用了虚拟化的技术，在一些硬件的帮助下，操作系统负责提供虚拟化，使得单个（或一小部分）CPU可以看似认为有无限数量的CPU，从而可以同时运行多个程序，但问题就是在调度，在特定时间运行，该运行哪个？所以操作系统也承担了**资源管理器（resource manager）**的角色。

虚拟化

  • 虚拟内存，每个进程访问自己的私有虚拟地址空间，操作系统以某种方式映射到机器的物理内存上，打游戏的时候每个角色都有一个背包，背包的0号格子可能装有不同的东西，但并没有冲突，操作系统把编号0分到了不同的内存地址上。
    每个程序都有自己的“背包”（内存空间），从地址 0 开始。但实际的物理内存只有一块
    程序 A 的地址 0x1000 → 实际是 物理地址 0xA000
    程序 B 的地址 0x1000 → 实际是 物理地址 0xC000
    这就是虚拟内存：给程序看的假地址，每个程序都以为自己独占整片内存，其实操作系统做了“背后映射”。

  • 操作系统通过时间片轮转（time-sharing）技术虚拟化 CPU，将 CPU 时间划分成小片段，每次只分配给一个进程运行一个时间片，然后切换到其他进程，从而营造出“多个进程同时运行”的假象。这种时分复用机制使得单核 CPU 也能实现多任务并发。其代价是频繁的上下文切换带来一定的性能开销。

  • 进程三态：运行、阻塞、就绪

  • fork()系统调用的返回值：父进程获得子进程的PID，子进程的返回值是0

受限直接执行

有两种模式：用户模式和内核模式，用户模式下功能受限，如I/O请求无法发送，但可以通过特殊的陷阱（trap）指令从用户模式进入内核模式，进入内核后系统就可以执行任何需要的特权操作，执行完成后，操作系统调用一个特殊的从陷阱返回(return-from-trap)指令回到用户模式。

多级反馈队列MLFQ

五条规则

  • 任务A的优先级高于任务B，先执行任务A，再执行任务B（保证高优先级任务的响应速度，提高系统的实时性。）
  • 任务A的优先级等于任务B，以轮询的方式执行任务A、B（在同等级中实现公平性，防止个别任务长期占用CPU。）

    Round-Robin
  • 新任务进入队列，放在最高优先级的队列执行（提高新任务启动速度，增强系统交互性。）
  • 一旦工作用完了其在某一层中的时间配额，无论中间主动放弃了多少次CPU，就降低其优先级。（避免任务通过频繁放弃CPU来“欺骗”调度器长期占用高优先级。）
  • 经过一段时间S后，就将所有任务重新加入到最高优先级（避免低优先级任务长时间得不到执行，防止饥饿现象。）

调度-比例份额

彩票数(ticket)代表了进程(或用户或其他)占有某个资源的份额，一个进程拥有的彩票数占总彩票数的百分比，就是它占有资源的份额。拥有的彩票数越多，那被调度的概率也就越大。
三大特性：

  • 彩票货币
  • 彩票转让：一个进程临时将自己的彩票转移给另一个进程
  • 彩票通胀：一个进程的彩票数可以临时提升或降低告诉操作系统我需要CPU。

步长调度：其实就是时间片轮转，执行完当前的步长然后去看看队列中现在谁的总步长最短，就去执行它，如果所有人的步长都相同了，那就随机抽一个去执行。

内存管理

如何将内存中的逻辑地址转换为物理地址？

  1. 绝对装入
  2. 静态重定位
  3. 动态重定位
  • 基址寄存器 + 逻辑地址 = 真实地址 （基址寻址） 采用动态重定位时允许程序在内存中发生移动

虚拟内存

单片机没有OS，每一次运行都需要重新烧录，单片机的CPU直接操作内存的物理地址。在单片机的情况下不可能同时运行两个程序，因为内存地址会被覆盖。
操作系统通过虚拟内存来解决这个问题。
操作系统通过为每一个进程分配一套独立的虚拟地址，进程在自己的虚拟地址里进行操作，最后OS通过映射关系映射到不同的物理地址上。进程持有的虚拟地址会通过CPU芯片上的MMU（Memory Management Unit）来转换成物理地址。

操作系统是如何管理虚拟内存和物理内存之间的关系？
主要有两种，内存分段和内存分页。

内存分段

程序是由若干个逻辑分段组成的，如可用代码分段，数据分段，栈段，堆段组成，不同的段有不同的属性。
分段机制下的虚拟地址由两部分组成：段选择子和段内偏移量

  • 段选择子：保存在段寄存器内，最重要的是段号，用作段的索引，段表里面保存的是这个段的基地址、段的界限和特权等级等。
  • 段内偏移量：应位于0和段界限之间，如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址。

分段产生的两个问题：内存碎片和内存交换效率低

  • 游戏512MB
  • 浏览器128MB
  • 音乐256MB
    如果浏览器被关闭了，新的200MB的程序也无法写入，出现了内存外部碎片的问题。此时可以通过内存交换来解决：
  • 可以把音乐程序占用的那256MB内存写到硬盘上，然后再从硬盘上读回来到内存里。不过再读回的时候，我们不能装载回原来的位置，而是紧紧跟着那已经被占用了的512MB内存后面。这样就能空缺出连续的256MB空间，于是新的200MB程序就可以装载进来。

    分段为什么导致内存交换效率低？

  • 对于多进程系统，外部碎片的产生很常见，就不得不使用Swap内存区域，但是硬盘上的访问速度远比内存低，每一次交换都需要把一大段连续内存数据写到硬盘上。

内存分页

为了解决内存分段的交换效率低以及内存碎片问题，提出了内存分页。

  • 将内存空间分为一个个大小相等的分区，每个分区就是一个页框==页帧==物理块==物理页面
  • 将进程的逻辑地址空间也分成与页框大小相等的一个个部分，每个部分称为一个页或页面
    进程的页面和内存的页框是一一对应的，大小相等。

    每个进程都有一张页表，一个进程对应着一张页表，每个页表项由页号和块号组成，页表记录进程页面和实际存放的内存块之间的映射关系

    前12位就代表在几号页，后20位就是页内偏移量

期末复习（以题目为导向）

一、 （20分，前3小题每题4分，第4小题8分）

  1. 多核处理器调度采用单队列调度和多队列调度，分别存在什么样的问题，如何处理？
    • 单队列调度：易于实现，负载均衡好，但线程频繁迁移会导致缓存未命中率提高，对策，采用核亲和性（CPU affinity）减少迁移
    • 多队列调度：缓存利用率高，但容易负载不均；对策，引入迁移实现动态负载均衡，让无任务的CPU上有任务。工作窃取（work stealing）：工作量较少的队列偷偷看其他队列是否比自己工作多，如果其他队列的工作比自己更满，就从他们那里窃取一些工作过来。
  2. 简要分析虚拟内存系统的三个主要目标。
    1. 扩展内存容量：
    2. 内存保护：
    3. 内存共享 ：
  3. 什么是死锁？死锁产生需要哪四个必要条件？
  • 死锁：多线程争夺共享资源，相互等待，然后永久阻塞。
    1. 互斥：资源一次只能被一个资源占有
    2. 占有并等待：已占有资源的进程可以申请新资源
    3. 不可抢占：资源不能被强制回收
    4. 循环等待：形成资源等待的闭环

为什么不能只靠offset或pfn？

  • 没有VPN，就不知道在哪一页；
  • 没有PFN，就不知道在哪一个内存块；
  • 没有OFFSET，就不知道在内存块的哪一个地方。
  • OFFSET，就是页的大小，如在32位的地址空间里一页是4KB，那offset就是pow(2,12);剩下的20位就是VPN，低位掩码
    二、假设虚拟地址有32位，页大小为4KB，回答下列问题：
  1. 算法中第1行VPN_MASK、SHIFT的值分别是多少？VPN的取值范围是多少？第 5 行的OFFSET_MASK的值是多少？
  • VPN_MASK和OFFSET_MASK是掩码，用于提取VPN以及OFFSET的，32位是由20位的VPN + 12位的偏移量构成的，所以VPN_MASK前20位全1，后12位全0；OFFSET_MASK前20位为0，后12位为1。 SHIFT 是指页内偏移位数，即页大小的对数，用来做地址右移或左移运算。VPN的取值范围是0 - pow(2,20)-1；
  1. 从算法中，你知道TLB、页表中分别包含哪些内容吗？
  • TLB中有VPN（页号），PFN（页帧号），ProtectBits（访问权限，比如读/写/执行），Valid 位（有时也在）；页表中含PFN，ProtectBits，valid位，访问位，修改位；
  1. 据你所知，软件（操作系统）管理的TLB控制流算法与上述算法有什么区别？
  • **硬件管理（如题中）：**TLB 查找、缺页中断、页表查找都由硬件完成，操作系统只负责处理例外情况（如页不存在）。
  • **软件管理（如 SPARC 架构）：**TLB 缺失时硬件产生异常，由操作系统查页表并手动更新TLB，增加灵活性，但效率较低。
  1. MIPS R4000 支持32位地址空间，用户地址只占地址空间的一半，可以支持最多64GB物理内存，页大小为4KB，那么其VPN、PFN分别是多少位？
  • 32位是4GB，但题目提到了用户地址只占地址空间的一半，所以用户空间有pow(2,31)，用地址空间大小/页大小 = VPN，31-12 = 19；64GB是pow(2,36)，VPN = pow(2,36) / pow(2,12) = pow(2,24);PFN就是24位
  • 所以VPN是19位，PFN是24位。

六、（15分）对于如图所示的1个简单文件系统结构，包括一个 inode 位图（inode bitmap，
只有 8 位，每个 inode 一个），一个数据块位图（data bitmap，也是 8 位，每个数据块
一个），inode（总共 8 个，编号为 0 到 7，分布在 4 个块上），以及数据块（总共 8 个，
编号为 0～7），数据块为4KB大小，试回答如下问题：

  1. 该系统最大支持多少个文件，为什么？
  • 一个文件对应一个inode，inode bitmap有8位 -> 最多支持8个inode ->最多支持八个文件。
    （2）如果inode中支持一级间接指针，该系统中单文件最大可存储多大的内容？（提示：需分情况讨论）

（3）假设要打开图中的灰色inode（第2个）所指示的文件并顺序读取所有数据，请按时间顺序列出对文件系统数据结构的所有操作。（假设在OS中该文件的inode号已知，Da数据块是文件的第1块，Db为第2块）
七、文件系统访问（15分）
（1）简要说明文件系统中inode的用途；inode一般包含哪些信息，试列举至少五个进行说明；

  • 有inodoe编号，文件的创建时间，文件的修改时间，文件访问权限，文件的大小，文件的数据块指针（用来指向数据存放的地方）
    （2）假设要读取/foo/bar路径下的bar文件，首先通过open(“/foo/bar”,O_RDONLY)打开文件，随后再使用read操作读取文件内容；请问：执行open和read操作时，进程与文件系统之间有哪些数据交互？可以使用表格或文字形式进行描述。
  • open：系统解析路径 /foo/bar ，通过目录项查找bar的inode，加载其元数据，建立文件描述符
  • read：系统根据fd找到file结构，定位inode，通过页缓存或磁盘读取数据块，将数据拷贝到用户空间中。

八、简述I/O设备标准协议的执行步骤，请分析其利弊并简要给出解决方案。（8分）

  1. 设备准备数据

  2. 设备向CPU发送中断信号

  3. CPU保存上下文，进入中断处理程序

  4. 驱动程序读取设备状态与数据

  5. 数据转入缓存区或用户空间

  6. CPU恢复上下文，继续原程序。

  7. 彩票调度和步长调度采用随机思想有其优势，但没有广泛使用，分析其原因。

  • 一个原因是这两种方式都不能很好的适应I/O，另一个原因是票数分配问题并没有具体的解决方式，不知道一个进程应该有多少彩票数。
  1. 虚拟内存的三个目标？
  • 透明（transparency）：操作系统实现虚拟内存的方式，应该让运行的程序看不见。
  • 效率 ：操作系统应该追求虚拟化尽可能高效(efficient)，包括时间上(即不会使程序运行得更慢)和空间上
  • 保护：操作系统应确保进程受到保护，不会受其他进程影响，操作系统本身也不会受进程影响。
  1. 什么是文件系统的崩溃一致性问题？
  • 当你想持久化数据的时候，突然被拔电了，数据没有成功写入。