软考操作系统2

考点归纳

1.操作系统基本知识

操作系统的分类、操作系统的作用、操作系统的内核、操作系统的配置

2.进程管理

进程的概念、进程状态转换图重点、同步与互斥、信号量与PV操作重点、进程死锁死锁的概念、条件和判定死锁、银行家算法重点、进程调度算法

3.存储管理

连续存储与非连续存储的概念、页式存储、段式存储、段页式存储、程序局部性原理、页面置换算法重点、通过逻辑地址计算物理地址、随机存取、直接存取、顺序存取

4.磁盘管理

磁盘的相关概念、磁道数计算、磁盘容量计算、磁盘调度算法重点、磁盘数据的存取过程

5.设备管理

数据传输控制方式（常见的4种）、虚拟设备与SPOOLING重点

6.文件管理

目录结构、绝对路径、相对路径、位示图重点、索引文件

计算机系统的一个重要组成部分是I/O系统。

 I/O系统包括: 
 ￥ 输入、输出设备 
 ￥ 存储功能的设备 
 ￥ 设备控制器

设备管理

一、设备管理的概念

设备管理程序提供下述功能

￥ 提供和进程管理系统的接口 
￥ 进行设备分配 
￥ 实现设备和设备之间、设备和CPU之间的并行操作 
￥ 进行缓冲区管理。

二、 I/O控制方式

(1) 程序I/O方式
(2) 中断控制I/O方式
(3) 直接存储器访问(DMA) 方式
(4) I/O通道控制方式

 ￥ 字节多路通道 
 ￥ 选择通道 
 ￥ 成组多路通道

三、缓冲管理

(1) 单缓冲 (2) 多缓冲 (3) 循环缓冲 (4) 缓冲池（Buffer Pool）

引入缓冲区的主要原因归结为以下几点：

$ 缓和CPU与I/O设备间速度不匹配的矛盾。 
$ 减少对CPU的中断频率，放宽对CPU中断响应时间的限制 
$ 提高CPU和I/O设备之间的并行性。

(1) 单缓冲（Single Buffer）

在单缓冲情况下，每当用户进程发出一I/O请求时，OS便在主存中为之分配一缓冲区。
在字符设备输入时，缓冲区用于暂存用户输入的一行数据，在输入期间，用户进程被挂起以等待数据输入完毕；在输出时，用户进程将一行数据输入到缓冲区后，继续执行处理。当用户进程已有第二行数据输出时，如果第一行数据尚未被提取完毕，则此时用户进程应阻塞。

(2)双缓冲（Double Buffer）

为了加快输入和输出速度，提高设备利用率，人们又引入了双缓冲区机制，也称为缓冲对换（Buffer Swapping）。在设备输入时，先将数据送入第一缓冲区，装满后便转向第二缓冲区。此时OS可以从第一缓冲区中移出数据，并送入用户进程。

(3)循环缓冲区

循环缓冲有多个大小相同的缓冲区，缓冲区有三种类型：
$ 用于装输入数据的空缓冲区R
$ 已装满数据的缓冲区G
$ 计算进程正在使用的现行工作缓冲区C

(4)缓冲池

对于既可输入又可输出的公用缓冲池，至少应含三种类型缓冲区：

1、空缓冲区； 2、装满输入数据的缓冲区； 3、装满输出数据的缓冲区；

四、设备的分配

1、设备分配原则：

& 静态分配
& 动态分配

2、设备分配策略

& 先请求先分配
& 优先级高者先分配

五、磁盘管理

1、磁盘的访问时间

寻道时间Ts：把磁臂从当前位置移到指定磁道上所经历的时间。
旋转延迟时间Tr：指定扇区移动到磁头下面所经历的时间。
传输时间Tt：数据从磁盘读出或向磁盘写入数据所经历的时间。

在访问时间中，寻道时间和旋转延迟时间，通常是占据了访问时间的大头。适当地集中数据（不要太零散）传输，将有利于提高传输效率。

