【复习】计算机操作系统知识点整理

一、基本特征1.并发2.共享3.虚拟4.异步 二、基本功能1.进程管理（1）进程与线程（2）进程状态（3）进程调度算法（4）进程同步（5）进程通信 2.内存管理（1）内存划分虚拟内存分页分段段页式 （2）内存分配页面置换算法 3.文件管理4.设备管理（1）磁盘磁盘调度算法 三、内核1.宏内核2.微内核3.系统调用 四、中断1.外中断2.异常3.陷入 五、编译1.编译系统2.链接静态链接动态链接

一、基本特征

1.并发

并发是指宏观上在一段时间内能同时运行多个程序。

并行则指同一时刻能运行多个指令。操作系统通过引入进程和线程，使得程序能够并发运行。并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统。

2.共享

共享是指系统中的资源可以被多个并发进程共同使用。有两种共享方式：互斥共享和同时共享。互斥共享的资源称为临界资源，例如打印机等，在同一时刻只允许一个进程访问，需要用同步机制来实现互斥访问。

3.虚拟

虚拟技术把一个物理实体转换为多个逻辑实体。主要有两种虚拟技术：（时间）时分复用技术和（空间）空分复用技术。多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换。虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。(地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中。)

4.异步

异步指进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进。

二、基本功能

1.进程管理

进程控制、进程同步、进程通信、死锁处理、处理机调度等。

（1）进程与线程

进程是资源分配的基本单位。

进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。线程是独立调度的基本单位。

线程控制块（Thread Control Block，TCB）与进程控制块相似。

一个进程中可以有多个线程，它们共享进程资源。如浏览器进程里面有很多线程——HTTP 请求线程、事件响应线程、渲染线程等

进程与线程的区别

Ⅰ 拥有资源

进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。

Ⅱ 调度

线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。

Ⅲ 系统开销

由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。

Ⅳ 通信方面

线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。

（2）进程状态

就绪状态：等待被调度；阻塞状态：等待资源。

注意

a. 只有就绪态和运行态可以相互转换，其它的都是单向转换。

就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。

b. 阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

（3）进程调度算法

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

批处理系统环境下

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

1.先来先服务 first-come first-serverd（FCFS）:非抢占式的调度算法，按照请求的顺序进行调度。(有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。)2.短作业优先 shortest job first（SJF）:非抢占式的调度算法，按估计运行时间最短的顺序进行调度。(长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。)3.最短剩余时间优先 shortest remaining time next（SRTN）:最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。(当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。)

交互式系统环境下

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

1.时间片轮转：将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。（因为进程切换都要保存进程的信息并且载入新进程的信息，所以时间片轮转算法的效率和时间片的大小有很大关系：如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。如果时间片过长，那么实时性就不能得到保证。）2.优先级调度：为每个进程分配一个优先级，按优先级进行调度。（为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。）3.多级反馈队列：可以看成是时间片轮转调度算法和优先级调度算法的结合。

实时系统环境下

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

（4）进程同步

同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。

同步与异步的区别

互斥：多个进程在同一时刻只有一个进程能进入临界区。

对临界资源进行访问的那段代码称为临界区。

为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。

信号量

信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作，用于为多个进程提供对共享数据对象的访问。

互斥量（Mutex）是信号量的取值只能为 0 或 1，0 表示临界区已经加锁，1 表示临界区解锁。

管程

经典问题

1）生产者-消费者问题

2）哲学家进餐问题

3）读者-写者问题

死锁

1）必要条件：互斥、占有和等待、不可抢占、环路等待

2）处理方法：鸵鸟策略、死锁检测与死锁恢复、死锁预防、死锁避免

1.鸵鸟策略：忽略发生的死锁问题。（因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。）2.死锁检测与死锁恢复：不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。（`死锁检测算法`；死锁恢复：利用抢占恢复、利用回滚恢复、通过杀死进程恢复）3.死锁预防：在程序运行之前预防发生死锁。（破坏互斥条件、破坏占有和等待条件、破坏不可抢占条件、破坏环路等待）4.死锁避免：在程序运行时避免发生死锁。（`安全状态`、`银行家算法`）

（5）进程通信

进程通信：进程间传输信息。（进程同步：控制多个进程按一定顺序执行）

进程通信是一种手段，而进程同步是一种目的。

也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

管道

具有以下限制：只支持半双工通信（单向交替传输）；只能在父子进程或者兄弟进程中使用。命名管道FIFO

去除了管道只能在父子进程中使用的限制。

FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据。消息队列

消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；

避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法；

读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。共享存储

允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制，所以这是最快的一种 IPC。

需要使用信号量用来同步对共享存储的访问。

多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。另外 XSI 共享内存不是使用文件，而是使用内存的匿名段。套接字

与其它通信机制不同的是，它可用于不同机器间的进程通信。

2.内存管理

操作系统对内存的划分和动态分配。包括内存分配、地址映射、内存保护与共享、虚拟内存等。

（1）内存划分

虚拟内存

目的：为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。

虚拟内存采用的是分页技术。

分页

分页的做法是将地址空间划分成固定大小的页，每一页再与内存进行映射。内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page

table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。

分段

分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。

段页式

程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

分页与分段的比较

1.对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。

2.地址空间的维度：分页是一维地址空间，分段是二维的。

3.大小是否可以改变：页的大小不可变，段的大小可以动态改变。

4.出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

（2）内存分配

页面置换算法

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。

最佳（OPT）：是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。

所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。最近最久未使用（LRU）

将最近最久未使用的页面换出。最近未使用（NRU）

每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：R=0，M=0；R=0，M=1；R=1，M=0；R=1，M=1。

当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。

NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。先进先出（FIFO）

选择换出的页面是最先进入的页面。该算法会将那些经常被访问的页面换出，导致缺页率升高。第二次机会算法

FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：

当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。时钟算法

第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。

3.文件管理

文件存储空间的管理、目录管理、文件读写管理和保护等。

4.设备管理

完成用户的 I/O 请求，方便用户使用各种设备，并提高设备的利用率。

主要包括缓冲管理、设备分配、设备处理、虛拟设备等。

（1）磁盘

磁盘调度算法

读写一个磁盘块的时间的影响因素有：旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）、寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）、实际的数据传输时间

其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

先来先服务（FCFS）

按照磁盘请求的顺序进行调度。

优点是公平和简单。缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。最短寻道时间优先（SSTF）

优先调度与当前磁头所在磁道距离最近的磁道。

虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。电梯算法（SCAN）

电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。

因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。

三、内核

1.宏内核

宏内核是将操作系统功能作为一个紧密结合的整体放到内核。由于各模块共享信息，因此有很高的性能。

2.微内核

由于操作系统不断复杂，因此将一部分操作系统功能移出内核，从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务，相互独立。在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。因为需要频繁地在用户态和核心态之间进行切换，所以会有一定的性能损失。

3.系统调用

如果一个进程在用户态需要使用内核态的功能，就进行系统调用从而陷入内核，由操作系统代为完成。

四、中断

1.外中断

由 CPU 执行指令以外的事件引起，如 I/O 完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。

2.异常

由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等。

3.陷入

在用户程序中使用系统调用。

五、编译

1.编译系统

预处理阶段：处理以 # 开头的预处理命令；编译阶段：翻译成汇编文件；汇编阶段：将汇编文件翻译成可重定位目标文件；

（可重定位目标文件：可与其它可重定位目标文件在链接阶段合并，创建一个可执行目标文件；）

（共享目标文件：这是一种特殊的可重定位目标文件，可以在运行时被动态加载进内存并链接；）链接阶段：将可重定位目标文件和 printf.o 等单独预编译好的目标文件进行合并，得到最终的可执行目标文件。

（可执行目标文件：可以直接在内存中执行；）

2.链接

静态链接

静态链接器以一组可重定位目标文件为输入，生成一个完全链接的可执行目标文件作为输出。

链接器主要完成以下两个任务：

符号解析：每个符号对应于一个函数、一个全局变量或一个静态变量，符号解析的目的是将每个符号引用与一个符号定义关联起来。重定位：链接器通过把每个符号定义与一个内存位置关联起来，然后修改所有对这些符号的引用，使得它们指向这个内存位置。

静态库有以下两个问题：

1）当静态库更新时那么整个程序都要重新进行链接；

2）对于 printf 这种标准函数库，如果每个程序都要有代码，这会极大浪费资源。

动态链接

共享库是为了解决静态库的这两个问题而设计的，在 Linux 系统中通常用.so 后缀来表示，Windows 系统上它们被称为DLL。

它具有以下特点：

在给定的文件系统中一个库只有一个文件，所有引用该库的可执行目标文件都共享这个文件，它不会被复制到引用它的可执行文件中；在内存中，一个共享库的 .text 节（已编译程序的机器代码）的一个副本可以被不同的正在运行的进程共享。