16年

单周期数据通路

单周期数据通路是一种简单的数据通路设计，每个时钟周期执行一条完整的指令，即每条指令的CPI为1，要考虑比较慢的指令，所以处理器的时钟频率较低。 这意味着每条指令执行过程中任何数据通路单元都只能被用一次，如果需要使用多次则必须将该数据通路单元复制多份。

控制信号是CU根据指令操作码发出的信号，对于单周期处理器来说，每条指令的执行只有一个时钟周期，而在一个时钟周期内控制信号并不会变化。

单周期数据通路必须有独立的指令存储器和数据存储器，因为处理器在一个周期内只能操作每个部件一次，而在一个周期内不可能对一个单端口存储器进行两次存取。且无法使用单总线数据通路，因为单总线数据通路将所有寄存器的输入出端都连接在一条公共通路上，一个时钟内只允许一次操作，无法完成指令的所有操作。

TSL指令实现互斥

1
2
3
4
5
6

do {
    while (TSL(&lock));
    critical section;
    lock = FALSE;
    ......
} while (TRUE);

退出临界区的进程负责唤醒就绪态进程？

因为在TSL方法下，一个进程只有两种状态：

  1. 运行态：用户处于了do{ }中，那么不管是是在其中的while (TSL(&lock))不断地循环，还是在访问临界资源，都是占用着CPU的，也就是处于运行态；
  2. 就绪态：若是在执行过程中由于并发所需要（如时间片到了），被其他进程占用了CPU，就变成了就绪态；

但是不会处于阻塞态，因为若是在等待临界资源，则会一直处于while (TSL(&lock));中，而且不会主动放弃CPU变成阻塞态（阻塞是一个主动的过程）。故不存在阻塞态的进城来给退出临界区的进程唤醒。

等待进入临界区的进程不会主动放弃CPU，故上述代码不满足“让权等待”的同步准则。因为会一直停留在执行while(TSL(&lock))的循环中，该语句应在开中断下进行，否则一直处于该循环且不被其他进程中断可能会导致系统终止。

操作系统的发展

手工发展阶段（无操作系统）：
所有工作都要人干预，用户独占全机。
特点：用户独占全机、CPU等待手工操作；
缺点：人机矛盾及 CPU 和 I/O 设备之间速度不匹配的矛盾，因此发展出了批处理系统。

批处理阶段（开始出现操作系统）：

  1. 单道批处理：系统对作业的处理是成批进行的，但内存中始终保持一道作业。
    特点：单道性、自动性、顺序性。
    缺点：每次主机内存中仅存放一道作业，每当它在运行时发出I/O请求后，高速的 CPU 便处于等待低速的 I/O 完成的状态。
    为了进一步提高资源的利用率和系统的吞吐量，引入了多道程序技术。
  2. 多道批处理：多道程序设计技术允许多个程序同时进入内存并允许它们在 CPU 中交替地运行。
    特点：多道、宏观上并行、微观上串行。
    优点：资源利用率高，多道程序共享计算机资源，从而使各种资源得到充分利用；系统吞吐量大， CPU 和其他资源保持“忙碌”状态。 缺点：用户响应的时间较长；不提供人机交互能力，用户既不能了解自己的程序的运行情况，又不能控制计算机。 因此发展出了分时操作系统。

分时操作系统：
分时操作系统是指多个用户通过终端同时共享一台主机，这些终端连接在主机上，用户可以同时（同时性）与主机进行交互（交互性）操作而互不干扰（独立性）。分时系统采用时间片轮转方式使一台计算机同时为多个终端服务，使用户能够对系统的及时响应感到满意（及时性）。分时系统也是支持多道程序设计的系统，但它不同于多道批处理系统。多道批处理是实现作业自动控制而无须人工干预的系统，而分时系统是实现人机交互的系统。
特点：同时性、交互性、独立性、及时性。
优点：较好地解决了人机交互问题。
缺点：在一些应用场合，需要系统能对外部的信息在规定的时间（比时间片的时间还短）内做出处理（比如飞机订票系统或导弹制导系统），因此，实时操作系统应运而生。

