1. OS的概念、特性​

概念​

操作系统是计算机系统中的一个系统软件，是一些程序模块的集合。

特性​

1. 并发/并行
2. 共享：操作系统与多个用户程序共同使用计算机系统中资源，其中分为：
   • 互斥共享：资源不能同时使用。
   • 同时共享：资源可以同时使用。
3. 虚拟：一个物理实体映射为若干个对应逻辑实体（分时或分空间）。存储器中每个进程都有独立的虚拟地址空间（存代码、数据、堆栈）。
4. 随机：OS要对不可预测的事件进行响应处理。

2. OS的功能​

1. 资源分配​

• 静态分配策略：把进程所有需要的资源先都分配给它，但这可能导致资源浪费。
• 动态分配策略：进程什么时候需要资源就什么时候分配，如果该资源已被占用，进程会阻塞并进入相应的等待队列。

2. 资源管理​

• 进程/线程管理
• 存储管理
• 文件管理
• 设备管理
• 用户接口管理

3. OS的发展历史及分类​

1) 批处理操作系统​

工作方式​

1. 用户将作业（作业：由作业说明书、用户程序、数据组成，且通常为卡片形式，输入设备为卡片机）交给系统操作员。
2. 系统操作员将多个作业组成一批作业，输入到计算机系统中，形成一个自动转接的连续作业流。
3. 启动OS。
4. OS自动执行每个作业，用户无法干预。
5. 执行结果交给用户。

追求目标​

• 提高资源利用率，增加作业处理吞吐量。

总体过程​

• 从卡片机读入用户作业和编译链接程序，编译链接生成可执行程序，执行程序并输出执行结果。

问题​

• 慢速I/O设备与CPU处理速度差异过大，导致CPU在等待数据时空闲。

2) Spooling技术​

利用磁盘做缓冲，将输入、计算、输出分别组成独立的任务流，使I/O和计算并行（假脱机：磁盘在高效的计算机上）。

工作流程​

1. 用户作业输入磁盘输入。
2. 按照某种调度策略，选几个搭配得当的作业调入内存。
3. 作业运行结果输出到磁盘的输出。
4. 运行结果从输出井到打印机。

备注：输入输出只到输入或输出井，主机不用直接与慢速的I/O打交道，能提高效率和速度。

现代打印机仍然使用这种技术。

应用Spooling技术后：

3) 分时操作系统​

工作方式​

多个终端（只有I/O设备没有计算能力）连接到同一主机中，然后OS将CPU时间分成若干个片段，OS以时间片为单位，轮流为每个终端用户服务，每次服务使用掉一个时间片。

追求目标​

• 及时响应。
• 响应时间：指从终端发出命令到系统给予回答所经历的时间。

4) 实时操作系统​

指计算机能及时响应外部时间请求，在规定的严格时间内完成对该事件的处理。

追求目标​

• 对外部请求在严格时间范围内做出响应。

---

第二章 OS硬件环境

1. 管态与目态​

