首页  思维导图  详情

408操作系统

2021-09-11 11:46:31   241  举报





AI智能生成

计算机考研和工作面试专用

学霸笔记

计算机考研

408计算机综合

计算机操作系统

大学教育

作者其他创作

大纲/内容

内存管理

原因

功能

内存分配和回收

可执行程序过程(进程)

地址转换

逻辑地址和物理地址

虚拟地址与实地址

内存扩充(虚拟技术)

存储保护

内存保护

程序装入和链接

链接

静态链接

动态链接

运行时动态链接

装入

绝对装入

单一连续分配

可重定位装入/静态重定位

固定分区

动态运行时装入/动态重定位

虚拟内存技术

分配方式

分区/连续

单一连续

固定分区

动态分区/可变分区分配

首次适应

简单，相对最好和最快

最佳适应

外部碎片多

最坏适应

不容易产生小碎片，但容易导致大内存块耗尽，性能差

邻近适应/循环首次适应

比首次适应算法还差

分页(段)/非连续

基本分页存储

页相关

页/页面大小

页框=页帧=内存块

进程块=页/页面

页面太小：页表过长，增加转换开销，降低换入/换出率

页面太大：页内碎片多，降低内存利用率

页表项

(页号P，块号B）

页表

记录进程页面在内存中对应的物理地址

页表存放于内存中，由页表项构成

每个进程有一个页表，多个页面

地址相关

地址变换机构

基本地址变换

快表地址变换

两级页表

地址转换

n级页表

基址寄存器内容

图解

地址结构

(页号P，页内地址偏移W)

寻址方式

基址寻址 EA=(BR)+A

分段存储

段表

（段号S，段长，本段在主存的始址)

每个进程都有一张段表，大多数驻留在内存中

段共享和保护

可同时读不可写【纯代码/可重入代码】

存取控制保护

地址越界保护

异常

段缺失异常

段页不在内存页表中

越界异常

超过段长

越权异常

读写权限越权

地址相关

地址变换机构

图解

寻址方式

变址寻址 EA=(IX)+A

逻辑地址/地址结构

(段号S，段内偏移量W)

段页式存储

虚拟内存

传统存储管理问题

一次性

驻留性

局部性原理

时间局部性

空间局部性

特征

部分装入、请求调入、置换功能

硬件支持

一定容量内存和外存

页/段表机制

中断机构

地址变换机构

请求分页技术

页表机制

(页号，物理块号，状态位，访问字段，修改位，外存地址)

缺页中断

内中断/异常

保护CPU环境->分析中断原因->转入中断处理程序->恢复CPU环境

下一条指令执行位置

页面置换算法

OPT最佳置换算法

FIFO先入先出

可能会出现Bledy现象

LRU最近最久未使用

CLOCK/NLU 时钟置换

改进型 CLOCK 算法

页面分配策略

驻留集

给进程分配的物理页框的集合

置换策略

固定分配局部置换

可变分配全局置换

可变分配局部置换

调入时机

预调页策略

请求调页策略

调入来源

对换区

文件区

UNIX方式

抖动/颠簸

定义

刚被置换的页面由被调入，频繁出现该页面调度行为

主要原因

常用页面数目高于可用物理页帧数

所有页面置换策略都有可能引起抖动

工作集

某段时间间隔内，进程要访问的页面集合

工作集窗口

某段时间间隔内，进程要访问的页面集合(包括重复)

最大容量

2^(地址寄存器)B

文件管理

文件

定义

以硬盘为载体的存储在计算机的信息集合

输入输出的基本单位

抽象数据类型

发展

数据项

基本数据项

组合数据项

记录

一组相关数据项的集合

文件

文件卷

文件结构

有结构文件(记录式文件)

顺序文件

索引文件

索引顺序

散列文件

无结构文件(流式文件)

操作

重定位(文件寻址)

截断文件

打开

关闭

读取

提前读

写入

延迟写

关联信息

打开文件表

文件指针

文件打开计数

文件磁盘位置

访问权限

UNIX 文件类型

普通文件

目录文件