描述特点优点缺点
手工操作阶段所有工作都要人干预用户独占全机、CPU等待手工操作；不会出现因资源己被其他用户占用而等待的情况资源利用率低，人机矛盾及 CPU 和 I/O 设备之间速度不匹配的矛盾，因此发展出了批处理系统。
单道批处理系统对作业的处理是成批进行的，但内存中始终保持一道作业。单道性、自动性、顺序性。（开始出现操作系统）每次主机内存中仅存放一道作业，每当它在运行时发出I/O请求后，高速的 CPU 便处于等待低速的 I/O 完成的状态。 为了进一步提高资源的利用率和系统的吞吐量，引入了多道程序技术。
多道批处理多道程序设计技术允许多个程序同时进入内存并允许它们在 CPU 中交替地运行。多道性、宏观上并行、微观上串行。资源利用率高，多道程序共享计算机资源，从而使各种资源得到充分利用；系统吞吐量大， CPU 和其他资源保持“忙碌”状态。用户响应的时间较长；不提供人机交互能力，用户既不能了解自己的程序的运行情况，又不能控制计算机。 因此发展出了分时操作系统。
分时操作系统用户可以同时（同时性）与主机进行交互（交互性）操作而互不干扰（独立性）。分时系统采用时间片轮转方式使一台计算机同时为多个终端服务，使用户能够对系统的及时响应感到满意（及时性）。同时性、交互性、独立性、及时性。较好地解决了人机交互问题。在一些应用场合，需要系统能对外部的信息在规定的时间（比时间片的时间还短）内做出处理（比如飞机订票系统或导弹制导系统），因此，实时操作系统应运而生。
实时操作系统为了能在某个时间限制内完成某些紧急任务而不需要时间片排队，诞生了实时操作系统。资源利用率不是其主要追求目标。及时性、可靠性

image-20231010110654340

管程

管程是由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。管程不仅能实现进程间的互斥，而且能实现进程间的同步。

管程由 4 部分组成：

  1. 管程的名称；
  2. 局部于管程内部的共享数据结构说明；
  3. 对该数据结构进行操作的一组过程（或函数）；
  4. 对局部于管程内部的共享数据设置初始值的语句。

管程具有特性：

  1. 局部于管程的数据只能被局部于管程内的过程所访问；
  2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
  3. 每次仅允许一个进程在管程内执行某个内部过程（实现互斥）；
  4. 互斥访问数据是由编译器实现的，程序员不用关心。

例如，若x是管程内的条件变量，则当进程执行x.wait()时所做的工作是阻塞该进程，并将之插入x的阻塞队列中。

“条件变量”是管程内部说明和使用的一种特殊变量，其作用类似于信号量机制中的“信号量”，都是用于实现进程同步的。需要注意的是，在同一时刻，管程中只能有一个进程在执行。如果进程 A 执行了x.wait()操作，那么该进程会阻塞，并挂到条件变量 x 对应的阻塞队列上。这样，管程的使用权被释放，就可以有另一个进程进入管程。如果进程 B 执行了x.signal()操作，那么会唤醒 x 对应的阻塞队列队头进程。在 Pascal 语言的管程中，规定只有一个进程要离开管程时才能调用signal()操作。

四次挥手各自的阶段

四次挥手

17年

顺序存储、链式存储对不同排序方式的影响

由顺序存储变成链式存储后，效率不会降低的有：插入排序、（简单）选择排序、冒泡排序，因为顺序存储下，时间复杂度就是$O(n^2)$，链式存储不会改变其复杂度；

效率会降低的有：希尔排序、堆排序、快速排序，因为是利用了顺序存储的随机访问特性。

指令级并行

  1. 超流水线：通过增加流水线级数来使更多的指令同时在流水线中重叠执行。超流水线并没有改变CPI的值，CPI还是1，但是，因为理想情况下流水线的加速比与流水段的数目成正比，流水段越多，时钟周期越短，主频越高，指令吞吐率越高，所以超流水线的性能比普通流水线好。然而，流水线级数越多，用于流水段寄存器的开销就越大，因而流水线级数是有限制的，不可能无限增加。

