猫熊小才天の书院
0%

操作系统知识总结

Posted on In Views: Valine:
Symbols count in article: 16k Reading time ≈ 15 mins.

第一章 OS引论

1 OS定义

操作系统是一组能有效地控制和管理计算机软件和硬件硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。是配置在计算机硬件上的第一层软件。是现代计算机系统中最基本和最重要的系统软件。

2 OS目标：有效性、方便性、可扩充性、开放性

3 推动OS发展的主要动力

  1. 不断提高计算机资源的利用率
  2. 方便用户
  3. 器件的不断更新和换代
  4. 计算机体系结构的不断发展
  5. 不断提出新的应用需求

4 OS作用：

  1. OS作为用户和计算机硬件系统之间的接口
  2. OS作为计算机系统资源的管理者
  3. OS实现了对计算机资源的抽象

5 OS发展历程

5.1 单道批处理系统

5.1.1 缺点

系统中的资源得不到充分的利用

5.2 多道批处理系统

用户提交的作业先存放在外存上，形成一个后备队列，利用其因IO操作而暂停时的CPU空档时间，再调度下一程序

5.2.1 优点

资源利用率高；系统吞吐量大；

5.2.2 缺点

平均周转时间长；无交互能力；

5.2.3 需要解决的问题：
  1. 处理机争用问题
  2. 内存分配和保护问题
  3. IO设备分配问题
  4. 文件的组织和管理问题
  5. 作业管理问题
  6. 用户与系统的接口问题
5.2.4 分时系统

在一台主机上连接多个配有显示器和键盘的终端并由此所组成的系统，该系统允许多个用户同时通过自己的终端，以交互方式使用计算机，共享主机中的资源

  1. 引入原因：为了满足用户对人一机交互的需求

  2. 特征：

    • 多路性
    • 独立性
    • 及时性（作业直接放入内存，采用时间片轮转运行方式）
    • 交互性
5.2.5 实时系统

类型：周期性实时任务和非周期性实时任务；硬实时任务和软实时任务

5.2.6 ※实时系统和分时系统特征的比较
  1. 多路性
    • 分时系统的多路性表现为系统按分时原则多个终端用户服务
    • 实时系统的多路性表现为系统周期性地对多路现场信息进行采集，以及对多个对象或多个执行机构进行控制。
  2. 独立性
  3. 及时性
  4. 交互性
  5. 可靠性
    • 实时系统要求系统高度可靠，往往采取多级容错措施来保障系统的安全性及数据的安全性。
5.2.7 微软OS发展
  1. 单用户单任务操作系统 eg：CP/M MS-DOS
  2. 单用户多任务操作系统 eg：Windows
  3. 多用户多任务操作系统 eg：Unix

6 OS的主要功能

6.1 处理机管理功能

∵处理机分配和运行都是以进程为基本单位 ∴对处理机的管理可归结为对进程的管理

  • ※进程互斥：指多个进程在对临界资源进行访问时，应采用互斥方式
  • ※进程同步：指在相互合作去完成共同任务的多个进程之间，由同步机构对它们的执行次序加以协调

6.2 存储器管理功能

为多道程序的运行提供良好的环境，提高存储器的利用率，方便用户使用，并能从逻辑上扩充内存
※静态&动态分配方式

6.3 设备管理功能

6.3.1 主要任务
  1. 完成用户进程提出的IO请求，为用户进程分配所需的IO设备，并完成指定的IO操作
  2. 提高CPU和IO设备的利用率，提高IO速度，方便用户使用IO设备

设备处理程序又称为设备驱动程序

6.4 文件管理功能

6.5 OS的基本特性

6.5.1 异
  1. 批处理系统有着高的资源利用率和系统吞吐量
  2. 分时系统能获得及时响应（∵作业直接放入内存）
  3. 实时系统具有实时特征
6.5.2 同

并发，共享，虚拟，异步（※并发和共享是多用户多任务OS的两个最基本的特征）
并发——正是程序能并发执行这一特征，才使得OS能有效地提高系统中的资源利用率，增加吞吐量

  • 并行：指两个或多个事件在同一时刻发生
  • 并发：指两个或多个事件在同一时间间隔内发生

6.6 OS结构设计

6.6.1 整体
6.6.2 模块化（模块—接口法）（无序模块法）
6.6.2.1 内聚性

指模块内部各部分间联系的紧密程度。内聚性越高，模块独立性越强。

6.6.2.2 耦合性

指模块间相互联系和相互影响的程度。耦合度越低，模块独立性越强。

6.6.2.3 优点
  1. 提高OS设计的正确性、可理解性和可维护性
  2. 增加OS的适应性
  3. 加速OS的开发过程。
6.6.2.4 缺点

OS设计阶段，设计者每一个决定应该建立在上一个决定的基础上，模块化结构中各模块齐头并进，无法寻找一个可靠的决定顺序，造成决定的“无序性”。

6.6.3 分层——高层仅依赖于紧邻它的底层
6.6.3.1 优点
  1. 易保证系统的正确性
  2. 易扩充和易维护性
6.6.3.2 缺点

系统效率低

∵层次结构是分层单向依赖，OS每执行一个功能，通常要自上而下穿越多个层次
6.6.4 客户/服务器模式
6.6.4.1 优点
  1. 数据的分布处理和存储
  2. 便于集中管理
  3. 灵活性和可扩充性
  4. 易于改编应用软件。
6.6.4.2 缺点

存在着不可靠性和瓶颈问题。一旦服务器故障，将导致整个网络瘫痪。

