操作系统知识点整理资料下载.pdf
《操作系统知识点整理资料下载.pdf》由会员分享,可在线阅读,更多相关《操作系统知识点整理资料下载.pdf(7页珍藏版)》请在冰点文库上搜索。
![操作系统知识点整理资料下载.pdf](https://file1.bingdoc.com/fileroot1/2023-4/30/48924468-34b0-489e-a7f1-1b453ab87d05/48924468-34b0-489e-a7f1-1b453ab87d051.gif)
分时系统的实现方法:
1)作业应直接进入内存。
2)规定每个程序只运行一很短的时间(时间片),然后便暂停该作业的运行并立即调度下一个程序运行。
具体的实现方法:
1)单道分时系统。
2)具有“前台”和“后台”的分时系统。
3)多道分时系统。
特征:
1)多路性。
2)独立性。
3)及时性。
4)交互性。
4.4、实时系统定义:
是指系统能(或即时)响应外部事件的请求,在规定的时间内完成对该事件的处理,并控制所有实时任务协调一致地运行。
实时任务的分类:
1)按任务执行时是否呈现周期性来划分:
周期性实时任务和非周期性实时任务。
(外部设备所发出的激励信号并无明显的周期性,但都必须联系着一个截止时间(Deadline)。
它又可分为:
开始截止时间任务在某时间以前必须开始执行;
完成截止时间任务在某时间以前必须完成。
)2)根据对截止时间的要求来划分:
硬实时任务。
系统必须满足任务对截止时间的要求,否则可能出现难以预测的结果;
软实时任务。
它也联系着一个截止时间,但并不严格,若偶尔错过了任务的截止时间,对系统产生的影响也不会太大。
实时系统与分时系统特征的比较:
5)可靠性。
5、操作系统的基本特征:
实时、并发、共享、虚拟、异步。
6、操作系统的主要功能:
处理机管理,存储器管理,设备管理,文件管理,用户接口。
第二章第二章进程的描述与控制进程的描述与控制1、程序顺序执行时的特征:
1)顺序性。
2)封闭性。
3)可再现性。
2、程序并发执行时的特征:
1)间断性。
2)失去封闭性。
3)不可再现性。
3、进程的定义:
进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位。
4、进程的特征:
1)动态性。
2)并发性。
3)独立性。
4)异步性。
5)结构特征(PCB结构)。
5、进程实体的组成:
程序段,相关的数据段,PCB(进程控制块)。
6、进程的三种状态:
就绪(Ready),执行(Running),阻塞(Block)就绪阻塞执行时间片完进程调度I/O完成I/O请求活动就绪静止就绪执行挂起激活释放挂起活动阻塞静止阻塞挂起激活释放请求I/O7、PCB已成为进程存在于系统中的唯一标识。
PCB常驻内存。
8、进程标识符:
1)外部标识符(不唯一,通常是由字母、数字组成)。
2)内部标识符(唯一的数字标识符)。
9、(了解知道)系统态:
又称管态,内核态。
用户态:
又称目态。
10、原语定义:
由若干条指令组成,用于完成一定功能的一个过程。
它们是“原子操作”,是一个不可分割的基本单位,在执行过程中不允许被中断。
11、引起进程创建的事件(选择题):
用户登录、作业调度、提供服务、应用请求。
12、进程的同步对应课本2.412.1、临界资源(区):
在一段时间内只允许一个进程访问或使用,这种资源被称为临界资源。
每个进程中访问临界资源的那段程序称为临界区。
12.2、同步机制应遵循的规则(同步规则):
1)空闲让进。
2)忙则等待。
3)有限等待。
4)让权等待。
12.3、信号量1)记录型信号量:
在记录型信号量机制中,S.value的初值表示系统中某类资源的数目,因而又称为资源信号量,对它的每次wait操作,意味着进程请求一个单位的该类资源,因此描述为S.value=S.value-1;
当S.value0时,表示该类资源已分配完毕,因此进程应调用block原语,进行自我阻塞,放弃处理机,并插入到信号量链表S.L中。
可见,该机制遵循了“让权等待”准则。
此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。
对信号量的每次signal操作,表示执行进程释放一个单位资源,故S.value=S.value+1操作表示资源数目加1。
若加1后仍是S.value0,则表示在该信号量链表中,仍有等待该资源的进程被阻塞,故还应调用wakeup原语,将S.L链表中的第一个等待进程唤醒。
如果S.value的初值为1,表示只允许一个进程访问临界资源,此时的信号量转化为互斥信号量。
2)互斥信号量:
mutex,初值为1,取值范围(-1,0,1)。
当mutex=1时,表示无进程进入,无进程等待进入该临界区;
当mutex=0时,表示有一个进程进入,无进程等待进入该临界区;
当mutex=-1时,表示有一个进程进入,有n个进程等待进入该临界区。
12.4、前驱图例题:
a,b,c,d,e,f,g=0,0,0,0,0,0,0;
S1;
V(a);
V(b);
P(a);
S2;
V(c);
V(d);
P(b);
S3;
V(g);
P(c);
S4;
V(e);
P(d);
S5;
V(f);
P(e);
P(f);
P(g);
S6;
S4S5S3S1S6S2cefdabg13、经典进程的同步问题13.1生产者-消费者问题1、原型semaphoremutex=1,empty=n,full=0;
生产者消费者生产了一个产品;
P(full);
P(empty);
P(mutex);
从缓冲区取产品;
放到缓冲区;
V(mutex);
V(empty);
V(full);
消费;
2、变型1:
父亲分苹果和橘子问题(奇数-偶数问题)semaphoremutex=1,orange=apple=0,empty=n;
父亲女儿儿子洗一个水果;
P(apple);
P(orange);
取走;
if(苹果)V(apple);
elseV(orange);
3、变型2:
生产-加工-消费问题semaphoreempty1=x,empty2=y,full1=full2=0;
生产加工消费生产了一个产品;
P(full1);
P(full2);
P(empty1);
从B1取走一个产品;
从B2取走一个产品;
放到缓冲区B1;
V(empty1);
V(empty2);
V(full1);
加工;
P(empty2);
放入缓冲区B2;
V(full2);
注:
若缓冲区B1,B2为互斥,则在B1,B2操作前后加上申请和释放互斥信号量即可。
13.2哲学家就餐问题semaphoreS1=S2=S3=S4=S5=1;
P1P2P3P4P5饿了;
饿了;
P(S5);
P(S1);
P(S2);
P(S3);
P(S4);
吃;
V(S5);
V(S1);
V(S2);
V(S3);
V(S4);
解决死锁办法:
任意一个人拿筷子的顺序相反。
13.3读者-写者问题semaphorermutex=wmutex=1;
intreadcount=0;
读者写者P(rmutex);
P(wmutex);
if(readcount=0)P(wmutex);
/第一个读者写;
readcount+;
V(wmutex);
V(rmutex);
读;
P(rmutex);
readcount-;
if(readcount=0)V(wmutex);
/最后一个读者V(rmutex);
第三章第三章处理机调度与死锁处理机调度与死锁1、处理机调度的层次1.1、高级调度:
又称长程调度或作业调度,他的调度对象是作业。
JCB是作业存在的唯一标识。
1.2、低级调度:
又称进程调度或短程调度,他的调度对象是进程(或内核级线程)。
1.3、中及调度:
又称内存调度。
2、作业调度算法(二选一考):
先来先服务(FCFS)调度算法和短作业优先(SJF)调度算法。
3、周转时间:
作业提交系统开始到作业完成的时间段。
平均周转时间:
T=n1nin1T。
4、进程调度方式(算法):
非抢占方式(调度算法)和抢占方式(调度算法)。
5、抢占方式的抢占原则:
1)优先权原则。
2)短进程优先原则。
3)时间片原则。
6、产生死锁的原因:
竞争资源,进程间推进顺序非法。
7、产生死锁的必要条件:
1)互斥条件。
2)请求和保持条件。
3)不可抢占条件。
4)循环等待条件。
8、处理死锁的方法:
1)预防死锁。
2)避免死锁。
3)检测死锁。
4)解除死锁。
9、预防死锁的方法:
是通过破坏产生死锁的四个必要条件中的一个或几个,以及避免发生死锁,主要是破坏产生死锁的后三个条件:
破坏“请求和保持”条件,破坏“不可抢占”条件,破坏“循环等待”条件。
10、安全状态:
是指系统能按某种进程顺序(P1,P2,,Pn)为每个进程Pi分配其所需资源,直至满足每个进程对资源的最大需求,使每个进程都可顺利地完成。
此时称P1,P2,Pn序列为安全序列。
11、利用银行家算法避免死锁:
例题:
P119在银行家算法中,若出现下述资源分配状况,试问:
(1)该状态是否安全?
Finish时全为True,所以状态安全。
(2)若进程P2提出请求Request(1,2,2,2)后,系统能否将资源分配给它?
P2的Request2(1,2,2,2)Need2(2,3,5,6)且Request2(1,2,2,2)Available(1,6,2,2)进行预分配Available=(1,3,5,4)+(1,6,2,2)=(2,5,7,6)Allocation2=(1,6,2,2)-(1,2,2,2)=(0,4,0,0)Finish不全为True不能分配,恢复数据结构12、资源分配图(会画)以及资源分配图的简化。
P115、P11613、死锁定理(S为死锁状态的充分条件):
当且仅当S状态的资源分配图是不可简化的。
ProcessAllocationNeedAvailableWork+AllocationFinishP00,0,3,20,0,1,21,6,2,21,6,5,4TP11,0,0,01,7,5,02,9,8,6TP21,3,5,42,3,5,63,12,13,10TP30,3,3,20,6,5,21,9,8,6TP40,0,1,40,6,5,63,12,14,14T14、死锁的解除:
1)剥夺资源。
2)撤消进程。
第四章第四章存储器管理存储器管理1、动态分区分配算法(选择题):
1)首次适应(FF)算法:
空闲区按地址递增顺序排列。
2)循环首次适应(NF)算法:
空闲区按地址递减顺序排列。
3)最佳适应(BF)算法:
空闲区按大小递增顺序排列4)最坏适应(WF)算法:
空闲区按大小递减顺序排列。
2、分页存储管理方式:
掌握一级页表的地址划分;
掌握查页表,做地址变换。
页面大小4KB,按字节编址,写出地址划分。
2的12次方等于4KB3112110页号页内地址3、分段存储管理方式:
掌握地址划分。
4、分页和分段的主要区别:
1)页是信息的物理单位,段则是信息的逻辑单位。
2)页的大小固定且由系统决定,段的长度不固定,决定于用户所编写的程序。
3)分页的用户程序地址空间是一维的,分段系统中,用户程序的地址是二维的。
第五章第五章虚拟存储器虚拟存储器1、局部性原理:
早在1968年,Denning.P就曾指出:
1)程序执行时,除了少部分的转移和过程调用指令外,在大多数情况下仍是顺序执行的。
2)过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域,但经研究看出,过程调用的深度在大多数情况下都不超过5。
3)程序中存在许多循环结构,这些虽然只由少数指令构成,但是它们将多次执行。
4)程序中还包括许多对数据结构的处理,如对数组进行操作,它们往往都局限于很小的范围内。
局限性又表现在下述两个方面:
1)时间局限性。
如果程序中的某条指令一旦执行,则不久以后该指令可能再次执行;
如果某数据被访问过,则不久以后该数据可能再次被访问。
产生时间局限性的典型原因,是由于在程序中存在着大量的循环操作。
2)空间局限性。
一旦程序访问了某个存储单元,在不久之后,其附近的存储单元也将被访问,即程序在一段时间内所访问的地址,可能集中在一定的范围之内,其典型情况便是程序的顺序执行。
2、虚拟存储器定义:
指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统。
3、虚拟存储器的特征:
1)离散性(最基本的特征)。
2)多次性。
3)对换性。
4)虚拟性(最重要特征)。
4、缺页中断的特点:
1)在指令执行期间产生和处理中断信号。
2)一条指令在执行期间可能产生多次缺页中断。
5、页面置换算法(三选一考)5.1、最佳(Optimal)置换算法:
其所选择的被淘汰页面,将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。
缺页率:
9/20*100%=45%引用率70770170122010320304243230321201201770101页框(物理块)2035.2、先进先出(FIFO)页面置换算法:
选择在内存驻留时间最久的页面予以淘汰。
15/20*100%=75%Belady现象:
增加物理块,缺页率有可能上升。
5.3、最近最久未使用(LRU)页面置换算法:
选择最近最久未使用的页面予以淘汰。
12/20*100%=60%第六章第六章输入输出系统输入输出系统1、I/O设备的类型1.1、按传输速率分类:
1)低速设备,键盘、有鼠标器、语音的输入和输出等设备。
2)第二类是中速设备,有行式打印机、激光打印机等。
3)第三类是高速设备,有磁带机、磁盘机、光盘机等。
1.2、按信息交换的单位分类:
1)块设备(BlockDevice),这类设备用于存储信息,由于信息的存取总是以数据块为单位,故而得名。
有磁盘。
2)第二类是字符设备(CharacterDevice),用于数据的输入和输出。
其基本单位是字符,故称为字符设备。
1.3、按设备的共享属性分类:
1)独占设备。
2)共享设备。
3)虚拟设备。
2、通道类型:
1)字节多路通道,适用于中低速设备。
2)数组选择通道,适用于中速设备。
3)数组多路通道,适用于中高速设备。
3、I/O的控制方式:
中断控制方式,DMA方式,通道控制方式,程序控制方式。
4、设备无关性:
应用程序独立于具体使用的物理设备。
5、关于表的名词:
设备控制表DCT,控制器控制表COCT,通道控制表CHCT,系统设备表SDT。
6、假脱机(SPOOLing)定义:
可以利用其中的一道程序,来模拟脱机输入时的外围控制机功能,把低速I/O设备上的数据传送到高速磁盘上;
再用另一道程序来模拟脱机输出时外围控制机的功能,把数据从磁盘传送到低速输出设备上。
这样,便可在主机的直接控制下,实现脱机输入、输出功能。
称为SPOOLing技术,或称为假脱机操作。
7、SPOOLing的组成(两区两井两进程):
输入井和输出井,输入缓冲区和输出缓冲区,输入进程和输出进程。
8、SPOOLing系统的特点:
1)提高了I/O的速度。
2)将独占设备改造为共享设备。
3)实现了虚拟设备功能。
9、引入缓冲的原因:
1)缓和CPU与I/O设备间速度不匹配的矛盾。
2)减少对CPU的中断频率,放宽对CPU中断响应时间的限制。
3)提高CPU和I/O设备之间的并行性。
10、磁盘访问时间(不需要计算):
寻道时间Ts,旋转延迟时间T,传输时间Tt。
11、磁盘调度算法:
先来先服务(FIFO),最短寻道时间优先(SSTF),扫描(SCAN)算法,循环扫描(CSCAN)算法。
第七章第七章文件管理文件管理1、按文件是否有结构分类:
有结构文件(记录长度分为定长和不定长),无结构文件(又称流式文件)。
2、按文件的组织方式分类:
顺序文件,索引文件,索引顺序文件。
3、对文件目录的管理要求如下:
1)实现“按名存取”2)提高对目录的检索速度3)文件共享4)允许文件重名。
引用率70770170122010323104430230321013201770201页框2304204230230127127011引用率70770170122010320304403230321132201710701页框402432032102第八章第八章磁盘存储器的管理磁盘存储器的管理1、位示图法(根据位示图写出盘快的分配与回收)P261例题:
位示图利用二进制的一位来表示磁盘中一个盘块的使用情况。
值为“0”表示对应盘块空闲,为“1”表示已分配。
有的系统值为“1”表示对应盘块空闲,为“0”表示已分配。
1234567891011121314151611100011100101110200000111110010113.A.盘快的分配1)顺序扫描位示图,从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。
2)将所找到的一个或一组二进制位,转换成与之相应的盘块号。
假定找到的其值为“0”的二进制位,位于位示图的第i行、第j列,则其相应的盘块号应按下式计算:
b=n(i-1)+j式中,n代表每行的位数。
3)修改位示图,令mapi,j=1。
B.盘块的回收1)将回收盘块的盘块号转换成位示图中的行号和列号。
转换公式为:
i=(b-1)DIVn+1j=(b-1)MODn+12)修改位示图。
令mapi,j=1。
若位视图的起始标号为0则相应改动具体计算。
第九章第九章操作系统接口操作系统接口1、操作系统向用户提供了两类接口:
用户接口和程序接口。
2、系统调用的处理步骤:
1)将处理机状态由用户态转为系统态;
2)由硬件和内核程序进行系统调用的一般性处理,即首先保护被中断进程的CPU环境,保护CPU环境,将用户定义的参数传送到指定的地方保存起来;
3)分析系统调用类型,转入相应的系统调用处理子程序;
4)在系统调用处理子程序执行完后,应恢复被中断的或设置新进程的CPU现场,然后返回被中断进程或新进程。
(软件一班姚弘扬整理编辑)