完整word版操作系统期末复习重点知识点总结word文档良心出品.docx
《完整word版操作系统期末复习重点知识点总结word文档良心出品.docx》由会员分享，可在线阅读，更多相关《完整word版操作系统期末复习重点知识点总结word文档良心出品.docx（57页珍藏版）》请在冰点文库上搜索。
完整word版操作系统期末复习重点知识点总结word文档良心出品
填空
绪论：
批处理系统、分时系统、实时系统的概念与特点，原语与原子操作。
1.批处理操作
（1）单道批处理系统概念
单道批处理系统是指系统通过作业控制语言将作业组织成批，使其能自动连续运行，但是，在内存中任何时候只有一道作业的系统。
单道批处理系统特征
顺序性单道性自动性
（2）多道批处理系统概念
系统对作业的处理是成批进行的，并且在主存中能同时保留多道作业的系统。
多道批处理系统的主要目标是提高系统吞吐率和各种资源的利用率。
多道批处理系统特征
无序性多道性调度性
2.分时系统
（1）概念
分时操作系统是指在一台主机上连接了多个联机终端，并允许多个用户通过终端以交互的方式使用主计算机，共享主机资源的系统。
（2）分时系统的主要目标是实现人与系统的交互性。
分时系统设计的目标是保证用户响应时间的及时性。
（3）分时系统的特征
多路性独立性及时性：
满足用户对响应时间的要求交互性
3.实时操作系统
（1）概念
实时操作系统是指系统能够及时响应外部（随机）事件的请求，并能在规定的时间内完成对该事件的处理，控制系统中所有的实时任务协调一致地工作。
（2）实时操作系统的特征
多路性独立性及时性：
满足实时任务截止时间的要求交互性可靠性
4.原语：
操作系统内核或微核提供核外调用的过程或函数称为原语，是由若干条指令构成，用于完成特定功能的一段程序。
原语在执行过程不允许被中断。
5.原子操作：
执行中不能被其它进程（线程）打断的操作就叫原子操作。
当该次操作不能完成的时候，必须回到操作之前的状态，原子操作不可拆分。
进程管理：
什么是进程？
进程与程序的区别与联系？
进程的特征有哪些？
进程之间的关系有哪些？
什么是信号量？
信号量的物理含义？
1.进程定义
可并发执行的程序在一个数据集合上的运行过程，是系统进行资源分配和调度的基本单位。
2.进程特征
（1）动态性
（2）并发性（3）独立性（4）异步性（5）结构特征：
3.进程与程序的关系
（1）程序是一组指令的集合，是静态的概念；进程是程序的执行，是动态的概念。
（本质区别）
（2）进程有生命周期，它的存在是暂时的；程序的存在是永久的。
（3）进程包括程序代码、数据和“进程控制块”三部分。
（4）进程是一个独立的运行单位，是系统进行资源分配和调度的独立单位。
（5）一个程序在执行中可对应多个进程，一个进程也可能包含多个程序段。
4，进程的基本状态
（1）运行状态（Running）:
已得到CPU，正在执行的状态。
（2）就绪状态（Ready）：
得到了除CPU以外的所有资源，正在等待CPU的状态。
（3）等待状态（Blocked，也称阻塞状态）：
进程等待某一事件的发生而暂时停止运行的状态。
5.进程之间的关系有哪些
同步互斥
6.什么是信号量？
信号量是实现进程同步的一种变量。
是一种有效的进程同步工具，可分为：
整型信号量、结构型信号量、信号量集等。
7.信号量的物理含义
S>0表示有S个资源可用
S=0表示无资源可用
S<0则|S|表示S等待队列中的进程个数
P（S）:
表示申请一个资源
V（S）表示释放一个资源。
信号量的初值应该大于等于0
设备管理：
设备的分类
按数据传输单位，设备可分成：
Ø字符设备（输入输出设备）：
字符设备中存储和传送的是不定长的数据，是以字符为单位发送或和接收一个字符流，传输速度低、不可寻址（源地址或目标地址）。
如打印机、键盘、网卡和显示器等。
Ø块设备（存储设备）：
块设备中存储是定长的、且可随机访问的数据块，每个块都有自己的地址，信息处理的基本单位是数据块，传输速度高、可寻址。
如磁盘，CD-ROM。
按传输速率，设备可分成：
Ø低速——键盘、鼠标器、语音的输入和输出设备
Ø中速——行式打印机、激光打印机
Ø高速——磁带机、磁盘器、光盘机
按共享属性，设备可分成：
Ø独占设备：
一次只允许一个进程访问的设备。
Ø共享设备：
一段间内允许多个进程同时访问的设备。
Ø虚拟设备：
虚拟技术将一台独占设备转换为若干台逻辑设备，共多个进程同时使用。
按使用属性，设备可分成：
Ø存储设备：
相同中存储信息的主要设备，外存及后备存储器。
Ø人机交互设备（输入/输出设备）：
输入、输出和集成输入和输出的设备。
文件管理：
什么是文件的逻辑结构和文件的物理结构？
文件的逻辑结构有哪些？
文件的物理结构有哪些？
1.文件的逻辑结构
（1）概念
是指用户可以直接处理的文件组织形式，也称文件组织。
文件逻辑结构选取的主要考虑因素：
存取速度、维护方便和可靠性等。
（2）分类
从逻辑结构上，文件分为：
有结构文件（记录式文件）和无结构文件（字符流文件，是一种顺序文件。
）
有结构文件（记录式文件）
①根据文件中记录特性分：
定长记录文件变长记录文件
②文件的组织方式（逻辑结构）：
顺序文件索引文件索引顺序文件
2.文件物理结构
（1）概念
是指文件在外存上的存储结构，也称文件存储结构。
文件的物理结构决定了文件信息在存储设备上的存放位置。
（2）物理结构的类型
连续文件串联文件（链接文件）索引文件hash文件
简答
1.进程的概念与特点、进程的同步与互斥。
进程概念
关于进程的定义有多种，其中最具代表性的定义有以下几个：
（1）进程是程序的一次执行
（2）进程是可以与别的计算并发执行的计算
（3）进程是一数据结构及能在其上进行操作的一个程序
（4）进程是一个程序及其数据在处理机上顺序执行时所发生的活动
（5）进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位
进程特征
（1）动态性：
动态性是进程的基本特性。
进程具有生命周期，它由创建而产生，经调度而执行，由撤消而消亡。
（2）并发性：
在内存中的多个进程实体能在一段时间内同时运行。
（3）独立性：
进程是系统进行资源分配和调度的一个基本单位，是一个能够进行独立运行的基本单位。
（4）异步性：
每个进程在运行时都在以不可预知的速度向前推进。
（5）结构特征：
进程实体实际上是由三部分所组成：
程序段、数据段和进程控制块PCB。
在UNIX系统中，也把这三部分称为“进程映像”。
进程同步与互基本概念
（1）并发进程之间的协作控制通常称为进程同步。
——直接制约关系（协作）
（2）并发进程之间的竞争控制通常称为进程互斥。
——间接制约关系（竞争）
进程同步与互斥的主要任务就是保证多个并发进程能有效地合作并共享系统资源，使并发进程的执行结果具有可再现性。
2.死锁的概念、死锁产生的原因、死锁的预防和避免方法、资源分配图的简化、死锁定理。
（1）死琐概念
死锁是指多个并发执行的进程因资源争夺而出现的一种彼此都不能继续向前推进的僵持局面。
（2）产生死琐的原因
①竞争资源——竞争非剥夺性资源（如，打印机）和竞争临时资源（如，某进程生产的数据、消息）
②进程推进的顺序非法
（3）死琐的预防
①避开“请求和保持”条件：
一次性请求，一次性分配。
在进程运行期间不再提出资源请求。
这种方法也称“预先静态分配法”。
②避开“不剥夺”条件：
进程逐个提出资源请求，当前请求不能满足时，必须释放它所拥有的全部资源。
③避开“环路等待”条件：
将所有资源按类型进行线性排队，并赋予不同序号，要求进程申请资源时按序号递增的次序提出。
这种方法也称“有序资源分配法”。
（4）死锁的避免——银行家算法，死锁的预防——资源有序分配法。
（5）资源分配图的简化
从图找一个进程结点pi，若它对资源Rj（1≤j≤m）的请求满足（既非阻塞也非孤立）：
abs（Pi,Rj）+
其中：
Wj表示j类资源的总数，（Pi,Rj）表示进程Pi申请j类资源的数量，（Rj,pk）表示分配给进程Pk的j类资源数。
简化操作：
①释放pi所占有的资源，即去掉它所有的请求边和分配边使其成为一个孤立结点。
②重复执行前两步，直到找不到满足条件的进程结点为止。
（6）死锁定理
系统状态S为死锁状态的充分条件，当且仅当S状态的系统资源分配图是不可完全简化的。
（至少有一个进程结点不能简化为孤立结点。
）该充分条件被称为死锁定理。
3.文件的多级目录结构（文件的物理结构、文件控制块、索引节点等）
文件物理结构
（1）概念
是指文件在外存上的存储结构，也称文件存储结构。
文件的物理结构决定了文件信息在存储设备上的存放位置。
（2）物理结构的类型
连续文件串联文件（链接文件）索引文件hash文件
文件控制块
（1）概念
是文件存在的标志，为提高查找速度，通常把FCB集中起来组织成文件目录（目录文件）。
目录项分两种：
子目录和文件的FCB。
一个文件由FCB和文件体（文件内容）两部分组成。
FCB是操文件系统为每个文件建立的唯一管理数据结构，FCB主要包括下列信息：
Ø文件标识符和控制信息：
文件名、用户名、存取权限、文件类型和文件口令等
Ø逻辑结构信息：
记录类型、记录个数和记录长度等
Ø物理结构信息：
设备号、文件物理结构类型、文件索引位置等
Ø使用信息：
共享进程数、文件最大长度、当前大小和修改情况等
Ø管理信息：
文件的建立日期、访问日期和保留期限等
（2）文件目录
一个文件系统中所有FCB的有序集合称为文件目录。
一个FCB就是一个文件目录项。
一个文件目录也被看作是一个文件，称为目录文件。
（3）索引结点（i结点）
是由除文件名外的其他文件描述信息所构成的一种数据结构。
为什么要引入索引结点？
①文件目录占用大量的盘块，检索时间长
②在检索目录文件过程中只用到文件名
种类
①磁盘索引结点
存放在外存上的索引结点。
基本信息包括：
文件主标识符、文件类型、文件存取权限、文件物理地址（磁盘上的地址）、文件长度、和文件存取时间等信息。
②内存索引结点
存放在内存上的索引结点。
内存索引结点包含磁盘索引接点的全部信息，并增加内存索引结点编号、状态、访问计数、文件所属的逻辑设备号和链接指针等信息。
（4）文件的目录结构
①单级目录结构
整个文件系统只建立一张目录表，每个文件在目录表中占有一目录项。
缺点：
Ø查找速度慢
Ø不允许重名
Ø不方便实现文件共享
②两级目录结构
在系统中建立一个主文件目录MFD，同时还为每个用户建立一用户文件目录UFD。
优点：
Ø解决了文件的重名问题和文件共享问题----用户名|文件名
Ø提高了目录检索的速度，降低查找时间
缺点：
增加了系统开销
③树型目录结构（多级）
在两极目录的基础上，允许用户创建自己的子目录，子目录创建自己的子目录，依次类推。
优点：
层次结构清晰，便于管理和保护；有利于文件分类；解决了文件的重名问题；提高了文件的检索速度；能进行存取权限的控制
缺点：
查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响存取速度。
4.磁盘调度（磁盘调度方法：
FCFS、SSTF，SCAN）
（1）先来先服务FCFS
根据进程请求访问磁盘的先后次序进行调度。
缺点：
平均寻道时间长
（2）最短寻道时间优先SSTF
选择与当前磁头所在的磁道距离最近的磁盘访问请求服务。
缺点：
出现“饥饿”现象。
（3）扫描（SCAN）算法（电梯调度算法）
首先考虑磁盘请求的磁头移动方向，在方向一致的情况下选择与当前磁头最近的磁盘请求服务。
若同方向没有请求，磁头转向反方向移动。
寻道时间Ts（启动磁臂时间s+磁头移动时间）Ts=m×n+s（移动n条磁道）
旋转延迟时间Tr=1\2r传输时间Tt=b\Rn
其中，b为传输的字节数，N为一条磁道上的字节数，r为磁盘每秒的转数。
5.虚拟设备、缓冲技术、SPOOLING系统
虚拟设备
操作系统使用共享设备来模拟独占设备的操作，经过操作系统虚拟技术处理后的设备称为虚拟设备。
在虚拟设备环境中，一个独占设备可以允许两个或两个以上的进程并行使用，并且每个进程都感觉在独占使用该设备。
缓冲技术
（1）为什么要引入缓冲技术
Ø缓和CPU和I/O设备之间速度不匹配的矛盾
Ø减少对CPU的中断次数。
Ø提高CPU和I/O设备之间的并行性
（2）缓冲的种类
单缓冲双缓冲循环缓冲缓冲池
SPOOLing系统
SPOOLing技术是实现虚拟设备以提高独占设备利用率的技术，也是一种以空间换时间的技术。
SPOOLing技术是在批处理操作系统时代引入的，即假脱机输入输出技术。
把这种技术实质就是对输入／输出数据成批处理。
（1）概念
SPOOLing技术是指在联机情况实现的同时外围操作，也称假脱机操作。
它通过共享设备来模拟独占设备的动作，使独占设备成为共享设备，也称为虚拟设备技术。
（2）SPOOLing技术实现原理
SPOOLing输入————作业预输入（输入机输入井）
SPOOLing输出————作业缓输出（输出井输出机）
由SPOOLing程序控制通道完成
（3）SPOOLing系统的组成
①输入井和输出井（外存：
暂存I/O设备传送的数据）
②输入缓冲区和输出缓冲区（内存：
匹配CPU与磁盘之间速度不匹配的矛盾）
③输入进程和输出进程（假脱机进程）
（4）SPOOLing系统的优点与缺点
优点：
①提高了I/O速度。
用户程序对慢速独占设备的独占时间大大缩短了，提高了慢速独占设备的利用率；
②用户程序本身的执行时间大大缩短了,提高了系统吞吐量和资源的利用率。
③使独占设备成为共享设备，实现了虚拟设备的功能。
缺点：
必须有高速、大容量和可随机存取的外存的支持。
综合应用题
1.多道系统、作业调度、进程调度、抢占式调度、非抢占式调度、周转时间、带权周转时间
（1）概念
作业调度：
是指按一定的作业调度算法，从外存的后备作业队列中选择若干个作业调入主存的过程。
进程调度：
按一定的进程调度算法，从已在内存的进程中选择一个进程并把CPU分配给它的过程。
作业周转时间：
从作业提交进入系统到结束退出系统所经历的一段时间。
平均周转时间：
多道作业周转时间的平均值。
系统吞吐量（吞吐率）：
单位时间系统所完成的总工作量（一般用作业数表示）。
（2）调度可分为三个层次：
作业调度：
也称高级调度或长期调度，决定每次接收多少个作业和接纳哪些作业的问题。
交换调度：
主要负责内外存上的进程交换。
一般通过“挂起”和“解挂”的方法来实现，也称“中期调度”。
进程/线程调度：
将处理器分配给一个或多个进程/线程的调度方法，也称“低级调度”和“短期调度”和“处理器调度”。
带权周转时间=周转时间/运行时间
例1：
先来先服务调度（非抢占）
执行次序
提交时刻
运行时间
等待时间
开始时刻
完成时刻
周转时间
带权周转时间
1
8.0
1.0
0
2
8.5
0.5
0.5
3
9.0
0.2
0.5
4
9.1
0.1
0.6
作业平均周转时间
作业平均带权周转时间
在一个单道批处理系统中，一组作业的提交时刻和运行时间如下表所示，请计算其平均周转时间T和平均带权周转时间W。
作业
提交时刻
运行时间
1
8.0
1.0
2
8.5
0.5
3
9.0
0.2
4
9.1
0.1
例2：
若采用抢占的高优先级调度算法，进程的调度次序是什么？
（假定优先数越小的作业，优先权越高。
）
作业
提交时刻
运行时间
时间：
8.08.59.09.19.29.39.8
作业：
123
（2）43（4）1（3）
（1）
优先数
1
8.0
1.0
3
2
8.5
0.5
1
3
9.0
0.2
2
4
9.1
0.1
1
例3：
短作业优先调度（短作业优先调度算法产生的平均周转时间短，系统吞吐量大。
非抢占）
作业
提交时刻
执行次序
提交
时刻
运行
时间
开始
时刻
完成时刻
周转时间
带权周转时间
1
8.0
1.0
3
9.0
0.2
4
9.1
0.1
2
8.5
0.5
作业平均周转时间
作业平均带权周转时间
运行时间
1
8.0
1.0
2
8.5
0.5
3
9.0
0.2
4
9.1
0.1
例4：
最短剩余时间优先调度（最短作业优先调度算法产生的平均周转时间最短，系统吞吐量最大。
抢占式）
作业
提交时刻
执行次序
提交
时刻
运行
时间
开始
时刻
完成时刻
周转时间
带权周转时间
1
8.0
1.0
3
9.0
0.2
4
9.1
0.1
2
8.5
0.3
作业平均周转时间
作业平均带权周转时间
运行时间
1
8.0
1.0
2
8.5
0.3
3
9.0
0.2
4
9.1
0.1
例5：
时间片轮转调度算法（是一种基于时间片的抢占式调度算法。
）
假定系统规定的时间片大小为0.3，不考虑切换开销。
作业提交情况如下表所示：
作业
提交时刻
执行次序
提交时刻
运行时间
运行及
完成时刻
周转
时间
带权周转时间
1
8.0
1.0
2
8.0
0.5
3
8.0
0.2
4
8.0
0.1
作业平均周转时间
作业平均带权周转时间
运行时间
1
8.0
1.0
2
8.1
0.5
3
8.2
0.2
4
8.3
0.1
例6：
高响应比调度（非抢占）
响应比Rp=等待时间+要求服务时间=响应时间
要求服务时间要求服务时间
作业
提交时刻
执行次序
提交时刻
运行时间
等待时间
开始时刻
完成时刻
周转时间
带权周转时间
1
8.0
1.0
2
8.5
0.5
3
9.0
0.2
4
9.1
0.1
作业平均周转时间
作业平均带权周转时间
运行时间
1
8.0
1.0
2
8.5
0.5
3
9.0
0.2
4
9.1
0.1
eg1：
执行次序
提交
时刻
运行
时间
优先数
运行及
完成时刻
周转
时间
带权周转时间
A
10:
00
40分钟
5
B
10:
20
30分钟
3
C
10:
30
50分钟
4
D
10:
50
20分钟
6
作业平均周转时间
作业平均带权周转时间
在一个具有两道作业的批处理系统中，作业调度采用短作业优先的调度算法，进程调度采用优先数为基础的抢占式调度算法（作业优先数即为进程优先数，优先数越小优先权越高），忽略进程切换和调度开销。
问题：
根据下表求它们的平均周转时间。
作业名
到达时间
运行时间
优先数
A
10：
00
40分钟
5
B
10：
20
30分钟
3
C
10：
30
50分钟
4
D
10：
50
20分钟
6
eg2:
在某多道程序系统中，用户当前可使用的系统资源：
内存空间100K，磁带机2台，打印机1台。
系统采用可变式分区分配方式管理内存，对磁带机和打印机采用静态分配方式，并假设输入输出操作的时间忽略不计。
假设作业调度采用先来先服务算法，内存分配采用首次适应算法且不准移动已在内存中的作业，进程调度采用短作业优先的调度算法。
作业序列情况如下表。
作业号
提交时间
运行时间
内存需求
申请磁带机
打印机
1
8：
00
30分钟
15K
1
1
2
8：
20
10分钟
30K
0
1
3
8：
20
20分钟
60K
1
0
4
8：
30
20分钟
20K
1
0
5
8：
35
15分钟
10K
1
1
问题：
（1）求作业调度的次序，并给出每道作业进驻内存的时刻（5分）。
（2）计算每道作业的周转时间（5分）。
解：
（1）（5分）
作业调度的顺序：
1→3→4→2→5
进驻内存的时刻分别为：
8：
00，8：
20，8：
30，
8：
50，9：
00……（5分）
（2）（5分）
作业的周转时间=作业的完成时间-作业到达系统的时间。
每道作业的周转时间如下：
1号作业：
30（分钟）2号作业：
40（分钟）3号作业：
30（分钟）4号作业：
65（分钟）5号作业：
40（分钟）
2.虚拟页式存储器管理系统（页表、快表、虚地址、物理地址、快表命中、页表命中、页面淘汰算法（LRU、CLOCK），驻留集、置换策略、抖动、缺页中断）
（1）页表：
放在系统空间的页表区，存储逻辑页与物理页帧之间的对应关系。
每个进程的PCB表中有一个指向页表的指针，即每一进程拥有一张页表。
有效地址结构：
逻辑地址=p（页号）*页面大小+d（页内位移）物理地址=f（页帧号））*页面大小+d（同上）
p=线性逻辑地址/页面大小；d=线性逻辑地址-p*页面大小。
例如：
页面的大小为1KB，求逻辑地址4101的页号和页内位移。
1514
1312
1110
98
66
54
32
10
00
01
00
00
00
00
01
01
得到页号p=4，页内位移d=5
进程被调度占用CPU时，进程页表始址被装入页表地址寄存器。
例如：
有一个32位的分页存储器管理系统，页面的大小规定为1KB，每个页表项占4个字节，求页表所占的最大内存空间？
32位计算机系统的逻辑地址空间应是232，页表长度（页表项的个数）为：
232/210=222
页表所占的内存空间：
222×22=224个字节，即16MB。
（2）快表：
由一组高速缓冲寄存器组成，用来存放当前访问过的页表项，以减少地址转换过程中的时间花费。
快表的表目结构：
（3）命中率：
选用8-12项组成的联想存储器，并采用适当的替换策略，在联想存储器中匹配成功的可能性可达80-90%。
（4）等效访问时间：
设访问主存时间为750ns，搜索联想存储器的时间为50ns，若联想存储器的命中率为80%，则一次访问主存的平均时间为（假设先查联想存储器再查页表）：
80%*（750+50）+20%*（750+50+750）=950ns
升级会员 