6.6.5 微内核——将操作系统最基本的部分放入微内核
6.6.5.1 基本功能
  1. 进程（线程）管理
  2. 低级存储器管理
  3. 中断和陷入处理。
6.6.5.2 优点
  1. 提高了系统的可扩展性
  2. 增强了系统的可靠性
  3. 可移植性
  4. 提供了对分布式系统的支持
  5. 融入了面向对象技术。

第二章 进程的描述和控制

1 前驱图——有向无循环图

2 程序顺序执行时的特征：

  1. 顺序性：每一操作必须在下一个操作开始之前结束
  2. 封闭性：程序运行时独占全机资源，资源的状态只有本程序才能改变它，一旦执行，结果不受外界影响
  3. 可再现性

3 程序并发执行

  1. 原因：为了提高资源利用率和系统吞吐量，通常采用多道程序技术，将多个程序同时装入内存，并发运行
  2. 特征：
    • 间断性
    • 失去封闭性
    • 不可再现性

※4 进程

4.1 定义

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。包括程序段、数据段和PCB三部分。
创建进程实质上就是创建进程实体中的PCB。

4.2 特征

除了进程具有程序没有的PCB结构以外，还具有：

  • 动态性 进程是动态的，程序是静态的
  • 并发性 没有建立PCB的程序是不能参与并发执行的
  • 独立性
  • 异步性
4.3 状态：就绪 执行 阻塞

4.4 进程控制——是进程管理中最基本的功能
4.4.1 OS内核

  1. 定义：
    通常将一些与硬件紧密相关的模块（如中断处理程序等）、各种常用设备的驱动程序以及运行频率较高的模块（如时钟管理、进程调度），都安排在紧靠硬件的软件层次中，将它们常驻内存——内核。目的是便于对这些软件进行保护，提高OS的运行效率。

  2. 状态：

    • 系统态：又称管态，内核态，具有较高的特权，能执行一切指令，访问所有寄存器和存储区
    • 用户态：又称目态

  3. 功能：支撑功能、资源管理功能

    • 支撑功能：
      • 中断处理：中断处理是内核最基本的功能。
      • 时钟管理：时钟管理是内核的一项基本功能。
      • 原语操作：“原子操作”，即不可分割的基本单位。∴原语在执行过程中不允许被中断。原子操作在系统态下执行，常驻内存。
    • 资源管理功能：
      • 进程管理
      • 存储器管理
      • 设备管理
4.4.2 进程的创建
  1. 允许一个进程创建另一个进程。但Windows不存在任何进程层次结构的概念。
  2. 进程图
  3. 引起创建进程的事件：用户登录、作业调度、提供服务、应用请求
  4. 创建过程
    OS调用进程创建原语Create→申请空白PCB→为新进程分配其运行所需的资源→初始化进程控制块PCB→如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列
4.4.3 进程的终止
  1. 引起进程终止的事件：
    • 正常结束、异常结束（越界错、保护错、非法指令、运行超时 etc）、外界干预
  2. 终止过程
    OS调用进程终止原语Terminate → 根据被终止进程的标识符，从PCB中检索出该进程的PCB，从中读出该进程的状态 → 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度 → 若该进程还有子孙进程，还应将其所有子孙进程也都予以终止，以防它们成为不可控的进程 → 将被终止进程所拥有的全部资源或者归还给其父进程，或者归还给系统 → 将被终止进程(PCB)从所在队列(或链表)中移出，等待其它程序来搜集信息
4.4.4 进程的阻塞和唤醒
  1. 引起进程阻塞和唤醒的事件：
    向系统请求共享资源失败、等待某种操作的完成、新数据尚未到达、等待新任务的到达。
  2. 进程阻塞过程：
    进程通过调用阻塞原语Block将自己阻塞。可见，阻塞是进程自身的一种主动行为。由于该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。
  3. 进程唤醒过程：
    唤醒原语Wakeup首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。
4.4.5 进程的挂起和激活
  1. 挂起：
    使用挂起原语Suspend。检查被挂起的进程状态，若是活动就绪状态，则改为静止就绪状态；若活动阻塞状态，则改为静止阻塞状态；把该进程的PCB复制到指定内存区域；若正在执行，则重新调度。
  2. 激活：
    使用激活原语Active。将进程调入内存，若为静止就绪，则改为活动就绪；ruo为静止阻塞，则改为活动阻塞。

4.5 进程同步：硬件同步机制、信号量机制（最常用）、管程机制
4.5.1 两种制约关系
  1. 间接相互制约关系：对于临界资源，多个进程只能互斥访问    进程互斥
  2. 直接相互制约关系：源于进程之间的相互合作    进程同步
4.5.2 互斥共享方式：

在一段时间内，只允许一个进程访问某个资源，仅当当前进程访问完毕并释放该资源后，才允许另外一个进程对其访问，这种资源共享方式成为互斥式共享。

4.5.3 临界区：每个进程中访问临界资源的那段代码成为临界区
4.5.4 同步机制应遵循的规则：空闲让进；忙则等待；有限等待；让权等待
4.5.5 硬件同步机制

关中断：实现互斥的最简单的方法之一。进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开 中断。这样，进程在临界区执行期间，计算机系统不响应中断，从而不会引发调度，也就不会发 生进程或线程切换。
缺点：滥用关中断权力可能导致严重后果；关中断时间过长，会影响系统效率，限制了处理器交叉执 行程序的能力；关中断方法也不适用于多CPU 系统。

  • 利用Test-and-Set指令实现互斥 ：借助一条硬件指令——“测试并建立”指令TS以实现互斥。
  • 利用Swap指令实现进程互斥：
    • Ⅵ信号量机制
    • 整型信号量：P V操作 P–wait V–signal
    • 记录型信号量
    • AND信号量
    • 信号量集

