软考之软件设计师——操作系统知识

操作系统

1、进程管理

1）进程的概念：进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的独立单位，由程序块（是程序执行时不可修改的部分）、进程控制块PCB（进程存在的唯一标识）和数据块（包括程序执行的数据，工作区，是进程可修改部分）三部分组成。线程：线程是进程中的一个实例，作为系统调度和分派的基本单位。是进程中的一段序列，能够完成进程中的一个功能。线程是轻量级的进程。
2）进程与程序的区别：程序是完成某个特定功能的一系列程序语句的集合，是静态的，不被破坏就永远存在。进程是动态的，由创建而产生，完成任务后因撤销而消亡。进程是系统进行资源分配和调度的独立单位，而程序不是。
3）程序顺序执行的主要特征：顺序性，封闭性和可再现性。
程序的并发执行，使其失去了程序的封闭性，可再现性；程序和机器的执行程序的活动不再一一对应；并发程序间存在相互制约。
4）进程的三态模型：运行，就绪（一个进程获得除处理机外的一切所需资源）、阻塞。

5）进程的五态模型加入挂起和**：

• 活动就绪：指进程在主存并且可以被调度
• 静止就绪：指就绪进程被兑换到辅存时的状态
• 活动阻塞：进程在主存中，一旦等待事件产生便进入活动就绪。
• 静止阻塞：指阻塞进程对换到辅存的存在。

6）进程的控制：进程控制是由操作系统内核中的原语实现的。原语是指由若干条机器指令组成，用于完成特定功能的程序段，特点是执行时不能被分割，原子操作要么都做，要么都不做。
7）进程间的同步：在系统中一些需要相互合作，协同工作的进程，它们之间的相互联系称为进程的同步。
进程间的互斥：系统中多个进程因争用临界资源而互斥执行。
8）临界区指进程对临界资源实施操作的那段程序。对互斥临界区管理的四条原则：有空即进、无空则等、有限等待（避免陷入“饥饿”状态）、让权等待（释放处理机，以免陷入“忙等”）
9）信号量机制：整型信号量、记录型信号量、信号量集机制（熟悉PV操作）

• PV操作是实现进程同步与互斥的常用方法。
• 整型信号量：信号量是一个整型变量。分为两类：公用信号量（实现进程间的互斥，初值为1或资源数目），私用信号量（实现进程的同步，初值为0或某个正整数）
• 典型的同步问题：单缓冲区生产者消费者的同步问题。
• 利用信号量mutex的初值为1来实现互斥。
• PV操作应用：
  传统流程形式。
  前驱图形式：进来的箭头代表P操作，出去的箭头代表V操作。
  
• PV属于低级通信方式：编程难度大，对用户不透明；效率低。
• 高级通信方式：共享存储模式、消息传递模式（程序员利用原语实现通信如send（A))、管道通信。

10）管程：采用资源集中管理方法，将系统中的资源用某种数据结构抽象表示。
11）进程调度：指更高优先级的进程到来如何分配CPU。调度方式分为可剥夺和不可剥夺两种。

• 三级调度：某些操作系统中，一个作业从提交到完成需要经历高、中、低三级调度。
• 高级调度：又称“作业调度”，它决定处于输入池中哪个后备作业可以调入主系统做好运行的准备，成为一个或一组就绪进程。在系统中一次作业只需经过一个高级调度。
• 中级调度：又称“对换调度”,它决定处于交换区中的哪个就绪进程可以调入内存，以便参与对CPU的竞争。
• 低级调度：又称“进程调度”，它决定处于内存中的哪个就绪进程可以占用CPU。低级调度是操作系统中最活跃、最主要的调度程序，对系统的影响很大。
• 调度算法：

1. 先来先服务（FCFS)。比较有利于长作业，而不利于短作业；有利于CPU繁忙的作业，而不利于I/O繁忙的作业。主要用于宏观调度。
2. 时间片轮转：用于微观调度，其设计目的是通过提高进程并发性和响应时间特性，从而提高资源利用率。有两种选择方法：固定时间片，可变时间片。
3. 优先级调度：分为静态优先级，动态优先级。
4. 多级反馈调度：设置多个就绪队列。该算法是时间片轮转和优先级调度算法的综合与发展。优点：照顾了短进程以提高系统吞吐率，缩短平均周转事件。照顾I/O型进程以获得较好的I/O设备利用率和缩短响应时间；不必估计进程的执行时间，动态调节优先级。

