Cuckoo!
0%

CS334 操作系统 期末复习

Posted on In
如果你觉得可笑就笑吧，很快就轮到操作系统嘲笑你了。——Three Easy Pieces

$\huge\text{Outline}$

  1. 操作系统导论
  2. 操作系统基础
  3. 进程
  4. CPU Scheduling
  5. Synchronization
  6. Address Translation
  7. Paging
  8. Demand Paging
  9. Linux Memory Management
  10. IO
  11. Storage
  12. File System

Appendix: Quiz

Chapter 1 - 操作系统导论

计算机系统的结构:

  • 硬件
    • 提供基础计算资源
    • CPU, 内存, IO
  • 操作系统
    • 控制、协调 多应用/多用户 对于硬件的使用
  • 应用程序
    • 定义系统资源的使用方法，用于解决计算问题
  • 用户
    • 人、机器、其他计算机…

操作系统:

使计算机正确、高效运行且易于使用的软件集。

A group of software that makes the computer operate correctly and efficiently in an easy-to-use manner.

操作系统包含一个称为内核的程序

  • 管理所有物理设备：CPU、RAM、硬盘……
  • 提供诸如系统调用的函数

操作系统包含其他的”helper”程序

  • 例如shell，提供了命令行用户接口
  • 例如GUI，提供了有图标的用户友好的接口
  • 例如浏览器，提供网页浏览服务

操作系统是资源管理器

  • 管理CPU、内存、硬盘、I/O设备
  • 管控公平高效的资源使用，协调资源冲突

操作系统是控制程序

  • 控制程序的执行，避免错误或对计算机的不当使用

操作系统都做些什么:

虚拟化 Virtualization

  • CPU虚拟化：单个CPU上运行多个程序
  • 内存虚拟化：为进程(程序)分配相互独立的虚拟内存地址空间

并发性 Concurrency

  • 运行多线程程序，保证其正确运行

持久化 Persistence

  • 从RAM写入数据到持久内存
  • 性能，崩溃恢复能力

操作系统的历史:

……

进程:

进程(process)是在运行中的程序(program)

  • 程序是

进程需要资源来完成任务

  • CPU、内存、I/O、文件
  • 进程终止，需要回收所有可再利用资源

进程顺序执行指令，一次一个，直到结束

  • 单线程进程由PC指定下一条执行的指令位置
  • 多线程进程的每个线程都有一个PC

一般而言，计算机系统有多个进程，若干用户，若干操作系统在一个或多个CPU上运行

  • 通过在进程/线程之间复用(multiplexing)CPU来实现并发性

进程管理:

创建/删除用户和系统进程

暂停/恢复进程

为进程同步(process synchronization)提供机制

为进程通信(process communication)提供机制

为死锁处理(deadlock handling)提供机制

内存：

动态随机访问内存DRAM

CPU在执行时只和主存交互

  • 处理前后数据都在内存里
  • 执行的指令都在内存里

操作系统管理内核和进程的主存，哪个进程用哪块内存

内存管理:

内存管理决定，当优化CPU利用率、回应用户时内存中存储什么

内存管理活动

  • 记录哪些内存正在被哪些进程使用
  • 决定哪些进程和数据要移入/移出内粗
  • 按需申请/释放内存空间

存储管理:

操作系统提供信息存储的统一、逻辑的情况

  • 将物理属性抽象为逻辑存储单元：文件

  • 每个介质都由设备控制

    可变的性质包括访存速度、容量、数据传输率、访问方法(顺序/随机访问)

文件系统管理

  • 文件通常分目录管理
  • 访问控制：决定谁能访问什么
  • 操作系统活动，包括：
    • 创建/删除文件和目录
    • 操作文件和目录的原语(primitives)
    • 将文件映射到二级存储
    • 将文件备份到稳定存储介质

I/O 子系统:

操作系统的一个目的是向用户隐藏硬件设备的特殊性

  • 包含I/O的内存管理
    • 缓存(buffering)，传输时临时存储数据
    • 缓存(caching)，将部分数据放入高速缓存以提高性能
  • 通用的设备-驱动接口
  • 特殊硬件设备的驱动

保护与安全:

保护：由操作系统定义，控制进程或用户对资源的访问的机制

安全：抵御内外对系统的攻击

操作系统决定哪个用户能做什么

  • 用户标识符：用户名，ID
  • 将用户ID与该用户的所有文件、进程联系起来，以控制访问
  • 组标识符(group ID)允许定义一组用户并管理控制权，与进程、文件相联系
  • 特权升级允许用户改变ID以获得更多权利

Chapter 2 - 操作系统基础

双模式操作(Dual-mode Operations):

硬件支持至少两种模式

  • 内核模式：运行内核代码
  • 用户模式：运行常规程序

为实现双模式操作，硬件提供：

  • 一个state比特位

  • 一些只能在内核模式执行的操作/行为

  • 用户态→内核态，设置系统模式，并保存用户PC

    操作系统将用户资源谨慎搁置，执行必要操作

  • 内核态→用户态，清除系统模式，并恢复用户PC

