知识体系 标签 归档 友链 关于 RSS
- 目录 -
计算机操作系统原理笔记
操作系统快考试了，我觉得自己过应该还是没问题的吧，毕竟也有认真听课。虽然对某些部分流程记忆有点发憷。
folder 笔记   label 操作系统   笔记   schedule 48 min 44 s.

操作系统快考试了，我觉得自己过应该还是没问题的吧，毕竟也有认真听课。虽然对某些部分流程记忆有点发憷。

操作系统做什么

操作系统是用户与计算机硬件之间的接口

用户 指包括最终用户在内的各级用户。

操作系统的发展

微机操作系统

个人机操作系统。

实时操作系统

支持实时计算的系统，实时计算即 系统的正确性不仅取决于计算的逻辑结果，而且还依赖于产生结果的时间。

实时任务的类型

  1. 周期性实时任务
  2. 非周期性实时任务
  3. 硬实时任务
  4. 软实时任务

实时计算机可以不运行实时操作系统，直接运行应用软件

  • 高可用性
  • 截止时间
    • 开始截止时间
    • 实际截止时间

单道批处理系统

  1. 自动性
  2. 顺序性
  3. 单道性

优点

减少人工等待时间

缺点

  • 作业独占CPU
  • CPU等待IO使得CPU利用率低

多道批处理系统

  • 多道性
  • 无序性
  • 调度性
  • 复杂性

优点

  1. 提高CPU利用率
  2. 提高内存和IO利用率
  3. 增加系统吞吐量

吞吐量：单位时间里系统处理的作业量 缺点

  1. 平均等待周期长
  2. 缺乏交互能力

分时系统

  1. 多路性
  2. 独立性
  3. 及时性
  4. 交互性

优点

  1. 提供人机交互
  2. 多终端共享主机

关键问题

  1. 及时接收用户的命令和顺序
  2. 及时处理用户的命令。 使所有的用户作业都进入内存，在很短的的时间内使每个作业都运行一次

操作系统产品现状

嵌入式操作系统

嵌入式系统 是宿主于非计算机设备的操作系统。 嵌入式操作系统 是运行于嵌入式系统中的操作系统。

掌上计算机操作系统

PDA

实时操作系统

在资源调度、中断处理等方面的设计和实现要充分考虑系统对时间都限制。应用领域如 自动控制、军事指挥系统、民用航空管理等

与嵌入式系统在分类上有一定重叠，有一定时限要求，在设计和实现上也有一些共同的特点， 专用性、规模小、实时性、高可靠性 。

操作系统的特征

支持多任务的操作系统

  • 并发 同一时间间隔执行多个任务
  • 共享
  • 虚拟
  • 异步

操作系统功能

  • 内存管理功能
  • 进程管理功能
  • 设备管理功能
  • 文件管理功能
  • 用户接口

内存管理功能

内存分配
内存保护

每个进程在自己的进程空间。

界限寄存器

地址映射

地址映射是硬件和操作系统配合完成的。 把进程的逻辑地址转换成内存上的物理地址。

逻辑地址 ：程序中的地址是从某一地址开始，相对于起始地址计算的，称为逻辑地址。

物理地址 由内存中的一系列单元所限定的地址范围称为 内存空间 ，其中的地址被称为物理地址。

obj文件中逻辑地址是从0开始的，exe中的不是。 编译系统形成逻辑地址原因：编译器并不知道操作系统会将程序载入内存的实际物理地址。 中断发生时，保存现场，PC的值已经指向下一条指令，待中断返回时继续执行下一条指令。 变长指令集，PC+1时根据当前指令的长度决定PC递增的值

内存扩充

虚拟技术。

内存回收

将进程占据的内存空间标记为空闲。

OS内核：在特权集下运行的程序。（除此之外，还有接口，在非特权集运行，如shell）

进程管理功能

  • 进程控制
  • 进程同步
  • 进程通信
  • 进程调度

设备管理

  • 缓冲管理：管理各种缓冲区
  • 设备分配：分配用户IO需要的设备
  • 设备处理：由设备驱动程序实现CPU与设备控制器之间的通信
  • 设备独立性
  • 虚拟设备：应用程序无需关注设备品牌等细节