• 进程优先级确定：对于I/O型进程，让其进入最高优先级队列。对于计算型进程，每次都执行完时间片后进入更低级队队列，采用最大时间片执行。对于I/O次数不多，主要是CPU处理的进程，I/O完成后，返回优先I/O请求时离开的队列。
  为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级，时间片用完时，降低优先级。

12）死锁：两个以上的进程互相都要求对方已经占有的资源导致无法继续运行下去的现象。

• 死锁产生的原因：竞争资源以及进程推进顺序非法。产生死锁的4个必要条件：互斥条件、请求保持条件、不可剥夺条件、环路条件。
• 死锁的处理策略：有鸵鸟策略（不理睬策略）、预防策略、避免策略、检查与解除死锁。

1. 死锁预防（破坏死锁产生的4个必要条件来预防死锁，由于资源互斥是资源使用的固有特性是无法改变的）：预先静态分配法：破坏了“不可剥夺条件”，降低了资源利用率，及进程的并发程度。 资源有序分配法：破坏了“环路条件”，限制进程对资源请求。资源的排序占用系统开销。
2. 死锁避免：Dijkstra提出的银行家算法，与死锁预防相比，提高了资源利用率，但需要很大系统开销。银行家算法：当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程。进程可以分期请求资源，但请求的总数不能超过最大需求量。当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源。根据银行家算法判断相关进程序列是否会形成死锁，是则为不安全序列。（学会判断安全序列，对于资源分配数，分配资源时每个进程得到可以完成进程的资源数减一，此时是形成死锁的最差情况，在此情况下多1个资源即可解决死锁问题，即不可能形成死锁。）
3. 死锁检测：允许死锁产生，定期运行检测程序，发现死锁则设法加以解除。
4. 死锁解除：资源剥夺法、撤销进程法。

2、存储管理

1）地址重定位：指将逻辑地址转换成主存物理地址的过程。分为静态重定位和动态重定位。
2）分区存储管理：主存的用户区划分为若干个区域，每个区域分配一个作业使用，不可跨区。分区方法：

