操作系统概念复习

导论

计算机系统部件

硬件、OS、应用程序、用户

配置操作系统的主要目标

1. 提供用户与计算机之间的接口，使计算机更易于使用；
2. 有效地控制和管理计算机系统中的各种资源，使之得到更有效的利用；
3. 合理地组织计算机系统的工作流程，以提高资源利用率并改善系统性能。

操作系统定义

操作系统是一组控制和管理计算机硬件和软件资源，合理地组织计算机工作流程，以及方便用户的程序的集合。

OS管理的计算机系统资源

处理机、存储器、设备、文件

批处理技术是指计算机系统对一批作业自动进行处理的一种技术。

单道批处理系统

单道批处理系统中内存仅一道程序，系统资源无法得到充分利用。

单处理机系统中多道程序

运行特点

1. 多道：计算机内存中同时存放多道相互独立的程序。
2. 宏观上并行：同时进入系统的多道程序都处于运行过程中，即它们先后开始了各自的运行，但都未运行完毕。
3. 微观上串行：内存中的多道程序轮流占有 CPU，交替执行。

多道批处理系统需要解决的问题

处理机管理、内存管理、设备管理、文件管理、作业管理

操作系统的类型

批处理操作系统、分时操作系统、实时操作系统。
如果一个系统兼顾其中多者的功能，则称为通用操作系统。
还有一些其他的：嵌入式、个人计算机OS、网络OS、分布式等。

单道批处理系统及其特征

内存中始终保存一道作业的批处理系统

1. 自动性：自动依次运行，无人工干预
2. 顺序性：完成顺序与进入顺序相同
3. 单道性：内存只有一道作业

多道批处理系统及其特征

1. 多道性：计算机内存中同时存放几道相互独立的程序。
2. 无序性：进入顺序与完成顺序无严格对应关系。
3. 调度性：作业从提交到完成经历两级调度：作业调度、进程调度。

分时系统

人机交互：控制程序运行
共享主机：机器昂贵，多人使用较经济
方便用户上机： 可以通过终端提交作业

分时技术

把处理机的运行时间分成时间片，时间片轮转。
如果在该时间片不能完成，就暂停给下一个。

分时操作系统

1. 计算机与多台终端连接，每个用户都可以通过终端向系统发出命令，请求完成某项工作，系统根据命令完成用户的要求。
2. 用户根据系统的结果，提出下一步的请求。
3. 重复上述交互，直到完成全部交互。

关键问题

及时接收、及时处理。

分时操作系统的特征

1. 多路性/同时性
2. 交互性：人机会话
3. 独立性：仿佛自己独占。
4. 及时性

实时系统

能及时响应外部事件的请求，在规定的时间范围内完成对该时间的处理，并控制实时任务协调一致地运行。

分类

实时控制系统：以计算机为中心的生产过程控制系统。
实时信息处理系统：对信息进行实时处理的系统。

特征

及时性、可靠性。

操作系统的基本特征

1. 并发：
   并行：同一时刻发生。并发：同一时间间隔发生。宏观上同时运行。
2. 共享：资源可供多个并发执行的进程同时使用。
   互斥共享：一段时间只让一个进程
   同时访问：一段时间允许多个进程访问
   上述是两个最基本的特征，互为存在条件。
3. 虚拟：把一个物理上的实体变成若干个逻辑上的对应物，如：分时技术、虚拟内存。
4. 不确定/异步性：多个作业的执行顺序和执行时间不确定。

操作系统的作用

1. 用户与计算机硬件之间的接口
2. 为用户提供虚拟机
3. 计算机系统的管理者

操作系统操作

要保证一个出错程序不会引起其他程序的运行错误。
用户模式和内核模式
（想起最近Intel的漏洞

计算机系统的两种运行状态

1. 核心态/管态/系统态：操作系统管理程序执行时机器的状态，具有较高的权限，执行一切指令，访问所有寄存器和存储区。
2. 用户态/目态： 只能做制定的事。

操作系统的功能

