EX-CO相关总结

强化梳理

考频

| 考查内容 | 考查次数 |

| ------------------------------------------ | -------- |

| 数据的运算 ，强制类型转换 ，精度、溢出问题 | 3+3 |

| Cache、TLB、虚拟分页 | 8 |

| 一条指令的执行过程 | 6 |

| 指令序列的工作过程 | 4 |

| 三种IO控制方式 | 3 |

| 杂七杂八 | 4 |

二级标题后面括号里面的数字表示09-22年的考频

简单计算

• 主频$f={\displaystyle \frac{1}{T}}$

  • $T$: 时钟周期

• 执行指令(平均)所需时钟周期数$CPI={\displaystyle \frac{m}{IC}}$

  • $CPI(ClockcyclePerInstruction)$

  • $IC$总指令条数

  • $m$执行所需时钟周期数

• 执行指令(平均)所需时钟周期数

  $$\mathrm{CPI}=\sum _{i=1}^n({\mathrm{CPI}}_i\times P_i)=\sum _{i=1}^n({\mathrm{CPI}}_i\times \frac{{\mathrm{IC}}_i}{\mathrm{IC}})$$

  • $P_i$每类指令的使用频率

  • $CP{I}_i$每类指令的$CPI$

  • $I{C}_i$每类指令的条数

• $CPU$时间$T_{\text{cpu}}$：执行程序一共需要多少时间

  $$\begin{gathered} T_{\text{cpu}}=m\times T \\ {T}_{\text{cpu}}=\mathrm{CPI}\times \mathrm{IC}\times T={\displaystyle \frac{\mathrm{CPI}\times \mathrm{IC}}{f}} \end{gathered}$$

• 每时钟周期执行指令条数$IPC={\displaystyle \frac{1}{CPI}}$

• $MIPS(MillionInstructionsPerSecond)$​每秒执行多少百万条指令

  $$\begin{gathered} MIPS={\displaystyle \frac{IC}{T_{\text{cpu}}\times {10}^6}}...(1) \\ MIPS={\displaystyle \frac{f}{CPI}}...(2) \end{gathered}$$
  • 只有在$f$单位是$MHz$时才可以直接用(2)式不然要除以$M({10}^6)$即只能使用(1)式

• 带宽：数据总线一次所能并行传送信息的位数

  • 总线宽度（换算为字节）乘主线时钟频率

  • $\mathcal{ {\normalsize OR} } $总线宽度（换算为字节）除以主线时钟周期

  • 注意带宽的计算$K={10}^3$

第二章数据表示与运算大题(3+3)

考频

大题一般结合C语言程序进行出题，故大题中可以不需要过于关注定点小数

数据的表示

1. 大小端

   1. 数据最左边的高位就是最高有效字节$MSB$。

   2. 数据最右边的低位就是最低有效字节$LSB$。

   3. 大端模式：将$MSB$存到最低地址，$LSB$存在最高地址。便于人类阅读。

   4. 小端模式：将$MSB$存到最高地址，$LSB$存在最低地址。便于机器读取。

   5. 边界对齐：

      • 现代计算机通常是按字节编址即每个字节对应一个地址。也支持按字、按半字、按字节寻址。

      • 假设存储字长为$32$位，则$1$个字=$32bit$，半字$=16bit$。每次访存只能读/写$1$个字。

      • 字地址转换为字节地址，只用逻辑左移两位就可以了，即乘以$4$，因为字长为$32$，而字节长$8$。

      • 使用边界对齐方式会让每个数据都能一次性读完而不用跨行读取，多余的空间用$0$填充。

2. 整数：主要考C语言的常见数据类型

   1. 类型占用：int类型占用4B=32bit，short类型占用2B=16bit，float类型占用4B=32bit，double类型占用8B=48bit，char类型占用1B=8bit

   2. C语言常见整数类型

      1. 无符号整数

         1. unsigned int：$0\sim 2^{32}-1=4,294,967,295$

         2. unsigned short：$0\sim 2^{16}-1=65,536-1=65,535$

      2. 带符号整数

         1. int：$-(2^{31}-1)\sim 2^{31}-1$

         2. short；$-32768\sim 2^{15}-1=32768-1=32767$

3. 浮点数：主要考IEEE754浮点数

   1. | 英文类型 | 中文类型 | 数符位 | 阶码位 | 尾数位 | 总位数 | 十六进制偏置值 | 十进制偏置值 |

      | :---------: | :--------: | :----: | :----: | :----: | :----: | :------------: | :----------: |

      | ==※float== | 短浮点数 | 1 | 8 | 23 | 32 | 7FH | 127 |

      | double | 长浮点数 | 1 | 11 | 52 | 64 | 3FFH | 1023 |

      | long double | 临时浮点数 | 1 | 15 | 64 | 80 | 3FFFH | 16383 |

   2. 强制类型转换

      1. 无损转换：

         • $char$→$int$→$long$→$double$。

         • $float$→$double$。

      2. $int$与$float$转换

         • $int$：表示整数，范围$[-2^{31}，2^{31}-1]$，有效数字$32$位。

         • $float$：表示整数及小数，范围$\pm [2^{-126}，2^{127}\times (2-2^{-23})]$，有效数字$23+1=24$位。

         • $int$→$float$：可能损失精度。

         • $float$→>$int$：可能溢出及损失精度。

4. 定点数强制类型转换

   1. 无符号数与有符号数：不改变数据内容，只改变解释方式。

      • 若最高位为1，则转换前后会出现一个正数和一个负数

      • 此时正负数的绝对值相加等于当前类型的占用位数的理论最大值

        • short类型占用2B=16bit，$2^{16}=65536$

   2. 长整数转短整数：把多余的高位直接截断，只保留低位。

   3. 短整数转长整数：先扩展（按照原来的数据类型选择相应的的扩展法：无符号整数零扩展、带符号整数符号扩展），再解释

      • 符号扩展：扩展后的高位部分用==原数字符号位==填充

      • 零扩展：扩展后的高位部分用0填充

5. 整数和浮点数之间的转换

   1. 整数转☒浮点数：精度丢失问题

   2. 浮点数转整数：溢出问题、精度丢失（⼩数点后的部分）

   

数据的运算

