北交操作系统辅导笔记.docx
- 文档编号:18375432
- 上传时间:2023-08-16
- 格式:DOCX
- 页数:33
- 大小:153.45KB
北交操作系统辅导笔记.docx
《北交操作系统辅导笔记.docx》由会员分享,可在线阅读,更多相关《北交操作系统辅导笔记.docx(33页珍藏版)》请在冰点文库上搜索。
北交操作系统辅导笔记
操作系统辅导(2004/4/10)
第一章引言
●OS的作用:
有效管理全部软硬资源
为用户提供一台虚拟机(屏蔽了硬件属性)
为用户与裸机之间建立接口(命令接口、图形接口、系统调用)
●OS的硬件基础知识
1.特权指令
特权指令:
启动设备、改变内存布局、….(OS可以使用)
非特权指令:
(允许一般用户使用.)
2.CPU状态和PSW
CPU状态:
(核态、管态、系统态、特权态)/(目态、用户态、普通态)
PSW:
描述CPU执行状态
CPU状态为用户态时,执行到特权指令,产生权利出错中断。
3.中断机构
1)中断类习型:
(1)I/O中断(设备I/O完成)。
(2)硬件故障(电源、内存校验等)。
(3)程序中断(非法指令--用户态执行特权指令,除0,地址越界等)。
(4)访管中断(系统调用)。
(5)外部中断(时钟、它机信号等)。
2)中断响应:
CPU响应中断请求,交换程序状态字(PSW)进入核态。
3)中断处理:
进步保留现场、执行相关的设备中断处理程序。
4)中断字寄存器:
每一中断源都有一位中断源触发器,所有触发器组成中断字寄存器。
CPU每执行完一条指令,扫描中断字寄存器,有则响应该中断。
●单道批处理系统:
解决人机矛盾,使作业流自动、顺序执行。
有作业调度,无进程调度。
●多道程序设计技术:
解决CPU与I/O速度不匹配矛盾,做到资源共享,提高资源利用率,提高系统吞吐量。
特点:
1)多道程序同时进入内存,在内存的位置不定。
2)按某中策略调度运行。
3)进程获得CPU后运行到完成或运行的条件不满足才让出CPU(阻塞或CPU被抢占)
●实时系统:
定义、分类、特征
●分时系统:
1)多道程序设计分时系统的实现方法。
2)特征。
●OS的基本特性(四个基本特性)
并发、共享、虚拟、异步性;
并发与共享互为条件。
虚拟:
一个物理实体改造为若干个逻辑上的对应体。
虚拟机、虚CPU、虚存、虚设。
异步性:
不确定性。
时序上不确定性;结果上的不确定性。
后者是不允许的。
●OS四大功能:
(P14)
1.CPU管理(四方面要点)
进程控制:
为作业创建进程、撤消进程、以及控制进程状态转换。
进程控制是通过内核相关的控制原语来实现。
进程同步:
1)对临界资源使用采用互斥方式,以解决结果不可再现问题。
2)对相互合作的进程采用同步方式,以协调合作进程执行次序。
进程通信:
低级通信(采用记数型信号量实现)、高级通信(由系统提供的命令、原语、系统调用来实现)。
进程调度;
2.存贮管理(四方面要点,按1的分析思路自己分析)
3.设备管理(三方面要点,按1的分析思路自己分析)
4.文件管理(三方面要点,按1的分析思路自己分析)
第二章进程管理
●程序并发执行的特性
1.间断性:
并发执行的程序存在着相互制约关系
间接制约:
共享临界资源。
直接制约:
合作完成一项任务。
2.失去了封闭性:
系统资源状态由并发执行的程序共同确定。
3.不可再现性:
时序上的不可再现,允许;结果上的不可再现,是不允许的,发生了与时间有关的错误。
●程序间存在着大量的结果不可再现的操作:
显然A、B的并发执行结果是不可再现的。
OS在设计中对类似的情况要进行技术处理:
同步与互斥问题。
●进程的基本概念
1.进程定义和特征:
(P29页)
有5个基本特征(结构特征、动态性、并发性、独立性、异步性)。
2.PCB的作用、PCB组成(三类信息:
标识、CPU状态、调度与控制)
3.进程的三种基本状态(就绪、运行、阻塞)
4.进程状态转换原因:
a:
交互用户发出的命令由命令解释进程立即创建进程投入就绪队列。
f:
(1)有作业进入后备队列;
(2)或系统某资源变得可用时:
作业调度(进程)被唤醒,为满足资源要求的作业创建进程。
作业调度进程平时处于阻塞状态。
b:
引起进程调度的事件:
(1)进程完成。
(2)进程异常终止。
(3)运行进程阻塞。
(4)CPU被剥夺。
c:
正在执行进程的CPU被剥夺:
(1)时间片到剥夺。
(2)就绪队列中优先级高的进程去剥夺运行进程的CPU。
d:
等待事件(进程阻塞):
(1)启动I/O,等待I/O完成。
(2)进程无事可做。
(设备驱动进程、消息通信中的接受进程、...)。
(3)申请资源得不到满足(如:
buffer、设备、...)。
(4)等待其它进程的数据或信号量(wait操作)。
e:
事件发生,由发现事件发生的进程(正在执行的进程)唤醒相关阻塞进程。
●OS内核:
提供了进程生存的条件(本身不是进程)
I.内核是传统意义的OS。
II.内核执行属性:
A.由中断驱动(包括系统调用)。
B.在核态下运行。
C.各种功能通过原语实现。
●进程管理内容:
进程控制、进程调度、进程同步与通信。
●进程控制:
6种原语,重点为创建、阻塞、唤醒原语。
a.创建原语:
1)引起的事件(p35,四种情况需要创建进程)。
2)创建过程。
b.阻塞原语:
1)引起阻塞的事件
2)阻塞原语流程
根据运行队列指针查到运行进程的PCB
置PCB为阻塞态
插入相关等待事件的阻塞队列
转进程调度
c.唤醒原语
1)引起唤醒的事件。
2)原语流程
(正在执行的进程发现与阻塞进程有关的事件发生,调用该原语把相关得进程唤醒。
)
从相关阻塞队列中移出一个劲成进程
PCB填为就绪
插入就绪队列
返回执行的进程
●线程概念
1.引入线程的目的:
进一步提高系统的并发能力,节省只有进程系统的时空开销。
2.传统进程特点:
资源的分配单位(占有打开的文件、内存、buf、设备等)。
是调度和分配CPU的单位、是一个执行单位。
3.线程特点:
共享创建者(进程)的资源,自己不占有CPU以外的资源。
是一个执行单位。
4.具有进程和线程系统的特点
1)进程仅仅是资源的分配单位(不再是执行单位)。
2)并发能力表现为:
各进程间的并发(各进程的线程并发)。
同一进程各个线程并发执行。
●进程的同步与通信
一.基本概念
临界资源、临界区、互斥、同步、临界区的管理原则。
同步要求的条件比互斥严格。
二.记录型信号量机制
1.记录型信号量定义。
2.Wait、signal两个原语的描述流程。
3.信号量值的物理含义。
三.利用记录型信号量机制解决互斥与同步问题
1.解决互斥问题:
设公用信号量mutex(互斥信号量),初值为1。
用wait(mutex)与signal(mutex)框住临界区。
2.解决简单的同步问题(供/用者通过单缓冲通信)
1)为A、B分别设私用信号量Sa、Sb,初值分别为1、0。
2)用wait(Sa)、signal(Sb)框住供者的临界区。
用wait(Sb)、signal(Sa)框住用者的临界区。
3.生产者与消费者问题
4.读写者问题
设有一个数据结构,有若干个进程要去读或写它
1)第一类读写问题的规则是:
(1)写是互斥的。
当一个进程正在写时,其它进程即不能写,也不能读。
(2)读可同时进行。
只要没有进程在写,则任何进程都可以同时去读。
要求对读写的同步过程要很清楚。
2)第二类读写问题的规则是:
除了满足以上两条规则外,还要满足第三条规则:
(3)写比读优先。
如果当前有要求写的进程则要求读的进程要等待,直至没有要求写的进程存在才可以去读。
对于此类问题通常要能看懂读与写的流程。
关键要:
对信号量的物理概念很清楚;
对wait、signal操作要很请楚;
要对互斥、同步的概念要很清楚;
四.消息缓冲队列通信机制
1.发送原语(send)
getbuf()从缓冲池申请一个空闲的buffer。
调用了缓冲池管理程序。
原语中的同步与互斥。
2.接受原语(receive)
原语中的同步与互斥。
用完的buffer应该调用缓冲池管理程序putbuf()过程交还给系统。
3.缓冲池管理程序见(p159)
3个队列(emq、inq、outq)
4个工作缓冲区
2个过程getbuf与putbuf,以及互斥与同步
第三章.调度与死锁
●调度类型
1.高级调度(以进程方式运行):
作业调度。
2.中级调度(以进程方式运行):
对换进程,UNIX中的0号进程。
负责内存与盘对换区之间信息的交换(页面、逻辑段、进程映象),凡是有此功能的系统,外存都有系统专用的对换区。
3.低级调度(原语):
进程调度:
非抢占方式:
适用于多道批处理系统。
抢占方式:
时间片的原则、短进程优先、优先权高者优先原则(适用于分时、实时、及批处理系统)
●调度队列模型
1.仅有进程调度:
p72(图3-1)
适用于分时系统、实时处理系统。
交互用户终端上的命令解释进程为用户的行命令或点击的图标创建进程并直接投入就绪对列。
2.具有高级与低级调度:
p73(图3-2)
适用于批处理系统和分时系统,要求后备队列按优先级排列,每过一段时间内外存作业交换(MULTICS),以保证交互用户的响应时间。
3.具有三级队列的调度模型:
(p74图3-3)
批作业进入后备队列,作业调度为后备作业创建进程投入就绪队列。
交互作业由命令解释进程直接创建进程投入就绪队列。
中级调度把进程映象在内存与交换区之间换入换出。
●调度方式和算法评价
1.面向系统准则:
吞吐量要高、CPU利用率要高、资源利用率要高
2.面向用户准则:
1)批处理系统:
要求平均T、W时间要小(即用户的满意程度要高)。
2)分时系统的响应时间T≦3s
3)实时系统保证截止时间(任务最迟开始时间、最迟完成时间)
4)优先权准则:
让优先级高的进程优先获得CPU。
●调度算法
1.FCFS
实用于:
作业调度。
到达时间指作业进入后备队列的时间。
实用于:
进程调度。
到达时间指进程进入就绪队列的时间。
2.SJ(p)F
实用于:
作业调度、进程调度。
1)用户满意程度好
2)长作业(进程)可能得不到运行机会.
3.简单时间片轮转法
1)时间片q的确定:
过大退化为FCFS.
过小,一个命令多个时间片才能完成,不满足响应时间要求.
2)响应时间T∝nqn….用户数量,q….系统处理能力(cpu速度等).
3)分时系统中,要求80%以上的交互命令,在一个q中完成,否则T难以保证.
4.优先权调度算法
1)非抢占方式:
进程获得CPU一直运行到完成,或等待事件才让出CPU。
2)抢占方式:
就绪队列出现更高优先级进程去抢占运行进程的CPU。
3)动态优先级计算
线性规则:
就绪队列各进程优先级+at
运行进程优先级+bt
a>b>0可防止运行进程长时间占据CPU。
非线性规则:
就绪队列(后备队列)的进程(作业)等待时间达某给定值时将其优先级突变到最大。
5.多级反馈队列调度(用以进程调度)p79
1)多个就绪队列优先级依次降低,分得的时间片依次增加。
2)同队列先来先服务。
3)优先调度高优先级队列进运行一个时间盘片,没完成投入下一个就绪队列。
4)进程首先进入最高优先级队列。
5)最低优先级队列进程按时间片轮转。
●死锁
1.死锁原因
1)资源不足:
包括非剥夺性资源和临时性资源。
2)推进速度非法:
生产者与消费者问题中wait语句对调、临界区设置有问题等。
2.死锁的四个必要条件
3.解决死锁的方法
1)预防死锁:
系统不可能发生死锁(破坏必要条件之一)。
2)避免死锁:
可能发生死锁,设法避免。
3)检测与解除死锁
主要是:
死锁产生原因、必要条件、银行家算法。
第四章存贮管理
一.程序的装入和链接
1链接:
链接是指多个目标模块在执行时的地址空间分配和相互引用。
1)静态链接:
静态链接是在生成可执行文件时进行的。
1)链接形成装入模块(又称可制行文件),由装入程序装入内存。
2)装入时动态链接:
loader边装入边链接。
3)运行时动态链接:
主程序模块装入运行,发生了外部访问,进行动态链接。
在装入或运行时进行链接。
通常被链接的共享代码称为动态链接库(DLL),或共享库(sharedlibrary)。
2.重定位:
在装入可执行文件时需要将可执行文件中地址(指令和数据)转变为物理地址的过程。
3.程序在成为进程前的准备工作
1)编辑:
形成源文件(符号地址空间)
2)编译:
形成目标模块(模块内符号地址解析)
3)链接:
由多个目标模块或程序库生成可执行文件(模块间符号地址解析)
4)装入:
构造PCB,形成进程(使用物理地址)
二.重定位方法:
1.绝对装入:
编译链接使用物理地址。
2.可重定位装入:
装入时根据装入的基地址,改变逻辑地址为物理地址。
3.动态装入:
重定位在执行过程中由地址变换机构完成。
三.单一连续区分配----作业需分配并装入连续内存空间
1.动态分区(可变分区):
装入程序时按其初始要求大小分配
1.
首次适应算法;循环首次适应算法;
最佳匹配算法。
2.可重定位分区分配
3.多重可重定位分区:
DOS采用了四重可重定位分区
重定位寄存器:
CS、DS、SS、ES
四重分区在内存中的位置可以不连续
每个分区(段),在内存中可以移动
物理地址=(段寄存器)+段内偏移地址(逻辑地址)
四.对换技术
1.对换(交换)空间概念:
用于暂存从内存换出的程序和数据,需要时再从该空间换入内存。
对换单位:
进程、页面、段
2.对外存交换区空间的管理
●采用动态分区方法
●对换空间管理的目标和空间分配方法
1)追求对换的速度而非空间利用率,文件系统往往追求外存空间的利用率。
2)采用以物理块为单位的连续分配策略,数据结构和算法类似内存管理中的可变分区管理。
二者差异:
(1)可变分区管理的是内存空间,对换技术管理的是外存的对换区。
(2)可变分区是以字节或内存块作为分配单位,对换技术是以对换区中物理块为单位。
五.基本分页管理
1.实现原理
1)进程地址空间分页,内存分块,页长=块长
2)通过页表把作业映射到内存
3)地址变换机构(P116图4-12):
2.基本分页管理采用的数据结构
1)进程页表(PMT):
每个进程一张,放于系统区.
2)内存空闲块的管理:
1)位示图. 2)空闲块链表.
3)对页表管理:
(1)整个系统一张请求表:
记录各进程页表的位置和长度.(进程运行前要装入页表控制寄存器)。
(2)页表位置、长度放于本进程的PCB中。
六.基本分段存管实现原理
●
1.地址空间分段,按段分配内存,每个段分配一个段号。
2.通过段表(SMT)把进程地址空间映射到内存。
3.地址变换机构(P121图4-17)。
七.虚拟存储的基本原理
1.在程序装入时,将当前需要执行的部分页或段装入到内存,就可让程序开始执行。
2.执行中,如果需执行的指令或访问的数据尚未在内存(称为缺页或缺段),将相应的页或段调入到内存,然后继续执行程序。
3.另一方面,操作系统将内存中暂时不使用的页或段调出保存在外存上,从而腾出空间存放将要调入的页或段。
4.以上2、3两条功能称之:
缺页中断(用于请求页式管理);
5.
6.
7.
8.缺段中断(用于请求段式管理)。
八.虚拟存储技术的特征
●
1.内存分配的离散性:
2.物理内存分配的不连续;
3.虚拟地址空间使用的不连续(数据段和栈段之间的空闲空间;共享段和动态链接库占用的空间)
4.作业装入的多次性:
不再一次性装入。
5.对换性
6。
虚拟性:
提供大范围的虚拟地址空间(通过物理内存和快速外存相结合).
注意:
总容量不超过物理内存和外存交换区容量之和
九.请求页式管理
1.实现原理
2.地址变换机构:
3.地址变换与中断处理流程(地址变换流程:
P130图4-24)。
4.物理块分配策略:
平均分配、按比例分配、按优先权分配.
5.
十.请求分段系统(P138)
1.段表:
对基本段式管理的段表要扩充5个字段
1)访问字段、修改位、存在位、外存地址这4个字段的功能类似请求页式的页表。
2)增补位(扩充位):
指示该段是否可动态增长。
当地址变换访问越界时,根据增补位的内容进行相应的中断处理。
2.缺段中断处理(P139图4-31)
3.地址变换机构(P140图4-32)
4.分段的共享与保护。
十一.虚拟存储的调入策略、分配策略
1.请求调页:
只调入发生缺页时所需的页面。
优点:
容易实现。
缺点:
对外存I/O次数多,开销较大
2.预调页:
在发生缺页需要调入某页时,一次调入该页以及相邻的几个页。
优点:
提高调页的I/O效率。
缺点:
基于预测,若调入的页在以后很少被访问,则效率低。
常用于程序装入时的调页。
3.在虚拟段式管理中,可采用可变分区分配算法。
4.调入页面的来源
1)进程装入时,将其全部页面复制到交换区,以后总是从交换区调入。
执行时调入速度快,要求交换区空间较大。
2)凡是未被修改的页面,都直接从文件区读入,而被置换时不需调出;已被修改的页面,被置换时需调出到交换区,以后从交换区调入。
节省交换区空间。
第五章设备管理
一.I/O设备类型(P144)
1.按传送速率分类:
低速、中速、高速设备。
2.按信息交换单位分类:
字符设备、块设备。
3.按设备共享属性分类:
独占、共享、虚拟设备。
二.I/O系统结构
1.总线结构(P150)
2.通道(CH)支持的I/O系统结构(5.1.3P148)
3.控制器(接口部件)的端口
1)当控制器接受一条命令后,可独立于CPU完成指定操作,CPU可以转去执行其它运算。
命令完成时,控制器产生一个中断,CPU响应中断,控制转给操作系统。
CPU通过读控制器寄存器中的信息,获得操作结果和设备状态
2)控制器与设备之间的接口常常是一个低级接口。
例如磁盘,可以按每个磁道9扇区,每个扇区512个字节进行格式化。
然而,实际从驱动器出来的却是一连串的位流,以一个头标,然后是一个扇区的4096比特位,最后是检查和错误校验码。
头标是在对磁盘格式化时写上的,它包括柱面和扇区数,扇区的大小等数据。
控制器的任务是把串行的位流转换为字节块,并进行必要的错误修正。
首先,控制器按位进行组装,然后存入控制器内部的缓冲区中形成以字节为单位的块。
在对块验证检查无错误时,再将它复制到主存中。
4.无论是采用总线,还是采用CH的I/O系统,都使用了控制器(接口)部件,每个接口部件都包含着一组寄存器(一组I/O端口),每个端口都有一固定地址,不同的信息将送入不同的端口。
1)数据端口:
对输入数据/输出数据起缓冲作用。
包括输入端口、输出端口。
2)状态端口:
保存设备、及控制器当前的状态。
3)命令端口:
存CH或CPU发来的命令,以便控制接口和设备的操作。
注:
CH或CPU对设备的操作归结为对接口(控制器)各端口的读/写。
5.端口编址方法
接口电路中:
有多个寄存器,每个寄存器有唯一的一个地址,每个地址为I/O端口,该地址称为I/O端口地址。
I/O指令形式与I/O地址是相互关联的,主要有两种形式:
内存映像I/O模式和I/O独立编址
1)I/O独立编址
分配给系统中所有端口的地址空间是完全独立的,与内存的地址空间没有关系,主机使用专门的I/O指令对端口进行操作。
例子:
8086/8088,分配给I/O端口的地址空间64K,0000H~0FFFFH,只能用IN和OUT指令对其进行读写操作
2)存储映像编址
分配给系统中所有端口的地址空间与内存的地址空间统一编址。
主机把I/O端口看作一个存储单元,对I/O的读写操作等同于对存储器的操作,不需要专门的I/O指令。
三.CH与CH程序
1.通道:
I/O处理器,能与CPU并行操作。
2.CH指令
读指令、写指令、控制指令。
3.CH程序:
CH指令的逻辑集合,放于内存的特定区域,由设备驱动程序自动生
4.CH程序执行:
2)
注:
CAW---CH地址字寄存器(功能相当于CPU中的PC)
CCW---CH控制字(功能相当于CPU中的IR)
CSW---CH状态字(功能相当于CPU中的PSW)
四.I/O控制方式(P151)
1)程序I/O方式:
CPU忙等待方式(查询方式)。
2)中断驱动方式:
CPU与外设并行操作,适用于慢速设备。
3)DMA方式:
CPU与块设备并行操作。
4)I/OCH方式:
CPU与CH并行操作,适用于各类设备。
五.缓冲管理(P155)
1.冲技术的引入
凡是数据到达和离去速度不匹配的地方均可采用缓冲技术。
在操作系统中采用缓冲是为了实现数据的I/O操作,以缓解CPU与外部设备之间速度不匹配的矛盾、减少了I/O设备对处理器的中断请求次数、简化了中断机制、提高资源利用率。
1)缓和CPU与I/O设备速度不匹配的矛盾。
2)减少中断次数。
3)提高CPU与外设的并行性。
2.缓冲区设置
硬缓冲:
在设备中设置缓冲区,由硬件实现。
软缓冲:
在内存中开辟一个空间,用作缓冲区。
单缓冲、双缓冲、循环缓冲、缓冲池(P159)
3.缓冲池(P159)
1).三个队列:
emq、inq、outq。
2).四个工作区:
hin、sin、hout、sout。
3).两个过程:
Getbuf(type)、Putbuf(type)。
(1)对三个队列操作的信号量
MS(type)----互斥信号量,type可以是emq、inq、outq
RS(type)----资源信号量,type可以是emq、inq、outq
RS(inq)、RS(outq)初值为0。
RS(emq)初值为缓冲池的容量。
同步、互斥实现、以及工作方式(P160)
六.设备分配
功能:
在内存与设备之间建立数据传输通路:
借助四种表格完成。
1.设备分配的数据结构(四种表格)
1)SDT:
系统设备表,整个系统一张,记录系统拥有的全部设备。
(P162)
2)DCT:
设备控制表,每台设备一张,记录设备使用情况。
(P161)
3)COCT:
控制器控制表,每个控制器一张,记录控制器使用情况。
(P162)
4)CHCT:
通道控制表,每个CH一张,记录CH使用情况。
(P162)
分配时依次查表,同时考虑到分配的安全性决定分配与否。
2.设备分配考虑的四个因素
1)设备属性
(1)独占设备:
考虑分配安全性,并采用独占分配策略。
(2)共享设备:
可同时分给多个进程,对进程的访问次序进行合理调度。
(3)虚拟设备:
可同时分给多个进程,对进程访问的物理设备次序进行合理调度。
2)分配算法
(1)先请求先服务:
请求进程依次排入设备请求队列。
(2)优先级高者优先:
请求进程按优先级排入设备请求队列。
3)安全性:
独占设备分配要进行安全性检查,以防死锁。
4)设备独立性
进程用逻辑设备名请求
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统 辅导 笔记