处理机管理/进程管理、存储器管理、设备管理、文件管理。

进程管理

进程是正在执行的程序。
为了完成任务，需要一定的资源，CPU时间、存储器、文件、I/O设备。

操作系统在进程管理的任务

1. 创建和恢复
2. 挂起和恢复
3. 提供进程同步机制
4. 提供进程通信机制
5. 提供死锁处理机制

处理机管理的任务

1. 进程管理
2. 进程同步
3. 进程通信
4. 调度

操作系统结构

操作系统提供的服务

用户接口、程序执行、I/O操作、文件系统操纵、通信、错误检测、资源分配、统计、保护和安全。

系统调用

若干指令构成的过程，用来实现特定的操作系统服务功能。
运行程序和OS之间的参数传递：

1. 寄存器中的参数传递
2. 参数存在内存的一张表中，表地址作为寄存器的参数传递
3. 程序把参数压入栈，由操作系统弹出

系统调用处理程序的执行过程

1. 为执行系统调用命令作准备。
   主要工作是保留现场，并把系统调用命令的参数放入指定的存储单元。
2. 执行系统调用。
   根据系统调用命令的编号找到相应子程序的入口地址，然后转去执行。
3. 系统调用命令执行完后的处理。
   主要工作是恢复现场，并把系统调用的返回参数送入指定存储单元。
   (回顾一下CSAPP学的调用就知道了。

系统调用与过程调用的区别

运行状态（核心态）、进入方式不同（中断，子程序直接调用不涉及运行状态改变）

系统调用的类型

进程控制 Process control
文件管理 File management
设备管理 Device management
信息维护 Information maintenance
通信 Communications

系统程序

系统程序提供程序开发和执行的便利环境
一小部分是系统调用接口

划分

文件操纵 File manipulation
状态信息 Status information
文件修改 File modification
程序语言支持 Programming language support
程序调入和执行 Program loading and execution
通信 Communications

多数用户所看到的操作系统是由应用和系统程序所定义的，而不是系统调用所定义。

操作系统结构

三种结构：模块结构、层次结构、微内核结构。

层次结构特点

一种特殊的模块结构
特点：

1. 给模块赋予了层次顺序，使调用关系变得有序；
2. 在上下两层不变的基础上可以换掉某层，便于移植和扩充。
3. 但以牺牲一定的灵活性为代价。

微内核结构

非基本的都拿走，微内核通常只包括最小的机才能拿和内存管理以及通信功能。
比如内存管理、设备管理、文件管理就被拿出去了，内核就保留了调度、进程间通信、地址空间支持等。

微内核优缺点：

1. 容易扩充操作系统
2. 容易从一种硬件平台移植到另一种硬件平台
3. 更安全可靠
   缺点：
   因系统功能总开销导致系统性能下降

模块 modules

面向对象编程技术来生成模块化的内核。

以Solaris为例

7个可加载的内核模块和一个核心内核
调度类 Scheduling classes
文件系统 File systems
可加载的系统调用 Loadable system calls
可执行格式 Executable formats
STREAMS模块 STREAMS modules
杂项模块 Miscellaneous modules
设备和总线驱动 Device and bus drivers

模块结构的特点

1. 效率高
2. 全局函数使用多造成访问控制困难
3. 结构不清晰，可理解性、可维护性和可移植性差。

宏内核与微内核

宏内核/单内核：在运行过程中，它是一个独立的进程。
微内核：大部分内核模块都作为独立的进程，它们之间通过消息通信使模块之间互相提供服务。

虚拟机

基本思想：将单个计算机的硬件抽象为几个不同的执行部件。
根本原因：运行几个不同的执行环境时能共享相同的硬件。

优点

1. 提供对系统的完全保护，完全独立，没有直接共享资源
2. 虚拟机是研发操作系统的完美载体。系统开发在虚拟机上而不是在物理硬件上完成，从而不会打扰正常系统运行。
   （喵喵喵？

系统启动

引导系统：转入内核以启动计算机的过程
引导程序：存储在ROM中的代码，能够定位内核，调入内存，并开始运行

UNIX

内核结构可分为两大部分：
内核：OS的资源管理功能构成。
核外程序：用户程序和系统服务构成。
核心中两个最主要的部分是文件子系统和进程控制子系统

进程管理

进程的概念

进程是资源分配的基本单位，也是独立运行的基本单位。

前趋图

直接前趋→直接后继
前趋→→→→

程序顺序执行的特征

1. 顺序性
2. 封闭性：程序一旦开始运行，执行结构不受外界因素影响。
3. 可再现性：只要初始条件和执行环境相同，重复执行可以获得相同的结果。

程序并发执行的特征

1. 间断性：“执行-暂停-执行”
2. 失去封闭性
3. 不可再现性

程序并发执行的条件

读集和写集：

1. R（Si）∩ W（Sj）={ } 这两条保证
2. R（Sj）∩ W（Si）={ } 两次读之间数据不变
3. W（Si）∩ W（Sj）={ } 本条保证写操作结果不丢

进程

一个进程包括：
代码段 text section
程序计数器和处理机寄存器内容
program counter and the contents of processor’s register
栈 stack
数据段 data section

进程的特征

1. 动态性：进程是程序的一次执行过程。因创建而产生，因调度而执行，因无资源而暂停，因撤销而消亡。

2. 并发性

3. 独立性：传统OS中，进程是独立运行的基本单位，也是系统分配资源和调度的基本单位。
4. 异步性
5. 结构性：进程实体由程序段、数据段、进程控制块组成，又称为进程映像。

进程与程序的关系

1. 进程是动态概念，程序是静态概念；京城是程序在处理机的一次执行过程。
2. 进程是暂时的，程序是永久的。
3. 进程与程序的组成不同：进程包括程序、数据、进程控制块。
4. 进程与程序密切相关的。（一对多，多对一都阔以
5. 进程可以创建新进程。

进程状态

1. 新建
2. 运行
3. 等待：等待某事件发生
4. 就绪：等待分配处理器
5. 终止：进程执行完毕

进程的基本状态

至少应该包括：就绪状态、执行状态、阻塞状态/等待状态/睡眠状态（就算给它处理机也不能运行）。

状态转换

大多数状态不可逆转。
状态转换大多为被动进行，但运行→等待是主动的。
一个进程在一个时刻只能处于上述状态之一。

进程的挂起状态

在某些系统中，希望人为讲进程挂起使之处于静止状态。
挂起的原因

• 系统故障
• 检查中间结果
• 资源不足
• 内存不足

进程控制块(PCB)

每个进程在OS内用进程控制块表示
PCB是描述和管理进程的数据结构，是进程实体的一部分，OS通过PCB感知进程的存在，PCB是进程存在的唯一标志。

PCB包含

1. 进程状态
2. 程序计数器 PC
3. CPU寄存器
4. CPU调度信息
5. 内存管理信息
6. 记账信息
7. I/O状态信息

PCB的内容

进程标识符：惟一标识进程的一个标识符或整数。
进程当前状态：说明进程当前所处状态。
进程队列指针：用于记录PCB队列中下一个PCB的地址。
程序和数据地址：进程的程序和数据在内存或外存中的存放地址。
进程优先级：反映进程获得CPU的优先级别。
CPU现场保护区：CPU现场信息的存放区域，包括：通用寄存器、程序计数器、程序状态字等。
通信信息：进程与其他进程所发生的信息交换。
家族关系：指明本进程与家族的关系，如父子进程标识。
资源清单：列出进程所需资源及当前已分配资源。

进程调度

调度队列

作业队列、就绪队列、设备队列（等待I/O设备的进程队列）
//一个队列头后面跟着一堆PCB

调度程序

长程调度/作业调度：选择可以进入就绪队列的进程
短程调度/CPU调度：选择可下一个执行并分配CPU的进程
两者的主要差别是执行频率
还有的系统引入了中程调度

进程的区分

I/O进程、CPU进程（看哪个时间多

上下文切换

将CPU切换到另一个进程需要保存当前进程的状态并回复另一个进程的状态。
上下文切换的时间开销较重；切换时，系统没有做有用的工作。时间取决于硬件的支持。

进程操作

进程控制的职能是对系统中所有进程实施有效的管理。
一般由OS内核原语来实现。

操作系统内核

把一些和硬件紧密相关的模块、运行频率较高的模块和一些基本操作安排在靠近硬件的软件层次中，让他们常驻内存，提高效率。
主要包括：

• 中断
• 时钟管理
• 进程管理
• 存储器管理
• 设备管理

进程创建

每个新进程可以再创建新进程，形成进程树。
资源共享方式：

• 父进程子进程共享所有资源
• 子进程共享父进程资源的子集
• 父进程和子进程无资源共享

执行方式：

• 并发执行
• 父进程等待，直到子进程终止

地址空间：

• 子进程是父进程的复制品
• 子进程装入一个新进程

创建原语的主要功能

创建一个新进程的操作过程

1. 向系统申请一个空闲PCB
2. 为新进程分配资源
3. 初始化新进程的PCB
4. 将新进程的PCB插入就绪队列

进程终止

执行完最后一个语句并使用系统调用exit()请求OS删除自身。
状态值返回给父进程，所有进程资源由OS回收。

• 父进程终止子进程的原因
  -子进程超量使用分配的资源（你居然还偷钱
  -赋予子进程的任务不再需要（你没用了
  -父进程退出
• 有些系统，若父进程终止，不允许子进程继续，称为级联终止

引起进程撤销的原因

• 正常结束
• 异常结束：超时、内存不足、地址越界、算数错误、I/O故障、非法指令等
• 外界干预

撤销原语采用的两种策略

1. 撤销指定标识符的进程
2. 撤销指定进程及其所有子孙进程
   1. 找到进程PCB
   2. 检查是否为执行状态，停止该进程执行，设置重新调度标志
   3. 检查是否有子孙进程
   4. 回收资源和PCB

进程的阻塞与唤醒

引起进程阻塞及唤醒的事件：

• 请求系统服务。如请求打印机
• 启动某种操作并等待操作完成。比如I/O
• 等待合作进程的协同配合。
• 系统进程无新工作可做。

阻塞原语的主要功能

1. 停止当前进程的执行
2. 保存该进程的CPU现场信息
3. 改变进程状态并插入到相应事件的等待队列中
4. 转进程调度程序，从就绪队列中选择一个新的进程投入运行

唤醒原语的主要功能

进程等待的事件发生后，由发现者进程将其唤醒。

1. 将被唤醒进程从相应的等待队列中移出；
2. 将进程状态改为就绪，并将该进程插入就绪队列；
3. 转进程调度或返回。

阻塞与唤醒的关系

执行→阻塞：这个进程自己调用的
阻塞→就绪：另一个发现者进程调用唤醒原语
一般发现者进程与被唤醒进程是合作的并发进程

进程的挂起与激活

就是多了一种挂起的状态，激活是与之配合的，但是要注意的是，对于执行的挂起和激活需要进程调度。

挂起原语的主要功能

1. 到PCB表中查找该进程的PCB；
2. 检查该进程的状态，
   • 若为执行则停止执行并保护CPU现场信息，将该进程状态改为挂起就绪；
   • 若为活动阻塞，则将该进程状态改为挂起阻塞；
   • 若为活动就绪，则将该进程状态改为挂起就绪；
3. 若进程挂起前为执行状态，则转进程调度，从就绪队列中选择一个进程投入运行。

激活原语的主要功能

1. 到PCB表中查找该进程的PCB。
2. 检查该进程的状态。
   • 若状态为挂起阻塞，则将该进程状态改为活动阻塞。
   • 若状态为挂起就绪，则将该进程状态改为活动就绪。
   • 若进程激活后为活动就绪状态，可能需要转进程调度。

进程的组织

将PCB组织起来，常用的有线性方式、链表方式、索引方式。

进程间的通信

独立进程不能影响其他进程或被影响
协作进程可能影响和被影响

进程协作的优点：

• 信息共享
• 加速运算
• 模块化
• 方便

进程通信

进程互斥与同步交换的信息量较少且效率低，因此称为低级进程通信方式，P、V原语称为低级通信原语。
高级进程通信方式：共享存储器系统、消息传递系统、管道通信系统或共享文件系统

共享内存系统

生产者消费者问题有两种缓冲区，无界缓冲和有界缓冲。

消息传递系统

建立通信连接，利用send/receive交换消息。
方法：

• 直接或间接通信
• 同步或异步通信
• 自动或显式的缓冲

消息缓冲通信及数据结构

消息缓冲区的数据结构

struct message 
    {   sender; 发送者进程标识符
         size; 消息长度
         text; 消息正文
         next; 指向下一个消息缓冲区的指针
    }

另外，在PCB中也要增加

struct PCB
   {     

           mq;消息队列队首指针
           mutex;消息队列互斥信号量
           sm;消息队列资源信号量
          
   }

发送原语的描述：

void send（receiver，a）receiver为接收者标识号，a为发送区首址
    {
       向系统申请一个消息缓冲区i；
       将发送区a中的消息复制到i中；
       获得接收进程的内部标识j;
       P（mutex）；
       把消息插入j的消息队列上；
       V（mutex）；
       V（sm）；
    }

接收原语的描述：

void  receive（b）b为接收区首址
{
          获得接收进程内部标识j;
          P（sm）；
          P（mutex）；
          将消息队列中的第一个消息移出；
          V（mutex）；
          将消息复制到接收区b；
  }

间接通信

通过邮箱或端口发送或接收消息
还有信箱通信。

同步

发送进程阻塞，直到这个消息被接收进程接收到，这种发送称为阻塞发送。
发送进程不阻塞，继续执行，这种发送称为非阻塞发送。

对于接收进程：
如果一个消息在接收原语执行之前已经发送，则该消息被接收进程接收，接收进程继续执行。
如果没有正在等待的消息，则该进程阻塞直到有消息到达；或者该进程继续执行，放弃接收的努力。前者称为阻塞接收，后者称为非阻塞接收。

通常有三种常用的组合：

• 非阻塞发送、阻塞接收
• 非阻塞发送、非阻塞接收
• 阻塞发送，阻塞接收

管道

基本上采用文件系统的原有机制实现。包括创建、打开、关闭、读写等。

• 互斥：诸进程互斥读写管道
• 同步：管道空、满情况处理
• 存在：确定对方是否存在

线程

为了减少程序并发执行所付出的时空开销

两个属性

• 拥有资源的独立单位
  Unit of Resource ownership
• 调度和分派的基本单位
  Unit of Dispatching

定义

线程是CPU使用的一个基本单元，包括：
线程标识 a thread ID
程序计数器 program counter
寄存器集 register set
栈 stack

同进程的线程共享

• 代码段 code section
• 数据段 data section
• 其他操作系统资源 other operating-system resources

优点

• 响应能力强
• 资源共享
• 经济性
• 多处理体系结构的利用
• 比创建新的进程更快
• 线程之间的切换更快
• 同进程的线程可以直接通信

多线程模型

内核线程、用户线程、上述两种方法的组合实现。

内核线程

依赖内核，由OS内核完成创建和撤销工作的线程。
处理机时间分配的对象是线程。

用户线程

由应用进程利用线程库来创建、同步、调度和管理线程。
当一个线程阻塞时，整个进程必须等待，处理机时间是分配给进程的。

线程与内核线程的关系

1. 多对一模型：
   线程管理由线程库在用户空间进行
2. 一对一模型：
   限制了系统支持的线程数量。早期Windows
3. 多对多模型
4. 二级模型（多对多的变种

CPU调度

中级调度

中级调度/中程调度/交换调度，将内存中暂时不用的信息移到外存，以腾出空间给内存中的进程使用，或者再调回来。

目的

提高内存利用率和系统吞吐率

作业的状态

• 提交状态
• 后备状态
• 运行状态
• 完成状态

作业控制块/JCB

包括的主要内容：

• 资源要求
• 资源使用情况
• 作业的控制方式、类型和优先级等
• 作业名、作业状态

作业的控制方式

联机作业控制、脱机作业控制

分派程序

分派程序用来将对CPU的控制交给由短程调度程序选择的进程

• 切换上下文 switching context
• 切换到用户态 switching to user mode
• 跳转到用户程序的适当位置并重新运行之 jumping to the proper location in the user program to restart that program

分派延迟/调度时间

周转时间

带权周转时间：周转时间/实际运行时间

调度算法

先来先服务

算法简单，利于实现
但不利于短作业及I/O繁忙型作业

最短作业优先调度

非掠夺式调度

优先级调度

静态优先级、动态优先级
饥饿问题：低优先级的进程可能永远得不到运行。

时间片轮转调度

确定时间片大小应考虑的因素：

• 系统对响应时间的要求：响应时间=时间片*进程数。进程数一定，则时间片与系统响应时间成正比。
• 就绪队列中的进程数目：时间片与就绪进程数成反比。
• 系统处理能力：人所能承受的响应时间一定，系统速度快则时间片可增长。

最高响应比

多级队列调度

多级反馈队列调度

存储器管理

存储器管理的功能

• 存储空间的分配和回收
• 地址变换
• 存储保护
• 存储扩充

指令和数据绑定到内存

• 编译时
• 加载时
• 执行时

程序装入内存的方式：

• 绝对装入方式
  按照模块内地址将程序和数据装入内存
• 可重定位装入方式
  由装入程序根据内存当时的实际使用情况，将装入模块装入到内存的适当地方。
• 动态运行时装入方式
  在将装入模块装入内存时并不进行地址变换，在程序执行过程中进行地址变换。

内存管理单元（MMU）

把虚拟地址映射到物理地址的设备
在MMU策略下，传入的地址都会加上重定位的值。

地址变换

• 静态地址变换
  静态地址重定位，地址变换在程序装入时一次完成，以后不再改变。
  特点：不需硬件支持，但程序运行时不能在内存移动，程序需要连续存储空间，难以共享。
• 动态地址变换
  动态重定位，在程序执行过程中，每次访问内存之前将要访问程序地址转换成内存地址。
  特点：需要硬件支持，不需连续空间，可以实现虚拟存储。

交换与覆盖

进程可以暂时从内存中交换到备份存储上，当需要再次执行时再换回内存。

覆盖技术：把一个大程序划分为一系列覆盖，每个覆盖是一个相独立的程序单位。
(类似C语言中的 联合 )

连续内存分配

内存通常分为：一个驻留OS，位于内存低端；一个用于用户进程，位于内存高端。

内存保护

• 界限寄存器法
• 存储保护键
• 环保护机制（有点像层次系统
• 访问权限

内存分配

分区回收

回收分区时，应将空闲去插入适当位置，此时有以下四种：

• 回收分区r上面邻接一个空闲分区
• 回收分区r下面邻接一个空闲分区
• 回收分区r上面、下面各邻接一个空闲分区
• 回收分区r不与任何空闲分区相邻

只有上下各相邻一个空闲分区时，空闲分区的个数才变化。

伙伴系统

采用伙伴算法对空闲内存进行管理。
当一块被分成两个大小相等的块时，这两块称为伙伴。

分页

逻辑地址由页号和页内偏移组成。

页表

为了在内存中找到进程每个页面对应的物理块而建立

存储分块表

地址变换

1. 分页地址变换机构将逻辑地址分为页号和页内偏移。
2. 页号与页表长度比较，超过则产生地址越界中断。
3. 未越界则计算页表项的位置，得到物理块号。
4. 将物理块号和页内偏移拼接在一起，形成访问主存的物理地址。

具有快表的地址变换机构

TLB：转换后备缓冲区/快表。
快表中存着页号，优先匹配快表中的页号。

有效访问时间

就是求一下期望= =

存储保护

添加一个保护位。

共享页（page）

可以共享公共代码，如果代码是可重入代码，则可以共享。
可重入代码：是不能自我修改的代码，它在执行期间不会改变。

页表结构

分级页表、哈希页表、反向页表

#####分级页表

• 离散方式存储页表
• 仅将当前需要的部分页表放在内存，其余放在磁盘，需要时调入。

分段

一个段是一个逻辑单位，每个分段都从0开始编址并采用一段连续的地址空间。

硬件支持

为每个进程建立一个段表，用来记录每段在内存的起始地址和相关信息

• 段号
• 段长
• 段在内存的起始地址
• 其他信息

段表一般放在内存里

地址变换

1. 逻辑地址中的段号和段表长度比较，超出则越界中断
2. 根据地址算出段表项的位置，读出该段在内存的起始地址
3. 检查段内地址是否超过段长，超过则越界中断
4. 未越界则把起始地址和段内位移相加，得到物理地址。

分段和分页的区别

• 页是信息的物理单位，是为了减少内存碎片及提高内存利用率，是系统管理的需要。段是信息的逻辑单位，它含有一组意义相对完整的信息，分段的目的是为了更好地满足用户的需要。
• 页的大小固定且由系统决定，由硬件把逻辑地址划分为页号和页内地址两部分。段的长度不固定且由用户所编写的程序决定，通常由编译系统在对源程序进行编译时根据信息的性质来划分。
• 分页系统中作业的地址空间是一维的，分段系统中作业的地址空间是二维的。

分段系统中的信息共享

多个进程的段表项指向同一内存区域实现的。

段页式存储

作业的地址空间首先被分成若干个逻辑分段，然后再将每一段分成若干个大小固定的页面

段号S-段内页号P-页内偏移D

段表寄存器：段表大小、段表始址
段表：段号、页表大小、页表开始地址
页表：页号、块号

地址变换

• 在进行地址变换时，首先将段号S与段表寄存器中的段表长度进行比较，若小于段表长度则表示未越界，
• 利用段表始址和段号求出该段对应段表项的位置，从中得到该段的页表始址，
• 再利用逻辑地址中的段内页号P获得对应页表项的位置，从中读出该页所在的物理块号，再与页内地址拼接成物理地址。

需要三次访问内存。

虚拟内存

• 离散性：不连续内存分配
• 多次性：一个作业分多次装入内存
• 对换性：允许运行中换进换出
• 虚拟性：逻辑上扩充内存

请求分页存储

请求分页存储管理方法是在分页存储管理的基础上增加了请求调页和页面置换功能

结构

页表（页号、物理块号、存在位、访问字段、修改位、外存地址）
缺页中断机构
地址变换机构
请求调页和页面置换软件

页面置换

先进先出
最佳置换算法
最近最久未使用置换算法(LRU)
LRU近似置换算法
二次机会算法

特殊栈来计算使用次数
当进程访问一个页面时，将该页面号从栈中移出压到栈顶。栈底即最近最久未使用的页面号。

页面缓冲算法

将分配策略和置换范围组合可得如下三种策略

• 固定分配局部置换
• 可变分配全局置换
• 可变分配局部置换

抖动

局部置换策略
挂起进程

请求分段存储管理

分段有如下优点：

• 有利于动态增长
• 允许按段进行编译
• 有利于共享
• 有利于保护

文件系统接口

文件系统：操作系统中与管理文件有关的软件和数据的集合。

主要功能

• 实现文件的按名存取
• 为用户提供接口
• 实施对文件和目录的管理
• 文件存储空间的分配及回收
• 文件的共享及保护

混合索引分配方式

是将多种索引分配方式相结合而形成的一种分配方式。这种方式已用于UNIX、Linux等系统中。
在UNIX System Ⅴ中，共设有13个地址项，包括10个直接地址项、一个一次间接地址项、一个二次间接地址项和一个三次间接地址项。