第一章操作系统引论

操作系统的特征

并发
共享
虚拟
异步

并发和共享是两个最基本的特征，二者互为存在条件。

1、并发与并行

并发：指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。

并行：指两个或多个事件在同一时间同时发生。

操作系统的并发性是指计算机系统中同时存在着多个运行着的程序。

2、共享

共享：即资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。

共享方式

互斥共享方式：系统中某些资源，一个时间段内只允许一个进程访问该资源。
同时共享方式：系统中某些资源，允许一个时间段内由多个进程“同时”对它们进行访问。

3、虚拟

虚拟：是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体是实际存在的，而逻辑上的对应物是用户感受到的。

虚拟技术

空分复用技术（如虚拟存储器技术）
时分复用技术（如虚拟处理机）

没有并发性，就谈不上虚拟性。

4、异步

异步：是指在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

只有系统拥有并发性，才可能导致异步性。

操作系统的发展与分类

手工操作阶段
批处理阶段
分时操作系统
实时操作系统
网络操作系统
分布式操作系统
个人计算机操作系统

1、手工操作阶段

缺点：用户独占全机，人机速度矛盾导致资源利用率极低。

2、批处理阶段

单道批处理系统

引入脱机输入/输出技术（用磁带完成），并监督程序负责控制作业的输入、输出。

优点：缓解了一定程度的人机速度矛盾，资源利用率有所提升。

缺点：内存中仅能有一道程序运行。CPU有大量的时间是在空闲等待I/O完成。资源利用率依然很低。

多道批处理系统

优点：多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU和其他资源保持“忙碌”状态，系统吞吐量增大。

缺点：用户响应时间长，没有人机交互功能。

3、分时操作系统

分时操作系统：计算机以时间片为单位轮流为各个用户/作业服务，各个用户可以通过终端与计算机进行交互。

优点：用户请求可以被即时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人存在。

缺点：不能优先处理一些紧急任务。操作系统对各个用户/作业都是完全公平的，循环地为每个用户/作业服务一个时间片，不区分任务的紧急性。

4、实时操作系统

优点：能够优先响应一些紧急任务，某些紧急任务不需要时间片排队。

在实时系统控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。

特点：及时性、可靠性

操作系统运行机制和体系结构

1、指令

指令：CPU能识别、执行的最基本命令。

特权指令
非特权指令

2、处理器状态

用户态（目态）：只能执行非特权指令
核心态（管态）

3、程序

内核程序：系统的管理者，既可以执行特权指令，也可以执行非特权指令，运行在核心态。
应用程序：只能执行非特权指令，运行在用户态。

4、操作系统的内核

时钟管理
中断处理
原语
对系统资源进行管理的功能

内核：是计算机上配置的底层软件，是操作系统最基本最核心的部分。

分类：大内核、微内核。

	定义	优点	缺点
大内核	将操作系统的主要功能模块都作为系统内核，运行在核心态	高性能	内核代码庞大，结构混乱，难以维护
微内核	只把最基本的功能保留在内核	内核功能少，结构清晰，方便维护	需要频繁的在核心态和用户态之间切换，性能低

中断

中断可以使CPU从用户态切换为核心态，使操作系统获得计算机的控制权。

内中断（也称异常、例外、陷入）
外中断（中断）

系统调用

设备管理：完成设备的请求/释放/启动等功能
文件管理：完成文件的读/写/创建/删除等功能
进程控制：完成进程的创建/撤销/阻塞/唤醒等功能
进程通信：完成进程之间的消息传递/信号传递等功能
内存管理：完成内存的分配/回收等功能

第二章进程

进程的定义、组成、组织方式、特征

1、进程的定义

程序：就是一个指令序列

进程实体（进程映像）：PCB（进程存在的唯一标志）、程序段、数据段。

进程：是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

2、进程的组成

程序段
数据段
PCB：进程标识符、处理机状态、进程调度信息、进程控制信息。

3、进程的组织方式

链接方式
索引方式

链接方式

按照进程状态将PCB分为多个队列

操作系统持有指向各个队列的指针

执行指针
就绪队列指针
阻塞队列指针

索引方式

按照进程状态不同，建立几张索引表

操作系统持有指向各个索引表的指针

执行指针
就绪表指针
阻塞表指针

4、进程的特征

动态性：进程是程序的一次执行过程，是动态地产生、变化、和消亡的。（最基本特征）
并发性：内存中有多个进程实体，各进程可并发执行。
独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位。
异步性：各进程按各自独立的、不可预知的速度向前推进，操作系统要提供“进程同步机制”来解决异步问题。
结构性：每个进程都会配置一个PCB。结构上看，进程由程序段、数据段、PCB组成。

进程的状态与转换

1、进程的状态

三种基本状态

运行态：占有CPU，并在CPU上运行。
就绪态：已经具备运行条件，但由于没有空闲CPU，而暂时不能运行。
阻塞态：因等待某一事件而暂时不能运行。

另外两种状态

创建态（新建态）：进程正在被创建，操作系统为进程分配资源、初始化PCB。
终止态（结束态）：进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB。

2、进程状态的转换

算法：

1)在资源分配图中，找出既不阻塞又不是孤点的进程Pi (即找出一-条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如下图中，R1没有空闲资源，R2有一个空闲资源。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源)。消去它所有的请求边和分配变，使之称为孤立的结点。在下图中，P1是满足这一条件的进程结点，于是将P1的所有边消去。

2)进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在下图中，P2 就满足这样的条件。根据1)中的方法进行一系列简化后，若能消去途中所有的边，则称该图是可完全简化的。

死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁。

死锁的解除

资源剥夺法。挂起( 暂时放到外存上)某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
撤销进程法(或称终止进程法)。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏- -篑，以后还得从头再来。
进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