1. 无符号整数和带符号整数的加减法及溢出

   1. 无符号整数和带符号整数均可代入真值计算后==转换为补码==

   2. 加法均为按位相加，溢出位直接舍去，减法均视为减去==减数的负数补码==

      • $[x{]}_{\mathrm{补}}\to [-x{]}_{\mathrm{补}}$：从右往左找到第一个1，这个1左边的==所有位（包括符号位）==按位取反

   3. 溢出判断：均可手算直接判断，计算器中使用符号位判断溢出

      • 无符号数：$OF$（$OverflowFlag$​）

        $$OF=C_0\oplus C_1$$

        • 对于有符号数的溢出判断方式有：

          1. 采用一位符号位：思想为==正正得负或负负得正则为溢出==，其他情况无溢出。

             • 设$A$符号为$A_S$、$B$符号为$B_S$、运算结果符号为$S_S$。

             • 溢出逻辑表达式为$V=A_S{B}_S\overline{S_S}+\overline{A_S{B}_S}{S}_S$。

          2. 采用双符号位：思想为==两符号位不一致即为溢出==，高位符号位代表正确的符号，若$s_1$、$s_2$表示运算结果的两个符号位

      • 有符号数：$CF$（$CarryFlag$​）

        $$CF=C_{out}\oplus Sub$$
        • $Sub$即为加减法控制信号，加法0减法1，$C_{out}$即为最高位产生的进位

2. 无符号整数和带符号整数的乘法

   1. 无符号整数$\to$可使用逻辑左移替代$\times$2

      • 逻辑左移则是将低位移出，高位补零

   2. 带符号整数$\to$可使用算数左移替代$\times$2

      • （补码）算术左移填充0。

   3. 溢出判断

      1. 若n位乘n位，若用2n位保存乘积，则不会溢出

      2. n位乘n位，用2n位保存中间结果，最后截取末尾位作为最终的乘积可能会溢出

         1. 手算判溢出：带入十进制计算结果，判断该结果是否超出了当前类型所能表示的范围，若超出，则溢出

         2. 机器判溢出

            1. 两个无符号数乘法：n位乘n位，用2n位保存中间结果。==仅当前n位都是0时才不溢出==。

            2. 两个有符号补码乘法：n位乘n位，用2n位保存中间结果。==仅当前n+1位全1或全0时不溢出==

3. 无符号整数和带符号整数的除法

   1. 在408中不会发现溢出：==408大纲不会考定点小数和浮点数的乘除运算==

   2. 无符号整数$\to$可使用逻辑右移替代$\div$2

      • 逻辑右移则是将低位移出，高位补零

   3. 带符号整数$\to$可使用算数右移替代$\div$2

      • 算术右移填充原数据的符号位。

4. 硬件相关：不会考太深，知道使用ALU、位移器、寄存器和相应功能及基本原理就行

异或$\oplus$：输入相同时输出为假，否则为真。

• 可以类比正负数乘法

• 正数（符号位）为0，负数（符号位）为1

• 同号相乘得正

  +   $1\oplus 1=0，0\oplus0=0 $

• 异号相乘得负

  +   $1\oplus 0=1，0\oplus1=1 $

第三章存储系统大题(8)

寻址

注意事项

1. 进程以分页的方式存储在内存中，需先将进程进行拆分，再将其放入内存的物理页框中（数据部分和指令部分）

2. 指令的执行需要使用某些数据时，其地址通过逻辑地址（VA）的形式给出；PC指向的也是逻辑地址（VA）；每个进程的部分相同的低地址（或者高地址）都会映射到同一些页框中（相当于页面共享），这些页框中存放的是执行系统调用的代码

3. 虚拟内存地址位数由操作系统位数决定，36位操作系统，即36bit的虚拟地址

4. 页内偏移量位数（页内地址）由页面大小决定，每个页面大小为4KB，即页内地址为12位（物理地址和虚拟地址的页面大小相等，即页内地址位数相同）

5. 物理地址地址位数由物理地址空间大小决定，物理地址空间4GB，即32bit的物理地址（通常物理地址的位数小于虚拟地址的位数）

6. 每个进程一张页表，页表始址存放在该进程的PCB中

虚拟地址=逻辑地址

寻址过程

1. 将逻辑地址转换为物理地址：$CPU$给出逻辑地址，由内存管理单元$MMU$算得<虚拟页号，页内偏移量>，进行越界判断无异常后将页号与快表$TLB$中的所有页号进行比较.

   1. 如果找到匹配的页号且有效位为1(即命中)，说明要访问的页表项在快表$TLB$中有副本。==若快表命中则访问某个逻辑地址仅需一次访存即可==

      1. 全相联映射：位数 = 虚拟页号位数

      2. 组相联映射：位数 = 虚拟页号位数 - 组号位数

      3. 无：

         1. 则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址

         2. 最后访问该物理地址对应的内存单元

   2. 如果未命中即没有找到匹配的页号

      1. 则需要访问==内存中==的页表/慢表，找到对应页表项，得到页面存放的内存块号

         • 若是多级页表，需先将页目录号分成一级页表页目录号和二级页表页号

           • 先查找一级页表，找到匹配的页号且有效位为1则将找到的数据作为起始地址查找二级页表

      2. 再将内存块号与页内偏移量拼接形成物理地址

      3. 最后，访问该物理地址对应的内存单元

      4. 同时将其存入快表，以便后面可能的再次访问

      5. 但若快表已满，则必须按照一定的页面置换算法对旧的页表项进行替换

      6. 因此，==若快表未命中，则访问某个逻辑地址需要两次访存.==

2. 根据物理地址查找数据：将优先访问Cache，速度快得多；未命中再去找主存

   • 查找Cache时将物理地址拆分为<Cache标记Tag，块内偏移量>

     • 先算块内偏移量

       • 首先确定按什么编址，就先把Cache块总大小除以这个编址方式得到总地址数

       • 然后用多少个二进制位能表示这个总地址数块内偏移量就有多少位

     • Cache标记：根据地址映射方式计算

       1. 全相联映射：主存中的每一块可以装入Cache中的任何位置

          ==Tag位数 = 物理地址位数 - 块内地址位数==

          • 用标记对比Cache中的每一行，且有效位为1，根据字块内地址找到某个字 / 字节

       2. 直接映射：对号入座，每一个主存块只能存放在唯一一个地方

          ==Tag位数 = 物理地址位数 - 行号位数 - 块内地址位数（行号 = Cache总行数=Cache总大小 / Cache块大小）==

          1. 根据Cache中有几行，确定行号的位数

          2. Cache标记位数 = 物理地址总位数 - 字块内地址位数

          3. 根据物理地址中行号所对应的位数唯一确定该数据块在Cache中出现的位置

          4. 查询顺序：对比行号→对比Cache标记→对比有效位→根据字块内地址访问Cache块中的某一字 / 字节

          5. Cache中的行号隐含（顺序存储，类似数组）

       3. 组相联映射：按号分组，组内随意放，结合了上面二者的优点

          ==Tag位数 = 物理地址位数 - 组号位数 - 块内地址位数（组号 = Cache总行数 / 几路组相联）==

          • 根据虚拟页号的末尾查找对应的组号→依次对比剩余虚拟页号位是否和组内TLB标记匹配→对比有效位→拼接得到物理地址

          • 主存块装入Cache时默认从0开始按顺序装

   • 查找主存

3. 把数据放到MDR中

<虚拟页号，页内偏移量>和<Cache标记Tag，块内偏移量>是不同的，长度也经常不一致

