操作系统 | echo

计算机系统概述

操作系统基本概念

操作系统特征：并发和共享。

操作系统的目标和功能

资源管理：处理机管理、存储器管理、文件管理、设备管理。
用户与硬件的接口：命令接口、程序接口（系统调用）。

操作系统的分类和发展

手工操作阶段（无操作系统）
批处理阶段（操作系统开始阶段）解决人机矛盾和CPU和I/O速度不匹配的问题。分为单道批处理和多道批处理系统（内存中只能保持一道作业和能保持多道作业）。
分时操作系统。将 CPU 时间分为许多时间片，采用时间片轮转法，支持多道程序设计的系统。
实时操作系统。
网络操作系统和分布式操作系统。

中断和异常

中断也称为外中断，指来自 CPU 执行指令以外的事情发生，如 I/O 中断。时钟中断表示固定的时间片已到。

异常也称为内中断，指源自CPU执行指令或内存内部的时间，如程序的非法操作码、地址越界、算术溢出、缺页等引起的事件。

系统调用

系统调用可视为特殊的公共子程序。凡是与资源有关的操作（如存储分配、进行 I/O 传输及管理文件等），都必须通过系统调用方式向操作系统提出服务请求。

核心态与用户态

系统调用需要使用某些特权指令才能完成，需要由操作系统内核程序负责完成。用户程序通过执行访管指令来发起系统调用，请求操作系统提供服务。执行操作系统内核应用程序时，CPU 会在核心态，执行用户程序时在用户态。

用户态转向核心态：系统调用、发生中断和异常、执行特权指令、进程状态变换。

进程管理

进程与线程

进程的特征：动态性、并发性、独立性、异步性、结构性。进程实体都是由程序段、数据段和进程控制块三部分组成的。

进程的状态与转换

运行态：单处理机环境下，每个时刻最多只能有一个进程处于运行态。

就绪态：进程已经准备运行，等待 CPU 调度。

阻塞态：进程正在等待某一事件而暂停运行。

进程三大状态之间的转换忽略。

线程概念和多线程模型

引入线程的目的是为了更好地使用多道程序并发执行，提高资源利用率和系统吞吐率。引进线程地目的则是为了减少程序在并发执行时所付出地时空开销，提高操作系统地并发性能。

处理机调度

作业调度。又称高级调度，从外存上处于后备状态地作业中挑选一个或多个作业，给他们分配内存、输入/输出等必要的资源，并建立相应的进程。
内存调度。又称中级调度，其作用是提高内存利用率和系统吞吐量。将暂时不能运行的进程调至外存等待，当运行条件已经具备，再将就绪进程重新调入内存。
进程调度。又称低级调度，按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。

典型的调度算法

先来先服务算法

FCFS 调度算法既可以用于作业调度，又可以用于进程调度。算法简单，效率较低。对长作业比较有利，对短作业不利；有利于 CPU 繁忙型作业，不利于 I/O繁忙型作业。

短作业优先

短作业优先算法从后备队列中选择一个或若干估计运行时间最短作业，将它们调入内存运行。对长作业不利，会导致“饥饿”现象，SJF 调度算法的平均等待时间、平均周转时间最少。

优先级调度算法

既可用于作业调度，又可用于进程调度，优先级描述作业运行的紧迫程度。按高优先级进程能否抢占正在执行的进程分为剥夺式优先级调度算法和非剥夺优先级调度算法。根据优先级是否改变分为动态优先级和静态优先级。

高响应比优先调度算法

用于作业调度，是对FCFS调度算法和SJF调度算法的一种综合平衡，同时还考虑了每个作业的等待时间和估计运行时间。
$$
响应比R_p=\frac{等待时间+要求服务时间}{要求服务时间}
$$

时间片轮转法

主要适用于分时系统，系统将所搜就绪进程按时间的先后顺序排成一个队列，进程调度程序选择就绪进程依次执行一个时间片。时间片很大时退化为 FCFS 算法，时间片很小时导致进程切换开销过大。

多级反馈队列调度算法

时间片轮转法和优先级调度算法的综合与发展。通过动态调整进程优先级和时间片大小，多级反馈队列可以兼顾多方面的系统目标。设置多个就绪队列，并为每个队列赋予不同的优先级，在优先级越高的队列中，每个进程运行的时间片越小。

