CAIE AS and A Level CS revision - Unit 16 (2nd)

【点此返回复习要点目录】

如遇到公式加载异常，请刷新页面！

Unit 16 System Software 系统软件

16.1 Purposes of an Operating System (OS) 操作系统（OS）的目的

• 大纲要求

16.1.1 Show understanding of how an OS can maximise the use of resources 了解操作系统如何最大限度地利用资源

• Multi-programming：多道程序设计，指的是在任何时间点，仅有一个程序能够访问CPU，但其他程序也会准备就绪，等到用户需要访问时可以直接使用。
• Time-sharing system：分时系统，指一些系统被设计成允许多个用户同时登录使用的情况。

• 操作系统的purpose目的：
  • Internal viewpoint：内部观点，关注操作系统内部活动，以便更好地利用相关资源。
  • External viewpoint：外部观点，关注系统提供给用户的设施情况。

• 操作系统的逻辑结构：
  • User mode：用户模式，指用户或应用程序可以调用的一部分操作系统，仅在需要时访问相关内容。
  • Kernel mode：内核模式，指能够访问部分内存和用户模式无法访问的某些系统功能，该部分一直在运转。

• 操作系统的结构示意图：
  • Layered structure：层级结构。用户的应用软件可以调用内核来实现对硬件的控制，但需要下层充分服务于上层。层级结构的示意图如下：

• • Modular structure：模块结构。实现同一功能的服务归为一个模块，内核需要实现该功能时才调用该模块。模块结构能够实现micro-kernel structure微内核结构，将内核部分压缩到最小规模。模块结构的示意图如下：

16.1.2 Describe the ways in which the user interface hides the complexities of the hardware from the user 描述用户界面如何向用户隐藏硬件的复杂性

• User interface用户界面可被用作command line命令行、graphical display图形显示或voice recognition system语音识别系统。
• 操作系统为用户提供了file system文件系统来储存数据和使用程序而无需了解磁盘上的存储结构；操作系统也为程序员提供了编程环境而无需了解处理器功能和硬件的构成结构。
• 操作系统提供application programming interface（API）应用程序编程接口，供多个系统调用，旨在为程序提供可移植性，只需进行很少的修改就能在其他系统中运行。

16.1.3 Show understanding of process management 表现出对流程管理的理解

The concept of multi-tasking and a process 多任务和一个进程的概念
The process states: running, ready and blocked 进程状态：running、ready、blocked
The need for scheduling and the function and benefits of different scheduling routines (including round robin, shortest job first, first come first served, shortest remaining time) 调度的需要以及不同调度例程的作用和好处（包括轮询、最短作业优先、先到先得、最短剩余时间）
How the kernel of the OS acts as an interrupt handler and how interrupt handling is used to manage low-level scheduling OS的内核如何充当中断处理程序以及如何使用中断处理程序来管理低级调度

• 流程管理的重要性：操作系统会确保I/O设备与内存或CPU之间的数据传输，但I/O设备的速度较慢，因此需要对CPU的流程进行管理，确保在输入或输出发生时，CPU不会出现空闲的状态，提高使用效率。
• 程序调度程序分类：
  • High-level scheduler：高级调度程序，也称为long-term scheduler，用于判断是否将disk磁盘中的程序或数据调入main memory内存。
  • Low-level scheduler：低级调度程序，也称为short-term scheduler，用于判断是否将main memory内存中的程序或数据调入CPU。
• 进程状态与切换：process进程在进入内存时会创建process control block（PCB）进程控制块，以便在进程执行时接收数据。进入内存后，state of process进程的状态会根据情况进行切换。常见的状态与切换情况如下所示：

• • New新进程进入内存后，创建PCB，然后进入Ready准备就绪状态。
  • 已经处于ready状态的进程被调入CPU，进入Running运行状态。
  • Running运行状态的进程如果遇到一些无法继续执行下去的情况（比如需要接收输入的数据等），则会进入waiting等待状态（也称为suspended暂停状态或blocked阻塞状态）。
  • 如果阻止进程运行的情况已经排除，进程将进入ready准备就绪状态。之后会重新进行运行。
  • 如果进程全部运行完毕，则由running运行状态转为terminated终止状态。

