OS_考试复习 | LiamY Blog

type

status

slug

date

summary

第四章

4.1 存储器的层次结构

CPU与外设交换数据必须依托于主存。

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

用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址。

不能用逻辑地址在内存中读取信息

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

内存中存储单元的地址，可直接寻址

名空间

一个用高级语言编制的源程序，我们说它存在于由程序员建立的符号名字空间（简称名空间）。

地址空间

程序用来访问信息所用地址单元的集合，是逻辑（相对）地址的集合，由编译程序生成。

存储空间：主存中物理单元的集合。这些单元的编号称物理地址或绝对地址。存储空间的大小是由主存的实际容量决定的。

分区分配算法

1.最佳适应算法(Best fit: BF) ：就是为一作业选择分区时总是寻找其大小最接近作业所要求的存储区域。即：把作业放入这样的分区后剩下的零头最小。

为了加快查找速度，应将存储空间中所有的空白区按其大小递增的顺序链接起来，组成一空白区链(Free List)。

2.最坏适应算法(Worst fit: WF)：与最佳适应算法相反，它在为作业选择存储区域时，总是寻找最大的空白区。在划分后剩下的空白区也是最大的，因而对以后的分配很可能仍然是有用的，这是该算法的一个优点。但是，由于最大的空白块总是首先被分配而进行划分，当有大的作业时，其存储空间的申请往往得不到满足，这是该算法的一个缺点。

3.首次适应算法(First Fit: FF) ：由上面讨论可见，BF和WF各有其利弊。首次适应算法是对它们进行折衷考虑后设计出来的。

Ø每个空白区按其在存储空间中地址递增的顺序链在一起，即每个后继空白区的起始地址总是比前者的大。在为作业分配存储区域时，从这个空白区链的始端开始查找，选择第一个足以满足请求的空白块，而不管它究竟有多大。主要缺点：这种算法常常利用一个大的空白区适应小作业的请求，从而留下一些较小的无法用的空白区，存储空间利用率不高；而且，由于所有的请求都是从空白区链的始端开始查找，因而这些小而无用的空白区集中在这个链的前端，相应地，一些较大空白区在链的尾端才能发现，这种情况将使找到合适空白区的速度降低。

4.下次适应算法(Next fit: NF) ：为了克服上述缺点，又设计了一种称为“下次”适应的算法，它实际上是首次适应算法的一种变形，故也被称为带旋转指针的首次适应算法(Next Fit with Roving Pointer)。

为此，我们把存储空间中空白区构成一个循环链。每次为存储请求查找合适的分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就将它划分后分配出去。显然，采用这一策略后，存储空间的利用更加均衡，而不至于使小的空白区集中于存储器的一端。但是，在存储器的另一端也不可能保留大的空白块，因此，当需要获得相当大的空白区时，能满足的可能性减少了。

5. 快速适应算法（Quik fit:QF)

Ø将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。

Ø这样，系统中存在多个空闲分区链表；

Ø同时，在内存中设立一张管理分区类型，并记录了该类型空闲分区链表表头的索引表，该表的每一个表项记录了对应类型空闲分区链表表头的指针。

Ø分配过程：根据进程的长度，寻找到能容纳它的最小空闲分区链表，并取下第一块进行分配即可

Ø优点：

1.查找效率高。

2.该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。

Ø缺点：

1.在分区归还主存时算法复杂，系统开销较大。

2.该算法在分配空闲分区时是以进程为单位，一个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少地存在一定的浪费。空闲分区划分越细，浪费则越严重，

分页存储管理方式

数据结构

地址结构

（1）1M、1KB、16位、64KB

（2）0x0420=0000 0100 0010 0000⇒偏移量00 0010 0000，页号：1

7*1024+32= 7168 +32 =

访问内存的有效时间

分段机制

信息共享

段页式存储管理方式

对换

外存被分为两部分：文件区和对换区

文件区：即一个文件可根据当前外存的使用情况被分成多块，分别存储到不邻接的多个存储区中，用指针相连。

对换区：即把一个换成的进程存放到一个连续的存储空间中

进程的换入与换出

为避免某进程被频繁的换入换出，还应该考虑进程在内存中的驻留时间，优先选择驻留时间长的进程。

虚拟存储器

一次性和驻留性严重降低内存利用率，减少系统吞吐量。

局部性原理：