一些例子：

  • x86 Ring 0 对应内核态，Ring 3对应应用态
  • RISC-V User/Supervisor/Machine 三种模式，应用态-内核态-固件态

三种模式转换的情形:

  1. 系统调用(system call)

  • 进程请求系统服务

  • 类似函数调用，但在进程外

  • 系统函数没有地址可供调用
  • 向寄存器写入系统调用ID和参数，执行系统调用
  1. 中断(interrupt)
  • 外部异步事件触发上下文切换(context switch)，如时钟、I/O设备
  • 与用户进程独立
  1. 陷阱(trap)或异常(exception)
  • 进程的内部同步事件触发上下文切换，如段错误、除以0…

系统调用:

由操作系统提供的服务的程序接口，以高级语言编写

每个系统调用都会有一个ID，映射关系表由系统调用接口维护

系统调用接口 调用 操作系统内核中对应的系统调用，返回系统调用的状态及返回值

调用者无需了解具体实现，只需要遵守调用规则，理解调用功能即可

大多数操作系统接口的细节通过library API隐藏，对使用者不可见

由运行时支持库（run-time support library, 包含在编译器中的库中的一组功能）管理

系统调用类型:

  • 进程控制: fork, exit, wait
  • 文件管理: open, read, write, close
  • 设备管理: ioctl, read, write
  • 信息维护: getpid, alarm, sleep
  • 通信: pipe, shmget, mmap
  • 保护: chmod, umask, chown

异常和中断:

异常(同步)应对非正常状况

  • 将swapped-out页映射回memory内
  • 非法内存访问
  • 除以0……

中断(异步)抢占正常执行

  • 外部设备的通知
  • 抢占式调度
  • 另一个CPU的通知

处理异常和中断

  • 停止执行当前程序
  • 执行handler程序
  • 处理器通过中断描述符表(Interrupt Descriptor Table, IDT)访问handler
  • 每种中断对应一个数字

内核结构:

宏内核:

宏内核(Monolithic Kernel)是一个操作系统软件框架，拥有访问所有I/O设备、内存、硬件中断、CPU栈的权限

宏内核包含很多组件，例如内存子系统、I/O子系统等，通常很大

宏内核是Linux, Unix, MS-DOS的基础

微内核:

微内核(Micro Kernel)将操作系统功能外包给用户进程，灵活性、安全性、容错性增强

用户级服务器收到内核信任(通常以root身份运行)

保护机制保留在内核，资源管理转移到用户级服务器

代表性微内核操作系统：Mach, seL4

优点：

  • 内核响应速度更快：内核功能在可抢占的用户级进程种
  • 稳定性和安全性提高：操作系统中代码更少
  • 更好地支持并发性和分布式操作系统

缺点：

  • 需要更多进程间通信(IPC)，带来更多上下文切换，更慢

杂交内核:

杂交内核(Hybrid Kernel)是宏内核和微内核的结合，例：Windows

外内核:

外内核(Exokernel)将抽象与安全分开

  • 内核相当小：安全复用(security multiplexing)
  • Library OS作为进程运行：操作系统抽象化

优点：

  • 直接管理资源，高效
  • 易于进行新内核设计的实验

缺点：

  • 通常只是个概念

变种：nanokernel, picokernel

虚拟化和管理程序:

管理程序(Hypervisor, virtual machine manager/monitor, VMM)强调虚拟化和隔离

  • 操作系统可以在管理程序上几乎不做修改地运行
  • 不同虚拟机之间资源隔离
  • 微内核和外内核可用于实现管理程序

操作系统设计原则:

不同操作系统内部结构五花八门

  • 从设置目标和规格开始
  • 收到硬件选择和系统类型的影响

用户目标和系统目标

  • 用户目标：易于使用，易于上手，可靠安全高效
  • 系统目标：易于设计、实现、维护，灵活可靠无错，高效

操作系统区分开政策和机制

  • 政策(Policy)：哪个软件可以在什么时候访问什么资源
  • 机制(Mechanism)：政策是如何实现的
  • 分离政策和机制提供了灵活性，更换政策后选择对应机制即可

操作系统服务:

用户接口(UI)：几乎所有操作系统都有UI，CLI vs. GUI

程序执行：将程序载入内存并运行，结束执行，无论正常或异常

I/O操作：运行程序可能需要I/O，可能涉及文件操作或I/O设备

文件系统控制：创删读写查文件目录，权限管理

通信：进程间通信，网络通信

错误检测：时刻关注可能的错误，硬件/外设/用户程序…，恰当处理，调试功能

资源分配：多用户/多任务并行，各自分配各类资源(CPU，主存，文件存储)

账户管理：哪些用户使用了哪些计算机资源

保护与安全：多用户/网络计算机系统的权限需要管理，并行进程应互不干扰

系统程序:

