系统软件

一台计算机有许多资源(CPU 时间、内存、磁盘、I/O)和许多程序争夺它们。OS 公平且高效地共享它们,使每个都被好好利用,系统保持响应:

• 多任务(multi-tasking)——在进程之间快速切换 CPU,使几个看起来一次运行。
• 内存管理(memory management)——给每个进程它需要的内存;当 RAM 用尽时用磁盘分页(paging)。
• 假脱机(spooling)和缓冲——打印作业在磁盘上排队,所以 CPU 从不等打印机。
• 缓存(caching)——把最近用过的磁盘数据保存在高速缓存(cache)/ RAM 中。

用户界面把硬件隐藏在友好的抽象之后:用户看到窗口、菜单和文件夹,而不是地址或扇区。在一个图标上点一下,使 OS 在磁盘上找到程序、分配内存、加载它并启动它。一个 CLI(命令行)对专家强大且可脚本化;一个 GUI(图形)更容易学。大多数系统两者都提供。

"描述硬件的复杂性对用户隐藏的两种方式。" (1) 用户用名字操作文件和文件夹,由 OS 把它们翻译成磁盘的磁道、扇区和块;(2) 用户用一次点击或一条命令运行程序,由 OS 装载它、分配内存并调度它,用户不需要知道任何地址;(3) 设备驱动程序让用户打印或保存而不必知道打印机或磁盘如何控制;(4) 图形界面用图标、窗口和菜单取代机器级命令。对学生的好处及例子:OS 使硬件无需技术知识即可使用,例如把文档的图标拖过去就能保存到 U 盘。

"说明 OS 如何最大化资源的利用。" 它调度处理器,使有进程就绪时处理器决不空闲;它管理内存,把内存分配给进程、回收并用虚拟内存扩展它;它管理输入和输出,用缓冲和假脱机使快慢设备的工作重叠;它管理存储,记录空闲空间和文件。每一点都要点名一种资源以及 OS 对它做什么。

一个进程(process)是执行中的一个程序——它的代码、当前状态、内存和打开的文件。

Scheduling

调度器(scheduler)选择哪个就绪进程接下来运行,以及运行多久:

• 轮转(round robin)——每个进程得到一个固定的时间片(time slice),然后去到队列的后面。
• 先来先服务;最短作业优先;最短剩余时间(shortest remaining time,运行剩余工作最少的作业);优先级;多级反馈队列。

权衡是响应性对吞吐量对公平性。

"描述多任务是什么意思以及它如何有益于进程管理。" 几个进程同时保存在内存中,处理器在它们之间切换得如此之快,以至于它们看起来在同时运行,每个轮流得到一份处理器时间。好处:当一个进程等待输入或输出时处理器决不闲置,所以吞吐量更高,用户可以同时在几个程序上工作。"解释调度的必要性。" 进程多于处理器,所以必须决定哪个进程接下来运行以及运行多久;调度确保每个进程都取得进展、处理器被充分利用、响应时间可接受,并且优先级得到尊重。

调度例程,按考试要求的描述方式。

例题。 三个进程同时到达,CPU 时间分别为 8、4 和 2 ms。比较 FCFS(按到达顺序 A、B、C)和最短作业优先下的平均等待时间。

FCFS:A 等 0,B 等 8,C 等 12;平均 $(0 + 8 + 12)/3 = 6.7\ \text{ms}$。SJF 运行 C、B、A:C 等 0,B 等 2,A 等 6;平均 $2.7\ \text{ms}$。两种方式总工作量都是 14 ms;顺序决定谁等待。时间片 2 ms 的轮转让 A、B、C 在前 6 ms 内各得一轮,所以 C 在 6 ms 完成,B 在 12 ms,A 在 14 ms:响应最好,但平均不是最快。

Process states

一个进程是新建(new)、就绪(ready,等待 CPU)、运行(running)、阻塞(blocked,等待 I/O 或一个锁),或终止(terminated)。当它的时间片结束时它从运行 → 就绪;当它请求 I/O 时它从运行 → 阻塞;当 I/O 完成时它从阻塞 → 就绪。