理论依据：程序执行的局部性原理

如何将程序划分成部分：分页或分段

逻辑容量由内存和外存之和决定

虚拟性是以多次性和对换性为基础的；而多次性和对换性又必须建立在离散分配的基础上

抖动问题

Copy A to B是一条指令，可能跨页

A作为一条数据，可能跨页

B作为一条数据，可能跨页

内存分配策略和分配算法

固定分配算法

页面调入策略

对于第一种：为此，在进程运行前，便需将与该进程有关的文件从文件区拷贝到对换区

页面置换算法

最佳置换算法（不切实际、无法实现）

FIFO

LRU(Least Recently Used)

LRU算法的硬件支持

最后一句话傻逼ppt写的不对：

须有寄存器和栈两类硬件之一的支持。

最少使用置换算法LFU

clock置换算法

注意调入进来的时候该页面的访问位会被标志位1，说明被访问

改进型clock算法

就是从1类找到4类，中间找2类的过程中会修改A位用于后续可能会找第三类甚至是第四类。

缺页率对有效访问时间(EAT)的影响

最后公式的化简是出书的人是个傻逼，真没水平，不会化简别化简。

抖动

缺段中断

第五章输入输出系统

设备控制器

若控制器可以连接多个设备时，则应含有多个设备地址，并使每一个设备地址对应一个设备

IO通道

虚拟设备是将独占设备转为共享

中断处理程序

设备驱动程序

使用轮询的可编程IO方式

中断驱动方式

直接存储器访问DMA

命令/状态寄存器CR：用于接收从CPU发来的I/O命令或有关控制信息，或设备的状态。

数据计数器DC：存放本次CPU要读或写的字节数

内存地址寄存器MAR：在输入时，它存放把数据从设备传送到内存的起始目标地址；在输出时，它存放由内存到设备的内存源地址

数据寄存器DR：用于暂存从设备到内存，或从内存到设备的数据。

IO通道控制方式

与设备无关的IO软件

设备分配灵活

易于实现IO重定向

磁盘系统以及磁盘调度

磁盘访问时间

rN=每秒钟传输的字节数

磁盘调度

先来先服务

最短寻到时间优先SSTF

扫描算法(SCAN)/电梯调度算法

循环扫描(CSCAN)算法

总结

第六章：文件及文件系统

概述

文件、记录、数据项

文件的属性

文件类型

文件长度

文件的物理位置

文件的建立时间

文件类型和文件系统模型

文件类型：

文件系统模型

文件的物理组织—存储空间的管理

连续分配

链接分配

隐式链接分配

显示链接

还可以混合一级二级乃至于直接索引：

文件存储空间的管理

空闲分区表

空闲链表法

位示图

成组链接法

文件目录

文件控制块的内容

单级目录结构

两级目录结构

多级目录结构

目录查询技术

稍微解释：

首先，系统应该先读入第一个文件名usr，用它与根目录（或当前目录文件）中各目录项中的文件名顺序地进行比较，从中找出匹配者，并得到匹配项的索引结点号为6，再从6号索引结点中得知usr目录文件放在132号盘块中，将该盘块内容读入内存，接下来接着和上面的操作一致，不再赘述。

文件共享和访问控制

文件共享的有效控制涉及两个方面：

同时存取（Simultaneous Access）

存取权限（Access Rights）

控制同时存取

控制存取权限

文件共享的实现

链接目录项实现文件共享

利用索引节点实现文件共享

只能删除硬链接，但是不能删除里面的实际内容，当所有硬链接都删除后，才可以删除其内容和索引节点。

利用符号链实现文件共享

注意这里OS的作用，它需要特殊处理：当B要访问被链接的文件F且正要读LINK类新文件时，将被OS截获，OS根据新文件中的路径名去读该文件，于是就实现了用户B对文件F的共享。

多拷贝这里解释：当有一个程序员要将一个目录中的所有文件都转储到磁带上去时，就可能对一个共享文件产生多个拷贝。

第8章SHELL

UNIX系统中的Shell具有两大功能:

. 命令解释器: 解释用户发出的各种操作系统命令

. 程序设计语言: 功能强大, 可包容引用所有的操作系统命令和可执行程序。

8.2.1 重定向

command > filename 进程输出覆盖文件filename

或 command >> filename 进程输出追加到文件filename后面, 不覆盖filename

