前言
普通字体内容为查阅无误，斜体部分为个人理解
电脑端可以于左栏“文章目录”来索引到指定小节，手机端可以通过左上角按钮唤出菜单索引到指定小节
操作系统
定义
操作系统是指控制和管理整个计算机系统的硬件和软件资源，并合理的在组织调动计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境，操作系统也是计算机系统中最基本的系统软件
功能和目标
向上层提供方便易用的服务
操作系统需要实现对硬件机器的拓展
四大特征
并发，共享，虚拟，异步
其中，并发和共享是操作系统最基本的特征，两者互为存在条件
并发
并发是指两个或者多个事件在同一时间间隔内发生，这些事情是在宏观上同时发生的，但是在微观上是交替发生的
单核CPU只能同一时刻执行一个程序，各个程序只能并发执行
多核CPU可以同时执行多个程序，各个程序之间可以并行执行
共享
共享即资源共享，存在两种资源共享方式，分别是互斥共享方式和同时共享方式
互斥共享方式指在一个时间段只能允许一个进程访问该资源
同时共享方式指允许一个时间段内有多个进程“同时”进行访问
虚拟
虚拟指把一个物理上的实体变成若干个逻辑上的对应物，物理实体是存在的，逻辑上对应物是用户感受到的
虚拟技术有空分复用技术和时分复用技术
异步
异步特性是指在多个程序环境下，允许多个程序并发执行，但由于资源有限，无法将进程执行彻底，推进一部分后推进其他进程，最后推进完毕
发展进程
手工操作阶段
主要缺点在于用户独占全机，人机速度矛盾导致资源利用率低
单道批处理
引入脱机输入输出技术，由监督程序负责控制输入输出
监督程序是操作系统的雏形
优点在于缓解了一定的人机矛盾，提升了资源利用率
缺点在于内存中仅有一道程序运行，CPU有大量的时间等待I/O完成，资源利用率仍然很低
多道批处理
单道批处理演化而来
优点是多道程序并发执行，共享计算机资源，资源利用率大幅度提升，系统吞吐量增大
缺点是用户响应时间长，没有人机交互功能，无法在过程中调试程序或者在程序运行过程中输入参数
分时操作系统
分时操作系统以时间片为单位轮流为各个用户/作业服务，用户通过终端与计算机进行交互
优点是用户请求可以被即时响应，解决了人机交互问题
缺点是不能按照优先级进行任务
实时操作系统
优点是能够优先响应紧急任务
计算机系统接收到外部信号后及时进行处理，并在严格的时间内完成处理
主要特点是及时性和可靠性
还可细分为硬实时系统和软实时系统
硬实时系统必须在严格的规定时间内完成处理，软实时系统可以偶尔违反时间规定
网络操作系统
分布式操作系统
个人计算机操作系统
运行机制
指令
指令是处理器能识别执行的最基本命令
内核是操作系统的最重要的组成部分，也是最接近硬件的部分
指令分为特权指令和非特权指令
特权指令仅允许操作系统内核调用
CPU
CPU有两个状态，内核态和用户态
在内核态的时候可以执行特权指令
在用户态的时候可以执行非特权指令
内核态又称作管态，用户态又称为目态
开机时为内核态，再合适的时候操作系统会使用一条特权指令修改PSW的标志位来切换为用户态
在触发中断信号之后会让硬件自动变换到内核态，触发中断信号意味着操作系统强行夺回CPU的使用权
中断
中断是操作系统内核夺回CPU使用权的唯一途径
中断分为内中断和外中断
内中断和当前执行的指令有关，中断信号来自于CPU内部
外中断和当前执行的指令无关，中断信号来自于CPU外部
应用程序可以使用陷入指令来引发一个内中断信号从而请求操作系统内核的服务
而时钟中断属于一种外中断
基本原理
不同的中断信号需要用不同的中断处理程序来处理，当CPU检测到中断信号后会去查询中断向量表，从而来找到中断处理程序在内存中的存放位置
内中断的检测是CPU在执行指令检查是否有异常发生，外中断是在每个指令周期末尾，CPU检查是否有外中断需要处理
系统调用
对共享资源进行调用就必须向操作系统内核发出请求从而确保安全
调用过程是先传入参数，传入后执行陷入指令从而引发内中断
系统调用入口程序会根据传入的参数判断用户需要哪种系统调用服务
体系结构
操作系统内核可以分为大内核和微内核
大内核的优点是高性能，缺点是内部代码庞大，结构混乱，难以维护
微内核的优点是内核功能少，结构清晰方便维护，缺点是需要频繁的在核心态和用户态之间切换，性能低
分层结构的优点是便于调试和验证，扩充和维护，却跌势效率低，不可以跨层调用，系统执行时间长
模块化的优点是易于维护，支持动态加载新的内核模块，且任何模块都可以调用其他模块，无需采用消息传递进行通信，效率高，缺点是模块相互依赖，更难调试和验证，且模块之间的接口定义未必实用合理
外核优点是减少了虚拟硬件资源的映射器，提升了效率，缺点是降低了系统的一致性，使系统变得更加复杂
引导
CPU从一个特定的主存地址开始，取指令执行ROM中的引导程序（先进行硬件自检再开机）
将硬盘的第一块–主引导记录读入内存执行磁盘引导程序，扫描分区表
从活动分区读入分区引导记录执行其中的程序
从根目录下找到完整的操作系统初始化程序（启动管理器）并执行，完成后续开机工作
虚拟机（VMM）
定义
使用虚拟化技术，将一台物理机器虚拟化为多台虚拟机器，每个虚拟机器都可以独立运行一个操作系统
第一类虚拟机直接运行在硬件上，第二类虚拟机运行在宿主操作系统上
第一类性能更好，第二类可迁移性更好
进程
构成
一个进程实体（进程映像）由PCB，程序段，数据段组成，进程是动态的，进程实体是静态的
PCB
进程被创建时会分配一个唯一的不重复的PID
操作系统会记录PID和UID以及分配资源的运行情况，把这些信息存放在PCB当中，当进程被创建之后，操作系统就会为其创建一个PCB，在进程结束之后回收PCB
PCB是提供给操作系统使用的，程序段和数据段是进程自己使用的
PCB是进程存在的唯一标志，一个进程可能存在有多个·PCB
PCB中会有一个变量state来表示进程的状态
特征
- 动态性
- 并发性
- 独立性
- 异步性
- 结构性
状态与转换
进程有五大状态
- 运行状态
- 就绪状态
- 阻塞状态
- 创建状态
- 终止状态
就绪态 ->运行态 进程被调动
运行态 ->就绪态 时间片到或者处理机被抢占
运行态 ->阻塞态 进程的主动行为
阻塞态 -> 就绪态 被动行为
运行态和就绪态和阻塞态被称为三种基本状态
进程的组织–链接方式
执行指针指向当前处于运行态的进程
就绪队列指针指向当前处于就绪态的进程，通常会把优先级高的进程放在队头
进程的组织还有索引方式
多用链式方式
进程控制
进程控制就是要实现进程状态转换
进程控制使用原语实现
原语执行具有原子性，执行不可被中断
可以使用关中断指令和开中断指令这两个特权指令实现原子性
CPU执行了关中断指令之后就不再检查中断信号，直到开中断指令之后才会恢复检查
进程的创建使用创建原语
进程的终止使用撤销原语
进程的切换使用切换原语
阻塞和唤醒要成对出现
进程通信（IPC）
进程通信是指两个进程之间产生数据交互
各进程拥有的内存地址空间相互独立
一个进程无法直接访问其他进程的内存空间
进程可以向操作系统申请共享存储区，各个进程对共享空间的访问应该是互斥的，各个进程可使用操作系统内核提供的同步互斥工具（如P，V操作）
以上是基于存储区的共享
基于数据结构的共享速度慢限制多，是一种低级通信方式
基于存储区的共享是一种高级通信方式
消息传递
进程间的数据交换以格式化的消息为单位，利用发送消息/接收消息两个原语进行数据交换
格式化的消息包含了消息头和消息体
消息头包含发送进程id和接受进程的id，信息长度等格式化消息
消息传递方式分为直接和间接两种
直接通信
信箱通信可以多个进程向其中发送消息，也可以让多个进程从中接受消息
管道通信是在内存中开辟一个大小固定的内存缓冲区
拥有先进先出的特性
共享存储的通信方式不限制从什么地方读写
管道通信的读写是先进先出的
管道本质上是一个循环队列
管道只能采用半双工通信，某一时间段内只能实现单向的传输，要实现双向同时通信，需要设置两个管道
各进程要互斥的访问管道
管道写满时，写进程将阻塞，直到读进程将管道内的数据取走
当管道读空时，读进程将阻塞
管道内的数据被读出会彻底消失
当多个进程读同一个管道时，可能会错乱
通常有两个解决方案
一个管道允许多个写进程，一个读进程（考试标准答案）
允许多个写进程和多个读进程，但是系统会让各个读进程轮流从管道中读数据（Linux的方案）
只要管道没空，读进程就可以从管道读数据
只要管道没满，写进程就可以往管道写数据
线程
引入线程之后，线程成为了程序执行流的最小单位
线程可以理解为轻量级进程
引入线程后
进程是资源分配的基本单位，线程是调度的基本单位
各线程之间也可以并发，提升了并发度
同一进程中的线程切换不需要切换进程环境，系统开销小
引入线程后，并发所带来的系统开销减少
线程的属性
- 线程是处理机调度的单位
- 多cpu计算机中，各个线程可以占用不同的cpu
- 每个线程都有一个线程ID，线程控制块（TCB）
- 线程也有就绪，阻塞，运行三种基本状态
- 线程几乎不拥有系统资源
- 同一进程的不同线程共享进程的资源
- 由于共享内存地址空间，同一进程的线程间通信无需系统干预
- 同一线程中的线程切换不会引起进程切换
- 不同进程中的线程切换会引起进程切换
- 切换同进程内的线程系统开销很小
- 切换进程系统开销较大
线程的实现方式
用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责
用户级线程中线程切换可以在用户态下即可完成，无需操作系统干预
在系统看来是意识不到线程的存在
用户级线程就是从用户视角能看到的线程
优点是用户级线程的切换在用户空间内即可完成，不需要切换到核心态，线程管理的开销小，效率高
缺点是当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高，多个线程不可以在多核处理机上并行运行
内核级线程
内核级线程的管理工作由操作系统内核来完成
线程调度和切换都由内核负责，所以内核级线程的切换必须在核心态下来完成
操作系统会为每一个内核级线程建立相应的TCB来对线程进行管理
优点是当一个线程被阻塞后，别的线程还可以继续执行，并发能力强，多线程可以在多核处理器上并行执行
缺点是一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大
在支持内核级线程的系统中，根据用户级线程和内核级线程的映射关系，可以划分为几种多线程模型
有一对一模型和多对一模型
一对一模型
一个用户级线程映射到一个内核级线程，每个用户进程有雨用户级线程同数量的内核级线程
优点是一个线程被阻塞后，别的线程还可以继续执行，并发能力强，多线程还可以在多核处理器上并行执行
缺点是一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到内核态，因此线程管理的成本高开销大
多对一模型
多个用户级线程映射到一个内核级线程，且一个进程只被分配一个内核级线程
优点是用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
缺点是当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高，多个线程不可在多核处理器上并行运行
多对多模型
n个用户级线程分配到m个内核级线程（n>=m）
内核级线程才是处理器分配的单位
处理器的调度
三个层次
高级调度（作业调度）
按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程
调度发生在外存到内存
发生频率最低
中级调度（内存调度）
按照某种策略决定将哪个处于挂起状态的进程重新调入内存
发生频率中等
低级调度（进程调度）
调度频率很高
进程的挂起态和七状态模型
进程调度的时机
当前运行的进程主动放弃处理机
当前运行的进程被动放弃处理机
不能进行进程调度和切换的情况
- 在处理中断的过程中
- 进程在操作系统内核程序临界区
- 在原子操作过程中
进程调度的方式
非剥夺调度方式（又称非抢占方式）
只允许进程主动放弃处理机，在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态
剥夺调度方式，又称抢占方式
当一个进程正在处理机上执行时，如果有一个更重要或者更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更加重要紧迫的那个进程
进程的切换是有代价的，如果过频繁的进行进程调度，切换，必然会使系统的效率降低
调度程序
出现以下情况时会触发调度程序
- 创建新进程
- 进程退出
- 运行进程阻塞
- I/O中断发生（可能唤醒某些阻塞进程）
非抢占式只有在运行进程阻塞或退出才出发调度程序工作
抢占式调度每个时钟中断或者k个时钟中断会触发调度程序工作
不支持内核级线程的操作系统进程为操作单位
支持的为线程
闲逛进程
在cpu没有进程时执行闲逛进程
特性
- 优先级最低
- 可以是0地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）
- 能耗低
调度算法的评价指标
- CPU利用率
- 系统吞吐量
- 周转时间
- 等待时间
- 响应时间
CPU利用率
利用率＝忙碌的时间/总时间
系统吞吐量
单位时间内完成作业的数量
系统吞吐量 = 总共完成的作业/总共花的时间
周转时间
作业被提交给系统开始，到作业完成为止的时间间隔
包括四个部分，高级调度的时间，低级调度的时间，进程在CPU上执行的时间，进程等待I/O操作完成的时间，后三项在一个作业的整个处理过程中可能发生多次
周转时间 = 作业完成时间 – 作业提交时间
平均周转时间 = 作业周转时间之和 / 作业数
带权周转时间 = 作业周转时间 / 作业实际运行的时间 =（ 作业完成时间 – 作业提交时间 ）/ 作业实际运行的时间
平均带权周转时间 = 各作业带权周转时间之和 / 作业数
等待时间
对于进程而言，等待时间就是指进程建立后等待被服务的时间之和
对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列的时间
响应时间指用户提交请求到首次产生响应所用的时间
调度算法
- 先来先服务（FCFS）
- 短作业优先（SJF）
- 高响应比优先（HRRN）
先来先服务算法（FCFS）
从公平的角度考虑
按照作业/进程到达的先后顺序进行服务
用于作业调度时，考虑的是哪个作业先到达后备队列，用于进程调度时，考虑的是哪个进程先到达就绪队列
属于非抢占式的算法
优点是公平，算法实现简单
缺点是排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好，FCFS算法对长作业有利，对短作业不利
不会导致饥饿
短作业优先（SJF）
追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间
最短的作业（进程）优先得到服务（最短指要求的服务时间最短）
可以用于作业调度和进程调度，用于进程时称为短进程优先算法（SPF）
SJF和SPF是非抢占式的算法，但是有抢占式的版本–最短剩余时间优先算法（SRTN）
优点是最短的平均等待时间和平均周转时间（但是最短剩余时间优先算法比他1更短）
缺点是不公平，对短作业有利，对长作业不利，并且运行时间由用户提供，并不一定真实，不一定能做到真正的短作业优先
会导致饥饿，并可能导致饿死
高相应比优先（HRRN）
综合考虑作业/进程的等待时间和要求服务时间
在每次调度时先计算响应比，选择响应比最高的作业/进程为其服务
响应比=（等待时间+要求服务时间）/要求服务时间
既可以用于作业调度也可用于进程调度
非抢占式的算法
优点是考虑了等待时间和运行时间
等待时间相同时要求服务时间长的优先
不会导致饥饿
时间片轮转（RR）
公平的，轮流的为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
按照进程到达就绪队列的顺序，轮流让各个进程执行一个时间片，结束后未执行完成的剥夺处理机，将进程重新放入就绪队列队尾重新排队
用于进程调度
抢占式算法
如果前一个进程执行完毕重回队列的同时有一个新进程到达，默认新到达的进程先进入就绪队列
如果时间片太大足够每个进程在一个时间片内就能完成就会退化成先来先服务算法并且会增大进程响应时间
一般来说时间片设置的大小要让切换进程的开销不超过1%
优点是公平，响应快，适用于分时操作系统
缺点是高频率的进程切换因此会有开销且不区分任务的紧急程度
不会导致饥饿
优先级调度算法
根据任务的紧急程度来决定处理顺序
每个作业/进程都有各自的优先级，调度时选择优先级最高的作业/进程
可用于作业调度和进程调度和I/O调度
有抢占式和非抢占式
优点是优先级可以很好的区分紧急程度，重要程度，适用于实时操作系统，可以灵活的调整对各种作业/进程的偏好程度
缺点是源源不断的高优先级进程可能会导致饥饿
会导致饥饿
多级反馈队列调度算法
对其他调度算法的折中权衡
规则
- 设计多级就绪队列，各级队列优先级从高到低，时间片从小到大
- 新进程到达时先进入第一级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾，如果此时已经在最下级的队列，则重新放回该队列的队尾
- 只有第k级队列为空，才会为k+1级队头的进程分配时间片
用于进程调度
抢占式算法，在运行过程中如果有进程进入了更上级的队列则会抢占处理机，被抢占的进程放回队尾
优点是相对公平，每个新到达的进程很快得到响应，短进程只用较少的时间就可以完成，无需顾忌用户作假进程的运行时间，可以灵活的调整各类进程的偏好程度
会导致饥饿
多级队列调度算法
队列之间可以采取固定优先级或者时间片划分
各队列可以采用不同的调度策略，如系统进程队列采用优先级调度
同步和互斥
同步
进程的并发性带来了异步性，有时需要通过进程同步解决异步问题，有的进程之间需要相互配合的完成工作，各个进程的工作推进需要遵循一定的先后顺序
互斥
对临界资源的访问需要互斥的进行，即同一时间段内只允许一个进程访问该资源
分为四个部分
- 进入区 检查是否可进入临界区，若可进入，需要上锁
- 临界区 访问临界资源的代码
- 退出区 负责解锁
- 剩余区 其余代码部分
需要遵循的原则有
- 空闲让进 临界区空闲时，应允许一个进程访问
- 忙则等待 临界区被访问时，其他试图访问的进程需要等待
- 有限等待 要在有限时间内进入临界区，保证不会饥饿
- 让权等待 进不了临界区的进程要释放处理机防止忙等
单标志法
两个进程在访问完临界区之后会把使用临界区的权限转交给另一个进程，也就是说每个进程进入林基区的权限只能被另一个进程赋予
该算法可以实现同一时刻最多只允许一个进程访问临界区
双标志先检查法
主要问题是违反了忙则等待的原则
双标志后检查法
先进行上锁过程，然后标记想要进入临界区
主要问题是违背了空闲让进和有限等待
会导致饥饿
Peterson算法
结合单标志法和双标志法
先表达意愿，然后表示谦让，在自己表达且谦让的情况下循环等待
缺点是未遵循让权等待的原则
中断屏蔽方法
使用开/关中断指令实现
优点是简单高效
缺点是不适用于多处理机，只适合操作系统内核进程，不适用于用户进程
TestAndSet指令（TSL）
用硬件实现，执行的过程中不允许被中断
不满足让权等待
Swap指令
用硬件实现，执行的过程中不允许被中断，只能一气呵成
不满足让权等待
信号量机制
用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而实现进程互斥和进程同步
一对源语 wait（S）和signal（S）原语，S为传入参数
简称为P，V操作，写作P（S），V（S）
整形信号量
用一个整数型的变量作为信号量，来表示特定资源的数量，与普通整数变量的区别在于对信号量的操作只有三种，即初始化，P操作，V操作
检查和上锁一气呵成，避免了并发，异步导致的问题
存在的问题有不满足让权等待原则，会发生忙等
记录型信号量
S.value表示某种资源数，S.L指向等待该资源的队列
P操作中一定先S.value–之后可能需要执行block原语
V操作中一定先S.value++之后可能需要执行wakeup原语
可以用记录形信号量实现系统资源的申请和释放
可以用记录型信号量实现进程互斥和进程同步
信号量机制
实现进程互斥
- 分析问题，确定临界区
- 设置互斥信号量，初始值为1
- 临界区之前对信号量执行P操作
- 临界区之后对信号量执行V操作
实现进程同步
- 分析问题，找出一前一后的同步关系
- 设置同步信号量为0
- 在前操作后执行V
- 在后操作之前执行P
实现进程的前驱关系
分析问题，画出前驱图，把每一对前驱关系都看成是一个同步问题
生产者消费者问题
生产者进程每次生产一个产品放入缓冲区
消费者进程每次拿走一个产品
各个进程需要互斥的访问
管程的定义和基本特征
管程是一种特殊的软件模块，有这些部分构成：
- 局部于管程的共享数据结构说明
- 对该数据结构进行操作的一组过程
- 对局部于管程的共享数据上设置初始值的语句
- 管程有一个名字
管程的基本特征
- 局部于管程的数据只能被局部于管程的过程所访问
- 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
- 每次仅允许一个进程在管程内执行某个内部过程
死锁
发生死锁说明至少有两个或者两个以上的进程同时发生死锁
饥饿
可能只有一个进程发生饥饿，可能处于就绪态和阻塞态
死循环
死循环可以上处理机运行
死锁和饥饿是操作系统分配资源的策略不合理导致的，死循环是由代码逻辑错误导致的，死循环不是操作系统的问题
死锁必须满足以下四个条件
- 互斥条件
- 不剥夺条件
- 请求和保持条件
- 循环等待条件
对不可剥夺资源的不合理分配会导致死锁
死锁的处理策略
1.预防死锁
2.避免死锁
3.死锁的检测和解除，允许死锁发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施来解除死锁
静态策略：预防死锁
破坏互斥条件
利用SPOOLing技术
破坏不剥夺条件
缺点是实现起来比较复杂，增加系统开销，会导致饥饿
破坏请求和保持条件
如静态分配方法，获得全部资源后开始运行
缺点是资源利用率极低，并且可能导致饥饿
破坏循环等待条件
采用顺序资源分配法，有小编号资源的进程才可以申请大编号的资源
缺点是不方便增加新的设备，因为需要重新分配所有的编号
进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费
用户编程也会麻烦
动态策略：避免死锁
安全序列，按照一个具体的序列分配资源不会发生死锁，只要能找出一个安全序列，系统就是安全状态，安全序列可能有多个
分配资源之后如果没有安全序列，就进入了不安全状态，意味着可能所有进程无法顺利的执行下去，如果有进程提前归还资源系统也有可能重新回到安全状态
系统处于安全状态一定不会发生死锁
系统进入不安全状态有可能发生死锁
在资源分配之前预先判断这次分配会不会导致系统进入不安全状态，从而决定是否答应分配请求，这也是银行家算法的核心思想
安全性算法，可以用循环检查剩余可用资源可以囊括的进程并把它加入到安全序列中，循环得到安全序列
如果找不到任何一个安全序列，说明系统此时不安全
银行家算法步骤
- 检查此次申请是否超过了之前声明的最大需求数
- 检查此时系统剩余的可用资源是否满足这次需求
- 试探着分配，更改各数据结构
- 用安全性算法检查此次分配是否会导致系统进入不安全状态
为了能对系统是否已发生了死锁进行检测，必须：
用某种数据结构来保存资源的请求和分配信息
提供一种算法，利用上述信息来检测系统是否进入死锁状态
解锁死锁的主要方法有
资源剥夺法和撤销进程法和进程回退法
资源分配图
- 两种结点 进程结点和资源节点
- 两种边 进程结点->资源结点（请求边）
- 资源节点 -> 进程结点（分配边）
死锁检测算法
依次消除与不阻塞进程相连的边，直到无边可消
死锁定理
若资源分配图是不可完全简化的，说明发生了死锁
内存的基础知识
进程运行的基本原理
原理：操作码+若干参数
逻辑地址（相对地址）vs物理地址（绝对地址）
从写程序到程序运行
- 编辑源代码文件
- 编译 源代码生成目标模块
- 链接 由目标模块生成装入模块，装入后形成物理地址
- 装入 将装入模块装入内存，装入后形成物理地址
三种链接方式
- 静态链接
- 装入时动态链接
- 运行时动态链接
三种装入方式
- 绝对装入
- 可重定位装入
- 动态运行时装入
地址转换
操作系统负责内存空间的分配和回收
操作系统需要提供从某种技术上从逻辑上对内存空间进行扩充
操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址
操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不打扰
存储保护的两种方式
设置上下限寄存器
利用重定位寄存器，界地址寄存器进行判断
覆盖技术
一个固定区域
存放最活跃的程序段
固定区中的程序段在运行过程中不会调入调出
若干覆盖区
不可能同时被访问程序段可共享一个覆盖区
覆盖区中的程序段在运行过程中会根据需要调入调出
必须由程序员声明覆盖结构，操作系统完成自动覆盖
缺点：对用户不透明，增加了用户编程负担
交换技术
内存紧张时，换出某些进程以腾出内存空间，再换入某些进程，磁盘分为文件区和对换区，换出的进程放在对换区
覆盖是在同一个程序或进程中
交换实在不同进程/作业之间进行的
内存分配
单一连续分配
内存被分为系统区和用户区，内存中只能由一道用户程序，用户程序独占整个用户区空间
优点是实现简单，无外部碎片，可以采用覆盖技术扩充内存，不一定需要采取内存保护
缺点是只能用于单用户，单任务的操作系统中，有内部碎片，存储器利用率极低
固定分区分配
两种分配方法
分区大小相等和分区大小不等
大小相等缺少灵活性但是很适合用于一台计算机控制多个相同对象的场合
大小不等的增加了灵活性
优点是实现简单无外部碎片，
缺点是当用户程序太大会不得不利用覆盖解决，并且会产生内部碎片
动态分区分配
不会预先划分内存分区，根据进程的大小动态建立分区
没有内部碎片但是有外部碎片
可以通过紧凑技术来解决外部碎片
动态分区分配算法
首次适应
从头到尾找合适的分区
最佳适应
优先使用更小的分区，以保留更多大分区
最坏适应
优先使用更大的分区
邻近适应
每次从上次查找结束位置开始查找
基本分页存储管理的基本概念
把进程分页，各个页面可离散的放到各个的内存块中
页表
- 页表记录了页面和实际存放的内存块之间的映射关系
- 一个进程对应一张页表，进程的每一页对应一个页表项，每个页表由页号和块号组成
- 每个页表项的大小是相同的，页号是隐含的
- i号页表项存放地址 = 页表始址 + i*页表项大小
逻辑地址结构 — 可拆分为页号P，业内偏移量W
页号 = 逻辑地址 / 页面大小
页内偏移量 = 逻辑地址%页面大小
实现地址转换
- 计算逻辑地址对应的【页号，业内偏移量】
- 找到对应页面在内存中的存放位置（查页表
- 物理地址 = 页面始址+业内偏移量
基本地址变换机构
页表寄存器的作用
存放页表起始地址
存放页表长度
地址变换过程
- 根据逻辑地址算出页号，业内偏移量
- 页号的合法性检查（与页表长度对比）
- 若页号合法，再根据页表起始地址，页号找到对应页表项
- 根据页表项中记录的内存块号，页内偏移量 得到最终的物理地址
- 访问物理内存中对应的内存单元
