操作系统复习

Posted by Mr.Be1ieVe on Monday, January 13, 2020

对不起我看吐了,考炸了

操作系统的目标

方便性,有效性,可扩充性和开放性

可扩充性:采用微内核结构 P30

发展主要动力

  • 不断提高计算机资源利用率
  • 方便用户
  • 器件的更新换代
  • 体系结构的发展
  • 新的应用需求

多道程序设计的基本概念

利用I/O操作的空闲时间,调度B程序运行,B空闲调度C等 P8

优缺点

  • 资源利用率高
  • 吞吐量大
  • 平均周转时间长
  • 没有交互能力

==操作系统定义为:一组能有效组织和管理硬件和软件资源,合理进行调度,方便用户使用程序的集合==

分时系统(The Sharing System)

在一台主机上连接多个终端,允许多个用户同时通过终端以交互方式使用计算机,共享主机资源

特征

  • 多路性
  • 独立性
  • 及时性
  • 交互性

基本特性

有并发,共享,虚拟,异步四个基本特征

并行与并发

并行:多个程序同时执行

并发:分时交替执行(为主)

进程

指在系统中可以独立运行并且是资源分配的基本单元

共享

互斥共享方式和同时访问方式

虚拟

(没有那么多但感觉有那么多)

  • 时分复用技术 (空闲时给其他用户服务
  • 空分复用技术 (储存器空闲时存储和运行程序

异步

(同时开始,不同时结束)

进程以不可预知的速度进行

存储器管理功能

  • 内存分配
  • 内存保护
  • 地址映射
  • 内存扩充

OS结构设计

第一代无结构OS,第二代模块化OS,第三代分层式OS

进程

PCB进程控制块(Process Control Block)

定义:

  • 进程的程序的一次执行
  • 进程是一个程序及其数据 顺序执行的活动
  • 进程是系统进行资源分配的独立单元

特性

  • 动态性
  • 并发性
  • 独立性
  • 异步性

进程状态转换

==P42-43==

操作系统内核

处理机两种执行状态:系统态和用户态

进程同步

临界资源-生产者消费者问题

设置临界区

  • 进入区 判断资源是否被访问
  • 临界区
  • 退出区 将正被访问标志恢复为未被访问
  • 剩余区

同步规则

  • 空闲让进
  • 忙则等待
  • 有限等待 有限时间内能访问
  • 让权等待 不能进入则释放处理机

利用信号量实现进程互斥

设mutex为互斥信号量,=1都未进入临界区,=0有一个进入运行,另一阻塞。= -1有一正在运行,另一等待。

线程

调度和分派的基本单位,能独立运行的基本单位

切换时仅保存和设置少量寄存器内容,切换代价远低于进程

处理机调度层次

高级调度

调度对象是作业,多用于多道批处理

低级调度

决定就绪队列哪个进程获得处理机

中级调度

提高内存利用率和系统吞吐量(把暂时不运行的进程调至外存,此时进程状态为就绪/挂起状态)

公式

CPU利用率

CPU利用率 = CPU有效工作时间/(CPU有效工作时间 + CPU空闲等待时间)

平均周转时间

T = 1/n(T1+T2 ······ +Tn)

平均带权周转时间

W = 1/n(作业周转时间Ti/提供服务Ts + ······ ) i=1,2,3,4…..

系统吞吐量大

与作业平均长度有关,单纯提高吞吐量可选择多的短作业运行

分时系统目标

  • 响应时间快
  • 均衡性(相应快慢和请求的复杂性相适应)

实时系统目标

  • 截止时间的保证
  • 可预测性

作业调度算法

FCFS(First Come First Server)先来先服务

SJF (Short Job First) 短作业优先

PSA (Priority-Scheduling Algorithm) 优先级调度算法

基于作业紧迫程度

HRRN (Highest Response Ratio Next) 高响应比优先调度算法

优先权 = (等待时间 + 要求服务时间) / 要求服务时间

RR ( Round Robin) 基于时间片的轮转调度算法

EDF (Earliest Deadline First) 最早截止时间优先算法

LLF (Least Laxity First) 最低松弛度算法

松弛度 = (必须完成时间 - 本身运行时间 - 当前时间)

死锁

定义

一组进程中每一个进程都在等待只有其他进程才能引发的时间

必要条件

  • 互斥条件
  • 请求和保持条件
  • 不可抢占条件
  • 循环等待条件

银行家算法 P121

判断 需求是否小于等于需要的

判断 需要是否小于等于可用的

模拟分配并检测是否有安全序列

磁盘缓存

在内存中暂存磁盘中读出的数据

固定分区分配

  • 相等

  • 不相等 建立表,记录分区信息

动态分区分配

常见数据结构:

  • 空闲分区链
  • 空闲分区表

空闲分区分配算法

FF (First Fit) 首次适应

从头找,找到空间再划分内存给作业

NF (Next fit) 循环首次适应

从上一次查找到的空闲区的下一个开始查找

BF (Best Fit) 最佳适应算法

把能满足要求、最小的空闲区分配,但碎片很多

WF (Worst Fit)最坏适应算法

总挑选最大的空闲区进行分配

优点 剩下的空闲区不至于太小 查找效率高

分页储存

分页储存

页面和物理块

用户程序的地址空间分为若干区域,成为页。

内存中同样划分,成为块

地址结构:

高20位 页号 低12位 位偏移量

页表

记录页在内存中对应的物理块号

分段管理

编程需要:

  • 信息共享
  • 信息保护
  • 动态增长
  • 动态链接

作业地址被分为多个段,所以呈现出二维特性

分段地址:

高16位 段号 低16位 段内地址

段表

各个段离散的放入内存不同分区中,需要为每个进程建立段映射表

实现从逻辑段到物理内存区的映射

虚拟存储器定义

具有请求调入和置换功能,从逻辑上对内存扩充的存储器系统

特征

  • 多次性 分多次装入内存
  • 对换性
  • 虚拟性

页面置换算法

Optimal 最佳置换算法

预测最久不使用的页并进行替换。

FIFO 先进先出页面置换算法

总淘汰最先进入的(驻留最久的)

LRU (Least Recent Used) 最近最久未使用

选择最近最久未使用的页面

LRU和OPT,加物理块数不会增加缺页次数,FIFO不一定能减少缺页次数

抖动

原因

运行的进程太多,频繁出新缺页,进程大部分时间都用于页面的换进换出

预防

  • 局部置换策略 只在分配给自己的内存中置换

请求分段储存管理

共享段表

分段保护

  • 越界检查
  • 存取控制检查
  • 环保护机构 类似系统的内核等级

I/O基本功能

  • 方便用户使用
  • 提高CPU和IO设备利用率
  • 共享设备时提供方便

中断处理程序

  • 测定是否有未响应的中断信号
  • 保护被中断进程的CPU环境
  • 转入相应的设备处理程序
  • 中断处理
  • 恢复CPU现场并退出中断

图p206

DMA控制器

主机-控制器接口

  • DR 数据寄存器
  • MAR 内存地址寄存器
  • DC 数据计数器
  • CR 命令/状态寄存器

DC,MAR,CR获得从CPU传来的数据和命令,DR获取数据,并传入MAR

设置MAR和DC初值 -> 启动DMA -> 使用存储器周期传送数据 -> 存储器地址+1,DC-1 -> 循环

若DC = 0 请求中断

与设备无关IO

  • 以物理设备名使用设备 不灵活,利用率也不高
  • 逻辑设备名

设备控制表DCT

  • 设备类型
  • 设备标志符
  • 设备状态
  • 指向控制器表的指针
  • 重复执行次数或时间
  • 设备队列的队首指针

控制器控制表COCT

记录控制器情况

LUT (Logical Unit Table) 逻辑设备表

逻辑设备名 | 物理设备名 | 驱动程序入口地址

/dev/tty | 3 | 1024

逻辑设备表 | 系统设备表指针

/dev/tty. | 3

缓冲

CPU和IO设备速度不匹配

利用缓冲寄存器暂存数据

磁盘调度算法

FCFS

SSTF (Shortest Search Time First) 最短寻道时间优先

基于扫描的磁盘调度

SCAN 扫描算法 又称电梯调度算法

要访问的磁道与刺头当前距离较近

文件结构

文件逻辑结构

文件由一系列逻辑记录组成,是可以直接处理的数据及其结构,独立于文件的物理特性,又称文件组织

物理结构

对磁盘管理器的要求

  • 有效地利用存储空间
  • 提高磁盘IO速率
  • 提高磁盘系统可靠性

外存组织方式

  • 连续
  • 链接
  • 索引

链接组织方式

显式 表中放指针,链表、隐式 链表

FAT

分成卷

一个磁盘可多个卷,一个卷可由多个磁盘组成

文件第一个盘号放在FCB中,FAT每个表项最后放下一个盘块号

是一组相邻的上去,作为虚拟扇区。盘块分配时以簇为基本单位

好处:能适应磁盘容量不断增大的情况,还可减少FAT表中项数

文件储存空间管理

空闲表法

给每个文件分配连续存储空间。

系统也会为外存空闲区建立空闲表

位视图法

二位数组模样,m*n=磁盘总块数

「真诚赞赏,手留余香」

Mr.Be1ieVe's Treasure

真诚赞赏,手留余香

使用微信扫描二维码完成支付