编程范型

Functional Programming

函数式编程：使用纯函数

• 程序使用紧密的函数调用表示，这些函数可以进行必要计算， 但是不会执行会改变程序状态（如：赋值）的操作
• 函数就是数据值，可以像对待其他数据值一样对其进行操作

纯函数

纯函数：没有副作用、表达式对所有引用透明度表达式也是引用透明 的函数

• 执行过程中除了根据输入参数给出运算结果外没有其他影响
• 输入完全由输入决定，任何内部、外部过程的状态改变不会影响 函数执行结果

• reference transparency：引用透明，表达式可以用其结果 取代而不改变程序含义

语言基础

错误类型

• trapped errors：导致程序终止执行错误

  • 除0
  • Java中数组越界访问

• untrapped errors：出错后程序继续执行，但行为不可预知， 可能出现任何行为

  • C缓冲区溢出、Jump到错误地址

程序行为

• forbidden behaviours：语言设计时定义的一组行为，必须 包括untrapped errors，trapped errors可选
• undefined behaviours：未定义为行为，C++标准没有做出 明确规定，由编译器自行决定
• well behaved：程序执行不可能出现forbidden behaviors
• ill behaved：否则

语言类型

• strongly typed：强类型，偏向于不能容忍隐式类型转换
• weakly typed：弱类型，偏向于容忍隐式类型转换
• statically typed：静态类型，编译时就知道每个变量类型， 因为类型错误而不能做的事情是语法错误
• dynamically typed：动态类型，编译时不知道每个变量类型 ，因为类型错误而不能做的事情是运行时错误

• 静态类型语言不定需要声明变量类型

  • explicitly typed：显式静态类型，类型是语言语法的 一部分，如：C
  • implicitly typed：隐式静态类型，类型由编译时推导 ，如：ML、OCaml、Haskell

• 类型绑定

  • 强类型倾向于值类型，即类型和值绑定
  • 弱类型倾向于变量类型，类型和变量绑定，因而偏向于 容忍隐式类型转换

polymorphism

多态：能将相同代码应用到多种数据类型上方式

• 相同对象收到不同消息、不同对象收到相同消息产生不同动作

Ad hoc Polymorphism：

ad hoc polymorphism：接口多态，为类型定义公用接口

• 函数重载：函数可以接受多种不同类型参数，根据参数类型有 不同的行为

• ad hoc：for this, 表示专为某特定问题、任务设计的解决 方案，不考虑泛用、适配其他问题

Parametric Polymorphism

parametric polymorphism：参数化多态，使用抽象符号代替具体 类型名

• 定义数据类型范型、函数范型

• 参数化多态能够让语言具有更强表达能力的同时，保证类型安全

• 例
  • C++：函数、类模板
  • Rust：trait bound

• 在函数式语言中广泛使用，被简称为polymorphism

Subtyping

subtyping/inclsion polymorphism：子类多态，使用基类实例 表示派生类

• 子类多态可以用于限制多态适用范围

• 子类多态一般是动态解析的，即函数地址绑定时间

  • 非多态：编译期间绑定
  • 多态：运行时绑定

• 例

  • C++：父类指针
  • Rust：trait bound

变量设计

Lvalue、Rvalue

• lvalue：location value，可寻址
• rvalue：readable value，可读取

• 左值：引用内存中能够存储数据的内存单元的表达式

  • 使用表达式在内存中位置
  • 考虑其作为对象的身份

• 右值：非左值表达式

  • 使用表达式的值
  • 考虑其作为对象的内容

• 左值、右值最初源自C

  • 左值：可以位于赋值运算符=左侧的表达式
  • 右值：不可以位于赋值运算赋=左侧的表达式

左值

• 任何左值都存储在内存中，所以都有一个地址
• 左值声明后，地址不会改变，地址中存储的内容可能发生 改变
• 左值的地址是一个指针值，可以被存储在内存中的、像数据 一样被修改

特点

• 重要原则

  • 多数情况下，需要右值处可使用左值替代
  • 需要左值处不能用右值替代

• 重要特点

  • 左值存在在变量中，有持久的状态
  • 右值常为字面常量、表达式求职过程中创建的临时对象， 没有持久状态

一等对象

一等对象：满足以下条件的程序实体

• 在运行时创建
• 能赋值给变量、数据结构中的元素
• 能作为参数传递给函数
• 能作为函数返回结果

高阶函数

高阶函数：以其他函数作为参数、返回函数作为结果的函数

短路求值

短路求值：布尔运算and/or中若结果已经确定，则不继续计算之后 表达式

• x and y：首先对x求值

  • 若x为假停止计算
  • 否则继续对y求值再判断

• x or y：首先对x求值

  • 若x为真则停止计算
  • 否则继续对y求值再判断

• 返回值取决于语言实现

  • 确定返回布尔值：C/C++
  • 返回x、或y的求值结果：python

并发和并行

• Parallel：并行，同时做多件事情，关于执行、实现
• Concurrent：并发，能够处理多件事情，关于结构、逻辑

• 并发问题可以使用并行方式解决，也可以串行解决

  • 100并发任务同时运行在4核CPU上，最多可能有4个并发任务 并行处理，其余只能是串行处理

• 并行角度：硬件技术的物理限制瓶颈

  • 单计算核心能力不足，所以需要多核并行运算
  • 进程、线程可认为是实现并行的基本逻辑实体

• 并发角度：程序执行的逻辑重用需求

  • 程序要求重用一组逻辑，所以需要将一组指令集打包，重复 调用该组指令集
  • 子程序、协程可认为是方便重用的基本逻辑实体，因此更 应是语言内建机制
    • 子程序：无状态保存，同样重入得到同样结果
    • 协程：有保存状态，重入会改变协程状态，结果可能 不同

• 线程作为任务执行的实体，可以认为是子程序、协程的具体执行

  • 内核线程作为可以独立执行的实体，逻辑上更会被设计为 完成独立任务，即没有保存状态需求，因此多是子程序的 具体执行
  • 用户线程则用程序负责调度，二者执行实例均可
  • 某种意义上线程、子程序是对应的执行实体、逻辑实体

子程序、协程

• 子程序可以看作时协程的特例
  • 只有一个状态，每次进入时局部状态重置
  • 唯一入口点
• 协程可视为子程序的组成
  • 维护自身状态，所以逻辑上不独立 ，应该是作为被 调用对象
  • 对于每次返回部分结果值的协程（也称生成器迭代器）， 可以直接视为类似链表之类的数据结构 （在某些语言中可以所有数据都是类，从这个角度这也都是 统一的）

• 现代指令集通常提供对调用栈的指令支持，便于实现可递归 调用的子程序，在提供续体的语言环境（如Scheme），恰好 可用此抽象状态表示实现协程

Subroutine/Procedure/Function/Routine/Method

子程序：打包为整体、用于执行特定任务的指令集序列

• 子程序是依赖可重入能力的弱化版本

  • 一旦唤醒，于起始点开始执行
  • 一旦退出，子程序结束
  • 子程序实例只返回一次，两次激活间不保存状态

• 子程序中局部变量在每次调用/重入函数时都是相同的

  • 相同输入得到相同输出

• procedure：过程，有时特指无返回值、仅有副作用

线程安全

线程安全：子程序在多线程环境调用时，能够正确处理多个线程之间 的共享变量，使程序功能能正确完成

• 线程安全函数应该为每个调用其的线程分配专门空间，存储需要 单独保存的状态

• Atomicity：原子性，操作不会被线程调度机制打断，一旦 开始就会运行到结束，中间不会有任何线程切换

  • 可以通过lock、synchronized确保原子性
• Visibility：可见性，某线程修改变量值后，其他线程能够 立刻感知
  • 一般可以通过volatile保证可见性，强制要求被修改值 从寄存器同步至主存
  • lock、synchronized也可以通过限制其他线程访问变量 的方式保证可见性
• Ordering：有序性/一致性，程序按照代码顺序执行
  • 可以通过volatile保证一定的有序性
  • 也可通过lock、synchronized提供单线程执行环境保证 有序性

Instruction Reorder

指令重排：编译器对无相互依赖的指令重新排序执行