例1：某磁盘磁头从一个磁道移至另一个磁道需要10ms，文件在磁盘上非连续存放，逻辑上相邻数据块的平均移动距离为10个磁道，每块的旋转延迟时间及传输时间分别为100ms和2ms，则读取一个 100块的文件需要( D )ms时间。

A．10200 B．11000 C．11200 D．20200

2、磁盘调度算法

 先来先服务 
 最短寻道时间优先 
 扫描（SCAN）算法（电梯调度算法） 
 循环扫描CSCAN

1）先来先服务（FCFS）

根据进程请求访问磁盘的先后次序进行调度。

 优点：公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。 
 缺点：未对寻道进行优化，致使平均寻道时间可能较长。仅适用于请求磁盘I/O的进程数目较少的场合。

2）最短寻道时间优先SSTF

优先满足访问磁道与当前磁头所在磁道距离最近的进程，以使每次的寻道时间最短。

问题：可能导致某些进程发生“饥饿”。因为只要不断有所要访问的磁道与磁头当前所在磁道的距离较近的新进程到达，就会出现“老进程饥饿”现象。这种调度算法不能保证平均寻道时间最短。

3）扫描（SCAN）算法（电梯调度算法）

SCAN算法中磁头移动的规律似电梯的运行，又称为电梯调度算法。算法既能获得较好的寻道性能，又能防止进程饥饿，被广泛用于大、中、小型机和网络中的磁盘调度。

问题：当磁头刚从里向外移动过某一磁道时，恰有一进程请求访问此磁道，这时该进程必须等待，待磁头从里向外，然后再从外向里扫描完所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被严重地推迟。

4）循环扫描CSCAN算法

为了减少请求进程的延迟，CSCAN算法规定磁头单向移动。若规定只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。

五、虚设备与SPOOLing技术

为缓和CPU的高速性与I/O设备低速性间的矛盾而引入了脱机输入、脱机输出技术。该技术是利用专门的外围控制机，将低速设备上的数据传送到高速磁盘上；或者相反。

这样就可以在主机的直接控制下实现脱机输入输出。此时外围操作与CPU对数据的处理同时进行，我们把这种在联机情况下实现的同时外围操作称为SPOOLing（Simultaneaus Periphernal Operating On—Line），或称为假脱机操作。

SPOOLing系统的有三大部分组成：

 输入井和输出井。是磁盘上开辟的两个大存储空间。
 输入缓冲区和输出缓冲区。在内存中开辟两个缓冲区，输入缓冲区暂存由输入设备送来的数据，后送输入井；输出缓冲区暂存从输出井送来的数据，后送输出设备。 
 输入进程和输出进程。利用两个进程模拟脱机I/O时的外围处理机。

进程SPi模拟脱机输入时的外围控制机，将数据从输入机，通过输入缓冲区再送到输入井。CPU直接从输入井读数据入内存。进程SPo模拟脱机输出时的外围控制机，把输出的数据从内存送到输出井，再待输出设备空闲时，将输出井中的数据，经过输出缓冲区送到输出设备上。

SPOOLing系统的特点

 提高了I/O的速度。利用输入输出井模拟成脱机输入输出，缓和了CPU和I/O设备速度不匹配的矛盾。
 将独占设备改造为共享设备。
 实现了虚拟设备功能。多个进程同时使用一***占设备，虚拟成了多台设备。

文件管理

一、文件和文件系统

文件是指具有文件名的若干相关元素的集合。

 现代OS中通过文件系统来组织和管理计算机中存储的数据； 
 文件系统包括两方面 
 负责管理文件的系统软件 
 被管理的对象--文件

文件的结构

文件存在以下两种形式的结构：

 文件的逻辑结构。从用户观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织。
 文件的物理结构。又称为文件的存储结构，是指文件在外存上的存储组织形式。与存储介质的存储性能和采用的外存分配方式有关。

1）、文件的逻辑结构

