望尘可及的秘密基地

2.3 同步与互斥

基本概念

临界资源，同步，互斥

实现互斥

略，软件方式和硬件方式

互斥锁&信号量

互斥锁：原子操作acquire(), release()；需要忙等待

信号量类型：整型信号量，记录型信号量

整型信号量：wait(), signal()；wait当信号量大于0后信号量减一，signal信号量加一

记录型信号量：wait信号量减一并将自己的进程加进等待队列，状态设置为block，signal信号量加一，当信号量大于0后从等待队列释放一个进程并唤醒该进程。

信号量实现同步与互斥

管程

略

经典同步问题

1. 生产者-消费者问题

要求：生产者和消费者共享一个缓存区，生产者在没满时生成，消费者在没空时消费

三个信号量：mutex，full，empty

先P(empty)或P(full)，再P(mutex)——可能死锁

2. 读者-写者问题

要求：读可以同时；只能一个写；写操作未完成前不能读或写；执行写操作前无正在执行的读或写

（感觉就一句，除读读外，其他操作互斥）

3. 哲学家就餐问题

解决办法：同时拿两根筷子；动作规定

4. 吸烟者问题

问题描述：三个吸烟者和一个供应者。造烟需要三种材料，三个吸烟者各有一种。供应者每次拿出两种使得一个吸烟者能够吸烟。当其吸完了，供应者再拿出两种材料。

分析：供应者和吸烟者同步，吸烟者之间互斥

2.4 死锁

基本概念

死锁原因：资源竞争+顺序不当

产生条件：互斥+不可剥夺+请求且持有资源+循环等待

处理策略：预防or避免or检测并解除

死锁预防

破坏条件即可

1. 不互斥

对共享资源可行，对临界资源不可行

2. 可剥夺

有的资源可行，有的不可行（打印机）

3. 获得所有资源才执行

可能导致饿死

4. 向后申请资源

给资源编号，只能申请编号更大的资源。

麻烦

死锁避免

1. 判断安全状态

系统判断分配该资源后是否会导致死锁

2. 银行家算法

进程事先向系统声明所需最大资源数

最大需求矩阵，分配矩阵，需求矩阵

具体执行步骤略

死锁检测和解除

资源分配图：进程，资源，请求边，分配边

简化资源分配图后可检测系统是否死锁：略

解除：剥夺资源，撤销进程和进程回退（这俩有啥区别？）

2.1 进程与线程

基本概念

1.进程是什么？多种定义

比如进程是程序的一次执行过程，是系统进行资源分配和调度的一个独立单位

2.程序段，数据段和PCB构成了进程实体

3.PCB是进程的唯一标识

4.进程特征：动态性，并发性，独立性和异步性

进程的状态

运行态，就绪态，阻塞态，创建态和终止态

进程的组成

程序段，数据段和PCB

PCB有进程标识符(PID)，状态，优先级，上下文等等，链接成队列或者放在索引表中

进程控制

创建：分配PID，申请PCB———>分配资源———>初始化PCB———>插入就绪队列

终止：查找PCB———>终止子孙进程———>归还资源———>从所在队列中删除

阻塞：查找PCB———>保护现场，设置状态———>插入相应队列

唤醒：查找PCB———>移出队列，设置状态———>插入就绪队列

进程间通信

共享存储：数据结构，存储区

消息传递：signal()和slot()

管程：生产者消费者方式，单向

线程

基本概念

基本的CPU执行单元，只拥有必不可少的资源，调度代价小

可以创建和撤销另一个进程

状态

执行，就绪和阻塞

组成与控制

TCB线程控制块：线程标识符，寄存器，状态，优先级，堆栈等等。

同一进程中所有线程共享地址空间和全局变量，即各线程可读写其他线程的堆栈。

线程被终止后不立即释放资源，仍可被其他线程调用，以使被终止线程重新恢复运行

用户级线程

内核不知道线程的存在

线程切换不用转换到内核空间

进程间调度算法不同

一个阻塞所有阻塞（我感觉是一内核对多用户模型的问题）

内核级线程

阻塞可调度

调度代价小

但线程切换需转换到内核空间

多线程模型

一内核对多用户模型

一对一模型

多内核对多用户模型

（线程阻塞后能不能及时调度到底是看什么？）

2.2 处理机调度

基本概念

调度就是对CPU进行分配，从队列中选择一个进程执行，以实现并发

高级调度（创建进程），中级调度（内存调度，暂时挂起），低级调度（进程调度，上下CPU）

or长程调度，短程调度

调度的目标

CPU利用率，系统吞吐量，周转时间（完成时间-提交时间），等待时间，响应时间

调度的实现

进程是怎么调度的？

不能调度的情况：中断；临界区；原子操作

调度方式：非抢占式调度（进程不可“中断”），抢占式调度

无就绪进程，则执行闲逛进程（仅有CPU资源）

调度算法

先来先服务调度算法（FCFS）：适合CPU繁忙型

短作业优先调度算法（SJF）：可能饿死；未考虑优先级；平均等待时间和平均周转时间最少

优先级调度算法：非抢占型or抢占型，静态优先级or动态优先级

高响应比优先调度算法：${响应比=\frac{等待时间+要求服务时间}{要求服务时间}}$

时间片轮转调度算法（RR）

多级队列调度算法：不同队列不同调度算法

多级反馈队列调度算法：多个就绪队列，除最后一级为RR外都使用FCFS，若若未完成则降级

进程切换

上下文切换（计算密集型）（内核态中发生）：

挂起进程，保存上下文———>更新PCB———>将PCB移入相应队列———>

选择一个进程，更新其PCB———>恢复上下文———>执行

上下文切换和模式切换

什么调度算法适合分时系统和实时系统？

剑指offer 40——最小的k个数

1. 快速排序。
2. 部分快速排序，前k个排好就返回。
3. 位图，vector\ arr，arr[i]表示数字 i 的个数。

剑指offer 41——数据流中的中位数

1. 一个大顶堆和一个小顶堆正好表示出最中间的两个数，我们可以用优先队列（priority_queue）实现堆。
2. 有序队列，双指针指向最中间的两个数。

课程作业：

记录每天的任务

1. leetcode
2. theory
3. english

在目录下执行命令bundle exec jekyll serve，然后打开 http://localhost:4000 即可预览。

bundle exec jekyll serve 和 jekyll serve 的区别