现代操作系统考试复习文档格式.docx
- 文档编号:6649331
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:48
- 大小:234.46KB
现代操作系统考试复习文档格式.docx
《现代操作系统考试复习文档格式.docx》由会员分享,可在线阅读,更多相关《现代操作系统考试复习文档格式.docx(48页珍藏版)》请在冰点文库上搜索。
宏内核的功能块之间的耦合度太高造成修改与维护的代价太高,宏内核因为是直接调用,所以效率是比较高的。
(三)3.进程概念Process-aprograminexecution
进程是OS中资源拥有的基本单位(unitofresourceownership)虚地址空间,内存及其他资源(I/O设备、文件等)进程管理:
进程控制块(PCB)进程的状态:
running,ready,wait,stopped,zombie进程间通讯代价大
(四)核心级线程以及用户级线程
4.线程:
程序的执行体anexecutionpathinaprocess,进程中的线程共享进程资源
核心级线程:
操作系统直接调度的线程是OS调度的基本单位线程阻塞不会导致整个进程的阻塞在多处理器环境下,内核可使线程在不同的处理器上运行,应用程序通过API调用核心线程管理例程(kernelthreadfacility)来管理;
需要进行模式切换
用户级线程:
由进程直接管理的线程
由应用程序自己通过线程库(threadlibrary)来管理:
线程创建、终止、线程间通信,线程调度与切换,OS感知不到ULT的存在,线程阻塞会导致整个进程的阻塞,在任何OS下都可以实现,无法利用多处理器纯线程管理的成本高
现在的操作系统:
多进程多线程方式,相对独立的执行体各自创建进程,同一个执行体中可以并发执行的功能设为线程
Linux中pthread创建的线程为核心级线程。
两进程的软件方法(如Peterson算法)信号量(以生产者/消费者问题为代表)
临界资源(criticalresource):
一次只能由一个进程访问的资源
临界区(criticalsection):
访问临界资源的代码段称为临界区(CS)
互斥(mutualexclusion)在一个时刻最多只有一个进程在临界区
同步(synchronization)协调需要访问临界资源的进程,否则会导致racecondition(竞争条件)
临界区问题解决方法正确性的准则
两个前提:
对处理器数及各进程的相对运行速度(不会是零速度)不应该有任何假设
进程在临界区停留的时间是有限的
三个必须:
互斥(mutualexclusion)
有空让进(progress),若没有进程在临界区,则应该让申请进入临界区的进程中的一个立即进入
有限等待(boundedwaiting),申请进入临界区的进程不会无止境的等待(即不会有饥饿现象)
Peterson算法:
算法直观,只能解决二个进程同步
考虑进程P0,一旦它设置flag[0]=true,则P1不能进入临界区。
如果P1已经进入临界区,那么flag[1]=true,P0被阻塞不能进入临界区。
另一方面,互相阻塞也避免了。
假设P0在while里被阻塞了,表示flag[1]为true且turn=1,则此时P1可以执行。
do{
flag[0]:
=true;
//希望进入
turn:
=1;
//给对方一次机会
whileflag[1]andturn=1do{nothing};
//如果对方先申请则等待
<
CS>
=false;
RS>
}while
(1)
信号量(semaphore,无忙等待)
❑OS提供的装置,用于进行进程/线程的同步与互斥
❑数据结构(s)
✓count:
integer;
>
=0表示可用资源数,<
0,其绝对值表示挂起进程数,初始化非负
✓queue:
listofprocess;
正在等待该类资源的进程
❑进程只能通过OS提供的wait和signal两个操作原语访问信号量
✓Wait(s):
等待资源
s.count=s.count–1;
ifs.count<
0thenbegin
placethisprocessins.queue;
blockthisprocess;
end;
✓Signal(s):
释放资源
s.count=s.count+1;
=0thenbegin
removeaprocessPfroms.queue;
placeprocessPonreadylist;
利用信号量解决CS问题实例:
生产者/消费者问题
信号量
✓full,初始化为0,表示缓冲区中可消费的资源数
✓mutex,初始化为1,用于对缓冲区的互斥操作
✓empty,初始化为缓冲区的长度N,表示缓冲区中空闲单元数
Producer:
repeat
produce;
wait(empty);
wait(mutex);
append;
signal(mutex);
signal(full);
forever
Consumer:
wait(full);
wait(mutex);
take;
signal(mutex);
signal(empty);
consume
例:
有n个进程(P1,P2,…,Pn)向容量为M的缓冲区写数据,每个进程一次写1个数据,当缓冲区写满时,另一个读进程Pr一次将M个数据全部读完,如此反复。
请用信号量解决这些进程的同步互斥问题。
答:
本题中需要定义下述变量和信号量:
data_typebuffer[M];
/*data_type对应于所需要的数据类型,如int、float等*/
intin=0;
/*用来指示下一个可存放数据的缓冲区*/
semaphoreempty=M;
/*对应空闲的缓冲区*/
semaphorefull=0;
/*对应缓冲区中的数据*/
semaphoremutex=1;
/*用来实现Pi进程对变量in的互斥访问*/
进程Pi可描述为:
Pi(){
while
(1){
向缓冲区buffer[in]中写数据;
in=(in+1)%M;
signal(full);
}}
进程Pr可描述为:
Pr(){
inti;
for(i=0;
i<
M;
i++)wait(full);
取出缓冲buffer[0]到buffer[M-1]中的数据;
signal(mutex);
i++)signal(empty);
有一个仓库,可以存放A和B两种产品,但要求:
(1)每次只能存入一种产品(A或B);
(2)-N<
A产品数量-B产品数量<
M。
其中,N和M是正整数。
试用信号量来同步产品A与产品B的入库过程。
本题中,首先需要设置一个初值为1的互斥信号量mutex,以保证每次只存入一种产品。
另外,为了保证“-N<
M”,还需设置信号量SA,表示仓库中目前可再存放的A产品的数量,其初值为M-1;
SB,表示目前还可再存放的B产品的数量,其初值为N-1。
A产品入库的过程可描述为:
B产品入库的过程可描述为:
while
(1){while
(1){
wait(SA);
/*还可放A产品?
*/wait(SB);
/*还可放B产品?
*/
将A产品放入仓库;
将B产品放入仓库;
signal(SB);
/*可放B产品数增1*/signal(SA);
/*可放A产品数增1*/
}
(六)10.死锁问题
死锁:
系统中存在一个进程集合,该集合中的每个进程都占用了一定数量的资源,并且在等待被集合中的其他进程占用的资源
死锁发生的四个必要条件:
Mutualexclusion:
互斥
Holdandwait:
保持等待,申请资源时拥有其他资源
Nopreemption:
非剥夺,进程占有的资源只能由进程自己释放,不会被别的进程剥夺
Circularwait:
循环等待(各类资源的资源数为1时一定死锁)
死锁预防:
间接预防:
阻止Mutualexclusion,Holdandwait及Nopreemption都满足直接预防:
阻止circularwait的发生。
有序申请法(对所有资源类别编号,进程申请资源按序进行);
资源预申请例:
哲学家就餐问题,筷子编号,先拿编号小的、再拿大的。
(有序申请)
死锁避免方法:
进程申请资源时,决定是否应该满足;
必须预先知道每个进程需要的各类资源数
Banker’salgorithm,银行家算法,基本思想,若新的状态是安全的(safe),则满足它
Safestate:
从此状态出发,存在某种执行顺序(安全序列,safesequence),可以使所有进程执行完毕。
安全状态只是暂时安全,如果以后资源分配不当,也会导致死锁;
不安全状态不一定就死锁。
图1安全,图2不安全.
(七)
11.进程调度
–进程的执行是CPUburst与I/Oburst交替的过程
–CPU约束进程:
大量时间作计算,少量I/O
–I/O约束进程:
大量的I/O,少量时间作计算
–衡量指标ResponseTime(响应时间)、TurnaroundTime(周转时间)、processorutilization、
fairness(公平性)、throughput(吞吐量)
调度模式:
–Non-preemptive(非剥夺方式)进程一旦被调度,则执行至结束或不能继续执行(如因为发起I/O操作而等待)
–Preemptive(剥夺方式)当一个新的进程到达时;
当有进程从阻塞变为就绪时;
进程从核心态返回到用户态时(如中断、系统调用返回时)
调度算法
FCFS(firstcomefirstserved)先来先服务,直至结束(nonpreemptive)
RR:
Roundrobin
�时间片轮转(timeslice,preemptive),时间片到时,将进程放入就绪队列的末尾,然后从队列头部取出一个进程运行,公平的调度策略,不会导致进程饥饿
Priorityscheduling:
基于优先级的调度
�存在问题:
饥饿-低优先级进程可能永远得不到执行
�解决办法:
老化(Aging)–随着时间的推移,进程的优先级可以提升(即进程的优先级可以是动态的)
分段、分页的基本概念与优缺点,虚拟存储中按需调页的基本思想
1.基本概念:
Relocation(重定位):
程序只有在执行时才能确定其在内存中的位置Protection(保护):
进程在未被允许时不能访问其他进程的地址空间Sharing(共享):
应该提供机制允许进程访问共享地址空间中的信息Logicaladdress(逻辑地址):
用户进程访问的地址,即虚地址Physicaladdress(物理地址):
物理存储器的地址
交换(swapping):
将进程从内存中换出到交换设备,下次执行时再换入。
早期技术,现在通过paging技术优化swapping(只换出/换入进程的一部分页面)
2.分区:
将内存划分为若干个分区,每个分区存放一个进程,以支持多道程序(multi-programming),
Fixedpartitioning:
固定大小的分区,分区内部会出现碎块(internalfragment)
Dynamicpartitioning:
动态分区,按照进程大小决定分区大小,不存在内部碎块,但有外部碎块(externalfragment),涉及放置算法(placementalgorithm):
firstfit,bestfit,nextfit
3.页式存储管理(由于进程的地址空间可能很大,因此页表也可能很大,导致管理代价大)为了更高效地管理内存,减少内部碎片和外部碎片,将内存划分为固定大小的页帧(frame),进程空间划分为同样大小的页(page),系统为进程分配物理存储器按页进行。
�逻辑地址是由page#+offset组成的1维线性地址
�装入进程时,按页进行
�每个进程一张页表,存储本进程中各页存放的位置(在内存中的frame号)
�OS维护一张free-framelist
�CPU提供分页机制的硬件支持:
�CPU无法将页表完全放在内部寄存器中,但提供页表高速缓存TLB,以实现对页表的快速存取。
�PTBR:
即页表基地址寄存器。
�CPU的页管理部件(MMU)实现从逻辑地址(page#+offset)到物理地址(frame#+offset)的变换
4.段式存储管理:
进程空间分为若干段,各段长度可不一致(用户以更自然的方式管理进程地址空间)
�类似于连续存储分配中的动态分区,但有区别:
进程是分段的,各段在内存中可以不连续
�逻辑地址是由seg#+offset组成的2维地址
�每个进程一张段表
�CPU提供分段机制的硬件支持:
�段表存储在内存中(线性地址空间),CPU提供段寄存器、段描述符寄存器等支持。
�CPU的段管理部件实现从逻辑地址(seg#+offset)到线性地址或物理地址的变换
5.段页式存储管理:
将分段和分页结合起来,充分利用两者的优势
逻辑地址先通过分段机制变换为线性地址,再通过分页机制变换为物理地址。
6.虚拟存储管理:
进程的虚地址空间(virtualaddressspace)
�由进程的逻辑地址组成的地址空间。
�虚地址空间可以远大于系统的物理内存。
�虚拟存储器(virtualmemory)逻辑地址访问的存储器页面装入策略:
决定何时将进程的逻辑页面装入内存
�Demandpaging(按需调页):
发生缺页时,才将页面装入。
�Prepaging(预取):
预先将某些页面装入内存。
7.页面替换策略:
OS分配给进程的物理内存不够用时,需要页替换(ppt47页)
Optimal:
最优化方法,选择将来最久不会被访问的页换出
�需要预先知道页访问序列
�不可能实现,只是作为一个评判标准
FIFO:
最先装入的被换出
LRU:
最久未使用的页被换出(基于locality现象,很有效)
Clockpolicy,时钟算法。
LRU算法不易实现,用时钟算法近似模拟
�每页设置一个referencebit,为1表示在时钟指针循环一周内被访问过;
�查找替换页:
指针扫描,若referencebit=1,置为0,否则该页就是替换对象。
Belady’sAnomaly(belady异态):
内存大,反而缺页率高
(九)文件系统与I/O
1.文件在磁盘上的组织形式:
连续,索引,链接多数使用索引法,连续会造成碎片
2.文件控制块(PCB)及目录的概念:
文件控制块:
为了实现对文件存取时的控制,文件对应的磁盘块位置,大小,文件属主等信息都在文件控制块中。
文件控制块中都没有标识文件名,文件系统是一颗树,目录的作用是让文件可以按类分散存放;
让系统可以按文件名来存取文件。
目录的信息中包含文件名和文件控制块。
3.unix中文件系统的磁盘布局:
文件系统是操作系统用于明确磁盘或分区上的文件的方法和数据结构;
即在磁盘上组织文件的方法。
大部分UNIX文件系统种类具有类似的通用结构,其核心概念是超级块superblock,i节点inode,数据块datablock,目录块directoryblock,和间接块indirectionblock。
超级块包括文件系统的总体信息,比如大小(其准确信息依赖文件系统)。
i节点包括除了名字外的一个文件的所有信息,名字与i节点数目一起存在目录中,目录条目包括文件名和文件的i节点数目。
i节点包括几个数据块的数目,用于存储文件的数据。
i节点中只有少量数据块数的空间,如果需要更多,会动态分配指向数据块的指针空间。
这些动态分配的块是间接块;
为了找到数据块,这名字指出它必须先找到间接块的号码。
4.磁盘的结构(硬盘的解释):
硬盘的内部是金属盘片,将圆形的盘片划分成若干个扇形区域,这就是扇区。
若干个扇区就组成整个盘片。
分扇区是逻辑化数据的需要,能更好的管理硬盘空间。
以盘片中心为圆心,把盘片分成若干个同心圆,那每一个划分圆的“线条”,就称为磁道。
硬盘内的盘片有两个面,都可以储存数据,而硬盘内的盘片往往不止一张,常见的有两张,那么,两张盘片中相同位置的磁道,就组成一个“柱面”,盘片中有多少个磁道,就有多少个柱面。
盘片两面都能存数据,要读取它,必须有磁头,所以,每一个面,都有一个磁头,一张盘片就有两个磁头。
以上就是硬盘的专业术语:
扇区、磁道、柱面、磁头的通俗解释。
硬盘的存储容量=磁头数×
磁道(柱面)数×
每道扇区数×
每扇区字节数。
5.典型磁盘调度策略(FCFS,SSTF,SCAN)磁盘调度的目标是使磁盘的平均寻道时间最少。
先来先服务FCFS(First-come,First-served)根据进程请求访问磁盘的先后次序进行调度。
优点:
公平、简单,每个进程的请求都能依次得到处理。
缺点:
未对寻道进行优化,致使平均寻道时间可能较长。
最短寻道时间优先SSTF(ShortestSeekTimeFirst)其要求访问的磁道与当前磁头所在的磁道,距离最短,以使每次的寻道时间最短,但这种调度算法却不能保证平均寻道时间最短。
缺点:
有新进程到达,且其所要访问的磁道与磁头当前所在磁道的距离较近,这种新进程的I/O请求务必先被满足,形成老进程的“饥饿”现象。
SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离,更优先考虑的是磁头的当前移动方向。
这种算法中磁头移动的规律颇似电梯的运行,又称电梯调度算法。
循环扫描CSCAN(CircularSCAN)为了减少SCAN算法造成的某些进程的请求被严重推迟,CSCAN算法规定磁头单向移动。
6.RAID将N台硬盘通过RAIDController结合成虚拟单台大容量的硬盘使用,其特色是N台硬盘同时读取速度加快及提供容错.磁盘:
条状读取,目的:
分散存放
n提高存取带宽:
各磁盘可以独立进行I/O.使用多个磁盘,提高了传输速率。
RAID通过在多个磁盘上同时存储和读取数据来大幅提高存储系统的数据吞吐量(Throughput)。
N提高冗余度:
数据镜像或校验
N通过数据校验,RAID可以提供容错功能。
校验方法:
奇校验,偶校验,奇偶校验,循环冗余校验,海明码校验
RAID0:
无差错控制的带区组RAID1:
镜象结构RAID2:
带海明码校验RAID3:
带奇偶校验码的并行传送RAID4:
带奇偶校验码的独立磁盘结构RAID5:
分布式奇偶校验的独立磁盘结构RAID6:
带有两种分布存储的奇偶校验码的独立磁盘结构RAID7:
优化的高速数据传送磁盘结构RAID10:
高可靠性与高效磁盘结构RAID53:
高效数据传送磁盘结构
(一十)Linux基础:
gcc,makefile,管道,重定向,运行级别
1.gcc
Gcc最基本的用法是∶gcc[options][filenames]其中options就是编译器所需要的参数,filenames给出相关的文件名称。
-c,只编译,不连接成为可执行文件,编译器只是由输入的.c等源代码文件生成.o为后缀的目标文件,通常用于编译不包含主程序的子程序文件。
-ooutput_filename,确定输出文件的名称为output_filename,同时这个名称不能和源文件同名。
如果不给出这个选项,gcc就给出预设的可执行文件a.out。
-g,产生符号调试工具(GNU的gdb)所必要的符号资讯,要想对源代码进行调试,我们就必须加入这个选项。
-O,对程序进行优化编译、连接,采用这个选项,整个源代码会在编译、连接过程中进行优化处理,这样产生的可执行文件的执行效率可以提高,但是,编译、连接的速度就相应地要慢一些。
-O2,比-O更好的优化编译、连接,当然整个编译、连接过程会更慢。
编译器的优化选项的4个级别,-O0表示没有优化,-O1为缺省值,-O3优化级别最高
-Idirname,将dirname所指出的目录加入到程序头文件目录列表中,是在预编译过程中使用的参数。
C程序中的头文件包含两种情况∶
A)#include
B)#include“myinc.h”
其中,A类使用尖括号(<
>
),
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 现代 操作系统 考试 复习