操作系统

kernel - 操作系统内部组件包括:

• CPU 调度器
• 物理内存管理
• 虚拟内存管理
• 文件系统管理
• 中断处理与设备驱动

• 并发指的是在一段时间内(可长可短)有多个程序可以运行,需要 OS 的管理和调度; 并行指的是在一个时间点上有多个程序可以同时运行, 并行要求计算机有多个 cpu,如果只有一个 cpu 的话,是没办法完成并行的

• 共享: 包括"同时"访问 和 互斥共享

• 虚拟: 利用多道程序设计技术,让每个用户都觉得有一个计算机专门为他服务

• 异步: 程序的执行不是一贯到底的,而是走走停停,向前推进的速度不可预知. 但只要运行环境相同,OS 需要保证程序运行结果也要相同

• 汇编语言是和硬件绑定的,C 语言可以使用编译工具编译成能在不同硬件上运行的可执行程序

• 操作系统的启动:
  当我们按下电源后会有POST(加电自检)来寻找显卡和执行 BIOS(基本 I/O系统) 去检测外设,来加载相应的应用程序,当这些检查完毕就会执行Bootloader来加载 OS. OS(操作系统)是存放在 DISK(硬盘)上的, 此外 DISK 上还有一个 Bootloader用来加载 OS, 将我们OS 加载到内存中去,然后让我们的 CPU 可以执行操作系统. Bootloader 一般放在我们硬盘的第一个主引导扇区.

• 系统调用: 应用程序主动向操作系统发出服务请求

• 异常: 应用程序执行过程中出现的一些意想不到的事情(比如非法指令或者其他坏的处理状态,如内存出错),由操作系统来完成

• 中断: 来自不同的硬件设备(外设)的计时器和网络的中断

• 处理时间：
  系统调用既有同步也有异步； 异常是同步的；中断一般是异步的

越靠近CPU访问速度越快
CPU ---> 寄存器 ---> 缓存1 ---> 缓存2 ---> 主存 ---> 硬盘

• 地址空间& 地址生成

• 地址空间定义
  物理地址空间： 硬件支持的地址空间，起始地址0到Max
  逻辑地址空间： 一个运行的程序所拥有的内存范围

• 地址生成:
  CPU里面有一块专门管理内存的单元叫MMU
  MMU 内存管理单元： 将逻辑地址映射到物理地址上

• 地址安全检查:
  操作系统需要确保应用程序访问内存的操作属于该应用程序的，根据分配给应用程序的起始地址和长度来判断,如果不满足,CPU就会产生一个内存访问异常,来让操作系统处理

内存分配

连续内存分配

• 当一个程序准许运行在内存中时,分配一个连续的区间给运行的程序以访问数据

内存碎片问题

• 空闲内存不能被利用
• 外部碎片: 在分配单元间的未使用内存
• 内部碎片: 在分配单元中的未使用内存

分区的动态分配策略

• 首次适配:
• 最优适配:
• 最差适配:

压缩式碎片整理

交换式碎片整理

非连续内存分配

硬件解决方案

• 分段

• 分页

  
  
  

• 页面置换算法
  FIFO（First in First out）
  LRU（The Least Recently Used）
  LFU（The Least Frequently Used）

---

进程

• 进程: 一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程, 一个进程应该包括:

1. 程序的代码
   2.程序处理的数据
   3.程序计数器中的值,指示下一条将运行的指令
   4.一组通用的寄存器的当前值, 堆,栈
2. 一组系统资源(如打开的文件, 网络资源)
   总之,进程包含了正在运行的一个程序的所有状态信息

进程与程序的联系

1. 程序是产生进程的基础
2. 程序的每次运行构成不同的进程
   3.进程是程序功能的体现
3. 通过多次执行,一个程序可对应多个进程; 通过调用关系,一个进程可以包括多个程序

进程与程序的区别

1. 进程是动态的,程序是静态的: 程序是有序代码的集合; 进程是程序的执行,进程有核心态/用户态
2. 进程是暂时的,程序是永久的: 进程是一个状态变化的过程,程序可以长久保存
3. 进程与程序的组成不同: 进程的组成包括程、数据和进程控制块(即进程状态信息)

进程的特点:

1. 动态性: 可动态地创建,结束进程
2. 并发性: 进程可以被独立调度并占用处理机运行
3. 独立性: 不同进程的工作不相互影响
4. 制约性: 因访问共享数据/资源或进程间同步而产生制约

并发: 指的是一段时间内有多个程序在执行
并行: 指的是在某一时刻有多个程序在执行(需要有多个 CPU)

进程控制结构

• 进程控制块: 操作系统管理控制进程运行所用的信息集合.操作系统用 PCB(Process Control Block)来描述进程的基本情况以及运行变化的过程,PCB 是进程存在的唯一标志

PCB 含有以下三大类信息:

• 进程标识信息. 如本进程的标识,本进程的产生者标识(父进程标识); 用户标识
• 处理机状态信息保存区. 保存进程的运行现场信息:

1. 用户可见寄存器, 用户程序可以使用的数据,地址等寄存器.
2. 控制和状态寄存器, 如程序计数器(PC), 程序状态字(PSW)
3. 栈指针, 过程调用/系统调用/中断处理和返回时需要用到它

• 进程控制信息

1. 调度和状态信息,用于操作系统调度进程并占用处理机使用.
2. 进程间通信信息, 为支持进程间的与通信相关的各种标识,信号,信件等,这些信息存放在接收方的进程控制块中
3. 存储管理信息,包含有指向本进程映像存储空间的数据结构
4. 进程所用资源,说明右进程打开,使用的系统资源,如打开的文件等
5. 有关数据结构连接信息, 进程可以连接到一个进程队列中,或连接到相关的其他进程的 PCB

PCB 的组织方式

• 链表: 同一状态的进程其 PCB 成一链表,多个状态对应多个不同的链表,各状态的进程形成不同的链表: 就绪链表,阻塞链表
• 索引表: 同一状态的进程归入一个 index 表(由 index 指向 PCB),多个状态对应多个不同的 index 表, 各状态的进行形成不同的索引表: 就绪索引表,阻塞索引表

进程管理

进程状态

• 进程的生命期管理:

1. 进程创建: 引起进程创建的 3 个主要事件:

2. 系统初始化时:

3. 用户请求创建一个新进程

4. 正在运行的进程执行了创建进程的系统调用

5. 进程运行: 内核选择一个就绪的进程,让它占处理机并执行

6. 进程等待:
   在以下情况,进程等待(阻塞)

7. 请求并等待系统服务,无法马上完成

8. 启动某种操作,无法马上完成

9. 需要的数据没有到达
   进程只能自己阻塞自己,因为只有进程自身才能知道何时需要等待某种事件的发生

10. 进程唤醒:
    唤醒进程的原因

11. 被阻塞进程需要的资源可被满足

12. 被阻塞进程等待的事件到达

13. 将该进程的 PCB 插入到就绪队列
    进程只能被别的进程或操作系统唤醒

14. 进程结束
    以下四种情况下,进程结束

15. 正常退出(自愿的)

16. 错误退出(自愿的)

17. 致命错误(强制性的)

18. 被其他进程所杀(强制性的)

• 进程状态变化模型

• 进程挂起模型

  
  

线程管理

• 自从 60 年代提出进程概念以来,在操作系统中一直都是以进程作为独立运行的基本单元,知道 80 年代中期,人们又提出了更小的能独立运行的基本单元--线程

• 线程是进程当中的一条执行流程,

  
  

上下文切换

调度

同步

硬件解决办法

• 禁用中断: 没有中断,就没有上下文切换,因此没有并发. 硬件将中断处理延迟到中断被启用之后, 大多数现代计算机体系结构都提供指令来完成. 在进入临界区的时候,禁用中断; 离开临界区的时候,开启中断.
• 缺点: 一旦中断被禁用,线程就无法被停止, 整个系统都会为你停下来,可能导致其他线程处于饥饿状态. 如果临界区很长,对系统的影响会很大,所以只能适用于临界区很小的情况. 同时屏蔽中断在多 CPU 的情况下也无法解决互斥的问题,因为只能禁用当前 CPU 的中断, 而其他 CPU 还是可以访问临界区的

软件解决办法

• 软件解决方法的缺点:

1. 复杂, 需要两个进程间的共享数据项
2. 需要忙等,浪费 CPU 时间
3. 没有硬件保证的情况下无真正的软件解决方案

基于硬件原子操作指令的软件解决方案

• 硬件通常只要提供以下两种方式的任意一种,就可以很简单的实现临界区的进入和退出操作

1. Test-and-Set: 首先从内存中读取值, 然后测试该值是否为 1(返回真或假),然后将内存值设置为 1

boolean TestAndSet(boolean *target) {
  boolean rv = *target;
  *target = TRUE;
  return rv;
}

2. Exchange: 交换内存中的两个值

void Exchange(boolean *a, boolean *b) {
  boolean temp = *a;
  *a = *b;
  *b = temp;
}

• 虽然上面两个指令是有三个步骤组成,但是它们已经被封装成一条机器指令,也就意味着在执行这三个步骤的时候,不允许被外界打断(不会有中断,上下文切换的情况)

• 使用 Test-And-Set 实现

  
  
• 上面实现有个问题,就是while 循环是一个忙等,会消耗 CPU 周期

• 使用 Exchange 实现

  
  

• 使用原子操作机器指令的优点:

1. 适用于单处理器或者共享主存的多处理器中任意数量的进程
2. 简单并且容易证明
   3.可以用于支持多临界区

• 缺点:

1. 忙等消耗处理器时间
2. 当进程离开临界区并且多个进程在等待的时候可能导致饥饿
3. 死锁: 如果一个底优先级的进程拥有临界区并且一个高优先级进程也需求,那么高优先级进程会获得处理器并等待临界区, 导致低优先级的线程得不到资源去释放锁

---

信号量

信号量解决的问题:

• 并发问题: 竞争条件(竞态条件), 多程序并发执行时存在的大问题
• 同步: 多线程共享公共谁的协调执行, 包括互斥与条件同步
  互斥: 在同一时间只有一个线程可以执行临界区
• 确保同步正确很难的问题, 需要高层次的编程对象(锁), 和底层硬件支持编译

PV 操作

• P: Prolaag(荷兰语尝试减少), P() 操作可以被阻塞,当资源不够用时会阻塞当前线程
• V: Verhoog(荷兰语增加), V() 操作不会阻塞, 会释放资源, 通知等待这个信号量的线程唤醒

信号量

• 信号量是一个被保护的整数变量, 初始化完成后,唯一改变一个信号量的值的办法是通过 P() 和 V() 操作来进行, 并且操作必须是原子的

信号量使用

Class BoundedBuffer {
  mutex = new Semaphore(1); // 设置一个队 buffer 操作的信号
  fullBuffers = new Semaphore(0); // 向 buffer 中添加元素的信号, 假定 buffer 中是满的
  emptyBuffers = new Semaphore(n); // 从 buffer 中取出元素的信号, 假定 buffer 中可以存 n 个元素
}

BoundedBuffer:: Deposit(c) { // 对 buffer 进行存的操作, 相当于生产者
  emptyBuffers -> P(); // 首先判断对 emptyBuffers 进行P 操作,如果 n > 1 ,那么 n - 1 ,继续向下执行, 如果不考虑移除,理论上要执行第 n  次 P 操作 buffer 中元素才被添加满, 在执行第 n+1次P 操作的时候会睡眠
  mutex -> P(); // 向 buffer 中添加元素, 要先对 mutex 做 P操作,判断是否可以对 buffer 进行操作,如果 mutex 值为 1,说明没有其他线程在访问 buffer, 此时可以对 buffer 进行操作, 如果 mutex 为 0 ,说明别的线程在访问 buffer, 那么此时不能对 buffer 进行操作,需要等别的线程将 mutex 置为 1 的时候才可以访问
  Add c to the buffer; // 向 buffer 中添加一个元素
  mutex -> V(); // 添加完元素, 将 mutex 置为 1, 此时别的线程可以访问 buffer 了
  fullBuffers -> V(); // 向 buffer 中添加完元素后,需要将 fullBuffers 值加 1, 这样才能保证别的线程可以从 buffer 中取到元素,
}

BoundedBuffer:: Remove(c) { // 从 buffer 中取元素的操作, 相当于消费者
  fullBuffers -> P(); // 首先判断 buffer 中是否还有元素
  mutex -> P(); // 判断是否可以操作 buffer 
  Remove c from buffer; // 从 buffer 中移除一个元素
  mutex -> V(); // 操作完 buffer ,释放 buffer
  emptyBuffers -> V(); // 取出一个元素后, 对 buffer 中还可存放元素的数量+1
}

信号量的实现

class Semaphore {
  int sem;
  WaitQueue q;
}

Semaphore:: P() {
  sem--; // 首先信号量减一
  if (sem < 0) { // 如果信号量 小于 0
    Add this thread t to q; // 把当前的线程放到等待队列中去,
    block(t); // 同时线程自身睡眠
  }
}

Semaphore:: V() {
  sem++; // 首先信号量加一
  if (sem<= 0) { // 因为先 sem++了,所有当 sem = 0 的时候说明之前已经是-1了,所以如果信号量小于等于 0 说明之前已经有线程在等待了
    Remove a thread t form q; // 从等待队列中取出一个线程, 一般是 FIFO 的规则
    wakeup(t); // 唤醒该线程
  }
}

管程(Monitor)

• 管程是操作系统中一种用于实现进程同步和互斥的高层抽象机制。它通过封装共享数据和对这些数据的操作，提供了一种简单而安全的方式来管理对共享资源的访问。

管程实现

class Condition {
  int numWaiting = 0;
  WaitQueue q;
}

Condition:: Wait(lock) {
  numWaiting++;
  Add this thread t to q;
  release(lock); // 睡眠之前先把锁释放掉,要不然别的线程一直得不到锁
  schedule(); // need mutex
  require(lock); // 被唤醒之后需要再将获得锁
}

Condition:: Signal() {
  if(numWating > 0) {
    Remove a thread t from q;
    wakeup(t); // need mutex
    numWating--;
  }
}

class BoundedBuffer {
  Lock lock;
  int count = 0 ;
  Condition notFull, notEmpty;
}
BoundedBuffer:: Deposit(c){
  lock->Acquire(); // 进来先加锁,保证只有一个线程在操作管程
  while(count == n) notFull.Wait(&lock); // 当 buffer 中满了的时候,需要进入睡眠等待 notFull signal 唤醒
  Add c to the buffer; 
  count++;
  notEmpty.Signal(); // buffet 中添加元素成功, 唤醒等待remove 的线程
  lock->Release(); // 释放锁资源
}
BoundedBuffer:: Remove(c){
  lock->Acquire(); // 保证只有一个线程操作管程
  while(count == 0) notEmpty.Wait(&lock); // 当 buffer 中没有元素时, notEmpty 进入休眠,等待 notEmpty Signal 的唤醒
  Remove c from buffer;
  coount--;
  notFull.Signal(); // buffer 中移除元素成功,唤醒等待 deposit 的线程
  lock->Release(); // 释放锁资源
}

经典同步问题

生产消费者问题

读者写者问题

• 读者: 只读取数据,不执行任何更新
• 写者: 可以读取和写入数据

使用信号量实现多读单写

• 共享数据包括 信号量 CountMutex 初始化为 1, 信号量 WriteMutex 初始化为 1, 整数 Rcount 初始化为 0
• Writer实现

sem_wait(WriteMutex); // 相当于 P 操作
write;
sem_post(WriteMutex); // 相当与 V 操作

• Reader 实现

sem_wait(CountMutex); // 对 Rcount 的操作用互斥包起来做保护
if(Rcount == 0) 
  sem_wait(WriteMutex); // Rcount = 0 说明当前没有读者, 此时对 WriteMutex做一个 P 操作; 如果 Rcount != 0,说明当前已经有线程在执行 Reader 操作,当在执行 Reader 操作的时候,Writer 一定是进不来的,
++Rcount;  // 对 Rcount +1
sem_post(CountMutex);
read;
sem_wait(CountMutex); // 对 Rcount 的操作用互斥包起来做保护
--Rcount; // 执行完read 将Rcount -1
if(Rcount == 0) 
  sem_post(WriteMutex); // 当 Rcount = 0 时,说明所有的 read 都已经结束了,那么做一个 V 操作,使有可能等待 Write 的线程被唤醒
sem_post(CountMutex);

使用管程实现多读单写

---

死锁

死锁特征

• 如果下面四个条件同时成立死锁可能出现

1. 互斥: 在一个时间只能有一个进程使用资源
2. 持有并等待: 进程保持至少一个资源在等待获取其他进程持有的额外资源
3. 无抢占: 一个资源只能被进程自愿释放,进程已经完成了它的任务之后
4. 循环等待: 存在等待进程集合{P0,P1...,PN}, P0 正在等待 P1 所占用的资源,P1 正在等待 P2 所占用的资源,..., PN-1 在等待 PN 所占用资源,PN 正在等待 P0 所占用的资源

• 死锁预防
• 死锁检测
• 死锁解决

---

IPC - 进程间通信

---

文件系统

• 操作系统读取文件是按照扇区来读的,每次把一整个扇区读到内存中取, 就算是读一个字节的内容,也是要把这个字节对应的扇区读取到内存中