④进程同步
描述：能够并发、改善利用率、提高吞吐量、但使系统复杂
一、进程同步的基本概念
制约关系：间接相互制约关系、直接相互制约关系
间接相互制约关系：互斥共享
直接相互制约关系：合作共享，异步性要做好
临界资源：生产者-消费者问题、
临界区、：进入区、临界区、退出区、剩余区
同步机制应遵循的规则：空闲让进、忙则等待、有限等待、让权等待

二、硬件同步机制
关中断：缺点多：滥用关中断.造成严重后果、关中断时间过长、不适用于多CPU系统（因为一个处理器关中断并不能防止进程在其他处理器上执行相同的临界段代码）
Test-and-Set：不断测试lock，如果是FALSE，就进入临界区，并lock == TRUE；否则测试到TS(s) == TRUE
Swap指令：一直等，直到key == TRUE
但以上都不符合“让权等待”原则

三、信号量机制
整形信号量：S≤0，就一直等，直到释放互斥资源
记录型信号量：整形信号量不符合“让权等待”原则。如果有资源，就分配，如果无，就插入阻塞队列；释放资源，如果有等待，就激活
AND型信号量：一口气全分配
信号量集：有多个信号量（S信号量,至少要t个,每次分配d个）

四、信号量的应用
利用信号量实现进程互斥：mutex = ( -1, 0, 1）= （无，一临一阻队， 一临一信队）
利用信号量实现前趋关系：需要的信号量被占用了，就这样实现

经典进程的同步问题
一、生产者-消费者问题
记录型信号量解决：如果缓冲区空，而且能够获取信号量，就投放产品；如果缓冲区有产品，而且能够获取信号量，就消费
AND信号量解决：一口气全分配
管程解决：利用管程只有一个进程能够使用的属性

二、哲学家进餐问题
记录型信号量解决：先拿左.后那右、先放左.后放右
解决死锁：最多4人取筷子、先检查.有左右筷子才能取、奇左右.偶右左
AND信号量解决：一口气全分配

三、读者-写者问题
描述：可以多读一、一旦开始写.就不能读或写
记录型信号量解决：
读操作：等rmutex就是为了改readcount→无人读？看看是否在写.等wmutex→readcount++→自增完成.rmutex还你→读读读→等rmutex为了自减readcount→无人读？可以写了.还你wmutex
写操作：等wmutex.即无读无写→写完.还你wmutex
利用信号量集机制：
读：限制reader个数→如果mx是1.就读→最后释放一个reader个数
写：如果mx是1.并且读者数为0.就写→写完释放mx

4.6 进程通信——进程之间的信息交换
4.6.1 高级通信机制分为四大类：共享存储器系统；管道通信系统；信息传递系统；客户机-服务器系统。
4.6.2 共享存储器系统可分为两种：基于共享数据结构的通信方式；基于共享存储区的通信方式。
4.6.3 为了协调双方的通信，管道机制必须提供以下三方面的协调能力：
  1. 互斥，即当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。
  2. 同步，指当写(输入)进程把一定数量(如4 KB)的数据写入pipe，便去睡眠等待，直到读(输出)进程取走数据后再把它唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后才将之唤醒。
  3. 确定对方是否存在，只有确定了对方已存在时才能进行通信。
4.7 进程管理中的数据结构——资源信息表或进程信息表
4.7.1 OS管理的这些数据结构一般分为以下四类：

内存表、设备表、文件表和用于进程管理的进程表，通常进程表又被称为进程控制块PCB。

4.7.2 PCB的作用：
  1. 作为独立运行基本单位的标志
  2. 能实现间断性运行方式
  3. 提供进程管理所需要的信息
  4. 提供进程调度所需要的信息
  5. 实现与其它进程的同步与通信。
4.7.3 PCB中的信息：
  1. 进程标识符
  2. 处理机状态
  3. 进程调度信息
  4. 进程控制信息
4.7.4 PCB的组织方式：
  1. 线性方式
  2. 链接方式
  3. 索引方式

※※※5 经典进程的同步问题

6 线程——作为调度与分派的基本单位

6.1 引入

  1. 进程——解决了单处理机程序并发执行的问题
  2. 线程——提高程序并发执行的速度

6.2 线程与进程的比较

  1. 调度的基本单位
  2. 并发性
  3. 拥有资源：线程只拥有一点必不可少的能保证独立运行的资源
  4. 独立性：在同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多
  5. 系统开销：线程小；在一些OS中，线程的切换、同步和通信都不需要OS内核的干预
  6. 支持多处理机系统

6.3 线程的状态：执行 就绪 阻塞 线程控制块：TCB

6.4 多线程OS中的进程属性

  1. 进程是一个可拥有资源的基本单位，仍是作为系统资源分配的基本单位
  2. 多个线程可并发执行
  3. 进程已不是可执行的实体，而把线程作为独立运行的基本单位

6.5 线程的实现方式

  1. 内核支持线程KST
  2. 用户级线程ULT

第三章 处理机的调度与死锁

3.1 注：

3.1.1 调度层次

  1. 高级调度：又叫长程调度或作业调度或接纳调度，对象是作业，主要用于多道批处理系统，在分时系统和实时系统中不设置高级调度
  2. 低级调度：又叫短程调度或进程调度，对象是进程。是最基本的一种调度，三种OS中都必须配置此种调度
  3. 内存调度，就是存储器管理中的对换功能提高内存利用率和系统吞吐率

3.1.2 处理机调度算法的共同目标

  1. 处理机利用率：
  2. 公平性：使诸进程都获得合理的CPU 时间
  3. 平衡性：使系统中的CPU和各种外部设备都能经常处于忙碌状态
  4. 策略强制执行

3.1.3 批处理系统的目标

  1. 平均周转时间短
    周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔（被称为作业周转时间），包括：外存上等待时间，进程在就绪队列上等待时间，CPU上执行时间，等待IO时间。
    应使作业周转时间和作业的平均周转时间尽可能短。可把平均周转时间描述为：

    平均带权周转时间则可表示为：

    作业的周转时间T与系统为它提供服务的时间Ts之比，即W = T/Ts

  2. 系统吞吐量高 吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理作业的平均长度有关。

  3. 处理机利用率高

3.1.4 分时系统的目标

  1. 响应时间快
    响应时间是指从用户通过键盘提交一个请求开始，直到屏幕上显示出处理结果为止的一段时间间隔
  2. 均衡性

3.1.5 实时系统的目标

  1. 截止时间的保证
  2. 可预测性

3.1.6 作业：包括程序、数据和一份作业说明书。

  1. 在批处理系统中，是以作业作为基本单位从外存调入内存的。
  2. 作业步：在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤得到结果。
  3. 作业控制块JCB：保存了系统对作业进行管理和调度所需的全部信息。
  4. 作业运行的三个阶段：收容 运行 完成
  5. 作业运行的三个状态：后备状态 运行状态 完成状态

3.1.7 作业调度的主要任务：

  1. 根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求
  2. 按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源
  3. 将新创建的进程排在就绪队列上等待调度。

3.1.8 短作业优先算法SJF——以作业的长短来计算优先级，作业的长短是以作业所要求的运行时间来衡量的

3.1.8.1 SJF算法可以分别用于作业调度和进程调度。

缺点：

  1. 必须预知作业的运行时间。很难准确估计作业的运行时间，一般都会偏长估计。
  2. 对长作业非常不利，长作业的周转时间会明显地增长。该算法完全忽视作业的等待时间，可能使作业等待时间过长，出现饥饿现象。
  3. 人—机无法实现交互。
  4. 该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理。
3.1.8.2 高响应比优先调度算法HRRN

  1. FCFS算法只考虑作业等待时间，而忽视了作业运行时间

  2. SJF算法只考虑作业运行时间，而忽视了作业等待时间

  3. HRRN算法考虑了两者，既照顾了短作业，又不使长作业等待时间过长，从而改善了处理机调度的性能

    • 等待时间相同，要求的服务时间越短，优先级越高，类似SJF
    • 要求服务时间相同，等待时间越长，优先级越高，类似FCFS
    • 对于长作业，随等待时间的增加，优先级提高。

3.1.9 进程调度

3.1.9.1 三种类型OS
  1. 单用户操作系统:DOS
  2. 分时操作系统:WIndows,Unix,Linux
  3. 实时操作系统:uCOS-II,VxWorks
3.1.9.2 进程调度的任务：

保存处理机的现场信息，按某种算法选取进程，把处理器分配给进程

3.1.9.3 进程调度方式
  1. 非抢占方式：一旦把处理机分配给某进程后，就一直让它运行下去，决不会因为时钟中断或任何其它原因去抢占当前正在运行进程的处理机。
  2. 抢占方式：允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。
  3. 原则：优先权原则，短进程优先原则，时间片原则
3.1.9.4 ※轮转调度算法
3.1.9.5 ※优先级调度算法
3.1.9.6 ※多级反馈队列算法
3.1.9.7 ※基于公平原则的调度算法

3.1.10 实时调度

3.1.10.1 实现实时调度的基本条件
  1. 提供必要的信息
  2. 系统处理能力强
  3. 采用抢占式调度机制
  4. 具有快速切换机制
3.1.10.2 实时调度的分类
  1. 非抢占式调度算法：非抢占式轮转调度算法；非抢占式优先调度算法
  2. 抢占式调度算法：基于时钟中断的抢占式优先级调度算法；立即抢占的优先级调算法（要求OS具有快速响应外部事件的能力）
3.1.10.3 ※最早截止时间优先EDF算法
  1. 非抢占式调度方式用于非周期实时任务
  2. 抢占式调度方式用于周期实时任务
3.1.10.4 ※最低松弛度优先LLF算法

优先级倒置及解决方法

3.1.11 ※死锁

3.1.11.1 定义：

如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的（Deadlock）。

3.1.11.2 产生死锁的必要条件，必须同时具备，缺一不可：
  1. 互斥条件
  2. 请求和保持条件
  3. 不可抢占条件
  4. 循环等待条件
3.1.11.3 计算机中的死锁

死锁的起因，通常是源于多个进程对资源的争夺，不仅是对不可抢占资源进行争夺时会发生死锁，而且对可消耗资源（又称为临时性资源）进行争夺时也会引起死锁。

  1. 竞争不可抢占性资源引起死锁
  2. 竞争可消耗资源引起死锁
  3. 进程推进顺序不当引起死锁
3.1.11.4 处理死锁的方法
3.1.11.4.1 预防死锁
  1. 破坏“请求和保持”条件
  2. 破坏“不可抢占”条件
  3. 破坏“循环等待”条件
3.1.11.4.2 避免死锁 eg：利用银行家算法避免死锁
3.1.11.4.3 检测死锁

为了能对系统中是否已发生了死锁进行检测，在系统中必须：保存有关资源的请求和分配信息；提供一种算法，它利用这些信息来检测系统是否已进入死锁状态。

  1. 资源分配图
  2. 死锁定理
  3. 死锁检测中的数据结构
3.1.11.4.4 解除死锁

第四章 存储器管理

4.1 存储层次

  1. 寄存器和主存储器被称为可执行存储器。
  2. 主存储器简称内存或主存，是计算机系统中的主要部件，用于保存进程运行时的程序和数据。
  3. 高速缓存介于寄存器和存储器之间的存储器，主要用于备份主存中较常用的数据，以减少处理机对主存储器的访问次数，这样可大幅度地提高程序执行速度
  4. 磁盘缓存本身并不是一种实际存在的存储器

4.2 应用程序的编译、链接、装入

4.2.1 链接：

由链接程序(Linker)将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块(Load Module)

  1. 静态链接
  2. 装入时动态链接
  3. 运行时动态链接

4.2.2 装入：由装入程序(Loader)将装入模块装入内存

  1. 绝对装入：在编译时就知道程序将要在内存中的物理地址，产生绝对地址(即物理地址)的目标代码。
  2. 可重定位装入：又称为静态重定位。对于用户程序编译所形成的若干个目标模块，它们的起始地址通常都是从0开始的，程序中的其它地址也都是相对于起始地址计算的。
  3. 动态运行时装入：又称为动态重定位。装入程序把装入模块装入内存后，并不立即把装入模块中的逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行的时候。
  4. 重定位：把在装入时对目标程序中指令和数据地址的修改过程称为重定位。逻辑地址→物理地址

4.3 连续分配存储管理方式

4.3.1 单一连续分配：

单道程序环境，在用户区内存中，仅装有一道用户程序，即整个内存的用户空间由该程序独占

4.3.2 固定分区分配：

将内存划分为多个固定大小的分区，每个分区装入一道作业，例如IBM 360。程序通常采用静态重定位的方式装入内存。
缺点：不能实现各进程共享一个主寸去，利用率低，会产生内部碎片

4.3.2.1 划分分区的方法
  1. 分区大小相等：缺乏灵活性，但方便实用，被广泛采用。
  2. 分区大小不等：一般会划分成多个较小分区、适量中等分区和少量大分区。
4.3.2.2 内存分配：

将分区按其大小进行排队，建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)。

