进程管理
- 要点：
- 基础：进程描述及控制
- 策略：进程调度
- 实现：互斥与同步
- 避免：死锁与饥饿
- 解决：几个经典问题
- 进程的引入
- 程序的顺序执行
- 源代码程序，目标程序和可执行程序
- 程序执行：编辑，编译，链接，执行
- 程序的结构：顺序，分支，循环结构
- 程序执行的特征：顺序性，封闭性，可再现性
- 程序并发执行
- 多道程序设计技术：多个程序并发执行
- 程序并发执行时的特征：间断性，非封闭性，不可再现性
- 并发执行引发的问题：
- 协调各程序的执行顺序：输入数据还未全部输入内存时，计算必须等待
- 多个执行程序共享系统资源，程序之间可能会相互影响，甚至影响输出结果
- 选择那些，多少个程序进入内存执行
- 内存中的执行程序谁先执行，谁后执行
- 内存如何有效分配？
- 进程的概念
- 定义：可并发执行的程序，在一个数据集合上的运行过程
- 申请、拥有资源~调度（线程）
- 程序：静态概念，是指令和数据的集合，可长期存储
- 进程与程序对应关系
- 一个程序可以对应一个进程或者多个进程
- 一个进程可以对应一个程序，或者一段程序
- 进程的特征
- 动态性
- 并发性
- 独立性
- 异步性
- 引入进程带来的问题
- 增加了空间开销：为进程建立数据结构
- 额外的时间开销：管理和协调，跟踪，填写和更新有关数据结构，切换进程，保护现场
- 更难控制：协调多个进程竞争和共享资源如何预防；解决多个集成因为竞争资源而出现的故障
- 处理机的竞争尤为突出
- 进程的结构
- 组成（进程映像）：程序，数据集合，进程控制块PCB（Process Control Block）
- PCB是进程存在的唯一标志。创建进程时，创建PCB；进程结束时，系统将撤销其PCB
- 程序的顺序执行
- PCB
- 进程标识信息：进程的内部（系统分配给它的标示）和外部标示符（name of a person）
- 处理机状态信息：通用寄存器值，指令计数器值，程序状态字PSW值，用户栈指针值
- 进程调度信息：进程状态，进程优先权，进程调度的其他信息
- 其他信息：程序及数据指针，进程同步和通讯机制，资源清单，连接指针
- PCB的组织方式
- 单一队列：所有进程的PCB通过链表组织成为一个单一队列。适用于进程数目不多的系统。如windows操作系统
- 表格结构（查找效率较高）
- PCB按进程状态不同组织成不同的表格：就绪进程表，执行进程表（多机系统中）及阻塞进程表
- 系统分别记载各PCB表的起始地址
- PCB多级队列
- 进程的状态
- 进程的执行轨迹：进程执行的指令序列，用以观察处理机的执行过程
- 两状态模型：
- 执行，未执行
- 并非所有进程只要“未执行”就处于就绪状态，有的需要阻塞，等待IO完成；“未执行”又可以分为就绪和阻塞
- 进程的五状态
- 执行Running：占用处理机（单处理机环境中，某一时刻仅一个进程占用处理机）
- 就绪Ready：准备执行
- 阻塞Blocked：等待某事件发生才能执行，如等待I/O完成等
- 新New：进程已经创建，但未被OS接纳为可执行进程
- 终止Terminated：因停止或取消，被OS从执行状态释放
- 某些系统允许父进程在任何情况下终止其子进程。如果一个父进程被终止，其子进程都必须终止
- 问题：多个进程竞争内存资源
- 内存资源紧张
- 无就绪进程，处理机空闲：I/O的速度比处理机的速度慢很多，可能出现全部进程阻塞等待I/O
- 解决方法
- 采用交换技术：换出一部分进程到外存，以腾出内存空间
- 采用虚拟存储技术：每个进程只能装入一部分程序和数据（存储管理部分）
- 对换技术，交换技术
- 将内存中暂时不能运行的进程，或暂时不用的数据和程序，换出到外存，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存
- 进程挂起的原因
- 进程全部阻塞，处理机空闲
- 系统负荷过重，内存空间紧张
- 操作系统的需要。操作系统可能需要挂起后台进程或一些服务进程，或者某些导致系统故障的进程
- 终端用户的请求
- 父进程的请求
- 被挂起进程的特征
- 不能够立即执行
- 可能是等待某事件发生，若是，则阻塞条件独立于挂起条件，即使阻塞事件发生，该进程也不能够执行
- 使之挂起的进程为：自身，父进程，OS
- 只有挂起他的进程才能使之由挂起状态转换为其他状态
- 挂起与阻塞
- 是否只能挂起阻塞进程
- 如何激活一个挂起进程
- 两个概念：进程是否等待事件，阻塞与否；进程是否被换出内存，挂起与否
- 4种状态组合：
- 就绪：进程在内存，准备执行
- 阻塞：进程在内存，等待事件
- 就绪/挂起：进程在外存，只要调入内存即可执行
- 阻塞/挂起：进程在外存，等待事件
- 处理机可调度执行的进程有两种：
- 新创建的进程
- 或换入一个以前挂起的进程
- 通常为了避免增加系统负载，系统会换入一个以前挂起的进程执行
- 进程的控制
- 两种执行模式：
- 系统模式（又称为系统态）、控制模式或内核模式
- 具有较高特权
- 运行系统特定的指令，包括读写控制寄存器的指令，基本IO指令以及与存储管理有关的指令及一些特定的内存区
- 内核模式下的处理机及其指令、寄存器和内存都受到完全控制和保护
- 用户模式（或用户态）
- 较低的特权
- 用户一般运行在用户模式
- 系统模式（又称为系统态）、控制模式或内核模式
- 模式切换
- 用户->系统：用户执行到一条系统调用，进入操作系统内核执行
- 系统->用户：执行完系统调用的功能，返回到用户程序
- 特殊情况：程序执行到结束语句时，切换到系统模式，不再返回到用户程序
- 操作系统内核
- 基于硬件的第一层软件扩充，提供操作系统最基本的功能，是操作系统工作的基础；
- 现代操作系统中，为减少系统本身的开销，往往将一些与硬件紧密相关的（如中断处理程序，设备驱动程序等），基本的，公共的，运行频率较高的模块（如时钟管理，进程调度等），以及关键性数据结构独立开来，使之常驻内存，并对他们进行数据保护。通常把这一部分称为操作系统的内核。
- 用户通过系统调用访问操作系统的功能，这些功能最终都通过操作系统内核实现。
- 一般滴，操作系统内核功能可以概括地划分为资源管理功能和支撑功能
- 资源管理：
- 进程管理：进程创建和终止，调度，状态转换，同步和通信，管理PCB
- 存储管理：为进程分配地址空间，对换，段/页管理
- IO设备管理：缓存管理，为进程分配IO通道和设备
- 支撑功能：
- 中断处理
- 统计
- 监测
- 时钟管理
- 原语（Primitive）：原子操作
- 进程的创建与终止
- 进程的阻塞与唤醒
- 进程的挂起与激活
- 进程切换
- 进程切换&模式切换
- 进程切换：作用与进程之间的一种操作
- 模式切换：进程内部所引用的一种操作，当用户程序和转入系统调用，或者相反时，该操作将被引用
- 进程切换一定会引发模式切换，反之则不然
- 进程切换&模式切换
- 资源管理：
- 两种执行模式：
- 进程调度
- 调度是指，在一个队列中，按照某种方法（算法），选择一个合适的个体的过程。
- 调度的关键是需要某种方法或者算法，好的调度算法有利于选择到合适的个体
- 调度目标
- 公平性
- 处理机利用率
- 提高系统吞吐量
- 尽量减少进程的响应事件
- 调度原则：
- 满足用户的要求：
- 响应时间：（考虑尽可能使绝大多数用户的请求能在响应时间内完成，常用于评价分时系统的性能）
- 周转时间：作业提交给系统开始到作业完成的这段时间间隔，评价批处理系统的性能
- 截止时间：实时系统中，某任务必须开始执行的最迟时间，或必须完成的最迟时间，常用来评价实时系统的性能
- 满足系统的需求：
- 系统吞吐量
- 处理机利用率
- 各类资源的平衡使用
- 公平性及优先级
- 满足用户的要求：
- 调度方式：
- 非剥夺方式
- 执行完毕or申请IO阻塞自己
- 不利于“及时性”要求较高的分时和实时系统，主要用于批处理系统
- 剥夺方式
- 操作系统可以在新进程到来时，或某个具有较高优先权的被阻塞进策划那个插入就绪队列时，或在基于时间片调度的的系统中，时间片用完而中断当前进程的执行，调度新的进程执行
- 这种方式会产生较多的中断，主要用于实时性要求较高的实时系统及性能要求较高的批处理系统
- 非剥夺方式
- 调度类型
- 批处理调度，分时调度，实时调度和多处理机调度
- 长程调度（外存到内存）：
- long-term scheduling
- 又称为高级调度或者作业调度，它为被调度作业或用户程序创建进程，分配必要的系统资源，并将新创建的进策划那个插入就绪队列，等待短程调度
- 某些采用交换技术的系统将新创建的进程插入到就绪/挂起队列，等待中程调度
- 在批处理系统中，作业进入系统后，先驻留在磁盘上，组织成批处理队列，称为后备队列。长程调度从该队列中选择一个或者多个作业，为之创建进程
- 考虑的问题：
- 选择多少个进入内存--取决于多道程序的度，即允许同时在内存中运行的进程数
- 选择那些作业：取决于长程调度算法
- 中程调度（进程间的外存内存之间）
- 又称为中级调度
- 内存空间紧张时，或处理机找不到一个可执行的就绪进程时，需要选择一个进程（阻塞或就绪状态）换出到外存，释放出内存空间给别的进程使用；当内存空间较充裕时，从外存选择一个挂起状态的进程调度到内存（换入）；
- 目的：为了提供内存的利用率和系统的吞吐量
- 只有支持进程挂起的操作系统才具有中程调度功能
- 短程调度（内存里）：
- 也成为进程调度，或低级调度，决定就绪队列中的那个进程将获得处理机
- 短程调度运行频率最高
- 现代操作系统几乎都具有短程调度功能
- IO调度（相近的磁道）
- 进程调度算法
- FCFS(先来先服务)：同时适合于三种调度
- 非剥夺调度方式，实现简单，看似公平
- 注意：后进入队列的运行时间较短的进程或者IO型进程而言，可能需要较长时间的等待
- 对段进程不公平
- 短进程优先（对FCFS的改进）
- 非剥夺。
- 难以准确预测进程的执行时间
- 可能导致长进程饥饿
- 采用非剥夺调度方式，未考虑进程的紧迫程度，不适合于分时系统和事务处理系统
- 时间片轮转调度法
- 用户数多时进程急剧增加
- 时间片大小会影响处理性能
- 进程切换会增加系统额外开销
- 太长太短都不好
- 综合考虑系统最大用户数，响应时间，系统效率等因素
- 对于短的，计算型的进程较有利
- 不适合IO型的进程
- 改进方法之一：可以将IO阻塞时间完成的进程单独组织成一个就绪队列，该队列进程的时间片可以设置的小一点，且优先调度
- 基于优先级的调度算法
- 设定进程的优先级
- 进程完成功能的重要性
- 进程完成功能的紧迫性
- 为均衡系统资源的使用，指定进程（作业）优先级
- 进程对资源的占用程度，例如，可以为短进程（或作业）赋予较高的优先级
- 静态与动态优先级
- 动态优先级：
- 剩余时间最短者优先（剥夺型）
- 响应比高者优先
- 进程的优先级与等待时间成正比
- 难以准确的估计进程的语气执行时间
- 计算响应比增加系统开销
- 动态优先级：
- 设定进程的优先级
- 反馈调度法
- 根据执行历史而非未来进行调度，将解决这个问题
- 根据进程的执行历史调整调度方式的调度方法，它结合了优先级和时间片轮转调度的方法
- 有利于交互性短进程或批处理作业，他们一般只需要一个或者几个时间片即可完成
- 可能是长进程的周转时间急剧增加
- 如果不断有新进程进来，还可能时长进程海长期饥饿现象
- 可以为各队列设置不同的时间片，优先级愈低时间片愈长
- FCFS(先来先服务)：同时适合于三种调度
- 实时系统（Real-Time System）
- 能及时响应外部事件爱你的请求，在规定时间内完成对该事件的处理，并控制所有的实时任务协调一致的运行的计算机系统
- 分为实时控制系统和实时信息处理系统
- 实时控制系统：
- 要求进行实时控制的系统
- 主要用于生产过程的控制。（自动控温，武器控制，导弹制导，自动驾驶）
- 实时信息处理系统
- 对信息进行实时处理的系统
- 很短的时间为用户做出正确的回答（飞机订票，情报检索）
- 实时任务（real-time task）
- 具有即时性要求的，常常被重复执行的特定进程，在实时系统中常被称为任务
- 周期性划分
- 周期性实时任务
- 周期性的控制某个外部事件
- 非周期性实时任务
- 必须联系着一个截止时间（开始截止时间，完成截止时间）
- 周期性实时任务
- 对截止时间的要求
- 硬实时任务（错过了出现难以预测的结果，可能是灾难性的）
- 软实时任务（错过了影响不会太大）
- 目标：
- 硬实时任务必须完成，软实时任务尽量完成
- 公平性和最短时间响应时间等要求已不再重要
- 算法：
- 实时性要求不太高的
- 基于时间片轮转调度算法
- 基于 优先级的调度算法
- 最早截止时间优先调度算法，即优先调度截止时间最近的实时任务
- 速度单调调度算法（RMS）
- 根据任务周期大小赋予优先级，最短优先任务具有最高优先级其中
- 任务周期（period），之一个任务到达至下一个任务到达之间的时间范围
- 任务速度（rate），即周期（以秒记）的倒数
- 任务周期的结束，表示任务的硬截止时间，任务的执行时间不应超过任务周期
- 以任务速度为参数，则优先级函数式一个单调递增的函数
- 广泛用于工业实时系统的周期性任务调度
- 根据任务周期大小赋予优先级，最短优先任务具有最高优先级其中
- 实时性要求不太高的
- 线程
- 引入线程是为了减少程序并发执行时系统所付出的额外开销，使系统具有更好的并发性
- 两个基本属性
- 进程是一个拥有资源的独立单位
- 同时又是一个可以独立调度的基本单位
- 由进程到线程
- 目标：既能提高进程的并发度，又能降低系统的额外开销
- 实现：将进程的资源申请和调度属性分开，即进程作为资源的申请和拥有者，但是不作为调度的基本单位，这样就产生了线程的概念
- 线程自身基本上不拥有系统资源，只拥有少许运行中必不可少的私有资源，线程可与同属一个进程的其他线程共享进程的全部资源
- 进程中的所有线程共享该进程的状态
- 三种基本状态：就绪执行阻塞
- 一般不具有挂起状态
- 一个进程可以创建和撤销多个线程，同一进程的多个线程可以并发执行
- 线程的操作包括:
- 派生（SPawn）
- 阻塞（Block）
- 解除阻塞（Unblock）
- 结束（Finish）
- 线程阻塞不一定会引起进程的阻塞
- 类型：
- 用户级线程（由应用程序完成）和内核级线程
- 进程中的某个线程需要等待另一线程的输入数据而阻塞时，整个进程并不会阻塞，即进程保持执行状态，其内的某个线程也是执行状态。
- 当某线程因为IO阻塞时，内核需要启动系统IO，控制从用户级转到系统内核级，这时常会引起整个进程阻塞，随即将发生进程切换，进程调度程序重新调度另一个就绪进程执行。
- 混合模式
- 进程的互斥与同步
- 问题：如何协调多个进程对系统资源，如内存空间，外部设备等的竞争和共享？如何解决多个进程因为竞争资源而出现的执行结果异常，设置系统不稳定，失效等问题。
- 并发控制：
- 竞争资源
- 死锁
- 某些资源必须互斥的使用--临界资源
- 访问临界资源的那段代码称为临界区
- 任何时刻，只允许一个进程进入临界区，以此实现进程对临界资源的互斥访问
- 竞争资源
- 互斥使用临界区
- 在进程需要使用临界资源时，通过获得临界区的使用权实现的。
- 首先，在进入区判断是否可以进入临界区，如果可以进入，则必须设置临界区使用标志，阻止其他后来的进程进入临界区。后来的进程通过查看临界区使用标志，知道自己不能够进入临界区，就进入阻塞队列，将自己阻塞
- 当临界区内的进程时候用完毕，推出临界区时，即在退出区修改临界区使用标志，并负责唤醒阻塞队列中的一个进程，让其进入临界区
- 必须保证“临界区使用标志”是可以被系统中的所有进程共享的全局变量，而且诸进程对该标志的修改操作必须互斥的进行
- 临界区使用原则
- 每次只允许一个进程进入临界区（忙则等待）
- 进程只能在临界区内逗留有限时间，不得使其他进程在临界区外无限等待（有限等待）
- 如果临界区空闲，则只要有进程申请就立即让其进入（空闲让进）
- 进入临界区的进程，不能够在临界区内长时间阻塞等待某事件，必须在一定期限内退出临界区（让权等待）
- 不能限制进程的执行进度及处理机的数量
- 竞争资源可能引起死锁
- 竞争资源可能引起饥饿
- 并发控制-共同协作
- 多个进程常常需要共同修改某些共享变量，表格文件数据库等，协作完成一些功能
- 必须确保他们对共享变量的修改时正确的，保证数据的完整型
- 共享协作同样涉及到互斥死锁和饥饿问题，当更强调对数据的写操作必须互斥的进行
- 必须保证数据的一致性（银行存款取款余额）
- 一般通过事务处理来保证数据的一致性，进入临界区的进程必须一次性完成对这一些列数据的修改操作
- 只有该进程退出临界区以后，才允许其他进程进入临界区进行数据修改，以保证数据的一致性。
- 并发控制-通信协作
- 当进程进行通信合作时，各个进程之间需要建立连接，通信进程需要同步和协调。进程通信的方式很多，包括消息传递，管道，共享存储区等。
- 通过消息传递实现进程通信时，由于没有共享资源，故无需互斥，但仍可能出现死锁与饥饿
- 通信死锁与饥饿
- 互斥与同步的解决策略
- 软件方法
- 由进程自己，通过执行相应的程序指令，实现与别的进程的同步于互斥，无需专门的程序设计语言或操作系统的支持
- 很难正确的控制进程间的同步与互斥，而且可能会大大增加系统的额外开销
- 硬件方法
- 通过屏蔽中断或采用专门的机器指令控制同步与互斥
- 减少了系统额外开销，需要太强的硬件约束条件，以及可能导致进程饥饿与死锁现象，没有成为通用的解决方法
- 信号量方法（重点）
- 由操作系统，或专门的程序设计语言提供特别支持，包括信号量方法，管程方法和消息传递方法
- 通用方法
- 管程方法
- 消息传递方法
- 软件方法
- 软件方法
- Dekker算法
- Peterson算法
- 初步设想：控制两个互斥进入临界区，可以让两个进程轮流进入临界区
- 保证了互斥
- 出现忙等现象
- a非要等b用完一次才能使用下一次
- 第一次改进
- 为临界区设置状态标志，表明临界区是否可用，空闲时，任何一个进程都能进入
- 进程在临界区失败问题
- 不能保证互斥
- 第二次改进
- 预先表明希望进入临界区
- 会死锁会忙等
- 第三次改进
- 使他们表明态度，懂得“谦让”
- Dekker互斥算法
- Peterson方法
- 硬件算法
- 屏蔽中断
- 约束太强，代价太大
- 专用机器指令
- Test and set 指令
- exchange指令
- 优点：简单，易于证明；同时适合与单处理机系统和共享内存的多处理机系统中多个进程的互斥；
- 缺点：忙等现象依然存在，但属于可接受的忙等；可能出现饥饿现象
- 可能导致死锁
- 信号量方法
- 实例：信号灯
- 两个或者两个进程可以通过传递信号进行合作，可以迫使进程在某个位置暂时停止执行（阻塞等待），知道它受到一个可以向前推进的信号（被唤醒）
- 相应的，实现信号灯作用的变量称为信号量，常定义为记录型变量s，其中一个域为整型，另一个域为队列，其元素为等待信号量的阻塞进程
- 信号量定义
- 定义对信号量的两个原子操作：wait（s）和signal（s）；早期这两个原语被称为P(s)和V(s)
- 信号量的类型：互斥信号量和资源信号量
- 互斥信号量用于申请或者释放资源的使用权，常初始化为1
- 资源信号量用于申请或归还资源，可以初始化为大于1的正整数，表示系统中某类资源的可用个数
- wait操作用于申请资源（或使用权），进程执行wait原语时，可能会阻塞自己
- signal操作用于释放资源（或归还资源使用权），进程执行signal原语时，有责任唤醒一个阻塞进程
- 信号量的物理意义s.count表示可用资源数
- 屏蔽中断
- 生产者/消费者问题
- 必须使生产者和消费者互斥进入缓冲区。即，某时刻只允许一个实体（生产者或消费者）访问缓冲区，生产者互斥消费者和其他任何生产者。
- 生产者不能够向满缓冲区写数据，消费者也不能在空缓冲区中取数据，即生产者与消费者必须同步
- 读者/写者问题
- 读者优先
- 读者优先
- 管程方式（面向对象的方法）（应用比较少）
- 管程结构
- 用管程实现互斥
- 消息传递
- 进程通信的方式
- 常用进程通信方式
- 基于共享存储区方式
- 消息传递方式
- 进程之间通信的两条原语
- Send（destination，message）
- Receive（sourse,message）
- 消息传递的同步
- 三种同步方式
- 阻塞接收
- 消息传递中的寻址
- 间接寻址
- 利用消息传递实现互斥
- attention
- 消息传递解决生产者消费者问题
- 邮件方式
在多道程序中，需要从磁盘中同时读入多个进程到内存，我们需要对内存进行管理，使得能够有条理地执行进程。
通常指令先要从内存中读入，进行解码，还要从内存中读取操作数，再将结果返回给内存。内存看到的只是地址。
一个进程占了一块内存，跨度是一串连续的地址，我们用base register和limit register来限定进程访问的范围。
CPU只能访问的存储器是内存和CPU的寄存器，所以如果有指令要访问数据，必须要提前导入到内存。下面会讲到交换方法，和动态载入。
Cache：因为访问CPU寄存器必访问内存速度快了很多，所以我们不能老是访问内存，所以要有Cache。访问内存可能会导致CPU暂停。
进程访问的地址的限定通过硬件实现：即通过base和limit寄存器的比较实现。
OS可以改limit和base的值。
磁盘有一个输入队列，存放准备导入内存的进程。
代码里我们通常用一个变量代表地址，我们可以将变量绑定到可重定位地址，加载程序再将重定位地址绑定成绝对地址。
绑定的情况：
1.编译时：如果在编译时就知道内存的地址，那么直接绑定绝对地址。
2.加载时：在编译时生成可重定位代码，在加载时才生成绝对代码。
3.执行时：如果执行时还要将进程从一个内存块移到另一个内存块，则只有执行时才绑定。
CPU生成的逻辑地址，内存的地址是物理地址。
程序生成的地址空间称为逻辑地址空间。
运行时虚拟地址到物理地址通过MMU映射。通过CPU的逻辑地址+base register就得到物理地址。用户是不知道物理地址的。
动态加载：如果一个程序必须全部加载入内存，那么必须限制程序的大小，所以动态加载是将一个大程序分成多个子程序，每次将某个子程序调入内存，如果一个子程序需要调入另一个子程序，则再加载，加强内存空间的使用率。
动态链接：通过在程序内部存放一个存根引用语言库，可以不必复制多个语言库副本，并且如果版本号不同，可以在内存中存放多个不同版本的库。
--------
如果CPU要执行的进程不再内存中，而在备份存储器中，则需要换入和换出，即交换。
当就进程换出后再次换入时，需要考虑位置问题：
1.当在加载时就绑定到物理地址，则换入到同一个位置。
2.在运行时绑定，则可以换入到任意位置。
交换的时间分为：转移时间，磁盘磁头寻址时间。
换出的进程选择方面需要注意不能选在I/O等待队列中的进程。
因此有一个修正的交换方式，可以在内存吃紧的情况下交换，但是在CPU使用率降低到一定时停止交换。
为了管理内存，需要为每个进程分配连续的内存。
内存映射需要将CPU的逻辑地址先与limit register比较，再加上base register。
当操作系统的一部分不常用时，可以先将它换出到备份存储，这块空间就可以腾给用户进程使用。
内存分配最简单的是将内存分成多个固定大小的分区，每个分区容纳一个进程。
可变分区是OS保存一个表，记录哪些内存可用，哪些内存已占用。
空闲的内存区域称为孔。
当一个进程从输入队列进入内存，有几种选取孔的方案：
1.最佳适应：遍历一遍，找到合适的最小孔。
2.首次适应。
3.最差适应。（真不知道要这个干嘛。。）
在第一第二中方法时，会存在外部碎片问题。
外部碎片问题：进程入孔后，还多出一点小空间，但不能放进程了。
内部碎片问题：分配内存时按块分配，比如一个进程3K，一个孔4K，则直接将4K分给进程，4-3=1K就是内部碎片。
解决外部碎片的方法是紧缩，将进程都挤一块。但是当绑定在加载时，则不能紧缩。
还有一种方法是重点，即可以将内存分配为非连续。
50%规则：在可分配的内存中，有50%的空间是碎片。
分页：将CPU的逻辑地址分成页，而将物理内存地址分成帧。备份存储也分成大小一样的块。先通过页号找到页表对应的帧，再加上页偏移找到内存的位置。
将CPU逻辑地址分成页号和页偏移方法：先将CPU逻辑地址的大小变成2^m,m就是逻辑地址的位数，设2^n为一页的大小，那么n则为页偏移。
m-n就为页号长度。
分页会导致内部碎片。因为帧大小固定，一次分配就是一帧的整数倍。
进程由几页组成，每个页对应一个帧。因此进程的内容就不一定要连续，每个进程对应一个页表。OS还持有每个进程页表的副本。
帧表：包括全部的帧以及他们是空闲还是被占用。
一开始页表放在PCB的寄存器中，因为速度快。但是随着页表的变大，必须把页表放在内存，而PCB只需保留一个页表基寄存器（PTBR），指向页表的头部。得到帧号再加上页偏移后再次访问内存。因此要2次访问。
由于上述方案需要2次内存访问，延迟大，所以产生了（TLB）快表（感觉就像cache），保留页表的一小部分，可以同时访问TLB的每个元素，速度快。如果TLB中没有，则按常规访问，并且将这个页表添加入TLB（局部性原理）。TLB的结构是键为页号，值为帧号。
有时TLB中还会有ASID，地址空间标识符（ASID）：唯一标识一个进程，一定要ASID匹配并且页号匹配才算匹配。
如果没有提供ASID时，则TLB保存一个进程的页表，每次进程切换，则TLB被flush。
TLB的命中率：访问TLB能找到的概率。
我们可以为每个帧授予权限，只读，可读写，可执行等。
页表的保护方式是通过在页表中提供一位称为“有效无效位”，即v或i。代表该页号是否合法。因为可能一个程序只有1-5的页号，所以页号为6以后的都被置为i。当然还可以通过PTLR(页表长度寄存器)来限制页表大小。
分页可以共享公共代码，但是这些公共代码是不能修改的。想象一下为什么能共享，因为进程只需要存放独有的页表，页表对应的帧在内存中，所以只需要一个程序即可，但是需要独立的数据，因此数据不能共享。
组织页表有几种方法：
1.多级页表。向前映射页表：从外级页表逐步映射到地址。想到了多级索引。【页表划分出题】
由来：因为我们的地址空间越来越大，所以页表也越来越大，因此到了我们都不能连续存放页表的地步，所以出现了多级页表。
2.hash页表。逻辑地址的页号通过hash后找到hash表对应位置，hash表每个元素对应一个链表，一个元素由虚拟页码、帧号、next组成。
群集页表适用于64位地址空间，hash页表的每个条目存储多个物理页帧的映射。
3.反向页表。通常一个进程有一个页表，但是占用内存大，因此整个系统只有一个反向页表，一个反向页表条目为<pid,page_number>，虚拟地址空间的一个条目为<pid,page_number,offset>，但是缺点为遍历时间长，但是可以结合前面提到的技术,如先TLB，再hash，再反向页表。但是反向页表不能共享内存。
分段是考虑到了用户对于内存的视角来构造的。将程序看成是一个段，没有顺序，用户通过<段号，段偏移>确定地址。
类似于页表，分段通过段表来实现地址映射，段表一个元素对应base register和limit register。
存储管理的基本原理
内存管理方法
内存管理主要包括内存分配和回收、地址变换、内存扩充、内存共享和保护等功能。
下面主要介绍连续分配存储管理、覆盖与交换技术以及页式与段式存储管理等基本概念和原理。
1． 连续分配存储管理方式
连续分配是指为一个用户程序分配连续的内存空间。连续分配有单一连续存储管理和分区式储管理两种方式。
(1)单一连续存储管理
在这种管理方式中，内存被分为两个区域：系统区和用户区。应用程序装入到用户区，可使用用户区全部空间。其特点是，最简单，适用于单用户、单任务的操作系统。CP／M和DOS 2．0以下就是采用此种方式。这种方式的最大优点就是易于管理。但也存在着一些问题和不足之处，例如对要求内存空间少的程序，造成内存浪费；程序全部装入，使得很少使用的程序部分也占用—定数量的内存。
(2)分区式存储管理
为了支持多道程序系统和分时系统，支持多个程序并发执行，引入了分区式存储管理。分区式存储管理是把内存分为一些大小相等或不等的分区，操作系统占用其中一个分区，其余的分区由应用程序使用，每个应用程序占用一个或几个分区。分区式存储管理虽然可以支持并发，但难以进行内存分区的共享。
分区式存储管理引人了两个新的问题：内碎片和外碎片。前者是占用分区内未被利用的空间，后者是占用分区之间难以利用的空闲分区(通常是小空闲分区)。为实现分区式存储管理，操作系统应维护的数据结构为分区表或分区链表。表中各表项一般包括每个分区的起始地址、大小及状态(是否已分配)。
分区式存储管理常采用的一项技术就是内存紧缩(compaction)：将各个占用分区向内存一端移动，然后将各个空闲分区合并成为一个空闲分区。这种技术在提供了某种程度上的灵活性的同时，也存在着一些弊端，例如：对占用分区进行内存数据搬移占用CPU~t寸间；如果对占用分区中的程序进行“浮动”，则其重定位需要硬件支持。
1)固定分区(nxedpartitioning)。
固定式分区的特点是把内存划分为若干个固定大小的连续分区。分区大小可以相等：这种作法只适合于多个相同程序的并发执行(处理多个类型相同的对象)。分区大小也可以不等：有多个小分区、适量的中等分区以及少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。这种技术的优点在于，易于实现，开销小。缺点主要有两个：内碎片造成浪费；分区总数固定，限制了并发执行的程序数目。
2)动态分区(dynamic partitioning)。
动态分区的特点是动态创建分区：在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。与固定分区相比较其优点是：没有内碎片。但它却引入了另一种碎片——外碎片。动态分区的分区分配就是寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区分配的先后次序通常是从内存低端到高端。动态分区的分区释放过程中有一个要注意的问题是，将相邻的空闲分区合并成一个大的空闲分区。
下面列出了几种常用的分区分配算法：
首先适配法(nrst-fit)：按分区在内存的先后次序从头查找，找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分会产生较多小分区，每次分配时查找时间开销便会增大。
下次适配法(next-fit)：按分区在内存的先后次序，从上次分配的分区起查找(到最后{区时再从头开始}，找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大空闲分区不易保留。
最佳适配法(best-fit)：按分区在内存的先后次序从头查找，找到其大小与要求相差最小的空闲分区进行分配。从个别来看，外碎片较小；但从整体来看，会形成较多外碎片优点是较大的空闲分区可以被保留。
最坏适配法(worst- fit)：按分区在内存的先后次序从头查找，找到最大的空闲分区进行分配。基本不留下小空闲分区，不易形成外碎片。但由于较大的空闲分区不被保留，当对内存需求较大的进程需要运行时，其要求不易被满足。
2．覆盖和交换技术
引入覆盖(overlay)技术的目标是在较小的可用内存中运行较大的程序。这种技术常用于多道程序系统之中，与分区式存储管理配合使用。覆盖技术的原理很简单，一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。将程序必要部分(常用功能)的代码和数据常驻内存；可选部分(不常用功能)平时存放在外存(覆盖文件)中，在需要时才装入内存。不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。覆盖技术的缺点是编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度；从外存装入覆盖文件，以时间延长换取空间节省。覆盖的实现方式有两种：以函数库方式实现或操作系统支持。
交换(swapping)技术在多个程序并发执行时，可以将暂时不能执行的程序送到外存中，从而获得空闲内存空间来装入新程序，或读人保存在外存中而处于就绪状态的程序。交换单位为整个进程的地址空间。交换技术常用于多道程序系统或小型分时系统中，与分区式存储管理配合使用又称作“对换”或“滚进／滚出”(roll-in／roll-out)。其优点之一是增加并发运行的程序数目，并给用户提供适当的响应时间；与覆盖技术相比交换技术另一个显著的优点是不影响程序结构。交换技术本身也存在着不足，例如：对换人和换出的控制增加处理器开销；程序整个地址空间都进行对换，没有考虑执行过程中地址访问的统计特性。
3．页式和段式存储管理
在前面的几种存储管理方法中，为进程分配的空间是连续的，使用的地址都是物理地址。如果允许将一个进程分散到许多不连续的空间，就可以避免内存紧缩，减少碎片。基于这一思想，通过引入进程的逻辑地址，把进程地址空间与实际存储空间分离，增加存储管理的灵活性。地址空间和存储空间两个基本概念的定义如下：
地址空间：将源程序经过编译后得到的目标程序，存在于它所限定的地址范围内，这个范围称为地址空间。地址空间是逻辑地址的集合。
存储空间：指主存中一系列存储信息的物理单元的集合，这些单元的编号称为物理地址存储空间是物理地址的集合。
根据分配时所采用的基本单位不同，可将离散分配的管理方式分为以下三种
段式存储管理和段页式存储管理。其中段页式存储管理是前两种结合的产物。
(1)页式存储管理
1)基本原理。将程序的逻辑地址空间划分为固定大小的页(page)，而物理内存划分为同样大小的页框(pageframe)。程序加载时，可将任意一页放人内存中任意一个页框，这些页框不必连续，从而实现了离散分配。该方法需要CPU的硬件支持，来实现逻辑地址和物理地址之间的映射。在页式存储管理方式中地址结构由两部构成，前一部分是页号，后一部分为页内地址，如图4-2所示。
这种管理方式的优点是，没有外碎片，每个内碎片不超过页大比前面所讨论的几种管理方式的最大进步是，一个程序不必连续存放。这样就便于改变程序占用空间的大小(主要指随着程序运行，动态生成的数据增多，所要求的地址空间相应增长)。缺点是仍旧要求程序全部装入内存，没有足够的内存，程序就不能执行。
2)页式管理的数据结构。在页式系统中进程建立时，操作系统为进程中所有的页分配页框。当进程撤销时收回所有分配给它的页框。在程序的运行期间，如果允许进程动态地申请空间，操作系统还要为进程申请的空间分配物理页框。操作系统为了完成这些功能，必须记录系统内存中
实际的页框使用情况。操作系统还要在进程切换时，正确地切换两个不同的进程地址空间到物理内存空间的映射。这就要求操作系统要记录每个进程页表的相关信息。为了完成上述的功能，—个页式系统中，一般要采用如下的数据结构。
进程页表：完成逻辑页号(本进程的地址空间)到物理页面号(实际内存空间)的映射。
每个进程有一个页表，描述该进程占用的物理页面及逻辑排列顺序。
物理页面表：整个系统有一个物理页面表，描述物理内存空间的分配使用状况，其数据结构可采用位示图和空闲页链表。
请求表：整个系统有一个请求表，描述系统内各个进程页表的位置和大小，用于地址转换也可以结合到各进程的PCB(进程控制块)里。
3）页式管理地址变换
在页式系统中，指令所给出的地址分为两部分：逻辑页号和页内地址。CPU中的内存管理单元(MMU)按逻辑页号通过查进程页表得到物理页框号，将物理页框号与页内地址相加形成物理地址(见图4-3)。上述过程通常由处理器的硬件直接完成，不需要软件参与。通常，操作系统只需在进程切换时，把进程页表的首地址装入处理器特定的寄存器中即可。一般来说，页表存储在主存之中。这样处理器每访问一个在内存中的操作数，就要访问两次内存。第一次用来查找页表将操作数的逻辑地址变换为物理地址；第二次完成真正的读写操作。这样做时间上耗费严重。为缩短查找时间，可以将页表从内存装入CPU内部的关联存储器(例如，快表)中，实现按内容查找。此时的地址变换过程是：在CPU给出有效地址后，由地址变换机构自动将页号送人快表，并将此页号与快表中的所有页号进行比较，而且这种比较是同时进行的。若其中有与此相匹配的页号，表示要访问的页的页表项在快表中。于是可直接读出该页所对应的物理页号，这样就无需访问内存中的页表。由于关联存储器的访问速度比内存的访问速度快得多。
(2)段式存储管理
1)基本原理。
在段式存储管理中，将程序的地址空间划分为若干个段(segment)，这样每个进程有一个二维的地址空间。在前面所介绍的动态分区分配方式中，系统为整个进程分配一个连续的内存空间。而在段式存储管理系统中，则为每个段分配一个连续的分区，而进程中的各个段可以不连续地存放在内存的不同分区中。程序加载时，操作系统为所有段分配其所需内存，这些段不必连续，物理内存的管理采用动态分区的管理方法。在为某个段分配物理内存时，可以采用首先适配法、下次适配法、最佳适配法等方法。在回收某个段所占用的空间时，要注意将收回的空间与其相邻的空间合并。段式存储管理也需要硬件支持，实现逻辑地址到物理地址的映射。程序通过分段划分为多个模块，如代码段、数据段、共享段。这样做的优点是：可以分别编写和编译源程序的一个文件，并且可以针对不同类型的段采取不同的保护，也可以按段为单位来进行共享。总的来说，段式存储管理的优点是：没有内碎片，外碎片可以通过内存紧缩来消除；便于实现内存共享。缺点与页式存储管理的缺点相同，进程必须全部装入内存。
2)段式管理的数据结构。
为了实现段式管理，操作系统需要如下的数据结构来实现进程的地址空间到物理内存空间的映射，并跟踪物理内存的使用情况，以便在装入新的段的时候，合理地分配内存空间。
·进程段表：描述组成进程地址空间的各段，可以是指向系统段表中表项的索引。每段有段基址(baseaddress)。
·系统段表：系统所有占用段。
·空闲段表：内存中所有空闲段，可以结合到系统段表中。
3)段式管理的地址变换。
在段式管理系统中，整个进程的地址空间是二维的，即其逻辑地址由段号和段内地址两部分组成。为了完成进程逻辑地址到物理地址的映射，处理器会查找内存中的段表，由段号得到段的首地址，加上段内地址，得到实际的物理地址(见图4—4)。这个过程也是由处理器的硬件直接完成的，操作系统只需在进程切换时，将进程段表的首地址装入处理器的特定寄存器当中。这个寄存器一般被称作段表地址寄存器。
4．页式和段式系统的区别
页式和段式系统有许多相似之处。比如，两者都采用离散分配方式，且都通过地址映射机构来实现地址变换。但概念上两者也有很多区别，主要表现在：
·页是信息的物理单位，分页是为了实现离散分配方式，以减少内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。段是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了更好地满足用户的需要。
·页的大小固定且由系统决定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的。段的长度不固定，且决定于用户所编写的程序，通常由编译系统在对源程序进行编译时根据信息的性质来划分。
·页式系统地址空间是一维的，即单一的线性地址空间，程序员只需利用一个标识符，即可表示一个地址。分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。
原理作业10. 页式存储管理和段式存储管理的工作原理特点、特点 及优劣。 答：页式管理的基本思想是：为了更好地利用分区存储管理中 所产生的"零头"问题，允许把一个作业存放在不连续的内存块中， 又可以连续运行，它允许只调入用户作业中常用部分，不常用部分 不长期驻留内存，有效提高了内存的利用率。 页式存储管理的工作原理： A、划分实页：将物理内存划分成位置固定、大小相同的"块"（实页 面）。 B、划分虚页：将用户逻辑地址空间也分成同样大小的页面，成为虚 拟空间的虚页面。 C、建立页表：有时称为页面表或页面映射表（PMT）。每个作业一 张，按虚页号进行登记，其基本的内容有特征位（表示该页是否 在内存、实页号以及对应外存的地址。 D、地址变换：将虚页面的逻辑地址转化为实页面的物理地址，在程 序执行时改变为物理地址，属于作业的动态重定位，一般由地址 转换机构（硬件）完成。 特点： 允许一个作业存放在不连续的内存块中而又能保证作业连续得以运行 ，既不需要移动内存中的信息，又可较好地解决零头。 优点： a、不要求作业存放在连续的内存块中，有效地解决零头。 b、允许用户作业不是一次集中装入内存而是根据需要调入，作业中 不常用部分不长期驻留内存，而本次运行的不用部分根本就不装 入内存。 c、提供了虚存，使用户作业地址空间不再受内存可用空间大小的限 制。 缺点： a、页式管理在内存的共享和保护方面还欠完善。 b、页面大小相同，位置不能动态增加。 c、往往需要多次缺页中断才能把所需的信息完整地调入内存。 段式存储管理的基本思想是：把程序按内容或过程（函数）关系 分成段，每段有自己的名字。一个用户作业或进程所包含的段对应于 一个二维线性虚拟空间，也就是一个二维虚拟存储器。段式管理程序 以段为单位分配内存，然后通过地址映射机构把段式虚拟存储地址转 化为内存中的实际地址。和页式管理一样，段式管理也采用只把那些 经常访问的段驻留内存，而把那些在将来一段时间内不被访问的段放 在外存，待需要时自动调入内存的方法实现二维虚拟存储器。按照作 业的逻辑单位--段，来分配内存，适合程序的逻辑结构，方便用户设 计程序。 段式存储管理的工作原理： A、采用二维地址空间，如段号（S）、页号（P）和页内单元号（D）； B、系统建两张表格每一作业一张段表，每一段建立一张页表，段表 指出该段的页表在内存中的位置； C、地址变换机构类似页式机制，只是前面增加一项段号。 特点： a、每一段分成若干页，再按页式管理，页间不要求连续； b、用分段方法分配管理作业，用分页方法分配管理内存； 优点： 便于段的共享和保护、段的动态增长以及动态连接。 缺点： 为了消除零头和允许段的动态增长，需要花费CPU的大量时间在内存 中移动作业的分段，而且段的大小也给外存管理带来困难。
内存的存储管理－－段式和页式管理的区别由华彩软件站为您最新收集整理,版权归原作者或公司所有。如有侵权，请与我们联系删除。