三个状态以及进程为什么转移。 *运行:*进程占有处理器。*就绪:*它可以运行但在等待处理器。*阻塞:*在其他事件发生之前它不能运行。每种转移的原因,考试会逐个问:运行到就绪,当它的时间片用完,或当一个更高优先级的进程变为就绪并抢占它(一次中断);运行到阻塞,当它请求输入或输出,或等待某个资源或另一个进程;阻塞到就绪,当它等待的 I/O 完成(由中断通知);就绪到运行,当调度器派遣它。阻塞的进程决不能直接进入运行:它必须先变为就绪。

Process control block and context switch

对每个进程,OS 保存一个进程控制块(process control block,PCB)——保存的程序计数器、寄存器、状态和内存信息。

• 一次上下文切换(context switch)挂起一个进程并启动另一个:它把状态保存进一个 PCB 并从另一个恢复它。这个小代价在每次切换时付出。
• 内核(kernel,OS 的核心)充当一个中断处理程序(interrupt handler)。当一个设备或定时器发起一个中断时,中断处理(interrupt handling)保存运行中的进程并运行正确的例程——这就是驱动底层调度的东西。

"概述内核如何充当中断处理程序"(两分)。 中断发生时,内核保存正在运行进程的状态(它的寄存器和程序计数器,存入进程控制块),识别中断的来源和优先级,运行相应的中断服务例程,然后恢复被中断的进程(或一个更高优先级的进程),使执行继续。定时器就是这样结束时间片的,完成的 I/O 操作也是这样解除进程阻塞的。

Inter-process communication

进程是隔离的,所以 OS 提供进程间通信(inter-process communication):管道(pipes,一个程序的输出馈入另一个的输入)、共享内存(shared memory,几个进程可以用的一个区域),以及消息传递。

每个进程得到它自己的虚拟地址空间(virtual address space)——OS 映射到物理内存的一个干净、连续的地址范围。这给每个进程一个简单的空间,保护进程彼此隔离,并让总内存超过物理 RAM。

在分页中,虚拟空间被拆成固定大小的页(pages),物理内存被拆成同样大小的页框(frames)。一个页表把每个页映射到一个页框。若一个被访问的页不在 RAM 中——一个缺页(page fault)——OS 从交换文件(swap file)把它读进一个页框,若 RAM 满了就逐出另一个页。频繁的缺页导致抖动(thrashing,磁盘抖动),那里 OS 把它的大部分时间花在交换页而不是做有用的工作。

在分段(segmentation)中,内存被拆成可变大小的逻辑段(代码、栈、堆),每个有它自己的权限。许多系统在段内使用分页。

"解释虚拟内存是什么意思"(三分)。 用辅助存储器(磁盘)扩展 RAM,使可用内存显得比物理内存大;进程的地址空间被分成页,只有当前需要的页保存在 RAM 中,其余在磁盘上等待;页按需要在 RAM 和磁盘之间交换,OS 把每个虚拟地址翻译成物理地址。OS 为什么需要它:正在运行的程序可能需要比安装的 RAM 更多的内存;它让更多(或更大)的程序同时运行;程序可以比物理内存大;内存得到高效利用,因为只有程序的活动部分占据 RAM。

分页对分段:考试要的区别。 分页把内存分成由硬件决定的固定大小的块(页和页框),不考虑程序的结构,映射对程序员不可见;分段把程序分成大小可变的逻辑单元(一个过程、一个数组、栈),其大小和边界跟随程序,所以一个段可以作为整体被保护或共享。"描述分段的过程":程序被拆成大小不同的段,每段给一个段号;段表记录每段在内存中从哪里开始、有多长;逻辑地址是段号加偏移量,OS 把偏移量加到该段的基地址上得到物理位置。