4.3.3 动态分区分配：

为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业

4.4 ※基于顺序搜索的动态分区分配算法——适用于不太大的系统。

将系统中的空闲分区连接成一个链。但对于大型系统，因为链太长，所以效率低下。

  1. 首次适应(first fit，FF)算法
  2. 循环首次适应(next fit，NF)算法
  3. 最佳适应(best fit，BF)算法
  4. 最坏适应(worst fit，WF)算法

4.5 基于索引搜索的动态分区分配算法——大中型系统中采用

  1. 快速适应(quick fit)算法 又称为分类搜索法
  2. 伙伴系统(buddy system)
  3. 哈希算法

4.6 内部碎片&&外部碎片的区别

4.7 ※非连续（离散）分配存储管理方式

4.7.1 分页存储管理方式

内存空间分为若干个“物理块”或“页框”。
页和块大小相同。

  1. 页面——进程的逻辑地址空间被分成若干个页，并加从0开始的编号；内存的物理地址空间分成若干物理块，并加从0开始的编号。最后会形成页内碎片。
  2. 页面大小通常为1K-8K
  3. 页表——在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程仍然能够正确地运行，即能在内存中找到每个页面所对应的物理块，系统又为每个进程建立了一张页面映像表，简称页表。每个进程有一个页表。由页号和块号组成。