文件管理功能

  • 文件等按名访问
  • 文件等存储

提供用户接口

shell运行于用户态。

  • 命令接口
  • 图形接口：采用图形化的操作界面
  • 程序接口：由一组系统调用组成

软件的体系结构

为什么要研究软件的体系结构

使软件模块更清晰，提高开发效率，更好测试、维护和移植，（提高软件运行的速度）。

操作系统的体系结构

  • 微内核优点：移植性好
  • 缺点：运行效率低一点

指令的执行

取指令与执行指令

取指令

每个指令周期开始时，处理器从内存中取一条指令。程序计数器PC保存有下一次要取的指令的地址。取指令后PC递增。

执行指令

取到的指令放置于IR中，处理器解释指令并执行动作。

一条语句常对应多条指令。 程序执行过程反复取指令执行指令（硬件完成） 指令执行结果是使寄存器或内存单元值变化 保存现场（硬件隐指令）不需要保存内存的内容。内存有隔离措施，保证中断后内存内容不变。恢复现场由操作系统完成（恢复AC等值）。 隐指令：在机器指令系统中没有的，对用户来说是不可见的，完成特定功能的指令，如中断隐指令。

进程同步

操作系统快考试了，我觉得自己过应该还是没问题的吧，毕竟也有认真听课。虽然对某些部分流程记忆有点发憷。 [tag]:操作系统|笔记

进程同步的基本概念

进程同步的任务：

  1. 在资源共享的情况下：保证诸进程以互斥方式访问
  2. 在相互合作的情况下：保证诸进程协调执行。相互合作进程可能存在资源共享的情况。
  • 临界资源：必须以互斥方式访问的共享资源。
  • 临界区：每个进程总访问共享资源的那段代码
  • 进入区：检查是否可以进入“临界区”并对临界区“加锁”的代码
  • 退出区：释放临界区访问权的代码

同步机制应遵循准则

  1. 空闲让进
  2. 忙则等待
  3. 有限等待
  4. 让权等待

整型信号量机制

整型信号量

整型信号量是表示共享资源状态 只能由特殊的原子操作(wait和signal)改变 的整型量。

整型量>0说明有可用资源。

wait和signal操作（P－V操作）

var s:integer;
wait(s){
	while s<=0 do no-op;//申请不到资源做空操作
	s=s-1;
}
signal(s){
	s=s+1;
}

思考：开关中断应该怎样加？

整型信号量应用举例

临界资源由程序员界定，需要为每种临界资源分别定义一种互斥信号量。

缺陷：不能实现让权等待。

记录型信号量机制

数据类型

Type semaphore=record
	Value:integer//资源数量
	L:list of process//阻塞队列（PCB）
end

考：记录型信号量、wait和singial操作

wait和signal操作

prodcedure wait(s)
	var s:semaphore;
	begin
		s.value=s.value-1;
		if s.value<0 then block(s.L);
	end
procedure signal(s)
	var s:semaphore;
	begin
		s.value=s.value+1;
		if s.value<=0 then wakeup(s.L);
	end

被阻塞的是调用wait申请资源的进程（自我阻塞）。

利用记录型信号量实现互斥

var s:semaphore;
	s.value=1;
begin
	repat
		wait(s);
			critical section;
		signal(s);
		reminder section;
	until false;
end

先唤醒哪个进程取决于操作系统，如果使用优先权，尽量不使用静态优先权。

利用记录型信号量实现“协调”的应用举例

设置两个信号量var empty,full:semaphore

初始：empty.value=2,full.value=0

输入进程：
{
	从外存读数据;
	wait(empty)
	往缓冲区放数据
	signal(full)
}
计算进程：
{
	wait(full);
	从缓冲区读取数据
	signal(empty)
	处理数据
}

管程

管程由编译器提供支持。

进程调度

操作系统快考试了，我觉得自己过应该还是没问题的吧，毕竟也有认真听课。虽然对某些部分流程记忆有点发憷。 [tag]:操作系统|笔记

操作系统的进程调度功能由进程调度程序完成 什么时候操作系统会进行进程调度？