"解释磁盘抖动是什么意思"以及它何时发生。 磁盘抖动(disk thrashing)是页在 RAM 中换入换出如此频繁,以至于处理器花在搬页上的时间多于执行指令、系统几乎停顿的状态。它发生在 RAM 对正在运行的进程所需的页(它们的工作集)来说太小时:刚换出的页几乎立刻又被需要,于是被取回,又挤出另一个很快就要用的页,如此往复。进程太多,或程序以不可预测的方式访问内存,都会引起它;更多 RAM 或更少进程能治愈它。

一个解释器(interpreter)同时翻译并运行源代码。对每条语句它读这行、做词法和语法分析、检查类型,然后执行该动作,并继续。错误被立即报告,它通常停止;不产生可执行文件。翻译每次运行都重做(更慢),但它给出快速的开发反馈并且是可移植的。

"解释解释器如何在不产生翻译版本的情况下执行程序"(三分)。 解释器一次取一条语句(一行),翻译(分析)它,并立即执行,然后再处理下一条;不创建或存储整个程序的翻译版本,所以每条语句每次执行都要翻译,包括循环的每一趟;若某条语句有错误,执行在那里停止并报告错误。这就是解释器适合开发和测试(错误在到达时被发现,修改可以立即试验)但运行成品程序较慢的原因。

一个编译器(compiler)分阶段把源代码变成机器码(machine code):

1. 词法分析(lexical analysis)——词法分析器把字符分组成词法单元(tokens,关键字、标识符、运算符、字面量),丢弃空白和注释。
2. 语法分析(解析)(syntax analysis / parsing)——检查词法单元符合文法并构建一棵抽象语法树(abstract syntax tree)。一个遗漏的括号给出一个语法错误(syntax error)。
3. 语义分析(semantic analysis)——检查程序说得通(变量已声明、类型匹配)。
4. 代码生成(code generation)——遍历树并发出目标代码,选择寄存器和布局。
5. 代码优化(code optimisation)——去除冗余的工作、折叠常量、为流水线重排。

输出是一个可执行文件。

各阶段的目的,用得分的措辞。 *词法分析:*去掉空白和注释;把源代码的字符转换成词法单元(关键字、标识符、运算符、常量),检查每一个在该语言中是否有效;把标识符登记到符号表(symbol table)中。*语法分析:*检查词法单元序列是否符合语言的文法(语法规则);构建解析树(抽象语法树);报告语法错误;类型检查和变量声明的检查有时归入语义分析。*代码生成:*把检查过的树转换成目标代码或机器码(可能经由中间代码),分配内存和寄存器。*优化:*使代码运行更快或占用更少内存,通过去除冗余指令、合并或简化计算、重组循环,而不改变程序的功能。配对题把每个阶段与这些描述之一配对。

一个文法(grammar)说明哪些词法单元序列是有效的程序。

巴科斯-诺尔范式(Backus-Naur Form,BNF)是文本的。一个产生式(production rule)有这样的形式:

<symbol> ::= alternative1 | alternative2 | ...

每个候选是一个终结符(terminal)符号(字面文本)和非终结符(non-terminal)符号(其他规则名)的序列:

<digit>      ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>

递归的第三条规则表达"一个字母后跟任意数目的字母或数字"。一个 IF 语句:

<if-statement> ::= IF <condition> THEN <statement> ENDIF
                 | IF <condition> THEN <statement> ELSE <statement> ENDIF

一个语法图(syntax diagram,铁路图)以图形显示同样的东西:非终结符用方框、终结符用圆角框、有效路径用箭头、重复用循环。两种记法是等价的。解析器用文法来判定一个程序是否有效。

读考试的图。 每张图定义一个非终结符;沿箭头从入口走到出口,能走通的每条路径都是一个有效字符串。并排的选择框是一组候选;回头的循环是"想重复多少次都行";另一个非终结符的框表示"插入那条规则允许的任何东西"。"说明该字符串为什么无效"要的是它违反的规则,用文字表述:9K 作为变量无效,因为第一个字符必须是字母而不是数字;若规则只允许数字前有一个字母,或 J 不在列出的字母集合中,JJ90 就是无效的口令。总是对照图实际允许的字符集合检查字符串,而不是对照真实语言会接受什么。