通常CPU执行两种不同性质的程序：一种是操作 系统内核程序；另一种是 用户自编程序或系统外层的应用程序。对操作系统而言，这两种程序的作用不同，前者是后者的管理者，因此“管理程序”要执行一些特权指令(不允许用户直接使用的指令，如I/O指令、置中断指令等），而“被管理程序”出于安全考虑不能执行这些指令。所以我们将机器分为两种状态，通过状态的切换来保护操作系统程序。

• 管态(核心态、系统态)：在此状态下，CPU可以执行指令系统的全集，是一种具有较高特权的执行状态，可以访问所有寄存器和存储区。另外OS内核通常是运行在系统态的，进程控制是由OS内核实现。
• 目态(用户态)：在此状态下，CPU只能执行非特权指令。可访问指定的寄存器和存储区，只具有较低的特权。一般的用户程序在此状态下执行。

2. 多级存储体系​

原因​

计算机采用多级存储，主要是基于 容量、速度、成本 这三个因素考虑的。

多级存储结构 从上到下，容量越来越大，速度越来越慢，成本越来越低；

同时这种多级存储的模式有利于计算机CPU发挥其性能，还解决了数据存储的问题；

因为外存虽然成本低，但是比较慢；它的运行频率、工作频率，数据的传送情况都是比较慢的；

寄存器虽然速度很快，但是成本高，容量小；

Cache​

Cache是现代计算机在CPU和主存之间设置的一个高速、小容量的缓冲存储器，填补了CPU和主存在速度上的巨大差距，可用用于提高整个计算机系统的性能。

Cache先被访问，如果不命中，内存后被访问

cache 映射​

◆ 直接映像 ➢ 某一主存块只能固定映射到某一缓冲块 ◆ 全相联映像 ➢ 某一主存块能映射到任一缓冲块 ◆ 组相联 ➢ 某一主存块只能映射到某一缓冲组中的任一块

靠近CPU的Cache要求高速，采用直接相联或路数较少的组相联；中间层次采用组相联；距离CPU最远的Cache采用全相联，对利用率强调越高。

cache 优化​

cache例题1

多级cache例题1

①强制性失效：当第一次访问一个块时，需要从下一级存储器中调入Cache，这种失效称为强制性失效。也称为冷启动失效或首次访问失效。强制性失效发生在对初始空Cache的访问中。 ②容量失效：由于Cache容量有限，使得程序执行所需的块不能全部调入Cache中，所以当某些块被替换后如果重新被访问就会发生失效。这种失效就称为容量失效。 ③冲突失效：在组相联或直接映像Cache中，多个块映像到同一组（个）块中，则会出现该组中的某一个块被别的块替换后又被重新访问的情况，这就发生了冲突失效。冲突失效也称为碰撞失效或干扰失效。

关于Cache失效的一些结论：

①Cache容量对失效的影响：强制性失效不受到Cache容量的影响，但是容量失效随着容量的增加而减少； ②相联度对失效的影响：强制性失效和容量失效不受相联度的影响，但是相联度越高冲突失效就越少； ③经验规则：大小为N的直接映像Cache的失效率约等于大小为N/2的2路组相联Cache的失效率。

虚拟存储​

虚拟存储器的分块​

虚存的分块方式：虚存的分块可以分为段式、页式和段页式三种。采用哪一种分块方式对操作系统的性能具有很大的影响。 ①页式分块：页式虚存把空间划分为大小相同的页面，其中每个存储单元的地址都是单一、固定长度的地址字，由页号和页内位移两部分组成。 ②段式分块：往往是按照程序的逻辑结构进行划分，段的长度可变。这种方式中地址一般用两个字表示：一个是段号，另一个是段内位移。 ③段页式分块：同时采用段式和页式，也就是将每个段划分为若干个页面。这种方式不仅保持了段作为逻辑单元的优点，又简化了替换操作的实现。

---

第三章 用户接口与作业管理

作业的概念，作业级接口与程序级接口​

1. 作业的概念​

作业就是用户一次请求计算机系统为用户完成任务所做工业的综合

2. 接口​

• **程序级接口：**系统为用户在程序一级提供有关服务而设置的，由一组系统调用命令组成
• 作业级接口: 系统为用户提供的各种命令接口，用户利用这些操作命令来组织和控制作业的执行或管理计算机系统

JCB；作业的状态及转换​

作业状态及转换​

一个作业在其生命周期内会经历多个状态，这些状态的变化反映了作业当前所处的阶段。常见的作业状态包括：

• 提交状态：当用户将作业提交给系统后，作业处于提交状态。此时，作业的信息正在进入外存的“作业收容井”中。
• 后备状态：作业已全部进入外存，等待被调度进入内存。在此状态下，系统为作业创建了作业控制块（JCB），记录了作业的各种属性和状态信息。
• 执行状态：作业被选中加载到内存中开始执行。这个阶段可能包括编译、链接、装入和实际运行等子阶段。一旦作业进入了执行状态，它就处于宏观上的运行中。
• 完成状态：作业已经执行完毕，所有资源已经被回收，作业结果可能已经输出。此时作业处于完成状态，等待最终的数据输出或删除。

作业控制块(JCB)​

作业控制块（JCB）是作业在系统中存在的唯一标志，它记录了与该作业有关的所有必要信息。JCB的内容通常包含以下方面：

• 作业标识：如作业号、用户名等。
• 作业类型：CPU繁忙型、I/O繁忙型、批量型、终端型等。
• 作业状态：反映作业当前的状态，如后备、执行、完成等。
• 资源需求：作业所需的内存大小、I/O设备类型和数量等。
• 优先级：根据作业的性质设定的优先级。
• 其他信息：如预计运行时间、实际运行时间、收费标准等。

JCB对于作业管理和调度至关重要，因为它是操作系统了解作业需求并据此进行决策的基础。每当作业的状态发生变化时，相应的JCB也会更新，以反映最新的作业状态。

作业调度算法：FCFS/SJF/HRN​

1. 先来先服务​

原理：按照作业到达系统的顺序进行调度，即最早到达的作业最先得到处理。

优点：实现简单，公平性好。 缺点：如果长作业位于队首，则短作业可能需要等待很长时间，导致平均周转时间较长。

例题： 假设有以下四个作业按如下时间提交给系统：

• 作业A：提交时刻10:00，运行时间2小时
• 作业B：提交时刻10:06，运行时间1小时
• 作业C：提交时刻10:15，运行时间0.25小时

使用FCFS算法计算它们的平均周转时间和平均带权周转时间。

解答：

• 作业A开始时间10:00，结束时间12:00，周转时间2小时，带权周转时间1
• 作业B开始时间12:00，结束时间13:00，周转时间2.9小时，带权周转时间2.9
• 作业C开始时间13:00，结束时间13:15，周转时间3小时，带权周转时间12

平均周转时间 = (2 + 2.9 + 3) / 3 ≈ 2.63 小时 平均带权周转时间 = (1 + 2.9 + 12) / 3 ≈ 5.30 小时

2. 短作业优先​

原理：选择估计运行时间最短的作业优先执行。

优点：可以减少平均等待时间，提高系统响应速度。 缺点：可能导致长作业长时间得不到执行，造成“饥饿”现象。

例题： 假设同样有上述三个作业，使用SJF算法计算它们的平均周转时间和平均带权周转时间。

解答：

• 作业A开始时间10:00，结束时间12:00，周转时间2小时，带权周转时间1
• 作业B开始时间12:15，结束时间13:15，周转时间3.1小时，带权周转时间3.1
• 作业A开始时间12:00，结束时间12:15，周转时间2小时，带权周转时间8

平均周转时间 = (2 + 3.1 + 2) / 3 小时 平均带权周转时间 = (1 + 3.1 + 8) / 3 小时

3. 高响应比优先​

原理：根据作业的响应比来决定调度顺序，响应比定义为 (等待时间 + 作业长度) / 作业长度。

优点：平衡了等待时间和作业长度，防止饥饿现象。 缺点：需要动态计算响应比，增加了系统开销。

例题： 假设有四个作业提交给系统，其信息如下：

• 作业D：提交时刻8:00，运行时间2小时
• 作业E：提交时刻8:30，运行时间0.5小时
• 作业F：提交时刻9:00，运行时间0.1小时
• 作业G：提交时刻9:30，运行时间0.2小时

使用HRRN算法计算它们的平均周转时间和平均带权周转时间。

解答：

• 作业D完成时间10:00
• 作业F完成时间10:06
• 作业E完成时间10:36
• 作业G完成时间10:46

作业D周转时间2小时，带权周转时间1 作业F周转时间0.1小时，带权周转时间1 作业E周转时间1.5小时，带权周转时间3 作业G周转时间1.2小时，带权周转时间6

平均周转时间 = (2 + 0.1 + 1.5 + 1.2) / 4 = 1.2 小时 平均带权周转时间 = (1 + 1 + 3 + 6) / 4 = 2.75 小时

系统调用（访管中断）​

访管指令是一条可以在用户态（又称目态）下执行的指令。在用户程序中，因要求操作系统提供服务而有意识地使用访管中断，从而产生一个中断事件（自愿中断），将操作系统转换为核心态，称为访管中断。访管中断由访管指令产生，程序员使用访管指令向操作系统请求服务。

---

第四章 进程管理

1. 程序的顺序执行的特点；多道程序并发执行的特点​

顺序执行时​

1.顺序性：严格的按照顺序执行

2.封闭性：程序运行时独占全机资源 资源状态只有本程序才能改变它，程序一旦开始执行，不受外界影响

3.可再现性：无论如何执行 都可缺获得相同的结果

并发执行时​

1.间断性：由于资源有限，并发执行的程序存在相互制约的关系

2.失去封闭性：并发执行的程序共享计算机资源，这些资源的状态由这些程序改变

3.不可再现性：并发执行的程序执行的顺序不同可能有不同的执行结果

3个点分别对立

1. 顺序性 -> 间断性, 程序执行相互制约
2. 封闭性 -> 失去封闭性, 资源状态随程序进行改变
3. 可再现性 -> 不可再现性, 每次执行都可能结果不同

2. 进程的状态及变迁​

状态变迁​

1. 运行态 → 等待态 当一个运行程序 因某件时间受阻 时，如申请资源被占用、启动数据传输未完成等，其状态会变迁； 详细点就是 请求外部传输：一个程序在运行时需要进行打印，提出外部请求使用打印机，然后从运行态变迁为等待态；

2. 等待态 → 就绪态 当所等待的事件发生时，如得到被申请资源、数据传输完成，其状态会由等待变为就绪；

3. 就绪态 → 运行态 当一个就绪程序获得CPU时，其状态就由就绪态变为运行态；

4. 运行态 → 就绪态 运行进程被剥夺处理器资源； 在分时操作系统中，该程序 用完了系统分配的时间片； 或者 出现高优先级别的其他进程；

5. 就绪态 → 等待态 不是全错，还是有可能的； 可能有，只是 现在的OS一般都没有这个变迁；

6. 等待态 → 运行态

   全错；这个变迁是绝对没有的；

3. 进程调度与时间片​

例题

4. 进程控制​

• 阻塞原语:

  • 进程的阻塞是要靠调用阻塞原语来实现。
  • 阻塞原语在进程期待某事件发生，但没有发生时(或所需资源尚不具备时)，被该进程调用来阻塞自己。(所以可以发现，阻塞常常是一种自我阻塞的过程，类似于人的欲望得不到满足，就降低要求)

• 唤醒原语:

  • 事件发生进程 和 被唤醒进程 之间是合作关系，唤醒原语既可被系统进程调用，也可被事件发生进程调用。(当然，进程不能够被自己唤醒，需要 “外界的激励” )

• 挂起原语与激活原语:

  • 挂起原语即可由进程自己也可由其他进程调用，但激活原语却只能由其他进程调用。

5. pv操作​

pv

6. 进程间通信​

• 管道(pipe)

  管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。

• 有名管道 (namedpipe)

  有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。

• 信号量(semaphore)

  信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

• 消息队列(messagequeue)

  消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

• 信号 (sinal)

  信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

• 共享内存(shared memory)

  共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。

• 套接字(socket)

  套接口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同设备及其间的进程通信。

7. 死锁​

产生条件​

1. 互斥条件 ： 指进程对所分配的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直到占有资源的进程用完后释放资源。

2. 占有且等待条件 ： 指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程阻塞，但它不会释放自己已经占有的资源。

3. 非抢占条件 ： 指进程已经获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

满足以上三个条件可能会产生死锁，但如果只有这三个条件，则不一定产生死锁。对死锁的产生，还需要第四个条件。

4. 循环等待条件 : 存在一个封闭的进程链，使得每个资源至少占有此链中下一个进程所需要的一个资源。

解决​

1. 破坏“互斥“条件 就是在系统里取消互斥。若资源不被一个进程独占使用，那么死锁是肯定不会发生的。但一般来说，第一个条件是不可能被禁止的，比如打印机等临界资源只能互斥使用。

2. 破坏“占有并等待”条件 就是在系统中不允许进程在已获得某种资源的情况下，申请其他资源，要求进程一次性地请求所有需要的资源，并且阻塞这个进程直到所有请求都同时满足。

   这样做有几个个缺陷，会很低效：

   一个进程可能被阻塞很长时间，等待满足其所有的资源请求，而实际上，只要有一部分资源，它就可以继续执行。 分配给一个进程的资源可能有相当长的一段时间处于不可用状态，并且再次期间，它们不能被其他进程使用。 一个进程可能事先并不会知道它所需要的所有资源。

3. 破坏“非抢占“条件 如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进程必须释放它最初占用的资源，如果有必要，可再次请求这些资源和另外的资源。 另一种方法是，要求两个进程不具有相同的优先级时才能有效预防死锁。即如果一个进程请求当前另外一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求它释放资源。

上述这两种方法只有在资源状态可以很容易地保存和恢复的情况下（如处理器），比较实用。

4. 破坏“循环等待“条件​

   循环等待条件可以通过定义资源类型的线性顺序来预防。如果一个进程已经分配到了R 类型的资源，那么接下来请求的资源只能是那些排在R 类型之后的资源类型。

8. 银行家算法​

银行家算法

---

第五章 存储管理

1. 页面置换算法​

页面置换算法

存储管理​

存储管理

碎片回收​

• 碎片紧凑

  • 实现方式：通过移动分配给进程的内存分区，以合并外部碎片。

• 分区对换

  • 抢占并回收处于等待状态进程的分区，以增大可用内存空间

• 伙伴系统

  • 空闲块按大小和起始位置组织称二维数组；
  • 初始状态时，只有一个大小为的空闲块；

  分配过程：

  • 由小到大在空闲块数组中找最小的可用空闲块；
  • 如果空闲块过大，对可用空闲块进行二等分，一个放入空闲块列表，另一块继续比较，直到得到合适的可用空闲块

2. 段页式内存​

段页式内存

---

第六章 文件系统

1. 有结构文件的逻辑结构​

顺序文件​

顺序文件：文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。

定长记录的顺序文件，若物理上采用顺序存储，则可实现随机存取；若能再保证记录的顺序结构，则可实现快速检索（即根据关键字快速找到对应记录）

一般来说，考试题目中所说的“顺序文件”指的是物理上顺序存储的顺序文件。可见，顺序文件的缺点是增加/删除一个记录比较困难（如果是串结构则相对简单）

索引文件​

索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。

另外，可以用不同的数据项建立多个索引表。如：

学生信息表中，可用关键字“学号”建立一张索引表。也可用“姓名”建立一张索引表。这样就可以根据“姓名”快速地检索文件了。

（Eg：SQL就支持根据某个数据项建立索引的功能）

索引顺序文件​

索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。

索引顺序文件（检索效率分析）​

若一个顺序文件有10000个记录，则根据关键字检索文件，只能从头开始顺序查找（这里指的并不是定长记录、顺序结构的顺序文件），平均须查找5000个记录。

若采用索引顺序文件结构，可把10000个记录分为√10000 = 100 组，每组100个记录。则需要先顺序查找索引表找到分组（共100个分组，因此索引表长度为100，平均需要查50次），找到分组后，再在分组中顺序查找记录（每个分组100个记录，因此平均需要查50次）。可见，采用索引顺序文件结构后，平均查找次数减少为50+50 = 100次。同理，若文件共有106个记录，则可分为1000个分组，每个分组1000个记录。根据关键字检索一个记录平均需要查找500+500 = 1000次。这个查找次数依然很多，如何解决呢？

多级索引顺序文件​

为了进一步提高检索效率，可以为顺序文件建立多级索引表。例如，对于一个含106个记录的文件，可先为该文件建立一张低级索引表，每100个记录为一组，故低级索引表中共有10000个表项（即10000个定长记录），再把这10000个定长记录分组，每组100个，为其建立顶级索引表，故顶级索引表中共有100个表项。

2. 文件目录​

---

第七章 设备管理

1. 设备的分类；设备控制（I/O 4方式）；设备管理的功能；高速缓存
2. 虚拟设备技术；SPOOLing技术；（输入井输出井，预输入缓输出）
3. 设备独立性

并行计算范围​

基础知识--并行平台​

• 单指令流多数据流（SIMD）: 单一控制部件向每个处理部件分派指令；
  • 控制语句会影响 SIMD 的性能
  • 只有一个全局控件
  • 设计研发周期长
• 多指令流多数据流（MIMD）: 计算机的每个处理器都能够独立于其他处理器执行不同的程序；
  • 需要在每个处理器上安装程序和操作系统
• 单程序多数据（SPMD）: 是MIMD模型的简单变形, 相当于将每一个MIMD中的计算指令用任务标识符指定的条件插入到一个大的if-else程序块中

基础知识--并行平台的数据通道/通信模型​

1. 共享地址平台​

共享地址空间是指并行平台支持一个公共的数据空间，所有处理器都能访问该空间。

处理器通过修改存储在共享地址空间的数据来实现交互。

2. 消息传递平台​

消息传递平台由p个处理节点构成，每个节点都有自己的独立地址空间。

运行在不同节点上的进程之间的交互必须用消息来完成，基本的消息交互操作是send和receive。

在由p个节点的共享地址空间计算机上，很容易模拟含有同样节点个数的消息传递体系结构；反之，在消息传递计算机上模拟共享地址空间体系结构的代价很高。

基础知识--并行平台的物理组织​

理想架构​

理想的并行随机访问计算机（PRAM） 包含p个处理器以及大小不受限制的全局内存，所有处理器同样可以访问该内存

然而允许并发就会带来同步问题,目前有几种协议解决同步问题:

• 共有，如果处理器试图写的所有值都相同，则允许并发写。
• 任意，任一处理器可以进行写操作，而其余的处理器则不行。
• 优先级，处理器按预定义的优先级列表排列、最高优先级的处理器可以进行写操作而其他的处理器不能。
• 求和，所有量的总和被写入（基于求和的写冲突解决模型能够扩展到任意由待写入量定义的相关操作符上)。

