复试--操作系统(二)
我想自己再敲一遍,不会的再结合书
文章会加上王道部分习题
第一章OS概述
1.1概念和功能
概念:操作系统是指控制和管理整个计算机系统硬件和软件资源的最基本的系统软件
功能:(计算机系统自下而上分为:硬件、操作系统、应用程序、用户)
1.向上提供接口(用户:命令接口,编程员:程序接口)
2.向下层功能的扩展
3.对系统资源的管理(处理机、存储器、文件、设备)
1.2特征
并发性:指两个或多个事件在同一时间间隔内发生;(并行性:在同一时刻)
共享性:系统中的资源可供内存中多个并发执行的进程共同使用
虚拟性:把一个物理上的实体变成若干个逻辑上的对应物
异步性:进程的执行并不是一气呵成的,而是以不可预知的速度向前推进
1.3发展与分类
A:手工OS
特点:用户独占全机,资源利用率低;所有工作都需要人工干预,速度慢
B:批处理OS
单道批处理:自动性、顺序性、单道性
多道批处理:多道、宏观上并行、微观上串行
特点:
多道程序共享计算机资源、资源利用率高;
无人机交互能力
C:分时OS
把处理机的时间分片轮流分配
特点:
具有人机交互能力
不能优先处理紧急事件
D:实时OS
在时间限制内优先处理紧急任务
1.4运行机制
CPU执行两种程序
OS内核程序(内核态)
应用程序(用户态)
CPU的两种状态:
用户态(目态):不可以执行特权指令
内核态(管态)
CPU“变态”的唯一条件:中断、异常
实现“变态”的机制:通过硬件实现
中断和异常:
中断(外中断):指来自CPU执行指令以外的事件发生
异常(内中断、trap):指源自CPU执行内部的事件
系统调用
概念:指用户在程序中调用OS所提供的一些功能
目的:用户必须通过调用系统调用才能操作系统资源(OS代为完成),以保证系统稳定性和安全性。
如何引起:用户程序执行trap指令
执行过程:用户程序执行trap指令引发系统调用,请求操作系统提供服务。操作系统做出相应处理,将CPU由用户态转为内核态,执行系统调用,执行完后退出内核态,回到用户态
注意:发出系统调用请求是在用户态,执行系统调用是在内核态,故trap不是特权指令
1.5习题
1.操作系统是对计算机资源进行管理的系统软件,基本功能是控制和管理系统内的各种资源
2.现代操作系统的两个基本特征是并发与共享
3.用户可以通过命令接口和系统调用来使用计算机
4.操作系统向用户提供了命令接口,该接口又可以分为联机用户接口和脱机用户接口
5.计算机开机后,操作系统最终被加载到RAM
6.批处理器的主要缺点是无交互能力
7.实时系统的进程调度,通常采用抢占式的优先级高者优先算法
8.中断处理是操作系统必须提供的功能
9.用户程序在用户态下要使用特权指令引起的中断属于访管中断
10.用户态到核心态的转换是由硬件完成的
第二章 进程管理
2.1进程的概述
概念
进程是进程实体运行过程,是系统进行资源分配和调度的一个独立单位
组成
PCB:进程存在的唯一标志
程序段
相关数据段
PCB的组织方式
链接方式
索引方式
特征
动态性:进程是程序的一次执行过程。进程是动态的,程序是静态的
并发性:多个进程同时存在于内存中,能在一段时间内同时运行。引入进程的目的就是为了使程序能够并发运行
独立性:进程实体是一个能独立运行、独立获得资源和独立接收调度的基本单位。而程序不能作为一个独立的单位参与运行
异步性:异步性导致执行结果的不可再现性,因此OS中必须配置进程同步机制
结构性:每个进程都配置一个PCB对其进行描述
2.2进程的状态与转换
状态转换关系:就绪态、运行态、阻塞态、创建态、结束态
2.3进程的控制
概念:进程控制的主要功能是实现进程状态的转换
实现方法:用原语实现。原语是一种特殊的程序,采用开/关中断实现
相关原语
进程创建:
引发进程创建的事件:
用户登录系统、作业调度、系统提供服务、用户程序的应用请求
创建进程的基本过程:
1.创建PCB;2.为进程分配资源;3.初始化PCB;4.将进程插入就绪队列
进程终止:
引发进程终止的事件:正常结束、外界干预、异常结束
进程的阻塞和唤醒
Block原语
Wakeup原语
进程的切换
从一个进程的运行转换到另一个进程的运行
2.4进程的通信
方式
低级通信:PV操作
高级通信方式:共享存储、消息传递、管道通信
共享存储
设置共享空间,互斥访问
低级:基于数据结构的共享
高级:基于存储区的共享
消息传递
传递格式化的消息;两个原语:发送消息和接收消息
直接通信方式:发送进程直接把消息挂在接收进程的信息队列上,接收进程从消息缓冲队列中取得消息
间接通信方式:发送方把消息放到中间实体(信箱),接收方从中间实体接收消息
管道通信
管道,即共享文件
半双工通信。没读完就不能写,没写完就不能读
2.5线程
引入进程的目的
为了更好的使多道程序并发执行,提高资源利用率和系统吞吐量
引入线程的目的
为了减少程序在并发执行的过程中所付出的时空开销,提高操作系统的并发性能(为什么线程可以提高系统的并发性呢?由于有了线程,线程的切换有可能会引发进程切换,也有可能不发生进程的切换,于是平均而言的开销就小了)
线程与进程的比较
调度:在传统的操作系统中,进程是拥有资源和独立调度的基本单位,在引入线程的操作系统,线程是独立调度的基本单位,进程是拥有资源的基本单位
拥有资源:进程是拥有资源的基本单位,线程除了本身所必须的一点资源,基本上不拥有资源
并发性:在引入线程的操作系统中,不仅进程之间可以并发执行,多个线程之间也可以并发执行,从而操作系统具有更好的并发性
系统开销:由于创建和撤销进程时,系统都要为之分配和回收资源,因此所付出的开销远远大于创建和撤销线程时的开销
线程实现的方式
用户级线程:线程的管理工作都由应用程序完成,应用程序通过使用线程库实现多线程程序
内核级线程:线程的所有工作
多线程模型
多对一:将多个用户级线程映射到一个内核级线程,线程管理在用户空间完成。
优点:开销小;
缺点:一个线程被阻塞,整个进程就会被阻塞,并发度低。
一对一:一个用户级线程映射到一个内核级线程。
优点:当一个线程被阻塞时,允许另一个线程继续执行,并发度高;
缺点:开销大。
多对多:将n个用户级线程映射到m个内核级线程上(m<=n)
特点:并发度高,开销小
2.6处理机调度
概念
处理机调度是对处理机进行分配,即从就绪队列中按照一定的算法选择一个进程,并将处理机分配给它运行
三个层次
作业调度(高级调度):将处于外存中后备队列的作业挑选一个调入内存,并分配相应的资源
内存调度(中级调度):将内存中已具备运行条件,但内存紧张时,将这些内存调至外存等待,此时进程为挂起态;当内存有空闲时,再将其调入内存 ,并将状态修改为就绪态。
进程调度(低级调度):从内存中的就绪队列选取一个进程分配处理机
三层调度之间的联系和区别
作业调度:次数最少;外存调至内存
内存调度:次数中等;外存调至内存
进程调度:次数最多;内存调至CPU
何时能调度和切换
发生引起调度条件且当前进程无法继续运行下去时
中断或异常处理结束后
何时不能调度和切换
在处理中断的过程中
进程在操作系统内核程序临界区中
需要屏蔽中断的原子操作过程
调度方式
非抢占式
抢占式
调度的性能准则
CPU利用率:应该尽量使CPU处于“忙”状态
系统吞吐量:表示单位时间内系统完成作业的数量;
周转时间:作业从提交到完成的时间;
等待时间:处于等处理机状态的时间;
响应时间:从用户提交到系统首次响应。
调度算法
FCFS、SJF、优先级、高响应比、时间片轮转、多级反馈队列
2.7进程同步与互斥
概念
进程的并发执行带来了异步性问题,进程同步机制用以解决异步性问题
临界资源和临界区
临界资源:一次仅允许一个进程使用的资源,必须互斥访问
临界区:每个进程中,访问临界资源的那段代码。(进入区、临界区、退出区、剩余区)实现进程互斥的方法
软件实现方法:在进入区设置并检查一些标志来表明是否有进程在临界区中,若有,则在进入区通过循环检查进行等待,进程离开临界区后则在退出区修改标志
硬件实现方法:
中断屏蔽法:使用“开/关中断”指令,禁止一切中断的发生,只适合单CPU、OS内核进程
硬件指令法(TSL/Swap):原子操作,适合多处理机
2.8信号量机制
整型信号量
S用于表示资源数目
如果资源不够,就会一直循环等待,使得进程可能处于“忙等”,为满足让权等待。
记录型信号量
value代表资源数目,链表L链接了所有等待该资源的进程
当value<0时,进程会进入阻塞态,并插入L等待队列中
不会出现“忙等”
实现同步
设置公告信号量S=0,前V后P
分析步骤:
1.分析问题,找出哪里需要实现一前一后同步关系
2.设置同步信号量S
3.在前操作之后执行V操作,在后操作之前执行P操作
实现互斥
设置互斥信号量S=1,临界区之前设置P,之后设置V
分析步骤
1.分析问题,确定临界区
2.设置信号量S=1
3.临界区之前,对信号量执行P操作,之后执行V操作
经典同步问题
生产者-消费者,哲学家进餐,吸烟者问题,读者-写者问题
2.9管程
概念
信号量机制的存在问题是让编写程序困难、易出错。管程用来实现进程同步、互斥,该机制让写程序时不用关系复杂的P、V操作
组成
局部于管程的数据结构
对数据结果进行操作的函数过程
数据结构的初始化
基本特性
局部于管程的数据只能被局部于管程的过程所访问
一个进程只能通过调用管程内的过程才能进入管程访问共享数据
每次仅允许一个进程在管程内执行某个内部过程
2.10死锁
定义
多个进程因竟争资源而造成的一种互相等待的局面,若无外力作用,这些进程将无法向前推进
产生的原因
系统资源的竟争、进程推进顺序不当
产生的必要条件(缺一不可)
互斥条件、不可剥夺条件、请求并保存条件、循环等待条件
注意:发生死锁时一定有循环等待,反之不一定。资源分配图含圈而不一定死锁的原因:同类资源数大于1
死锁的处理策略
死锁预防:设置某些限制条件,破坏死锁的四个必要条件中的一个或几个,以防止死锁的发生
避免死锁:在资源的动态分配过程中,用某种方法防止系统进入不安全状态,从而避免死锁
死锁的检测与解除:通过系统的检测机构及时地检测出死锁地发生,然后采取某些措施解决死锁
死锁预防
破坏互斥条件:使系统资源都能共享
破坏不剥夺条件:当进程已保持了一些不可剥夺资源且又申请新的资源而得不到满足时,它必须释放
破坏请求并保持状态:进程在运行前一次性申请完他所需要地全部资源
破坏循环等待状态:给系统中地资源编号,规定每个进程必须按照编号递增地顺序请求资源,同类资源一次申请完
避免死锁
概念:进程可以动态地申请资源,但系统在进行资源分配前,需要先计算此资源分配地安全性,若此次分配不会导致系统进入不安全状态则分配,否则让进程等待
安全序列:指系统能按照某种顺序为每个进程分配其所需地资源,直到满足每个进程对资源地最大需求,使得每个进程都可以顺利完成
死锁的检测与解除
资源分配图
死锁定理:死锁的条件是当且仅当资源分配图是不可完全简化的
死锁检测
2.11习题
1.管道通信进程对管道进行读操作和写操作都可能被阻塞
2.父进程和子进程可以使用同一临界资源
3.导致进程P阻塞的有进程P申请临界资源,进程P从磁盘读数据,系统将CPU分配给高优先级的进程
4.可能会将进程唤醒的事件是IO结束,某进程退出临界区,当前进程时间片用完