进程阻塞 时间片用完 程序正常或异常结束 中断返回 高优先权进程到来

调度算法

周转时间=服务时间+等待时间

平均周转时间=总周转时间/进程数

带权周转时间=服务时间/等待时间

平均带权周转时间=总带权周转时间/进程数

立即抢占：高优先级进程立即执行的最小时间单位可以是每执行完一条指令。

先来先服务（FCFS）

适合长作业，不利于短作业。有利于CPU繁忙型作业，不利于I/O繁忙型作业。

短作业（进程）优先

短作业优先SJF

短进程优先SPF

有效缩短作业和进程的平均等待时间，提高系统吞吐量。

缺陷

  1. 对长作业和长进程不利，如果系统中不断有短作业和短进程到来，则长作业及长进程可能长时间得不到调度。
  2. 不能保证紧迫作业和进程的及时处理
  3. 作业和进程的长短由用户的估算，不一定能真正做到短进程或短作业优先

与先来先服务相比，能缩短系统的平均周转时间和平均带权周转时间。

优先权调度算法

实时系统中非阻塞式难以保证高优先权进程得到及时调度，因此主要用于批处理系统。

静态优先权存在进程饥饿问题，使用 老化 技术动优先权避免这个问题。

时间片轮转算法

进程需要在CPU上运行的时间可能小于一个时间片，也可能大于一个时间片。对于进程的时间区间小于一个时间片的情况，进程在CPU上运行结束本身会自动释放CPU，然后由操作系统执行进程调度程序为另一个就绪进程分配CPU；对于进程的时间区间大于一个时间片的情况，进程可能执行若干时间片，每当进程在CPU上连续运行的时间等于一个时间片长度时，操作系统在 时钟中断处理过程 中就会抢占CPU，进行进程切换，用新的就绪进程替代当前进程，而被替换的当前进程则重新回到就绪队列中。

时间片大型的确定

时间片太长，那么进程看上去就不是并发执行的；时间片太短，频繁切换进程上下文影响效率。

在系统允许的最大进程数一定的情况下，时间片的长短取决于系统要求的响应时间，且响应时间越短，时间片取值应该越小。

时间片轮转需要的硬件软件：

硬件：可编程间隔定时器、可编程中断控制器 软件：PCB中记录在CPU上运行剩余时间都字段、时钟中断处理程序、中断处理程序

多级队列调度算法

将就绪队列分为多个独立队列……

课本p100

参考

死锁

操作系统快考试了，我觉得自己过应该还是没问题的吧，毕竟也有认真听课。虽然对某些部分流程记忆有点发憷。 [tag]:操作系统|笔记

产生死锁的原因和必要条件

产生死锁的原因

  1. 竞争共享资源
  2. 进程推进顺序不当

产生死锁的必要条件

  1. 互斥条件 一个进程在访问某资源的过程中，其他进程不能访问该资源
  2. 请求和保持条件 进程提出新的资源请求，被阻塞，但不释放已经保持的资源
  3. 不剥夺条件 进程已经获得的资源不能被剥夺，只能由进程自己释放
  4. 环路等待条件 必然存在一个进程申请资源的环形链，互相等待对方占用的资源

只有上述四个条件同时满足时才会发生死锁。

处理死锁的基本方法

  1. 预防死锁
  2. 避免死锁
  3. 检测并解除死锁
  4. 忽略死锁问题，认为死锁不可能在系统内发生

认为死锁不可能发生是一个经验、统计规律。

死锁的预防

摒弃三个必要条件之一。

摒弃请求和保持条件

系统要求所有进程在执行前要一次性地申请整个运行过程中所需要的全部资源，只要有一个资源申请不成功，其他所有的资源就不分配给该进程,并阻塞该进程。

摒弃不剥夺条件

一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源。

摒弃环路等待条件

规定进程必须按一定顺序申请资源。

参考

死锁的避免

把系统的资源分配状态分为 安全状态 和 不安全状态 ，只要资源分配使系统处于安全状态，死锁就不会发生。

利用银行家算法避免死锁

