并发：强调同一时间点两个活动都在执行
并行：强调同一时间点两个程序在不同处理机上执行
故并行真包含于并发
竞争现象：由调度产生的不确定性
数据竞争产生原因：多进程在没有同步保护的情况下对同一个共享变量进行访问，且有一方执行写操作
数据竞争解决：并发程序执行时不能在没同步保护的情况下对同一共享变量进行至少一个写的操作 (Berstein条件)
进程
defi: 程序在一个数据集合上运行的过程。系统进行资源分配和调度的最小单位
包含代码、数据、PC的值、通用寄存器的值、系统资源（文件等）
进程控制：进程创建、撤销和状态转换
- 进程创建
- 系统初始化（shell，daemon）
- 创建进程（系统调用）
- 启动程序
原语：一个指令序列，用于实现某个特定功能（常驻内存，不可中断）
创建原语：fork，exec
fork子进程后调用exec，会用新进程的text、data和堆栈段替换当前进程
进程状态：
- 就绪：除cpu资源以外其他资源全部就绪，排队
- 执行：占用cpu资源
- 阻塞：正在执行的cpu需要等待（等待访问资源，初始化I / O且必须等待结果）
转换：注意阻塞不能转执行，只能转就绪
进程上下文切换
内核态only
切换包括虚拟内存、栈、全局变量等用户空间资源，也包括内核堆栈、寄存器的内核空间资源，保存在寄存器
在OS中设计进程机制
进程控制块PCB：进程对应的数据结构，在linux里就是task_struct
内容
- 进程描述信息
- 进程标识符：每个进程唯一
- 用户标识符：进程所属用户
- 进程控制和管理信息
- 进程状态
- 进程抢占CPU的优先级
- 资源分配清单
- 内存资源
- 地址：指向该进程的地址可见在物理内存或虚拟内存（页表）里的位置的指针
- 内存分配详情：e.g. 页表、段表指针、分配给进程的内存大小和权限（可读写、可执行）等
- 文件资源
- 打开的文件列表：可能是文件描述符
- 文件详情：每个打开文件的指针、访问模式、当前位置偏移量等
- 使用的I/O信息
- 分配的设备列表
- 设备状态：例如，分配给进程的网络套接字、音频通道等
- 其他资源
- 例如：IPC相关资源，如消息队列、共享内存段、信息量等
组织方式
- 线性表：全部连在一起
- 索引表：线性表 + 构建一个不同状态的进程索引表
- 链式表：相同状态的PCB首尾相连
在中断处理的切换中，使用汇编写的原因：汇编可以直接访问CPU硬件，效率最高
模式切换（用户态 ↔ 内核态）：主要就切换寄存器，比进程上下文切换的消耗小得多
线程
defi：线程是进程当中的一条执行流程
进程不足：切换、通信、共享数据开销大
资源拥有者：进程
可执行单元：线程（共享同一份进程资源，但是处理的计算不同）
线程可并发运行，且共享进程资源
线程独立资源（主要）：寄存器和执行栈
线程执行栈的管理：
线程在被创建时，会在当前进程的虚拟地址空间中分配一块新的内存区域作为线程栈
在TCB中保存当前线程的运行栈顶指针
同一进程的线程切换开销比起进程切换小很多，因为要切换加载保存的东西很少
实现方式
用户级线程
由用户态的线程管理库实现线程的一切，包括TCB
不太需要kernel支持，不用切换内核态和用户态，上下文切换较快
内核只能感知进程，无法感知用户级线程
资源直接给到一个进程上，怎么分完全由用户级线程库管理
也因此无法将一个进程的多个线程映射到多个处理器核上
系统调用过多引起阻塞，内核直接阻塞进程
所以，无法实现一个进程中多个线程的并行
线程库：POSIX Pthreads
内核级线程
kernel的几个线程，分别提供各自的服务
可以在多个处理器上调度一个进程的多个线程
只阻塞一个线程
CPU调度以线程为单位
线程管理全靠syscall，开销大
混合
UT-to-KT
KT多：开销大 UT多：被阻之后会阻一堆
many-to-one
one-to-one
many-to-many
作业 VS 进程
作业主要用于批处理系统，是用户向计算机提交任务的任务实体，提交后会被放在外存中的作业等待队列
而进程一旦创建则总有一部分留在内存中
作业由≥1个进程组成
作业 = 程序 + 数据 + 操作说明书
进程 = 程序 + 数据 + PCB
同步与互斥
并发：有限物理资源强行行使多用户共享
竞争条件：多个进程对同一数据的访问顺序影响最终执行结果
临界资源：一次仅允许一个进程访问的资源
临界区：每个进程的 访问临界资源的代码
进程互斥：共享资源需要唯一且排他性的使用，无序访问
临界区管理：空闲让进，忙则等待，有限让权等待（等待进入临界区时间有限，且长时间不使用临界区时释放CPU）
进程同步：互斥，但是通过其他机制实现了对访问者的控制
基于忙等待的互斥
软件
面包店算法：每个进程在进入临界区前抓号，发号器由小到大发号（可能出现不同进程号码相同的情况，此时根据pid编号排序），小号先进
缺点：忙等待空耗CPU资源
硬件
补充：原子操作：不可（被线程调度机制）中断的一个或一系列操作，运行期间不会有任何上下文切换
开关中断
test and set（一种不会被中断的原子指令）
swap
共性问题：忙等待浪费CPU时间，且进程优先级反转
solution：进不去临界区的进程被阻塞，让出CPU；离开临界区的进程唤醒被阻塞的进程
基于信号量的同步
忙等 → 阻塞，A用完了就唤醒队列中的进程
信号量：用于累计唤醒次数的变量类型，只有P(S)和V(S)两种操作
- 程序对其的访问都是原子操作
- 结构：(int s, queue q)
- s ≥ 0: s = 发出P操作后可立即执行的进程数
- s < 0: |s| = 被阻塞的进程数，发出P后进程被阻塞
- q：被阻塞进程队列（不是ready list）
- 分类
- 二元（s只取0or1，用于互斥）
- 一般
- 强弱（描述queue的出队顺序，强则FIFO，弱则无序）
- semWait，P(S): S.count -= 1，如果S.count < 0则当前进程被阻塞
- semSignal，V(S): +=1，≤0则解除被P操作阻塞的进程的阻塞
- 实现：原子操作（TS指令 or 开关中断）
- 信号量应用
- 有限并发就控制s.count初值为资源数
- 实现同步（顺序执行）就把s.count初值设为0
- 注意：语句执行 和 信号量设置没有必然联系，信号量是人为通过指令控制的，语句执行是语句自身的问题
- 信号量集
- AND型：把资源类别扩展到底多个资源Sn，一次分配进程所需要的全部进程，释放的时候也是全部使用完之后一起释放
- 一般型：参数扩展：SP(Si, ti, di, …), SV(Si, di, …)
- ti表示对信号量最小值的约束：若Si.count < ti则不分配
- di表示分配的资源数，即信号量的增减
- 缺点：死锁问题，恶意进程
管程
引入条件变量X：对应不同原因的进程阻塞等待队列，可以执行
wait(X) 和 signal(X)操作场景：多进程进入管程
Hoare
信号量定义
mutex：表示资源数，P表示管程入口，V表示管程出口
next：使用
signal 操作后P一下，把自己挂起，进程退出前V一下，以唤醒在next上等待的进程x-sem：申请资源得不到满足时P（在
signal 操作之后V一下）进程间通信
无名管道
- 数据只能单向流动
- 只能用于兄弟或者父子进程
- 只存在于内存当中
有名管道
- 直接存在于OS的文件系统中，通过路径则可访问
- 任意进程间使用
- FIFO规则：读则读队首，写则写队尾
消息传递：发送和接收(
send, receive)- 陷入内核
- 复制消息到OS空间的缓冲区中
- 入队（接收进程的消息接收列表）
- 复制消息至接收进程
共享内存
同一物理内存映射到不同进程各自的逻辑地址
I/O密集型进程：频繁请求IO，不需要太多时间就会被阻塞（利：RR, MLQF）
CPU密集型：计算量大，需要大量CPU时间（利：FCFS）
RR: 这一时间片执行完的进程 会优先于 下一时间片被调进就绪队列的进程
最短剩余时间优先(SRTF)：抢占式的SJF，只有有比目前进程剩余时间短的直接切换
最高响应比优先(HRRF)：RP = 1 + 等待时间 / 要求运行时间，性能比SJF差（计算响应比）
MLFQ: 从高到低级的队列，最低级是RR，其他的都是FCFS（一个时间片没执行完丢到下一级的队尾）
实时调度算法
实时系统的任务集：周期性执行的时间固定的任务，必须在规定的时限内完成 (Ti, ci, Di)
CPU利用率 = Σ(ci/Ti)
静态表：事先确定一个调度方案
单调速率调度RMS：最优，抢占式，周期越小优先级越高，相同时随机选
最早截止期优先EDF：抢占式，任务离ddl越近（即本次的截止期越小）优先级越高
信号量问题
先P资源再P互斥量（确认资源ok了再进去排队）
对计数器的访问也需要一个mutex信号量进行控制
控制read_count是为了控制读写互斥，副作用是让读者优先
写者优先：需要一个 读者禁止锁r加在读者最外层，需要一个write_count变量记录写者个数，当且仅当写者个数为0时才把 读者禁止锁r 给释放
在读者优先的情况下为读者和写者的外层都套一个P(queue)和V(queue)，queue := 1，保证队列是一个一个进来的
哲学家问题（5人）
- 奇数拿左，偶数拿右
- 设置同时可以拿起筷子的人数为4，即semaphore room = 4
- 只有左右手同时拿到筷子了才让别人拿，即拿筷子前加一个mutex