四、处理机调度

1、操作系统的多级调度

分为四级

1. 作业调度
2. 交换调度
3. 进程调度
4. 线程调度

作业调度

高级调度（宏观调度）：又称作业调度。其主要功能是根据一定的算法，从输人的一批作业中选出若干个作业，分配必要的资源，如内存、外设等，为它建立相应的用户作业进程和为其服务的系统进程（如输人、输出进程），最后把它们的程序和数据调人内存，等待进程调度程序对其执行调度，并在作业完成后作善后处理工作。

交换调度

又称中级调度。为了使内存中同时存放的进程数目不至于太多，有时就需要把某些进程从内存中移到外存上，以减少多道程序的数目，为此设立了中级调度。

特别在采用虚拟存储技术的系统或分时系统中，往往增加中级调度这一级。

所以中级调度的功能是在内存使用情况紧张时，将一些暂时不能运行的讲程从内存对换到外存上等待。当以后内存有足够的空闲空间时，再将合适的进程重新换人内存，等待进程调度。

引人中级调度的主要目的是为了提高内存的利用率和系统吞吐量。它实际上就是存储器管理中的对换功能

进程调度

又称中级调度。其主要功能是根据一定的算法将CPU分派给就绪队列中的一个进程。

执行低级调度功能的程序称做进程调度程序，由它实现CPU在进程间的切换。进程调度的运行频率很高，在分时系统中往往几十毫秒就要运行一次。进程调度是操作系统中最基本的一种调度。

在一般类型的操作系统中都必须有进程调度，而且它的策略的优劣直接影响整个系统的计能。

2、作业调度和进程调度常用算法的调度原则

先来先服务（FCFS）

将用户作业和就绪进程按照提交顺序变为就绪状态的先后排队进行调度

这样对段时间作业不太公平

最短作业优先法（SJF）

就是在作业调度时，选择就绪队列中最短的作业进行调度

如果短时间作业过多，会多长时间作业不公平

最高响应比优先法（HRN）

相应比：R=(W+T)/T=1+W/T

其中R为响应比，W为等待时间，T为执行时间

最高响应法是按照这个公式对就绪队列中进行计算，选出响应比最高的作业进行调度

这个算法在每次调度前都需要进行相应比计算，所有系统开销比较大

五、存储管理

1、虚拟储存器

是存储管理的核心概念，它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换

2、分区管理分类及其基本原理、内存分配和回收方法

分为固定分区和动态分区

固定分区:就是提前把内存划为大小固定的分区，分区原则由系统操作或者操作员来决定

动态分区:通过程序的大小来进行划分分区存储程序

内存分配

1、最适应算法（最快得到风区）

2、最佳适应算法（最少浪费空间）

3、最坏适应算法（先进行区间探索，然后从大到小进行排序，程序从第一个开始进入）

回收时，他会把前后相邻空闲的分区进行整合处理

缺点：会产生许多的内存碎

3、地址和重定位

地址

逻辑地址：（相对地址，虚地址）

物理地址：（绝对地址，实地址）

地址重定位

静态重定位

是在虚拟空间程序执行之前由装配程序完成地址映射工作

通俗一点就是在作业装入时，一次性把作业指令地址转换为绝对地址

缺点：必须占用连续的内存空间，很难做到程序和数据的共享

动态重定位

在程序执行过程中，在CPU访问内存钱，需要将程序和数据的地址转换为内存地址

需要一个和多个基地址寄存器(BR)和虚拟空间(VR)

关系：指令或数据物理地址(MA)=(BR)+(VR)

关系图：

优点：内存空间可以移动；各个用户进程可以共享内存中同一程序的副本。

缺点：增加了机器成本，而且实现存储管理的软件算法比较复杂。

4、页式存储管理中页表及其作用

程序访问的是虚拟地址，但实际访问内存却需要使用物理地址，页表的作用就是通过线性地址来找到实际的物理地址

5、页式存储管理基本原理，页式动态地址变换

原理

1. 分页存储器将进程的虚拟空间和内存空间划分成多个大小相等的页架
2. 受页架尺寸限制，程序的逻辑地址也自然分成页
3. 不同的页可以放在不同页架中，不需要连续
4. 页表用于维系进程的主存完整性

页式动态地址变换

页内地址=逻辑地址-（页号*快长）

页内地址=页内地址+（块号*快长）

6、请求页式存储管理页面置换算法（FIFO、LRU）、缺页中断、抖动

FIFO、LRU

FIFO是先进先出。LRU是最近最久未使用

缺页中断

