Coursera: Operating Systems Peking University

Week 1 操作系统概述

并发(concurrency): 处理多个同时性活动的能力

• 宏观上：这些程序在同时进行
• 微观上：任何时刻只有一个程序真正在执行，在CPU上轮流执行

并行(parallel): 不同程序同时在多个硬件上执行

Windows Architecture:

• User mode （系统进程、服务进程、用户进程、环境子系统、动态链接库DLL）
• Kernel mode (系统服务分发器、调用接口、内核、硬件驱动、图形窗口系统、硬件抽象层HAL)

UNIX Architecture:

• Hardware
• Kernel
• System call interface
• UNIX commands and libraries

LINUX/Android

传统操作系统分类：

• 批处理操作系统 (spooling 同时的外围设备联系操作)
• 分时操作系统 (一台主机为多台终端服务，时间片time slice)
• 实时操作系统
• 个人计算机操作系统
• 网络操作系统
• 分布式操作系统
• 嵌入式操作系统

练习题：

1. 用户向操作系统提出服务请求一般有两种方式：终端命令和 系统调用。
2. 并发性是指若干程序在同一时间间隔内执行。

Week 2 操作系统运行环境

常见控制与状态寄存器：

• 程序计数器，记录将要取出的指令的地址
• 指令寄存器 (Instruction Register)
• 程序状态字（Program Status Word)

在程序状态字PSW中专门设置一位或两位，根据运行程序对资源和指令的使用权限而设置不同的CPU状态。

操作系统需要两种CPU状态

• 内核态: 运行操作系统程序 (R0)
• 用户态: 运行用户程序 (R3)

特权指令: 只能由操作系统使用、用户程序不能使用的指令 (e.g., x86 四个特权级别 R0, R1, R2, R3)

• 启动I/O
• 内存清零
• 修改程序状态字
• 设置时钟
• 允许、禁止中断
• 停机 非特权指令: 用户程序可以使用的指令
• 控制转移
• 算数运算
• 取数指令
• 访管指令

CPU 状态之间的转换：

1. 用户态 -> 内核态: 中断/异常/陷入机制
2. 内核态 -> 用户态: 设置程序状态字 PSW

陷入指令 (又称访管指令): 从用户态访问管理内核态，提供给用户程序的接口，用于调用操作系统的功能

中断/异常机制：CPU 对系统发生的某个事件做出的一种反应。CPU 暂停正在执行的程序，保留现场后自动转去执行相应事件的处理程序，处理完成后返回断点继续执行被打断的程序。中断：突发外部事件。异常：CPU 执行指令本身出现的问题。

• 随机发送
• 自动处理
• 可恢复

事件：

1. 中断（外中断）
   • I/O 中断
   • 时钟中断（定时器到时，时间片到时）
   • 硬件故障
2. 异常（内中断）
   • 系统调用
   • 页故障
   • 保护性异常
   • 断点指令（调试程度）
   • 程序异常（算数溢出）

中断响应流程：

1. 设备发中断信号
2. 硬件保存现场
3. 根据中断码查表，得到中断处理程序
4. 把中断处理程序入口地址等推送到相应寄存器
5. 执行中断处理程序

中断发生后OS底层工作步骤：

1. 硬件压栈：程序计数器等
2. 硬件从中断向量表装入新的程度设计器
3. 汇编语言过程保存寄存器值
4. 汇编语言过程设置新的堆栈
5. C语言中断服务程序运行
6. 进程调度程序决定下一个将运行的进程
7. C语言过程返回至汇编代码
8. 汇编语言开始运行新的当前进程

练习题：

1. 中断向量（中断描述符）的作用非常重要，因为它保存了 程序状态字和中断入口程序地址。
2. 中断系统中保存现场的工作都是由硬件部件完成的。错，软件也会参与。

Week 3 进程线程模型

进程：具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。

调度：操作系统将CPU 控制权交给需要的进程

进程控制块 (PCB, process control block)：用于管理控制进程的一个专门数据结构。 进程和PCB一一对应。进程表上所有进程的PCB集合。

