总结(三) 操作系统
模块一：硬件
1，存储分层
越上面速度越快。
L1,L2 Cache是CPU私有的。L3是多个CPU共用的。
CPU
CPU缓存一致性问题
要解决这个问题，需要保证两点
- 写传播：每一条写进cache的，要传给所有CPU的cache。
- 事务的串行化：某个CPU对数据操作，应该在其他CPU看来是有序的。
写传播的实现用的是总线嗅探。
事务的串行化实现用的是MESI，它是基于总线嗅探实现的。
模块二：内存管理
如果程序直接引用物理地址，可能导致内存只能使用一个程序。因为其他程序也运行的话，可能会直接占用前一个程序的物理地址。
这时候我们就需要一个虚拟内存的机制，再分配到物理地址里。
虚拟内存地址和物理内存地址。
虚拟内存的实现主要有两种方式：内存分段和内存分页。
内存分段
通过段表和物理内存地址进行映射。
段表结构
该段的物理地址 = 短号对应的基地址+偏移量。如果偏移量超过段长，则越界中断。
问题
内存碎片问题和内存交换效率低的问题。
出现碎片问题
很多个程序同时运行，这时候中间一个小程序内存可能被释放，那么就会出现碎片问题。
碎片问题分两种
- 内部碎片问题：一个程序内很多占用内存的部分不咋用，浪费。
- 外部碎片问题：释放后出现多个不连续的物理小内存。
解决内部碎片问题
使用内存交换的方法。
将占用的内存读到磁盘去，再从磁盘读回来，但是位置和以前不同了，这样能解决碎片问题。
因为磁盘效率慢，如果读到磁盘的是很大的程序，就会效率非常差。
内存分页
为了解决分段的两个缺点（碎片问题和内存交换效率低）。
实现：将虚拟内存和实际内存分割成一小片，这片称为页。Linux中页的大小是4k。
再把页表和物理内存映射起来。
页表存在内存里，MMU则进行虚拟地址和物理地址转换的操作。
缺页异常：当进程在页表查询虚拟内存，找不到的时候，就会发生缺页异常。然后就分重新分配页表，最后进程恢复运行。
如何解决碎片问题和内存交换效率低的问题？
碎片问题：
因为是通过映射页的方式，所以不会出现进程无法使用的内存块，每个释放的页都能被重新使用。
内存交换：
遇到不常使用的内存空间时，不需要像分段一样传递整个程序的占用内存，只需要传递几个页到磁盘，这样效率就很高。
页表如何实现
页表内有虚拟页号和物理页号(对应的块号)。
转换到物理地址的过程：
- 将虚拟地址转换成页号和页内偏移量
- 拿着页号去页表查询物理页号
- 物理页号加偏移量就是物理地址
缺点
1，简单分页的情况下，因为操作系统运行的进程很大，那么就意味着页表占用内存也特别大，很浪费。
进步
因为简单页表出现的占用大问题，所以引入了多级页表。
多级页表：
一级页表和简单页表一样，然后通过对页表的分页，建立出二级页表。
虽然这样比一级页表占用更多了，但是可以通过二级页表直接映射，也就是说，一级页表可以置换到磁盘里了。
再继续分页，就出现多级页表。
段页式内存管理
分段和分页不是分开的功能，我们可以把他们合并起来一起使用。
实现方式：
- 先把程序划分成有逻辑意义的段。
- 再将每个段划分成页，也就是对分段划分出的连续空间，划分成固定大小的页。
通过这种方式，就可以将表划分为 段号，段内页号，页内位移。
每个程序拥有一个段表，然后每个段拥有一张页表。
这样提高了CPU利用率。
Linux内存管理
主要采用分页内存管理，但是也有用上分段机制。
模块三：进程与线程
进程
1，并行与并发
2，进程的基本状态
- 运行状态
- 阻塞状态
- 就绪状态
- 创建状态
- 结束状态
3，进程的其他状态
因为有时候等太久，很浪费内存，得放入磁盘，调用时再掉到内存里，这种叫挂起。
所以又有两个状态
就绪挂起状态和阻塞挂起状态
4，如何挂起？
- CPU自行调度
- sleep方法
- Ctrl - Z （linux）
进程的控制结构 - PCB
1，操作系统靠控制PCB/进程控制块来控制进程。
2，PCB是进程存在的唯一标识，进程如果存在一定存在PCB，进程被释放PCB也被释放。
3，PCB包含信息
不太重要/记不住
4，PCB如何组织
- 通过链表组织成队列。如阻塞队列，就绪队列。
- 还有索引的方式组织。
一般选用链表，因为抢占式调度，链接比较容易插入和删除。
进程的控制
通过PCB进程控制。
1，创建进程：
- 先分配一个进程标识号，再分配一个空白的PCB。
- 给进程分配内存空间。
- 初始化PCB
- 插入队列中。
2，终止进程
- 找到该进程的PCB。
- 如果执行，终止执行。
- 如果有子进程，终止子进程。
- 释放资源。
- 清楚PCB。
3，阻塞状态/唤醒状态
- 找到PCB
- 修改PCB中的状态
- 插入队列。
进程的上下文切换
一个进程还没执行完，切换到下一个进程。
1，过程：
把交换的信息保存在进程的PCB中，然后切换到下一个进程，下次再通过PCB恢复。
进程的调度
1，先来先服务调度算法
2，时间片轮转调度算法
3，高响应比优先调度算法
4，最短作业优先调度算法
5，最高优先级调度算法
6，多级反馈队列调度算法
线程
1，为什么用线程？
- 进程间通信开销大
- 进程各种状态，上下文切换开销大
2，线程是进程的一条执行流程。
3，线程的优点
- 共享资源和地址
- 并发执行
- 一个进程有多个线程
4，线程和进程的区别
- 进程是资源分配的单位，线程是CPU调度的单位。（最大差别）
- 进程有完整的资源平台，线程只占用必要的资源，如寄存器和栈。
- 线程有三种基本状态，执行，阻塞，就绪。
- 线程启动和终止时间和占用资源都比进程少。
- 线程崩了，所在进程也会崩溃。但是进程间互不影响。
- 同一进程的线程共享同样的资源，就不用经过内核，速度快还减小开销。
- 线程的上下文切换速度比进程快。
5，线程的上下文切换
- 同一进程的话，虚拟内存不变，只需要切换线程的私有数据，寄存器和栈啥的就行。
- 不同进程的话，和进程上下文切换一样。
6，线程的实现
有三种线程和其对应的实现方式：
- 用户线程：用户实现的线程
- 内核线程：内核中实现的线程
- 轻量级进程：
进程的通信
- 管道
1，存在内核中的缓存，一端存进去，另外一端读出来缓存。
分为两种
匿名管道和命名管道。
匿名管道：只能在父子进程之间使用。
命名管道：可以在不同进程使用，匿名管道的功能同样可以。
缺点：管道不适合频繁交换信息的情况。
- 消息队列
类似邮箱，通信时一方进程将信息交给消息队列，另外一方需要的时候取出来就好。
消息队列是保存在内核的链表。
缺点：通信不及时，信息大小限制。
- 共享内存
拿出一块虚拟内存，映射到相同的物理地址。
缺点：并发问题。
- 信号量
为了防止共享内存出现的竞争问题，推出机制信号量。
信号量用来表示资源的互斥与同步。
P操作和V操作
信号量=0同步，=1互斥。
- 信号
上面都是常用情况下，这是对异常情况下。
比如人为强制。
- Socket
上面都是同主机进程，socket可以跨主机跨网络通信。当然同主机也可以。
多线程同步
呃。
死锁
两个进程竞争资源，每个进程都拿了一部分又不释放，就会出现死锁问题。
死锁四个条件
- 互斥条件：多个线程不能用同一份资源。
- 持有并等待条件：持有了一份资源，等待另外一份资源
- 不可剥夺条件：使用前不可以被剥夺。
- 环路等待条件：获取资源的顺序行成环。比如说A获得了1资源，等待2资源，这时候2获得2资源，等待1资源。
破坏死锁
只要破坏其他一个条件就可以。
所以常用的方法：使用资源有序分配法，破坏环路等待。
乐观锁和悲观锁
- 基础锁
互斥锁和自旋锁
区别：
互斥锁：没获取锁的时候，进程会释放CPU。但是会从用户态变成内核态（阻塞），也增大了内核开销。
自旋锁：没获取锁的时候，进程会忙等待(自旋)，一直占用CPU。
所以如果能确定锁的时间很短，则应该使用互斥锁，不是自旋锁。
- 读锁和写锁和其优先级
原理：当写锁没被持有的时候，则多个进程可以并发持有读锁。
当写锁被持有时，持有读锁的线程会被阻塞，获取读锁的操作也被阻塞。
所以读写锁，用于读多写少的环境下。
- 读优先锁和写优先锁
根据情况的不同，可以分成这两种锁。
读优先锁：当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候，会被阻塞，并且在阻塞过程中，后续来的读线程 C 仍然可以成功获取读锁，最后直到读线程 A 和 C 释放读锁后，写线程 B 才可以成功获取写锁。
写优先锁：当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候，会被阻塞，并且在阻塞过程中，后续来的读线程 C 获取读锁时会失败，于是读线程 C 将被阻塞在获取读锁的操作，这样只要读线程 A 释放读锁后，写线程 B 就可以成功获取读锁。
不管是哪一种锁，都会出现线程饥饿问题。所以还有一种，公平读写锁。
谁先获得谁拿锁，另外一种阻塞。
乐观锁和悲观锁
思想。
悲观锁：互斥锁。
乐观锁：先修改共享数据，然后检查是否冲突，如果有线程修改了就放弃这次操作。
协程
轻量级线程。
由用户自由调度（yield）。线程是由CPU调度上下文切换，协程是全部由用户来操作。
线程同步的方式
模块四：调度算法
分为三大类：进程调度，页面调度，磁盘调度。
