软考系统架构设计师(三)：操作系统

操作系统基础知识

一、操作系统定义

操作系统是直接控制和管理计算机硬件、软件资源，合理地对各类作业进行调度，以方便用户使用的程序集合。
操作系统定义

二、操作系统在计算机中的地位

操作系统在计算机中的地位

三、OS的作用

作为用户和计算机间的接口作为计算机系统资源的管理者实现了对计算机资源的抽象
OS的作用

四、操作系统分类

批处理操作系统
分时操作系统
实时操作系统
网络操作系统
分布式操作系统
微内核操作系统

五、操作系统的功能

处理机管理功能
存储器管理功能
设备管理功能
文件管理功能
用户接口

OS定义:OS是直接控制和管理计算机硬件、软件资源，合理地对各类作业进行调度，以方便用户使用的程序集合

处理器管理（进程）

一、进程的定义
进程︰程序关于某个数据集合的一次执行过程。

进程的特征(与程序比较)
1. 结构特征
  进程控制块(PCB)＋程序＋数据=进程实体
2. 动态性–最基本特征
  进程∶进程实体的一次执行过程，有生命周期。程序︰程序是一组有序指令的集合，是静态的概念。
进程的三种基本状态
1. 就绪状态(Ready)
  进程已获得除CPU之外的所有必需的资源，一旦得到CPU控制权，立即可以运行。
2. 运行状态(Running)
  进程已获得运行所必需的资源，它正在处理机上执行。
3. 阻塞状态(Blocked)
  正在执行的进程由于发生某事件而暂时无法执行时，便放弃处理机而处于暂停状态，称该进程处于阻塞状态或等待状态。

进程的三种基本状态

进程的五种状态
引入挂起状态后，增加了挂起状态(静止状态)到非挂起状态(活动状态)的转换，或者相反。

二、进程互斥与同步

进程间两种形式的制约关系
1. 间接相互制约关系— 源于资源共享
2. 直接相互制约关系— 源于进程合作
临界资源
临界资源(Critical Resource):把一段时间内只允许一个进程访问的资源称为临界资源或独占资源
临界区( Critical Section ) :每个进程中访问临界资源的那段代码称为临界区

三、信号量机制
信号量是Os提供的管理公有资源的有效手段。
信号量是一个整数，当信号量大于等于零时，代表可供并发进程使用的资源数量，当信号量小于零时，表示处于阻塞态进程的个数。

Wait 操作︰
申请资源，减量操作，S.value:=S.value-1
当S.value<0时，表示资源分配完，进行自我阻塞。Signal操作:
释放资源，增量操作，S.value:=S.value+1当S.value≤=0，唤醒S.L链表中的等待进程。

四、信号量的应用

利用信号量实现进程互斥（模式)
利用信号量实现前驱关系（模式)
利用记录型信号量实现同步（模式)
利用信号量实现进程互斥（模式)
为使多个进程互斥的访问某临界资源，须为该资源设置一互斥信号量mutex，并设其初始值为1，然后将各进程访问资源的临界区CS置于wait(mutex)和signal(mutex)之间即可。
利用信号量实现前驱关系（模式)
设有两个并发执行的进程PI和P2，P1中有语句S1，P2中有语句S2，希望在S1执行后再执行S2。
使进程P1和P2共享一个公用信号量S，并赋予其初值为0。
利用记录型信号量实现同步（模式)
P1，p2两进程因合作完成一项任务而共用一个变量x。进程p2将处理结果送入x﹔进程P1将x的结果打印。

文件管理

一、文件和文件系统
文件是指具有文件名的若干相关元素的集合。
现代os中通过文件系统来组织和管理计算机中存储的数据;文件系统包括两方面
负责管理文件的系统软件
被管理的对象–文件

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

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

一、文件的逻辑结构可以分为两大类∶

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

有结构文件

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

顺序文件。由一系列记录按某种顺序排列所形成的文件。通常是定长记录。
索引文件。当记录可变长时，通常为之建立一张索引表，并为每个记录设置一个表项以加快对记录检索的速度。
索引顺序文件。上述两种方式的结合。为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。
直接文件
无结构文件如果说大量的数据结构和数据库，是采用有结构的文件形式的话，则大量的源程序、可执行文件、库函数等，所采用的就是无结构的文件形式，即流式文件。其长度以字节为单位。对流式文件的访问，则是采用读写指针来指出下一个要访问的字符。

UNIX系统中，所有的文件都被看做是流式文件。

二、文件的物理结构
由于磁盘具有可直接访问的特性，故当利用磁盘来存放文件时，具有很大的灵活性。
常用的外存分配方法有∶
1、连续分配
链接分配索引分配
在一个系统通常只采用一种方法。

2、链接分配
采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的文件称为链接文件。
3、索引分配
链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了另外两个问题:
不能支持高效的直接存取。要对一个文件进行直接存取，需首先在FAT中顺序的查找许多盘块号。
FAT需占用较大的内存空间。当磁盘容量较大时，FAT可能要占用数MB以上的内存空间。这是令人难以忍受的。

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