• as-if-serial语义：指令可以为优化而重排序，但是必须保证 最终执行结果不变

  • 规则：重排序过程不破坏数据依赖关系
  • 只能保证单线程执行结果有效，但不保证多线程并发执行 的正确性

  

• happens-before原则：保证前后两个操作间不会被重排序，

  • 程序次序规则：线程中每个操作happens-before该线程中 任意后续操作
  • 锁定规则：锁的解锁happens-before加锁
  • volatile变量规则：volatile变量写操作happens-before 其读操作
  • 传递规则：若A happens-before B、B happens-before C，则A happens-before C
  • 线程启动规则：线程对象启动happens-before线程中每个 动作
  • 线程中断规则：线程中断方法的调用happens-before被 中断线程代码检测到的中断事件的发生
  • 线程终结规则：线程中所有操作happens-before线程的 终止检测
  • 对象终结规则：对象的初始化happens-before其final 方法的开始

• happens-before原则被JVM用于规定（跨线程）操作之间偏序 关系，若操作之间的关系可以由此原则退出，则两个操作有序

Reentrant

• A computer program or routine is described as reentrant if it can be safely executed concorrently; that is, the routine can be re-entered while it is already running

可重入函数：对于相同（合法）的函数参数，多次重复调用（包括 执行过程中被中断再重入）结果总是可预期的

• 可重入需要满足条件

  • 不在函数内部使用静态或全局数据，所有数据都由函数 调用者提供
    • 全局变量区
    • 中断向量表
  • 使用本地数据，或制作全局数据的本地拷贝保护全局数据
  • 不返回静态或全局数据
  • 不调用不可重入函数

• 不可重入后果主要体现在信号处理函数这样需要重入情况中， 若在信号处理函数中使用了不可重入函数，则可能导致程序错误

• 可重入函数总是线程安全的，反之不一定成立

  • 线程安全可以通过“并发不冲突”实现
  • 可重入则要求“并行不冲突”

Coroutine

协程：为非抢占式多任务产生子程序的程序组件，允许执行过程 中挂起、恢复

• 挂起、恢复：协程可以通过yield（让步）调用其他协程暂时 退出，之后可在退出位置恢复执行

  • 从协程角度看，这是调用其他协程而不是退出
  • 但实际是各协程之间是对称的，而不像子程序调用 中主调-被调关系
  • 这即暗含
    • 协程可包含多个入口点
    • 允许在不同入口点暂停、开始执行程序

• 局部状态维护：协程实例保持上次退出时状态

  • 则协程被唤醒时状态可能不同
  • 可能同时有多个给定协程实例

• 协程将原在子程序外、输入状态管理工作交由自身逻辑维护
• 原生不支持协程的语言也可以使用循环等构建
• 经典状态机、对象已经具有协程特性

用途

• 协程可以简化异步代码的实现，使得需要使用异步+回调的代码 可以使用看似同步方式写出

  • 协程本身只涉及状态保存、过程重入，和并发/异步无关系
  • 但协程本身蕴含的状态保存使得状态切换几乎无成本，适合 高并发任务

• 协程在线程中调度完全由用户控制，可以视为用户态轻量级线程

  • 避免陷入无效内核级别上下文切换造成的性能损失
  • 较线程在IO密集任务上性能上更好

进程、线程

• 这里仅讨论理论上的异同，不考虑各平台具体实现

• 进程：具有独立功能的程序关于某数据集合的一次运行活动
• 线程/子程序：进程内某特定任务的执行活动
• 协程：推广协作式多任务的子程序

• 进程、线程、协程可以看作是控制权逐渐从系统已经移交到自身 的过程

• 这里的协程强调其在实现方面的资源、调度特点，其与子程序间 功能差异参加cs_program/parallel/implementation
• 通信：参见cs_program/parallel/#todo
• 移植性：基于进程分支多进程和windows模型有很大冲突，往往 不能在windows平台上使用

Process

进程：具有独立功能的程序关于某数据集合的一次运行活动

• 进程是处于运行期的程序和相关资源的总称

  • 程序：代码、指令
  • 运行：对CPU的占用，逐渐发展为线程，标识进程中指令的执行
  • 资源：执行上下文，由进程内线程共享

• 从系统调度方面看

  • 进程是系统进行资源分配、调度的独立单位
  • 在系统中有进程控制块（进程描述符）描述进程相关信息， 系统通过此控制块控制系统相关行为

• 从资源分配方面看

  • 有独立的存储空间（虚拟寻址空间）
    • 独享的用户空间
    • 进程专用的“共享内核空间”
  • 可执行的程序代码

• 线程可能对系统是可感知的，则进程不定是资源分配的基本 单位
• Linux线程实现即类似进程，但不包含独立存储空间

调度角度

• 内核跟踪进程运行所需的状态信息（上下文）

  • 主存、虚拟内存内容
  • 寄存器文件值
  • 栈
  • 文件句柄

• 调度：分配CPU执行进程

  • 内核决定CPU控制权在进程间的转移

• 上下文切换：进程状态的记录、恢复、切换

  • 保存当前进程上下文、恢复新进程上下文
  • 通过处理器在进程间切换，实现单个CPU“看似”并发执行 多个进程
  • 上下文进程间切换开销比较大，但相对比较稳定安全

资源角度

• 独立内存空间/虚拟地址空间：每个进程“独占的”使用 内存、看到一致的存储器

• 用户空间

  • 程序代码、数据：对所有进程，代码从同一固定位置开始， 直接按照可执行目标文件的内容初始化
  • （运行时）堆：可在运行时动态扩展、收缩
  • 共享库：共享库代码和数据，如：C标准库、数学库
  • 栈：用于实现函数调用，运行时动态扩展、收缩，位于虚拟 地址空间顶部

• 内核空间

  • 内核虚拟存储器：内核总是驻留在内存中，为其保留地址 空间顶部
  • 不允许程序读写区域内容或直接调用内核代码定义的函数

Thread

线程：进程执行实体，进程中包含指令的执行活动

调度角度

• 线程是CPU调度、分派的基本单位，有时被称为轻量级进程 （在Linux系统中也是按照轻量级进程实现）

• 线程引入逻辑

  • 进程内部可能存在多个不同task，task需要共享进程数据
  • 同时task操作的数据具有独立性，多个task不需要按照时序 执行
  • task间需根据不同策略进行调度，因此产生了线程概念， 并被引入作为内核调度基本单位

• 线程：比进程更小的、能独立运行的基本单位

  • 线程能/是“独立运行”，但不一定能被内核感知到，也一定由 内核调度
  • 只能说线程是针对某个task的执行活动

资源角度

• 线程运行在进程的上下文中，共享同样代码和全局数据

  • 进程代码段、公有数据
  • 进程打开的文件描述符、信号的处理器
  • 进程当前目录
  • 进程用户ID、进程组ID

• 线程还独享某些个性以实现并发性

  • 线程ID：进程中唯一标识
  • 寄存器组值：线程间并发运行，线程有不同运行线索， 切换时需要保存当前线程的寄存器集合状态
  • 线程堆栈：独立函数堆栈保证线程内函数调用可以正常 执行，不受其他线程影响
  • 错误返回码：线程的系统调用错误可能未及时处理，独立 错误返回码避免其被其他线程修改
  • 线程的信号屏蔽码：线程感兴趣的信号不同，因此信号 屏蔽码应由自己管理
  • 线程优先级：线程需要像进程被调度，需要有相应的优先级

线程实现理论

User-Level Thread

用户级线程：由用户程序自身负责支持、调度

• 特点

  • 相当于实现自己的线程调度内核，实现线程数据结构、 创建、销毁、调度维护
  • 线程运行在内核（可感知的）进程内

• 优点

  • 即使系统不支持线程，也可通过库函数支持在系统中实现 真实的多线程
  • 线程只在用户态，减少内核态到用户态切换开销

• 缺点：线程对系统透明，对系统每个进程只有一个线程， 系统直接调用进程

  • 当线程进行系统调用而阻塞时，系统会阻塞整个进程
  • 用户空间没有时钟中断机制，若线程长时间不释放CPU， 会导致阻塞其他线程

