Resources, Compilers & RPN
A-Level Computer Science Topic 16 14:05 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Open a browser, a music player, and a game.
打开一个浏览器、一个音乐播放器和一个游戏。
You have one processor — maybe a few cores — yet all of them seem to run at once.
你只有一个处理器——也许几个核心—— 可它们看上去却在同时运行。
And together they want more memory than your machine has.
而且它们加起来想要的内存，比你机器上有的还多。
The operating system is the juggler: it slices the processor between them, invents memory that isn't really there, and keeps everything responsive.
操作系统就是那个耍杂技的人：它把处理器在它们之间切分，凭空造出并不真正存在的内存， 还让一切都保持流畅。
Let's see the tricks it uses.
让我们看看它用了哪些招数。
How an operating system squeezes the most from limited hardware — and how your code becomes something it can run.
操作系统如何从有限的硬件里榨出最多的性能——以及你的代码如何变成它能运行的东西。
Today: scheduling and process states, virtual memory and paging, the stages of compilation, grammars, and reverse Polish notation.
今天我们讲：调度与进程状态、虚拟内存与分页、编译的各个阶段、文法，以及逆波兰表示法。
Let's begin.
让我们开始吧。
A computer has many resources — CPU time, memory, disk, input and output — and many programs competing for them.
一台计算机有许多资源——处理器时间、内存、磁盘、输入输出—— 还有许多程序在争抢它们。
The OS shares them fairly and efficiently so each is well used and the system stays responsive.
操作系统公平而高效地共享这些资源，让每一样都被充分利用， 同时保持系统的响应。
Four mechanisms.
有四种机制。
Multi-tasking switches the CPU rapidly between processes so several appear to run at once.
多任务让处理器在各个进程之间快速切换， 于是好几个程序看起来在同时运行。
Memory management gives each process what it needs, and uses disk paging when RAM runs out.
内存管理给每个进程它所需要的内存， 在内存不够时使用磁盘分页。
Spooling queues print jobs on disk so the CPU never sits waiting for a slow printer.
假脱机把打印任务排在磁盘上， 这样处理器就绝不会干等着一台慢吞吞的打印机。
And caching keeps recently-used disk data in cache — fast memory.
而高速缓存把最近用过的磁盘数据 留在缓存——也就是快速内存——里。
There is a fifth job too: the user interface hides all of this behind windows, menus and folders — a CLI for experts, a GUI that is easier to learn — so one click makes the OS find the program on disk, allocate memory, load it and start it.
还有第五件工作：用户界面把这一切藏在窗口、菜单和文件夹背后—— 专家用命令行，图形界面则更易学—— 于是点击一下，操作系统就会在磁盘上找到程序、分配内存、加载并启动它。
A process is a program in execution — its code, its current state, its memory and its open files.
进程就是正在执行中的程序——它的代码、它当前的状态、它的内存和它打开的文件。
It moves between five states, and the transitions are what get examined.
它在五个状态之间移动，而这些转换正是考试要考的。
New becomes ready when the OS admits it.
当操作系统接纳它时， 新建变为就绪。
Ready becomes running when the scheduler dispatches it.
当调度器分派它时，就绪变为运行。
Running goes back to ready when its time slice ends or it is interrupted — note it does not go straight back to running.
当它的时间片用完或者被中断时， 运行退回就绪——注意它不会直接回到运行。
Running becomes blocked when it requests input or output, because it cannot use the CPU while it waits.
当它请求输入或输出时，运行变为阻塞， 因为等待期间它无法使用处理器。
Blocked returns to ready, not to running, when that I/O completes — it must queue for the CPU again.
当那次输入输出完成时，阻塞回到就绪，而不是回到运行—— 它必须重新排队等处理器。
And running becomes terminated when it exits.
而当它退出时，运行变为终止。
The scheduler chooses which ready process runs next and for how long.
调度器决定下一个运行哪个就绪进程，以及运行多久。
First-come-first-served simply runs each to completion in arrival order — simple, but one long job blocks everyone behind it.
先来先服务就是按到达顺序 把每个进程一直运行到结束——简单，但一个长任务会把排在后面的所有人都堵住。
Round robin gives each process a fixed time slice, then sends it to the back of the queue, which is far more responsive.
轮转法给每个进程一个固定的时间片，然后把它送到队尾，这样响应性好得多。
Shortest job first, and shortest remaining time, pick the job with the least work left, which minimises average waiting but can starve long jobs.
最短作业优先和最短剩余时间优先，挑选剩余工作量最少的任务， 这能让平均等待时间最短，却可能让长任务饿死。
Priority scheduling and multilevel feedback queues refine that further.
优先级调度和多级反馈队列 在此基础上进一步细化。
Every one of them is a trade-off between three things you cannot maximise at once: responsiveness, throughput and fairness.
它们每一种都是在三件无法同时最大化的事情之间做权衡： 响应性、吞吐量和公平性。
For every process the OS keeps a process control block, holding the saved program counter, the registers, the state and the memory information.
操作系统为每个进程保存一个进程控制块，里面存着保存下来的程序计数器、 各个寄存器、状态以及内存信息。
A context switch suspends one process and starts another: it saves the whole state into one PCB and restores it from another.
上下文切换会挂起一个进程并启动另一个： 它把整个状态存进一个进程控制块，再从另一个里面恢复出来。
And that cost is paid on every single switch — which is why a very short time slice makes a system responsive but wasteful.
而这份开销在每一次切换时都要付——这正是为什么很短的时间片虽能让系统反应灵敏， 却也很浪费。
Driving all of this is the kernel, the core of the OS, which acts as an interrupt handler: when a device or the timer raises an interrupt, interrupt handling saves the running process and runs the right routine.
驱动这一切的是内核，也就是操作系统的核心，它充当中断处理程序： 当某个设备或定时器发出中断时，中断处理会保存正在运行的进程，转去运行相应的例程。
Finally, because processes are isolated from each other, the OS provides inter-process communication — pipes, where one program's output feeds another's input; shared memory, a region several processes can use; and message passing.
最后，由于进程之间是相互隔离的，操作系统提供了进程间通信—— 管道，让一个程序的输出成为另一个程序的输入；共享内存，一块多个进程都能使用的区域； 以及消息传递。
First, sharing the processor.
首先是共享处理器。
The scheduler picks which ready process runs next.
调度器挑选下一个运行哪个就绪的进程。
Round robin gives each one a fixed time slice, then sends it to the back of the queue — so nothing hogs the CPU.
轮转调度给每个进程一个固定的时间片， 然后把它送到队列末尾——这样谁也霸占不了 CPU。
A process moves between states: ready when it wants the processor, running when it has it, and blocked when it is waiting for input or output.
一个进程在几种状态之间移动： 想要处理器时是就绪，拿到处理器时是运行，等待输入输出时是阻塞。
Every switch saves one process's registers into its control block and loads another's — that's a context switch, and it isn't free.
每一次切换都要把一个进程的寄存器存进它的控制块，再载入另一个的——这就是上下文切换， 而它并不是免费的。
Next, memory.
接下来是内存。
Each process gets its own virtual address space, which the operating system maps onto real memory.
每个进程都有自己的虚拟地址空间，操作系统把它映射到真实的内存上。
Split it into fixed-size pages, and physical memory into frames of the same size; a page table records which page sits in which frame.
把它切成固定大小的页，把物理内存切成同样大小的页框；一张页表记录哪一页放在哪一个页框里。
If a page isn't in memory, that's a page fault — the system fetches it from disk, evicting another page if it must.
如果某一页不在内存里，那就是缺页——系统会从磁盘把它取回来，必要时还会赶走另一页。
This lets programs use more memory than you have.
这让程序能使用比你实际拥有的更多的内存。
But if it happens too often, the machine spends all its time swapping instead of working — that's thrashing.
但如果这种情况太频繁， 机器就会把所有时间都花在换页上而不是干活——这就是抖动。
Each process gets its own virtual address space — a clean contiguous range of addresses that the OS maps to physical memory.
每个进程都得到自己的虚拟地址空间——一段干净、连续的地址范围， 由操作系统映射到物理内存上。
That buys three things: a simple space for each process, it protects processes from each other, and a total memory that can exceed the physical RAM.
这带来三样好处：每个进程都有一个简单的空间、 进程之间互相保护，以及总内存可以超过物理内存的实际容量。
In paging, the virtual space is cut into fixed-size pages and physical memory into same-sized frames, and a page table maps each page to a frame.
在分页机制中，虚拟空间被切成固定大小的页，物理内存被切成同样大小的页框， 再由页表把每一页映射到一个页框。
Notice that consecutive pages need NOT land in consecutive frames — that is the whole trick.
注意，相邻的页并不需要落在相邻的页框里—— 这正是整个诀窍所在。
When a process touches a page that is not in RAM, that is a page fault: the OS fetches it from the swap file into a frame, evicting another page if RAM is full.
当进程访问一个不在内存中的页时，就发生了缺页： 操作系统把它从交换文件读进一个页框，如果内存已满就先淘汰掉另一页。
Paging has a failure mode with a name examiners like.
分页有一种考官很喜欢的失效模式。
If the working set does not fit in RAM, every page the OS brings in evicts one it is about to need again, so faults follow faults.
如果工作集装不进内存， 操作系统每调进一页，就要淘汰掉一页它马上又要用的，于是缺页接着缺页。
That is thrashing — the system spends most of its time swapping pages instead of doing useful work, and it feels frozen while the disk light stays on.
这就是抖动——系统把大部分时间花在换页上，而不是做有用的工作， 给人的感觉就是卡死，而硬盘灯一直亮着。
The alternative organisation is segmentation: memory is split into variable-sized logical segments — code, stack, heap — each with its own permissions, mapped through a segment table of sizes and start addresses.
另一种组织方式是分段： 内存被切成大小可变、在逻辑上有意义的段——代码段、栈、堆—— 每一段有自己的权限，通过一张记录大小和起始地址的段表来映射。
The difference to state is that pages are fixed-size and segments are variable-sized and logically meaningful.
要答出的区别是：页是固定大小的，而段是可变大小、且有逻辑含义的。
Many real systems use paging within segments.
许多真实系统在段内部又使用分页。
Now, turning your code into something runnable.
现在，把你的代码变成能运行的东西。
A compiler works in phases.
编译器分阶段工作。
Lexical analysis chops the characters into tokens — keywords, names, operators.
词法分析把字符切成一个个词法单元—— 关键字、名字、运算符。
Syntax analysis checks those tokens fit the grammar and builds a tree; a missing bracket is caught here.
语法分析检查这些词法单元是否符合文法，并建起一棵语法树； 少了一个括号就在这里被抓住。
Semantic analysis checks the program makes sense — are the variables declared, do the types match.
语义分析检查程序是否讲得通——变量声明了吗，类型对得上吗。
Then code generation emits machine code, and optimisation trims the waste.
然后代码生成产出机器码，代码优化再削掉浪费的部分。
An interpreter, by contrast, translates and runs line by line, every single time.
而解释器则相反：它逐行翻译并逐行运行，每次运行都要重来一遍。
An interpreter translates and runs at the same time, which is the sentence a question wants.
解释器在翻译的同时执行，这正是考题想要的那一句话。
For each statement it reads the line, does lexical and syntax analysis, checks the types, then executes that action and moves to the next.
对每一条语句，它读入这一行，做词法分析和语法分析，检查类型， 然后执行这个动作，再转到下一条。
Two consequences follow.
由此有两个后果。
Errors are reported immediately, at the line where they occur, and the program usually stops there — and no executable is ever produced.
错误会被立即报告，就在它出现的那一行，而且程序通常就停在那里—— 而且从来不会产生可执行文件。
And the translation is redone every run, which makes it slower than compiled code, but gives fast development feedback and is portable, because the same source runs anywhere the interpreter runs.
另外，每次运行都要重新翻译一遍， 这使它比编译过的代码慢，但能给出很快的开发反馈，而且可移植性好， 因为同一份源代码在任何能运行解释器的地方都能跑。
A compiler works in five phases, and you should be able to name each and say what it does.
编译器分五个阶段工作，你应当能说出每一个的名称和它做什么。
Lexical analysis: the lexer groups characters into tokens — keywords, identifiers, operators, literals — discarding whitespace and comments.
词法分析：词法分析器把字符归并成词法单元——关键字、标识符、运算符、字面量—— 同时丢弃空白和注释。
Syntax analysis, also called parsing: check the tokens fit the grammar and build an abstract syntax tree; a missing bracket produces a syntax error here.
语法分析，也叫解析：检查这些词法单元是否符合文法， 并构建抽象语法树；括号缺失产生的语法错误就是在这里报出来的。
Semantic analysis: check the program actually makes sense — variables declared, types matching.
语义分析：检查程序是否真的讲得通——变量是否声明过、类型是否匹配。
Code generation: walk the tree and emit target code, choosing registers and layouts.
代码生成：遍历这棵树并生成目标代码，选择寄存器和布局。
And code optimisation: remove redundant work, fold constants, reorder for the pipeline.
以及代码优化：去掉多余的工作、合并常量、为流水线重排指令。
The output is an executable — which is the fundamental difference from an interpreter.
输出是一个可执行文件——这正是它与解释器的根本区别。
How does the parser know the grammar?
语法分析器怎么知道文法呢？
We write it down.
我们把它写下来。
Backus-Naur Form gives a rule for each symbol: a digit is zero, or one, or two, and so on up to nine.
巴科斯-诺尔范式为每个符号给出一条规则： 一个数字是零，或一，或二，一直到九。
Rules can be recursive — an identifier is a letter, or an identifier followed by another letter or digit — which captures "any number of them" in a single line.
规则可以是递归的——一个标识符是一个字母， 或者是一个标识符后面再跟一个字母或数字——这一行就表达了"任意多个"。
A syntax diagram says exactly the same thing as a picture: boxes and arrows, with a loop wherever something may repeat.
语法图用图形说的是完全相同的事：方框和箭头，凡是可以重复的地方就画一个回环。
A grammar says which token sequences are valid programs, and Backus-Naur Form writes one down.
文法规定哪些词法单元序列是合法的程序，而巴科斯-诺尔范式把它写下来。
A production rule has a symbol, then the two-colon-equals sign, then alternatives separated by vertical bars.
一条产生式由一个符号、然后是双冒号等号、再是用竖线隔开的若干候选式组成。
Each alternative is a sequence of terminal symbols, which are literal text, and non-terminal symbols, which are the names of other rules.
每个候选式是终结符和非终结符的序列，终结符是字面文本，非终结符是其他规则的名字。
The digit rule is the simplest: a digit is nought, or one, or two, and so on.
数字规则最简单：一个数字是零，或者一，或者二，依此类推。
Now the recursive rule, which is the one that catches people out.
现在看那条递归规则，正是它把人绊倒的。
An identifier is a letter, OR an identifier followed by a letter, OR an identifier followed by a digit.
一个标识符是一个字母， 或者是一个标识符后面跟一个字母，或者是一个标识符后面跟一个数字。
Read it carefully and it says: start with a letter, then add any number of letters or digits.
仔细读它就是在说：以一个字母开头，然后接任意多个字母或数字。
And an IF statement shows alternatives at work: one form with ELSE, one without.
而 IF 语句展示了候选式的用法：一种带 ELSE，一种不带。
A syntax diagram, also called a railroad diagram, says exactly the same thing graphically.
语法图，也叫铁路图，用图形说的是完全相同的事情。
You read it by following the arrows from left to right, and any path you can trace is a valid construct.
你从左往右顺着箭头读，凡是你能描出的一条通路，都是一个合法的构造。
Rectangular boxes are non-terminals — other rules to expand.
矩形框是非终结符——需要继续展开的其他规则。
Rounded boxes are terminals, the literal text.
圆角框是终结符，也就是字面文本。
Branches are alternatives, and a loop back is repetition, which is how it expresses what recursion expressed in BNF.
分叉表示多种候选，而回环表示重复，这正是它表达递归的方式， 与巴科斯-诺尔范式里的递归对应。
This one reads: an identifier, then the assignment symbol, then an expression.
这一张读作：一个标识符，然后是赋值符号， 然后是一个表达式。
The two notations are equivalent, and the parser uses whichever you give it to decide whether a program is valid.
两种记法是等价的，解析器会用你给它的那一种， 来判断一个程序是否合法。
In infix notation the operator sits between its operands, which is why we need brackets and precedence rules.
在中缀记法里运算符夹在两个操作数中间，正因如此我们才需要括号和优先级规则。
In Reverse Polish Notation the operator follows its operands, and then you need no brackets and no precedence rules at all.
在逆波兰记法里运算符跟在操作数后面，于是就完全不需要括号，也不需要优先级规则了。
To convert, use an operator stack and scan left to right.
转换时使用一个运算符栈，从左往右扫描。
An operand goes straight to the output.
操作数直接送到输出。
For an operator, first pop any stacked operators of higher or equal precedence to the output, then push it.
遇到运算符，先把栈里优先级高于或等于它的运算符弹出到输出，然后再把它压入。
Push an opening bracket; on a closing bracket, pop to the output until you reach the matching opening one.
左括号直接压栈；遇到右括号，就一直弹出到输出，直到遇见配对的左括号。
At the end, pop everything left.
扫描结束后，把剩下的全部弹出。
Convert A plus B, times C minus D.
来转换 A 加 B，乘以 C 减 D。
The first bracket gives A B plus; push the times; the second bracket gives C D minus; then pop the times.
第一个括号给出 A B 加；压入乘号；第二个括号给出 C D 减；然后把乘号弹出。
The result is A B plus C D minus times.
结果是 A B 加 C D 减 乘。
And here is the check that catches errors: the operands keep their original order, A B C D — only the operators move.
这里有一个能抓出错误的检验： 操作数保持原来的顺序，A B C D——移动的只有运算符。
Evaluating is easier still, using a stack of operands.
求值更简单，用一个操作数栈。
Scan left to right: push each operand; on an operator, pop the top two, apply it, and push the result back.
从左往右扫描：每个操作数就压栈； 遇到运算符，就弹出栈顶的两个，施加运算，再把结果压回去。
Evaluate three plus four, times five minus two, which in RPN is three four plus five two minus times.
来求三加四，乘以五减二，写成逆波兰式就是 三 四 加 五 二 减 乘。
Push three, push four.
压入三，压入四。
The plus pops both and pushes seven.
加号把两个都弹出，压入七。
Push five, push two.
压入五，压入二。
The minus pops both and pushes three.
减号把两个都弹出，压入三。
Now the times pops seven and three, and pushes twenty-one.
现在乘号弹出七和三，压入二十一。
The rule that makes this reliable is that every operator acts on the two values immediately below it on the stack.
让这套方法可靠的规则是：每个运算符作用的，永远是栈中紧挨在它下面的那两个值。
And this is not just an exam exercise — it is exactly how a stack machine works, which is how the JVM and many bytecode interpreters execute code.
而这不只是一道考题——这正是栈式机器的工作方式， Java 虚拟机和许多字节码解释器就是这样执行代码的。
Finally, a neat trick for evaluating expressions.
最后，一个求值表达式的巧妙办法。
In reverse Polish notation — also called postfix — the operator comes after its operands, so no brackets are needed at all.
在逆波兰表示法——也叫后缀表示法——里，运算符跟在它的操作数后面， 所以完全不需要括号。
Three, four, two, times, plus.
三、四、二、乘、加。
Evaluate it with a stack: push each number; when you meet an operator, pop the top two, apply it, and push the result.
用一个栈来求值：把每个数字压进去； 遇到运算符时，弹出最上面的两个，对它们做运算，再把结果压回去。
Four times two is eight; three plus eight is eleven.
四乘二得八； 三加八得十一。
That is exactly how a stack machine — like the one running Java bytecode — does its arithmetic.
这正是栈式机器——比如运行 Java 字节码的那台——做算术的方式。
Three marks to lock in.
三个要拿稳的分。
First, list the stages of compilation and say what each one does.
第一，列出编译的各个阶段，并说清楚每个阶段做什么。
Second, explain virtual memory and paging — disk standing in for RAM — and its cost, thrashing.
第二，解释虚拟内存和分页——用磁盘来顶替内存——以及它的代价，也就是抖动。
Third, evaluate reverse Polish notation with a stack, and use a grammar to test whether a string is valid.
第三，用栈来对逆波兰表示法求值，并用文法来检验一个字符串是否合法。
Nail these, and this topic is yours.
掌握这些，这个专题就是你的了。