可以分为两大类：

 有结构文件，是指由一个以上的记录构成的文件，又把它称为记录式文件；根据记录的长度可分为定长记录文件；不定长记录文件。
 无结构文件，这是指由字符流构成的文件，故又称为是流式文件。

有结构文件

根据记录的组织方式分为下列文件：

 顺序文件。由一系列记录按某种顺序排列所形成的文件。通常是定长记录。 
 索引文件。当记录可变长时，通常为之建立一张索引表，并为每个记录设置一个表项以加快对记录检索的速度。 
 索引顺序文件。上述两种方式的结合。为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。 
 直接文件

无结构文件

 如果说大量的数据结构和数据库，是采用有结构的文件形式 的话，则大量的源程序、可执行文件、库函数等，所采用的 就是无结构的文件形式，即流式文件。其长度以字节为单位 。对流式文件的访问，则是采用读写指针来指出下一个要访 问的字符。 
 UNIX 系统中，所有的文件都被看做是流式文件。

二、文件的物理结构

由于磁盘具有可直接访问的特性，故当利用磁盘来存放文件时，具有很大的灵活性。

常用的外存分配方法有：

 连续分配  链接分配  索引分配

在一个系统通常只采用一种方法。

1、连续分配

连续分配要求为每一个文件分配一组相邻的盘块。在采用该方式时，可把逻辑文件中的记录顺序的存储到邻接的各物理块中，这样所形成的文件结构成为顺序文件结构，此时的物理文件称为顺序文件。这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。
随着文件的建立与删除不断进行，将产生很多外存的碎片，利用紧凑方法也可消除碎片。

2、链接分配

采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的文件称为链接文件。

3、索引分配

链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了另外两个问题：

 不能支持高效的直接存取。要对一个文件进行直接存取，需首先在FAT中顺序的查找许多盘块号。
 FAT需占用较大的内存空间。当磁盘容量较大时，FAT可能要占用数MB以上的内存空间。这是令人难以忍受的。

索引分配方式示意图

 单级索引方式  多级索引方式  混合索引方式

索引分配方式的问题可能要花费较多的外存空间。每当建立一个文件时，便须为之分配一个索引块，将分配给该文件的所有盘块号记录于其中。

例：某文件系统采用多级索引结构，若磁盘块的大小为 512 字节，每个块号需占 3 字节，那么根索引采用一级索引时的文件最大长度为( A )K字节；采用二级索引时的文件最大长度为 ( C )K 字节。
A.85 B.170 C.512 D. 1024
A.512 B.1024 C.14450 D.28900

例：某文件管理系统在磁盘上建立了位示图（bitmap），记录磁盘的使用情况。若系统的字长为32位，磁盘上的物理块依次编号为：0、1、2、…，那么4096号物理块的使用情况在位示图中的第（ A ）个字中描述；若磁盘的容量为200GB，物理块的大小为1MB，那么位示图的大小为（ D ）个字。

A．129 B．257 C．513 D．1025

A．600 B．1200 C．3200 D．6400

作业管理

一、作业状态

一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，要经历提交、后备、执行和完成4个状态。

二、处理机调度

高级调度（High Scheduling）

也称为作业调度，是指在后备队列中选择一个或一给作业，为它们建立进程，分配必要的资源，使它们能够运行。

 在批处理系统中，因作业进入系统后先驻留在外存，故需要 有作业调度。
 在分时系统中为做到及时响应，命令或数据被直接送入内存 ，故不需作业调度。 
 在实时系统中，不需作业调度。

中级调度（Intermediate-Level Scheduling）

也称为进程调度或短程调度，用来决定就绪队列中的哪个进程应获得处理机。

为最基本的一种调度，三种类型OS中都必须有进程调度。

低级调度（Low Level Scheduling）

是为了提高内存利用率和系统吞吐量。
应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调到外存去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。

三、调度算法

(1)先来先服务
(2)短作业（进程）优先调度算法
(3)高优先权优先调度算法
(4)高响应比优先调度算法

四、用户接口

 操作系统接口 
 命令接口 
 程序接口