块特殊文件

字符特殊文件

FIFO

套接字

符号链接

硬链接(索引共享)

软链接(符号链)

文件系统

存储空间管理

物理空间管理/分配

连续分配

位图法

空闲表法

链接分配

隐式链接

图解

显示连接

FAT 文件分配表

inode 索引节点

图解

空闲链表法

索引分配

索引文件长度计算

混合索引

索引分配

成组链接法

Hash结构

文件与目录

文件目录

结构

单级目录

两级目录

多级/树形目录

无环图目录结构

目录文件

目录实现

线性列表

哈希表/散列表

文件控制块FCB

基本信息

存取控制信息

使用信息

索引结点

文件共享与保护

文件共享

硬链接(索引共享)

软链接(符号链)

文件保护

口令保护

加密保护

访问控制

文件权限位数

文件层次结构

用户调用接口

文件目录系统 FCB

存取控制验证

逻辑文件系统/文件信息缓冲区

物理文件系统

辅助分配模块

设备管理程序模块

磁盘管理

磁盘结构

磁头

磁道

扇区

磁盘地址

簇

块

磁盘类型

固定头磁盘

活动头磁盘

固定盘磁盘

可换盘磁盘

磁盘调度算法

时间组成

寻找(道)时间【主要】

旋转延迟时间

平均查询时间 = (1/磁盘转速)/2

传输时间

寻道时间减少

先来先服务FCFS

最短寻找时间优先SSTF

扫描算法SCAN

循环扫描算法C-SCAN

NStepScan

FSCAN

延迟时间减少

交替编号/交叉编址

错位命名

管理操作

初始化

引导块

坏块

格式化

物理格式化

逻辑格式化

分区

真题

I/O管理

I/O管理概述

I/O设备

外部设备

打印机

显示器

鼠标

存储设备

磁盘

磁带

光盘

网络通信设备

网络接口

调制解调器

I/O控制方式

程序直接控制

中断驱动方式

DMA方式

传送过程

预处理

CPU给DMA控制器发出读命令

数据传送钱由DMA控制器请求总线使用权

DMA传送前由设备驱动程序设置传送参数

数据传送

初始化DMA控制器并启动磁盘

从磁盘传输一块数据到内存缓冲区

后处理

DMA控制器发出中断请求

CPU在指令周期末尾检查中断并处理

执行"DMA结束"中断服务程序

与中断方式区别

过程上

中断为程序切换，需保存和恢复现场；

DMA方式处理预处理和后处理，其余不占用CPU资源

响应时刻

中断在指令周期结束后(末尾)；

DMA请求可发生在每个及其周期结束时（取指、间址、执行）均可以 只要CPU不占用总线即可被响应

CPU参与

中断过程需要CPU参与

DMA传送过程不需要CPU干预，因此数据传输效率高，适合高速外设数据传送

优先级

DMA优先级高于中断请求

作用范围

中断方式除I/O外，还有异常处理能力

DMA仅局限于传送数据块I/O操作

数据传输

中断I/O采用软件完成

DMA采用硬件完成

基本单位

组成

主存地址计数器

传送长度计数器

数据缓冲寄存器

DMA请求触发器

"控制/状态"逻辑

中断机构

四类寄存器

命令/状态寄存器 CR

内存地址寄存器AR

数据寄存器DR

数据计数器DC

传送方式

停止CPU访存

周期挪用/周期窃取

DMA与CPU交替访存

通道控制方式

I/O通道

字节多路通道

数据选择通道

数据多路通道

I/O子系统层次结构

用户层I/O

系统调用层/设备独立性软件

设备映射表 DMT

逻辑设备表 LUT

设备驱动程序

中断处理程序

硬件设备

设备控制器

控制字符设备

控制块设备

I/O核心子系统

I/O子系统

I/O调度

缓冲与高速缓存

磁盘高速缓存 Disk Cache

缓冲区 Buffer

单缓冲

双缓冲

循环缓冲

缓冲池

对比

设备分配与回收【不考】

设备使用方式

独占式使用

分式式共享使用