408中认为主存块和页框是不一样的，主存块和Cache块大小一致，故内存和Cache以块为单位进行数据交换，页框和虚拟页面大小一致，故页框是内存和磁盘之间数据交换的单位

各组件存放位置

1. PCB：抽象为一种数据结构，存放在主存的内核区

2. 页表：存放在主存的内核区

3. 页表始址：指明该进程的页表从哪开始存放，INT型变量，包含于PCB

4. 页表始址寄存器（硬件）：包含于MMU（内存管理单元）中；系统运行进程前（切换进程），CPU将会把页表始址复制到页表始址寄存器中（每个进程的页表始址不同）

5. MMU（硬件）：集成在CPU中

6. TLB（硬件，当前进程页表项的副本）：高速存储器，SRAM，包含于MMU，属于CPU；切换进程后，之前的TLB的有效位全部置为0（TLB是当前进程的页表项副本，故之前进程的TLB作废）

7. Cache（硬件，内存的副本）：高速存储器，包含于CPU，但不属于MMU的一部分；切换进程，Cache进程不作废，不同进程可能共享同一页框

1. TLB和Cache在底层硬件原理上相同，但作用不同

2. 切换进程：页表始址寄存器更新；TLB作废；Cache不需要全部作废，但是会经常出现Cache未命中

主存

1. 交叉编址方式：低位交叉编址

   • 低位是体号，高位是体内地址。

   • 由于每个存储体都是独立的，所以可以间隔一小段时间就能进行另一个的存储单元的访存而不用等待上一个单元的阶数。

   • 若连续取$n$个存储字，每次访问需要$T$的时间，启动间隔为$\tau$，则耗时$T+(n-1)\tau$

   • ==存储周期=总线周期×模块数==

Cache

1. 主存块大小 = Cache块大小；一般地，页框大小 ＞Cache块大小：主存块和页框是不同概念

2. 字块内地址位数决定Cache块的大小，字块内地址6bit即Cache块大小为64B

3. 根据Cache映射方式和Cache块大小确定物理地址的格式结构

4. Cache对所有程序员透明

5. 根据字块内地址确定访问该Cache块中的具体字节 / 字

6. 数据Cache的总位数应包括==标记项的总位数和数据块的位数==。

   • 标记项的总位数=一个标记项总位数$\times$总标记项数（Cache块总数）

     • 每个Cache块对应一个标记项，标记项中应包括

       1. 标记字段：需要计算，主存位数-字块内位数-Cache行数$\mathcal{ {\normalsize OR} } $Cache组数

       2. 有效位：一位

       3. 一致性维护位：“脏”位，仅适用于回写法/写分配法，若采用回写法/写分配法就加一位

       4. 替换算法位，即最近最久未使用置换算法$LRU$：对于$r$路组相联，替换算法为$lo{g}_{2}r$

   • 数据块的位数=总标记项数（Cache块总数）$\times$块大小$\times$8（用字节编址，用什么编址就乘相应位数）

7. 写策略（命中+不命中）

   1. 全写法/直写策略+非写分配法

      1. 全写法/直写策略：写命中时把数据同时写入$Cache$和主存，当某一块需要替换时，不把替换块写回主存，直接用新调入的块直接覆盖即可

      2. 非写分配法：只写入主存，不调入$Cache$

   2. 回写法+写分配法

      1. 回写法：写命中时，只修改$Cache$的内容，而不立即写入主存，只有当此块被换出时才写回主存（全部改完了再写回主存）。

      2. 写分配法：加载主存中的块到$Cache$中，然后更新这个$Cache$块

快表TLB

1. Tag：

   1. 全相联映射：位数 = 虚拟页号位数

   2. 组相联映射：位数 = 虚拟页号位数 - 组号位数

   3. 不可能使用直接映射

2. 有效位：一定存在，且固定为1bit

3. 页框号：由页大小决定（注意区别于主存块大小）

4. 替换信息位：与Cache同理

虚拟存储器

1. 页式虚拟寄存器：虚拟地址=虚页号和页内地址

2. 段式虚拟寄存器：虚拟地址=段号和段内地址

3. 段页式寄存器：虚拟地址=段号+段内页号+页内地址。

第四章指令系统大题(6)

大纲

一般会结合机器级代码（汇编语言）和C语言的对应出题

汇编语言只要求掌握$x86$汇编语言，其他汇编语言会提供注释

机器级代码/汇编语言

汇编语言程序的每行的基本格式为

$$\mathrm{行}\mathrm{号}\mathcal{,}\mathrm{虚}\mathrm{拟}\mathrm{地}\mathrm{址}\mathcal{,}\mathrm{机}\mathrm{器}\mathrm{指}\mathrm{令}\mathcal{,}\mathrm{汇}\mathrm{编}\mathrm{指}\mathrm{令}$$

解题方法

解题方法：

1. 首先先分辨是$x86$还是$MIPS$

   1. 观察是否有注释：通常来说，真题中x86汇编语⾔不会给太多注释（考研中默认⼤家懂 x86）

   2. 观察指令⻓度是否固定

      • $x86$属于$CISC$，指令⻓度不固定

      • $MIPS$属于$RISC$，需要使用指令流水线，指令⻓度固定

   3. 观察寄存器名

      • $x86$的寄存器名为 $eax、ebx、ecx、edx$

      • $MIPS$的寄存器名为$ R[0]、R[1]、R[2]$

2. $x86$：重点关注 intel 格式

   1. 首先先搞懂题上的C语言代码，分析该段代码中的代码结构，带着分析出来的代码结构看汇编代码做题

   2. 分析分支结构：jmp，jxxx

      • 无条件转移指令：jmp

      • 条件转移指令：jxxx，一般会前置cmp指令

        • cmp A，B ：本质是 A-B，A-B 的标志位信息会存放到PSW中

          • 零标志位$ZF$（$ZeroFlag$）：判断当前数字是否为全0值

          • 溢出标志位$OF$（$OverflowFlag$​）：表示带符号整数运算时结果发生溢出

            $$OF=C_0\oplus C_1$$

            • $C_0$：表示运算时符号位(最高位)是否产生进位，若符号位产生进位则为$1$，否则为$0$。

            • $C_1$：表示运算时最高数值位(次高位)是否产生进位，若最高数值位产生进位则为$1$，否则为$0$

          • 符号标志位$SF$（$SymbolFlag$​）：判断当前结果符号

            $$SF=F_{i=max}$$
            • $F_{i=max}$即为运算结果的最高位

          • 进/借位标志位$CF$（$CarryFlag$​）：表示无符号整数数加/减运算时的进位/借位（==溢出==）

            $$CF=C_{out}\oplus Sub$$

            • $Sub$即为加减法控制信号，加法0减法1

            • $C_{out}$即为最高位产生的进位

   3. 分析循环结构：jxxx,loop xxx

   4. 分析函数调用：call,ret

      1. 函数调⽤参数：函数调⽤参数⼀般在 [ebp+8]、[ebp+12] 等位置

      2. 局部变量：局部变量的存储地址⼀般在 [ebp-4]、[ebp-8]、[ebp-12] 等位置

   5. 算数、逻辑运算类指令：加、减、乘、除、左移、右移 等指令

   6. ==$x86$默认小端存储==，实在写不出来可以蒙，尽量验证

机器级语言的过程调用

从上往下是从高位（栈底）到低位（栈顶），局部变量存放在低位（栈顶）下（在栈帧中，通过ebp-4k取得数据），函数调⽤参数存放在低位（栈顶）下（在栈帧外，上一层函数中，通过ebp+4k取得数据）

---

机器级语言的条件转移：==$x86$的转移指令都是相对寻址==

使用条件转移指令实现循环，一般有四个步骤

1. 循环前的初始化

2. 是否直接跳过循环

3. 循环主体

4. 是否继续循环

第五章$CPU$大题(4)

考纲

注释风格

解题思路

1. 分析框架

   1. 取指阶段：把程序计数器$PC$所指的指令从内存中取出来放到指令寄存器$IR$

      • $PC{+}^{\prime }{1}^{\prime }$：这里的1是指令字长，程序计数器$PC$指向的是下一条指令

        • 实现方式

          1. ALU（加法）

          2. 加法器

          3. 有自增功能的寄存器

   2. 执行阶段：根据指令类别思考

      1. 数据传送类：mov、load、store

         1. 寄存器到寄存器

         2. 寄存器到主存

         3. 主存到寄存器

         4. 立即数到寄存器

         5. 立即数到主存

         6. 寄存器到暂存寄存器：通常不是完整指令，通常是某指令的子步骤

            • 常用于ALU操作时

      2. 运算类指令：加、减、乘、除、移位、与、或

         1. 加减运算：加法器Adder，ALU

         2. 自增、自减运算：加法器Adder，ALU，有自增功能的寄存器

         3. 乘除运算：ALU，乘法器、除法器，整数乘除$2^k$也可以使用ALU进行移位运算，带移位功能的寄存器（简称“移位寄存器”）

            • 无符号数乘除运算：逻辑左移、逻辑右移

            • 带符号数乘除运算：算术左移、算术右移

         4. 移位运算：ALU，带移位功能的寄存器（简称“移位寄存器”）

         5. 与运算、或运算、异或运算：ALU，门电路

         6. 非运算：ALU，门电路，带取反功能的寄存器

         7. 求补码，求负值：ALU，带特殊功能的寄存器

         8. 符号扩展、零扩展：ALU，带特殊功能的寄存器，符号扩展器、零扩展器

            • 符号扩展：扩展带符号数

            • 零扩展：扩展无符号数

      3. 转移类指令：jmp、jxxx，可能改变PC值（重点真题2013年真题第44题，王道书2024版4.2.3大题第八题）

         1. 前置条件：cmp A，B ：本质是 A-B，A-B 的标志位信息会存放到PSW中

            • 零标志位$ZF$（$ZeroFlag$）：判断当前数字是否为全0值

            • 溢出标志位$OF$（$OverflowFlag$​）：表示带符号整数运算时结果发生溢出

              $$OF=C_0\oplus C_1$$

              • $C_0$：表示运算时符号位(最高位)是否产生进位，若符号位产生进位则为$1$，否则为$0$。

              • $C_1$：表示运算时最高数值位(次高位)是否产生进位，若最高数值位产生进位则为$1$，否则为$0$

            • 符号标志位$SF$（$SymbolFlag$​）：判断当前结果符号

              $$SF=F_{i=max}$$
              • $F_{i=max}$即为运算结果的最高位

            • 进/借位标志位$CF$（$CarryFlag$​）：表示无符号整数数加/减运算时的进位/借位（==溢出==）

              $$CF=C_{out}\oplus Sub$$

              • $Sub$即为加减法控制信号，加法0减法1

              • $C_{out}$即为最高位产生的进位

         2. 原理：根据标志位判断是否转移（指令中会给出偏移量，注意偏移量是按字为单位还是以字节为单位）

            1. 确定指令寻址方式

               1. 相对寻址：$PC+$偏移量，偏移量可能为正为负

               2. 直接寻址方式（比较少见）

            2. 注意程序计数器$PC$的值

               1. 以字节为单位：$RISC,CISC$

               2. 以指令字为单位：$RISC$

2. 硬件实现与数据流

   1. 主存读写

      1. 读主存

         1. 把地址放到$MAR$

         2. $CU$发出读命令

         3. $M(MAR)\to MDR$

         4. $MDR$到目的地

      2. 写主存

         1. 地址到$MAR$

         2. 数据到$MDR$

         3. $CU$发出写命令

         4. $MDR\to M(MAR)$

   2. 主线占用：安排控制信号，总线是临界资源

   3. 对用户是否透明：取决于该部件的功能是否有必要被用户操作

      • 对所有用户/程序员可见：程序计数器$PC$，通用寄存器组$X$，累加寄存器$ACC$

      • 对汇编程序/汇编程序员可见：编写汇编程序需要的，用户可见的汇编程序员也可见

        • 中断字寄存器：可以修改中断的优先级

        • 中断保存的==现场信息==

        • 基址寄存器：基址寻址

        • 变址寄存器：变址寻址，如数组的访问需要

        • 程序状态字寄存器$PSW$：有无进位$CF$、有无溢出$OF$、结果正负$SF$、结果是否为零$ZF$

      • 完全透明，对所有用户不可见

        • 指令寄存器$IR$，最常考

        • 微指令寄存器$\mu IR$，包括它的好朋友们$\mu MAR,\mu MDR$

        • 暂存寄存器$R$

        • 高速缓存$Cache$

        • 存储器地址寄存器$MAR$

        • 存储器数据寄存器$MDR$

        • 微程序的结构和功能

取指周期数据流

$PC$中存放的是指令的地址，根据此地址从内存单元中取出的是指令，并放在指令寄存器$IR$中，==取指令的同时，PC内容+1==。 取指周期的数据流向如下：

1. $PC\stackrel{(1)}{⟶}MAR\stackrel{(2)}{⟶}$地址总线$\stackrel{(3)}{⟶}$主存

   1.   当前指令地址送至存储器地址寄存器，记做：$(PC)\rightarrow MAR$。

   2.   $MAR$将地址码发送到地址总线。

   3.   地址总线将地址发送给存储器，等待使用地址。

2. $CU$发出读命令$\stackrel{(4)}{⟶}$控制总线$\stackrel{(5)}{⟶}$主存。

   4.   $CU$发出控制读信号给控制总线。

   5.   控制总线将控制读的信号发送给存储器。启动存储器做读操作，这是**读信号**，记做：$1\rightarrow R$。

        + $R$(头上没有横杠)表示高电平激活，这里$1$表示高电平

