系统软件

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

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

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

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

Scheduling

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

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

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

Process states

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

Process control block and context switch

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

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

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

一个解释器(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)——去除冗余的工作、折叠常量、为流水线重排。

输出是一个可执行文件。

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

在中缀(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)解释器工作的方式。

例题。 把 $(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。有两点能让这类题做得稳:转换过程中操作数保持原来的顺序(只有运算符在移动),而且每个运算符作用于栈中紧挨着它下面的两个值。

• 列出编译的各阶段(词法、语法和语义分析、代码生成、优化)以及每个做什么。
• 解释虚拟内存和分页(磁盘用作额外的 RAM)以及它的代价(磁盘抖动)。
• 用一个栈求值逆波兰表示法——不需要括号。
• 用 BNF 或一个语法图来测试一个字符串是否有效。