互联网络​

互联网络 提供多个处理节点之间或处理器与内存模块之间的数据传输的机制。

网络拓扑结构​

互联网络中使用了各种各样的拓扑。这些结构用来实现成本、可拓展性和性能间的平衡

1. 总线网络​

简单,到任意节点距离为O(1)

瓶颈在于总线带宽

2. 交叉开关​

网格型,每个交叉点均为一个开关

3. 多级网络​

多级网络比总线网络在性能方面可扩展性更强，又比交叉开关网络在成本上可扩展性更强

节点分层,每一层都可以采用不同结构

4. 多级omega网络​

每一级网络处理 p 个输入, p 个输出, 网络级数为 log p

每一级都有一种互联模式, 例如 完全混洗互联

经过完全混洗互联后,并非直接输出,而是两辆一组送到 2 * 2 **开关 **中

因此网络成本为 log p * p / 2 , 其中 log p 为 网络深度, p / 2 为每一层开关个数

此成本低于完全交叉网络的 p ^ 2

多级omega网络路由选择​

• 设s为需要写数据到存储区t的处理器的二进制表示。
• 数据穿过链路到达第一个开关节点。
• 如果s和t的最高有效位相同，那么开关就会按直通式方式进行数据选路;如果最高有效位不同，则以跨接方式进行数据选路。
• 在下一个开关级，再使用下一个最高有效位来重复同样的方案。