• Thread：线程，指process进程中拆分出来的一部分。如果进程被拆分成多个线程，则每个线程都应被当作是一个独立的新进程。

• Scheduling algorithm：调度算法，指根据系统的资源分配策略所规定的资源分配算法。
  • 当有多个进程要使用计算机的资源时，因为资源是有限的，因此必须按照一定的原则选择进程来占用资源。
  • 调度算法分类：
    • Non-preemptive algorithm：非抢占式算法，指各个进程之间不构成竞争关系，不会刻意中止其他进程。
    • Preemptive algorithm：抢占式算法，指一项进程的进入会中止之前运行的其他进程。
  • 具体的调度算法包括：
    • First come first served (FCFS)：先到先服务调度算法。该算法将准备就绪的进程按提交顺序或变为准备就绪状态的先后排成队列，并按照先进先处理的方式进行调度处理，是一种最普遍和最简单的方法。该算法属于Non-preemptive algorithm非抢占式算法，效率很低，但可以成为其他高效率算法中的组成部分。
    • Round-robin algorithm：轮询调度算法。该算法为每项进程分配了一定的time slice时间片，执行进程时，如果属于该进程的时间片用尽，则中止该程序并将其排到队列末尾，然后开始执行下一项进程。该算法属于Preemptive algorithm抢占式算法，但通常不涉及优先级问题，会对每项进程进行循环式执行。
    • Priority-based scheduling algorithm：基于优先级的调度算法。该算法根据进程的优先级进行执行，如果有更高优先级的进程进入队列，则立即中止当前进程，开始执行更高优先级的进程。该算法属于Preemptive algorithm抢占式算法。按照判断优先级的方式，可以分为以下类型：
      • shortest job first：短作业优先调度算法。该算法根据进程执行的时间判断优先级，需要时间越短，优先级越高。
      • shortest remaining time：最短剩余时间优先调度算法。该算法根据进程剩余的执行时间判断优先级，剩余时间越短，优先级越高。

• Interrupt：中断，指进程的运行被暂时停止。
  • 中断发生的原因：
    • 进程在运行中需要I/O操作。由于输入或输出耗费的时间较长，因此进程不得不进入中断状态以等待操作完成。
    • Scheduler调度器决定对进程进行中断。比如在Round-robin algorithm轮询调度算法、Priority-based scheduling algorithm基于优先级的调度算法等调度算法中，遇到需要中断当前进程的情况时，调度器便会中断当前进程。【参考16.1.3】
  • 中断的运行操作：当进程被中断时，OS kernel操作系统内核会调用interrupt-handling routine中断处理例程，其中一项操作是要将中断发生时的数据值存入register寄存器内，以便恢复运行时能够重新提取当前数据以便继续进行运算。

16.1.4 Show understanding of virtual memory, paging and segmentation for memory management 展示对虚拟内存、内存管理的分页和分段的理解

The concepts of paging, virtual memory and segmentation 分页、虚拟内存和分段的概念
The difference between paging and segmentation 分页和分段的区别
How pages can be replaced 如何更换页面
How disk thrashing can occur 磁盘抖动是如何发生的