3、储存空间管理
空闲表法和空闲链表法
位示图法
成组链接法

储存管理

存储管理主要是指对内存的管理，负责内存分配和回收，内存的保护和扩充。
存储管理的目的是尽量提高内存的使用效率。

内存的分配方式有两种
连续的分配方式
离散的分配方式

一、连续分配方式
指为一个用户程序分配一个连续的内存空间。
(1)单一连续分配
(2)固定分区分配
(3)动态分区分配
为把一个新作业装入内存，需按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。
常用的分配算法︰
a.首次适应算法
b.循环首次适应算法
c.最佳适应算法
d.最坏适应算法

(4)可重定位分区分配
如果在系统中只有若干个小分区，即使它们的容量总和大于要装入的程序，但由于这些分区不相邻，也无法将程序装入内存。
解决方法∶将内存中的所有作业进行移动，使它们全部邻接，这样把原来分散的小分区拼接成大分区，这种方法称为“拼接”或“紧凑”。

二、对换与覆盖技术
1.覆盖技术
一个作业的若干程序段或数据段的某些部分共享内存空间
2.对换技术
把内存中暂时不能运行的进程或者暂时不用的程序和数据，调到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程和进程所需要的程序和数据调入内存。

对换的分类:
整体对换(或进程对换):以整个进程为单位页面对换或分段对换∶以页或段为单位
连续分配方式会形成“碎片”，虽然可以通过“紧凑”解决，但开销天。如果允许将一个进程直接分散地装入许多不相邻的分区中，则无需“紧凑”，由此产生离散分配方式。分类∶
分页存储管理方式:离散分配的基本单位是页
分段存储管理方式:离散分配的基本单位是段

三、基本分页存储管理方式
1、页面与页表
2、地址变换机构

1、页面
分页式存储管理的原理:
将一个进程的逻辑地址空间分成若干个大小相等的片称为页面或页，并为各页加以编号，从0开始。同时把内存空间分成与页面相同大小的若干个存储块，称为块或页框。
在为进程分配内存时，以块为单位将进程的若干个页分别装入到多个可以不相邻的物理块中。进程的最后一页经常装不满一块而形成“页内碎片”。

2、地址变换
若给定一个逻辑地址空间中的地址为A，页面大小为L，则
页号P= INT[A/L]
页内地址d = [A] MOD L
例如∶系统页面大小为1KB，设A=2170D，则
P=2, d=122

3、基本分页式存储管理的实现
进程的每一页离散地存储在内存的任一存储块中，为方便查找，系统为每一进程建立一张页面映像表，简称页表。
页表实现了从页号到物理块号的地址映射。

为了能将用户地址空间的逻辑地址变换为内存空间的物理地址，在系统中必须设置地址变换机构。
地址变换机构实现从逻辑地址到物理地址的转换，由于页内地址与物理地址是一—对应的，因此，地址变换机构的任务是借助于页表，将逻辑地址中的页号转换为内存中的物理块号。
基本分页式存储管理的实现

4、具有快表的地址变换机构
由于页表是存放在内存中的，CPU 在每存取一个数据时，需要两次访问内存︰
第一次:访问页表，找到指定页的物理块号，将块号与页内
偏移量拼接形成物理地址。
第二次∶从第一次所得地址中获得所需数据，或向此地址中写入数据。

存储器利用率提高，处理器处理速度降低。
解决方法︰在地址变换机构中，增设一个具有并行查寻能力的特殊高速缓冲寄存器，称为“联想存储器”或“快表”。

数值的表示:
二进制,十进制,八进制,十六进制,分别在其后加上B,D,Q,H。
(Binary,Decimal ,Q(Octal),Hexadecimal)

例1.设页面大小为2KB，将逻辑地址3BADH划分为页号和页内偏移量两部分。用16进制表示。

四、基本分段式存储管理的实现
1)段表
为使程序正常运行，须在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项。
段表结构∶段号;段在内存中的起始地址(基址);段长。段表可以存放在寄存器中，但更多的是存放在内存中。段表用于实现从逻辑段到物理内存区的映射。

2 )地址变换机构
在系统中设置段表寄存器，用于存放段表始址和段表长度，以实现从进程的逻辑地址到物理地址的变换。
当段表存放在内存中时，每访问一个数据，都需访问两次内存，降低了计算机的速率。
解决方法∶设置联想寄存器，用于保存最近常用的段表项。

3.分页和分段的主要区别
相似点∶
采用离散分配方式，通过地址映射机构实现地址变换不同点∶
页是信息的物理单位，分页是为了满足系统的需要;段是信息的逻辑单位，含有意义相对完整的信息，是为了满足用户的需要。页的大小固定且由系统确定，由系统把逻辑地址分为页号和页内地址，由机器硬件实现;段的长度不固定，取决于用户程序，编译程序对源程序编译时根据信息的性质划分。
分页的作业地址空间是一维的;分段的作业地址空间是二维的。