一个进程提出资源请求后，系统先进行资源的试分配，然后检测本次的试分配是否使系统处于安全状态，若安全，则按试分配方案分配资源，否则不分配资源。

安全状态：能找到一个执行序列分配资源。（满足最大需求后进程释放资源）

系统处于安全状态时， 一定不会发生死锁 ，进入不安全状态 未必会发生死锁 ，发生死锁 一定是进入了不安全状态 。

  1. available[] 是个一维数组，表示系统中某种资源的可用数量。
  2. max[] 是个二维数组，表示各进程需要各类资源的最大数量，如max[i,j]=k表示进程pi需要j类资源的最大数量为k。
  3. allocation[] 是个二维数组，表示某时刻已分配给进程的某类资源数，如allocation[i,j]=k 表示进程pi已经占有j类资源k个。
  4. need[] 是二维数组，表示某个进程还需要多少个某类资源，如need[i,j]=k表示进程pi还需要j类资源k个。

该算法缺乏实用价值，因为很少有进程能够在运行之前就知道其所需资源的最大值，而且进程数不是固定的，往往在不断变化，原本可用的资源也可能在突然之间变成不可用。

死锁的检测和解除

操作系统可以不采取预防和避免的方法来解决死锁问题，而是检测是否有死锁发生，如果检测到系统中有死锁的进程，则解除死锁。

应用检测死锁算法必须面对的问题是 何时调用检测算法 及 如何检测死锁 。 资源分配图：进程指向资源是资源请求边，资源指向进程是资源分配边。

死锁定理用于检测系统所处的 资源分配状态 S是否为 死锁状态 。

S为死锁状态<=>S状态的资源分配图是不可完全简化的

解除死锁的途径有两个：

  1. 终止处于死锁状态的进程
  2. 抢占死锁进程占有的资源

系统中不会出现单个进程死锁的情况，但会出现只有一个进程饥饿的情况。

存储器管理

操作系统快考试了，我觉得自己过应该还是没问题的吧，毕竟也有认真听课。虽然对某些部分流程记忆有点发憷。 [tag]:操作系统|笔记

存储器的层次结构

局部性原理

  1. 程序执行时，除少部分的转移和过程调用外，大多数情况下是按顺序执行的。
  2. 过程调用会使程序的执行轨迹由一部分内存区域转到另一部分内存区域。但研究表明，在大多数情况下过程调用的深度都不超过5，也就是说，程序将会在一段时间内局限在很小的范围内。
  3. 程序中存在很多循环结构，它们虽然由少数指令构成，但需要多次执行。
  4. 程序中往往包括许多对数据结构的处理，它们往往局限在很小的范围内。

少用goto：goto破坏程序的局部性。

程序的装入和链接

高级语言程序必须经过 编译 、 链接 才能为之成为可执行程序，可执行程序必须被操作系统 装入 内存才能执行。

交叉编译：开发平台不同于目标平台。

程序的装入

  • 绝对装入方式

在编译时形成物理地址

  • 可重定位装入方式（静态重定位）

装入时形成物理地址

  • 动态运行时装入方式

运行时形成物理地址（运行时才进行物理映射），逻辑地址在PC中。

需要 重定位寄存器 的支持。

程序的链接

链接要解决的问题

将编译后的目标模块装配成一个可执行的程序。

链接的两种方式
静态链接
  • 静态链接 在程序运行前，用链接程序将目标模块链接成一个完整的装入模块。
  • 静态链接的任务
    • 对相对地址进行修改
    • 变换外部调用符号
  1. 存储开销大
  2. 程序开发不方便
  3. 程序运行相对于动态链接快
动态链接
  1. 节省内存和外存空间
  2. 方便程序开发
  3. 程序运行时的速度变慢

连续存储管理方式

单一连续分配

把内存分为系统区和用户区。

固定分区分配

固定分区分配的 用户分区数量 是固定的， 每个分区的大小 也是固定的，其大小可以相等也可以不想等。

  • 分区编号
  • 分区大小
  • 分区起始地址
  • 分区状态

在PCB中记录分配的分区的起始地址

固定分区的特点

  1. 管理简单
  2. 内存利用率低

记录和维护空闲分区情况数据结构，常用空闲分区表、空闲分区链表。