• Memory management：内存管理，包括为内核提供受保护的内存空间、为程序及数据定义内存地址、为各个进程分配运行所需的内存空间、将进程移入或移出内存等。
• 内存管理的方法：
  • Partition：分区。内存被划分成多个区块，每个进程加载入一个区内运行。
    • 存在的问题：如果进程实际所需内存小于分区大小，则会造成内存的浪费。
  • Dynamic partitioning：动态分区。内存被划分成多个区块，允许调整分区大小以匹配进程大小，但每个分区仍然只有一个进程运行。
  • Segment：分段。将大进程划分为若干段，每段被加载入动态分区中运行。
    • 存在的问题：分段时没有限制每段是同样的大小，调整耗时较多。有时无法将所有分段全部加载入内存，需要时得从磁盘调入，耗时、可能无法再次载入或容易出现碎片。
  • Paging：分页。将内存分成大小一致的众多分区，每个分区称为frame帧或page frame页框。操作系统将进程分成多个与页框大小相等的page页，然后给进程的每页分配一个页框的内存，同时用一张page table页表记录来记录页号与内存页框号的映射关系。
    • 注意：为进程分配内存时，不同的进程页可以分配到不连续的内存位置。
    • 注意：如果要使用的页不在内存中，可以根据一些规则将内存中的一页替换掉，比如按照先进先出原则替换，或者将最少使用到的页替换掉等。
  • Virtual memory：虚拟内存，指应用程序认为它拥有连续的可用内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存页，还有部分暂时存储在外部磁盘存储器上，在需要时才进行数据交换。
    • 虚拟内存的问题：disk thrashing磁盘抖动。在分页管理系统中，内存中只存放了那些经常使用的页面，而其它页面则存放在磁盘中。当进程运行需要的内容不在内存时，便启动磁盘读操作将所需内容调入内存，若内存中没有空闲物理块，还需要将内存中的某页面置换出去。系统需要不断地在内外存之间交换信息。若在系统运行过程中，刚被淘汰出内存的页面，过后不久又要访问它，需要再次将其调入。而该页面调入内存后不久又再次被淘汰出内存，然后又要访问它。如此反复，使得系统把大部分时间用在了页面的调入/换出上，几乎不能完成任何有效的工作，这种现象称为抖动。

16.2 Translation Software 翻译软件

• 大纲要求

16.2.1 Show understanding of how an interpreter can execute programs without producing a translated version 理解解释器如何在不产生翻译版本的情况下执行程序

• interpreter解释器对source code源代码进行读取与分析，生成intermediate code中间代码，然后将其合成并生成object code目标代码。示意图如下所示：

16.2.2 Show understanding of the various stages in the compilation of a program 理解程序编译的各个阶段

Including: lexical analysis, syntax analysis, code generation and optimisation 包括：词法分析、语法分析、代码生成与优化

• 程序编译的阶段：
  • Front-end analysis stage：前端分析阶段，指将source code源代码转换为intermediate code中间代码的过程。
    • 前端分析阶段的分过程：
      • lexical analysis：词法分析，指对字符或字符集合的识别。
        • 每个有意义的单个字符或字符集合被称为lexeme词位，比如关键字、符号、运算符等。一种常见的词法分析方法是去掉空格与所有注释内容后，读取一行代码并识别出每个词位。
          • 例子：在var count: integer; 中，一共包含5个词位。
        • 注意：识别出的每个identifier标识符都会被列入symbol table符号表内，便于之后的阶段使用。
        • 注意：词法分析时，会对识别出的非标识符内容做出token标记，输出时的内容是已经做了标记的版本。
      • syntax analysis：语法分析，也称为parsing解析，指对程序结构的分析，了解程序运行时逻辑的先后关系，以syntax tree语法树（又称parse tree解析树）的形式记录下来。
        • 语法树的例子：比如y := 2 * x + 4的语法树可画为如下形式（左中右结构的树）：

• • • • semantic analysis：语义分析，指确定代码的全部含义，将语法树中的各个标识符与其数据类型等属性联系起来，构成annotated abstract syntax tree带有注释的抽象语法树。
      • intermediate code generation：中间代码生成，指根据语义分析的结果转换成中间代码。Reverse Polish Notation（RPN）逆波兰式是最简单的中间代码形式之一。【参考16.2.4】
        • 中间代码形成这一步中，创建的代码多为three-address code三地址码，如果多于三个引用地址，可以通过增加临时变量的方式将代码转换成三地址码。
        • 三地址码的例子：在y := a + (b * c – d) / e的代码中，包含5个引用地址（abcde），因此可以用以下代码来代替上述代码：

temp := b * c
temp := temp – d
temp := temp / e
y := a + temp

• • • Front-end analysis stage前端分析阶段的运行示意图：