Kernel-Level Thread

内核级线程：系统内核支持的线程，通过内核完成线程切换

• 优点/特点：系统负责线程的创建、销毁、调度、维护

  • 内核通过操纵调度器对线程进行调度，并负责将线程 的任务映射到各个处理器上
  • 程序可以直接使用系统调用已实现线程，无需实现线程 调度、对CPU资源抢占使用

• 缺点：内核线程需要内核支持

  • 创建、销毁、调度、维护往往都需要系统调用，代价较高
  • 需要消耗内核资源，不能大量创建

线程调度模型

• X对Y是指X task对应Y内核调度单位

N对1模型

N对1模型：线程库有实现用户级线程，内核未实现内核级线程

• 系统只负责调用进程
• 线程对系统透明，由进程自身负责调用

• 此模型中内核没有实现内核级线程，所以内核调度单位就是进程 S

  1对1模型

1对1模型：线程库未实现用户级线程，内核实现有内核线程

• 程序（逻辑）层面

  • 创建执行独立task的线程
  • 程序创建的线程直接由内核负责调度

• 内核（实现）层面

  • 每次创建线程都是调用系统调用创建内核级线程
  • 可视为每个“用户创建的线程”同内核级线程绑定，二者一一 对应

• 此模型中内核调度单位就是内核级线程
• 此模型中不存在上述定义的用户级线程，图中Thread实际上 应该就是Kernel Thread，仅拆分出来表示是程序创建的线程

M对N模型

M对N模型：线程库实现有用户级线程，系统也实现有内核级线程

• 程序（逻辑）层面

  • 创建执行独立task的用户级线程
  • 创建可独立被内核调度的内核级线程
  • 将若干和用户线程同内核线程相关联，即task组总体由内核 负责调度，task组内task由程序自身负责调度

• 内核（实现）层面

  • 调用系统调用创建内核级线程
  • 内核线程执行指令中包含用户线程创建、调度指令

• 优点

  • 用户级线程创建、切换、析构等均在用户空间中，依然 廉价，支持大规模用户线程并发
  • 内核级线程作为用户线程在内核中调度、执行的桥梁， 降低整个进程被完全阻塞的风险

• 此模型中内核调度单位为内核级线程、task单位为用户线程， 二者比例不定
• 有的说法里面会使用Light Weighted Process表示内核级线程

通用调度算法

• 耗时相差不大的task队列总是比较好处理，难以调度的task是

  • 耗时相差大
  • IO任务、计算任务混合

• 内核调度除考虑任务（线程）外，还会考虑进程因素

  • Gang Scheduling：尽量将同进程中线程同时调度，而非 随机从多个进程中挑选CPU数量线程调度
  • Space Sharing：将CPU划分，各进程仅允许占用部分CPU 执行并发

• 从任务角度，调度需要考虑

  • Responsiveness
  • Schedule Overload
  • Starvation-Freedom：饥饿避免
  • Fairness

First-In-First-Out

先进先出：按task在队列中的顺序依次调用，执行完task再执行下个 task，仅在task结束后才会切换task

• 优点

  • 最少task切换开销
  • 最大吞吐量（总处理效率）
  • 朴实公平

• 缺点

  • 平均相应时间高

Shortest task First/Shortest Remained Time task

最短耗时task优先：有限调度耗时短task

• 优点

  • 平均相应时间短：长耗时task不断推移，必然统计出较短 平均响应时间

• 缺点

  • 不公平，长耗时task难被调度，容易饥饿
  • 频繁task切换，调度额外开销大

Round Robin

时间片轮转：给队列中每个task时间片，时间片结束之后task移至 队列末尾，切换到执行下个task

• 优点

  • 每个task可以得到公平调度
  • 耗时短task即使在耗时长task之后也可以较快得到执行

• 缺点

  • task切换引起的调度开销大，需要多次切换task上下文
  • 时间片不好设置
    • 时间片足够小则退化为SFJ
    • 时间片足够大则退化为FIFO
  • 需要知道task（剩余）执行时间

(Weighted) Max-Min Fairness

（带权重的）最大最小公平：资源按照需求递增的顺序分配，不存在 需求得到资源超过自身需求，未得到满足得到需求等价分享资源

• 具体方案
  • 每轮开始将资源按照权重分配
  • 若需求大于被分配资源则推迟执行，进入下轮
  • 若需求小于被分配资源则执行，并将多余资源继续按照权重 分配给无法执行资源

Multi-level Feedback Queue

多级反馈队列：监控task处理耗时，若task未用尽分配资源则提高 优先级，否则降低其优先级

• 具体方案

  • task、分片时长具有相对应的不同优先级
    • 分片时长越长优先级越低
    • 高级优先级task可以抢占低优先级task
    • 新task位于高优先级task
  • 同一优先级task使用Round Robin （事实上仅有最低优先级task使用Round Robin算法， 其他优先级都是FIFO）
    • 时间片用完后task结束则正常退出系统，否则优先级 下滑一等级
    • 若是主动让出CPU（IO等），则停留在当前优先级或 提升

• 多核场景

  • 应该为每个CPU分配单独MFQ，同时采用 Affinity Scheduling保证task尽量同一CPU核上执行， 避免CPU cache频繁失效
  • 若共用MFQ，则容易出现
    • 随CPU增长，对MFQ锁争抢严重
    • task每次执行位于的CPU不同，CPU Cache需要在不同 CPU间转移

同步问题

生产者-消费者问题/缓存绑定问题

• 生产者生成数据放入缓存，消费者从缓存获取、移除、消费数据 ，问题核心在于保证不让生产者在缓存已满时放入数据、不让 消费者在缓存为空时读取数据

• 若缓存满：生产者者停止工作
• 若缓存空：消费者停止消费
• 消费者从缓存中取走数据，通知生产者工作
• 生产者向缓存中放入数据，通知消费者消费

• 不完善的解决方案会造成死锁：生产者、消费者均等待对方唤醒

信号量解决方案

• mutex信号量：互斥信号量，确保只有一个生产者、消费者 操作缓存区，单一消费者、生产者可省略此信号量
• fill_count信号量：已使用缓存区数量
• empty_count信号量：空闲缓存区数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

semaphore mutex = 1
semaphore fill_count = 0
semaphore empty_count = BUFFER_SIZE

producer():
	while true:
		item = produce_item()
		down(empty_count)
		down(mutex)
		put_item_into_buffer(item)
		up(mutex)
		up(fillcount)

consumer():
	while true:
		down(fill_count)
		down(mutex)
		item = remove_item_from_buffer()
		up(mutex)
		up(empty_count)
		consume_item(item)

状态监控解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

item_count = 0
condition full
condition empty

add(item):
	while item_count == BUFFER_SIZE:
		wait(full)

	item_count = item_count + 1
	put_item_into_buffer(item)

	if item_count == 1:
		notify(empty)

remove():
	while item_count == 0:
		wait(empty)

	item_count = item_count - 1
	item = remove_item_from_buffer()

	if item_count == BUFFER_SIZE - 1:
		notify(full)

produer():
	while true:
		item = produce_item()
		add(item)

consumer():
	while true:
		item = remove()
		consume_item(item)

• 互斥信号没有保护关键区，监控方法更好

其他

• 协调生产者、消费者的关闭

  • 可在在队列中放置特殊的值，消费者读到时终止执行，结束 消费者线程
  • 有多个消费者时，消费者读取特殊值之后可将特殊值放回 队列中继续传递，直至关闭所有消费者

哲学家就餐问题

• 哲学家围坐在圆桌旁，只能吃饭或者思考，每两个哲学家 之间只有一根筷子，只有同时拿到左右两根筷子才能正常吃饭

• 实际计算机问题中，筷子视为共享资源

服务生

• 引入服务生判断资源是否能被获取

• 引入服务生，哲学家必须经过其允许才能拿起筷子

• 服务生知道有哪些筷子正在被使用，能够判断是否会死锁

资源分级

• 为资源（筷子）分配偏序关系

  • 约定所有资源都按此偏序获取、相反顺序释放
  • 且保证不会有无关资源同时被同一工作获取