在《计算机组成与设计：软件/硬件接口》书中，有一个形象的解释：

任何一个经常光顾洗衣店的人都会不自觉地使用流水线技术。非流水线方式的洗衣过程包括如下几个步骤：

  1. 把一批脏衣服放入洗衣机里清洗
  2. 洗衣机洗完后，把衣服取出并放入烘干机中。
  3. 烘干衣服后，将衣服从烘干机中取出，然后放在桌子上叠起来。
  4. 叠好衣服后，请你的室友帮忙把桌子上的衣服收好。

当你的室友把这批干净衣服从桌子上拿走后，再开始洗下一批脏衣服。采用流水线的方法将节省大量的时间，如图 4-25 所示。当把第一批脏衣服从洗衣机里取出放入烘干机之后，就可以把第二批脏衣服放入洗衣机里进行清洗了。当第一批衣服被烘干之后，就可以将它们叠起来，同时把洗净的下一批湿衣服放入烘干机中，同时再将下一批脏衣服放入洗衣机里清洗。接着让你的室友把第一批衣服从桌子上收好，而你开始叠第二批衣服，这时烘干机中放的是第三批衣服，同时可以把第四批脏衣服放入洗衣机清洗了。这样，所有的洗衣步骤（流水线的步骤）都在同时操作。只要在每一个操作步骤中都有独立的工作单元时，我们就可以采用流水线的方式来快速完成任务了。

image-20231011150257327

有两种方法可以增加潜在的指令级并行程度：

  1. 第一种是增加流水线的深度以重叠更多的指令。还是用洗衣店的例子来说明，假设洗衣机周期比其他机器的周期要长，我们可以把洗衣机划分成三个机器，分别完成原洗衣机洗、漂、甩三个功能。这样我们就将四级流水线变成了六级流水线。为了达到完全的加速效果，我们需要重新平衡其他步骤使得它们的长度相同，在处理器和洗衣店中都是这样。因为更多的操作被重叠，有更多的并行性被挖掘出来。
    通过增加流水线级数来使更多的指令同时在流水线中重叠执行。超流水线并没有改变CPI的值，CPI还是1，但是，因为理想情况下流水线的加速比与流水段的数目成正比，流水段越多，时钟周期越短，主频越高，指令吞吐率越高，所以超流水线的性能比普通流水线好。然而，流水线级数越多，用于流水段寄存器的开销就越大，因而流水线级数是有限制的，不可能无限增加。

  2. 另一种方法是复制计算机内部部件的数量，使得每个流水级可以启动多条指令。这种技术一般被称为多发射。一个多发射的洗衣店会把原有的一台洗衣机和烘干机替换为三台洗衣机和三台烘干机。还需要雇用更多的洗衣工来折叠和存储三倍于原来的衣服。这种方法的缺点是需要额外的工作让所有机器同时运转并将负载传到下个流水级。
    实现多发射流水线必须完成以下两个任务：指令打包和冒险处理。指令打包任务就是将能够并行处理的多条指令同时发送到发射槽中，因此处理器必须知道每个周期能发射几条指令，哪些指令可以同时发射。这通过推测技术来完成，可以由编译器或处理器通过猜测指令执行结果来调整指令执行顺序。根据推测任务主要由编译器静态完成还是由处理器动态执行，可将多发射技术分为两类：静态多发射和动态多发射：

    • 静态多发射主要通过编译器静态推测来辅助完成“指令打包”和“冒险处理”。指令打包的结果可看成将同时发射的多条指令合并到一个长指令中。通常将一个时钟周期内发射的多个指令看成一条多个操作的长指令，称为一个“发射包“。所以，静态多发射指令最初被称为“超长指令字”。

    • 动态多发射由处理器硬件动态进行流水线调度来完成“指令打包“和“冒险处理”，能在一个时钟周期内执行一条以上指令。采用动态多发射流水线技术的处理器称为超标量处理器。在简单的超标量处理器中，指令按顺序发射，每个周期由处理器决定是发射一条或多条指令。能结合动态调度技术提高指令执行并行性。