例如:

$ cat myfile

把文件myfile的内容输出到标准输出文件----荧光屏上

$ cat myfile > newfile

把文件myfile的内容输出到文件newfile中(标准输出已被重新定向到newfile). 其结果相当于拷贝文件.

$ cat abc >> xyz

把abc添加到xyz已有内容后面, 而不是覆盖xyz

cat指令

标准错误输出重定向

管道

后台执行

一些指令

echo指令

export

Shell的内部命令

进程监控

获取进程状态信息：ps命令

sleep命令

Kill命令

shell编程

常用的功能性语句（命令）

read

如果执行read语句时标准输入无数据，则程序在此停留等候，知道数据的到来或被终止运行。

echo -n 在命令行中的作用是输出文本但不在末尾添加换行符。这意味着，如果你在终端中使用 echo -n 输出文本，终端的光标将停留在同一行的末尾，而不是新的一行。这在需要将多个命令的输出拼接在同一行时非常有用。

tup命令

结构性语句

IF

$ prog2 $1没有取到任何文件名

$ prog2 file1 file2 $1只取第一个参数，file1

如果没有exit语句，prog3就只有一个出口（最后一个fi语句）；如果有exit语句，prog3就有两个出口。但执行结果没有区别。

prog2的主要缺点是什么? 当给出的文件或目录名是不存在时，没有未知种类的判断

Test

case

for

Shell函数

功能：给一个文本文件中的每一行前面加上行号。注意：while循环体的标准输入，被重定向为从管道中读。 while循环体的标准输出，被重定向到了 tmp$$文件中，这里的$$就是当前进程的进程号，因为进程号的唯一性，所以多个用户同时运行该程序时，不会相互覆盖！ $$ 当前进程的ID号 $# 命令行上的参数个数

这是一个条件语句，用于检查是否传递了正确的参数。$# 是传递给脚本的参数个数，如果参数个数不等于 1，则打印一条错误消息，并退出脚本。$0 是当前脚本的名称，>&2 是将错误消息输出到标准错误输出。这是一个管道语句，将文件 $1 的内容传递给 while 循环处理。每次循环读取一行内容，使用 echo 命令输出当前行号 count 和行内容 line。然后使用 expr 命令将 count 加 1。整个循环的输出结果被重定向到一个临时文件 tmp$$。这是一个重命名语句，将临时文件 tmp$$ 重命名为原始文件 $1，覆盖原始文件。综合来看，这个脚本的作用是为给定的文件添加行号，并将修改后的内容覆盖到原始文件中。

功能：程序从文件中每读入一行，就询问用户是否正确，如用户回答正确（以y或Y开头的字符串）就直接输出；否则就提示用户重新输入这行的内容，并输出。说明：while循环体的标准输入被重定向为file.old语句，因放在done语句后面的，容易被忽略。 while循环体内的read语句的标准输入已被重定向为当前键盘（/dev/tty)，而不是file.old while循环体的标准输出没有重定向，所以其中的提示类信息是显示在终端上的，但输出的文件内容，却被重定向到file.new中了。

流编辑器sed

一. 什么是流编辑器？

流编辑器是一种流水线型的、非交互式的文本编辑器。它使用户可以在命令行上（而不是编辑器中）对文件进行无破坏性编辑。

注意:

sed命令的结果是送到标准输出上，即荧光屏上，如果要将结果保存在文件中，应该使用重定向功能！

例如：

sed ‘s/student/teacher/g’ oldfile > newfile

awk

什么是awk

awk 是一种程序设计语言, 主要用来处理文本类数据并产生报表。

它执行时对输入数据(文件、标准输入或命令的输出）逐行进行扫描，匹配指定的模式，并执行指定的操作。

本例中awk命令后的第二个命令行参数（文件名）缺乏，所以awk要从标准输入（键盘）上读取数据。键盘输入的第一行中没有包含aaa字符串，所以awk没有输出；键盘输入的第二行内容中包含aaa字符串，所以awk命令有输出（第三行）；第四行是键盘输入的第三行，同样因为其中没有包含aaa字符串而没有输出，最后输入的^D表示键盘输入结束，因此awk执行结束。

注意这里：awk运行时，对输入文件中的每一行执行命令文件中的所有操作后，再对下一行数据进行同样的处理过程，以此类推，直到输入文件中的最后一行。