• 哲学家只能拿左右侧筷子：不会有无关资源被同一工作获取

• 将筷子按顺序编号：资源分配偏序关系

  • 哲学家只能先拿左右筷子中编号较小者
  • 哲学家需要先放下筷子中编号较大者

• 最实用的解法：为锁指定常量分级，强制获取顺序的顺序
• 策略不总是实用的，尤其是所需资源列表事先不知道，可能需要 先释放已获取资源、获取低编号资源、重新获取资源，效率不高

Chandy/Misra解法

• 标记资源，保留未使用资源、交出已使用资源，初始所以资源 已使用

• 每根筷子分为干净、脏，最初所有筷子都脏

• 对每对竞争同一筷子的哲学家，新拿筷子给编号较低者

• 当哲学家需要某筷子时

  • 向其竞争对手发送请求
  • 拥有筷子的哲学家收到请求
    • 若筷子干净则保留
    • 否则擦干净交出

• 哲学家吃完东西后，筷子变脏

  • 若有哲学家之前请求过该筷子，擦干净交出

• 有很大并行性，适合任意大问题

读者-写者问题

• 多线程同时访问共享内存地址，线程写入时其他线程不能读取、 写入，多个线程可以同时读取

• 一般使用readers-writer lock解决问题

读者优先

• 若共享内存被读取，其他读者可以立即、同时读取
• 若一直有读者开始读取，则写者会一直被插队、无法修改

写者优先

• 如果写者在排队，应该尽快写入共享内存
• 若一直有写者准备写入，则读者会一直被插队、无法读取

限定时间

• 共享内存区的锁定权要在限定时间内结束
• 能避免读者、写者一直排队

熟睡的理发师问题

• 理发店只有一名理发师、一张理发时坐的椅子、若干普通椅子 供顾客等待

  • 没有顾客时理发师在理发椅子上睡觉，顾客到达后离开、 或者叫醒理发师
  • 有顾客时，理发师为别人立法，顾客达到后若有空闲普通 椅子则坐下休息、否则离开
  • 理完发后，任选顾客开始理发

• 理发师等待顾客、顾客等待理发师，造成死锁
• 有顾客不按顺序等待，让某些顾客永远不能理发

3信标解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

semaphore customer = 0
semaphore barber = 0
semaphore mutex = 1
empty_chairs = BUFFER_SIZE

barber():
	while true:
		if empty_chairs == BUFFER_SIZE:
			sleep()

		down(mutex)
		item = get_customer_from_chairs()
		empty_chairs += 1
		up(mutex)

		down(barber)
		cut_hair(item)
		up(barber)

customer():
	while true:
		down(mutex)
		if empty_chairs > 0:
			empty_chairs -= 1

		else:
			wait() or leave()

		up(mutex)

三个烟鬼问题

• 香烟需要：烟草、卷烟纸、火柴，三个烟鬼分别有无限各一种， 不吸烟协调人会随机安排两个烟鬼各拿出一份材料放在桌上， 另外一个烟鬼拿到材料卷烟、抽

  • 桌上空了后，协调人就随机要求烟鬼拿出材料
  • 烟鬼只会在抽完手中烟后才会卷另一只
  • 若烟草、卷烟纸在桌上，有火柴的烟鬼在吸烟，直到该烟鬼 吸完烟拿走桌上材料才会继续

• 问题模拟程序中4种角色，展示信标方法作用有限

数值存储

• 机器数：数在计算机中二进制表示形式，带符号
• 真值：考虑表示规则，机器数二进制表示的真实数值

• 大小端

  • big-little endian大小端：高位byte在低位byte前
    • 更适合人理解
  • little-big endian小大端：低位byte在高位byte前
    • 更适合计算机计算，大部分计算机架构
    • 方便截断操作

• 符号（有符号数）：大部分（静态）语言使用最高位表示符号

  • 0：正数
  • 1：负数

  • 动态语言如 python 的整形不对应定长数据类型，存储逻辑和 cpp/c 等语言相差较大

整形

• 模：衡量计数系统容量的参数，代表了计数系统能表示、存储的状态数

原码、反码、补码

• sign and magnitude 原码：二进制位表示数值本身
  • 需要额外符号位标识正负
• ones’ complement 反码：二进制位为真值对计数系统最大值求补
  • one：表示有限位计数系统能表示的最大值，即二进制位全为 1
    • 符号位不仅标识正负值，且可作为数值位参与运算
    • 但不是对模求补
      • 存在 +0/-0 问题
      • 运算结果和实际结果相差 1
  • 考虑到二进制位全 1 性质
    • 正数：反码即为其原码
    • 负数：反码为原码符号位不变，数值位取反（因此被称反码）
• twos’ complement 补码：二进制位为真值对计数系统模求补
  • two：表示有限位计数系统容量，即溢出 1、二进制位全为 0
    • 符号位不仅标识正负值，且可作为数值位参与运算
    • 考虑到是对模求补
      • -0 表最大负值，不存在 +0/-0 问题
      • 运算结果和实际结果相同
  • 将有限位计数系统视为加法封闭群
    • 系统中各元素是有序的，为保证加法计算，则最大正值之后必然为最大负值
    • 正、负值可视为是对群元素的人为划分
    • 可以任意值作为划分，但二进制位计算真值复杂
  • 考虑到二进制位全 0 性质
    • 正数：补码即为其原码
    • 负数：补码为反码 +1（原码也为补码数值位求反后 +1）

浮点型

• 遵循 IEEE 754 标准的系统必须支持单精度，最好支持双精度，对扩展精度则无要求

• 符号位：数值整体正负号
• 指数/阶码：数值小数点位置，也即数值放缩
  • 阶码部分没有单独的符号位，为表示负值，则需要规定指数偏移，将 阶码减去偏移量得到实际指数值
  • 指数偏移被设置为 $2^{E-1} - 1$ 好处
    • 对称正负取值范围
    • 首位即可判断浮点值和 1 关系
• 尾数：数值精确程度
  • 根据 IEEE 754，规格化值尾数首位（整数位）必须为 1
    • 规格化值的尾数值必然大于 1
    • 单、双精度可以省略对首位的存储，有效位数比尾数长度多 1
    • 扩展精度不区分是否为规格化值
  • （单、双精度）非规格化值首位为 0，同样省略
    • 非规格化值允许尾数部分小于 1，扩展浮点数对小值的表示
    • 所以，非规格化值阶数部分必然（规定）全为 0
    • 非规格化值指数偏移量比规格化值小 1，可缩小最小规格化值与最大非规格化值间距
• 特殊浮点值
  • 指数值全 1、尾数非 0：NaN
  • 指数值全 1、尾数为 0：正、负无穷

• 事实上指数底数可以是任意值，但 IEEE 754 标准规定底数为 2

Abstract Charater Repertoire

抽象字符集：ACR

字符

字母、数字、标点、表意文字（汉字）、符号或其他文本形式的 “原子”

抽象字符

抽象的字符，包括空白、不可打印的字符

• 对于某些语言中，抽象字符应该还包括发音字符

• 如：印度语中单词“नमस्ते”

  • 有6个字符[‘न’, ‘म’, ‘स’, ‘्’, ‘त’, ‘े’]，
  • 其中4、6两个字符在单词不出现，是发音字符

Abstract Charater Repertoire

抽象字符集：ACR，抽象字符的集合

• 集合表明无序性
• 有时也简称为字符集（charater set）
• 有开放（字符不会改变）和封闭之分（会扩张）

Coded Character Set

编码字符集：CCS

Code Point

码位：抽象字符集中与字符关联的数字编号

• 一般是非负整数
• 习惯上有16进制表示

Coded Character Set

编码字符集：CCS，每个所属字符都分配了码位的抽象字符集

• 经常简称为字符集（charater set），同ACR弄混
• 字符与码位一一映射
• 可以更加方便的引用字符集中的某个元素
• 可以类比于dict

字符集（抽象、编码）举例

US-ASCII

ACSII字符集

• 128个抽象字符，封闭字符集

• 主要包括

  • 控制字符：回车、退格、换行
  • 可显示字符：英文大小写、阿拉伯数字、西文符号

