郑州大学操作系统期末考试重点整理.docx
《郑州大学操作系统期末考试重点整理.docx》由会员分享，可在线阅读，更多相关《郑州大学操作系统期末考试重点整理.docx（15页珍藏版）》请在冰点文库上搜索。
郑州大学操作系统期末考试重点整理
操作系统是管理系统资源、控制程序执行、改善人机界面、提供各种服务、合理组织计算机工作流程和为用户有效使用计算机提供良好运行环境的一种系统软件。
资源管理1资源复用（空分复用共享,,时分复用共享）2资源虚化3资源抽象4组合使用抽象和虚化技术
.操作系统中的基础抽象——进程、虚存和文件
（1）进程抽象
（2）虚存抽象（3）文件抽象（4）其他资源抽象
操作系统的作用:
（1）OS作为用户接口和公共服务程序：
（2）OS作为扩展计算机或者虚拟计算机
（2）OS作为资源的管理者和控制者（4）OS作为程序执行的控制着和管理者
从资源管理的角度，看操作系统具有六项主要功能：
处理器管理，存储管理，设备管理，文件管理，网络与通信管理，用户接口
操作系统的主要特性：
并发性，共享性，异步性
并发性：
指两个或两个以上事件或活动在同一时间间隔内发生。
并行性：
指两个或两个以上事件或活动在同一时刻发生。
关系：
并行活动一定是并发的，反之并发活动未必是并行的，并行性是并发性的特例，并发性是并行性的扩展。
共享性：
指操作系统中的资源可被多个并发执行的进程共同使用，而不是被其中某一个程序所独占。
1，透明资源共享：
必须妥善解决的问题有资源隔离，
授权访问2，显式资源共享：
独占资源是指同一时间段内只允许一个进程访问的资源
异步性：
由计算机系统中的资源有限而进程众多，每个进程的执行并非连贯的，而是以“走走停停”的方式向前推进。
多道程序设计是指允许多个程序同时进入一个计算机系统的主存储器并启动进行交替计算的方法。
从宏观上看，多道程序并发运行，它们都处于运行过程中，但都未运行结束。
从微观上看，多道程序的执行是串行的，各道程序轮流占用CPU，交替地执行。
好处：
1，提高CPU、主存和设备的利用率，2，提高系统的吞吐率，是单位时间内完成的作业数增加。
3充分发挥计算机系统部件的并行性
操作系统可分为三种基本类型：
批处理操作系统分时操作系统.实时操作系统
通用操作系统：
如果某个操作系统兼具批处理、分时、实时处理的全部或两种功能，则为通用OS
操作系统为用户提供两种调用其服务和功能的接口:
程序接口：
允许运行程序调用操作系统的服务和功能。
许多操作系统的程序接口由一组系统调用（SystemCall））组成，用户程序使用“系统调用”就可获得操作系统的底层服务，使用或访问系统的各种软硬件资源。
操作接口：
操作系统为用户提供的操作控制计算机工作和提供服务手段的集合，通常有操作控制命令、图形操作界面、以及批处理系统提供的作业控制语言等实现手段。
内核是一组程序模块，作为可信软件来支持进程并发执行的基本功能和基本操作，通常驻留在内核空间，运行于核心态，具有访问硬件设备和所有主存空间的权限，是仅有的能执行特权指令的程序。
分类可分为微内核和单内核两种类型。
功能1）资源抽象2）资源分配3）资源共享。
属性1）内核是由中断驱动的2）内核的执行是连续的3）内核在屏蔽中断状态下执行4）内核可以使用特权指令。
从操作系统的运行方式来看，可分成：
独立运行的内核模型、在应用进程内执行的模型和作为独立进程运行的模型。
处理器流可以分作以下四类：
单指令流单数据流（SISD）：
传统的计算机系统。
单指令流多数据流（SIMD）和多指令流多数据流（MIMD）都属于并行计算机！
多指令流单数据流（MISD）：
在研究中
处理器现场：
处理器包括一组寄存器，用于存放数据、变量和中间结果，这组寄存器所存储的信息与程序的执行有很大关系，构成了处理器现场。
特权指令是指只能提供给操作系统的核心程序使用的指令，如启动I/O设备、设置时钟、控制中断屏蔽位、清内存、建立存储键，加载PSW（程序状态字）等。
非特权指令：
指供应用程序使用的、权限较低的指令。
处理器状态分类：
核心状态和用户状态。
核心态具体的权限有：
1，CPUU运行可信软件2，硬件执行全部机器指令3，可以访问所有内存单元和系统资源4，具体改变处理器状态的能力。
用户态具有的权限有：
1，CPU运行非可信软件2，程序无法执行特权指令3，访问权限仅限于当前进程的地址空间4，不具有改变处理器状态的能力
处理器状态之间的转换：
（1）用户状态向核心状态的转换：
一是程序请求操作系统服务，执行一条系统调用；二是程序运行时，产生了一个中断（或者异常）事件，运行程序被中断，让中断处理程序工作。
这两种情况都是通过中断机构发生的。
中断（异常）是用户态到核心态转换的唯一途径。
（2）核心状态向用户状态的转换：
每台计算机通常会提供一条特权指令称作加载程序状态字LPSW（LoadPSW），用来实现操作系统向用户程序的转换。
加载程序状态字指令的作用：
把哪个程序的程序状态字加载到程序状态字寄存器中，就意味着该程序获得CPU控制权执行。
中断是指程序执行过程中，遇到急需处理的某个事件时，暂时中止CPU上现行程序的运行，转而执行相应的事件处理程序执行的过程，待处理完毕之后再返回断点（继续执行）或者调度其他程序执行。
中断源是引起中断的事件。
中断装置是发现中断源并产生中断的硬件。
中断源分类：
1.从中断事件的性质和激活的手段来分，可以分成两类：
强迫性中断事件和自愿性中断事件。
2按照中断信号的来源和实现手段来分：
可分为硬中断和软中断两类。
硬中断可以分为外中断和内中断。
中断/异常响应需要顺序执行的四个步骤：
发现中断源，保护现场，转向中断/异常事件的处理程序，恢复现场。
进程（process）是一个可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，也是操作系统进行资源分配和保护的基本单位。
进程的属性（进程与程序比较）：
（1）结构性
（2）共享性
（3）动态性（4）独立性（5）制约性（6）并发性
三态模型：
运行态，就绪态，等待态
五态模型：
新建态，终止态，运行态，就绪态，等待态
进程映像的组成
进程组成主要包括：
进程控制块，进程程序块，进程核心栈，进程数据块
进程控制块三类信息：
标识信息、现场信息、控制信息
允许发生进程上下文切换的四种情况：
（1）当进程进入等待态时；
（2）当进程完成其系统调用返回用户态，但不是最有资格获得CPU时；（3）当内核完成中断处理，进程返回用户态但不是最有资格获得CPU时；（4）当进程执行结束时。
模式切换和进程切换的联系与区别：
1，模式切换不一定会引起进程状态的转换，也不一定引起进程切换。
2，在完成系统调用服务或者中断处理之后，可通过模式切换来恢复被中断进程的运行。
进程控制原语：
1.进程创建2.进程的撤销3.进程的阻塞和唤醒4.进程的挂起和激活
线程的实现分三类：
1，用户级线程2内核级线程3混合式线程
处理器调度可分为三个级别：
高级调度、中级调度和低级调度
作业和进程的关系：
•作业是任务实体，进程是完成任务的执行实体；没有作业任务，进程无事可干，没有进程，作业任务没法完成。
•作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统
资源竞争产生两个控制问题：
一个是死锁（Deadlock）问题，就是一组进程如果都获得了部分资源，还想要得到其他进程所占用的资源，最终所有进程都将陷入死锁。
一个是饥饿（Starvation）问题，是指一个进程由于其它进程总是优先于它而被无限期拖延。
既要解决饥饿问题，又要解决死锁问题。
解决饥饿问题的最简单策略是FCFS资源分配策略。
临界区的调度原则:
一次至多允许一个进程进入临界区内；一个进程不能无限地停留在临界区内；一个进程不能无限地等待进入临界区；
管程：
属性共享性：
安全性：
互斥性：
进程通信分类：
1）信号（signal）通信机制；2）管道（pipeline）通信机制；3）消息传递（messagepassing）通信机制；4）信号量（semaphore）通信机制5）共享主存（sharedmemory）通信机制
死锁的定义:
如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，而无限期陷入僵持的局面称为（这一组进程）发生了死锁。
产生死锁的因素:
系统拥有的资源数量。
与资源分配策略。
进程对资源的使用。
并发进程的推进顺序。
产生死锁的四个必要条件：
互斥条件：
进程互斥使用资源。
占有和等待条件（部分分配条件）：
进程在请求资源得不到满足而等待时，不释放已占有资源。
不剥夺条件：
已占有的资源只能由属主释放，不允许其他进程强制剥夺。
循环等待条件（环路条件）：
存在一组循环等待链，其中每一个进程都在链中等待下一个进程所持有的资源，造成种族进程处于永远等待状态。
文件系统是操作系统中负责存取和管理信息的模块，文件不但反映了用户概念中的逻辑结构，而且和存放它的辅助存储器的存储结构紧密相关。
一个文件必须从逻辑文件和物理文件两个侧面来观察它。
逻辑结构，即记录及其逻辑关系，数据独立于物理环境；
物理结构，数据被文件系统按照某种规则排列和存放到物理存储介质上。
顺序存取:
按记录顺序进行读/写操作的存取方法.主要用于磁带文件以及磁盘上的顺序文件.
直接存取:
以任意次序直接读写某个记录.用户提供相对块号给操作系统,绝对块号由系统换算得到.
索引存取:
文件专门有一个按记录关键字有序的索引表,用户通过查找索引表定位并读出记录.
文件系统给每个文件建立唯一的管理数据结构，即文件控制块（FCB），也叫文件目录项。
文件目录的基本功能是将文件名转变成此文件信息在磁盘上的物理位置。
为了加快文件的查找速度，通常把ＦＣＢ集中起来进行管理，组成文件目录。
目录中的文件名和管理信息分开，后者单独组成数据结构，称索引节点（i-node）
块是存储介质上连续信息所组成的一个区域，也叫做物理记录。
块是主存储器和辅助存储设备进行信息交换的物理单位，每次总是交换一块或整数块信息
文件的逻辑结构分两种形式：
流式文件，记录式文件
流式文件指文件内的数据不再组成记录，只是依次的一串信息集合，可以看成是只有一个记录的记录式文件
记录式文件是一种有结构的文件,包含若干逻辑记录，逻辑记录是文件中按信息在逻辑上的独立含意划分的信息单位。
顺序文件（连续文件）一个文件中逻辑上连续的信息存放到存储介质的依次相邻的块上便形成顺序文件。
连接文件使用连接字，又叫指针来表示文件中各个记录之间的关系.第一块文件信息的物理地址由文件目录给出,每一块的连接字指出文件下一个物理块位置
直接文件（哈希文件）记录的关键字与其地址间可通过某种方式建立对应关系，利用这种关系实现存取的文件叫直接文件。
索引文件的优点:
不要求物理块连续,便于直接存取,便于文件的增、删、改。
缺点:
增加了索引表的空间开销和查找时间.
文件的静态共享：
允许一个文件同时属于多个目录，但实际上文件仅有一处物理存储，这种文件在物理上一处存储，从多个目录可到达该文件的结构称为文件链接。
要实现静态链接，只要不同目录的索引结点i-node号，指定为同一文件的索引结点即可。
文件的动态共享：
是系统中不同的用户进程或同一用户的不同进程并发地访问同一文件。
共享关系只有当用户进程存在时才可能出现，一旦用户的进程消亡，其共享关系也就自动消失。
外围设备分为两类:
存储型设备和输入输出型设备.
I/O系统：
I/O设备及其接口线路、控制部件、通道和管理软件的总称。
I/O设备可以划分为输入型、输出型和存储型外围设备三类。
按照I/O信息交换的单位,I/O设备可分为字符设备和块设备。
存储型外围设备可以划分为顺序存取存储设备和直接存取存储设备。
顺序存取存储设备严格依赖信息的物理位置进行定位和读写，如磁带机。
直接存取存储设备的特点是存取任何一个物理块所需的时间几乎不依赖于此信息的位置，如磁盘。
I/O设备的4种控制方式分类：
轮询方式：
轮询方式又称程序直接控制方式，特点：
CPU不停测试设备状态，直到设备准备就绪，开始传输数据；中断方式：
启动I/O后，不必查询I/O是否就绪，继续执行现行程序。
特点：
不需要CPU做忙式测试，直到设备准备就绪之后产生中断。
DMA方式：
I/O设备能直接与主存交换数据而不占用CPU,其利用率还可提高。
特点：
负责数据的交换，CPU不必参与；从设备读数据，存入缓冲寄存器，这个过程与CPU无关；与内存交换数据时，是一次交换一块数据；与内存进行数据交换时，需要抢占内存总线（周期窃取），此时CPU必须等待。
通道方式：
为获得CPU和外围设备间更高的并行工作能力,引入了自成独立体系的通道结构。
特点：
通道负责管理设备与内存之间的数据传送的一切工作；数据传输完毕后，产生中断，CPU执行中断处理；数据传输中如果出错，产生中断，CPU执行中断处理。
I/O设备包括一个机械部件和一个电子部件。
电子部件称为设备控制器或适配器，机械部件则是设备本身。
操作系统基本上与控制器打交道，而非设备本身。
I/O软件总体设计目标:
高效率。
通用性。
I/O软件组织成四个层次:
I/O中断处理程序。
设备驱动程序。
与设备无关的操作系统I/O软件。
用户层I/O软件.
笼统地说，设备驱动程序的功能是从独立于设备的软件中接收并执行I/O请求。
设备驱动程序主要包括三部分功能：
1设备初始化2执行设备驱动例程3执行中断处理例程。
SPOOLing又称为假脱机操作.Spooling技术就是利用一类物理设备模拟另一类物理设备的技术,是使独占使用的设备变成可共享设备的技术.
为什么需要缓冲技术？
改善中央处理器与外围设备之间速度不匹配的矛盾，协调逻辑记录大小与物理记录大小不一致，提高CPU和I/O设备的并行性。
提高磁盘I/O速度的方法:
提前读:
在读当前块的同时，将下一个盘块中的数据也读入缓冲区。
延迟写:
本应写回磁盘的缓冲区中的数据不久之后可能还会再被访问，因而不立即将其写回磁盘。
虚拟盘:
利用内存空间仿真磁盘，又称为RAM盘。
虚拟盘中的数据在掉电或系统重启动以及发生故障时会丢失。
设备独立性带来的好处:
用户与物理的外围设备无关，系统增减或变更外围设备时程序不必修改；易于对付输入输出设备的故障。
为了存放从输入设备输入的信息以及作业执行的结果,系统在磁盘上开辟两个大的存储空间,称为井.
存储器的层次：
寄存器、高速缓存、主存储器，磁盘，磁带。
内存是程序运行的主要场所，是进程映像（进程实体）存在的主要位置。
把程序和数据的逻辑地址转换为物理地址的工作称为地址转换或重定位.一种方式是在程序装入时根据程序所装入的内存位置由装入程序依据重定位信息一次性将程序中所有的逻辑地址都转变为物理地址，称为静态重定位，不允许程序在内存中移动位置。
另一种方式是在程序执行过程中，地址转换工作穿插在指令执行的过程中，每执行一条指令，CPU对指令中涉及的逻辑地址进行转换，称为动态重定位，允许程序在内存中移动位置。
动态重定位必须借助于硬件的地址转换机构实现。
页框：
物理地址分成大小相等的许多区域，每个区域叫做一块（或者一个页框pageframe）。
页面：
逻辑地址分成大小相等的区域，每个区域的大小与块的大小相等，叫做一个页面（page）。
逻辑地址形式：
分页式存储器的逻辑地址由两部分组成：
页号和单元号（页内位移）。
页表：
操作系统需为每个作业建立一张页表,该表登记该作业的页号—物理块号对应信息,系统通过页表可以准确访问内存中属于一个作业的所有页面.所以页表实际上用于完成地址变换.
虚拟存储器的定义：
在具有层次结构存储器的计算机系统中，采用自动实现部分装入和部分对换功能，为用户提供一个比物理内存容量大得多的，可寻址的一种“内存储器”。
假定作业p共计n页，系统分配给它的主存块只有m块（１≤m≤n）。
如果作业p在运行中成功的访问次数为s，不成功的访问次数为F，则总的访问次数Ａ为：
A=S+F又定义：
f=F/A称f为缺页中断率。
影响缺页中断率f的因素有：
1）主存页框数。
2）页面大小。
3）页面替换算法。
4）程序特性。
最佳页面算法（OPT）、先进先出页面淘汰算法（FIFO）、最近最久未使用页面淘汰算法（LRU）、
外围设备分为两类:
存储型设备和输入输出型设备。
设备管理具有以下功能1外围设备中断处理。
2缓冲区管理。
3外围设备的分配 4外围设备驱动调度。
5虚拟设备及其实现
存储型外围设备可以划分为顺序存取存储设备和直接存取存储设备。
顺序存取存储设备严格依赖信息的物理位置进行定位和读写，如磁带机直接存取存储设备的特点是存取任何一个物理块所需的时间几乎不依赖于此信息的位置，如磁盘。
有三个并发进程：
R负责从输入设备读入信息块，M负责对信息块加工处理；P负责打印输出信息块。
今提供；l）一个缓冲区，可放置K个信息块；2）二个缓冲区，每个可放置K个信息块；试用信号量和P、V操作写出三个进程正确工作的流程。
答：
1一个缓冲区：
cobegin
Semaphoresread,smanager,sprint;
itema[K];intrr,rm,rp;
itemx;
sread=k;smanager=0;sprint=0;
rr=rm=rp=0;
processPR（）
{while（true）
{P（sread）;
a[rr]=x;
rr=（rr+1）%K;
V（smanager）;}}
processPM（）
{while（true）
{P（smanager）;
x=a[rm];
rr=（rr+1）%K;
V（sprint）;}}
processPP（）
{while（true）
{P（sprint）;
x=a[rp];
rr=（rr+1）%K;
V（sread）;}}
Coend
（2）两个缓冲区：
semaphoreswrite1,sread1,swrite2,sread2;
Swrite1=swrite2=1;sread1=sread2=0;
itemA1[k],A2[k];read1=write1=read2=write2=0;
cobegin
processPR
{while（true）
{P（swrite1）;
A1[write1]=x;
write1=（write1+1）%K;
V（sread1）;}}
processPM
{while（true）
{P（sread1）;
x=A1[read1];
read1=（read1+1）%K;
V（swrite1）;
P（swrite2）
A2[write2]=x;
write2=（write+1）%K;
V（sread2）;}}
processPP
{while（true）
{P（sread2）;
x=A2[read2];
read2=（read2+1）%K;
V（swrite2）;}}
coend
设公共汽车上，司机和售票员的活动分别如下：
司机的活动：
启动车辆：
正常行车；到站停车。
售票员的活动：
关车门；售票；开车门。
在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？
用信号量和P、V操作实现它们的同步。
答：
在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：
售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开门让乘客上下车。
因此，司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。
应设置两个信号量：
S1、S2;S1表示是否允许司机启动汽车（其初值为0）;S2表示是否允许售票员开门（其初值为0）。
用P、v原语描述如下：
varS1,S2:
semaphore;
S1=0；S2=0；
cobegin
{driver（）;
busman（）;}
coend
driver（）
begin
while
（1）{P（S1）
启动车辆；正常行车；到站停车；
V（S2）;}
end
busman（）
begin
while
（1）{关车门；
V（51）
售票;
P（S2）
开车门；
上下乘客；}
end
1条公路两次横跨运河，两个运河桥相距100米，均带有闸门，以供船只通过运河桥。
运河和公路的交通均是单方向的。
运河上的运输由驳船担负。
在一驳船接近吊桥A时就拉汽笛警告，若桥上无车辆，吊桥就吊起，直到驳船尾P通过此桥为止。
对吊桥B也按同样次序处理。
一般典型的驳船长度为200米，当它在河上航行时是否会产生死锁？
若会，说明理由，请提出一个防止死锁的办法，并用信号量来实现驳船的同步。
答：
当汽车或驳船未同时到达桥A时，以任何次序前进不会产生死锁。
但假设汽车驶过了桥A，它在继续前进，并且在驶过桥B之前，此时有驳船并快速地通过了桥A，驳船头到达桥B，这时会发生死锁。
因为若吊起吊桥B让驳船通过，则汽车无法通过桥B；若不吊起吊桥B让汽车通过，则驳船无法通过桥B。
可用两个信号量同步车、船通过两座桥的动作。
varSa,Sb:
semaphore;
Sa:
=Sb:
=1;
cobegin
{process驳船
begin
P（Sa）;
P（Sb）;
船过桥A、B;
V（Sa）;
V（Sb）;
end
process汽车
begin
P（Sa）;
P（Sb）;
车过桥A、B;
V（Sa）;
V（Sb）;
end}
coend
假定磁盘有200个柱面，编号O-199，当前存取臂的位置在143号柱面上，并刚刚完成了125号柱面的服务请求，如果请求队列的先后顺序是：
86,147,91,177,94,150,102,175,130；试问：
为完成上述请求，下列算法存取臂移动的总量是多少？
并算出存取臂移动的顺序。
（1）先来先服务算法FCFS;
（2）最短查找时间优先算法SSTF:
（3）扫描算法SCAN。
（4）电梯调度。
答：
（l）先来先服务算法FCFS为565，依次为143-86-147-91-177-94-150-102-175-130。
（2）最短查找时间优先算法SSTF为162，依次为143-147-150-130-102-94-91-86-175-177。
（3）扫描算法SCAN为169，依次为143-147-150-175-177-199-130-102-94-91-86。
（4）电梯调度为125，依次为143-147-150-175-177-130-102-94-91-86。
先来先服务算法FCFS策略：
按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。
这是一种非剥夺式算法。
最短作业优先算法SJF：
以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。
这是一种非剥夺式调度算法
例：
•SJF的作业调度顺序为作业2、4、1、3，
平均作业周转时间T=（4+12+21+31）/4=17
平均带权作业周转时间W=（4/4+12/8+21/9+31/10）/4=1.98
•如果对它们施行FCFS调度算法，
平均作业周转时间T=（9+13+23+31）/4=19
平均带权作业周转时间W=（9/9+13/4+23/10+31/8）/
升级会员 