3. 主存$\stackrel{(6)}{⟶}$数据总线$\stackrel{(7)}{⟶}MDR\stackrel{(8)}{⟶}IR$ （存放指令）。

   6.   存储器根据**地址总线**传来的地址信息和**控制总线**传来的控制读信息来进行读操作，从中读出数据，并将地址所指的数据发送给数据总线。

   7.   数据总线将数据送入$MDR$，记做：$M(MAR)\rightarrow MDR$。

        + $M(MAR)$指主存$(Memory)$中$MAR$存储地址所指的数据

   8.   将$MDR$中数据（此时是指令内容）**复制**送入$IR$，记做：$(MDR)\rightarrow IR$。

4. $CU$发出控制信号$\stackrel{(9)}{⟶}PC$内容+1

   9.   $CU$发出控制信号，控制$PC$形成下一条指令地址，默认是加一，记做：$(PC)+1\rightarrow PC$。

---

间址周期（以一次间址为例）：将指令中的地址码送到$MAR$并送至地址总线，此后$CU$向存储器发读命令，以获取有效地址并存至$MDR$。

间址周期的数据流向如下：

1. $Ad(IR)\mathbb{OR}MDR\stackrel{(1)}{⟶}MAR\stackrel{(2)}{⟶}$地址总线$\stackrel{(3)}{⟶}$主存。

   1.   $IR$将指令的地址码送入$MAR$，记做：$Ad(IR)\rightarrow MAR {\tiny \mathbb{OR}}  Ad(MDR)\rightarrow MAR$。

        + 由于取指周期$(MDR)\rightarrow IR$时，$MDR$是复制一份地址码送入$IR$的，此时$MDR$中还留有地址码

   2.   $MAD$将地址码发送到地址总线。

   3.   地址总线将地址发送给存储器，等待使用地址。

2. $CU$发出读命令$\stackrel{(4)}{⟶}$控制总线$\stackrel{(5)}{⟶}$主存。

   4.   $CU$发出控制读信号给控制总线。

   5.   控制总线将控制读信息发送到存储器中，启动主存做**读操作**，记做：$1\rightarrow R$。

3. 主存$\stackrel{(6)}{⟶}$数据总线$\stackrel{(7)}{⟶}MDR$ （存放有效地址）$\underline{\stackrel{(8)}{\longrightarrow}Ad(IR)} $

   6.   存储器根据地址总线传来的地址信息和控制总线传来的控制 读信息来进行读操作，从中读出数据，并将地址所指的数据发送给数据总线。

   7.   数据总线将数据送入$MDR$，记做：$M(MAR)\rightarrow MDR$

        +   ==此时$MDR$保存的是操作数的地址而不是操作数本身==。

   8.   将有效地址送至指令的地址码字段，记做：$MDR\rightarrow Ad(IR)$。

        + ==这一步只有部分$CPU$会有==

        + 这一步会将有效地址覆盖于原指令的间接地址

第六章总线(0)

主要考察小题

第七章$I/O$大题(3)

• ==若准备数据的时间小于取走数据的时间，则数据会被刷新，造成丢失==

  • 准备数据的时间：①缓冲区大小$\div $ ②I/O速率=③最大准备数据时间，单位$n({10}^{-9})s，\mu ({10}^{-6})s，m({10}^{-3})s$等，每轮的查询时间必须小于等于这个时间，才能来得及把数据取走

    • 可以理解为工人把货物一个个搬过来，缓冲区大小就是仓库大小，I/O速率是工人的速度，没来得及取走数据只能放在外面容易丢

    • 若取④取走数据的时间=③最大准备数据时间，则⑤每秒的查询次数最小，⑤每秒的查询次数至少为1$÷$④取走数据的时间=②I/O速率$\div $①缓冲区大小

  • 取走数据的时间：每轮的查询时间

    • 中断I/O方式：中断响应和中断处理的总时间

    • DMA：会自己把数据取出

• CPU用于查询的时间占总时间的最小比例：一秒内CPU用于设备A输入/输出的所需时钟周期占总时钟周期(即主频)的比率

  • 先算出一次数据传送所用的时钟周期

  • 然后算出每秒的总数据传输次数（即每秒申请的中断次数）

  • 相乘得到用于中断的开销时钟周期

  • 除以主频即为所求

• DMA方式

  • 后处理包含对DMA中断的处理

  • DMA⑤每秒的查询次数最多为②I/O速率$\div $①缓冲区大小

易错

字

字、字长、机器字长、指令宇长、存储字长和字节

• 字节是固定单位，一个字节始终等于8位，$1B=8bit$，与以下其他没有联系

• 字用来表示被处理信息的单位，用来度量数据类型的宽度，如x86机器中将一个字定义为16位。

• 字长/机器字长：在通常所说的“某16位或32位机器”中，16、32指的是字长，也称机器字长。

  • 所谓字长，通常是指CPU内部用于整数运算的数据通路的宽度，

  • 因此字长等于CPU内部用于整数运算的运算器位数和通用寄存器宽度，它反映了计算机处理信息的能力。

  • ==决定了虚拟地址的长度==

• 存储字长：一个存储单元存储的二进制代码的长度。

  • 早期的存储字长一般与指令字长、字长相等，因此访问一次主存便可取出一条指令或一个数据。

  • 随着计算机的发展，指令字长、字长都可变，但==必须都是字节的整数倍==。

• 指令字长：一个指令字中包含的二进制代码的位数。

  • 指令字长一般是存储字长的整数倍，这是为了硬件设计方便，而不是必然的关系。

    • 若指令字长等于存储字长的$n$倍，则需要$n$个访存周期来取出一条指令

    • 若指令字长等于存储字长，则取指周期等于机器周期。

  • ==实际上指令字长取决于操作码长度、地址码长度和地址码个数==。

    • 与机器字长没有必然的联系

    • 但为了硬件设计方便，指令字长一般取字节或存储字长的整数倍

各种硬件的位数

| 硬件 | 位数 |

| ---------- | ---------------- |

| ALU | 机器字长 |

| 通用寄存器 | 机器字长 |

| IR | 指令字长 |

| PC | 对应存储单元个数 |

| MAR | 对应存储单元个数 |

| MDR | 存储字长 |

• $ALU$

  • 基本ALU具有三个并行数据总线，包括两个输入操作数A、B和一个结果输出Y，且A、B、Y总线宽度相同。

  • ALU的宽度即ALU运算对象的宽度，通常与字长/机器字长相同

  • ALU是CPU的核心部分，能直接处理的二进制数据位数（输入的操作数的位数）等于==机器字长==。

• 通用寄存器

  • ALU操作数的来源通常是通用寄存器

  • 因此通用寄存器位数=输入ALU的操作数的位数===机器字长==。