5. 线性阵列、格网、k-d网​

网络中链路过多, 选择稀疏网构造并行计算机

线性阵列 拓展到二维及为 格网

再拓展到更高维则成为 k-d网

6. 基于树的网络​

网络中任意一对节点间只存在一条通路

线性阵列和星形连接网络都是树网格的特例

静态网络在树的每个节点都有处理器;

动态树网络中，中间层的节点位交换节点，叶子节点是处理器

网络评价​

静态网络​

• 网络直径：网络中任意两个处理节点之间的最长距离。两个处理节点间的距离定义为它们间的最短路径（用链路数目表示)。
• 连通性：连通性是网络中任意两个节点间路径多重性的度量。
• 弧连通性：将一个网络分为两个不连通网络需要删去的最少弧数目。
• 对分宽度：把网络分为两个相等网络时，必须删去的最小通信链路的数目。
• 通道宽度：能够通过连接两个节点链路同时进行通信的位数。
• 对分带宽（或截面带宽）：对分网络任何两半之间允许的最小通信量，它是对分宽度和通道宽度的乘积。成本：网络中所需的通信链路数量。

动态网络​

由于动态网络中存在开关的概念, 因此需要将开关损耗也考虑在内,新增 节点连通性 指标

• 节点连通性：把网络分成两个部分必须删去的最小节点数目。这里只考虑开关节点（与考虑所有节点不同)。