作业：写一个分配分区的程序，打印版。

动态分区分配

首次适应算法

空闲分区地址递增，链首顺序查找，找出能满足要求的第一个。

  1. 高地址部分大空闲区较多
  2. 低地址部分容易留下小分区
  3. 查找时间开销大
循环首次适应

不再从头开始查找，从上次找到的位置开始查找。

  1. 空闲空间分配均匀
  2. 查找开销较小
  3. 容易使系统缺乏较大空闲分区
最佳适应算法

空闲分区大小递增，返回满足条件，最小的第一个。

  1. 避免大材小用，提高内存利用率
  2. 容易留下难以利用的小空闲区

问题

考虑回收否？ 起始大小、状态 代码行数、链表

回收

修改分区大小，（删除多余的节点）

紧凑

将多个空闲分区拼接成连续大空闲分区。

基本分页管理方式

离散的内存管理方式

  1. 分页存储管理
  2. 分段存储管理
  3. 段页式存储管理

分页存储管理的方式

基本概念
  1. 页 将一个进程的逻辑地址空间分为若干大小相等的片，称为页面或 页
  2. 物理块 将内存空间分成与页相同大小的若干存储块，称为 物理块 或页框或帧
  3. 分页存储 在为进程分配内存时，以块为单位将进程的若干页分别装入多个可不连续的块中
  4. 页内碎片 进程的最后一页一般装不满一块，而形成不可利用的碎片，称为 页内碎片

（一级分页）逻辑地址由页号、页内偏移量构成。

计算关系

32位系统中为高20位页号，低12位页内偏移。

在有关计算题中用二进制或十六进制表示。 页表建立页号和块号联系，但一般不必存页号，用块号顺序表示。

页表在内存中连续存放，列表项长度固定（页表本身长度是页表项项数，页表项长度是页表项占字节数），页表寄存器中存储了页表起始地址和页表长度，由硬件检索页表得到访存实际地址。 一级分页下读数据要两次访存。

地址变换过程
  1. 进程执行，PCB中页表起始地址送页表寄存器
  2. CPU访问逻辑单元a
  3. 由分页地址变换机构自动将a分为页号和页内偏移
  4. 由硬件检索机构搜索页表，得到物理块号

得到物理地址后，先查看高速缓存，如果命中直接取，未命中则去内存找。 页大小的选择

由机器的体系结构决定，亦由硬件决定

页太小，进程所需页多，页表太长，占用大量内存空间；降低页换入换出效率。

页太大，页内碎片大，内存利用率低。

  • 页的大小是2的幂
  • 一般页大小在512B~4K
  • 现在硬件可以支持多种不同的页大小

快表

快表是为了提高CPU访存速度而采用的专用缓存，用来存放 最近被访问过的页表项

有效减少访问页表时间。

  • TLB命中，1次访问TLB时间+1次访问内存的时间
  • TLB不命中，1次访问TLB时间+2次访问内存的时间

TLB每CPU一个。

两级和多级分页

页表寄存器中的值是外层页表的起始地址。

二级分页中TLB存放什么？ 外层页号、页表分页、进程页面

减少页表占用内存的方法：将当前所需要的页表和外层页表放在内存中，其余页表分页放在外存中，当所需的分页不在内存时，产生中断，将请求的页表调入内存。

分段存储管理

  • 段的逻辑地址
    • 段号
    • 段内偏移

段表

  1. 页是按物理空间划分的，段是按逻辑空间划分的
  2. 页大小固定，段大小不固定
  3. 分页地址空间是一维的，程序员给出的只是一个助记符

虚拟内存管理

操作系统快考试了，我觉得自己过应该还是没问题的吧，毕竟也有认真听课。虽然对某些部分流程记忆有点发憷。 [tag]:操作系统|笔记

虚拟存储器概述

  1. 提高内存利用率
  2. 提高多道程序度
  3. 把逻辑空间和物理空间分开

虚拟存储系统具有以下主要特征：

  1. 离散型
  2. 多次性
  3. 对换性
  4. 虚拟性

请求分页存储管理方式