SPOOLing方式使用

设备分配数据结构

设备控制表 DCT

控制器控制表 COCT

通道控制表 CHCT

系统设备表 SDT

设备分配策略

设备分配安全性

安全分配

不安全分配

逻辑设备名到物理设备名映射

LUT 逻辑设备表

SPooLing假脱机【不考】

虚拟设备

组成

输入(出)井

输入(出)缓冲区

输入(出)进程

管理

预输出程序

井管理程序

缓输出程序

设备保护

差错处理

I/O管理功能

状态跟踪

设备存取

设备分配

独享分配

共享分配

虚拟分配

设备控制

概述

计算机系统

硬件

输入设备

输出设备

存储器

运算器

控制器

操作系统

应用程序

系统软件

编译器

应用软件

通用软件

用户

操作系统OS

特征

并发Concurrence

共享Sharing

互斥共享

同时访问

虚拟Virtual

时分复用

虚拟处理器

空分复用

虚拟内存

虚拟外部设备

异步Asynchronism

管理对象

处理机

进程管理

进程同步

进程通信

死锁处理

处理机调度

存储器

内存分配

内存保护

互斥共享

地址映射

文件

设备

接口

命令接口

联机命令/交互式命令接口 UNIX,DOS命令窗口(黑框框): CMD

脱机命令/批处理命令接口 穿孔纸带程序

程序接口

由一组系统调用(广义指令)组成

例如：C语言#include <unistd.h> fork() 函数

API函数集，DLL形式；例如：Kernel32.dll

图形接口GUI

系统调用(特权指令)

系统调用

与库函数的区别

高级语言使用库函数进行系统调用

高级语言转化为汇编指令，调用访管指令，切换至内核态，执行系统调用相关代码

执行过程

执行陷入trap指令 -> 传递系统调用参数 -> 执行相应的服务程序 -> 返回用户态

存放/加载

存放于外存/辅存