由图写 BNF。 每张图变成一条规则 <名称> ::= ...;候选用 | 分隔;序列一个符号接一个符号地写;而重复用递归来写,因为 BNF 没有循环符号:"一个或多个字母"是 <word> ::= <letter> | <letter><word>,"一个字母后接零个或多个数字"是 <variable> ::= <letter> | <letter><digits>,其中 <digits> ::= <digit> | <digit><digits>。

例题。 补全车辆登记号的 BNF:必须以两个字母(取自 A B C)开头,后接一位、两位或三位数字(取自 0 1 2)。

<letter>       ::= A | B | C
<digit>        ::= 0 | 1 | 2
<digits>       ::= <digit> | <digit><digit> | <digit><digit><digit>
<registration> ::= <letter><letter><digits>

AB12 有效;A12 无效(只有一个字母);AB1234 无效(四位数字);AD1 无效(D 不是列出的字母)。被要求加约束如"第三个字符也可以是符号"时,只给那个位置的规则加额外候选,并用单独的规则定义 <symbol>。

例题。 写出表达式的 BNF:表达式是一个变量,后接一个运算符,再接一个变量或一个数,其中变量是取自 a b c 的单个小写字母,运算符是 + 或 -。

<variable>   ::= a | b | c
<operator>   ::= + | -
<number>     ::= <digit> | <digit><number>
<expression> ::= <variable><operator><variable> | <variable><operator><number>

递归的 <number> 规则允许任意多位数字;<expression> 的两个候选覆盖定义中提到的两种情况。每个非终结符都放在尖括号里,每个终结符都不加。

在中缀(infix)记法中,运算符坐在它的操作数之间(3 + 4 * 2),需要括号和优先级规则。在逆波兰表示法(Reverse Polish Notation,RPN,后缀(postfix))中,运算符跟在它的操作数之后(3 4 2 * +),不需要括号。

Converting infix to RPN