• 指令寄存器$IR$

  • IR用于保存当前正在执行或解码的指令，在简单的处理器中，每条要执行的指令都被加载到IR中

  • 其位数取决于==指令字长==。

• 程序计数器$PC$

  • 用于存放下一条要执行的指令在主存中的地址。

  • 位数取决于==可寻址内存==，例如，PC宽度为$32$位能够寻址$2^{32}$个存储单元。

  • 所以PC的位数n反映了主存的容量。

• 地址寄存器$MAR$

  • MAR里保存着需要访问的数据的内存位置。

  • ==位数同PC，由存储单元的个数决定==。

• 数据寄存器$MDR$

  • $MDR$充当处理器和内存单元之间的缓冲区，存放指令或地址（间接寻址）。

  • 一个要存储的字必须传送到$MDR $，从那里转到特定的内存位置。

  • $MDR$的位数由==存储字长==决定。

• 按字节/字/X bit编址

  • 按字节/字/Xbit编址分别表示存储空间的最小编址单位是字节/字/Xbit，

  • 用白话说，每个存储单元里的二进制代码位数为1字节/1个字长/Xbit

  • 这个长度就是存储单元长度，也即==存储字长==。

• 地址总线

  • 地址总线位数决定了CPU可以直接访问的RAM的最大数量，因为每根线对应一个地址位。

    • 有多少位就可以传输多少位的数据

    • 例如，具有32位地址总线的计算机可以传输32位/4B的数据

  • 例如：

    • 具有32位地址总线的计算机可以直接寻址4GB（$2^{32}$B ）的物理内存

    • 而36位的计算机可以寻址64GB($2^{36}$B)。

  • 如果I/O端口和主存地址空间统一编址，也要把I/O端口的数量考虑进去。

• 数据总线

  • 数据总线==可以双向传输，其位数和机器字长、存储字长有关==

    • 有多少位就可以传输多少位的数据

    • 例如，具有32位数据总线的计算机可以传输32位/4B的数据

  • ==如果等于机器字长，那么传输一次刚好可以处理一次==

  • ==如果等于存储字长，那么传输一次刚好可以读写一次==。

  • 数据总线的位数与处理器的位数相同，它表示CPU 一次能处理的数据的数，即==CPU的位数==

• 总线宽度

  • 总线宽度又称总线位宽，是该总线可同时传输数据的位数，通常指==数据总线的根数==。

若存储器容量为$64K\times 32$位，则主机内各个寄存器位数为

| ACC | MQ | ALU | X | IR | MDR | PC | MAR |

| ---- | ---- | ---- | ---- | ------------------ | ---- | ---- | ---- |

| 32 | 32 | 32 | 32 | 32，取决于指令字长 | 32 | 16 | 16 |

存储容量=存储单元个数$\times$存储字长，$64K=2^{16}$，因此PC和MAR为16位，而MDR为 32位，其他寄存器的位数与MDR的相等。

※※※※※※※※※※※※※※※※※※※

前面的=存储单元个数=地址总数=存储地址$\to$与寻址有关的（PC和MAR），地址总线/字扩展法，位数决定物理地址长度

后面的=每一个地址里面存放的数据的长度（字长）=与数据、计算（数据处理）和指令内容（==但不完全等于==）有关的，数据总线/位扩展法，位数决定逻辑地址长度

※※※※※※※※※※※※※※※※※※※

程序计数器$PC$存放==下一条指令==的实际==存放地址==

指令寄存器IR存放==当前指令本身==

※K的换算

通常前者用大写的$K$，后者用小写的$k$，但其他前缀均为大写，表示的含义取决于所用的场景。

• ==在描述存储容量、文件大小等时，$K、M、G、T$通常用$2$的幂次表示，如$1Kb=2^{10}b$;==

  • 计算机内部的$K$基本都表示$1024$

• ==在描达速率、频率等时，$k、M、G、T$通常用$10$的幂次表示，如$1kb/s={10}^{3}b/s$。==

  • $CN$中在计算信号的传输速率时表示$1000$

  • $CO$中总线的==数据传输率==/总线带宽表示$1000$

对用户是否透明

取决于该部件的功能是否有必要被用户操作

• 对所有用户/程序员可见：程序计数器$PC$，通用寄存器组$X$，累加寄存器$ACC$

• 对汇编程序/汇编程序员可见：编写汇编程序需要的，用户可见的汇编程序员也可见

  • 中断字寄存器：可以修改中断的优先级

  • 中断保存的==现场信息==

  • 基址寄存器：基址寻址

  • 变址寄存器：变址寻址，如数组的访问需要

  • 程序状态字寄存器$PSW$：有无进位$CF$、有无溢出$OF$、结果正负$SF$、结果是否为零$ZF$

• 完全透明，对所有用户不可见

  • 指令寄存器$IR$，最常考

  • 微指令寄存器$\mu IR$，包括它的好朋友们$\mu MAR,\mu MDR$

  • 暂存寄存器$R$

  • 高速缓存$Cache$

  • 存储器地址寄存器$MAR$

  • 存储器数据寄存器$MDR$

  • 微程序的结构和功能

标志位

带标志位加法器的四个标志位

零标志位

即$ZF$（$ZeroFlag$）。判断当前数字是否为全0值。

• $ZF=1$表示结果为$0$。

• 无论是有符号数还是无符号数，$ZF$都有意义。

• 通过加法电路和最后的取反操作实现。

溢出标志位

即$OF$（$OverflowFlag$）。表示带符号整数运算时结果发生溢出。

• $OF=1$表示溢出。

• 根据数据位和符号位的进位情况判断溢出，思想为==符号位进位和最高数值位进位不同则溢出，相同则无溢出==:

  $$V=C_0\oplus C_1$$

  • $C_0$：表示运算时符号位(最高位)是否产生进位，若符号位产生进位则为$1$，否则为$0$。

  • $C_1$：表示运算时最高数值位(次高位)是否产生进位，若最高数值位产生进位则为$1$，否则为$0$

• 对于无符号整数运算，$OF$没有意义。

符号标志位

即$SF$（$SymbolFlag$）。判断当前结果符号。

• $SF=1$表示结果为负值。

• 当产生溢出时，符号标志位置出错。

• 计算方式为：

  $$SF=F_{i=max}$$
  • $F_{i=max}$即为运算结果的最高位

• 对于无符号整数运算，$SF$没有意义。

进/借位标志位

即$CF$（$CarryFlag$）。表示无符号整数数加/减运算时的进位/借位（溢出）。

• $CF=1$表示无符号数加法溢出/减法借位。

• 计算方式为：

  $$CF=C_{out}\oplus Sub$$

  • $Sub$即为加减法控制信号，加法0减法1

  • $C_{out}$即为最高位产生的进位

• ==对于有符号数的整数运算，$CF$没有意义。==

调度算法

作业与进程的调度算法

• 适用于批处理系统算法：

  • $FCFS$.

  • $SJF/SPF/SRTN$.

  • $HRRN$.