4.7.2 地址变换机构——逻辑地址物理地址 借助页表完成

  1. 基本的地址变换机构
    大部分页表是驻留内存的。
    系统中仅设置一个页表寄存器（PTR），存放页表在内存中的起始地址和长度。
    进程未执行时，页表起始地址和长度放在该进程的PCB中，执行时才装入页表寄存器。

  1. 具有块表的地址变换机构
    为提高地址变换速度，增设特殊高速缓冲寄存器，又称“联想寄存器”或“快表”。
    CPU给出有效地址，在快表中查找页号：如果找到，直接可以读出物理地址；如果找不到，再到内存中找，并重新修改快表（如果快表已满，则需要换出一个被认为是不再需要的页表项）

4.7.3 访问内存的有效时间(Effective Access Time，EAT)

4.7.3.1 定义：

从进程发出指定逻辑地址的访问请求，经过地址变换，到在内存中找到对应的实际物理地址单元并取出数据，所需要花费的总时间，称为内存的有效访问时间。
假设访问一次内存的时间为t，在基本分页存储管理方式中，有效访问时间分为第一次访问内存时间(即查找页表对应的页表项所耗费的时间t)与第二次访问内存时间(即将需要的指令或数据取出所耗费的时间t)之和：
EAT = t + t = 2t
在引入快表的分页存储管理方式中，有效访问时间的计算公式即为：
EAT=а×λ+(t+λ)(1—а)+t=2t+λ—t×а
上式中，λ表示查找快表所需要的时间，а表示命中率，t表示访问一次内存所需要的时间。

4.7.4 两级和多级页表