高速缓存一致性​

该问题仍属于同步问题,目前依靠协议解决, 现存 更新 以及 无效 协议

• 更新协议: 无论何时写入一个数据项，它在系统中的所有副本都被更新。因此，如果某处理器只读了一次数据项，就再也不使用它，那么，其他处理器对该数据项的更新将会造成多余的开销。
• 更新协议和无效协议的性能均会受到**假共享（false sharing）**的影响。
• 当前的高速缓存一致性计算机 通常依靠无效协议。

无效协议​

每个数据副本都关联一个状态（shared, invalid, dirty）

当某处理器对变量做 存储操作 时, 该变量的所有副本都被标记为无效(invalid)。并把自己拥有的变量标记为已修改或脏（dirty)

若另一处理器执行 加载操作, 将变量标记为 dirty 的处理器会对请求提供服务, 并将全局副本更新, 数据重新变回 共享(shared) 状态

基础知识-进程-处理器映射​

映射过程中，有三个参数很重要。

• 第一，E中有可能不止一条边映射到E^′的一条边上。映射到E^′的任意边上的边数最大值称为映射拥塞度(congestion)。
• 第二，E中的一条边可能被映射到E'中多个相邻的边上。这一点也很重要，因为在相应链路的通信必须穿过不止一条链路，可能导致网络拥塞。E中的任意一条边能映射到E^′中的最大链路数目，称为映射膨胀度( dilation)。
• 第三，集合V和V^′可能包含不同数量的顶点。在这种情况下，V中的节点和V^′中不止一个节点相对应。集合V^′中节点的数目和集合V中节点数目之比称为映射扩充度。

