关于操作系统一般笔试面试中问的比较浅,根据教材整理了一份比较基础的操作系统的学习笔记
一、进程管理
1. 为何引入进程
程序的执行顺序:
(1)顺序执行:顺序性、封闭性、可再现性
(2)并发执行:间断性、失去封闭性、不可再现性
在多道程序环境下程序的执行是并发的,这样程序就要失去封闭性,并且间断且不可再现。并发执行的三个特点决定通常的程序是不能被并发执行的,于是引入了进程。
2. 进程的特征
(1)结构特征:每个进程都对应一个PCB(进程控制块)。程序段、数据段和PCB构成了进程实体。
(2)动态性:动态性是进程最基本的特征,因为进程的实质是进程实体的一次执行过程。
(3)并发性:进程的引入就是为了满足多道程序的并发执行的特征。
(4)独立性:进程是参与资源分配的基本单位(线程是被调度的基本单位)
(5)异步性:指进程被执行的速度和顺序具有不确定性,即进程按异步方式运行。
3. 进程的状态
就绪状态:只差CPU就可以运行的进程
执行状态
阻塞状态:正在执行的进程遇到某个时间之后暂时不需要CPU了,就把CPU让出来并排到阻塞状态的进程队列中去。
4. PCB
PCB是进程存在的唯一标志。
PCB的作用:是让一个在多道程序环境下无法兵法运行的程序成为一个能够独立地接受调度和运行的基本单位,从而使之成为能和其他进程并发运行的进程。
PCB的内容:进程标识符、CPU状态信息、进程调度信息、进程控制信息等。
PCB的组织方式:链接方式、索引方式
5. 进程控制
进程的创建
1)引起进程创建的事件有:用户登录、作业调度、提供服务、应用请求
2)创建步骤:申请空白PCB、为新进程分配资源、初始化进程控制块、将新进程插入就绪进程的终止
1)引起进程终止的事件有:正常结束、异常结束、外界干预
2)终止步骤:读进程状态、若被终止进程处于执行状态则表示该进程被终止后需要重新调度、若该进程有子孙进程则终止所有子孙进程、归还进程资源、移除队列中的PCB
进程的阻塞与唤醒
引起进程阻塞的事件:请求系统服务、启动某种操作、新数据尚未到达、无新工作可做
引起唤醒的事件:当被阻塞进程所期待的事件出现的,如系统服务完成、I/O操作完成、所期待数据已经到达
6、进程同步
(1)临界资源:某些共享资源仅允许一个进程使用,这就是临界资源。比如打印机、磁带机。
(2)临界区:每个进程中访问临界资源的那段代码叫做临界区。临界区是进程中的代码!!
为了查看当前有没有进程在访问临界资源,所以每个进程在进入临界区之前要执行一段检测代码,这段代码叫做进入区。在离开临界区后进程要标记下现在已经没有进程访问临界资源,这段代码叫做退出区。其他代码称为剩余区。
(3)同步(直接相互制约关系):一个进程到达了某点后,除非另一进程已经完成了某些操作,否则就不得不停下来等待这些操作的结束,这就是进程间的同步,有了同步后进程间就可以相互合作。
(4)互斥(间接相互制约关系):多个进程都想使用一个临界资源,但是不能同时使用,于是只好一个进程用完了才能给其他进程用,这就是进程互斥。某种意义上说进程互斥是进程同步的一个特殊情况。
1. 实现同步的准则
A. 空闲让进:当无进程处于临界区时,应允许一个请求进入临界区的进程立即进入自己的临界区
B. 忙则等待:当已有进程进入临界区时,其他试图进入临界区的进程必须等待,以保证临界资源互斥访问
C. 有限等待:对要求访问临界资源的进程,应保证有限时间内进入自己的临界区,以免陷入“死等”
D. 让权等待:当进程不能进入自己的临界区时,应立即释放处理机,以免进程陷入“忙等”(忙等是指当一个进程在临界区,当其他进程欲进入临界区时,反复检测是否可以进入,即忙于等待临界区中的进程离开)
2. 信号量机制
(1)整型信号量
整型信号量是一个整型的变量S,能对S进程的操作有3种:
第一个是初始化S,给出S的初值;
第二个原子操作wait(S),又称作P操作;
Wait(S){
While(S <= 0); //不执行任何操作,循环
S--;
}
第三个是原子操作signal(S),又称作V操作
Signal(S){
S++;
}
注:原子操作是指不能被中断的操作,可以用原语实现。
(2)记录型信号量
整型信号量没有实现同步机制的第四条“让权等待”,因为执行了wait操作时弱信号量S<=0,那么就会不断的循环测试S的数值,不会释放CPU资源。记录型信号量就是为了解决这种忙等现象而被提出的。
记录型信号量的数据结构可用结构体表示:
Struct{
Int value;
Struct process *L;
}semaphore;
Wait操作的伪代码:
Void wait(semaphore S){
S.value --;
If(S.value < 0) //S.value < 0时,阻塞进程
Add this process to S.L;
Block(S.L);
}
Signal操作的伪代码:
Void signal(semaphore S){
S.value ++;
If(S.value <= 0){
Remove a process P from S.L;
}
}
3. 管程机制
管程的定义:管程是由一组数据以及定义在这个数据之上的对这组数据的操作组成的软件模块,这组操作能初始化并改变管程中的数据和同步进程。
7. 进程通信
进程通信就是进程间的数据交换。进程的互斥与进程的同步就是进程通信中的低级通信方式。Wait和signal操作成为低级通信原语。
高级通信方式是指以较高的效率传输大量数据的通信方式。
(1)共享存储器系统:是指互相通信的进程通过某些共享存储区或者共享数据结构进行通信。通过对共享存储区的读写来进行通信的方式属于高级通信方式,基于共享数据结构的通信方式属于低级通信方式。
(2)消息传递系统:进程间的数据交换是以格式化的消息为单位进行。具体又分直接通信方式和简介通信方式。
(3)管道通信:所谓的管道就是一个共享文件,它连接了一个读进程和一个写进程,让它们之间可以借助这个共享文件进行通信。写进程以字符流的形式将大量信息写入管道,读进程则在需要时从管道读出数据。
8. 线程
引入线程的原因:
创建进程的开销大、导致进程并发度不够,进程管理的开销大,进程间通信太麻烦,正是由于进程存在着这些缺点,致使引入线程。
线程的概念:
线程是进程中某个单一顺序的控制流,也被称为轻量进程,它是进程中的一个实体,是被系统独立调度和分派的基本单位。
用户级线程和内核支持线程:
用户级线程:仅存在用户空间,与内核无关。内核管理用户级线程对应的整个进程。它感觉不到用户级线程的存在。好处:无需内核支持就可以实现多线程,线程的切换不需要陷入到内核,所以切换的开销小速度快。缺点:进程的一个线程被阻塞后整个进程中的所有线程都被阻塞,并且无法享有多处理机带来的好处。(调度单位为进程)
内核支持线程:是由内核负责管理的,线程控制块也在内核中。所以线程的创建、切换、撤销等操作都是通过系统调用在内核中完成的。好处:进程中的一个线程被阻塞之后该进程的其他线程还可以继续执行不会被阻塞。缺点:即使是同一个进程内的不同线程之间的切换也要陷入内核,开销大。
多线程模型:
(1)多对一模型(多个用户级线程映射到一个内核线程)
优点:线程管理是在用户控件进行的,因而效率比较高。
缺点:进程的一个线程被阻塞后整个进程中的所有线程都被阻塞
(2)一对一模型(一个用户级线程映射到一个内核线程)
优点:进程中的一个线程被阻塞之后该进程的其他线程不会被阻塞,并发能力较强
缺点:开销大
(3)多对多模型(m个用户级线程映射到n个内核线程,m ≥ n)
特点:集二者之所长
二、处理及调度与死锁
1. 处理及调度的基本概念
1. 三级调度
(1)高级调度:又称为作业调度或长期调度
作业调度负责从外存上等候调度的作业中断则一个调入内存,并给这个作业分配资源,创建进程,然后挂到就绪队列上等待进程调度。
(2)中级调度:又称为进程对换或中程调度
中级调度负责把暂时无法运行的在内存中的进程调到外存中等待以减少内存空间的浪费,在内存有空闲时把外存中有条件运行的进程重新调入内存。所以引入中程调度主要是为了提高内存的利用率和系统的吞吐量。被中级调度处内存的进程处于挂起状态,中级调度的实质是对换。
(3)低级调度:又称为进程调度或短程调度,是最基本的一种调度
进程调度负责从内存的就绪队列上等候调度的进程中选择一个分配CPU给他,该进程的状态于是从就绪转变为运行。
调度队列
进程进入系统时,会被加入到作业队列中。驻留在内存中就绪的等待运行的进程被保存在就绪队列上,该队列一般用链表的形式来存储。等到特定的I/O设备的进程被放在特点的设备队列中,每个设备都有自己的设备队列。
2. 调度方式
1)非抢占式:即一个进程在执行过程中除了它自身有I/O请求等事件发生的情况外,其他进程不得中断它的执行,也就是不得抢夺他的CPU资源
2)抢占式:根据某种算法计算各个进程的优先权,优先权高的进程可以在优先权低的进程正在执行的时候抢夺其CPU资源
抢占的原则:
A. 给重要和紧急的进程赋予高的优先权
B. 短作业优先原则,即给短作业赋予高的优先权
C. 时间片原则,即给时间片完了的进程最低的优先权
3. 选择调度方式和算法的准则
(1)用户角度
A. 周转时间短
周转时间:作业从被提交给系统开始到作业完成为止的这段时间间隔的长度
带权周转时间:周转时间/运行时间
B. 相应是间短(尤其对于分时系统)
响应时间:用户通过键盘提交请求后开始计时,到系统做出第一个响应为止的时间间隔。
C. 截止时间的保证
截止时间:一个任务开始得到执行或被执行完毕的最迟时间
(2)系统的角度
吞度量、处理机利用率、各类资源的平衡利用
2. 调度算法
1. 先来先服务算法(FCFS)
2. 短作业优先算法(SJF)
3. 优先级调度算法
静态优先权算法:进程的优先权在整个运行期间不变
动态优先权算法:进程的优先权随着进程被调度的情况变化而变化,如随着进程等待的时间的增加而增加,这样可以防止有些优先级低的进程长期得不到运行
高响应比优先(动态):响应比 = (等待时间 + 运行时间)/ 运行时间
4.时间片轮转法(RR)
执行中的进程只要时间片用完就要被就绪队列队首的那个进程抢占CPU。
5.多级队列调度算法
将就绪队列分成多个独立的队列,根据进程的属性和类型将一个进程永久地分配到一个队列中。每个队列都有自己的调度算法。队列之间有优先级差别,通常采用固定优先权可抢占调度
6.多级反馈队列调度算法
多级反馈队列调度算法将就绪队列分成多个队列,每个队列拥有的优先级不同,一个新的进程到达内存后,先被放到优先级高的队列中按时间片轮转法被调度执行,若在时间片用完后没有被执行完,那就被扔到优先级低的下一个队列去时间片轮转,相应的得到执行的机会就减少了。
优势:
1)保证了短作业的优先,让终端型用户满意
2)短批处理作业也能在一两个队列给的时间片里完成,周转时间仍然较短
3)长批处理作业虽然优先级较低,但经过前面几个队列后已经得到了部分执行,用户不必担心他长期处理
3. 产生死锁的原因和必要条件
1. 死锁产生的原因
根本原因:系统资源数量不足、进程推进顺序不当
(1)竞争资源
可剥夺性资源;指抢占式系统中的一个进程得到了这种资源后还可以被其他进程所抢占。
不可剥夺性资源:指一旦被分配给了一个进程就不能被抢占,除非该进程用完后释放的资源
竞争不可剥夺性资源可能导致死锁,但竞争可剥夺型资源不可能导致死锁
(2)进程间推进顺序非法
2. 必要条件
(1)互斥条件:被争夺的资源同一时间只能被一个进程使用
(2)请求和保持条件:即一个进程由于请求某个资源不成功而被阻塞的时候不释放它之前申请到的资源(解决:只有一次性申请到所有所需资源,否则将释放已经申请的资源)
(3)不剥夺条件:是指一个进程在申请到资源后不能被其他进程剥夺,直到其自己释放(解决:允许系统中的进程在申请了系统中已经没有的资源后,可从其他没有在运行的进程抢占该资源)
(4)环路等待条件:是指发生死锁时必然存在一个资源-进程环路。(解决:要求进程按资源的编号来顺序申请资源)
3. 处理方法
(1)死锁预防:通过破坏上述四个必要条件的一个或多个,这种方法往往导致系统的效率低,资源利用率低
(2)死锁避免:并非事先就设置好限制条件来破坏死锁发生的必要条件,而是在资源动态分配的过程中用某些算法加以限制,防止系统进入不安全状态从而避免死锁的发生。(银行家算法)
(3)死锁检测
(4)死锁解除:通过撤销一些进程回收资源,以较低限度的代价把系统从死锁中解脱出来。
三、存储器管理
1. 连续分配方式
连续分配方式是指为一个用户程序分配一个连续的内存空间。
(1)单一连续分配:把内存分为系统区和用户区,各让OS和用户使用,只能用于单用户、单任务OS,可以采用覆盖技术。
(2)固定分区分配:把用户的内存空间划分成几个固定大小的区域,每个分区中可以装入一道作业,这样就可以实现多道程序。分区大小可相等也可不等。
(3)动态分区分配
A. 首次适应算法FF
B. 循环首次适应算法(每次不是从队首而是从上次找到空闲分区的下一分区开始查找)
C. 最佳适应算法
D. 最差适应算法
(4)动态可重定位分区分配
内部碎片:就是已经被分配出去(能明确指出属于哪个进程)却不能被利用的内存空间;
外部碎片:还没有被分配出去(不属于任何进程),但由于大小太小无法分配给申请内存空间的新进程的内存空闲区。
紧凑(拼接):采用移动内存中的作业到一起的方法把空闲空间从多个小分区变为一个大分区以满足要求,紧凑之后要对被移动的作业的程序和数据的地址加以变化。
对换:把系统中暂时无法运行的进程或暂时不用的程序和数据调出到外存上,以便腾出内存空间给已经具备运行条件的进程或进程所需的数据和程序,以增加内存使用率
2. 基本分页和基本分段存储管理方式
3. 段也是存储管理方式
先页后段
克服了外部碎片,但是内部碎片比分页还多。
多访问一次内存。
4. 虚拟存储器
引入原因:解决内存不足的问题
1. 局部性原理
程序的局部性原理是指程序在执行的时候呈现出的局部性规律,也就是说一个短的时间范围内,程序的执行仅仅局限于某个部分,相应的他所访问的存储空间也局限于某个区域。
(1)时间局部性
程序中的某条指令一旦被执行,他们他不久后可能再次被执行
(2)空间局部性
当程序访问了某个存储单元后,之后的时间内这个存储单元附近的存储单元也有可能被访问到,也就是程序在一段时间内访问的存储空间集中在一定的范围内。
2. 虚拟存储器的概念和特征
虚拟存储器是指有请求调入功能和置换功能的能从逻辑上对内存容量加以扩充的一种存储器系统,实际上是一个地址空间
虚拟存储器的特征
多次性(最重要的特征):与常规存储管理的一次性相反,虚拟存储器把一个作业分多次调入到内存
对换性:与常规存储管理的驻留性相反,在作业运行期间虚拟存储器允许将那些暂时不运行的程序或数据调出到外存的兑换区,到运行需要用到的时候才再调回到内存,提高了内存利用率
虚拟性:虚拟存储器对内存的扩充是逻辑上的
四、设备管理
1. I/O设备和设备控制器
(1)I/O设备类型
按速度分类:低速设备(键鼠),中速设备(打印机),高速设备(磁盘)
按信息交换单位:块设备(磁盘),字符设备(打印机、终端)
按共享类型:独占设备、共享设备(同一时刻仍只允许一个进程访问)、虚拟设备
按使用特性:I/O设备、存储设备
(2)设备控制器
控制一个或多个I/O设备的硬件,它提供了CPU和I/O设备直接的接口。如网卡、显卡
2. I/O控制方式
——最主要的驱动力:减少CPU对I/O控制的干预
(1)程序I/O方式
程序I/O方式中,有I/O速度远远慢于CPU,致使CPU绝大部分时间都在测试I/O设备是否已经完成数据传输。
(2)中断驱动I/O控制方式
中断的优点:CPU和I/O可以并行工作,无需CPU不断测试,I/O设备会自行传输数据,等到一个数据传输完毕,I/O设备会发出一个中断来提醒CPU,CPU只需收到中断后处理下即可。
中断的缺点:由于中断I/O控制方式每传输几个字节(由数据缓冲寄存器大小决定)就发出一次中断,所以CPU还是会频繁的去处理中断。
中断处理程序的过程(仅指I/O完成时发出的中断):
1)唤醒被阻塞的驱动程序进程
2)保护被中断进程的CPU环境:将处理机状态字PSW和程序计数器PC等压栈。
3)转入相应的设备处理程序:测试中断源以确定引起中断的设备号
4)恢复被中断进程的现场:把当时压入栈保护的数据弹出恢复当时CPU执行的上下文
(3)直接存储器访问I/O控制方式(DMA)
用DMA控制器来控制一个数据块的传输,而CPU只需在一个数据块传输的开始阶段设置好传输所需的控制信息并在传输的结束阶段做进一步处理即可的传输控制方式。其基本思想是在I/O设备和内存间开启一个可以直接传输数据的通路
特点:
1)数据传输的基本单位是数据块
2)所传诵的数据时从设备直接送入内存,或者相反
3)仅在传送一个或多个数据块的开始和结束时,才需CPU干预,整块数据的传送是在控制器的控制下完成的。
(4)I/O通道控制方式
I/O通道实际上是一种特殊的处理机。相对于DMA对每个数据块的读写为单位的干预,减少为对一组数据库的读写及有关控制和管理为单位的干预。又可实现CPU、通道和I/O设备三者的并行操作。
通道与DMA方式的比较:
类似:都是以内存为中心,实现了内存和设备直接交换数据
区别:
1)DMA方式需要CPU来控制传输的数据块的大小、传输的内存,而通道方式中这些信息都是有通道来控制管理的。
2)每个DMA控制器对应一台设备与内存传递数据,而一个通道可以控制多台设备与内存的数据交换。
3. 缓冲管理
高速缓存和缓冲区的区别:
高速缓存是为了存放低速设备上经常要被访问到的数据的拷贝,如果需要访问的数据高速缓存中没有,那么还是要去访问低速设备的。缓冲区是为了缓和高速设备和低速设备之间速度不匹配的矛盾而存在的,高速设备和低速设备通信每次都要经过缓冲区,高速设备不会直接去访问低速设备(因为不一定有拷贝)。
4. 设备分配
设备独立性:应用程序独立于具体使用的物理设备,它可以提高设备分配的灵活性和设备的利用率。
为了实现设备独立性而引入逻辑设备和物理设备这两个概念,而系统中需要设置一张逻辑设备表(LUT),其中每个表象中都有逻辑设备名、物理设备名和设备驱动程序入口地址。
设备独立性的优点:(1)设备分配时的灵活性、易于实现I/O重定向(2)提高设备资源利用率