• 一般字符集都是兼容ascii编码字符集，即相同字符的码位相同

ISO-8859-X

扩展的ASCII字符集

• 涵盖了大多数西欧语言字符、希腊语

GBXXXX

国标系列字符集：每个标准包含的字符数量不同、对应的编码方案 也不不完全相同

• GB2312：信息交换用汉字编码字符集基本集

  • 包含汉字覆盖99.75%的使用频率
  • 人名、古汉语等罕用字不能处理

• GBK：汉字内码扩展规范

  • 包括21003个汉字
  • 支持国际标准ISO/IEC10646-1和国家标准GB13000-1中 全部中日韩汉字
  • 包含了BIG5编码中的所有汉字
  • 兼容GB2312

• GB18030：信息技术中文编码字符集

  • 其中收入汉字70000余个
  • 以汉字为主并包含多种我国少数民族文字（如藏、蒙古、 傣、彝、朝鲜、维吾尔文等）的超大型中文编码字符集 强制性标准
  • 兼容GBK

Big5

Big5字符集：主要包含台湾、香港地区繁体字

Universal Character Set/Unicode/UCS

统一字符集/Unicode字符集：ISO/IEC 10646定义的编码字符

• 开放字符集，码位无上限，容纳一切字符，包括emoji等

• UCS中码位不是连续分配的

  • 目前为止，分为0x0000~0x10FFFF共17个平面

  • 其中0平面0x0000~0xFFFF称为 basic multilingual plane

  • BMP中码位只有16bit长度，能够节约大量存储空间，有 战略意义

  • 因此“常用”语言的常用字符放在BMP，其他不常用的字符 只能放在其他平面

• unicode本身是指一系列用于计算机表示所有语言字符的标准

Character Encoding Form

字符编码表：CEF，将码位映射为码元序列

• fixed-length-encoding：定长编码，对每个码位（字符） 赋予长度同为m的码元（位串）

  • 封闭字符集符号有限，可以直接确定一一对应编码表

• variable-length-encoding：变长编码，允许对不同码位 赋予不同长度的码元

  • 开放字符集包括符号无上限，无法定长码元表示码位， 必须有某种方式将码位一一映射为码元序列
  • 封闭字符集出于节约成本考量，也可能使用变长编码 如：Huffman编码

• 码元：能用于处理或交换编码文本的最小比特组合（位串）

Unicode定义的CEF

本质思想：预留标记位值使码元序列的长度实现变长

UTF-8

• 码元为1B
• 对BMP中字符一般需要1~3B，BMP外需要4B
• 兼容ASCII编码表（方案）
  • 不同于编码字符集兼容的意义，基本上编码字符集都 兼容ASCII编码字符集，即对应字符码位相同
  • 兼容编码表指，“ASCII编码方案”可以使用UTF-8解码 方案直接解码

UTF-16

• 码元为2B
• 对BMP中字符一般需要2B，BMP外需要4B

UTF-32

• 码元为4B

Prefix-Free Code

（自由）前缀码：所有代码码元都不是另一个字符码元的前缀

• 可以简单扫描位串直到得到一组有效码元，转换为相应字符

• 这样编码表可以很容易用一棵（编码）二叉树表示

  • 树左向边标记为0、右向边标记为1
  • 叶子节点表示字符，根节点到叶子节点路径为其码元
  • 树中叶子节点到其他叶子节点的简单路径不存在，即码元 不可能为其他码元前缀
  • 所以任何二叉树对应一套编码表

• 这种编码方案一般用于产生平均长度最短的位串

  • 因此这类编码方案以bit为单位，而不是以byte为单位

Huffman Encoding

哈夫曼编码：prefix-free code的一种

• 根据字符出现频率进行编码

  • 需要事先知道字符出现概率
  • 可以事先扫描给定文本，对文本中字符出现字符计数
  • 将较短位串分配给高频字符、较长位串分配给低频字符

• 若字符独立出现，则哈夫曼编码是最优编码（最短长度编码）

• 需要把编码树信息包含在编码文本中才能正确解码

• 构造哈夫曼树的贪婪算法参见组合问题

Adaptive Huffman Encoding

利用已经处理字符串动态更新编码

Lempel-ziv

对字符串编码

Character Encoding Schema

字符编码方案：CES，字符编码表+字节序列化方案，将码位 映射为字节流

• 大小端序问题：码元高位还是低位字节在前
• 字节序标记问题：不同程序之间端序交流

• 通常所说编码、解码就是指使用CES

应用场合

• CES是真正的应用层面，需要给出具体存储方案实现， 前述都是理论上protocol

• 所有字符串存储介质中，磁盘、内存都采用某种具体CES 实现存储

  • Java、Python3这样的偏上层语言，字符串对象在内存中 通常采用UTF-16

  • C这样偏底层语言，基本上按照源文件的编码确定，即将 源文件中对应字符串对应字节，但现在C/C++中还有一种 宽字符w_char类型

• 以上仅对Unicode而言，对于ASCII来说没有区分必要

内存CSE说明

• 内存中如果不使用某种CES实现，直接使用码元，一样会出现 长度问题，所以显然会使用某种CES方案

• 虽然在内存中，字符仍然使用某种编码方案得到字节流存储，但 这个字节流并不是这个字符，码位才“是”这个字符

  • 大部分提供Unicode处理语言会自动处理字符，不仅仅 是字节

  • 在考虑字符串问题时，可以“抽象的”忽略具体存储方式， 认为存储的就是“码位”本身

Byte Order Mark

字节序标：BOM，放置于编码字节开始处的特殊字节序列，表明 序列大小端序

• 0xFFFE：小端序，低位在前
• 0xFEFF：大端序，高位在前

Unicode族CES方案

UTF

unicode transfromation format：历史上是指CES，而UTF-X 现在可以同时指代CES和CEF，Unicode族标准CEF方案

• UTF-8：utf-8编码表码元为1B，不存在字节序问题

  • 指代CES和CEF没有什么区别，CEF只有一种

• UTF-16：指代CES和CEF时有歧义，需要明确指明是 UTF-16 encoding form（码元序列）、 UTF-16 encoding schema（字节流）

  • UTF-16-le：utf-16编码表小端版本
  • UTF-16-be：yutf-16编码表大端版本
  • UTF-16：utf-16编码表带BOM版本，大小端均可

  • UTF-16 CES表示BMP（包含大部分常用字符）只需要2B， 权衡了内存占用、处理便捷，适合作为内存中字符串的 编码方案

• UTF-32

  • UTF-32le：
  • UTF-32be
  • UTF-32

UCS

Unicode还有两种非标准CES

• UCS-2：使用2B定长序列化码位
  • 可以视为UTF-16的子集
  • 不支持BMP外的字符表示
• UCS-4：使用4B定长序列化码位
  • 可以视为UTF-32的子集

其他字符集CES方案

US-ASCII、GBK都有自己的编码方案，只是编码方案太简单，以至于 CCS、CEF、CES三层合一

• ASCII编码方案：1B的低7位表示一个字符
• ISO-8895-1编码方案：1B表示一个字符
• GB2312编码方案：2B表示一个汉字
  • 第一个字节：区字节，高位字节
  • 第二个字节：位字节，低位字节
• GBK编码方案：2B表示一个汉字
  • 兼容GB2312方案
  • 编码范围：0x8140~0xFEFE，剔除0xxx7F
• GB18030编码方案：变长字节1B、2B、4B
  • 兼容GBK方案
• Big5编码方案：2B表示一个汉字
  • 字节顺序类似GB2312

ANSI编码

• 各个国家、地区独立制定、兼容ASCII编码，但彼此之间不兼容 的编码方案，微软统称为ANSI编码

• ANSI编码一般代表系统（仅win）默认编码方式，在不同系统中 指不同的编码方案

  • 英文操作系统：ISO-8859-1
  • 简体中文：GBxxxx编码
  • 繁体中文：Big5编码
  • 日文：Shift JIS编码

• 默认ANSI编码可以通过设置系统Locale更改

  • win下系统Locale决定代码页，用户Locale决定数字、 数字、货币、时间与日期格式

Transfer Encoding Syntax