• 适用于交互式系统算法：

  • $RR$.

  • $PS$.

  • $MFQ$.

|   | 先来先服务 | 短作业优先 | 高响应比优先 | 时间片轮转 | 多级反馈队列 |

| :----------: | :----------: | :----------------------------: | :----------------: | :----------------------------------: | :--------------------------------------: |

| 能否是可抢占 | 否 | 是 | 是 | 是 | 队列内算法不一定 |

| 优点 | 公平实现简单 | 平均等待时间最少，效率最高 | 兼顾长短作业 | 兼顾长短作业 | 兼颐长短作业，有较好的响应时间，可行性强 |

| 缺点 | 不利于短作业 | 长作业会饥饿，估计时间不易确定 | 计算响应比的开销大 | 平均等待时间较长，上下文切换浪费时间 | 无 |

| 适用于 | 无 | 作业调度，批处理系统 | 无 | 分时系统 | 通用 |

| 默认决策模式 | 非抢占 | 非抢占 | 非抢占 | 抢占 | 抢占 |

$CPU$繁忙型更接近于长作业，少$I/O$所以少中断.而$I/O$繁忙型需要大量$I/O$，等待输入输出数据时会阻塞从而重新排队，所以更接近短作业.

算法评价指标

• $CPU$利用率：$CPU$忙碌时间占总时间的比例.

  • $CPU$利用率=$CPU$忙碌（运行）时间÷进程运行总时间.

  • $CPU$是计算机系统中最重要和昂贵的资源之一，所以应尽可能使$CPU$保持“忙”状态，使这一资源利用率最高

• 系统吞吐量：单位时间内完成作业的数量.

  • 系统吞吐量$={\displaystyle \frac{\text{总共完成多少道作业}}{\text{总时间}}}$.

• 周转时间：从作业被提交到系统开始到作业完成为止的时间间隔.

  • 它包括四个部分：

    1. 作业在外存后备队列上等待作业调度（高级调度）的时间

    2. 进程在就绪队列上等待进程调度（低级调度）的时间

    3. 进程在$CPU$上执行的时间

    4. 进程等待$I/O$操作完成的时间.

    后三项在一个作业的整个处理过程中，可能发生多次.

  • （作业）周转时间=作业完成时间-作业提交时间.

  • 平均周转时间$={\displaystyle \frac{\text{各作业周转时间之和}}{\text{作业数}}}$.

  • 带权周转时间$={\displaystyle \frac{\text{作业周转时间}}{\text{作业实际运行的时间}}}={\displaystyle \frac{\text{作业完成时间}-\text{作业提交时间}}{\text{作业实际运行的时间}}}⩾1$.是一个比值，越靠近$1$越合理.

  • 平均带权周转时间$={\displaystyle \frac{\text{各作业带权周转时间之和}}{\text{作业数}}}$.

• 等待时间：指进程或作业处于等待处理机状态时间之和.

  • 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和

  • 在等待$I/O$完成的期间其实进程也是在被服务的，所以不计入等待时间.

  • 对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间.

  • 一个作业总共需要被$CPU$服务多久，被$I/O$设备服务多久一般是确定不变的，因此==调度算法其实只会影响作业或进程的等待时间==

    • 当然，与前面指标类似，也有“平均等待时间”来评价整体性能.

  • 如果一个进程到达后要么等待要么运行，则等待时间=周转时间-运行时间.

  • 如果一个进程又有计算又有$I/O$操作，则等待时间=周转时间-运行时间-$I/O$操作时间.

• 响应时间：从用户提交请求到首次产生响应所用的时间

  • 主要用于交互式系统.

先来先服务调度算法$FCFS$

即$FCFS(First-Come，First-Served)$算法.

• 算法思想：主要从“公平”的角度考虑.

• 算法规则：按照作业/进程到达的先后顺序进行服务.

• 用于作业/进程调度：既可用于作业调度，又可用于进程调度

  • 用于作业调度时，考虑的是哪个作业先到达后备队列

  • 用于进程调度时，考虑的是哪个进程先到达就绪队列.

• 是否可抢占：非抢占式的算法.

• 特点：

  • 优点：公平、算法实现简单.

  • 缺点：排在长作业/进程后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好.

    • 即$FCFS$算法对长作业有利，对短作业不利.

    • ==不能作为分时系统和实时系统的主要调度策略.==

  • 但它常被结合在其他调度策略中使用。

    • 例如，在使用优先级作为调度策略的系统中，往往对多个具有相同优先级的进程按$FCFS$原则处理。

  • 利于$CPU$繁忙型作业，不利于$I/O$繁忙型作业（即适用于长作业类型）.

• 是否会导致饥饿：不会.

短作业优先调度算法$SJF$

即$SJF(ShortestJobFirst)$算法.

• 算法思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间.

• 算法规则：最短的作业/进程优先得到服务（==所谓“最短”，是指要求服务时间最短==）.

• 用于作业/进程调度：==即可用于作业调度，也可用于进程调度.==

  • 用于进程调度时称为短进程优先$SPF(ShortestProcessFirst)$算法

• 特点：

  • 优点：“最短的”平均等待时间、平均周转时间.

  • 缺点：

    • 不公平.==对短作业有利，对长作业不利==.

    • 可能产生饥饿现象.

    • 未考虑作业紧迫性.

    • 另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先.

• 是否可抢占：$SJF$和$SPF$都是非抢占式的算法.但是也有抢占式的版本：最短剩余时间优先算法$SRTN（ShortestRemainingTimeNext）$

  • 最短剩余时间优先算法$SRTN$：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列.另外，当一个进程完成时也需要使用$SRTN$进行调度

• 是否会导致饥饿：会.

  • 如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象.如果一直得不到服务，则称为“饿死”.

1. 如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的.

2. 很多书上都会说“$SJF$调度算法的平均等待时间、平均周转时间最少”，严格来说，这个表述是错误的，不严谨的.

  + **最短剩余时间优先算法$SRTN$得到的平均等待时间、平均周转时间还要更少.**

  + 应该加上一个条件“在所有进程同时可运行时，采用$SJF$调度算法的平均等待时间、平均周转时间最少”，或者说“在所有进程都**几乎**同时到达时，采用$SJF$调度算法的平均等待时间、平均周转时间最少”.

  + 如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法（最短剩余时间优先，$SRNT$算法）的平均等待时间、平均周转时间最少”.

3. 虽然严格来说，$SJF$的平均等待时间、平均周转时间并不一定最少，但相比于其他算法（如$FCFS$），$SJF$依然可以获得较少的平均等待时间、平均周转时间.

4. 如果选择题中遇到“$SJF$算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项.

高响应比优先调度算法$HRRN$

即$HRRN$算法，高响应比优先调度$HRRN$算法主要用于作业调度

• 算法思想：要综合考虑作业/进程的等待时间和要求服务的时间，是$FCFS$和$SJF$的综合.