进程的同步

进程同步的基本概念

临界资源：一次只允许一个进程使用的资源称为临界资源。

临界区：访问临界资源的那段代码。

同步：直接制约关系，为完成某任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程之间的直接制约关系源于它们之间的合作。

互斥：间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界区资源的进程退出临界区后，另一个进程才允许访问此临界资源。

死锁

多个进程因竞争资源而造成的一种相互等待的情况，若无外力作用，这些进程都将无法向前推进。

死锁产生的必要条件

互斥条件
不可抢占条件
请求并保持条件
循环等待条件

死锁的处理策略

死锁预防，破环产生死锁 4 个条件中的一个或几个。
死锁避免，在动态分配资源过程中，用某种方法防止系统进入不安全状态。银行家算法
死锁的检测及解除，通过系统检查出死锁的发生，采取某种措施解除死锁。

内存管理

内存管理概念

内存管理的功能

内存空间的分配与回收，由操作系统完成主存储器空间的分配与管理。
地址转换，在多道程序环境下，程序中的逻辑地址与内存中的物理地址不可能一致，存储器管理须提供地址变换功能，将逻辑地址转换为响应的物理地址。
内存空间的扩充，利用虚拟存储技术
存储保护，保证各道作业在各自的存储空间内运行，互不干扰。

程序的装入和链接

将源程序变为可在内存中执行的程序，一般需要以下几个步骤：

编译，将用户源代码编译成若干目标模块，形成逻辑地址。
链接，将编译后的目标模块及所需要的库函数链接在一起，形成整个完整的装入模块。
装入，将完整的装入模块装入内存。

链接分为三种：

静态链接，在程序运行前，链接库函数。
装入时动态链接，在程序装入内存时，将库函数链接。
运行时动态链接，在程序执行时，将库函数链接。

装入分三种：

绝对装入，逻辑地址和物理地址完全相同。
可重定位装入。将装入模块装入内存适当的位置，装入时对指令和数据的修改过程称为重定位。地址变化通常是在装入时一次完成。
动态运行时装入，装入程序把装入模块装入内存后，并不立即把模块中的相对地址转换为绝对地址，在程序运行的过程中才进行地址的转换。

连续分配管理方式

单一连续分配。在内存中永远只有一道程序，不会产生越界访问。
固定分区分配。将内存划分为若干固定大小的区域，每个分区只装入一道作业。
动态分区分配。在进程装入内存时，根据进程的大小动态地建立分区。

动态分区的分配策略：

首次适应算法，空闲分区按地址递增的次序链接，分配时按顺序查找，找到大小能满足要求的第一个空闲分区。
最佳适应算法，空闲分区按分区大小递增的次序链接，找到第一个能满足要求的分区。
最坏适应算法，空闲分区按分区大小递减的次序链接，找到第一个能满足要求的分区。
临近适应算法，分配内存时从上一次查找结束的位置开始继续查找。

非连续分配管理方式

非连续分配允许将一个程序分散地装入不相邻的内存分区。

把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存块中的空间。

1. 分页

进程中的块称为页(Page)，内存中的块称为页框(Page Frame，或页帧)。外存也以同样的单位进行划分，直接称为块(Block)。进程在执行时需要申请主存空间，即为每个页面分配主存中的可用页框。

页面大小应该是2的整数幂。页面太小会使进程的页面过多，页表过长，占用大量的内存，增加硬件地址转换的开销，降低页面换人/换出的效率；页面过大会使内部碎片增多，降低内存利用率。

为了便于内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页表，它记录页面在内存中对应的物理块号，页表一般存放在内存中。页表由页表项组成，页表项 = 页号 + 页框号。物理地址 = 页内地址 + 页框号 × 页面大小

2. 分段

段式管理按照用户进程中的自然段划分逻辑空间。在页式系统中，逻辑地址的页号和页内偏移量对用户是透明的，但在段式系统中，段号和段内偏移量必须由用户显式提供，在高级程序设计语言中，这个工作由编译程序完成。

虚拟内存管理

虚拟内存基本概念