运行过程中访存，若发现所访问的页面不在内存中，则产生一个缺页中断信号，系统响应缺页中断，请求调入缺页。若调入缺页时内存已满，则需要先从内存中选择一个或若干个页面换出到外存空间，以腾出内存空间容纳请求调入的缺页。

系统通常不会等缺页中断再选择一页换出，而是有一个最小阈值，定期扫描

请求分页中的硬件支持

页表机制
  • 页号 作为地址映射时的索引
  • 物理块号 页面在物理内存中的物理块编号
  • 状态位P 用来标识页面是否在内存中
  • 访问字段A 用来记录页面最近被访问的情况
  • 修改位M 用于标识页面最近是否被修改过
  • 外存地址 用于指出页面在外存的地址
缺页中断机构

在访存过程中发现缺页时产生的缺页中断信号，使CPU中断当前控制流的执行，转去执行操作系统的缺页中断处理程序。

  1. 通过检查页表的存在位P，判断当前被访问的页是否在内存中，如果不在，则产生缺页中断信号。
  2. 在内存中为请求调入的页找一个空闲物理块
  3. 调磁盘操作，把需要的页装入找到的空闲物理块中
  4. 修改页表，更新已经调入页的存在位、在内存中的物理块号、访问位等字段的值
  5. 重新执行因缺页而被中断的指令
地址变换机构
  1. 由内存地址变换机构从线性逻辑地址中分离出页号和页内偏移地址
  2. 以页号作为索引查找快表，若快表中存在该页的页表项，则读出物理块号，计算物理地址
  3. 若快表中不存在该页的信息，则转到内存页表中查找。若页表中状态位P显示该页已经调入内存，则从响应的页表项读出页面所在的物理块号并计算物理地址，然后把该页表项写入快表
  4. 若该页尚未调入内存，则产生缺页中断，请求OS把该页从外存中调入内存，然后修改页表，重新执行被中断的指令。

缺页中断一定产生于指令执行的过程中。缺页中断返回时执行原指令，而不是下一条指令。

页面分配

最少物理块数

最少物理块数是指能保证进程正常运行所需要的最少物理块数。保证进程正常运行所需要的最少物理块数与 进程的大小 无关，与 计算机的硬件结构 有关，取决于指令的 格式 、 功能 和 寻址方式 。

指令本身涉及的页面、操作数部分的地址涉及的页面、操作数地址中存在的内存地址中可能涉及的地址……

页面分配和置换策略
  1. 固定分配局部置换
  2. 可变分配全局置换 广泛使用
  3. 可变分配局部置换
分配算法
  • 平均分配算法
  • 按比例分配算法
  • 考虑优先权的分配算法

页面调入策略

当系统产生缺页中断时，调入请求页面的同时可以只把该页面进入内存，也可以同时把与该页相邻的页面调入内存。外存页面既可以存放在对换区，也可以存放在文件区。

页面置换算法

页面置换算法是选择淘汰页的算法。

最佳置换算法

选择以后永远不会被访问的页面或最长时间不会再访问的页面。

先进先出页面置换算法

选择进入内存最早的页面淘汰。

最近最久未使用置换算法

将最近最久未使用的页面予以淘汰。

实现：

寄存器

为每个内存中的页面配置一个移位寄存器，访问时最高位1，定时右移寄存器，最小数值的最久未使用。

栈

访问时把页面号移出，压入栈顶，栈底为最久未使用的页面。

计数器

为每个页表项增加时间字段……

LRU的近似算法

附加引用位算法

类寄存器方法。

简单Clock算法

为每一页设置一位访问位，再将内存中的所有页面通过链接指针链接成循环队列。某页被访问时，访问位置1。按FIFO算法检查访问位，若为0，选择换出；若为1，重新置0，暂不换出。

只考虑访问位，未考虑修改位。

改进型Clock算法

A=0，M=0 最佳淘汰页 A=0，M=1 并不是很好的淘汰页 A=1，M=0 已访问，未修改 A=1，M=1 已访问，已修改

  1. 寻找A=0 M=0的，选中第一个
  2. 第一步失败，寻找A=0，M=1的，选中第一个。所有经过的A置0
  3. 回到开始位置，并将所有访问位A复0，重复第一步，失败则重复第二步