传输编码语法：TES，有时候需要对字节流再次编码以进行传输

• 如：某些字符不允许出现在传输流中

举例

• base64编码：将字节流映射成64个安全字符集组成的字符流

输入、输出辨析

输入

所有的输入都是经过CES编码的字节流（包括数字）

• 文件输入流：文件编码方案决定
• 标准输入流（terminal）：terminal编码方案决定
• 管道传输流：由管道输入端的编码方案决定

处理

这里应该有两种处理方式

• 将输入视为字节流，不做任何处理，直接按字节存储在 内存中

  • 将输入字节流视为其自身编码方案字节流，直接储存

• 将输入视为字符串，尝试解码

  • 若解码发现无法解释位串

    • strict：报错
    • replace：将违规字符替换为有效字符
      • 替换为某种?：很多应用采用此方式，是乱码 发生的主要原因
      • 有些也替换为Unicode码位
    • ignore：忽略该位串

  • 而解码后字符串的在内存中的存储，取决于解释器、编译器 、系统等处理主体的编码方案

• 以上只是对真正有字符串类型的语言Python、Java有这样区分
• 对于没有字符串类型的语言C并没有真正意义上的字符串，只有 字节串，不涉及解码、自身字符串内存存储的问题，仅有换行符 转义问题（若处理换行符被视为解码）

输出

所有输出都是编码后字节流（包括数字）

• 文件输出流：write
• 标准输出流（terminal）：print
• 管道传输流

• 需要注意的是，输出的字节流编码方案和处理主体在内存中编码 方案不一定相同，和编程实现、平台等因素都有关，比如很多 默认输出编码方案为utf-8
• 同样的，此输出流是对于其接收者而言仅仅是字节流，需要自行 决定如何处理字节流
• 此输出是指传递给直接输出外部的输出，有些语言在输出前 会隐式调用函数生成字符串

其他常见问题

乱码

乱码主要有以下3种可能

• 读取乱码：真正的乱码
  • 读取时没有正确解码，内容被替换，打印输出
• 存储乱码：保存时已经是“乱码”，其实也不能算是乱码
  • 读取时没有正确解码，内存中内容已经被错误，保存后内容 保持错误
  • 内存中数据正确，但保存使用的编码方案不支持某些字符， 内容被替换
• 缺少字体库

• 乱码不是其实已经是将不能打印的字符剔除、替换，能看到的 乱码已经是程序认为“正确解码的字符串”

换行符处理

• 鉴于以下两种行为

  • win下换行需要两个字符\r\n标识，linux下只需要\n 即可
  • 编程语言往往类似Linux只需要\n即标识换行

  • Vim中在内存中以<CR>标识换行

• 在win下很多语言以字符串模式：读取字节流时会自动将\r\n 替换为\n、写出字节流时替换回\r\n

  • Python这种原生支持字符串语言，这个特性可以看作字符串 解码的行为
  • C这种原生只支持字节串的语言，这个特性可能是二进制、 字符串读写的唯一区别

例子

以UTF-8编码方案为例

• 输入的所有的内容都是由UTF-8编码方案编码的字节流

• 处理主体获取字节序列，根据指令处理字节序列

  • 比如字节序列编码和处理主体编码不同，将其解码为 主体编码方案
  • 比如按照约定将字节序列转变为不同类型的数据

• 输出则是将需要输出的内容（包括数字等）转换字节流传给底层 函数

局域网协议

Identification Protocal

Ident协议

• 如果客户端支持Ident协议，可以在TCP端口113上监听ident请求

  • 基本每个类Unix操作系统都带有Ident协议

• Ident在组织内部可以很好工作，但是在公共网络不能很好工作

  • 很多PC客户端没有运行Ident识别协议守护进程
  • Ident协议会使HTTP事务处理产生严重时延
  • 很多防火墙不允许Ident流量进入
  • Ident协议不安全，容易被伪造
  • Ident协议不支持虚拟IP地址
  • 暴露客户端用户名涉及隐私问题

• Ident协议不应用作认证、访问控制协议

Internet协议

C0、C1 控制字符集

• C0、C1 控制字符

  • ISO/IEC 2022 定义的控制字符集
  • Unicode 中控制字符码位兼容 ISO/IEC 2022，但
    • 仅对 U+001C - U+001F、U+0009 - U+000D、U+0085 限定语义
    • 其余控制字符语义对 Unicode 透明，留给高层协议

  • https://zh.wikipedia.org/wiki/C0%E4%B8%8EC1%E6%8E%A7%E5%88%B6%E5%AD%97%E7%AC%A6

C0 控制字符集

• CO 控制字符集码位范围：0x00 - 0x1F

  • ASCII 中定义控制字符标准
  • 码位限定在 1byte 可以表示，避免终端机需要实现状态机处理多字节控制序列
  • 现只有少数控制字符被使用

• C0 控制字符码位范围之外，还有定义有两个具备控制符特点的字符

  • 0x7F（delete）
  • 0x20（space）

C1 控制字符集

• C1 控制字符集码位范围：0x80 - 0x9F

  • 8bits ISO/IEC 8859 ASCII 扩展提出后
    • 考虑到可打印字符的最高比特位去掉之后不应变成控制字符
    • 以 C0 控制字符集作为低位、最高位置 1，得到 C1 控制字符集
  • C1 码位在经常被私有编码方案（Windows-1252、Mac Os Roman）用于提供额外的可打印字符

• ISO/IEC 8859 ASCII 扩展标准中指定

  • 为兼容 7bits 传输，所有 C1 控制字符使用 ESC 开头的 7bits 字符序列表示

标准 C 转义规则

• 非打印（包括控制）字符可以通过其 ASCII 码位 16 进制、8 进制表示
  • \0[ooo]：八进制数 oo 码位字符
  • \x[hh]：十六进制数 hh 码位字符
    • \x0a：同 \n
• 针对常用非打印字符，有如下简写方式
  • \\：反斜杠 \
  • \'：单引号 '
  • \"：双引号 "
  • \a：BEL ASCII 响铃
  • \b：BS ASCII退格
  • \f：FF ASCII 进纸
  • \n：LF/NL ASCII 换行，开启新行
  • \r：CR ASCII 回车，“指针移至行首”
  • \t：TAB ASCII 制表符
  • \v：VT 垂直制表符

ANSI Escape Sequences

ANSI：一种 In-band Signaling 的转义序列标准，用于控制终端上 光标位置、颜色、其他选项

• 在文本中嵌入的 ANSI 转义序列，终端会将 ANSI 转义序列解释为相应指令，而不是普通字符

  • ANSI 转义序列使用 ASCII 中字符传递所有信息

• ANSI 转义序列有不同长度，但都

  • 以 ASCII 字符 ESC（0x1b） 开头
    • 8 进制表示：\033
    • 16 进制表示：\x1b
  • 第二字节则是 0x45 - 0x5F（ASCIIi @A-Z[\]^_）范围内的字符

• 标准规定，在 8bits 环境中

  • ANSI 转义序列前两个字节的序列可以合并为 0x80 - 0x9F 范围内的单个字节（即 C1 控制字符）
  • 但在现代设备上，C1 控制字符码位被用于其他目的，一般不被使用
    • UTF-8 编码对 x80 字符本就需要 2bytes
    • Windows-1252 编码将 C1 控制字符码位挪作他用

• C0 控制字符输出有时也会产生与 ANSI 转义序列相近效果，如：LF、ESC E都有换行效果
• https://zh.wikipedia.org/wiki/ANSI%E8%BD%AC%E4%B9%89%E5%BA%8F%E5%88%97
• https://www.gnu.org/software/screen/manual/html_node/Control-Sequences.html

No-CSI - 非控制序列

Control Sequence Introducer

