Sprooc

第13讲-总线 总线概述 类型 芯片内部总线：连接芯片内部的各个部分 例：CPU 中连接寄存器、ALU 等部分 系统总线：连接CPU 、存储器、IO 控制器和其他功能设备 通信总线：连接主机和I/O 设备，或连接不同的计算机系统 总线结构 数据线：在系统组件之间传输数据 数据线的数量决定了一次可以传输的数据的大小 地址线：在数据线和地址I/O 端口上指定数据的来源和去向 地址线的数量决定了寻址空间的大小 控制线：控制对数据线和地址线的存取和使用 时钟（clock）：用于总线同步操作 总线请求（bus request）：表示模块需要获得对总线的控制 总线允许（bus grant）：发出请求的设备已经被允许控制总线 中断请求（interrupt request）：表示某个中断正在悬而未决 中断响应（interrupt ACK）：未决的终端请求被响应 存储器读（memory read）：从存储器读数据到总线 存储器写（memory write）：将数据从总线写入存储器 I/O读（I/O read）：从I/O 端口读数据到总线 I/O写（I/O write）：将数据从总线写 ...

第12讲-虚拟存储器 操作系统的出现 第一台计算机诞生时，采用手工操作的方式 一个用户独占全机：不会出现因资源已被其他用户占用而等待的现象，但资源的利用率低 CPU等待手工操作：CPU 的利用不充分 批处理系统：加载在计算机上的一个系统软件，在它的控制下，计算机能够自动地、成批地处理一个或多个用户的作业（包括程序、数据和命令） 联机批处理系统，脱机批处理系统 操作系统：一种控制应用程序运行和在计算机用户与计算机硬件之间提供接口的程序 目标：使计算机使用起来更方便；允许计算机系统的资源以有效的方式使用 存储器管理 早期计算机的主存中仅包含系统软件和一个用户程序 单道程序设计 现在计算机的主存中包含操作系统和若干个用户程序 当所有任务都需要等待I/O 时，为了避免处理器处于空闲状态，需要尽可能让更多的任务进入主存 多道程序设计：让处理器一次处理多个任务，提高处理器的利用率 存储器管理 在多道程序系统中，主存需要进一步划分给多个任务，划分的任务由操作系统动态执行 本门课不区分“进程”和“任务”这个更抽象的概念 交换技术 如何将更多更大的任务装入主存 增大主存容量 使用 ...

第11讲-冗余磁盘阵列 RAID简介 冗余磁盘阵列/独立磁盘冗余阵列：Redundant Arrays of Independent Disks (RAID) 基本思想 将多个独立操作的磁盘按某种方式组织成磁盘阵列，以增加容量 将数据存储在多个盘体上，通过这些盘并行工作来提高数据传输率 采用数据冗余来进行错误恢复以提高系统可靠性 特性 由一组物理磁盘驱动器组成，被视为单个逻辑驱动器。 数据是分布在多个物理磁盘上，分布方案称为条带。 冗余磁盘容量用于存储奇偶校验信息，保证磁盘万一损坏时能恢复数据。 RAID 0 数据以条带的形式在可用的磁盘上分布 不采用冗余来改善性能（不是RAID 家族中的真正成员） 用途 高数据传输率 高速响应I/O 请求：两个I/O 请求所需要的数据块可能在不同的磁盘上.如果条的大小相对较大，那么单个IO请求只涉及单个磁盘访问，则多个等待的IO请求就可以被并行处理，减少了每个请求的排队时间。 RAID 1 采用了数据条带，采用简单地备份所有数据的方法来实现冗余。 优点 高速响应I/O 请求：即便是同一个磁盘上的数据块，也可以由两组硬盘 ...

第10讲-数据校验码 差错（Error） 数据在计算机内部进行计算、存取和传送过程中，由于元器件故障或噪音干扰等原因，会出现差错 以存储为例 硬故障（hard failure）：永久性的物理故障，以至于受影响的存储单元不能可靠地存储数据，成为固定的“1”或“0”故障，或者在0 和1之间不稳定地跳变。由恶劣的环境、制造缺陷和旧损引起 软故障（soft error）：随机非破坏性事件，它改变了某个或某些存储单元的内容，但没有损坏机器。由电源问题或α 粒子引起 解决方案 从计算机硬件可靠性入手，在电路、电源、布线等方面采取必要的措施，提高计算机的抗干扰能力 采取数据检错和校正措施，自动发现并纠正错误 纠错（Error Correction） 基本思想：存储额外的信息以进行检错和校正 处理过程 数据输入：使用函数𝑓在𝑀位数据𝐷上生成𝐾位校验码𝐶 数据输出：使用函数𝑓在𝑀位数据𝐷 上生成新的𝐾位代码𝐶”，并与取出的𝐾位码𝐶 进行比较 没有检测到差错：使用数据𝐷 检测到差错且可以校正：校正数据𝐷 来生成数据𝐷”，并用数据𝐷 检测到差错但无法纠正：报告 ...