用一个运算符栈(stack)。从左到右扫描:输出一个操作数;对一个运算符,先把任何更高或相等****优先级(precedence)的已入栈运算符弹到输出,然后把它压栈;把 ( 压栈;遇到 ) 弹出到输出直到匹配的 (。在最后,弹出所有运算符。例子:(3 + 4) * 2 → 3 4 + 2 *。

Evaluating RPN

用一个操作数栈。从左到右扫描:把每个操作数压栈;遇到一个运算符,弹出顶上两个、应用它,并把结果压栈。求值 3 4 2 * +:

结果:11。RPN 在求值时不需要括号并适合一个栈机器——这就是 JVM 和许多字节码(bytecode)解释器工作的方式。

"解释为什么用 RPN 求表达式的值"(两分)。 在 RPN 中运算符按它们被应用的顺序出现,所以表达式可以从左到右一趟求值,不需要括号,也不需要优先级规则;因此编译器或解释器处理起来更简单、更快。"指出一种合适的数据结构并说明理由":**栈,因为求值需要先用最近**压入的操作数(后进先出):每个操作数被压入,每个运算符弹出顶部两个,应用自身,再压入结果。被要求时要写出每个词法单元之后的栈内容。

手工把中缀转成 RPN。 (1) 按优先级规则给表达式完全加括号;(2) 把每个运算符移到它自己那对括号的右括号之后;(3) 去掉括号。于是 $(a - b) * (a + c) / 7$ 变成 $((a - b) * (a + c)) / 7$,再变成 a b - a c + * 7 /。注意 * 和 / 从左到右应用,所以除法是最后一个运算符,而不是乘法。更多转换:$((7 + 3) - (2 * 8)) / 6$ 是 7 3 + 2 8 * - 6 /;$(7 - 2 + 8) / (9 - 5)$ 是 7 2 - 8 + 9 5 - /;$a * b + b - d + 15$ 是 a b * b + d - 15 +;$(2 - 6) * (13 + 7) / 5$ 是 2 6 - 13 7 + * 5 /。

把 RPN 转回中缀。 用一个表达式栈处理 RPN:压入每个操作数;对每个运算符弹出两个,加括号写在它两侧,再压入结果。于是 a b / 4 * a b + - 是 $((a / b) * 4) - (a + b)$;5 2 + 9 3 - / 3 * 是 $((5 + 2) / (9 - 3)) * 3$;b a c - + d b + * c / 是 $((b + (a - c)) * (d + b)) / c$;a b - c + c a - * d / 是 $(((a - b) + c) * (c - a)) / d$。保留括号:去掉它们可能改变含义。

例题。 当 $a = 17$、$b = 5$、$c = 7$、$d = 3$、$e = 10$ 时求 a b - c d + * e / 的值,写出栈。

结果 12。对 - 和 / 弹出的顺序很重要:第二个弹出的值是左操作数,所以 a b - 是 $a - b$,不是 $b - a$。再来两个,方法相同:d a b + * c a - / 在 $a = 6, b = 12, c = 15, d = 5$ 时给出 $5 \times (6 + 12) / (15 - 6) = 90 / 9 = 10$;c a - b d + * b c + / 在 $a = 4, b = 12, c = 24, d = 6$ 时给出 $(24 - 4) \times (12 + 6) / (12 + 24) = 360 / 36 = 10$。

例题。 把 $(A + B) \times (C - D)$ 转换成逆波兰式,然后计算 $(3 + 4) \times (5 - 2)$。用一个运算符栈从左向右扫描。压入 (;输出 A;压入 +;输出 B;遇到 ) 时弹出直到匹配的 (,此时已输出 A B +。压入 ×,第二个括号同样处理,得到 C D -。最后弹出 ×。结果是:A B + C D - ×。要计算数值,则用一个操作数栈:压入 3,压入 4;+ 弹出两者并压入 7;压入 5,压入 2;- 弹出两者并压入 3;× 弹出 7 和 3 并压入 21。有两点能让这类题做得稳:转换过程中操作数保持原来的顺序(只有运算符在移动),而且每个运算符作用于栈中紧挨着它下面的两个值。

定义题按固定措辞评分。准确学会这些,只给一个答案。

• OS 题按点名的机制评分:调度、内存管理、I/O 缓冲和假脱机、文件管理;对界面,文件名而非地址、点击而非命令、驱动程序、GUI。
• 进程状态及其转移和每种转移的原因;调度例程按功能加优点加缺点;内核保存状态、识别中断、处理、恢复。
• 虚拟内存:磁盘扩展 RAM、页交换、地址翻译;分页是固定大小且不可见,分段是可变大小且逻辑的;抖动是交换而不是工作。
• 解释器:一次一条语句,先翻译再执行,不存储任何东西。编译阶段:词法单元和符号表、文法和解析树、代码、优化。
• BNF:每张图一条规则,| 表示选择,递归表示重复,终结符不加括号而非终结符加尖括号。要说出字符串违反了哪条规则。
• RPN:运算符在操作数之后,用栈求值,写出每一步;转换时完全加括号;转回时保留括号。

常见错误

• 把多任务描述成"同时运行几个程序"而不说处理器在它们之间切换。
• 让阻塞的进程直接进入运行,或把"时间片用完"当作运行到阻塞的原因。
• 混淆最短作业优先(非抢占)与最短剩余时间(抢占),或混淆轮转与优先级。
• 把虚拟内存定义为"把硬盘当 RAM 用"而不提页的交换。
• 说解释器"把程序转换成机器码然后运行";那是编译器。
• 把语法检查放进词法分析,或在配对题中把优化放在代码生成之前。
• 把 BNF 的重复写成 <letter>* 或用省略号;要用递归。非终结符漏掉尖括号。
• 求 RPN 值时把 - 或 / 的操作数弄反,或把 $a * b + c$ 的 RPN 写成 a b c + *。