其他置换算法

最少使用置换算法

选择最近时期使用次数最少的页面作为淘汰页。

实际实现与LRU通常相同。

页面缓冲算法

采用FIFO算法选择淘汰页，建立两个链表 空闲页面链表、已修改页面链表。

没有被修改页面换出时实际不把它换出内存，而是把该页所在的物理块挂在空闲页链表的尾部。置换已修改页面，挂在已修改页面链表尾部。

一般与其他分配算法配合使用。 缺页中断处理的性能受不受页缓冲机制的影响？ 受影响，因为如果引入缓冲机制，缺失的页在内存中，就不必再到外存寻找，会加快处理速度。

请求分页系统性能分析

缺页率对有效访问时间的影响

工作集

把最近访问的页全部装入内存

W(t,Δ) 工作集的窗口

Δ为窗口尺寸，Δ太大，影响存储器利用率

Δ太小，缺页率高，影响系统的吞吐量

抖动

多道程序度太高，使运行进程大部分时间都用于页换入换出，几乎不能完成任何有效工作的状态称为 抖动

预防

  1. 采用局部置换策略 进程缺页时，仅在自己内存空间范围置换页面
  2. 在CPU调度程序中引入工作集算法 只有当每个进程在内存中都有足够大驻留集时，才能从外存调入新的作业
  3. L=S准则 调整多道程序度，以使发生缺页的平均时间L=系统处理缺页的平均时间S
  4. 挂起若干进程 预防抖动，挂起若干进程，腾出进程占用的空间

文件系统

操作系统快考试了，我觉得自己过应该还是没问题的吧，毕竟也有认真听课。虽然对某些部分流程记忆有点发憷。 [tag]:操作系统|笔记

文件命名

文件命名向用户提供文件访问的抽象机制。

  • 大小写
  • 文件扩展名

文件结构

无结构字节序列

也称 流式文件 ，操作系统不关心文件的内容是什么，它所见到的就是字节，含义由使用文件的程序自行理解。

固定长度记录序列

构成文件的基本单位是具有固定长度的记录，每个记录都有其内部结构。读操作返回一个记录，写操作返回或追加一个记录。

树形结构

文件由一颗记录树构成，记录长度不变，在记录的固定位置包含一个关键字域，记录树按 关键字域 排序。基本操作是获取具有特定关键字的记录。增加记录时，由操作系统决定记录在文件中的存放位置。

文件类型

文件的类型有 正规文件 、 目录文件 、 字符设备文件 、 块设备文件 等。正规文件包含用户信息，一般分为 ASCII文件 和 二进制文件 。

ASCII文件

由多行正文组成，在某些系统中，每行用 回车符 结束，某些则用 换行符 结束，有些系统还同时采用回车符和换行符。

优势

  • 可以显示和打印
  • 可以使用通常的文本编辑器进行编辑
  • 程序使用ASCII文件输入输出可以很容易把一个程序的输出当做另一个程序的输入。
二进制文件
  • 具有一定的内部结构，只有使用该文件的程序才了解这种结构。
  • 通常的编辑器不能直接显示和打印二进制文件
  • 不同的操作系统可以识别不同的二进制文件，把某一种结构的二进制文件作为系统中的可执行文件。

文件存取

用户通过对 文件的存取 完成对文件的各种操作。文件的存取方式是由 文件的性质和用户使用文件的情况 来确定的。

  • 顺序存取
  • 随机存取

定长记录的文件能很好地支持随机存取，而变长记录虽然可以随机存取，但实现起来复杂且存取速度慢。

文件操作

使用文件的目的是存储信息，方便以后的检索。

  1. CREATE
  2. DELETE
  3. OPEN 使用文件之前，必须先打开文件。OPEN调用的目的是将 文件属性和磁盘地址表 装入主存，以便后续调用的快速存取。
  4. CLOSE
  5. READ
  6. WRITE
  7. APPEND
  8. SEEK
  9. GETATTRIBUTES
  10. SETATTRIBUTES
  11. RENAME

目录