传统存储管理方式的特征

1）一次性。作业必须一次性全部装入内存，才开始运行。

2）驻留性。作业被装入内存后，就一直驻留在内存中，可能造成进程长时间阻塞。

局部性原则

1）时间局部性。程序中某条指令一旦执行，不久后该指令可能再次执行。

2）空间局部性。一旦程序访问了某个存储单元，不久后，其附近的存储单元也被访问。

虚拟存储器的主要特性

1）多次性。作业可分多次调入内存执行。

2）对换性。在作业运行过程中允许进行换入和换出。

3）虚拟性。从逻辑上扩充内存的容量。

虚拟存储技术的实现

虚拟存储系统只能基于非连续分配技术，连续分配方式时，会使相当一部分内存空间处于暂时或者“永久”空闲的状态，严重造成内存资源的浪费。

1）请求分页存储管理

2）请求分段存储管理

3）请求段页式存储管理

不管哪种方式，都需要一定的硬件的支持，一般需要的支持有以下几个方面：

一定容量的内存和外存
页表机制(或段表机制)，作为主要的数据结构
中断机制，当用户程序要访问的部分尚未调入内存时，则产生中断
地址变换机制，逻辑地址和物理地址的转换。

页面置换算法

最佳(OPT)置换算法

淘汰以后永久不使用的页面或者在最长时间内不再被访问的页面，以便保证获得最低的缺页率。由于人们目前无法预知进程在内存下的若干页面中哪个是未来最长时间内不再被访问的，因此该算法无法实现。

先进先出(FIFO)页面置换算法

优先淘汰最早进入内存的页面，即在内存中驻留时间最久的页面。

最近最久未使用(LRU)置换算法

选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近将来可能也不会被访问。

时钟(CLOCK)置换算法

简单的CLOCK算法给每帧关联一个附加位，称为使用位。当某页首次装入主存时，将该帧的使用位置为1。

抖动

在页面置换算法中，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存，这种频繁的页面调度行为称为抖动。

文件系统

文件三种分配方式比较

	访问第 n 条记录	优点	缺点
连续分配	访问磁盘 1 次	顺序存取速度快，文件定长时可按文件起始地址及记录长度进行随机访问。	文件存储需要连续的存储空间，会产生碎片，不利于文件的动态扩充
链式分配	访问磁盘 n 次	可解决外存的随便化问题，提高外存空间的利用率，动态增长较方便	只能按照文件的指针链顺序访问，查找效率低，指针信息存放消耗外存空间
索引分配	m 级需访问磁盘 m+1 次	可以随机访问，文件易于增删	索引表增加存储空间的开销，索引表的查找策略对文件系统效率影响较大

磁盘调度算法

	描述	优点	缺点
先来先服务(FCFS)算法	按磁盘请求队列中的磁道号依次移动	公平、简单	平均寻道距离大，仅应用在磁盘I/O较少的场合
最短寻找时间优先(SSTF)算法	选择离当前磁头距离最近的磁道	性能比“先来先服务”好	不能保证平均寻道时间最短，可能导致“饥饿”现象
扫描(SCAN)算法	按磁头移动方向移动到最边缘的磁道，然后反向	寻道性能较好，可避免“饥饿”现象	不利于远离磁头一端的访问请求
循环扫描(C-SCAN)算法	按磁头移动方向移动到最边缘的磁道，然后从另一端开始重新扫描	消除了对两端磁道请求的不公平	—

I/O 管理

I/O 控制方式

程序直接控制方式，每读一个字，CPU 对外设状态进行循环检查。CPU和I/O设备只能串行工作，CPU的利用率相对低。
中断驱动方式，允许I/O设备主动打断CPU的运行并请求服务，使得其向I/O控制器发送读命令后 CPU 继续做其它有用的工作。比程序直接控制更有效，但由于数据中的每个字在存储器与I/O控制器之间的传输都必须经过CPU，这就导致了中断驱动方式仍然会耗很多CPU时间。
DMA 方式，I/O设备和内存之间开辟直接的数据通路。
通道控制方式，I/O通道是专门负责输入/输出的处理机。I/O通道方式是DMA方式的发展，它可以减少CPU的干预。