总结

第一章

进程的状态转换和进程的管理

第二章

线程

处理机的调度

调度算法

第三章

进程互斥和进程同步

进程互斥的软件实现

进程互斥的硬件实现

信号量

cpu 管理的直观想法

1. io 指令消耗的时间远远大于普通的计算
2. 如何避免io 消耗？
   就只有通过并发的执行的方式

多进程如何组织？

进程的状态

新建态直接就是就绪态

终止态只能由运行态转换

在新建态的时候，系统会为其创建pcb 和相关的资源，只有所有的都初始化结束了，新建态 转变为了 就绪态

从运行态 -> 阻塞态

当应用程序需要资源，一直等待，就会变成阻塞态

或者可以说一直等待某一个事件发生

阻塞态 -> 就绪态

对应的时间发生了，就会从阻塞态 -> 就绪态

这些状态都在pcb 中进行描述

进程组织

链式方式

大多数操作系统选择

索引方式

通过一个索引表进行索引

进程控制

由于要保证进程切换的统一性，所以需要利用操作系统的原语进行操作

原语

原语的执行具有原子性，即执行过程只能一气呵成，期间不允许被中断。
可以用“关中断指令”和“开中断指令”这两个特权指令实现原子性

如何防止被用户直接调用，开中断和关中断指令呢？

由于这个原语是内核指令，用户没有权限调用

进程控制所需要的原语

进程创建

作业调度，中的作业是没有放入内存的应用或者是程序，所以作业调度就是将一个没有运行的放入到内存当中运行起来

撤销进程

阻塞进程

切换进程

进程之间通信方式

共享存储

基于存储区的共享：操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。这种共享方式速度很快，是一种高级通信方式。

基于数据结构的共享：比如共享空间里只能放个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式

每一个进程都有自己的进程空间

每一个进程无法访问别人的地址空间

所以当出现需要进程通信的时候，就可以选择共享存储区

那如何防止多个进程同时操作同一个共享存储区呢？

各个进程可使用操作系统内核提供的同步互斥工具（如P、V操作）

消息传递

进程间的数据交换以格式化的消息(Message)为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。

消息体就是一个进程给另一个进程所发送的消息

直接通信和间接通信

直接通信

本质上，就是需要点名到姓的方式

当进程P 使用发送原语之后，该消息就会被复制到内核中进程Q 的消息队列中

当进程Q 使用了接受原语，就会遍历进程Q 的消息队列，然后找进程P 发送的消息receive(P,&msg)

间接通信

管道通信

只有单向的管道，只能是单向的

本质上来说管道也是内存中的一块地址

可以说是一个循环队列

1. 管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
2. 各进程要互斥地访问管道（由操作系统实现）
3. 当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。
4. 当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程。
5. 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案：①一个管道允许多个写进程，一个读进程(2014年408真题高教社官方答案)；②允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据(Liux的方案)。

线程的属性

线程的实现方式

用户级线程

简介

每一个线程可以理解为一段代码逻辑，然后这一段代码逻辑可以抽象成，一个if

比如

1
2
3
4
5
6
7
8
9
10

int main(){
  int i=0;
  while(true){
    if(i==1){....}   // 处理第一个任务
    if(i==2){....}	 // 处理第二个任务
    if(i==3){....}	 // 处理第三个任务
    i=(i+1)%3;
  }
  
}

由于计算机执行while 会非常的快，所以可以抽象的看成三个任务是并发的

但是这个是认为的抽象出来的线程，在内核看来，还是一个进程

所以这个叫用户级线程

特点

1. 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换)
2. 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。
3. 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。“用户级线程”就是“从用户视角看能看到的线程

优缺点

优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高

缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

内核级线程

多线程模型

一对一

也就是说，有多少个用户级线程就会有多少个内核级线程

优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。

缺点：一个用户进程会占用多个内核级线程线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大

多对一

这种方式就类似于使用线程库创建的用户级线程

多对一模型：多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。

优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高

缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行

多对多

多对多模型：n用户及线程映射到m个内核级线程(n>=m)。每个用户进程对应m个内核级线程克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞)，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点

克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞)，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点

线程的转换

和进程的逻辑基本一致

进程的组织与控制

TCB

线程表

每一个TCB 就可以代表一个线程

进程拥有一个TCB 也就是线程表，通过线程表中的TCB 就可以管理线程

调度的三个层次

高级调度

又称为作业调度

高级调度（作业调度）。按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB,调出时才撤销PCB

低级调度

又称为，进程调度或者是处理机调度

中级调度

举一个简单的例子

当像使用某一个长期没有使用的软件，进入软件的时候会出现一点卡顿

