操作系统
2021-08-19 23:47:07 3 举报AI智能生成
os
作者其他创作
大纲/内容
概论
特征
并发
两个及以上的事件在同一时间间隔内发生
共享
系统中的资源可以被多个并发执行的进程所使用
虚拟
将物理上的实体变为若干逻辑上的对应物
异步
在多道程序并发执行时，彼此间的相对顺序是不确定的
目标和功能
计算机系统资源的管理者
处理机（CPU）管理
储存器管理
文件管理
设备管理
用户与计算机系统间的接口
命令接口
联机命令接口
脱机命令接口
程序接口
GUI
扩充机器
发展
批处理系统
分时操作系统
实时操作系统
网络和分布式处理系统
运行机制
中断和异常
内中断
自愿中断
指令中断
强迫中断
硬件故障
软件中断
外中断（强迫中断）
外设请求
人为干预
系统调用
设备管理
文件管理
进程控制
进程通信
内存管理
体系结构
大内核
微内核
进程管理
进程
进程的概念
概念
程序的一次执行过程
在处理机上顺序执行时所发生的活动
系统进行资源分配和调度的基本单位
PCB
控制和描述进程基本情况和运行情况的基本状态
是进程存在的唯一标志
进程的特征
动态性
并发性
独立性
异步性
结构性
进程的状态和转换
运行态
就绪态
阻塞态
创建态
结束态
转换
就绪态→运行态
运行态→就绪态
运行态→阻塞态
阻塞态→就绪态
进程控制
进程的创建
父子进程
创建过程
为新进程分配一个pid，并申请一个PCB（若申请PCB失败，进程创建失败）
为进程分配资源（若资源不足，则阻塞）
初始化PCB
若可以插入就绪队列则插入
进程的终止
终止原因
正常结束
异常结束（内部）
外部干预
终止过程
检索PCB读出进程的状态
若进程正在执行，则立刻结束，释放资源给其他进程
若该进程有子孙进程，将其所有子孙进程终止
释放该进程的所有资源，或归还父进程，或归还系统
删除PCB
进程的阻塞
阻塞过程
找到与pid对应的PCB
若是运行态，保护运行状态，转为阻塞态，停止运行
将该PCB插入对应事件的等待队列，将处理机资源调配给其余进程
需要使用BLOCK源语
进程的唤醒
唤醒过程
在对应的等待队列中找到该进程的PCB
将PCB从等待队列中移出，并置为就绪态
将PCB插入就绪队列
需要使用WAKEUP原语
进程的切换
切换过程
保存上下文，包括程序计数器（PC）和其他寄存器
更新PCB信息
将PCB移入对应的队列
选择另一个进程执行
更新内存管理的数据
恢复处理机的上下文
调度指的是决定资源分配给哪个进程的行为，是决策行为
切换是实际分配的行为是执行行为
进程的组织
进程控制块（PCB）
是进程实体的一部分，是进程存在的唯一标志
系统通过PCB来管理和控制进程
PCB的组织方式
链接方式
将相同状态的PCB组织成为一个队列
索引方式
将同一状态的PCB组织在一个索引表中，表项指向相应的PCB
程序段（代码段）
程序可被多个进程共享
数据段
进程加工处理的原始数据
进程的通信
共享存储
消息传递
管道通信
线程
引入线程的目的
减少程序在并发执行时的时空开销，提高操作系统的性能
定义
基本的CPU执行/调度单元，也是程序执行流的最小单元
组成
线程ID：tid
程序技计数器
寄存器集合
堆栈
特点
不拥有系统资源，但有一个唯一对应的标识符，其中记录了线程执行的寄存器和栈的状态
线程不同也可执行相同的程序
同一进程下的各线程共享系统资源
多个线程之间彼此并发执行
线程在生命周期内同样会有就绪、运行、就绪等状态
线程的实现方式
内核级线程
线程管理工作由内核完成，线程调度在内核基于线程框架的基础上完成
用户级线程
内核意识不到线程的存在
多线程模型
多对一模型
将多个用户级线程映射到一个内核级线程上，用户级线程对操作系统不可见
优点线程管理在用户空间进行，效率较高
缺点：当一个线程被阻塞时，映射至该内核级线程的用户级线程都被阻塞
一对一模型
将每个用户级线程映射到一个内核级线程上
优点：当一个线程被阻塞后允许另一个线程继续执行，并发能力强
缺点：创建用户级线程需要内核级线程与之对应，开销大，会影响到系统性能
多对多模型
将n个用户级线程映射至m个内核级线程上
克服两者缺点，拥有两者优点
处理机调度
调度的概念
处理机调度就是对处理机进行分配（按照一定的算法）
处理机调度就是多道程序操作系统的基础，是操作系统设计的核心问题
调度的层次
作业调度（高级调度）
按一定原则将外存上处于后备队列的作业中挑选一个，为期分配系统资源，并使其用于竞争处理机的权利
就是内存与外存间的调度，单个作业只调入一次，调出一次
中级调度（内存调度）
作用是提高内存的利用效率和系统吞吐量
具体操作就是将暂时不能运行的进程调出内存，放入外存中（变为挂起态），从外存中已经具有运行条件的进程调入内存（变为就绪态）
进程调度（低级调度）
按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给他
三调度的层次
作业调度为进程活动做准备
进程调度使进程正常活动起来
中级调度将暂时不能运行的进程挂起，处于作业调度和进程调度之间
作业调度次数少，中级调度次数略多，进程调度频率最高
进程调度使最基础的，不可或缺
不可进行处理机调度的情形
在处理机处于处理中断的过程中时
进程在操作系统内核程序临界区时
其他需要屏蔽中断的原子操作时
需要进行处理机调度与切换的情形
发生引起调度条件且当前进程无法 继续执行下去时
中断处理结束或者自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，则可立刻进行进程调度与切换
内核进行进程调入的操作
从新进程中的内核中装入新进程的现场信息
更新当前运行进程空间指针
重设PC寄存器
进程调度方式
非剥夺调度方式（非抢占式）
剥夺式调度方式（抢占式方式）
经典调度算法
FCFS（先来先服务）调度算法
不可剥夺算法
特点
算法简单，实现容易
对长作业有利，对短作业有利
有利于CPU繁忙作业，不利于I/O繁忙作业
SJF（短作业）优先
特点
对长作业不利
未考虑作业的紧迫程度，不能保证紧迫性作业会被及时处理
SJF调度算法的平均等待时间，平均周转时间最少
不一定能真正做到短作业优先调度
优先级调度算法
是否剥夺
剥夺式
非剥夺式
优先级是否可变
静态优先级
动态优先级
高响应比优先调度算法
计算就绪队列中每个作业的相应比，选取相应比最高的作业投入运行
要求服务时间越短，相应比越高，有利于短作业
作业的响应比由其等待时间决定，等待时间越久，其相应比越高，某种程度上是先来先服务
兼顾长作业
时间片轮转调度算法
剥夺式算法
适用于分时系统
被剥夺的进程返回就绪队列的队尾，重新排队
在时间片足够大时，退化为先来先服务
若时间片过短，处理机切换频繁，拖慢系统速度
时间片长度的决定因素
系统响应时间
就绪队列中的进程数目
系统的处理能力
多级反馈队列调度算法（融合了前几种算法优点）
优势
终端型作业用户：短作业优先
短批处理作业用户：周转时间短
长批处理用户：经过前面几个队列得到部分执行，不会长期得不到执行
进程同步
临界资源
多个进程可以共享系统中的各种资源，但在同一时刻只能有一个进程使用，一次仅允许一个进程使用的资源称为临界资源
对临界区资源的访问过程
进入区
临界区
退出区
剩余区
死锁
死锁的概念
程序在并发执行过程中因相互竞争资源造成的一种互相等待的情形，若无外力作用，这些进程都将无法向前推进
死锁产生的原因
系统资源的竞争
进程的推进顺序非法
死锁产生的四个必要条件
互斥
不剥夺
请求并保持
循环等待
死锁的处理策略
死锁预防
破坏互斥条件（不可行）
破坏不剥夺条件
保持某些不可剥夺资源的进程在申请新的资源得不到满足时，释放已经拥有的资源，待将来再申请
反复申请资源造成系统开销增大，降低吞吐量
通常用于状态已于保存的资源，譬如内存空间，一般不可用于打印机之类的资源
破坏请求并保持条件
一次性申请全部资源
系统资源被严重浪费，部分资源可能仅在运行初期或者末期才使用，甚至根本不使用
可能导致饥饿现象
破坏循环等待条件
采用顺序资源分配法
按编号递增的顺序请求资源同类资源一次性申请完
资源编号必须相对稳定
限制了新类型设备的增加
也会发生作业使用资源顺序与系统规定顺序不同的情况，造成资源的浪费
给编程造成负担
死锁避免
在资源动态分配过程中，防止系统进入不安全状态
系统安全状态
指系统按某种进程推进顺序为每个进程Pi分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序完成；此进程推进顺序称为安全序列
并不是所有的不安全状态都是死锁状态；
只要系统处于安全状态便不会进入死锁状态
银行家算法
进程运行之前先声明对各种资源的最大需求量
当该进程在执行过程中继续申请资源时，先测试该进程已占用的资源和本次申请资源数量之和是否超过该进程声明的最大需求量；超过则拒绝
若未超过则再测试系统现存的资源是否能满足该进程尚需的最大资源量，若能满足则按当前申请量分配资源，否则也需推迟分配
死锁的检测与解除
若系统在为进程分配资源时不采取任何措施，则应该提供死锁检测和解除的手段
资源分配图
死锁定理
死锁解除
资源剥夺法
撤销进程法
进程回退法
内存管理
内存管理概念
内存管理的基本原理和要求
操作系统对内存的划分和动态分配
内存管理的功能
内存空间的分配与回收
地址转换
内存空间的扩充
存储保护
程序的装入和链接
编译
链接
装入
程序的链接方式
静态链接
装入时动态链接
运行时动态链接
程序的装入方式
绝对装入
可重定位装入
动态运行时装入（动态重定位）
逻辑地址空间和物理地址空间
相对地址
逻辑地址空间
物理地址
内存保护
CPU中设置上下限寄存器（两个）每当CPU进行访存时都与两寄存器相比较，判断是否越界
采用重定位寄存器（也称基址寄存器）和界地址寄存器（也称限长寄存器），重定位寄存器保存最小的物理地址，限长寄存器保存最大的逻辑地址，每个访存地址必须小于界地址寄存器
连续分配管理方式
单一连续分配
将内存地址空间分为用户区和系统区
简单无外部碎片、可采用覆盖技术，不需要额外技术支持
只可用于单用户、单任务的状态，有内部碎片，存储器利用率极低
固定分区分配
将用户内存空间分为若干固定大小的区域，每个分区只装入一道作业；当有空闲分区时，便可再从外存的后备作业队列中选择适当大小的作业装入该分区
两种分区方法
分区大小相等
分区大小不等
分区方式存在的问题
程序可能太大而放不进任何一个分区中，此时需要采取覆盖技术来使用内存空间
主存利用率低，当程序小于固定分区大小时也占用一个内存分区空间，产生内部碎片
特点
可用于多道程序的最简单存储分配，无外部碎片
不能实现多进程共享，存储效率低
动态分区分配
不预先划分内存，在程序装入时，根据进程大小动态地建立分区，并使该分区的大小正好适合进程的需要
随着多道程序运行会导致内存中出现外部碎片，内存的利用率随之下降
分配策略
首次适应算法
最佳适应算法
最坏适应算法
邻近适应算法
非连续分配管理方式
基本分页存储管理方式
将主存空间划分为大小相等且固定的块；块相对较小，作为主存的基本单位
将进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间
分页存储的几个基本概念
页面和页面大小
地址结构
页表
基本地址变换机构
进程在执行时；该进程的页表起始地址存在页表寄存器中；不在执行时；页表起始地址存在PCB中；
流程
计算页号P（P = A/L）和页内偏移量W（W = A%L）
比较页号P和页表长度M， 若P>=M，则产生越界中断，否则继续执行
页表中页号P对应的页表地址 = 页表始址F + 页号P x 页表项长度，取出该页表项内容b，即为物理块号
计算E = b x L +W，用得到的物理地址E去访问内存
要求
地址转换必须足够快，否则访存速度会降低
页表不能太大，否则内存利用率会降低
具有快表的地址变换机构
相联存储器（TLB）
存放当前访问的若干页表项，用以加速地址变换的过程
变换过程
CPU给出逻辑地址后，由硬件进行地址转换，将页号送入高速缓存寄存器，并将此页号与快表中的所有页号进行比较
若找到匹配的页号，说明所要访问的页表项在快表中，则直接从中取出该页对应的页框号，与页内偏移量拼接形成物理地址
若未找到，则需访问主存中的页表；并同时将取出页表项存入快表
多级快表
建立多级页表的目的在于建立索引，以便不用浪费主存空间去存储无用的页表项，也不用盲目的顺序式查找页表项
基本分段存储管理方式
分段
段表
地址变换机构
段表寄存器
变换过程
从逻辑地址A中取出前几位为段号S，后几位为段内偏移量W
比较段号S和段表长度M,若S>=M，则产生越界中断，否则继续执行
段表始址F+段号S x段表长度取出该段表项的前几位得到段长C若段内偏移量>=C，则产生越界中断；否则继续执行
取出段表项中该段的始址b， 计算E = b + W，得到实际物理地址E去访存
段的共享与保护
存取控制保护
地址越界保护
段页式管理方式
先将作业的地址空间分为若干段，每段都有段号；再将每段分为大小固定的页
每个段有一个段表；每个分段有一个页表。
虚拟内存管理
虚拟内存的基本概念
传统存储管理方式的特点
一次性
驻留性
局部性原理
时间局部性
空间局部性
虚拟存储器的定义和特征
多次性
对换性
虚拟性
虚拟内存技术的实现
实现方式
请求分页管理方式
请求分段管理方式
请求段页式管理方式
所需支持
一定容量的内存和外存
页表机制（或段表机制）
中断机构
地址变换机构
请求分页管理方式
页表机制
子主题
缺页中断机制
地址变换机构
页面置换算法
最佳（OPT）置换算法
先进先出（FIFO）算法
最近最久未使用（LRU）算法
时钟（CLOCK）算法
页面分配策略
驻留集大小
调入页面的时机
从何处调入页面
抖动
子主题
0 条评论
下一页