• • Back-end synthesis stage：后端综合阶段，指由中间代码生成目标代码的过程。
    • 如果前端分析中发现存在语法错误，则后端过程将仅输出错误列表，包括发生错误的位置以及对错误的解释。
    • 如果前端分析中没有语法错误，则后端综合过程将把中间代码转换为机器代码。在转换过程中，如果涉及到以下情况，则可考虑代码的optimisation优化：
      • 中间代码中的语句逻辑较为复杂，可考虑使用临时变量对复杂语句进行化简。
      • 循环结构中存在着无论如何循环其值都不会改变的语句，可考虑将该语句移出循环体内。
      • 在创建机器代码时，考虑对register寄存器或memory内存的有效使用。

16.2.3 Show understanding of how the grammar of a language can be expressed using syntax diagrams or Backus-Naur Form (BNF) notation 理解如何使用语法图或巴科斯-瑙尔形式 (BNF) 表示法来表达语言的语法

• Syntax diagram：语法图，指用来表示程序语言语法规则的图像。图像从左到右阅读，通常在上部表示流程，在下部表示循环。比如用来表示标识符命名规则（以字母开头，后面跟若干字母或数字）的语法图如下所示：

• Backus-Naur Form（BNF）：巴科斯-诺尔形式，一种形式化的语法表示方法，用来描述程序中的语法。
  • BNF的基本规则：
    • 尖括号“<>”及其中内容：非终结符。如果一个非终结符出现在生成规则的右边，这意味着会有另一条生成规则来解释它。
    • 竖线符号“|”：代表“或”的含义。
    • 符号“::=”：代表“定义为”的含义。
    • 普通字符：对规则的语法解释。
  • BNF的一些例子：

<Identifier> ::= <Letter>|<Identifier><Letter>|<Identifier><Digit>
<Digit> ::= 0|1|2|3|4|5|6|7|8|9
<Letter> ::= <UpperCaseLetter>|<LowerCaseLetter>
<UpperCaseLetter> ::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
<LowerCaseLetter> ::= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z

• • • 第一行代表标识符<Identifier>可以由单独一个<Letter>、<Identifier>后续再加<Letter>或<Identifier>后续再加<Digit>构成。此处的<Identifier><Letter>和<Identifier><Digit>都是递归定义，可以节约循环列举的篇幅。这里的<Letter>和<Digit>都是右侧的非终结符，需要另外的规则进行说明。
    • 第二行对<Digit>进行定义，其代表0~9中的一个数字。
    • 第三行对<Letter>进行定义，包括<UpperCaseLetter>或<LowerCaseLetter>。这两个都是右侧的非终结符，需要另外的规则进行说明。
    • 第四行对<UpperCaseLetter>进行定义，其代表A~Z中的一个大写字母。
    • 第五行对<LowerCaseLetter>进行定义，其代表a~z中的一个小写字母。
    • 至此，所有的非终结符都得到了相应的定义。

• Syntax diagram语法图与BNF的比较：
  • 语法图不能作为算法合并到程序中，用途有限。
  • BNF可描述任何数据组合，用作算法的基础，用途广泛。

16.2.4 Show understanding of how Reverse Polish Notation (RPN) can be used to carry out the evaluation of expressions 了解如何使用逆波兰表示法 (RPN) 来执行表达式的评估

• Reverse Polish Notation：逆波兰式，又称为后缀表达式，是一种简单的中间代码形式。
• 将infix中缀逻辑式写成RPN逆波兰式：
  • 手动修改：按照数学运算律的先后顺序，将每一步中的运算式改写成“标识符 标识符 运算符号”的“左右中”后缀形式。
    • 例子：将a+b*c手动改写成逆波兰式。步骤如下：
      • b*c是最优先计算的，将其改写成bc*。
      • 之后会计算a与bc*这个整体的加法，将其改写成abc*+。
      • 运算完毕，原中缀表达式的RPN是abc*+。
  • 运用syntax tree语法树修改：根据原中缀表达式画出语法树结构，然后按照后序遍历（左右中顺序）进行遍历，写出的式子即为逆波兰式。
    • 例子：将a+b*c运用syntax tree语法树改写成逆波兰式。步骤如下：
      • 根据中缀表达式画出语法树，如下图所示：