两级页表：为离散分配的页表再建立一张页表，称为外层页表(Outer Page Table)，在每个页表项中记录了页表页面的物理块号。为了方便实现地址变换，在地址变换机构中，同样需要增设一个外层页表寄存器，用于存放外层页表的始址

4.7.5 反置页表

4.7.6 分段存储管理方式：用户程序地址空间分为若干大小不同的段
单道多道 单一连续分配固定分区分配
使用不同大小的程序要求 固定分区分配动态分区分配
提高内存利用率 连续分配离散分配（分页）
满足程序员编程和使用方便 出现分段（需要语言编译程序支持）
4.7.6.1 引入原因
  1. 方便编程
  2. 信息共享
  3. 信息保护
  4. 动态增长
  5. 动态链接
    在程序运行过程中，当需要调用某个目标程序时，才将该段(目标程序)调入内存并进行链接。 动态链接要求的是以目标程序（段）作为链接的基本单位。∴分段存储管理方式非常适合动态链接
4.7.6.2 基本原理
4.7.6.2.1 分段

分段地址中的地址具有如下结构

该地址结构中，允许一个作业最长有64K个段，每个段最长64KB

4.7.6.2.2 段表——为每个进程建立一张段映射表

在分段式存储管理系统中，则是为每个分段分配一个连续的分区。进程中的各个段，可以离散地装入内存中不同的分区中。每个段占一个表项，记录该段在内存中的起始地址（基址）和段长。

4.7.6.2.3 地址变换机构

4.7.7 分页和分段的主要区别

  1. 页是信息的物理单位，分页仅仅是系统管理上的需要，对用户不可见。段是逻辑单位，分段的目的是能更好地满足用户的需要。
  2. 页的大小固定且由系统决定，每个系统中只能有一种大小的页面。段的长度不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分

4.7.8 信息分享

可重入代码又称为纯代码，是一种允许多个进程同时访问的代码。

4.7.9 段页式存储管理方式：上面两点结合，目前应用很广

4.7.9.1 基本原理：

先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。

4.7.9.2 地址变换过程

配置一个段表寄存器，存放段表始址和段长TL。
首先利用段号S，将它与段长TL进行比较，若未越界，利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，利用逻辑地址中的段内页号P来获得对应页的页表项位置，读出该页所在的物理块号b，再利用块号b和页内地址来构成物理地址。

4.7.9.3 为了获得一条指令或数据，需要三次访问内存。
  1. 访问内存中的段表，取得页表地址。
  2. 访问内存中的页表，取得物理块号，并与页内地址合并成物理地址。
  3. 取出内存中的指令或数据。

第五章 虚拟存储器

5.1 定义：

指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

5.2 特征：多次性，对换性，虚拟性

5.3 ※实现方法

5.3.1 分页请求系统：

在分页系统基础上增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。

5.3.1.1硬件支持：
  1. 请求分页的页表机制
  2. 缺页中断机构
  3. ※地址变换机构
5.3.1.2 实现请求分页的软件：用于实现调页的软件和实现页面置换的软件。
5.3.1.3 请求分页中的内存分配：
  1. 最小物理块数的确定：指能保证进程正常运行所需要的最小物理块数
  2. 内存分配策略：
    • 固定分配局部置换
    • 可变分配全局置换
    • 可变分配局部置换
  3. 物理块分配算法：
    • 平均分配算法
    • 按比例分配算法
    • 考虑优先权的分配算法

5.3.2 请求分段系统：

在分段系统的基础上增加了请求调段及分段置换功能后形成的段式虚拟存储系统。

5.3.2.1 硬件支持：
  1. 请求分段的段表机制
  2. 缺页中断机构
  3. 地址变换机构
5.3.2.2 软件支持：用于实现请求调段的软件和实现段置换的软件。

5.4 页面调入策略

5.4.1 何时调入页面

  1. 预调页策略：调入那些预计不久之后便会被访问的页面，目前成功率仅约50%。但某些方面取得了良好的效果。
  2. 请求调页策略：若发现页面不在内存，立即提出请求，由OS将其调入内存。该方法易于实现，目前虚拟存储器中，大多采用该策略。

5.4.2 从何处调入页面

请求调页系统的外存分为两部分：文件区（离散分配方式，慢）和对换区（连续分配方式，快）。

  1. 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。
  2. 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改，则不必再将它们重写到磁盘(换出)，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时便须调到对换区，以后需要时再从对换区调入。

5.4.3 页面调入过程

5.4.4 缺页率

假设一个进程的逻辑空间为n页，系统为其分配的内存物理块数为m(m≤n)。如果在进程的运行过程中，访问页面成功(即所访问页面在内存中)的次数为S，访问页面失败(即所访问页面不在内存中，需要从外存调入)的次数为F，则该进程总的页面访问次数为A = S + F，那么该进程在其运行过程中的缺页率即为 f = F / A

5.4.4.1 影响缺页率的几个因素：
  1. 页面大小
  2. 进程所分配的物理块数目
  3. 页面置换算法
  4. 程序固有特性（程序编制的局部化程度）

假设被置换的页面被修改的概率是β，其缺页中断处理时间为ta，被置换页面没有被修改的缺页中断时间为tb，那么，缺页中断处理时间的计算公式为t=β×ta+(1—β)×tb

5.5 ※页面置换算法

5.5.1 最佳置换算法(OPT)：

其所选择的被淘汰页面将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。
该算法是无法实现的，可以利用该算法去评价其它算法。

5.5.2 先进先出(FIFO)页面置换算法：

淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

5.5.3 Belady异常：