进程的三种基本状态

• 运行态：占有CPU
• 就绪态：等待空闲CPU
• 等待态：等待某一时间而暂时不能运行

挂起：用于调节负载，进程不占用存储空间，其进程映像交换到磁盘上

原语（原子操作）：进程状态之间的转换，不能被中断。完成特定功能的一段程序，没有分割性或不可中断性。

进程撤消：

1. 回收进程所占有的资源
   • 关闭打开的文件
   • 断开网络
   • 回收分配的内存…
2. 撤消进程的PCB

每一个进程有自己相对独立的地址空间，输出的是相对的虚拟地址。

Web Server Process:

1. 分派线程
2. 工作线程
3. 网页缓存

线程共享所在进程的地址空间和其他资源。

POSIX线程库 (PTHREAD)

进程映像也称进程图像，是进程执行的上下文环境，包括处理机中各通用寄存器的值，进程的内存映像，打开文件的状态和进程占用资源的信息等。

练习题：

1. 下列关于进程控制操作的叙述中，哪一个是不正确的？撤销进程就是释放该进程占有的内存资源
2. 下列哪一项工作不是创建进程时所作的？将处理器控制权交给新进程

Week 4 处理器调度

CPU调度解决三个问题：

• 按什么原则选择下一个要执行的程序 （调度算法）
• 何时进行选择 （调度时机）
• 如何让被选中的进程上CPU运行（调度过程，进程的上下文切换）

上下文切换的开销包括：

• 直接开销： 内核完成切换所用的CPU时间（保存和恢复寄存器、切换地址空间）
• 间接开销：告诉缓存、缓冲区缓存和TLB(Translation Lookup Buffer)失效

性能指标（用户角度）-> 可预测：

• 周转时间
• 响应时间
• 最后期限

性能指标（系统角度）-> 公平、强制优先级、平衡资源：

• 吞吐量
• CPU利用率

批处理系统中采用的调度算法

(吞吐量、周转时间、CPU利用率、公平、平衡)

• 先来先服务 (FCFS - First Come First Serve)
• 最短作业优先 (SJF - Shortest Job First)
• 最短剩余时间优先 (SRTN - Shortest Remaining Time Next)
• 最高响应比优先 (HRRN - Highest Response Ratio Next)

短作业优先SJF虽然能获得最短的平均周转时间，但不公平，可能使长的任务长时间得不到运行，导致“饥饿”现象(starvation)。响应比 (处理时间+等待时间/处理时间) 权衡了等待时间和任务长度。

交互式系统中采用的调度算法

(响应时间、公平、平衡)

• 轮转调度 (RR - Round Robin)：时间片的合适选择
• 最高优先级调度 (HPF - Highest Priority First)：优先级可以是静态的或动态调整的。可能出现优先级反转问题。
• 多级反馈队列 (Multiple Feedback Queue)：设置多个就绪队列，第一级队列优先级最高。给高优先级队列分配较小的时间片；随着队列优先级降低，时间片增大。
• 最短进程优先 (Shortest Process Next)

• Linux: 抢占式调度
• Windows: 基于动态优先级的抢占式多任务调度，结合时间配额的调整。 32个线程优先级，分成三类： 实时优先级、可变优先级和系统线程。

线程的亲和(Affinity)处理机集合：只允许该线程在几个处理机上进行。当亲和处理机集合改变，Windows会引发线程的调度。

平衡集管理器每秒会扫描一次就绪队列，发现是否存在等待时间超过300个时钟中断间隔的线程，管理器会提高其优先级至15（最高可变优先级），并分配一个长度为正常值4倍的时间配额。

练习题：

1. 采用下列哪一个调度算法会产生“饥饿”现象？多级反馈队列(Feedback)
2. 进程优先数决定了进程的优先级，优先数是一个数值
3. 有三个进程P1、P2和P3，运行时间均为50ms。假设时间片大小为10ms，且不考虑上下文切换的开销。采用时间片轮转（RR）算法执行完这三个进程，其平均完成时间是多少？ 140ms

Week 5 同步机制