数据通路包含哪些

机器指令的执行是在数据通路中完成的，通常将指令执行过程中数据所经过的路径（包括路径上的部件）称为数据通路。程序计数器、ALU、通用寄存器、状态寄存器、cache、MMU（主存管理单元）、浮点运算逻辑、异常和中断处理逻辑等都是指令执行过程中数据流经的部件，都属于数据通路的一部分。通常把数据通路中专门进行数据运算的部件称为执行部件(execution unit) 或功能部件(function unit)。数据通路由控制部件进行控制。控制部件根据每条指令功能的不同生成对数据通路的控制信号，因此数据通路不包括控制部件。

指令执行所用到的元件有两类：组合逻辑元件（也称操作元件）和时序逻辑元件（也称状态元件或存储元件）。故也可以说数据通路由组合逻辑电路和时序逻辑电路组合而成。

组合逻辑元件的输出只取决于当前的输人。若输入一样，其输出也一样。组合电路的定时不受时钟信号的控制，所有输入信号到达后，经过一定的逻辑门延迟，输出端的值被改变，并一直保持其值不变，直到输入信号改变。数据通路中常用的组合逻辑元件有多路选择器（MUX） 、加法器（Adder） 、算术逻辑部件（ALU）、译码器（Decoder）等。

时序逻辑元件具有存储功能，输人状态在时钟控制下被写到电路中，并保持电路的输出值不变，直到下一个时钟到达。输人端状态由时钟决定何时被写入，输出端状态随时可以读出。数据通路中的寄存器是一种典型的状态存储元件，根据功能和实现方式的不同，有各种不同类型的寄存器。

磁盘初始化

  1. 低级格式化（物理格式化）：一个新的磁盘是一个空白版，必须分成扇区以便磁盘控制器能读和写，这个过程称为低级格式化（或物理格式化）。低级格式化为磁盘的每个扇区采用特别的数据结构，包括校验码。
  2. 磁盘分区：磁盘分为由一个或多个柱面组成的分区，每个分区可以作为一个独立的磁盘。
  3. 逻辑格式化（创建文件系统）：在这一步，操作系统将初始的文件系统数据结构存储到磁盘上，包括创建文件系统的根目录，对空闲磁盘块进行管理的数据结构进行初始化（如位示图、空闲分区表、i结点区）

划分扇区不等于磁盘分区。

MAC帧的地址

image-20231011155546332

image-20231011155635959

image-20231011155650449

“接化发”

18年

行地址位数和列地址位数的大小关系

在采用引脚复用时，为了提高DRAM的性价比，通常设置行地址位数$r$和列地址位数$c$满足$r\leq c$且$|r-c|$最小。

可以提高文件访问速度的措施

  1. 提前读：提前读是指读当前盘块时，将下个可能要访问的盘块数据读入缓冲区，以便需要时直接从缓冲区中读取，提高了文件的访问速度；
  2. 为文件分配连续的簇；
  3. 延迟写：延迟写是先将写数据写入缓冲区，并置上“延迟写”标志，以备不久之后、问，当缓冲区需要再次被分配出去时才将缓冲区数据写入磁盘，减少了访问磁盘的次数，高了文件的访问速度；
  4. 采用磁盘高速缓存；

分用复用

image-20231012191429758

  1. 发送方的某些应用进程所发送的不同的应用报文，在传输层使用UDP协议进行封装，称为UDP复用，TCP复用概念类似。传输层发送端使用源端口号来区分不同的应用进程；
  2. 不管是UDP封装的UDP用户数据报还是TCP协议封装的TCP报文段，在网络层都需要使用IP协议来封装成IP数据报，称为IP复用，IP数据报首部的协议字段的值用来表明封装的是何种协议数据单元，如取值为6表示封装的是TCP报文段，取值为17表示封装的是UDP用户数据报；
  3. 接收方网络层收到IP数据报后进行IP分用，根据IP首部的协议字段来向上交付给传输层对应的协议。
  4. 接收方传输层根据UDP数据报或TCP报文段首部的目的端口号，向上交付给应用层的相应应用进程。