启动时执行BIOS指令(存于ROM中)加载到RAM(内存）

类型

批处理

单道批处理

多道批处理

分时/多任务OS

具有并行和并发特点

实时OS

网络/分布式OS

个人计算机(PC)

运行机制

运行环境

核心态(内核态、管态）

中断相关

缺页中断处理

时钟中断处理程序

关中断

输入/输出操作

置时钟指令

广义指令的执行

进程调度程序

进程切换

用户态(目态）

命令解释程序

编程相关

访管指令（trap）

系统调用

读时钟指令

寄存器清零

取数指令

压栈指令

跳转指令

用户态异常

缺页异常

外部中断

用户态转内核态

系统调用

中断产生

程序错误状态

请求特权指令

时钟管理

标准系统时间

时钟脉冲信号-时钟周期

时间片轮转调度

IRQ(Interrupt R est) 中断机制

I/O输入输出

进程管理和调度

系统功能的调用

设备驱动

文件访问

原语

设备驱动

CPU切换

进程通信

系统控制数据结构及处理

进程管理

作业控制块

进程控制块 PCB

存储器管理

空闲登记表

内存分配表

设备管理

设备控制快

消息队列

缓冲区

中断/异常

中断类型

(Exception) 内中断/异常

自愿

指令中断

强迫

硬件故障

软件中断

三类型

Fault 错误

Trap 自陷

可用于程序调试的断点设置和单步跟踪

发生后CPU将转为去执行操作系统内核相应程序

自陷处理结束后返回陷阱指令的下一条指令执行

Abort 终止

外中断

IO请求

用户干预

时钟中断

内/外中断联系区别

"缺页"或"溢出"等异常事件利用特定指令在执行过程中产生，而中断不和任何指令相关联

异常的检测由CPU自身完成【指令周期末尾】，不必通过外部的某个信号通知CPU CPU必须通过总线获取中断源的标识信息，才能知道哪个设备发生了何种中断

中断处理过程

已响应中断

关中断

保存断点

中断服务程序寻址

保存现场和屏蔽字

开中断

执行中断服务程序

关中断

恢复现场和屏蔽字

开中断、中断返回

中断相关概念

中断上下文

中断服务程序

上半部与下半部的对比

注册中断处理程序

中断向量

中断嵌套

中断描述符表

中断隐指令

中断响应优先级

中断处理优先级

向量地址

中断源识别

中断处理与子程序调用

入口地址

中断隐指令根据中断向量得到

由调用程序根据寻址方式得到

保存环境

保存PC、PSW、通用寄存器(数据、地址等)

进程状态

从用户态转化为内核态

系统调用

传递系统调用参数

trap指令转换OS 用户态->内核态

将返回地址压栈备用

CPU执行相应的内核态服务程序

返回用户态

体系结构

大内核

微内核

进程管理

状态与转换

七状态

挂起

就绪挂起

阻塞挂起

五状态

New 新建

终止

三状态

Ready 就绪态

Running 运行态

Block / Wait 阻塞/等待态

进程通信

共享存储

信号PV

消息传递

间接通信

信箱通信

直接通信

消息(缓冲)队列

管道通信

信号量

socket套接字

线程

组成

线程ID、程序计数器PC，寄存器集合和堆栈

没有独立地址空间，可独立执行程序；同一线程能够被不同进程调用

类别

用户级线程

内核级线程

多线程模型

多对一

相当于用户逻辑上模拟多并发线程

一对一

并发能力强，支持多处理器，但线程有开销，会影响性能

多对多

对上述两种模型的综合

多线程优缺点

进程

定义

进程是程序的一次执行过程

进程是一个程序以及其数据在处理机上顺序执行时所发生的活动

进程是具有独立功能的程序在一个数据集合上运行的过程，他是系统进行资源分配的独立单位

综上： 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

组成

PCB进程控制块

描述信息

管理和控制信息

分配清单

处理机(环境信息)

程序

相关数据结构

可利用资源向量Avail

最大需求矩阵Max

分配矩阵Allocation

需求矩阵Need

算法描述

系统安全状态

安全性算法

检测与解除

资源分配图

死锁定理

图片

这里进程由矩形表示

死锁解除

资源剥夺法

进程撤销法

进程回退法

最大资源数

发生死锁的最大资源数为 n(m-1)

可能发生死锁的最小进程数 K(m-1)>= n

饥饿与死锁

补充

C语言内存分配

stack

heap

bss 未初始化数据段

data 全局赋值变量

text 只读段

计算机开机启动原理

第一阶段：BIOS

硬件自检

启动顺序

第二阶段：MBR 主引导记录

主引导记录结构

分区表

第三阶段：硬盘启动

情况A：VBR 卷引导记录

情况B：扩展分区和逻辑分区

情况C：启动管理器

第四阶段：操作系统

Linux 文件系统

文件描述符

三张表关系

文件描述表，打开文件表，索引表

文件指针

文件索引节点

外部碎片问题

定义

引起外部碎片的分配方式

连续分配

分区

单一连续

固定分区

动态分区/可变分区分配

首次适应

简单，相对最好和最快

最佳适应

外部碎片多

最坏适应

不容易产生小碎片，但容易导致大内存块耗尽，性能差

邻近适应/循环首次适应

比首次适应算法还差

分段

分页

链接分配

索引分配

Hash结构

Linux I/O 复用

select函数

epoll函数

mmap

935 考纲

一、操作系统概述 （一）操作系统的概念、特征、功能和提供的服务 （二）操作系统的发展与分类 （三）操作系统的运行环境 1. 内核态与用户态 2. 中断、异常 3. 系统调用 （四）操作系统的结构 二、进程管理 （一）进程与线程 1. 进程概念 2. 进程的状态与转换 3. 进程控制和组织 进程控制块；调度队列和调度器；进程的创建和终止。 4.线程概念与多线程模型 （二）CPU调度 1. 调度的基本概念 2. 调度时机、切换与过程 3. 调度的基本准则 4. 调度方式 5. 典型调度算法 先来先服务调度算法； 短作业（短进程、短线程）优先调度算法； 时间片轮转调度算法；优先级调度算法； 多级反馈队列调度算法。 （三）同步与互斥 1. 进程同步和临界区的基本概念 2. 信号量 3. 使用信号量描述和解决经典同步问题 （四）死锁 1. 死锁的概念 2. 死锁处理策略 3. 死锁预防 4. 死锁避免 系统安全状态；银行家算法。 5. 死锁检测和解除 三、内存管理 （一）内存管理基础 1. 内存管理概念 程序装入与链接；逻辑地址与物理地址空间；内存保护。 2. 连续分配管理方式 3. 非连续分配管理方式 分页管理方式；分段管理方式；段页式管理方式。 （二）虚拟内存管理 1. 虚拟内存基本概念 2. 请求分页管理方式 3. 页面置换算法 最佳置换算法（OPT）；先进先出置换算法（FIFO）； 最近最少使用置换算法（LRU）。 4. 页面分配策略 5. 工作集 6. 抖动 四、文件管理 （一）文件系统基础 1. 文件概念 2. 文件的逻辑结构 顺序文件；索引文件；索引顺序文件。 3. 目录结构 文件控制块和索引节点；单级目录结构和两级目录结构； 树形目录结构；图形目录结构。 4. 文件共享 5. 文件保护 访问类型；访问控制。 （二）文件系统实现 1. 文件系统层次结构 2. 目录实现 3. 文件实现 （三）磁盘组织与管理 1. 磁盘的结构 2. 磁盘调度算法 3. 磁盘的管理 五、输入输出（I/O）管理 （一）I/O管理概述 1. I/O控制方式 2. I/O软件层次结构 （二）I/O核心子系统 1. I/O调度概念 2. 高速缓存与缓冲区

一、操作系统概述 （一）操作系统的概念、特征、功能和提供的服务 （二）操作系统的发展与分类 （三）操作系统的运行环境 1. 内核态与用户态 2. 中断、异常 3. 系统调用 （四）操作系统的结构 二、进程管理 （一）进程与线程 1. 进程概念 2. 进程的状态与转换 3. 进程控制和组织 进程控制块；调度队列和调度器；进程的创建和终止。 4.线程概念与多线程模型 （二）CPU调度 1. 调度的基本概念 2. 调度时机、切换与过程 3. 调度的基本准则 4. 调度方式 5. 典型调度算法 先来先服务调度算法； 短作业（短进程、短线程）优先调度算法； 时间片轮转调度算法；优先级调度算法； 多级反馈队列调度算法。 （三）同步与互斥 1. 进程同步和临界区的基本概念 2. 信号量 3. 使用信号量描述和解决经典同步问题 （四）死锁 1. 死锁的概念 2. 死锁处理策略 3. 死锁预防 4. 死锁避免 系统安全状态；银行家算法。 5. 死锁检测和解除 三、内存管理 （一）内存管理基础 1. 内存管理概念 程序装入与链接；逻辑地址与物理地址空间；内存保护。 2. 连续分配管理方式 3. 非连续分配管理方式 分页管理方式；分段管理方式；段页式管理方式。 （二）虚拟内存管理 1. 虚拟内存基本概念 2. 请求分页管理方式 3. 页面置换算法 最佳置换算法（OPT）；先进先出置换算法（FIFO）； 最近最少使用置换算法（LRU）。 4. 页面分配策略 5. 工作集 6. 抖动 四、文件管理 （一）文件系统基础 1. 文件概念 2. 文件的逻辑结构 顺序文件；索引文件；索引顺序文件。 3. 目录结构 文件控制块和索引节点；单级目录结构和两级目录结构； 树形目录结构；图形目录结构。 4. 文件共享 5. 文件保护 访问类型；访问控制。 （二）文件系统实现 1. 文件系统层次结构 2. 目录实现 3. 文件实现 （三）磁盘组织与管理 1. 磁盘的结构 2. 磁盘调度算法 3. 磁盘的管理 五、输入输出（I/O）管理 （一）I/O管理概述 1. I/O控制方式 2. I/O软件层次结构 （二）I/O核心子系统 1. I/O调度概念 2. 高速缓存与缓冲区