第9讲-外部存储器 外部存储器 特性：用于存储不经常使用的、数据量较大的信息；非易失。 类型： 磁盘存储器（magnetic disk disk） 光存储器（optical memory memory） 磁带（magnetic tape tape） U盘（USB flash disk disk） 固态硬盘（solid state disk disk，SSD） 磁盘 磁盘是由涂有可磁化材料的非磁性材料（基材）构成的圆形盘片 基材：铝、铝合金、玻璃 玻璃基材的优势（稳定可靠、为存储更多信息提供基础） 改善磁膜表面的均匀性，提高磁盘的可靠性 显著减少整体表面瑕疵，以帮助减少读写错误 能够支持（磁头）较低的飞行高度 更高的硬度，使磁盘转动时更加稳定 更强的抗冲击和抗损伤能力 类型：硬盘、软盘 磁头：对盘片进行读写操作的装置 磁盘存储器每个盘片表面有一个读写磁头，所有磁头通过机械方式固定在一起，同时移动。在任何时候，所有磁头都位于距磁盘中心等距离的磁道上。 磁头必须产生或感应足够大的电磁场，以便正确地读写 磁头越窄，电磁感应能力越弱，离盘片的距离就越近 更高的数据密度需要更窄的磁头 ...

第8讲-高速缓冲存储器 Cache的目的和基本思路 问题：CPU的速度比内存的速度快，且两者差距不断扩大—内存墙。 解决：CPU和内存之间增加Cache。 解决内存墙带来的CPU和主存协作问题 在使用主存（相对大而慢）之余，添加一块小而快的cache Cache位于CPU和主存之间，可以集成在CPU内部或作为主板上的一个模块 Cache中存放了主存中的部分信息的“副本” Cache的工作流程 检查（Check）：当CPU试图访问主存中的某个字时，首先检查这个字是否在cache中 检查后分两种情况处理： 命中（Hit）：如果在cache中，则把这个字传送给CPU 未命中（Miss）：如果不在cache中, 则将主存中包含这个字固定大小的块（block）读入cache中，然后再从cache传送该字给CPU 如何判断是命中还是未命中? Cache通过标记（tags）来标识其内容在主存中的对应位置 局部性原理 定义：处理器频繁访问主存中相同位置或者相邻存储位置的现象。 时间局部性：在相对较短的时间周期内，重复访问特定的信息（也就是访问相同存储位置的信息） 空间局部性：在 ...

第7讲-内部存储器 存储器（Memory） 定义：存储器（Memory）由一定数量的单元构成，每个单元可以被唯一标识，每个单元都 有存储一个数值的能力 地址：单元的唯一标识符（采用二进制） 地址空间：可唯一标识的单元总数 寻址能力：存储在每个单元中的信息的位数，即内存中能被单独识别并独立存放一个数据的最小内存空间— 大多数存储器是字节（8bit）寻址的，32位计算机的最大寻址空间为4GB 层次结构 主板内存储器：寄存器，Cache，主存。 主板外存储器：磁盘，CD-ROM，CD-RW，DVD-RW，DVD-RAM。 离线存储器：磁带 AND-OR锁存器参考文章：谁能告诉我AND-OR锁存器原理？ - 知乎 (zhihu.com)先解释OR锁OR锁： OR门B输入和输出连接。INIT为初始状态A=B=0；当A=1，B=0时，OUTPUT变为1同时将B变为1；此时，当A变回0，OUTPUT仍为1（被锁住）。 AND锁： AND门B输入和输出连接。 INIT为初始状态A=B=1； 当A=0，B=1时，OUTPUT变为0同时将B变为0； 此时，当A变回1，OUTPUT仍 ...

本周的算法学习主要是刷题+看书，没有学什么新算法，只零碎地学了一些小的知识点。 二分模版虽然以前二分写的不少，但从来没有一次写对过，看了lyd的书之后才知道有两种二分模版。 123456789101112// 模版一while(l < r) { int mid = (l + r) / 2; if(a[mid] >= x) r = mid; else l = mid + 1; // 避免进入l = mid的死循环}// 模版二while(l < r) { int mid = (l + r + 1) / 2; if(a[mid] <= x) l = mid; else r = mid - 1; // 避免进入 r = mid的死循环} 货仓选址问题数轴上有N家商店，坐标分别为A[1]~A[N]，选一个位置建货仓，令货仓到每家商店的距离之和最小。 货仓必须建在中位数处，证明不难，思考一下。 矩形面积问题复习了一下这几道题，很典型。 84. 柱状图中最大的矩形 - 力扣（LeetCod ...

数据的机器级表示1.将整数真值（十进制表示）转化成补码表示的二进制，默认长度32位。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748public static String intToBinary(String numStr) { int num = Integer.parseInt(numStr); if(num == Integer.MIN_VALUE) return "10000000000000000000000000000000"; boolean neg = false; if(num < 0) { num = -num; neg = true; } StringBuilder temp = new StringBuilder(); while(num > 0) { temp.insert ...

快速幂 12345678int pow(int a, int b, int m) { int ans = 1; for (; b; b >>= 1) { if (b & 1) ans = (LL)ans * a % m; a = (LL)a * a % m; } return ans;} 龟速乘 12345678910LL mul(LL a, LL b, LL p) { a %= p; b %= p; LL c = (double)a * b / p; LL x = a * b; LL y = c * p; LL ans = (LL)(x % p) - (LL)(y % p); if (ans < 0) ans += p; return ans;} 等比数列（公比为p，项数为e，以1为首项） 123456789int sum(int p, int e, int m) { if (e == 1) return 1; if (e % 2 == 0)
...