文件系统通常提供目录用于记录文件，在很多系统中目录本身也是文件。目录的数量对应文件的数量。

层次目录结构

目录文件的结构

2^n个扇区叫做一个簇，作为文件分配的最小单位。文件系统按名访问时需要簇号。

文件名 地址信息（簇号）

地址信息在MS－DOS系统中是起始簇号，在unix是i节点所在簇号。

  • 单层目录
  • 双层目录 一个用户一个目录
  • 目录树

路径名

实现文件

连续分配是将文件作为连续数据存储在磁盘上。

优点：简单易实现，性能好，一次操作可读出整个文件

缺点：无法事先知道该为文件分多少空间，文件长度会变，造成磁盘碎片。

链接表分配是为每个文件构建磁盘块的链接表，每个块的第一个字用于指向下一块的指针，块的其他部分存放数据

优点：磁盘空间利用率高，管理简单

缺点：随机存取的速度慢

使用索引的链接表分配使用链接表实现文件，取出文件名和地址信息作为索引表。

目录结合FAT表 FAT12

FAT文件系统目录结构、FAT表结构作用、如何实现按名访问、数据结构与单个文件管理的最大长度的关系。

  • FAT12采用12位文件分配表，磁盘块大小为2KB
  • 则FAT12可以管理的磁盘容量为8M
  • FAT12文件系统文件名：只能是8.3格式的文件名

实现目录

问：有目录dir，其下有100B的a.txt，问占用磁盘空间。

答：两个簇，因为一个簇不会比512B更小。

UNIX中的目录

磁盘空间管理

块大小

太大浪费空间，太小浪费时间

记录空闲块
  • 空闲磁盘块链表
  • 位图

I/O设备管理

操作系统快考试了，我觉得自己过应该还是没问题的吧，毕竟也有认真听课。虽然对某些部分流程记忆有点发憷。 [tag]:操作系统|笔记

I/O系统的组成

I/O系统不仅包含各种I/O设备，还包含于设备相连的设备控制器，有的系统亦配备了专门用于输入输出控制的专业计算机 通道 。

I/O系统的结构

  1. 微机I/O系统
  2. 主机I/O系统

I/O设备的分类

  1. 按速率分类
  2. 按信息交换的单位分类
  • 块设备
  • 字符设备

两种设备操作系统实现驱动程序的方式是不同的。

  1. 按设备的共享属性分类
  • 独占设备
  • 共享设备 资源调度问题
  • 虚拟设备 利用虚拟技术把一台物理设备变为若干逻辑设备

设备控制器

设备控制器是 CPU 与 I/O设备 之间的接口，接收I/O的命令并控制I/O完成设备工作。设备控制器是一个可编址设备，连接多个设备时可有多个设备地址。

【待补充】

I/O控制方式

轮询控制方式

中断控制方式

DMA控制方式

不同控制下I/O的过程 ……进程状态会发生什么变化 OS内核会做些什么 将进程置为阻塞态 为进程分配设备 中断处理，唤醒进程

  1. DMA控制器的组成
  • 命令/状态寄存器
  • 内存地址寄存器MAR
  • 数据寄存器DR
  • 数据计数器DC

不使用DMA过程

  1. 首先控制器从设备完整读出一块数据放入数据寄存器
  2. 计算校验和
  3. 发中断信号，将数据读入内存

使用DMA方式

  1. CPU发【待补充】

缓冲管理

缓冲的引入

在数据到达和数据离开速度不一致的地方都可以引入缓冲。

降低对硬件响应时间的要求。

循环缓冲

  1. 引入循环缓冲的理由
  2. 循环缓冲的组成
  3. 缓冲区的使用
  4. 进程同步

设备分配

设备分配要考虑的因素

设备独立性

应用程序独立于具体的物理设备。

SPOOLING技术

磁盘管理

磁盘结构

通过改善调度算法提高访问速度=>减少寻道次数

磁盘调度

考磁盘调度算法

最后修改于 2019-12-10

归零幻想
零点还不算熬夜
知识体系 标签 归档 友链 关于 RSS
Hugo Theme Diary by Rise
移植自 Makito's Journal.

© CC BY-SA 4.0
- 目录 -