并行计算优化​

传统意义上的串行计算机主要由 处理器、内存和数据通道 三个部件组成

优化处理器延迟​

改进设计理念: 一个时钟周期内执行多个指令

1. 流水线与超标量​

单流水线的速度最终受到流水线中最大原子任务的限制。

超标量: 在CPU中有一条以上的流水线，并且每时钟周期内可以完成一条以上的指令

超标量效率:

• 垂直浪费: 某一周期中执行部件没有指令发送；
• 水平浪费: 一个周期中只用到部分部件；

2. 超长指令字处理器(VLIW)​

超标量调度器的硬件成本和复杂性是处理器设计中的主要瓶颈。

为解决这个问题，VLIW处理器依靠编译分析技术来识别和捆绑可以同时执行的指令。

这些指令被调度和打包在一起，因此成为了长度超长的指令字。

这样做的好处是硬件设计简单

优化内存延迟​

1. 设立高速缓存(cache)​

2. 增加内存带宽​

增加块大小,使得取数操作减少,减少与 DRAM 交互,减少等待, 从而提高效率

3. 消除跨距访问​

该例子中,每次只读取 b 一行中的一个数, 会导致 cache 失效, 从而每次都需要直接与 DRAM 交互, 产生 跨距访问

该问题本质上与高速缓存相同

4. 多线程躲避延迟​

任务划分,这在第二章会详细解释, 本章节中简单理解为将互不影响的部分分到不同线程中并行执行,从而减少空闲时间

5. 预取​

数据载入操作提前, 即使发生 cache miss, 在真正需要使用时也能准备好

缺点: 如果数据项在载入和使用之间的时间间隔内被覆盖，就必须重新发出数据载入指令，从而影响程序性能。

优化通信成本​

两个节点间传送一条消息所花的时间是准备传送消息所花的时间及消息从网络中传送到目的地所花时间之和. 有以下主要参数：

1. 启动时间(ts)：在发送节点和接收节点处理消息所花费的时间。它包括消息的准备、执行路由算法等时间。
2. 每站时间(th)：消息在单个节点上的延迟时间。该时间受到网络延时、开关或路由延时的影响。
3. 每字传送时间(tw)：如果通道带宽是r个字每秒，那么每个字要花tw=1/r秒穿过链路。它包括网络开销以及缓冲开销。

1. 存储转发​

消息穿过有多个链路的路径时，路径上的每个中间节点接收和存储完整的消息后，就把消息转发给下一个节点。

将m个字的消息通过l个通讯链路发送到目的节点的总通讯时间 可用上述参数表示为: ts + th * l + tw * m * l

由于每站时间 th 很小,因此可以忽略不计, 简化为: ts + tw * m * l

2. 包路由选择​

把大的消息块分割成多个包,在网络中以流水线的方式处理这些包

这样可以省去等待包传输的时间, 因此总时间优化为: ts + th * l + tw * m

3. 直通路由选择​

直通路由选择在包路由选择的基础上做了以下改动：

• 消息被分成固定大小的单元，称为流量控制数字(flow control digit)或数据片(flit)；
• 强制所有的数据片走同样的路径。

相较于包路由选择，直通路由选择有以下优势：

• Flit比包小得多；
• 无每个包的传送路由选择信息开销；
• 无需顺序信息；
• 在并行计算机互连网络中（错误率极低），可采用错误检测机制取代开销很大的错误校正方案

在直通路由选择中,消息传递还可优化:

1. 大块通信：把多个小消息集中成一个大消息，这样就不用发送每条小消息和为每条消息花费开始成本ts；
2. 减少数据的大小：减少每字传送时间的开销；
3. 减少数据传送的距离：减少消息必须通过的站的数目。

互联网络路由选择​

根据路径长短的方式划分：

• 最小化路由选择；
• 非最小化路由选择。

根据确定性的方式划分：

• 确定性路由选择；

• XY路由选择 -》二维格网

  • 消息首先沿X维出发，直到到达目标节点的列，再沿Y维达到目的节点

• E立方体路由选择 -〉 超立方体网络

  • 与XY路由选择方案类似：在d维的超立方网络中，先从第一维出发，找到目标节点第一维相同的位置，再从第二维出发，直到在第d维到达目标节点

• 自适应路由选择

分解与分配是并行计算的关键步骤​

• 分解：将计算划分成许多小的计算；

• 分配：再把分解得到的小的计算分配到不同处理器中以便并行执行。

本文依据上述关键步骤, 大体上也分为 分解 与 分配 两个板块, 但在进入真正学习之前, 还请了解基础知识

一、基础知识​

1. 粒度、并发度、交互关系​

• 粒度: 体现了分解问题得到的任务数量和大小。

• 最大并发度: 任意时刻可同时执行的最大任务数称为最大并发度

• 平均并发度: 程序执行的整个过程中能并发运行的任务平均数,程序执行的整个过程中能并发运行的任务平均数