当所分配的物理块数增大而缺页中断数不减反增的异常现象。
FIFO算法可能出现Belady异常，而LRU和OPT算法永远不会出现Belady异常。

5.5.4 最近最久未使用（LRU）置换算法：

选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，选择该时间最大的做为淘汰对象。

5.5.5 最少使用（LFU)置换算法：

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

5.5.6 Clock置换算法

5.5.7 改进的Clock置换算法

5.5.8 页面缓冲算法（PBA）

5.5.8.1 PBA算法的主要特点是：
  1. 显著地降低了页面换进、换出的频率，使磁盘I/O的操作次数大为减少，因而减少了页面换进、换出的开销；
  2. 正是由于换入换出的开销大幅度减小，才能使其采用一种较简单的置换策略，如先进先出(FIFO)算法，它不需要特殊硬件的支持，实现起来非常简单。
    • 空闲页面链表
    • 修改页面链表

5.5.9 访问内存的有效时间

与基本分页存储管理方式不同，在请求分页管理方式中，内存有效访问时间不仅要考虑访问页表和访问实际物理地址数据的时间，还必须要考虑到缺页中断的处理时间。

  1. 被访问页在内存中，且其对应的页表在快表中
    • EAT=λ+t λ：查找快表的时间 t：访问实际物理地址所需的时间
  2. 被访问页在内存中，且其对应的页表不在快表中
    • EAT=λ+t+λ+t 查找快表时间、查找页表时间、更新快表、访问实际物理地址所需的时间
  3. 被访问页不在内存中
    • EAT=λ+t+ε+λ+t 查找快表、查找页表、处理缺页中断时间、更新快表、访问实际物理地址

第六章 输入输出系统

6.1 IO系统的主要任务：

完成用户提出的IO请求，提高IO速率，提高设备的利用率

6.2 IO系统的基本功能

隐藏物理设备的细节，与设备的无关性，提高处理机和IO设备的利用率，对IO设备进行控制，确保对设备的正确共享，错误处理

6.3 IO设备分类：

  1. 按使用特性分
    • 人机交互类外设，如打印机、显示器、键盘、鼠标等
    • 存储设备，如磁盘、光盘等
    • 网络通信设备，如各种网络接口、调制解调器
  2. 按传输速率分
    • 低速设备，如键盘、鼠标。每秒几个到数百个字节
    • 中速设备，如打印机。每秒数千个字节至数万个字节
    • 高速设备，如磁盘。每秒数百个千字节到千兆字节
  3. 按信息交换单位分
    • 块设备，属于有结构设备，如磁盘
    • 字符设备，属于无结构设备，如打印机

6.4 IO控制方式：

  1. 程序直接控制方式
  2. 中断驱动方式
  3. DMA方式
  4. 通道控制方式

6.5 系统调用是应用程序取得OS所有服务的唯一途径。C语言中，首先提供了与系统调用相对应的库函数。

6.6 缓冲区的引入

  1. 缓和CPU与I/O设备间速度不匹配的矛盾
  2. 减少对CPU的中断频率，放宽对CPU中断响应时间的限制
  3. 解决数据粒度不匹配的问题
  4. 提高CPU和I/O设备之间的并行性。

6.7 各种缓冲区

  1. 单缓冲区
  2. 双缓冲区
  3. 环形缓冲区
  4. 缓冲池

第七章 文件管理

系统运行时，计算机以进程为基本单位进行资源的调度和分配；在用户进行的输入输出中，则以文件为基本单位。

7.1 文件的组成：

包含一块存储空间（其实是存储空间中的数据），包含分类和检索信息，包含关于访问权限的信息。

7.2 文件的结构：数据项、记录和文件

7.2.1 数据项：在文件系统中，数据项是最低级的数据组织形式。

可分为以下两种类型：

  1. 基本数据项：用于描述一个对象的某种属性的一个值，例如姓名、证件号码、日期等。是数据中可命名的最小逻辑数据单位，即原子数据。
  2. 组合数据项：由多个基本数据项组成。

7.2.2 记录：是一组相关数据项的集合，用于描述一个对象在某方面的属性。

如一个考生报名记录包括姓名、出生日期、报考学校、身份证号等一系列域。

7.2.3 文件：是指由创建者所定义的、具有文件名的一组相关元素的集合。

可分为以下两种类型：

  1. 有结构文件：文件由一组相似记录组成，又称记录式文件。例如报考某一学校的所有考生报名信息。
  2. 无结构文件：看作一个字符流，又称流式文件。例如一个二进制文件或字符文件。

7.3 文件的属性

  1. 名称，唯一。
  2. 标识符，文件系统内标识文件的唯一标志，一般为数字。
  3. 类型，一般由不同的扩展名表示。
  4. 位置。
  5. 大小。
  6. 保护，对文件进行保护的访问控制信息。
  7. 时间、日期和用户标识，创建、上次修改、上次访问等信息。

7.4 文件的基本操作

7.5 文件的打开与关闭

每个打开的文件都有如下信息：

  1. 文件指针，这个指针对打开文件的某个进程来说是唯一的。
  2. 文件打开计数，多个进程共用一个文件时用。
  3. 文件磁盘位置，该信息直接存入内存，避免每个文件操作都从磁盘读取。
  4. 访问权限。

7.6 文件的逻辑结构——指文件在外存上的存储组织形式

  1. 无结构文件（流式文件）
  2. 有结构文件（记录式文件）
    • 顺序文件
    • 索引文件
    • 索引顺序文件
    • 直接文件或散列文件