第三章内存

内存的基础知识

内存是用于存放数据的硬件。程序执行前需要先放到内存中才能被CPU处理。

装入的三种方式

绝对装入：在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存。（只适用于单道程序环境）

静态重定位：又称可重定位装入。编译、链接后的装入模块的地址都是从0开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变换为物理地址(地址变换是在装入时一次完成的)。

动态重定位：又称动态运行时装入。编译、链接后的装入模块的地址都是从0开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。（允许程序在内存中发生移动）

链接的三种方式

静态链接：在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件(装入模块)之后不再拆开。
装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式。

运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。

内存管理的概念

1、操作系统负责内存空间的分配与回收

2、操作系统需要提供某种技术从逻辑上对内存空间进行扩充

3、操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换

4、操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰。

设置一对上下限寄存器
采用重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）

重定位寄存器：放的是起始物理地址。

界地址寄存器：放的是最大逻辑地址。

内存空间的扩充

覆盖技术

必须由程序员声明覆盖结构，操作系统完成自动覆盖。

缺点：对用户不透明，增加了用户编程负担。

交换技术

设计思想：内存空间紧张时，系统将内存中某些进程暂时换出（挂起）外存，把外存中某些已具备运行条件的进程换入内存。

磁盘分为文件区和交换区，换出的进程放在对换区。

区别

覆盖时在同一个程序或进程中的。

交换时在不同进程（或作业）之间的。

内存空间的分配与回收

连续分配：指用户进程分配的必须是一个连续的内存空间。

连续分配管理方式

单一连续分配

内存分为系统区和用户区。

系统区通常位于内存的低地址部分，用于存放操作系统相关数据；

用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间。

优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护。

缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。

固定分区分配

分区大小相等
分区大小不等

使用分区说明表来实现对各个分区的分配与回收。每个表包括对应分区的大小，起始地址，状态。

优点：实现简单，无外部碎片。

缺点：a.当用户程序太大时，可能所有分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能；b.会产生内部碎片，内存利用率低。

动态分区分配

不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态的建立分区。

数据结构：空闲分区表/空闲分区链

动态分区没有内部碎片，但有外部碎片。

紧凑技术

动态分区分配算法

首次适应算法

算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

最佳适应算法

算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的–整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。

实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

缺点：每次都选择最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多外部碎片。

最坏适应算法

又称最大适应算法( Largest Fit)
算法思想：为了解决最佳适应算法的问题–即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。

实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。

邻近适应算法

算法思想：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

实现：空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

首次适应算法每次都要从头查找，每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时，
会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留”下来(最佳适应算法的优点)

邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使
用，划分为小分区，最后导致无大分区可用(最大适应算法的缺点)

基本分页存储管理的基本概念

思想：把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分。

每个分区就是一个页框/页帧/内存块/物理块。每个页框有一个编号，即”页框号“，页框号从0开始。

将用户进程的地址空间也分为与页框大小相等的一个个区域，称为“页”或“页面”。每个页面也有一个编号，即“页号”，页号也是从0开始。

地址转换

页号=逻辑地址/页面长度

页内偏移量=逻辑地址%页面长度

页表

页表项由”页号“（隐含）和”块号“组成。

页表记录进程页面和实际存放的内存块之间的对应关系

基本地址变换机构

具有快表的地址变换机构

局部性原理

时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某个数据被访问过，不久之后该数据很可能再次被访问。( 因为程序中存在大量的循环)

空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的)

快表

快表，又称联想寄存器(TLB) ，是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。

页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。

段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。

页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。

分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。

分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。

分段比分页更容易实现信息的共享和保护。

不能被修改的代码称为纯代码或可重入代码(不属于临界资源)，这样的代码是可以共享的。可修改的代码是不能共享的(比如，有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致)

分页（单级页表）、分段访问一个逻辑地址都需要两次访存，分段存储中也可以引入快表机构。

段页式管理方式

	优点	缺点
分页管理	内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片	不方便按照逻辑模块实现信息的共享和保护
分段管理	很方便按照逻辑模块实现信息的共享和保护	如果段长过大，为其分配很大的连续空间会很不方便。另外，段式管理会产生外部碎片

段页式系统的逻辑地址结构：由段号、页号和页内地址所组成。

引入快表后仅需一次访存。

虚拟内存

基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存。

特征:

多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
对换性：在作业运行时无需一-直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。

实现

请求分页存储管理
请求分段存储管理
请求段页式存储管理

请求分页管理方式

缺页中断机构

在请求分页系统中，每当要访问的页面不在内存时，便产生-一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。

缺页中断属于内中断。

地址变换机构

页面置换算法

最佳置换算法（OPT）
先进先出置换算法（FIFO）
最近最久未使用置换算法（LRU）
时钟置换算法（CLOCK）
改进型时钟置换算法

1、最佳置换算法（OPT）

内容：每次选择淘汰的页面将是以后永远不使用，或者在最长时间内不再被访问的页面。

2、先进先出置换算法（FIFO）

内容：每次选择淘汰的页面是最早进入内存的页面

实现方法：把调入内存的页面根据调入的先后顺序排成一一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。

Belady异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

3、最近最久未使用置换算法（LRU）

内容：每次淘汰的页面是最近最久未使用的页面

实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。

4、时钟置换算法（CLOCK）

内容：最佳置换算法性能最好，但无法实现;先进先出置换算法实现简单，但算法性能差;最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。时钟置换算法是一-种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法(NRU，Not Recently Used)。

实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出;如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些

来源：CHE_NG程

声明：本站部分文章及图片转载于互联网，内容版权归原作者所有，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！

【知识点总结】计算机操作系统

第一章 操作系统引论