• 任务依赖图: 抽象表示任务间的依赖关系和任务的执行次序关系

• 关键路径长度: 依赖图中, 没有输入边的节点称为 起始节点，把没有输出边的节点称为 终止节点，任何一对起始节点和终止节点之间的最长有向路径就是 关键路径。关键路径上所有节点的权重之和称为 关键路径长度

• 任务交互图: 任务之间的交互方式可通过 任务交互图 来描述。

  • 任务交互图中节点代表任务，边连接彼此交互的任务

  • 任务交互图中的边集合通常是对应任务依赖图边集合的超集

• 任务间交互有无规则判定:

  • 有规则: 对于一个交互模式，如果 有一些结构（空间结构）有利于其交互的高效实现，那么这个模式被认为是有规则的。

  • 无规则: 如果一个交互模式中 不包含规则模式 ，则被称为是无规则的。

• 任务间交互静态与动态性

  • 静态交互模式：对于每一个任务，它们之间的交互在预定的时间发生，并且在这些时间交互的任务集在算法执行之前是已知的。

  • 动态交互模式：在算法执行前，交互的时间或交互的任务集不与先确定

• 交互的单向与双向

  • 双向交互：需要交互涉及的两个任务参与，某一任务或任务子集所需要的数据或工作明显由另一任务或任务子集提供。
  • 单项交互：交互可由参与某一个任务发起和完成，完成此交互并不会妨碍其他交互。双向交互在编程时往往更加 复杂。

2. 进程与映射​

分解中的任务数量超过可用处理元素的数量。因此，并行算法还必须提供 任务到进程的映射

映射由任务依赖关系图和任务交互图确定。

任务依赖图 可用于确保工作在任何时间点均等地分布在所有进程中（最小空闲和最佳负载平衡）

任务交互图 可用于确保进程需要与其他进程的交互最少（最少通信）

好的映射:

1. 应把相互独立的任务映射到不同的进程以获取最大并发度;
2. 应确保可用进程来执行关键路径上的任务，以使得任务变成可执行的时候总计算时间最短;
3. 映射相互交互的任务到同一个进程以便最小化进程间的交互

静态映射和动态映射​

• 静态映射:静态映射技术在 算法执行前 将任务分配给进程。
  • 以数据划分为基础的映射
  • 以任务划分为基础的映射
  • 分级映射(混合映射)
• 动态映射:动态映射技术在 算法执行期间 在进程间分配任务。
• 动态与静态的选择取决于以下几个因素：
  • 任务是否是动态产生
  • 任务大小是否已知
  • 与任务相关的数据大小任务间交互的特点
  • 并行编程模式等

二、 分解任务​

1. 递归分解​

流程:

1. 递归划分子问题
2. 对独立子问题并发求解

2. 数据分解​

流程:

1. 对数据划分
2. 根据划分数据推导计算到任务的划分

数据分解形式多样,可分为:

• 输入划分
• 输出划分
• 输入输出划分
• 中间结果划分

例子如下:

拥有者-计算规则

以划分输入或输出数据为基础的分解也常称为 拥有者-计算 规则。

规则思想：每一个划分都执行涉及它拥有的数据的所有计算。

3. 探测性分解​

探测性分解中只要一个任务找到答案，其他未完成任务就可以终止。因此并行形式执行的操作既可以少于也可以多于串行算法执行的操作

4. 推测性分解​

对于类似 switch 的语句, 在编译阶段并不可知其最终进入哪个分支, 因此需要推测分解任务

通常有两种方法：

• 保守方法：仅在保证没有依赖关系时并行执行；
• 乐观方法：即使它们可能是错误的，也调度和执行任务

保守的方法可能会产生很少的并发性，而乐观的方法可能需要在发生错误的情况下使用回滚机制

5. 混合分解​

组合以上分解方法以获得更优效果

分配任务(映射)​

负载平衡映射​

让各个进程负载平衡，并使进程的空闲时间最小，并尽量减少进程间的交互

静态映射​

以数据划分为基础​

数组分配​

• 块分配

  • 把数组分成小块,按照块划分, 负载不平衡

• 循环分配

  • 块循环分配思想：把数组划分成比可用进程数更多的块，这样就可以采用循环的方式把划分的块（和相关任务）分配给进程，以便每个进程都能得到若干不相邻的独立的块。解决负载不平衡

  • 在二维块循环分配中，如果每一块只有一个元素，这种分配称为循环分配

图划分​

有许多运行在稀疏数据结构上的算法，这些算法的数据元素间的交互模式具有数据依赖，并且非常不规则,物理现象的数值模拟提供了这种计算类型的大量来源。

以任务划分为基础​

决定一个通用任务依赖图的最优映射是NP完全问题。但在特定情况下，人们通常可以找到简单的最优解或者可接受的近似解。

分级映射​

纯粹建立在任务依赖图上的映射可能会遇到负载不平衡，或并发度不够

动态映射​

如果静态映射导致进程间负载高度不平衡，或任务依赖图本身就是动态的，就必须采用动态映射而排除静态映射。

一对多广播​

一个进程发送相同的数据给其他所有的进程或其他所有进程的子集

多对一归约(一对多广播的对偶)：在多对一归约操作中，p个参与进程的每一个都有一个缓冲区M，它包含m个字。来自所有进程的数据通过一个相关的操作符组合起来，并被累加到一个目标进程中一个m字的缓冲区中