• 固定分区是一种静态分区方式，系统生成时先划分好区域，大小可不等。已分配分区中未用的空间称为内碎片。
• 可变分区：动态分区方式，作业转入时进行划分。需要两种管理表格，记录已分配和未分配的分区情况。一个分区一分为二，由于不连续，小到无法再进行分配的分区称为外碎片。解决碎片的方法：拼接。可变分区的请求和释放分区4种算法：最佳适应算法（容易产生外碎片）、最差适应算法（分配最大分区，不容易产生外碎片）、首次适应算法（易实现相邻的空白区合并）、循环首次适应算法。
• 可重定位分区：解决碎片问题的简单且行之有效的方法。移动已经分配好的分区，使之成为连续区域。不过有地址重定位问题。
• 分区保护方式：采用上界/下界寄存器保护，物理地址满足[上界寄存器，下届寄存器]。采用基址/限长寄存器保护，物理地址满足[基址寄存器，基址寄存器+限长寄存器）。

3）分页存储管理：利用率高，碎片小，分配与管理简单，不过增加了系统开销，可能产生抖动现象，不易实现共享。

• 纯分页存储管理：分页原理：将一个进程的地址空间划分为若干个大小相等的区域，称为页。相应地，将主存空间划分为与页大小相同的若干个物理块，称为块。为进程分配主存时，将进程的若干页转入多个不相邻的块中。
  地址结构（逻辑地址，例如32位地址）：页号（12-31位，允许地址空间最多1Mb个页）、页内地址（0-11位为页内地址，每页约4kb）
  物理地址=页帧号+页内地址
  页表的作用实现页号到物理块号的地址映射。
• 快表：由一组高速存储器组成，用来保存当前访问频率高的少数活动页的页号及相关信息。
• 两级页表机制：80283采用两级页表机制。需要建立外层页表（第一级是页目录表，第二级是页表）
  
  4）分段存储管理：多道程序共享内存，各段程序修改互不影响，易于实现段的共享，不过内存利用率低，内存碎片浪费大。
• 各段的长度是不等的，逻辑地址由段号（16-31位）和段内地址（0-15位）组成
• 段表：记录主存中的起始地址（基址），和段的长度。

5）段页式存储管理：先分段再分页。需要配置段表和页表，段表中保存页表起始地址和页表长度。而用段表寄存器保存段表起始地址，段表长度。空间浪费小，存储保护容易，能动态连接。不过复杂性和开销也随之增加，硬件及占用内容增多，执行速度大大下降。

6）虚拟存储管理虚拟存储器：具有请求调入和置换功能，能仅把作业的一部分装入主存便可以运行作业的存储器系统。

• 虚拟存储器的实现方式：三种
• 请求分页系统：在分页系统的基础上增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。
• 请求分段系统：在分段系统的基础上增加了请求掉段和分段置换功能所形成的段式虚拟存储系统。
• 请求段页系统：上面两种的结合。
• 在请求分页系统中，如果访问页面不在主存中就会产生缺页中断。缺页中断与一般中断的区别：缺页中断在指令执行期间产生和处理中断信号，一般中断则是在一条指令执行完，下一条指令开始前。发生缺页中断时，返回到被中断指令的开始重新执行该指令，而一般中断返回到下一条指令执行。一条指令在执行期间可能产生多次缺页中断。

7）页面淘汰时，主要依据原则：先淘汰最近未被访问的（访问位为0），其次淘汰但未被修改的（即修改位为0，因为修改后的页面）
页面置换算法

• 最佳置换算法（OPT，向后看）：置换在最长时间内不在被访问的页或不使用的页，性能最好，不过难以实现。缺页中断次数与页面置换次数不一样。缺页率：缺页次数/访问次数。
• 先进先出（FIFO）置换算法：置换在主存中驻留时间最久的页面。可能出现抖动或者Belady现象（物理块增加，可能出现缺页次数增加，缺页率提高）。最直观，性能最差的算法。
• 最近最少未使用（LRU，向前看）置换算法：选择最近最少使用的页面淘汰，需要设置一个访问字段（时间T），需要硬件支持（寄存器或栈）。
• 最久未用置换算法（NUR）置换算法：最近一段时间未引用的页面换出，将所有页面通过链接指针形成循环队列，某位被访问，访问位值1，选择某页淘汰，若为0，淘汰，若为1，置为0，暂不淘汰。

8）工作集：缺页率与物理块也有关系，如何为进程分配物理块才合适，因此引入工作集。工作集指某段时间间隔进程实际要访问的页面的集合。

3、作业管理

1）作业：系统为完成一个用户的计算任务所做的工作总和，由程序、数据、作业说明书3部分组成。
2）作业的控制：脱机控制方式（无须人工干预）、联机控制方式（需要人工干预）
3）作业的四种状态：提交、后备、执行和完成。

4）作业控制块（JCB）：记录与该作业有关的各种信息的登记表。作业后备队列是由若干个JCB组成的。
5）作业调度算法：先来先服务、短作业优先、响应比高优先、优先级调度算法、均衡调度算法。

• 响应比：R=作业响应时间/作业执行时间；
  由于作业响应时间等于等候时间+作业执行时间，故R=1+等待时间/作业执行时间。

6）作业调度算法衡量指标：平均周转时间或平均带权周转时间。

4、文件管理

• 信息项是构成文件内容的基本单位，一个文件包括文件体和文件说明。
• 文件系统的功能包括按名存取、统一的用户接口、并发访问和控制、安全性控制、优化性能。
• 文件类型：
  根据文件性能和用途分为系统文件、库文件、用户文件。
  按信息保存期限：临时文件、档案文件、永久文件。
  按保护方式：只读文件、读/写文件、可执行文件和不保护文件。
  UNIX系统将文件分为普通文件、目录文件和设备文件（特殊文件）
  目前常用的文件系统类型：FAT、Vfat、NTFS、Ext2、HPFS
• 文件的逻辑结构：用户角度看到的文件组织形式。分为两类。

1. 有结构的记录文件：记录描述的是一个实体集的相同数目或者不同数目的数据项。记录分为定长记录和变长记录。不过无论哪种结构在处理前每个记录的长度是可知的。
2. 无结构的流式文件：文件体为字节流，采用顺序访问方式。在UNIX系统中。所有的文件都被看做流式文件。

• 文件的物理结构：文件在文件存储器上的存取方式。常见的文件物理结构：连续结构、链接结构、索引结构、多个物理块的索引表（两种组织方式：链接文件和多重索引方式）UNIX采用的是三级索引结构，在文件系统中inode是基本构件。UNIX文件索引表项的四种寻址方式：直接寻址、一级间接寻址、二级间接寻址和三级间接寻址。

3. 常考根据物理块大小（假设1KB）和地址项长度（假设4B），可以计算存放间接索引的物理块可以存放的地址项个数：物理块大小/地址项长度。
4. 直接索引（即索引结点直接指向实际存储文件的物理块），能够表示的逻辑页号范围是0~9，能够表示的文件大小时10*1KB。
5. 一级间接索引（即索引结点指向的物理块存放的是地址项，对应地址项个数256个，可以指向256个实际存储文件的物理块），能够表示的逻辑页号范围是10~265，能够表示的文件大小是256*1KB。
6. 二级间接索引（即索引结点指向的物理块存放的是间接索引的地址项，共256个，可以指向256个存放地址项的物理块，每个物理块指向实际存储文件的地址项有256个，最终指向的物理块共有256*256个），能够表示的逻辑页号范围是266~65801，能够表示的文件大小是65536KB。
   

• 文件目录：

7. 文件控制块：包括基本信息类、存取控制信息类、使用信息类。
8. 常见目录结构：一级目录结构、二级目录结构（包括主文件目录和用户目录）、多级目录结构
9. 绝对路径从根目录开始写起，并且该文件的全名即为绝对路径+文件名。相对路径从当前位置下一级目录开始写起。

• 文件的存取方式：顺序存取和随机存取
• 文件系统需要对磁盘空间进行管理，外存空闲管理的数据结构称为磁盘分配表。采用的空闲空间管理方法：空闲区表（适用于连续文件结构）、位士图（描述能力强，适用各种物理结构，大小由磁盘空间即物理块大小决定）、空闲块链（不需要磁盘分配表）和成组链接法（UNIX采用该方法）。（学会位士图相关计算）
• 文件的共享：常见文件链接方式：硬链接（不可跨越文件系统，不利于主文件删除它拥有的文件）和符号链接（可跨越文件系统，不过增加了读盘操作的次数）
• 文件的保护采用存取控制：存取控制矩阵（难以实现）、存取控制表、用户权限表、密码。
• 不同级别保护文件系统安全性：系统级、用户级、目录级、文件级。
• 文件系统的可靠性：文件系统的一致性是影响文件系统可靠性的因素一致性。
  转储与恢复：转储方法：静态和动态转储、海量转储、增量转储。日治文件：用于进行系统故障恢复。

5、设备管理

1）设备分类：按数据组织方式：块设备、字符设备。按资源分配角度：独占设备、共享设备、虚拟设备（可以利用Spooling实现虚拟设备）。按数据传输率：低速、中速、高速设备。
2）I/O系统层次结构：中断处理程序、设备驱动程序、与设备无关的系统软件、用户级软件。

3）对于I/O传输控制方式：程序查询方式（CPU一直处于询问、等待的过程，占用CPU时间最长，CPU利用率最低）；中断方式（I/O完成后向CPU发送中断请求信号，CPU和I/O可以并行）；DMA（CPU只做初始化，不参与具体数据传输过程）；通道方式、I/O处理机，专用硬件方式。
4）设备管理采用的相关技术：通道技术（字节多路通道、数组选择通道、数组多路通道）、DMA技术、缓冲技术（单缓冲、双缓冲、多缓冲、环形缓冲）
5）Spooling技术：SPOOLing是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。 SPOOLing技术通过磁盘实现。

• spooling系统是由预处理程序、缓输出程序、井管理程序以及输入和输出井组成。
  
  6）磁盘调度：使各进程对磁盘的平均访问（主要是寻道）时间最小。磁盘调度分为移臂调度和旋转调度，并且是先进行移臂调度，再进行旋转调度。

• 磁盘调度算法：先来先服务FCFS（谁先申请先服务谁）；最短寻道时间优先SSTF（申请时判断与磁头当前位置的距离，谁短先服务谁）；扫描算法SCAN（电梯算法，双向扫描）；循环扫描CSCAN（单向扫描，从里向外）。

• 旋转调度算法：移动臂定位后，如何决定进程的访问顺序。考虑三种情况：对于1、2旋转调度总让首先到达读/写磁头位置下的扇区先传送。对于3任选一个读/写磁头位置下的扇区传送。（会找出最短寻道时间优先大的序列）

1. 进程请求访问的是同一磁道上不同编号的扇区
2. 请求访问的是不同磁道上不同编号的扇区
3. 请求访问的是不同磁道上具有相同编号的扇区

• 存取时间=寻道时间+等待时间，寻道时间是指磁头移动到磁道所需的时间；等待时间为等待读写的扇区转到磁头下方所用的时间。有时还需要加上数据的传输时间
• 。对于磁盘存储的优化，是因为磁头保持转动的状态，当读取数据传输或处理时，磁头会移动到超前的位置，需要继续旋转才能回到逻辑下一磁盘块，优化存储就是调整磁盘块的位置，让逻辑下一磁盘块放到磁头将要开始读取该逻辑块的位置。（掌握磁盘存储优化的过程和计算方法）
• 柱面号由外向里增大。