这个是因为，由于没有使用，对应的数据都存放在了外存，当你再次使用的时候，就需要从外存重新加载到内存

挂起状态（7状态模型）

五状态模型

七状态模型

暂时调到外存等待的进程状态为挂起状态（挂起态，suspend)挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态

挂起就是存放在了外存

从创建态，如果创建的时候没有内存，那么就会直接放入到外存，也就是就绪挂起

同样的就绪态的，遇到了内存不足，也会直接放入就绪挂起

总结的来说，很多放入外存的原因都是由于没有内存了

挂起和阻塞的区别

注意“挂起”和“阻塞”的区别，两种状态都是暂时不能获得CPU的服务，但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。

进程调度的时机

临界资源和临界区

进程调度的方式

注意非剥夺调度方式=非抢占式 只允许主动放弃处理机

调度时机

1. 创建新进程进程

2. 退出运行

   需要调度程序判断是否创建新的程序

3. 进程阻塞I/O

   调度程序切换进程

4. 中断发生（可能唤醒某些阻塞进程）

调度对象

1. 在不支持内核线程的系统中

   调度对象是进程

2. 支持内核线程的系统中

   调度对象是内核级线程

调度算法

先来先服务

短作业优先

1. 非抢占式

   

   意思就是说，新提交的任务，不会抢占，等正在运行的进程，运行完了之后才会进行重新排序

2. 抢占式

   也叫最短剩余时间

   每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度

   

高响应比优先算法

时间片轮转

如果时间片太大的话，那么就喝先来先服务一样了

优先级调度

同样的分为抢占式和非抢占式

多级反馈队列

注意当新来的就会发生抢占，被抢占的就会被放回原队列，而不是放入下一级队列

进程同步

进程互斥

进程互斥的基本的原则

1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
2. 忙则等待。当己有进程进入临界区时，其他试图进入临界区的进程必须等待：
3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

软件实现方法

单标识法

远离上，就是将自己的临界区的控制权进行谦让

双标志先法

问题：

如果是并发的运行两个，那么就会有问题

两个进程会同时的检测对方是否有意愿使用，但是这个时候，两个flag都是false 所以都会进入

但是可以结合前面的调度来看

如果当进入到临界区的一个进程被调度了，另一个进程也可以使用临界区，那么临界区的访问就会发生冲突

若按照①⑤②⑥③⑦..的顺序执行，P0和P1将会同时访问临界区。
因此，双标志先检查法的主要问题是：违反“忙则等待”原则。
原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发
生进程切换。

双标志后检查法

为什么会违背了“空闲让进”和“有限等待”

当并发执行两个进程的时候，会发现两个flag 都会被设置成true

进入while 两个进程都会发现对方有使用的意愿

空闲让进，是因为，这个时候都是空闲的，但是资源却无法使用

有限等待是因为两个都会一直检测到对方有意愿进行使用所以会出现永久等待

peterson

Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

不满足让权等待的原因是：因为无法使用临界区应该被剥夺处理剂，但是这个算法是while 一直等待

硬件实现方法

中断屏蔽


TestAndSet

swap

锁

互斥锁

信号量机制

整形信号量

记录型信号量

信号量的运用

信号量实现进程互斥

信号量实现进程同步

可以理解为一个资源

代码4 在代码2 之后运行，那么代码2 之后将资源的数量++ 之后代码4的p 操作就不会被阻塞

信号量实现前驱关系

可以总结为前v 后p

典型问题

生产者和消费者

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者
进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）
生产者、消费者共享一个初始为空、大小为的缓冲区。
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。
缓冲区是临界资源，各进程必须互斥地访问。

一般的代码实现应该是如下的样子

注意的是，实现互斥的应该是在同一个进程中，实现同步的应该在两个进程中

p 操作会让资源–

v 操作会让资源++

而且需要注意，实现的互斥的p 操作一定要在实现同步的p 操作之后

多生产者和多消费者

所以在这个条件下，我们可以发现，只要盘子（临界资源）的数量是1，我们就可以不用加锁的访问，具体问题，具体的解决

管程

产生的原因

管程的定义

管程的设计方式很像是类的设计

死锁

死锁，饥饿，死循环的概念

死锁产生的条件

预防死锁

避免死锁

安全序列、不安全状态、死锁的联系

银行家算法

第一种计算方式

逐个比较计算

比如剩余的有（3，3，2）

我们可以从头开始逐个比较，然后计算出结果

第二种计算方式

从剩余的出发，可以发现还有（3，3，2）

这个时候可以发现，p1,p3 都是满足的，那么将这两个都添加到安全序列之后变成的（7，4，3）这个数字是通过已分配归还的

检测和解除死锁