7.7 目录结构：目录在用户（应用程序）所需要的文件名和文件之间提供一种映射

  1. 实现“按名存取”。
  2. 提高对目录的检索速度。
  3. 文件共享。
  4. 允许文件重名。

7.8 文件控制块FCB：用来存放控制文件需要的各种信息的数据结构,，以实现“按名存取”。

FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。
FCB包含： 文件基本信息；存取控制信息；使用信息。

7.9 索引结点

7.9.1 引入：

在检索目录文件的过程中，只用到了文件名，仅当找到一个目录项时，才需要从该目录项中读出该文件的物理地址。因此，有的系统采用将文件名和文件描述信息分开的方法，文件描述信息单独形成一个称为索引结点的数据结构，简称为i结点。在文件目录中的每个目录项仅由文件名和指向该文件所对应的i结点的指针构成。

7.9.2 索引结点主要包括以下内容：

  1. 文件主标识符，即拥有该文件的个人或小组的标识符；
  2. 文件类型，包括正规文件、目录文件或特别文件；
  3. 文件存取权限，指各类用户对该文件的存取权限；
  4. 文件物理地址，每一个索引结点中含有13个地址项，即iaddr(0)～iaddr(12)，它们以直接或间接方式给出数据文件所在盘块的编号；
  5. 文件长度，指以字节为单位的文件长度；
  6. 文件连接计数，表明在本文件系统中所有指向该(文件的)文件名的指针计数；
  7. 文件存取时间，指出本文件最近被进程存取的时间、最近被修改的时间及索引结点最近被修改的时间。

7.10 文件目录结构

需要执行的操作：搜索、创建文件、删除文件、显示目录、修改目录。

  1. 单级文件目录
  2. 两级文件目录
  3. 多级目录结构（树形结构目录)：最通用且实用的文件目录无疑是树形结构目录

7.11 文件共享

  1. 基于有向无环图实现文件共享：有向无环图DAG，利用索引结点（硬链接）（文件的物理地址及其它的文件属性等信息，不再是放在目录项中，而是放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针）
  2. 利用符号链接实现文件共享（软链接）

第八章 磁盘存储器的管理

8.1 磁盘存储器

∵磁盘存储器不仅容量大，存取速度快，而且可以实现随机存取 ∴磁盘存储器是实现虚拟存储器和存放文件最理想的外存。

8.2 磁盘存储器管理的主要任务和要求：

  1. 有效地利用存储空间
  2. 提高磁盘的IO速度
  3. 提高磁盘系统的可靠性

8.3 常见的外存组织方式：

  1. 连续组织方式（连续分配方式）

    • 优点：顺序访问容易；顺序访问速度快
    • 缺点：
      • 要求为一个文件分配连续的存储空间
      • 必须事先知道文件的长度
      • 不能灵活地删除和插入记录
      • 对于那些动态增长的文件，由于事先很难知道文件的文件，很难分配空间。

  2. 链接组织方式

    • 优点：
      • 消除了磁盘的外部碎片，提高了外存的利用率
      • 对插入、删除和修改记录都非常容易
      • 能适应文件的动态增长，无需事先知道文件的大小。
    • 隐式链接：只适用于顺序访问
    • 显式链接：把用于链接文件各物理块的指针显式地存放在内存的一张链接表中——文件分配表FAT

  3. 索引组织方式

8.4 文件存储空间的管理：

  1. 空闲表法
  2. 空闲链表法
  3. 位视图法（位视图 盘块的分配 回收）

8.5 提高磁盘IO速度方法：

  1. 改进目录结构及检索目录方法来减少查找时间
  2. 选取好的文件存储结构，以提高对文件的访问速度
  3. 提高磁盘IO速度，能将文件中的数据块快速地从磁盘传送到内存中，或者相反

8.6 磁盘高速缓存：

在内存中为磁盘盘块设置的一个缓冲区，在缓冲区中保存了某些盘块的副本。

8.7 提高磁盘IO速度的其他方法：

  1. 提前读
  2. 延迟写
  3. 优化物理块的分布
  4. 虚拟盘

8.8 磁盘容错技术往往也被人们称为系统容错技术SFT。

8.9 提高磁盘可靠性技术：

第一级容错技术SFT1，第二级容错技术SFT2，集群技术的容错，后备系统（磁带机，硬盘，光盘驱动器）

第九章 补充 操作系统的生命周期

9.1 开发方法

  1. 交叉开发
    • 开发新操作系统，移植操作系统到新机器。
  2. 增量开发
    • 在已有操作系统上作内核，驱动程序更新和升级。

9.2 引导程序的特征：

  1. 必须是512B，因为BIOS只读512B到内存。
  2. 结尾两个字节必须是“55AA”，这是引导扇区的标志。
  3. 引导程序总是放在磁盘的0磁头，0磁道，1扇区(CHS，Cylinder-head-sector，寻址方式）。

由此可知，即使你随意编写一段512B的程序，只要放在该位置，并符合第2点，BIOS都会认为这是你的引导程序，并将其调入内存。

9.3 操作系统究竟如何开始:

9.3.1 由boot.s（bootsect.s）开始

boot被bios加载至7c00h（31k）处，并将自己移动到了地址90000h（576k）处，并跳转至那里。 使用BIOS中断将‘setup’直接加载到自己的后面地址90200h（576.5k)。将system加载到地址10000h处。

9.3.2 调入setup.s

9.3.3 调入system模块，第一个文件是head.s，在此启动main.c

9.3.4 执行main.c