• 将该语法树进行“左右中”的后序遍历，得到abc*+，该式即为逆波兰式的表达形式。
  • 运用stack栈修改：将原中缀表达式从左到右依次进行栈操作。如果遇到identifier标识符则直接弹出栈（或理解为无需进栈，直接写入逆波兰式表达）。当遇到运算符号时，如果栈中是空的或仅包含比其运算级别低的运算符号，则该运算符号进入栈中；如果栈中包含比其运算级别高的运算符号，则将高级别的运算符号弹出栈（写入逆波兰式表达），然后再将该运算符号入栈。当所有元素都完成入栈操作后，将栈中剩余的运算符号按顺序弹出并写入逆波兰式表达中。
    • 例子：将a+b*c运用stack栈改写成逆波兰式。步骤如下：
      • a是标识符，直接计入RPN表达，此时RPN表达变为a。
      • +是运算符号，此时栈中是空的，+入栈。
      • b是标识符，直接计入RPN表达，此时RPN表达变为ab。
      • 其中*是运算符号，此时栈中已有的运算符号+低于*的运算级别，因此*入栈。
      • c是标识符，直接计入RPN表达，此时RPN表达变为abc。
      • 原中缀表达式全部元素均运行完毕，将栈中的所有运算符号按照先入后出的栈原则依次弹出并计入RPN表达，此时RPN表达变为abc*+，即为最后的逆波兰式表达。

• 将RPN逆波兰式写成infix中缀表达式：
  • 手动修改：将“标识符 标识符 运算符号”的结构看成一个可改写的部分。从左到右对RPN表达进行改写，每遇到这样的结构就将其改写成“标识符 运算符号 标识符”的形式，然后将改写后的形式作为一个标识符整体处理。
    • 例子：将x 2 * y 3 * + 6 /的逆波兰式改写成中缀表达式。步骤如下：
      • 从左往右读，前三项x2*构成一个可改写的部分，中缀表达式为x*2，此时原逆波兰式变为(x*2) y 3 * + 6 /。
      • 从左往右读，y3*构成一个可改写的部分，中缀表达式为y*3，此时原逆波兰式变为(x*2)(y*3) + 6 /。
      • 从左往右读，(x*2)(y*3)+构成一个可改写的部分，中缀表达式为(x*2)+(y*3) ，此时原逆波兰式变为(x*2)+(y*3) 6 /。
      • 从左往右读，(x*2)+(y*3)6/构成一个可改写的部分，中缀表达式为[(x*2)+(y*3)]/6 ，此时原逆波兰式完全改写完毕。中缀表达式去掉多余的括号，变为(x*2+y*3)/6，即为要求的中缀表达式。
  • 运用stack栈修改：将原RPN表达式从左到右依次进行栈操作。如果遇到identifier标识符则直接入栈。当遇到运算符号时，如果栈的前两层为标识符，则依次弹出两个标识符，成为运算符号的两端，写成“标识符 运算符号 标识符”的形式。将改写好的形式作为一个整体重新入栈。直至所有元素都完成过入栈操作，栈中的元素即为要求的中缀表达式，弹出即可。
    • 例子：将x 2 * y 3 * + 6 /的逆波兰式改写成中缀表达式。步骤如下：
      • 从左往右进行入栈操作。x和2都是标识符类，直接入栈。
      • 其中*是运算符号，弹出之前的两项标识符x和2，与*组成x*2的表达式，再次入栈。
      • y和3都是标识符类，直接入栈。
        • 是运算符号，弹出之前的两项标识符y和3，与*组成y*3的表达式，再次入栈。
      • +是运算符号，弹出之前的两项标识符(x*2)和(y*3)，与+组成(x*2)+(y*3)的表达式，再次入栈。
      • 6是标识符类，直接入栈。
      • /是运算符号，弹出之前的两项标识符(x*2)+(y*3)和6，与/组成[(x*2)+(y*3)]/6的表达式，再次入栈。
      • 全部数据处理完毕，弹出栈内的表达式，去掉多余的括号，变为(x*2+y*3)/6，即为要求的中缀表达式。