为程序开发和执行提供方便的环境，被分为：

  • 文件操作：创建、删除、复制、重命名、打印、转存、列表，操纵文件和目录
  • 状态信息：日期、可用内存、性能、用户数量、调试信息…(注册表)
  • 文件修改：文本编辑器，对文本进行修改
  • 编程语言支持：编译器、汇编器、调试器、翻译器
  • 程序加载与运行
  • 通讯：提供虚拟连接的机制，供进程间、用户间、计算机系统间通信。
  • 应用程序

Chapter 3 - 进程

Appendix - Quiz

Which of the following is/are correct about von Neumann architecture?

❌It has better performance than Harvard architecture

  • 实际上哈佛架构把指令和数据分开之后，效率相对会高一点

✔️It is a widely used architecture in modern computers

  • 确实，相当一部分计算机使用冯诺依曼架构

✔️It use a shared memory for programs and data

  • 冯诺依曼架构特色

❌It was first described in 1958

  • 冯诺依曼架构的名词提出于1945

Which of the following is/are true about dual-mode operation?

❌The operating system must maintain a global bit to represent the current execution mode

  • 这个是CPU维护的

❌Certain operations are not permitted in the kernel mode and will be trapped to the user mode

  • 反过来就是对的

✔️Three ways to transit from user to kernel mode: system call, interrupt, and exception

  • U→K: 系统调用，中断，异常

❌Dual-mode operations are needed because applications need to be protected from OS

  • 反过来就是对的

What are the differences between an interrupt and an exception?

✔️Interrupts are usually asynchronous with the program execution, but exceptions are usually synchronous

  • 中断是外部设备接入等与程序运行异步的事件产生的，异常则是于程序运行时同步产生的

❌Interrupts may happen due to an abnormal condition, but exceptions are typically caused by normal conditions

  • 异常是对于异常(abnormal)情况的反馈，中断抢占正常执行。

❌Interrupts and exceptions are handled in different ways

  • 都是到被捕获后由handler处理，具体不一样

✔️Interrupts include notifications from devices or hardware components (e.g., APIC) but exceptions do not

  • 设备/硬件的异步通知造成中断，而不是异常

Which of the followings belong to operating system services?

✔️Error detection and handling

✔️Inter-process communication and networking

❌CPU scheduling

  • 虽然CPU调度是进程管理的重要方面，但它并不被视为操作系统提供的独立服务

✔️User interface

Which of the followings is/are true about state transition(s) in a process life cycle?

image.png

✔️Waiting->ready upon I/O completion

✔️Ready->running when it is dispatched by the CPU scheduler

❌Waiting->running when return from I/O requests

❌Running->waiting when it has used up its CPU quota and begin to wait until its next turn

Which of the followings is/are true about fork() and exec()?

❌In the parent process, fork() returns 0; in the child process, fork() returns its own pid.

✔️The parent and child process share the same program counter, memory content, and opened files.

✔️Copy-on-write means the address space of the parent and child processes are only copied when updated

❌Calling exec() to load the same program into the memory is equivalent to not calling exec() at all

Which of the followings is/are true about exit() and wait()?

✔️Exit() is always invoked when the process terminates.

❌Exit() sends SIGCHLD to the parent process if the parent process is already waiting by calling wait().

✔️Exit() frees allocated kernel memory and everying on the userspace memory.

✔️A process becomes a zombie process when it is terminated but not yet cleaned up by its parent process.

Which of the following is/are true about user-level and kernel-level thread?

✔️Many-to-many mapping requires thread implementation on both user-level and kernel-level.

❌The benefit of one-to-many mapping is that when a user thread blocks on I/O, it may use other kernel thread to run.

✔️Kernel-level thread is an implementation of the thread abstraction in the OS kernel.

❌With many-to-one mapping, the OS kernel can schedule user threads independently.

Which of the followings is/are true about preemptive scheduling?

✔️If scheduler is invoked when a process switches from running to ready state, it is preemptive scheduling.

❌RR is non-preemptive because the scheduler is not invoked when a process switches from waiting to ready.

❌A scheduler is preemptive if it is invoked when a process switches from waiting to running.

✔️If the running process only gives up the CPU when it terminates or blocks on I/O, the scheduler is non-preemptive.

Which of the following is/are true about race condition and mutual exclusion?

✔️Implementation of critical sections require mutual exclusion, bounded-waiting and progress.

✔️Race condition may happen when two processes concurrently access shared variables.

❌Priority inversion may happen when two processes are synchronized with semaphores.

✔️Peterson’s solution satisfies all the three requirements of critical section implementation.

Which of the following is/are true about semaphores?

❌A binary semaphore could only have two values whereas a counting semaphore could have more than two values.

✔️Semaphores must be implemented in the kernel.

❌When solving producer-consumer problem with semaphores, it is OK to swap the order of wait(&fill) and wait(&mutex).

❌In the correct solution to dining philosopher problem, semaphore is used to model a chopstick.