19年

森林的遍历、多叉树的遍历

树森林二叉树
先根遍历先序遍历先序遍历
后根遍历中序遍历中序遍历

森林的先序遍历也称为先根遍历，中序遍历也称为中根遍历、后根遍历。

结合了cache和虚拟存储器的CPU访存过程

CPU访存导图1

cache缺失由硬件完成；缺页处理由软件完成，操作系统通过缺页异常处理程序来实现；TLB缺失既可以由硬件来处理也可以软件来处理。用软件处理时，OS通过专门的TLB缺失异常处理程序来实现。

DMA的一些细节

DMA的数据传送分为预处理、数据传送和后处理3个阶段。

  1. DMA预处理阶段需要CPU参与，由CPU完成必要的准备工作，由设备驱动程序设置传送参数**。每类设备都配置一个设备驱动程序，设备驱动程序向上层用户程序提供一组标准接口，负责实现对设备发出各种具体操作指令，**用户程序不能直接和 DMA 打交道。
  2. 在DMA传送过程中，DMA控制器直接控制总线传输。每次将一个数据块送到主存中后，在下次数据传送前，DMA控制器会再次请求总线使用权（即DMA请求），该请求的响应无需CPU干预；
  3. 在所有所需的块传送完成后，DMA传送结束，进入后处理阶段，DMA控制器发出DMA中断，CPU参与中断的处理。

各种动态分区管理方式特点

  1. 首次适应（ First Fit ）算法。空闲分区以地址递增的次序链接。分配内存时，从链首开始顺序查找，找到大小能满足要求的第一个空闲分区分配给作业。
  2. 邻近适应（ Next Fit) 算法。又称循环首次适应算法，由首次适应算法演变而成。不同之处是，分配内存时从上次查找结束的位置开始继续查找。
  3. 最佳适应（ Best Fit ）算法。空闲分区按容量递增的次序形成空闲分区链，找到第一个能满足要求且最小的空闲分区分配给作业，避免“大材小用”。
  4. 最坏适应 (Worst Fit ）算法。空闲分区以容量递减的次序链接，找到第一个能满足要求的，即最大的分区，从中分割一部分存储空间给作业。

首次适应算法最简单，通常也是最好和最快的。不过，首次适应算法会使得内存的低地址部分出现很多小的空闲分区，而每次分配查找时都要经过这些分区，因此增加了开销。

邻近适应算法试图解决这个问题。但它常常导致在内存空间的尾部（因为在一遍扫描中，内存前面部分使用后再释放时，不会参与分配）分裂成小碎片。通常比首次适应算法要差。

最佳适应算法虽然称为“最佳”，但是性能通常很差，因为每次最佳的分配会留下很小的难以利用的内存块，会产生最多的外部碎片。

最坏适应算法与最佳适应算法相反，它选择最大的可用块，这看起来最不容易产生碎片，但是却把最大的连续内存划分开，会很快导致没有可用的大内存块，因此性能也非常差。

物理层介质总结

同轴电缆：coaxial cable

双绞线：Twisted pair（T）

绞合的作用：

  1. 减少相邻导线间的电磁干扰
  2. 抵御部分来自外界的电磁干扰

光纤：Optical fiber（F）

光纤的优点：

  1. 通信容量非常大
  2. 抗雷电和电磁千扰
  3. 性能好，传输损耗小，中继距离长
  4. 无串音，干扰保密性好
  5. 体积小，重量轻

光线的缺点：

  1. 切割光纤需要较贵的专用设备
  2. 目前光电接口还比较昂贵

GBN确认号、TCP确认号

在GBN中，若本次A发送给B的帧序号为n，B发送给A的确认序号为n，说明已经收到了前n个帧；

在TCP中，若本次B发送的确认报文段中的确认号为n+1，说明已经收到了A发送给B的前n个报文段，期待收到第n+1个报文段；