• 算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务.

  • 响应比$R_P={\displaystyle \frac{\text{等待时间}+\text{要求服务时间}}{\text{要求服务时间}}}⩾1$.

• 用于作业/进程调度：==即可用于作业调度，也可用于进程调度，但是主要用于作业调度.==

• 是否可抢占：非抢占式的算法.

  • 因此只有当前运行的作业/进程主动放弃处理机(正常/异常完成，或主动阻塞)时，才需要调度，才需要计算响应比.

    • 只有存在$I/O$操作的进程队列才会存在主动阻塞的情况

• 特点：

  • 综合考虑了等待时间和运行时间（要求服务时间）.

  • 等待时间相同时，要求服务时间短的优先，有利于短作业

    • $SJF$的优点

  • 要求服务时间相同时，等待时间长的优先

    • $FCFS$的优点

  • 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题.

• 是否会导致饥饿：不会.

优先级调度算法$PS$

也称为优先权调度算法，即$PS（PrioritySchedulingAlgorithm）$算法.

==优先级调度算法既可用于作业调度，又可用于进程调度==

• 算法思想：随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序.

• 算法规则：==调度时选择优先级最高的作业/进程.==

  • $I/O$繁忙型作业要优于计算繁忙型作业

    • 因为$I/O$操作需要及时完成，其无法长时间保存输入输出数据

  • 系统进程的优先权应高于用户进程优先权.

• 用于作业/进程调度：==既可用于作业调度，也可用于进程调度.甚至，还会用于在之后会学习的$I/O$调度中.==

• 是否可抢占：抢占式、非抢占式都有，做题时的区别在于：

  • 非抢占式只需在进程主动放弃处理机时进行调度即可.

  • 抢占式还需在就绪队列变化时，检查是否会发生抢占，若优先级更高的进程进入就绪队列，则立刻暂停正在运行的进行.

• 特点：

  • 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统

    • 可灵活地调整对各种作业/进程的偏好程度.

  • 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿.

• 是否会导致饥饿：会.

  • 见上，若源源不断地有高优先级进程到来，则可能导致饥饿.

• 优先数与优先级的关系要看具体情况，如$Windows$优先级与优先数成正比，$UNIX$中成反比.

• 优先级调度算法中就绪队列未必只有一个，可以按照不同优先级来组织.

• 可以把优先级更高的进程排在队头位置.

• 根据优先级是否可以动态改变，分为：

  • 静态优先级：创建进程时确定，一直保持不变.

    • 依据

      1. 进程类型

      2. 进程对资源的要求

      3. 用户要求.

  • 动态优先级：创建进程时有初始值，之后根据情况动态调整优先级.

    • 依据

      1. 进程占用$CPU$时间的长短

      2. 就绪进程等待$CPU$时间的长短.

• 设置进程优先级：

  • 系统进程高于用户进程.

  • 前台进程高于后台进程

    • 即交互性进程高于非交互性进程.

  • 操作系统更偏好$I/O$型进程（$I/O$繁忙型进程）而不是计算型进程（$CPU$繁忙型进程）

    • $I/O$设备和$CPU$可以并行工作

    • 如果优先让$I/O$繁忙型进程优先运行的话，则越有可能让$I/O$设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升.

• 调整动态优先级：

  • 若进程在就绪队列中等待了很长时间，则提升其优先级.

  • 若进程占用处理机很长时间，则降低其优先级.

  • 若进程频繁进行$I/O$操作，则提升其优先级.

时间片轮转调度算法

即$RR(Round-Robin-Scheduling-Algorithm)$算法.

• 算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应.

• 算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如$100ms$）.若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队.

• 用于作业/进程调度：用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）.

• 是否可抢占：若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法.由时钟装置发出时钟中断来通知$CPU$时间片已到.

• 特点：

  • 优点：

    • 公平.

    • ==响应快，适用于分时操作系统.==

  • 缺点：

    • 由于高频率的进程切换，因此有一定开销.

    • 不区分任务的紧急程度.

• 是否会导致饥饿：不会.

• 常用于分时操作系统，更注重响应时间，所以不怎么关系周转时间.

• 在时间片轮转调度算法中，时间片的大小对系统性能的影响很大

  • 如果时间片太大，每个进程在一个时间片内就可以完完成，则时间片轮转算法会退化为先来先服务$FCFS$算法，增大进程响应时间，所以时间片不能太大.

  • 如果时间片太小，进程切换会频繁发生，需要保存现场恢复环境，增加时间开销.

  • 时间片分片因素：系统响应时间、就绪队列中的进程数目、系统处理能力.

  • 一般设计时间片段时要让切换进程的开销不超过$1\mathrm{\%}$.

多级反馈队列调度算法

即$MFQ$算法.

• 算法思想：对时间片轮转调度算法和优先级调度算法的折中权衡，动态调整进程优先级和时间片大小.

• 算法规则：

  1. 设置多级就绪队列，各级队列优先级从$1$到$k$依次递减，时间片从小到大依次变大一倍.

  2. 新进程到达时先进入第$1$级队列队尾，按$FCFS$原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾.如果此时已经是在最下级的队列，则重新放回该队列队尾.若是被剥夺，则回退到该队列队尾.

  3. 只有第$k$级队列为空时，才会为$k+1$级队头的进程分配时间片，当又有新进程进入优先级较高的队列则立刻抢占给更够优先级的进程.

• 用于作业/进程调度：用于进程调度.

• 是否可抢占：一般认为是抢占式的

  • 抢占式的算法.在$k$级队列的进程运行过程中，若更上级的队列（$1\sim k-1$级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回$k$级队列队尾.

• 优缺点：

  • 对各类型进程相对公平（$FCFS$的优点）.

  • 每个新到达的进程都可以很快就得到响应（$RR$的优点）.

  • 短进程只用较少的时间就可完成($SPF$的优点）.

  • 不必实现估计进程的运行时间（避免用户作假）.

  • 可灵活地调整对各类进程的偏好程度

    • 比如$CPU$密集型进程、$I/O$密集型进程

    • 拓展：可以将因$I/O$而阻塞的进程重新放回原队列，这样$I/O$型进程就可以保持较高优先级

  • 一般不说认为$MFQ$算法有缺点，不过可能导致饥饿

• 是否会导致饥饿：会.

各就绪队列的调度算法也可能不是时间片调度算法而是别的，但是基本上都是差不多的计算方式.

多级队列调度算法

• 系统中按进程类型设置多个队列，进程创建成功后插入某个队列

• 队列之间可采取固定优先级，或时间片划分

  • 固定优先级：高优先级空时低优先级进程才能被调度

  • 时间片划分：如三个队列分配时间$50$

• 各队列可采用不同的调度策略

  • 系统进程队列采用优先级调度

  • 交互式队列采用$RR$

  • 批处理队列采用$FCFS$