五、段页式存储管理
分段和分页存储管理方式各有优缺点。把两者结合成一种新的存储管理方式–段页式存储管理方式，具有两者的长处。
1．基本原理
先将用户程序分成若干段，再把每个段分成若干页，并为每个段赋予一个段名。
基本段页式存储管理︰把作业的所有段装入内存方可运行。请求段页式存储管理∶没必要把整个作业装入内存，可把作业的几段或几页装入内存即可运行。
段页式系统地址结构︰段号;段内页号;页内地址。

基本原理

六、页面置换算法
(1)最佳置换算法
最佳置换算法是一种理想化的算法，具有最好的性能，但难于实现。先进先出置换算法最直观，但可能性能最差，故应用极少。
1.最佳置换算法
其所选择的被淘汰页面，将是以后永不再用的，或许是在最长(未来)时间内不再被访问的页面。
优点∶保证获得最低的缺页率
缺点∶无法预知一个进程在内存的若干个页面，哪个在未来最长时间内不再被访问。
算法无法实现，但可评价其他算法。
(2)先进先出置换算法
算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针(替换指针)，使它总是指向最老的页面。
算法与进程的实际运行规律不相适应，因为进程中的某些页面经常被访问，但先进先出置换算法不能保证这些页面不被淘汰。

Belady 现象
如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。发生在FIFO（先进先出）置换算法。

(3)最近最久未使用(LRU)算法

算法根据页面调入内存后的使用情况进行决策。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当需淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

作业管理

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

二、处理机调度
1.高级调度（High Scheduling ）
也称为作业调度，是指在后备队列中选择-个或一给作业，为它们建立进程，分配必要的资源，使它们能够运行。
在批处理系统中，因作业进入系统后先驻留在外存，故需要有作业调度。
在分时系统中为做到及时响应，命令或数据被直接送入内存，故不需作业调度。
在实时系统中，不需作业调度。

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

3.低级调度（Low Level Scheduling ）
也称为进程调度或短程调度，用来决定就绪队列中的哪个进程应获得处理机
为最基本的一种调度，三种类型OS中都必须有进程调度。

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

设备管理

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

输入、输出设备
存储功能的设备
设备控制器

一、设备管理的概念
设备管理程序提供下述功能

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

二、I/O控制方式
(1)程序I/O方式
(2)中断控制I/O方式
(3)直接存储器访问(DMA)方式
(4)I/O通道控制方式
字节多路通道
选择通道
成组多路通道

三、磁盘管理

1、磁盘的访问时间

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

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

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

2、磁盘调度算法

先来先服务
先来先服务调度算法之例
9个进程先后提出读盘请求，访问的磁道号为∶55 ; 58; 39; 18;90 ;160 ; 150; 38; 184。目前磁头停留在100道。此时开始磁盘调度;其调度序列为︰
最短寻道时间优先
优先满足访问磁道与当前磁头所在磁道距离最近的进程，以使每次的寻道时间最短。
问题:可能导致某些进程发生“饥饿”。因为只要不断有所要访问的磁道与磁头当前所在磁道的距离较近的新进程到达，就会出现“老进程饥饿”现象。这种调度算法不能保证平均寻道时间最短。
最短寻道时间优先调度算法之例
9个进程先后提出读盘请求，访问的磁道号为:55 ; 58;39; 18; 90; 160; 150; 38; 184。目前磁头停留在100道。此时开始磁盘调度;其调度序列为∶
扫描(SCAN)算法（电梯调度算法)
SCAN算法中磁头移动的规律似电梯的运行，又称为电梯调度算法。算法既能获得较好的寻道性能，又能防止进程饥饿，被广泛用于大、中、小型机和网络中的磁盘调度。
问题:当磁头刚从里向外移动过某一磁道时，恰有一进程请求访问此磁道，这时该进程必须等待，待磁头从里向外，然后再从外向里扫描完所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被严重地推迟。
扫描(SCAN)算法之例
9个进程先后提出读盘请求，访问的磁道号为:55 ; 58; 39; 18;90;160;150; 38;184。目前磁头停留在100道。此时开始磁盘调度;其调度序列为∶
循环扫描CSCANv 算法
为了减少请求进程的延迟，CSCAN算法规定磁头单向移动。若规定只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。
循环扫描CSCAN算法之例
9个进程先后提出读盘请求，访问的磁道号为:55 ; 58;39; 18;90;160;150; 38;184。目前磁头停留在100道。此时开始磁盘调度﹔其调度序列为∶

四、虚设备与SPOOLing技术
为缓和CPU的高速性与I/O设备低速性间的矛盾而引入了脱机输入、脱机输出技术。该技术是利用专门的外围控制机，将低速设备上的数据传送到高速磁盘上;或者相反。
这样就可以在主机的直接控制下实现脱机输入输出。此时外围操作与CPU对数据的处理同时进行，我们把这种在联机情况下实现的同时外围操作称为SPOOLing ( Simultaneaus Periphernal OperatingOn-Line )，或称为假脱机操作。
SPOOLing系统的有三大部分组成: