408

16年 单周期数据通路 单周期数据通路是一种简单的数据通路设计，每个时钟周期执行一条完整的指令，即每条指令的CPI为1，要考虑比较慢的指令，所以处理器的时钟频率较低。 这意味着每条指令执行过程中任何数据通路单元都只能被用一次，如果需要使用多次则必须将该数据通路单元复制多份。 控制信号是CU根据指令操作码发出的信号，对于单周期处理器来说，每条指令的执行只有一个时钟周期，而在一个时钟周期内控制信号并不会变化。 单周期数据通路必须有独立的指令存储器和数据存储器，因为处理器在一个周期内只能操作每个部件一次，而在一个周期内不可能对一个单端口存储器进行两次存取。且无法使用单总线数据通路，因为单总线数据通路将所有寄存器的输入出端都连接在一条公共通路上，一个时钟内只允许一次操作，无法完成指令的所有操作。 TSL指令实现互斥 1 2 3 4 5 6 do { while (TSL(&lock)); critical section; lock = FALSE; ...... } while (TRUE); 退出临界区的进程负责唤醒就绪态进程？ 因为在TSL方法下，一个进程只有两种状态： 运行态：用户处于了do{ }中，那么不管是是在其中的while (TSL(&lock))不断地循环，还是在访问临界资源，都是占用着CPU的，也就是处于运行态； 就绪态：若是在执行过程中由于并发所需要（如时间片到了），被其他进程占用了CPU，就变成了就绪态； 但是不会处于阻塞态，因为若是在等待临界资源，则会一直处于while (TSL(&lock));中，而且不会主动放弃CPU变成阻塞态（阻塞是一个主动的过程）。故不存在阻塞态的进城来给退出临界区的进程唤醒。 等待进入临界区的进程不会主动放弃CPU，故上述代码不满足“让权等待”的同步准则。因为会一直停留在执行while(TSL(&lock))的循环中，该语句应在开中断下进行，否则一直处于该循环且不被其他进程中断可能会导致系统终止。 操作系统的发展 手工发展阶段（无操作系统）： 所有工作都要人干预，用户独占全机。 特点：用户独占全机、CPU等待手工操作； 缺点：人机矛盾及 CPU 和 I/O 设备之间速度不匹配的矛盾，因此发展出了批处理系统。 批处理阶段（开始出现操作系统）： 单道批处理：系统对作业的处理是成批进行的，但内存中始终保持一道作业。 特点：单道性、自动性、顺序性。 缺点：每次主机内存中仅存放一道作业，每当它在运行时发出I/O请求后，高速的 CPU 便处于等待低速的 I/O 完成的状态。 为了进一步提高资源的利用率和系统的吞吐量，引入了多道程序技术。 多道批处理：多道程序设计技术允许多个程序同时进入内存并允许它们在 CPU 中交替地运行。 特点：多道、宏观上并行、微观上串行。 优点：资源利用率高，多道程序共享计算机资源，从而使各种资源得到充分利用；系统吞吐量大， CPU 和其他资源保持“忙碌”状态。 缺点：用户响应的时间较长；不提供人机交互能力，用户既不能了解自己的程序的运行情况，又不能控制计算机。 因此发展出了分时操作系统。 分时操作系统： 分时操作系统是指多个用户通过终端同时共享一台主机，这些终端连接在主机上，用户可以同时（同时性）与主机进行交互（交互性）操作而互不干扰（独立性）。分时系统采用时间片轮转方式使一台计算机同时为多个终端服务，使用户能够对系统的及时响应感到满意（及时性）。分时系统也是支持多道程序设计的系统，但它不同于多道批处理系统。多道批处理是实现作业自动控制而无须人工干预的系统，而分时系统是实现人机交互的系统。 特点：同时性、交互性、独立性、及时性。 优点：较好地解决了人机交互问题。 缺点：在一些应用场合，需要系统能对外部的信息在规定的时间（比时间片的时间还短）内做出处理（比如飞机订票系统或导弹制导系统），因此，实时操作系统应运而生。 描述 特点 优点 缺点 手工操作阶段 所有工作都要人干预 用户独占全机、CPU等待手工操作； 不会出现因资源己被其他用户占用而等待的情况 资源利用率低，人机矛盾及 CPU 和 I/O 设备之间速度不匹配的矛盾，因此发展出了批处理系统。 单道批处理 系统对作业的处理是成批进行的，但内存中始终保持一道作业。 单道性、自动性、顺序性。 （开始出现操作系统） 每次主机内存中仅存放一道作业，每当它在运行时发出I/O请求后，高速的 CPU 便处于等待低速的 I/O 完成的状态。 为了进一步提高资源的利用率和系统的吞吐量，引入了多道程序技术。 多道批处理 多道程序设计技术允许多个程序同时进入内存并允许它们在 CPU 中交替地运行。 多道性、宏观上并行、微观上串行。 资源利用率高，多道程序共享计算机资源，从而使各种资源得到充分利用；系统吞吐量大， CPU 和其他资源保持“忙碌”状态。 用户响应的时间较长；不提供人机交互能力，用户既不能了解自己的程序的运行情况，又不能控制计算机。 因此发展出了分时操作系统。 分时操作系统 用户可以同时（同时性）与主机进行交互（交互性）操作而互不干扰（独立性）。分时系统采用时间片轮转方式使一台计算机同时为多个终端服务，使用户能够对系统的及时响应感到满意（及时性）。 同时性、交互性、独立性、及时性。 较好地解决了人机交互问题。 在一些应用场合，需要系统能对外部的信息在规定的时间（比时间片的时间还短）内做出处理（比如飞机订票系统或导弹制导系统），因此，实时操作系统应运而生。 实时操作系统 为了能在某个时间限制内完成某些紧急任务而不需要时间片排队，诞生了实时操作系统。资源利用率不是其主要追求目标。 及时性、可靠性 管程 管程是由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。管程不仅能实现进程间的互斥，而且能实现进程间的同步。...

10年 平衡二叉树的调整 LL调整 RR调整 RL调整 例如（原谅我图画的难看😂）： LR调整 二分查找的次数（成功失败）、折半查找判定树与二叉搜索树的关系 平衡二叉树是一种特殊的二叉查找树，它要求任何节点的两棵子树的高度差不超过1（同一棵树的不同节点的子树高度差可以为1、0、-1）。平衡二叉树通过在插入和删除节点时做旋转来维持树的平衡。 折半查找判定树是一种特殊的平衡二叉树，它要求更加严格。同一棵树节点的左子树和右子树的差不能同时存在1和-1（即为统一向上取整或统一向下取整）。查找时，根据比较的结果折半排除一边的树。折半查找判定树中，只有最下面一层才可以不满。 根据完全二叉树的高度计算公式，元素个数为n时，树高 $h=\lceil log_2(n+1)\rceil$ 或 $h=\lfloor log_2(n)\rfloor+1$ 。在折半查找中， 查找成功的最小比较次数为1，最大比较次数为$h$； 查找失败的最小比较次数为：若$n=2^h-1$，则为$h$，否则为$h-1$，最大比较次数：$h$。 数据类型转换造成的精度丢失等问题 将高精度数转换为低精度数可能会引起： 精度丢失：高精度数通常能够表示更大范围和更高精度的数字，但当将其转换为低精度数时，可能会导致小数部分被截断或丢失，从而引起精度丧失。 溢出：如果高精度数的值超出了低精度数所能表示的范围，会导致溢出。 将整型数转换为浮点数一般不会出现问题，但特殊情况下会导致精度丢失，对于非常大或非常小的整数，可能无法精确表示。如int类型数据二进制表示有32位，但是对于float类型，在IEEE 754格式下，尾数部分只有23位，可能无法完全表示某一个int类型数，造成精度的丢失。 单精度与双精度浮点数的运算也有可能会有一些问题，例如10年真题$T_{14}$，$f=1.5678e3,d=1.5e100$，进行$(d+f)-d$运算，在$d+f$时，需要先进行对阶（小阶向大阶对齐），由于格式中的尾数限制，对阶后，$f$的尾数被舍去而变成了0，故$d+f$仍然为$d$，再减去$d$结果为0，而不是$f$。 字扩展、位扩展与相关的芯片最低地址问题 位扩展 位扩展是指用若干片位数较少的存储器芯片构成给定字长的存储器，容量改变，位数改变，地址单元个数不变。 在袁春风老师的《计算机系统基础》中的一个例子如下： 注意到8个$16M\times8bit$的芯片扩展构成一个128M内存条。在进行扩展之前，对于单个芯片，地址位数为24bit。即地址单元个数为$16M=2^{24}$ 。每个地址单元存储8bit。 在进行扩展之后，$128M=2^{27}$，而行列地址位数加起来一共$24bit$，$2^{24}=16M$，则说明此次扩展为位扩展。一个地址单元中的数据位数增加，但是总的地址单元个数并未改变。 12位行地址$i$和12位列地址$j$分别送到DRAM芯片内部的行地址译码器和列地址译码器，选择行列地址交叉点$(i,j)$的8位数据同时进行读写，8个芯片就可以同时读取64bit，组合成总线所需要的64位传输宽度，再通过存储器总线进行传输。 字扩展 字扩展，容量改变，地址单元个数改变，即地址位数会改变，位数不会改变。 另外，对于某一存储器，由多个DRAM经过字扩展而成，那么对于单个DRAM芯片来说，其行地址RAS位数、列地址CAS位数也不会变，但是整体存储器的总地址位数会变，会增加片选信号位数。 此时，对于一个主存地址，可以理解为芯片序号+芯片内的位置 。 也就是说，无论是位扩展还是字扩展，对于单一的DRAM芯片，其行列地址位数均不含会改变。（14年T15） 引起进程状态改变的一些典型事件 进程状态可以在以下情况下发生改变： 创建新进程：当操作系统启动一个新的程序时，会创建一个新的进程，并将其状态设置为就绪状态。 进程等待：当一个进程等待某些事件发生，例如等待用户输入、等待某个文件就绪等，它的状态会从运行状态变为阻塞状态。 时间片用完：如果一个进程在分配给它的时间片用完之后，调度器会将其状态从运行状态变为就绪状态，降低其进程优先级，然后选择下一个要执行的进程。 I/O操作完成：当一个进程等待的I/O操作完成后，它的状态会从阻塞状态变为就绪状态。 进程终止：当一个进程完成了它的任务，或者由于某种原因需要被终止，它的状态会从运行状态变为终止状态。 进程被阻塞的资源可用：当一个进程等待的资源（如锁或信号量）变为可用时，它的状态会从阻塞状态变为就绪状态。设备分配是在一个已经存在的进程中进行的，不会导致创建新进程。 进程被唤醒：在多任务环境中，一个进程可能会被另一个进程唤醒，使得它从阻塞状态变为就绪状态。 进程被挂起或恢复：操作系统可以将一个进程从内存中挂起（暂时移出内存）或者从挂起状态恢复（重新加载到内存中）。 父进程等待子进程：当一个父进程等待其子进程结束时，它的状态可能会从运行状态变为阻塞状态。 发生错误或异常：当一个进程遇到错误或异常情况时，它的状态可能会从运行状态变为终止状态或者阻塞状态（如果它在等待某些事件发生时发生了错误）。 IO系统的分层结构 碰撞域、广播域 冲突域：在同一个冲突域中，每一个结点都能收到所有其他结点发送的帧。简单地说，冲突域为同一时间内只能有一台设备发送信息的范围。 广播域：网络中能接收任意设备发出的广播帧的所有设备的集合。即，如果站点发出一个广播信号，所有能接收到这个信号的设备范围被称为一个广播域。 通常一个网段为一个冲突域，一个局域网为一个广播域。 磁盘的调度策略 磁盘调度算法是操作系统中用于管理磁盘上的I/O请求的一种策略。以下是一些常见的磁盘调度算法： 先来先服务（FCFS）：最简单的磁盘调度算法，按照请求的到达顺序依次执行。但可能会出现“早来的请求等待时间长”的问题。 最短寻道时间优先（SSTF）：选择当前磁头位置最近的请求进行服务，以最小化寻道时间。但可能会导致某些请求长时间等待。 SCAN算法：扫描算法，也称为电梯算法，类似于电梯的运行方式，磁头按一个方向移动，直到最后一个磁道后再改变方向。 C-SCAN算法：循环扫描算法，磁头按同一个方向移动，直到到达最后一个磁道后，立即直接返回到磁道0处，再继续扫描。 LOOK 算法：类似于扫描算法，但在到达最远的请求后不会立即返回，而是根据当前请求的方向决定下一个服务的磁道。在朝一个给定方向移动前查看是否有请求。 C-LOOK 算法：类似于 C-SCAN 算法，但在到达最远的请求后不会立即返回，而是直接返回到最远端的有请求的磁道。 注意，在做题时，若无特别说明，也可以默认SCAN算法和C-SCAN算法为LOOK和C-LOOK调度。...