控制序列导入器：ESC[ + 若干参数字节 + 若干中间字节 + 一个最终字节

• 常见序列只是把参数用作一系列分号分隔的数字，如：1;2;3

  • 缺少的数字视为 0
  • 某些序列（CUU）把 0 视为 1，以使缺少参数情况下有意义

• 一部分字符定义“私有”，方便终端制造商插入私有序列

  • 参数字节 <=>? 的使用：ESC[?25h、ESC[?251 打开、关闭光标显示
  • 最终字节 0x70 - 0x7F

光标移动

窗口

Select Graphic Rendition

• SGR 选择图形再现：ESC[[n]m
  • [n]：多个参数用 ; 分隔，缺省为 0
  • m：结束字节

样式

3/4位色

• 可通过反显 7 实现背景色、高亮 1 实现多高亮色

8bits 色

• 8bits 色设置格式
  • ESC[38;5;37m：设置256位前景色
  • ESC[48;5;37m：设置256位背景色
• 预定义 8bits 色情况
  • 0-7：标准颜色，同 ESC[30-37m
  • 8-15：高强度颜色，同 ESC[90-97m
  • 16-231：16 + 36*r + 6*g + b（$0 leq r,g,b leq 5$ 得到 6 6 6 立方）
  • 232-255：24阶灰阶

24bits 色

• 24bits 色设置格式

  • ESC[38;2;<r>;<g>;<b>m：选择 RGB 前景色
  • ESC[48;2;<r>;<g>;<b>m：选择 RGB 辈景色

• 字符内容体系结构有一个不太受支持的替代版本

  • ESC[38:2:<Color-Space-ID>:<r>:<g>:<b>:<unused>:<CS tolerance>:<Color-Space: 0="CIELUV";1="CIELAB">m：选择 RGB 前景色
  • ESC[48:2:<Color-Space-ID>:<r>:<g>:<b>:<unused>:<CS tolerance>:<Color-Space: 0="CIELUV";1="CIELAB">m：选择 RGB 背景色

• 支持 libvte 的终端上支持 ISO-8613-3 的 24bits 前景色、背景色设置，如 Xterm、Konsole
• 24bits 色的替代版本是 ISO/IEC 8613-6 采用的 ITU 的 T.416 信息技术

Abstarct Syntax Tree

AST：抽象语法树，源代码的抽象语法结构的树状表示形式

• 基本上语言中每种结构都与一种AST对象相对应

  • 不同解释器会有独有的AST格式

• AST定义了代码的结构，可以通过操纵AST，精准定位到各种语句 ，实现

  • 代码分析、检查：语法、风格、错误提示
  • 代码结构优化：代码格式化、高亮、自动补全
  • 优化变更代码：改变代码结构

函数通信

• 简单通信方式：允许进程向其他进程发送简单信息

  • 命令行参数
  • 信号：受控于操作系统的非同步事件机制
  • shell环境变量
  • 程序退出状态码
  • 简单文件

• 匿名管道：允许共享文件描述符的线程、进程传递数据

  • 仅在进程内部存在，通常和进程分支合用作为父进程、 子进程之间的通信手段、线程之间通信

  • 依赖于类Unix下进程分支模型，可移植性差

• 具名管道FIFO：映射到系统的文件系统，允许不相关程序 进行交流

  • 是真正的外部文件，通过标准文件接口实现
  • 可以独立启动，局限于本地进程通信时可以替代套接字
  • 相较于普通外部文件，操作系统同步化FIFO访问，使之 适合IPC

• 套接字socket：映射到系统级别端口号

  • 允许远程联网机器程序之间交流
  • 可移植性较好，几乎所有平台都支持

• 共享内存：消息保存在函数外部，不随着函数栈清除消失

  • 全局变量
  • 类中变量

锁

• 线程/进程调度本质上是不确定的

• 并行编程中错误使用锁机制可能会导致随机数据损坏、其他 异常行为，即竞争条件

• 最好在临界区（对临界资源进行操作的部分代码）使用锁

死锁、预防

• 线程/进程同时获取多个锁

避免、预防方案

• 尽可能保证每个线程/进程只能同时保持一个锁

• 为程序中每个锁分配唯一ID，然后只允许按照升序规则使用 多个锁

  • 单纯按照对象ID递增顺序加锁不会产生循环依赖，而循环 依赖时死锁必要，从而避免进入死锁状态
  • 可以数学上证明，这样能保证程序不会进入死锁状态

检测、恢复方案

• 引入看门狗计数器：
  • 线程正常运行时每隔一段时间重置计数器
  • 没有发生死锁时正常运行
  • 一旦发生死锁，无法重置计数器导致计数器超时，程序通过 重启恢复自身状态

并行计算模型

PRAM

Parallel Random Access Machine：随机存取并行机器模型，也称 共享存储的SIMD模型，从串行的RAM模型直接发展起来

假定

• 容量无限大的共享存储器

• 有限个或无限个功能相同的处理器，具有简单的算术运算和逻辑 判断功能

• 任何时刻各处理器都可以通过共享存储单元相互交互数据

分类

根据处理器对共享存储单元同时读、同时写的限制，PRAM模型可以 分为下面几种

• PRAM-EREW：Exclusive-Read and Exclusive-Write，不允许同时 读、写

• PRAM-CREW：Concurrent-Read and Exclusive-Write，允许同时 读、不允许同时写

• PRAM-CRCW：Concurrent-Read and Concurrent-Write，允许 同时读和同时写，允许同时写是不现实的，进一步约定

  • CPRAM-CRCW：Common PRAM-CRCN，只允许所有的处理器同时 写相同的数

  • PPRAM-CRCW：Priority PRAM-CRCN，只允许最优先的处理器 先写

  • APRAM-CRCW：Aribitrary PRAM-CRCN，允许任意处理器 自由写

  • SPRAM-CRCW：Sum PRAM-CRCN，往存储器中写的实际内容是 所有处理器写的数的和

优点

• 适合于并行算法的表达、分析和比较

• 使用简单，很多关于并行计算机的底层细节，比如处理器间通信 、存储系统管理和进程同步都被隐含在模型中

• 易于设计算法和稍加修改便可以运行在不同的并行计算机系统上

缺点

• 模型中使用了全局、单一共享存储器、局存容量较小

  • 不足以描述分布主存多处理机的性能瓶颈
  • 共享单一存储器的假定，不适合分布存储结构的MIMD机器

• PRAM模型是同步的

  • 意味着所有的指令都按照锁步的方式操作
  • 耗时长、不能反映现实中很多系统的异步性；

• 假设不现实

  • 模型假设每个处理器可在单位时间访问共享存储器的任一 单元，要求处理机间通信无延迟、无限带宽和无开销，忽略 资源竞争和有限带宽
  • 假设处理机有限或无限，对并行任务的增大无开销

BSP模型

异步MIMD-DM（Distributed Memory）模型

• BSP模型支持消息传递系统，块内异步并行，块间显式同步

• 模型基于一个master协调，所有worker同步(lock-step)执行， 数据从输入的队列中读取

模型描述

模型可以用 p/s/g/i 4个参数进行描述

• p：处理器的数目(带有存储器)。

• s：处理器的计算速度。

• g：选路器吞吐率

  • 定义为：time_steps / packet
  • time_steps：每秒本地完成的局部计算数目
  • packet：通信网络每秒传送的数据量

• i：全局同步时间开销，Barrier synchronization time

同步和通信的开销都规格化为处理器的指定条数，p台处理器同时 传送h个字节信息，则gh就是通信的开销

模型结构

BSP程序同时具有水平和垂直两个方面的结构

• 垂直上：BSP程序由一系列串行的超步(superstep)组成

  

• 从水平上看：在一个超步中，所有的进程并行执行局部计算

• 超步可分为三个阶段

  

  • 本地计算阶段：每个处理器只对存储本地内存中的数据进行 本地计算
  • 全局通信阶段：对任何非本地数据进行操作
  • 栅栏同步阶段：等待所有通信行为的结束

特点

• 模型将计算划分为一个一个的超步(superstep)，有效避免死锁。

• 处理器和路由器分开，强调了计算任务和通信任务的分开，且 路由器仅仅完成点到点的消息传递，不提供组合、复制和广播等 功能，掩盖具体的互连网络拓扑、简化了通信协议

• 一般分布存储的MIMD模型的可编程性比较差，但BSP模型中，若 计算和通信可以合适的平衡（例如g=1），则它在可编程方面 呈现出主要的优点。

• 采用障碍同步的方式以硬件实现的全局同步是在可控的粗粒度级 ，从而提供了执行紧耦合同步式并行算法的有效方式，而程序员 并无过分的负担

• BSP模型起到为软件和硬件之间架起一座类似于冯·诺伊曼机的 桥梁的作业，因此BSP模型也常叫做桥模型

• BSP模型上曾直接实现了一些重要的算法（如矩阵乘、并行前序 运算、FFT和排序等），均避免自动存储管理的额外开销

• 为PRAM模型所设计的算法，都可以采用在每个BSP处理器上模拟 一些PRAM处理器的方法来实现。

不足

• 模型中，在超级步开始发送的消息，即使网络延迟时间比超级步 长度短，该消息也只能在下一个超级步才能被使用

• 全局障碍同步假定是用特殊的硬件支持的，但很多并行机中可能 没有相应的硬件

LogP模型

分布存储、点到点的多处理机模型

模型描述

通信网络由4个主要参数描述

• L：Latency，源处理机与目的处理机进行消息通信所需要的 等待或延迟时间的上限，表示网络中消息的延迟

• O：Overhead，处理机准备发送或接收每个消息的时间开销

  • 包括操作系统核心开销和网络软件开销
  • 在这段时间里处理不能执行其它操作

• G：Gap，一台处理机连续两次发送或接收消息时的最小时间 间隔，其倒数即微处理机的通信带宽。

• P：Processor，处理机/存储器模块个数

以处理器周期为时间单位，L、o、g可以表示成处理器周期 整数倍

特点

• 抓住了网络与处理机之间的性能瓶颈：带宽

  • g反映了通信带宽，单位时间内最多有L/g个消息能进行处理机间传送。

• 处理机之间异步工作，并通过处理机间的消息传送来完成同步

• 对多线程技术有一定反映。每个物理处理机可以模拟多个虚拟 处理机（VP）

  • 某个VP有访问请求时，计算不会终止
  • VP的个数受限于通信带宽和上下文交换的开销、网络容量
  • 至多有L/g个VP。

• 消息延迟不确定，但延迟不大于L

  • 消息经历的等待时间是不可预测的
  • 但在没有阻塞的情况下，最大不超过L。

• 可以预估算法的实际运行时间。

不足

• 对网络中的通信模式描述的不够深入，有些现象未描述、考虑

  • 重发消息可能占满带宽
  • 中间路由器缓存饱和等未加描述

• 主要适用于消息传递算法设计

  • 对于共享存储模式，则简单地认为远地读操作相当于两次 消息传递
  • 未考虑流水线预取技术、Cache引起的数据不一致性以及 Cache命中率对计算的影响

• 未考虑多线程技术的上下文开销

• 用点对点消息路由器进行通信，这增加了编程者考虑路由器上 相关通信操作的负担

背景

• 根据技术发展的趋势，20世纪90年代末和未来的并行计算机发展 的主流之一是巨量并行机，即MPC（Massively Parallel Computers）， 它由成千个功能强大的处理器/存储器节点，通过具有有限带宽 和相当大的延迟的互连网络构成。所以我们建立并行计算模型 应该充分考虑到这个情况，这样基于模型的并行算法才能在现有 和将来的并行计算机上有效的运行。

• 根据已有的编程经验，现有的共享存储、消息传递和数据并行 等编程方式都很流行，但还没有一个公认的和占支配地位的编程方式， 因此应该寻求一种与上面的编程方式无关的计算模型。而根据 现有的理论模型，共享存储PRAM模型和互连网络的SIMD模型对 开发并行算法还不够合适，因为它们既没有包含分布存储的情况， 也没有考虑通信和同步等实际因素，从而也不能精确的反映运行 在真实的并行计算机上的算法的行为，所以，1993年D.Culer等人 在分析了分布式存储计算机特点的基础上，提出了点对点通信 的多计算机模型，它充分说明了互联网络的性能特性，而不涉 及到具体的网络结构，也不假定算法一定要用现实的消息传递 操作进行描述

并行算法基本设计策略

串改并

发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行 算法

• 最常用的设计思路但并不普适
• 好的串行算法一般无法并行化（数值串行算法可以）

全新设计

从问题本身描述出发，不考虑相应的串行算法，设计全新并行算法

借用法

找出求解问题和某个已解决问题之间的联系，改造或利用已知算法 应用到求解问题上

并行算法常用设计技术

划分设计技术

使用划分法把问题求解分成两步：

• 把给定问题划分成p个几乎等尺寸的子问题
• 用p台处理器并行求解子问题

分治设计技术

• 将复杂问题划分成较小规模特性相同的子问题
• 且子问题类型和原问题类型相同
• 通常用递归完成分治算法

平衡树设计技术

• 以树的叶结点为输入，中间结点为处理结点
• 由叶向根或由根向叶逐层进行并行处理

倍增设计技术

• 递归调用时，所要处理数据之间的距离逐步加倍
• 经过k步后即可完成距离为2^k的所有数据的计算

流水线技术

• 将算法路程分成p个前后衔接的任务片段，一个任务片段完成后 ，其后继任务片段可以立即开始

• 则可以引入流水线的思想来处理多条数据

并行计算机体系架构

Shared Memory

Distributed Memory

Hybrid

并行编程模型

数据并行模型

相同操作同时作用于不同数据

共享变量模型

用共享变量实现并行进程间通信

消息传递模型

驻留在不同节点上的进程通过网络传递消息相互通信，实现进程之间 信息交换、协调步伐、控制执行等

?

Hook/Callback

• callback：回调函数，实现与调用者分离

  • 在API中注册、用于在处理流中的合适时刻调用的函数
  • 可以看作是hook的一种

• hook：钩子函数

  • 更广义的、用于修改对API调用的函数
  • callback、hook意义其实差不多，很多情况下名词混用

• register：注册函数

  • 提供参数作为hook的挂载点
  • register通过挂载点调用hook

优点

• 让用户实现hook然后注册，框架调用用户自定义的hook，提供 更好的泛用性

• 框架不再处理hook函数中涉及的问题，降低系统耦合程度

• hook函数可以随时更换，提升框架的灵活性、扩展性

实现

函数指针作为函数参数，API通过函数指针调用函数实现 定制API

C实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

 # include<stdlib.h>
 # include<stdio.h>

void populate_array(
	int *array, 
	size_t array_size,
	int (*get_next_value_hook)(void)
	// `get_next_value_hook`就是函数指针
	// hook的“挂载点”
){
	for (size_t i=0; i<array_size; i++){
		array[i] = get_next_value();
	}
}

int get_next_random_value(){
	return rand();
}

int main(){
	int array[10];
	poppulate_array(array, 10, get_next_random_value);
		// 这里`get_next_random_value`就是钩子函数
	for(int i=0; i<10; i++){
		printf("%d\n", array[i]);
	}
	printf("\n");
	return 0;

Python实现

python中虽然没有明确的C中的函数指针，但是实现原理仍然类似， 都是“函数指针”作为参数，由API负责调用实现定制API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import random

populate_array(l, len, func):
	# `func`就类似于`C`中的函数指针，hook的挂载点
	for i in range(len):
		l[l] = func()

get_next_random_value():
	return random.random()

def test():
	l = [ ]
	populate_array(l, 10, get_next_random_value)
		# `get_next_random_value`就是钩子函数
	print(l)

Closure

闭包：一个函数及与其相关的组合

• 将回调函数与数据封装成单独的单元
• 实现方式
  • 允许在函数定义的同时，使用函数内部变量支持闭包，如： python
  • 使用特定数据结构实现闭包，如：C++使用函数类实现

Cache

• 固定大小：存储空间有上限
• 快速获取：插入、查找操作必须快速，最好$\in O(1)$
• 达到存储空间上限时可以替换已有缓冲项

Least Recently Used Cache

LRU Cache：优先排除least recently缓冲条目

• hashmap存储键、节点地址：常数时间查找
• 双向链表存储数据：利用地址可常数时间插入、删除

• 缓冲条目每次被获取后，移至双向链表头
• 缓冲区满后，删除双向链表最后节点条目，新条目插入表头

• https://medium.com/@krishankantsinghal/my-first-blog-on-medium-583159139237