实现方法​

可利用对偶性（一对多广播的对偶）实现：多对一归约可以先进行多对多归约（多对多广播的对偶），再进行收集操作（散发的对偶）

• 简单实现: 源节点向其余节点都发送消息, 简单但效率低下
• 递归加倍：源进程首先发送消息给另外一个进程。然后，这两个进程可以同时发送消息给还在等待消息的其他两个进程。继续这一过程，直到所有进程都收到了数据，这样消息可以在log p步广播完毕

1. 环或线形队列​

2. 网格​

可以把一个具有p个节点的方形格网的行或者列看作一个有√p节点的线性阵列。

一个线性阵列的通信操作可以在一个格网中分两个阶段来执行。

• 第一阶段，可以将格网中的行看作是线性阵列,将操作沿着一行或所有行进行。(除去每一行末尾节点)
• 第二阶段，再对列进行同样的操作。

3. 超立方体​

超立方具有2d个节点，那么可以将其看作是一个d维的格网，每个维度上有两个节点。因此格网算法能扩展到超立方体，在超立方体中的通信需要分d步来进行，每一步对应于每一维。

4. 平衡二叉树​

一对多广播的超立方算法可以自然地映射到平衡二叉树；

在平衡二叉树中，每一个叶子是处理节点，每一个中间节点是开关单元。

多对多广播​

实现方法​

1. 每个节点同时向它的一个邻居节点广播数据；
2. 在后面的步骤中，将每个节点同时向其他邻居节点转发从上一步骤中接受到的邻居节点的数据。
3. 整个算法在p-1步完成

1. 环型队列​

2. 网格​

1. 第一阶段，格网中的每一行执行一次线性阵列形式的多对多广播。在这一阶段里，每个节点从它们各自所属的具有√p个节点的行上收集√p个消息。每个节点把这些收集到的消息聚合成一个大小为m √p的消息，然后进行算法的第二通信阶段。
2. 第二通信阶段按列对合并后的消息执行多对多广播。当这一阶段完成时，每个节点获得p个m字的数据、这些数据原来驻留在不同的节点上。

全归约与前缀和​

• 全归约( all-reduce）操作等同于先进行一个多对一归约，再进行一个一对多广播。这个操作与多对多归约不同，多对多归约是p个多对一归约同时进行，并且每个操作都有不同的目标节点。使用多对多广播通信模式，可以更快地进行全归约操作
• 前缀和: 原始数字序列为（3，1，4，0，2），那么前缀和序列为（3，4，8，8，10）。

散发和收集​

• 散发(scatter)：单个节点发送一个大小为m的唯一消息给每一个其他的节点。发散操作的源节点从p个独自消息开始，每个消息将发给不同的节点。
• 收集(gather)：一个节点从其他各个节点那里处收集消息。收集操作并不涉及数据的组合与归约。

多对多私自通信​

每个节点给其他的每个节点发送一个大小为m的不同消息。每个节点都发送不同的消息给不同的节点！

环上的多对多私自通信​

1. 开始时每个节点把它们所有的数据作为一个合并的大小为m(p-1)的消息，发送给它们的一个邻居节点。
2. 随后，每个节点从接收到的数据中提取属于自身的数据，然后将剩下的p-2块m字大小的数据转发到下一个邻居节点上。
3. 重复步骤2，直至所有数据都发送到相应的节点上。

循环位移​

循环q移位(circular q-shift）定义:在一个p节点的系统中，节点i发送一个数据包给节点 (i+q) mod p，其中(0 < q < p )。

并行算法性能解析基础​

并行算法的执行时间不仅依赖于输入数据大小，还依赖于所用的处理器的数目，及它们相关的计算速度和进程间的通信速度

开销类型​

• 进程间通信：并行系统中 进程之间的通信，通常是并行程序开销的 最重要来源。
• 空闲时间：由于负载不平衡、同步问题或执行串行部分程序造成的空闲时间。
• 额外计算：在某些情况下，最优的串行算法可能无法并行化，这时我们需要使用较慢但容易并行化的算法，从而带来额外的计算开销。

性能评估指标​

• 执行时间: 从程序开始到结束所使用的时间
• 总并行开销: 所有处理器使用的总时间
• 加速比: 在单个处理器上求解问题所花的最短时间与用p个相同处理器并行计算机求解同一问题所花时间之比。

效率​

加速比与处理器数目的比率，即E= S/p。E的理想值应该小于等于1

当给定处理器数目p后，加速性能随着任务数n增加而下降！

粒度对于性能的影响​

有的时候使用更少的处理器可以提高并行系统的性能

如果使用少于最大可用处理器数量来执行一个并行算法的方法被称为按处理器数目***缩小（scaling down）***一个并行系统

可拓展性​

具备同时增加处理器数目和问题规模来保持效率为固定值的特性的系统称为 可扩展并行系统

并行系统的可扩展性是与处理器数目成比例增加加速比能力的度量，它反映一个并行系统有效利用（可变数量的）处理资源的能力。

对于给定的问题规模，当增加处理器数目时并行系统的总效率下降。这种现象在所有并行系统是常见的。

在很多情况下，如果问题规模增加而处理器数目不变，并行系统的效率增加。