在内存中没有该页，需要去外存中掉用

抖动

在更换页面时，如果更换的页面是一个很快就会被再次访问的页面，则在此缺页中断后很快又会发生新的缺页中断。整个系统的效率急剧下降，这种现象称为抖动(Trashing)。

内存抖动的解决策略主要有：

1. 如果是因为页面替换策略失误，可以修改替换算法来解决这个问题；
2. 如果是因为运行的程序太多，造成程序无法同时将所有频繁访问的页面调入内存，则要降低多道程序的数量；
3. 否则，采取的办法有两个：一是终止该进程；二是增加物理内存容量。

7、段式存储管理和页式存储管理的区别

1、页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零
头，提高内存的利用率;或者说，分页仅仅是由于系统管理的需要，而不是用户
的需要。

段是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好的满足用户的需要。

2、页的大小固定且由系统确定,把逻辑地址划分为页号和页内地址两部分，
是由机器硬件实现的，因而一个系统只能有一种大小的页面。

段的长度却不固定，决定于用户所编写的程序，通常由编辑程序在对源程序
进行编辑时，根据信息的性质来划分。

3、分页的作业地址空间是一维的，即单一的线性空间，程序员只须利用一
个记忆符，即可表示一地址。

分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，
又需给出段内地址。

八、文件系统

1、什么是文件，什么是文件系统、文件的分类

文件：文件是具有符号名的、在逻辑上具有完整意义的一组相关信息项的有序序列。

文件系统：文件系统就是操作系统中实现文件统一管理的一组软件、被管理的文件以及为实施文件管理所需的一些数据结构的总称。

文件分类

系统文件;库文件;用户文件;

2、文件的逻辑结构和存取方法

逻辑结构

分为字符流无结构文件和记录式有结构文件

字符流无结构文件：是指对文件内信息不再划分单位，它是依次的一串字符流构成的文件

记录式有结构文件：是用户把文件内的信息按逻辑上独立的含义划分信息单位，每个单位称为一个逻辑记录（简称记录）。

记录式

连续结构：把记录生成先后顺序连续排列的逻辑结构，有利于记录追加和变更

多重结构：把记录按关键字和记录名排成行列式结构，对搜索有利

转置结构：最适用于给关键字后的记录搜索

顺序结构：按照某种系统要求优先顺序来搜索或者追加、删除记录，就用顺序结构

存取方式

1. 顺序存取：顺序存取是按照文件的逻辑地址顺序存取。
2. 直接存取（随机存取法）：很多应用场合要求以任意次序直接读写某个记录。
3. 索引存取：第三种类型的存取是基于索引文件的索引存取方法

3、文件的物理结构

连续文件

优点：

1. 支持顺序存取和随机存取；
2. 速度快；
3. 所需的磁盘寻道次数和寻道时间最少。

缺点：

1. 需要为每个文件预留若干物理块以满足文件增长的部分需要。
2. 不利于文件插入和删除。

串行文件

优点：

1. 提高了磁盘空间利用率，不需要为每个文件预留物理块。
2. 有利于文件插入和删除。
3. 有利于文件动态扩充。

缺点：

1. 存取速度慢，不适于随机存取。
2. 当物理块间的连接指针出错时，数据丢失。
3. 更多的寻道次数和寻道时间。
4. 链接指针占用一定的空间，降低了空间利用率。

索引文件

优点：

1. 不需要为每个文件预留物理块。
2. 既能顺序存取，又能随机存取。
3. 满足了文件动态增长、插入删除的要求。

缺点：

1. 较多的寻道次数和寻道时间。
2. 索引表本身带来了系统开销

4、FCB、文件目录和目录文件、多级文件目录优点

FCB : 为了能对一个文件进行正确的存取，操作系统必须为文件设置用于描述和控制文件的数据结构，称之为“文件控制块（FCB）”。

文件目录：把所有的FCB组织在一起，就构成了文件目录，即文件控制块的有序集合；

目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保持在外存，这个文件就叫目录文件。

多级目录的优点：

1. 目录层次清楚
2. 解决了文件重名问题
3. 查找搜索速度快

5、文件存储空间管理的方法

1. 空白文件目录：这种方法将盘空间的一个未分配区域称为一个空白文件，系统为所有的空白文件建立一个目录，每个空白文件在这个目录中建立一个表目。
2. 空白块链：这种方法将盘上的所有空白块用链接指针或索引结构组织成一个空白文件。
3. 位示图：它将文件存储器的存储空间建立一张位示图，用以反映整个盘空间的分配情况。