韩国网站怎么打开,东莞是什么网站建设,吉安网站建设收费,静态网站制作模板第一章
1、操作系统#xff1a;OS是一个大型的系统软件、它负责计算机的全部软件和硬件资源的管理#xff0c;并为用户提供良好的应用界面#xff0c;使整个计算机系统实现高效率和高度自动化 2、操作系统的形成
1#xff09;手工操作阶段
2#xff09;批处理系统…第一章
1、操作系统OS是一个大型的系统软件、它负责计算机的全部软件和硬件资源的管理并为用户提供良好的应用界面使整个计算机系统实现高效率和高度自动化 2、操作系统的形成
1手工操作阶段
2批处理系统一系列作业的序列称之为批
1单道批处理系统一批作业以脱机方式输入到存储介质上磁带、磁盘系统能对这批作业一个接一个连续自动处理因在内存上只保持一道作业故称单道批处理系统
2多道程序设计技术--多道批处理系统在计算机内存中同时存放几道相互独立的程序它们在管理程序控制下相互交替执行当某道作业因某种原因不需要CPU时管理程序将另一道作业投入运行这样使CPU和各种设备处于忙碌状态从而大大提高了计算机的使用效率
多道程序设计技术的硬件支持是中断与通道技术、使主机与外设之间可以并行工作
特点①多道②宏观上并行③微观上串行
优点①资源利用率高②系统的吞吐量大
缺点①有时用户的响应时间较长②交互性不好
分时技术与分时操作系统特点用户有较快的响应时间、交互性好响应时间与就绪队列中进程数目和时间片大小有关 3、操作系统的基本类型
1批处理操作系统
2分时操作系统
批处理操作系统和分时操作系统的不同点
1追求的目标不同
①批处理系统提高系统资源利用率和作业的吞吐能力为目标
②分时系统强调公平性对于联机用户的立即型命令要快速响应
2适应作业不同
①批处理系统已调试好的大型作业
②分时系统正在调试的小型作业
3资源利用率不同
批处理系统可以合理安排不同负载的作业使资源利用率达到最佳作业可分为以计算为主以I/O为主计算与I/O均衡
4作业控制方式不同
①批处理系统用户通过JCB书写作业控制流预先提交脱机工作
②分时系统作业由用户从键盘输入控制命令一交互方式联机工作
3实时操作系统特点及时性和高可靠性 4、操作系统的功能
1处理机管理为了提高处理机的效率操作系统对处理机的管理采用多级调度作业调度、进程调度、线程调度
2存储器管理分区存储管理、页式存储管理、段式存储管理、段页式存储管理
3设备管理
1设备无关性程序中只使用设备的逻辑名屏蔽设备的物理特性方便用户使用
2设备的分配独占型设备、共享型设备、虚拟设备、静态分配、动态分配
3设备传输的控制方式程序查询方式、中断方式、DMA方式、通道方式等
4其它如缓冲技术、SPOOL技术等
4文件管理
1文件的逻辑结构和物理结构
2磁盘空间的管理
3目录管理
4文件操作
5文件的安全与保护 5、操作系统的特征
1并发性指多个时间在同一时间间隔内发生如I/O操作与CPU处理重叠
2共享性
1空分复用如内存中的多道程序、磁盘上的多个文件等
2时分复用如时分系统中的CPU
并发和共享是操作系统的两个最为基本的特征它们互为存在条件一方面若系统不允许并发执行自然不存在资源共享的问题另一方面若不能对资源共享实施有效的管理也将影响到并发执行
3不确定性异步性
只要运行环境相同作业经过多次运行都将获得相同的结果
4虚拟性如虚拟机、虚拟内存、虚拟设备 6、UNIX特性
1UNIX系统是一个多用户、多任务的分时操作系统
2UNIX的系统结构可分为三部分操作系统内核是UNIX系统核心管理和控制中心在系统启动或常驻内存系统调用供程序开发者开发应用程序时调用系统组件包括进程管理、文件管理、设备状态等应用程序包括各种开发工具、编译器、网络通讯处理程序等所有应用程序都在Shell的管理和控制下为用户服务
3UNIX系统大部分是由C语言编写的这使得系统易读、易修改、易移植
4UNIX提供了丰富的、精心挑选的系统调用整个系统的实现十分紧凑、简洁
5UNIX提供了功能强大的可编程的Shell语言外壳语言作为用户界面具有简洁、高效的特点
6UNIX系统采用树状目录结构具有良好的安全性、保密性和可维护性
7UNIX系统采用进程对换的内存管理机制和请求调页的存储方式实现了虚拟内存管理大大提高了内存的使用效率
8UNIX系统提供多种通信机制如管道通信、软中断通信、消息通信、共享存储器通信、信号灯通信 7、在单CPU和两台I/O设备I1、I2的多道程序设计环境下同时投入三个作业job1、job2、job3运行这三个作业对CPU和I/O设备的使用顺序和时间如下
Job1:I2(30ms);CPU(10ms);I1(30ms);CPU(10ms);I2(20ms);
Job2:I1(20ms);CPU(20ms);I2(40ms);
Job3:CPU(30ms);I1(20ms);CPU(10ms);I1(10ms);
假定CPU、I1、I2都能并行工作job1的优先级最高job2次之job3最低优先级高的作业进程可以抢占优先级低的作业进程的CPU但不能抢占I1和I2
试求
1三个作业从投入到完成所需的时间
2从投入到完成的CPU利用率
3I/O设备利用率
解
1 时间 10 20 30 40 50 60 70 80 90 100 110 CPU Job3 Job3 Job2 Job1 Job2 Job3 Job1 Job3 I1 Job2 Job2 Job1 Job1 Job1 Job3 Job3 Job3 I2 Job1 Job1 Job1 Job2 Job2 Job2 Job2 Job1 Job1
Job1从投入到完成需要110ms
Job2从投入到完成需要90ms
Job3从投入到完成需要110ms
2从投入到完成的CPU利用率80/11072.7%
3I1的利用率80/11072.7%
I2的利用率90/11081.8% 第二章
1、处理机的状态
1管态OS的管理程序执行CPU的状态在此状态下允许CPU使用全部的机器资源和全部指令
2用户态用户程序执行时机器所处的状态在此状态下禁止使用特权指令不能直接取用资源和改变机器状态只允许访问自己的存储区域
有些系统将OS执行时机器的状态进一步细分为核心态和管态核心态具有上述管态的所有权限而此时的管态比核心态的权限低只允许使用一些在用户态所不能使用的资源但不能使用修改机器状态的指令
eg.当CPU处于管态时它可以执行的指令应该是计算机系统的全部指令 2、特权指令集
1改变机器状态的指令
2修改特殊寄存器的指令如中断屏蔽寄存器、限界寄存器等
3设计外设的输入/输出指令 3、中断机制
1中断是实现OS功能的基础是构成多道程序运行环境的根本措施中断是OS各种功能的驱动源
2当CPU正在执行程序时出现某种非预期事件CPU暂停当前程序的执行转而为该事件服务当处理完该事件后再继续原来程序的执行这一过程称为中断
3中断的类型
1输入输出中断
如程序中断接口DMA接口通道
2外中断CPU的外部装置所引起的中断
如时钟中断控制台中断
3机器故障中断
如电源故障奇偶校验出错等
4程序性中断
如溢出地址越界地址出错非法操作等
5访管中断对OS提出需求时所发生的中断
例如请求I/O服务各种系统调用如建立进程等
4中断的处理过程
1中断源的识别
2保护断点和现场
3执行中断服务程序
4回复断点和现场 4、假设一个计算机系统具有如下特征处理一次中断平均耗用1ms一次进程调度平均需要2ms将cpu分配给选中的进程又需要平均1ms再假设其定时器芯片每秒产生100次中断请回答
1操作系统将百分之几的CPU时间用于时钟中断处理
2如果操作系统采用轮转法调度10个时钟中断为1个时间片那么操作系统将百分之几的CPU时间用于进程调度包括调度分配CPU和引起调度时的时钟中断处理时间
解1100*1ms/1s10%
2时间片的大小10*1s/100100ms
一个时间片要处理10个时钟中断需要10*1ms10ms
时间片到后再进行一次进程调度需要2ms
再将CPU分配给选中的进程又需要平均1ms
故系统将CPU时间的1012/10013%用于进程调度 第三章用户界面
导致CPU从用户态向核心态转换的情况
1程序请求OS服务执行系统调用
2程序在运行时产生中断或异常事件运行程序被中断转向中断服务程序或异常处理程序 第四章并发处理
1、并发执行程序的特点
1间断性如果Ci-1完成后若Ii未完成则Ci也无法处理导致计算程序段暂停
2失去程序的封闭性程序在并发执行时是多个程序共享系统中的各种资源因而这些资源的状态将由多个程序来改变致使程序的运行失去封闭性
3不可再现性当初始条件相同时程序多次执行其结果必然重复出现称为可再现性 2、进程包括程序段、数据段、栈段、进程控制块
1进程是一个具有独立功能的程序关于某个数据集合的一次运行活动
2从核心看来进程是分了类的根据一组规则操纵的数据结构 3、进程和程序的关系
1进程与程序的联系
1进程程序程序段、数据段、栈段进程控制块PCB
2程序是构成进程的组成部分之一一个进程存在的目的就是执行其所对应的程序
2进程和程序的区别
1程序是静止的进程是动态的有生命周期的
2进程是能独立运行的单位能与其他进程并发执行
3进程是资源分配的基本单位也是CPU调度的基本单位 4、进程的特征
1并发性可以与其他进程在宏观上同时向前推进
2动态性进程是执行中的程序
3独立性进程是资源分配和调度的基本单位
4交互性进程在运行时可能会与其他进程发生直接或间接的相互作用
5异步性每个进程都可以相对独立不可预知的速度向前推进
6结构性每个进程都对应一个进程控制块 5、进程的状态
1就绪状态获得了除CPU以外的所有资源一旦获得CPU控制权就可以立即运行
2运行状态当就绪进程由OS的进程调度程序调度得到CPU控制权占用CPU运行的状态
3等待状态阻塞状态、睡眠状态若某一进程正在等待某一事件的发生而暂时停止这时即使获得CPU控制权也无法执行
4创建态进程刚刚创建如建立PCB完成初始化但未分配内存等资源
5终止态正常结束或异常结束 6、进程控制块PCB包括UNIX的PCBproc结构user结构其中proc结构常驻内存user结构常驻辅存进程执行时调入内存
1进程标识符由OS创建进程时给出要求唯一
2进程的状态作为进程调度时分配处理机的主要依据为了便于对进程实施管理通常把具有相同状态的进程链接在一起组成各种队列如就绪队列、各种等待队列
3当前队列指针指向相同状态的下一个PCB
4总链指针就系统中所有进程的PCB勾链起来
5程序开始地址表示进程的程序从此开始执行
5进程优先级
7CPU现场保护区
8通信信息eg.记录消息缓冲队列指针htpr
9家族信息eg.父进程的标识符ppid 10占有资源清单 7、在进程基本状态转换图中增加换出将进程换出至辅存和换入将进程从辅存换入至主存两个操作试画出进程状态转换图 8、进程控制原语有创建原语、撤销原语、阻塞原语、唤醒原语、延迟原语 9、进程的创建可来源于
1用户向系统提交作业或程序
2OS创建服务进程
3已存在的进程创建新的进程如父进程创建子进程 10、进程的创建过程
1申请一个空闲的PCB
2初始化PCB如进程号、优先级、状态等
3为新的进程分配资源如内存等
4为新进程插入就绪队列 11、引起进程终止的事件
1正常结束如程序执行完毕
2异常结束如溢出
3外界干预如程序执行时用户ctrlbreak 11、引起进程阻塞的事件
1请求OS服务
2请求中断处理
3新的数据还未到达
4无新工作可做 13、进程的相互制约关系
1竞争关系原本不存在逻辑关系的各进程因共享资源而产生的制约关系又称互斥关系eg.学生在图书馆占座位
2协作关系同步一组并发进程为了完成任务需要分工协作这种协作进程之间需要排定执行的先后次序如一个作业分为输入i、计算c、输出p三个过程段 14、进程互斥是指若干进程因相互争夺独占型资源而产生的竞争制约关系
1临界资源一次仅允许一个进程使用的资源独占型资源如打印机、公共变量、链表、数据结构等对临界资源必须互斥使用否则会发生错误
2临界区每个进程中访问临界资源的那段代码又称临界段 15、互斥应遵循的原则
1空闲让进临界资源处于空闲状态时应允许一个请求进入临界区地进程立即进入自己的临界区
2忙则等待当已有进程进入自己的临界区时其它所有试图进入临界区的进程必须等待
3有限等待要求访问临界资源的进程应保证能在有限的时间内进入自己的临界区
4让权等待当进程不能进入自己的临界区时应立即释放CPU以免进程陷入“忙等待” 16、同步机构系统提供了lock(w)和unlock(w)原语
1实现互斥方法之一锁
2对每个临界资源设置一个锁位W按惯例w0表示资源可用w1表示资源已被占用
3当进程使用临界资源之前必须完成上锁操作即w置1当进程使用完临界资源后须开锁操作即w置0
lock(w) {while(w1) {保护当前进程的现场至进程的PCB将当前进程的PCB插入w的等待队列置该进程为“等待”状态转os的进程调度}w1
}unlock(w) {if(w的等待队列不空) {移出等待队列的首元素将该进程插入就绪队列置该进程为“就绪”状态}w0
}
17、信号灯信号量semaphore和P、V操作
struct semaphore{// s初值0其值只能由P、V操作改变int s;// q是初始状态为空的排队站Queue q;
}
// 申请一个资源如果申请不到就进入等待状态
// s0时没有影响
// s0时当前进程由运行状态变为等待状态
P(s) {s--if(s 0) {保留当前进程的现场将该进程插入s的等待队列q中置该进程为“等待”状态转OS的进程调度程序}
}
// 释放一个资源如果有进程因申请不到该资源而等待的话就唤醒一个等待的进程
V(s) {sif(s0) {移出s等待队列q的首元素将该进程插入就绪队列置该进程为“就绪”状态}
}
18、有n个并发进程
1mutex1表示没有进程进入临界区
2mutex0表示有一个进程进入临界区
3mutex-1表示有一个进程进入临界区另一个进程等待进入
4对于n个并发进程分析mutex的取值范围以及每个值的物理意义对于n个并发进程mutex的值可为1、0、-1、……、-n-1当mutex0时|mutex|的值为等待进入临界区的进程数 19、进程同步并发进程在一些关键点上可能需要互相等待或互通消息eg.一组合作进程按逻辑需要所确定的次序执行共享缓冲区或贡献数据的合作进程同步 20、用P、V操作描述进程流图中这3个进程的同步 Semaphore Sa0
Main() {cobeginPa();Pb()Pc();coend
}
Pa() {……V(Sa);V(Sa);
}
Pb() {P(Sa);……
}
Pc() {P(Sa);……
}
21、生产者--消费者问题 同步规则缓冲区空消费者进程等待
缓冲区满生产者进程等待
设置2个同步信号量1个互斥信号量
Semaphore Full0 //表示缓冲区中产品的数目Emptyn //表示空缓冲区的数目Mutex1 //互斥访问有界缓冲区
Main() {CobeginP1();......Pm();C1();......Ck();Coend
}
Pi() {while(1) {生产一个产品P(empty);P(mutex);产品送入缓冲区V(mutex);V(full);}
}
Vj() {while(1) {P(full);P(mutex);从缓冲区中取出产品V(mutex);V(empty);消费一个产品}
}
22、某工厂有两个生产车间和一个装配车间两个生产车间分别市场A、B两个零件装配车间的任务是把A、B两种零件组装成产品。两个生产车间每生产一个零件后都要分别把它们送到装配车间的货架F1、F2上F1存放零件AF2存放零件BF1和F2的容量均可以存放10个零件装配工人每次从货架上取一个A零件和一个B零件然后组装成产品请用PV操作进行正确的管理
解
Semaphore Sa10;Ta0;Sb10;Tb0;M11;M21;
Main() {CobeginworkshopA();workshopB();workshopC();Coend
}
workshopA() {while(生产未完成) {生产A产品P(Sa);P(M1);放入A产品货架V(M1);V(Ta);}
}
workshopB() {while(生产未完成) {生产B产品;P(Sb);P(M2);放入B产品货架V(M2);V(Tb);}
}
workshopC() {while(装配未完成) {P(Ta);P(M1);取出A产品V(M1);V(Sa);P(Tb);P(M2);取出B产品V(M2);V(Sb);装配产品}
}
23、过独木桥问题
//互斥独木桥
Semaphore bridgemutex1; //互斥count1M11; //互斥count2M21;
//记录从西向东的过桥人数
int count10; //记录从东向西的过桥人数count20;
Main() {CobeginWest_easti() ;East_westj();Coend
}
West_easti() {P(M1);count1;//第一个人上桥时封装对向上桥if(count11)P(bridgemutex); V(M1);从西向东过桥P(M1);count1--;// 最后一个人下桥时解封对象上桥if(count10)V(bridgemutex);V(M1);
}
East_westj() {P(M2);count2;// 第一个人上桥时封锁对向上桥if(Count21)P(bridgemutex);V(M2);从东向西过桥P(M2);count2--;// 最后一个人下桥时解封对象上桥if(count20)V(bridgemutex);V(M2);
}
24、下面的描述中ABD是正确的
A、进程执行的相对速度不能由自己来控制
B、P、V操作都是原语操作
C、利用信号量的P、V操作可以交换大量信息
D、同步是并发进程之间存在的一种制约关系
解利用信号量的P、V操作是为了实现互斥而不是交换大量信息 第五章死锁
1、死锁是指多个进程因竞争资源而造成的一种僵局若无外力作用这些进程都将永远不能再向前推进 2、产生死锁的原因
1系统资源不足根本原因
2进程推进顺序非法 2、产生死锁的四个必要条件
1互斥条件在一段时间内某资源只能有一个进程占有如果此时还有其他进程要求该资源要求者只能阻塞直到占有该资源的进程用毕释放即资源是互斥的独木桥一次仅允许一个人对向通过
2不剥夺条件进程获得的资源再未使用完之前不能被其他进程剥夺只能由自己释放不能将对方推下桥
3部分分配条件在等待一新资源的同时进程继续占有已分配到的资源都已占据桥面等待对方让开
4环路条件即进程集合{P1、P2、……、Pn}中P1等待P2占有的资源P2等待P3占有的资源……Pn等待P1占有的资源形成环路互相等待对方的位置 4、解决死锁问题的策略
1静态预防死锁
1破坏“互斥条件”难以否定
2破坏“不剥夺条件”若某进程的资源申请被拒绝时则必须释放所有已获得如果需要再和其他资源一起申请
3破坏“部分分配条件”各进程所需要的全部资源只能一次申请并且在没有获得全部资源之前进程不能投入运行
4破坏“环路条件”系统将所有的资源按类型进行编号所有进程对资源的请求必须按资源的序号递增或递减的次序提出这样所形成的资源分配图中不可能出现环路
由于所施加的限制条件太严格可能导致系统资源利用率和系统吞吐量降低
2动态避免死锁
在资源的动态分配中用某种方法防止系统进不安全状态从而避免死锁发生最具代表性的是“银行家算法”
eg.假定系统有五个进程{P0、P1、P2、P3、P4}和三类资源{A、B、C}数量为{10、5、7}在T0时刻的资源分配情况如下 进程\资源 MAX A B C Allocation A B C Need A B C Available A B C P0 7 5 3 0 1 0 7 4 3 P1 3 2 2 2 0 0 1 2 2 3 3 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1
1T0时刻的安全性
2P1请求资源Request1(102)
3P4请求资源Request4(330)
4P0请求资源Request0(020);
解1 进程\资源 Work A B C Need A B C Allocation A B C WorkAllocation A B C P1 3 3 2 1 2 2 2 0 0 5 3 2 P3 5 3 2 0 1 1 2 1 1 7 4 3 P4 7 4 3 4 3 1 0 0 2 7 4 5 P0 7 4 5 7 4 3 0 1 0 7 5 5 P2 7 5 5 6 0 0 3 0 2 10 5 7
故T0时刻存在一个安全序列{P1、P3、P4、P0、P2}故系统是安全的
2若进程P1请求资源Req102银行家算法判断如下
①判断Req102Need1122表示Req为合法请求
②判断Req102Available332表示Req为可满足的请求
③试探性分配Available-Req变为230
AllocationReq变为302
Need-Req变为020
④新状态的安全性 进程\资源 Work A B C Need A B C Allocation A B C WorkAllocation A B C P1 2 3 0 0 2 0 3 0 2 5 3 2 P3 5 3 2 0 1 1 2 1 1 7 4 3 P4 7 4 3 4 3 1 0 0 2 7 4 5 P0 7 4 5 7 4 3 0 1 0 7 5 5 P2 7 5 5 6 0 0 3 0 2 10 5 7
故新状态是安全的可找到安全序列{P1、P3、P4、P0、P2}因此可以分配资源Available变为230
3若进程P4请求资源Req330银行家算法判断如下
①判断Req330Need4430表示Req为合法请求
②判断Req330Available230可知Request不是可满足的请求故新状态是不安全的因此不能满足进程P4的资源请求Req330
4若进程P0请求资源Req020银行家算法判断如下
①判断Req020Need0743表示Req为合法请求
②判断Req020Available332表示Req为可满足的请求
③试探性分配Available-Req变为210
AllocationReq变为030
Need-Req变为723
④新状态的安全性因为Available210不能满足任何进程的资源需求即找不到安全序列此时系统进入不安全状态因此不能满足进程P0的资源请求Req020
3检测死锁/解除死锁
预先不采取任何限制性的措施也不检查系统是否进入不安全状态允许系统在运行过程中发生死锁但可通过系统设置的检测机构及时地检测出死锁地发生并精确地确定与死锁有关地进程和资源然后采取适当地措施从系统中将已发生死锁清除掉如撤销或挂起一些进程以便回收一些资源再将这些资源分配给已处于阻塞状态地进程使之转为就绪状态继续运行 第六章处理机调度
1、处理机调度
1为了提高处理机的效率处理机采用多级调度
2用户作业从进入系统成为后备作业开始直到运行结束退出系统为止需要经过不同级别的调度
3批处理OS可能经历作业调度、进程调度、线程调度
4分时OS可能经历进程调度、线程调度 2、作业的状态
1后备状态作业在辅存上并建立JCB等待调度
2执行状态作业进入主存到作业计算完成为止
3完成状态从作业计算完成开始到善后处理完毕并退出系统为止 3、作业调度的功能主要是完成作业从后备到执行、执行到完成状态的转变当作业处于执行状态时其对应的进程不一定处于执行状态 4、调度目标这些目标本身有些是相互冲突的
1对所有作业应该是公平合理的
2应使设备有高的利用率
3系统吞吐量大
4有较快的响应时间 5、作业调度算法
1先来先服务调度算法FCFS算法作业按来到的先后次序进行调度对短作业不利
2短作业优先调度算法SJF算法从后备作业中选择执行时间最短的作业作为下一次服务的对象只照顾短作业的利益而不考虑长作业的利益
3相应比高者优先调度算法相应比rp等待时间/执行时间当调度时需计算后备作业的响应比然后选择相应比高者投入运行每次需要调度时都要计算响应比较复杂 6、一个单处理机分时系统收到了三个作业作业的提交情况见下表 作业 作业提交时间 运行时间 I/O时间 CPU时间 A 10.0 0.36 0.18 0.18 B 10.2 0.32 0.16 0.16 C 10.4 0.36 0.18 0.18
现假设在单CPU上分时运行两道作业时若每道作业的I/O等待时间皆占各种总运行时间的50%则CPU将有20%的时间空闲请写出各个作业的结束时间为计算方便时间采用十进制
分析当有一道作业时CPU有50%的时间空闲50%的时间计算
当有两道作业时CPU有20%的时间空闲80%的时间计算
解10.0-10.2时间段内作业A到达一道作业作业A计算0.1还需要0.08
10.2-10.4时间段内作业B到达两道作业0.2*80%0.16的CPU时间计算作业A和作业B分别使用CPU各使用0.08故10.4时作业A结束作业B还需0.08
10.4-10.6时间段内作业C到达两道作业0.2*80%0.16的CPU时间计算作业B和作业C分别使用CPU各使用0.08故10.6时作业B结束作业C还需0.1
10.6时间以后一道作业CPU有50%的时间空闲50%的时间计算故0.2*50%0.110.8时作业C结束
因此作业A的结束时间为10.4
作业B的结束时间为10.6
作业C的结束时间为10.8 7、进程调度的时机的可能情况
1正在执行的进程执行完毕
2执行的进程因中断调用、自陷、请求I/O服务等而阻塞
3在分时系统中进程分配的时间片用完
4在可剥夺方式中有优先级更高的进程要求处理 8、静态优先权在进程建立时确定且规定他在进程的整个运行期间保持不变确定优先级的依据
1进程所需资源的要求如进程的执行时间及内存需要量少的应赋予较高的优先级
2进程类型如系统进程的优先权应高于用户进程
3根据用户类型如按用户付费用的多少来确定优先权 9、动态优先权在进程创建时所赋予的优先权可以随着进程的推进而改变以便获得更好的调度性能 10、进程的两个基本属性
1进程是一个可拥有资源的独立单位
2进程又是一个可以独立调度和分配CPU的基本单位 11、由于进程是一个资源拥有者因而在进程的创建、撤销和切换中涉及资源的释放系统必须付出较大的时空开销正因如此在系统中所设置的进程数目不宜过多进程切换的频率也不宜过高但这也限制了并发进程的进一步提高 12、1进程作为资源分配的基本单位
2线程是在进程内用于调度和占有CPU的基本单位
3每个线程可以用一个现场表示现场由PC、GR、PSW组成这样线程切换时就不涉及资源的分配和释放 13、当一个线程执行时它只有一个线程如果需要进程可以继续创建新的线程也就是一个进程可以包含多个控制线程每个线程运行进程中的一个程序段这样进程就有多个执行路径增强了并行处理能力线程完全继承父进程占有的资源但它活动时具有自己的运行现场 14、线程与进程的比较
1调度
线程作为CPU调度的基本单位进程作为资源调度的基本单位
在同一进程中线程的切换不会引起进程的切换由一个进程的线程切换到另一个进程的线程时将会引起进程的切换
2并发性
在引入线程的OS中不仅进程之间可以并发执行而且一个进程中的多个线程之间也可并发因而使OS具有更好的并发性从而能更有效地使用系统资源和提高系统的吞吐量
3拥有资源
进程是拥有资源的一个独立单位线程自己不拥有系统资源也有一点必不可少的资源但可访问其隶属进程的资源即一个进程的代码段、数据段及系统资源可供同一进程的所有线程共享
4系统开销
线程切换只需保存和设置少量寄存器的内容并不涉及存储器管理方面的操作进程切换的开销远大于线程切换的开销远大于线程切换的开销 15、线程的状态及变迁
1创建建立的新生线程处于新建状态已完成初始化
2就绪进入线程就绪队列一旦分到CPU时间就可立即运行
3运行一个线程正占用CPU执行它的程序
4等待让出CPU暂时终止自己的执行进入等待状态
5终止一个线程已经退出当该信息还未被其他线程所收集 16、在一个两道批处理系统中有一作业序列其到达时刻/估计运行时间列表及优先数如下 作业 到达时刻 估计运行时间分钟 优先数 JA 1000 40 5 JB 1020 30 3 JC 1030 50 4 JD 1050 20 6 JE 1100 30 2
假设作业调度采用短作业优先的调度算法进程调度采用以优先数为基础的抢占式调度算法表中所列优先数即为进程优先数数值越小优先级越高哪个作业短就调入哪个作业然后再通过优先级判断处理哪个作业
1列出各作业的执行时间即列出每个作业运行的时间片段例如作业i的运行时间序列为1000-1040、1100-1120、1130-1150结束
2计算这批作业的平均周转时间和带权平均周转时间
解1
1000 JA到达JA进入内存PA执行
1020 JB到达JB进入内存JB的优先级更高PB执行此时PA已执行20分钟还需20分钟
1030 JC到达JC后备
1050 JD到达JD后备JD进入内存JB终止PB完成PA执行
1100 JE到达JE后备
1110 JA终止PA完成JE进入内存PE执行
1140 JE终止PE完成JC进入内存PC执行
1230 JC终止PC完成PD执行
1250 JD终止PD完成
故 运行时间 平均周转时间 带权平均周转时间 JA 1000-10201050-1110 70 1.75 JB 1020-1050 30 1 JC 1140-1230 120 2.4 JD 1230-1250 120 6 JE 1110-1140 40 1.33
2
这批作业的平均周转时间为703012012040/576
带权平均周转时间1.7512.461.33/52.496 17、在一个两道批处理系统中有一作业序列其到达时刻及估计运行序列如下 作业 到达时刻 估计运行时间分钟 1 1000 35 2 1010 30 3 1015 45 4 1020 20 5 1030 30
系统采用最高响应比优先的作业调度算法响应比等待时间/估计运行时间作业进程的调度采用短作业优先的抢占式调度算法即根据相应比决定调入哪个作业进入内存然后根据短作业优先算法决定处理哪个作业
1列出各作业的执行时间即列出每个作业运行的时间片段
2计算这批作业的平均周转时间
解11000 J1到达J1进入内存P1执行
1010 J2到达J2进入内存此时P1已经执行了10分钟还需25分钟
1015 J3到达J3后备此时P1还需20分钟
1020 J4到达J4后备此时P1还需15分钟
1030 J5到达J5后备此时P1还需5分钟
1035 J1终止P1完成J4进入内存P4执行
1055 J4终止P4完成J3进入内存P2执行
1125 J2终止P2完成J5进入内存P5执行
1155 J5终止P5完成P3执行
1240 J3终止P3完成 作业 运行时间 周转时间分钟 J1 1000-1035 35 J2 1055-1125 75 J3 1155-1240 145 J4 1035-1055 35 J5 1125-1155 85
2这批作业的平均周转时间为35751453585/575分钟 第七章主存管理
1、主存管理的主要功能
1逻辑地址到物理地址的映射
2主存的分配和回收
3存储保护保护进入主存的各道作业都在自己的存储空间内运行互不干扰防止一道作业由于发生错误而破坏其他作业或系统程序
4提高主存利用率使多道程序能动态共享主存中的信息如段式系统中代码段是可共享的
5“扩大”主存容量借助虚拟存储技术为用户提供比主存空间大的地址空间 2、分区存储管理
固定分区将内存用户区划分为若干固定大小的区域每个区域中驻留一道程序
动态分区根据用户程序的大小动态对内存进行划分可以提高内存的利用率 3、分区的分配和回收
1首次适应算法
空闲区队列中空闲区按地址从小到大排序
2最佳适应算法
空闲区队列中空闲区按大小从小到大排序
3最坏适应算法
空闲区队列中空闲区按大小从大到小排序
4、回收空闲块
上邻空闲区空闲区总数不变
下邻空闲区空闲区总数不变
上、下邻空闲区空闲区总数减一
上、下不相邻空闲区空闲区总数加一 5、什么时候进行拼接
回收一个分区时立即拼接这样主存中总是只有一个连续的空闲区而无碎片开销大
当找不到足够大的空闲区而空闲区总和可以满足作业需求时拼接开销小但空闲区管理复杂 6、拼接技术的缺点
拼接程序花费CPU时间
拼接时必须停止所有的其他工作对于交互用户导致响应时间不规律对于实时用户由于不能及时响应而可能造成严重后果
有时为拼接所花费的系统开销要大于拼接技术带来的效益
当所有空闲区之和无法满足某一作业需求时该作业永远无法运行 7、虚拟存储器的大小受以下因素限制
一定容量的主存
大容量的辅存存放多道程序
地址变换机构如虚地址要放入地址寄存器如果地址寄存器为32位则虚存最大为2^324G 8、虚拟存储器的最大容量是由计算机系统的地址结构和外存空间决定的即等于min计算机地址内存辅存 9、缺页中断与一般中断的区别
缺页中断发生在指令的执行过程中一般中断发生在指令周期之后
一条指令的执行可能有多次缺页中断 10、页表 页号 块号 中断位i 辅存地址 改变位 引用位
1中断位i用来标示该页是否在内存
i0此页不在主存
i1此页不在主存请求调入
2辅存地址表示该页在辅存中的位置
3改变位用来标示该页最近是否被修改过
改变位0表示该页最近未被修改过淘汰时该页不写回辅存
改变位1表示该页最近被修改过淘汰时该页需要写回辅存全写法、写回法、写一次法
4引用位用来标示该页最近是否被访问过
引用位0表示该页最近没有被访问过
引用位1表示该页最近已被访问过 11、置换算法
1最佳算法optimal算法淘汰的页面将是永不使用或者是在最长时间内不再被访问的页面
2先进先出算法FIFO算法总是选择在主存中居留时间最长的一页淘汰
3LRU算法当需要淘汰一页时选择最长时间未被使用的那一页淘汰掉
LRU近似算法clock算法页表中每个主存块号有一个“引用位”当某块中的页面被访问时“引用位”置“1”而页面管理程序周期性设周期为T地将所有“引用位”重新置“0”这样在T时间内被访问页面的“引用位”为“1”未被访问页面的“引用位”为“0”当需要置换一页时选择“引用位”为“0”的页淘汰掉
缺点①T太大可能所有块为“1”
②T太小可能“引用位”为“0”的块相当多
③若缺页中断发生在页面管理程序将所有“引用位”清零时有可能将常用的页面淘汰掉 12、抖动颠簸导致系统效率急剧下降的主存和辅存之间的频繁页面置换现象 13、抖动的预防
1采用局部置换策略
当进程发生缺页后仅在自己的内存空间范围内置换页面不允许从其它进程获得新的物理块
缺点
1不能从根本上防止抖动的发生
该进程发生抖动后会长期处于磁盘I/O的等待队列从而影响了其他进程的缺页中断的处理时间
2当多道程序度偏高时挂起一些进程
如优先级低的缺页进程剩余执行时间较大的进程等
3在调度程序中引入工作集算法工作集又称驻留集在某段时间间隔内进程要访问的页面的集合仅在每个进程在内存中都有足够大的驻留集时才能从外存调入新的作业这样才不致因新作业的调入而导致缺页率的增加
4LS准则用于调整多道程序的道数使产生缺页的平均时间L等于处理缺页的平均时间S此时CPU的利用率最大 14、在页式系统中若采用FIFO页面淘汰算法会产生一种奇怪的现象分配给作业的内存块越多进程执行时的缺页率反而越高也称为“Belady现象” 15、段表 段号 段长 段首址 中断位 辅存地址 引用位 改变位 RWEA 其他
1中断位i用来标示该段所在位置
i0此段在内存
i1此段在外存
2辅存地址表示该段在辅存中的位置
3改变位用来标示该段最近是否被修改过
改变位0表示该段最近未被修改过淘汰时该段不写回辅存
改变位1表示该段最近被修改过淘汰时该段需要写回辅存全写法、写回法、写一次法
4引用位用来标示该段最近是否被访问过
引用位0表示该段最近没有被访问过
引用位1表示该段最近已被访问过
RWEA存取方式保护
R表示读权W表示写权E表示执行权A表示可添加 16、段式和页式管理的比较
1每个段是一段有意义的信息段长可动态增加每个页的信息无意义页长固定不变
2段式管理中以分段为单位交换页式管理中需多次缺页中断才能把所需信息完整调入内存
3段式便于对具有完整逻辑功能的信息段进行共享而页式管理的共享实现较难
4段式管理便于实现动态链接可用段名加上段入口地址等方法在执行过程中调入相应的段进行动态链接
5段式系统便于共享和存储保护但存在碎片问题且每个段的长度受内存可用区大小的限制
6页式管理克服了碎片但不利于共享 17、段页式管理
1要得到指令或数据的物理地址须经过二次访问主存访问段表得到页表起始地址访问页表得到主存块号
2中断位在页表设置存取保护在段表设置
3引用位、修改位在页表设置
4不同进程的段表中如果段号指向相同的页表地址则可以实现该段的共享 18、页和页表
1内存划分为大小相同的块
2每个区划分为大小相同的页面典型的页面大小为1KB、2KB或4KB
3块的大小页的大小
4页可以在内存中不连续存放所以需要为每个区建立一个页表 19、在一个页式虚拟存储内存管理系统中页面大小为1K字节某个进程分配到的内存块数为3并按下列地址顺序引用内存单元1200215218650506453613960030330007331860上述数字均为十进制数且开始时内存中尚未装入任何页试用先进先出FIFO和最近最久未使用LRU两种置换算法分别计算程序访问过程中所发生的缺页率
解根据页面大小和引用单元地址请求页面的应用次序为1210410301当分配的内存块数为3时采用FIFO和LRU置换算法的页面载入及替换情况如下
FIFO算法 页面号 1 2 1 0 4 1 0 3 0 1 内存块1 1 2 2 0 4 1 1 3 0 0 内存块2 1 1 2 0 4 4 1 3 3 内存块3 1 2 0 0 4 1 1 是否发生缺页 × × × × × × ×
缺页率7/1070%
LRU算法 页面号 1 2 1 0 4 1 0 3 0 1 内存块1 1 2 1 0 4 1 0 3 0 1 内存块2 1 2 1 0 4 1 0 3 0 内存块3 2 1 0 4 1 1 3 是否发生缺页 × × × × ×
缺页率5/1050% 20、某计算机系统采用二级页表的分页存储管理方式虚拟地址格式如下所示 10位 10位 12位 页目录号 页表索引 页内地址
回答下列问题
1逻辑地址的页页面大小和物理地址的块页框大小各为多少进程的虚拟地址空间大小为多少页
2若某指令周期内先后访问了虚拟地址0100 0000H和0111 2048H则进行地址转换时共访问了多少个二级页表要求说明理由 解1逻辑地址的页大小和物理地址的块大小各为4KB进程的虚拟地址空间大小为2^32B含有2^32/2^122^20页
2只需要访问一个二级页表因为虚拟地址0100 0000H和0111 2048H的最高10位的值都是4访问的是同一个二级页表 21、某计算机采用二级页表的分页存储管理方式按照字节编址页大小为2^10字节页表项为2字节逻辑地址结构为 页目录号P1 页号P2 页内偏移地址w
逻辑地址空间大小为2^16页则整个逻辑地址空间的页表目录中包含的表项数是多少
解因为页大小为2^10字节页表项为2字节
故页表项数为2^10/2 2^9即页号P2为9位
因为逻辑地址空间大小为2^16页所以P1P216位即P17位
故页表目录中包含的表项数为2^7128项 22、已知一个采用了LRU置换算法的虚拟页式存储管理系统其页面尺寸为4KB内存访问速度为100ns/次快表访问速度为20ns/次缺页中断处理时间为25ms/次今有一个长度为30KB的进程进入系统分配给该进程的内存块有3块进程的所有页面都是在该进程运行中动态装入若访问快表的命中率为20%对于下属页面号访问序列
70120304230321201701
请问1该进程有多少个页面
2计算平均有效访存时间为多少
解1该进程有30KB/4KB7.25故页面数为8
2LRU算法 页面号 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 内存块1 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 内存块2 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 内存块3 7 0 1 2 2 3 0 4 2 2 0 3 3 1 2 0 1 7 是否缺页 × × × × × × × × × × × ×
平均有效访存时间T1-p*map*缺页中断处理时间
其中p为缺页率ma为不缺页的平均访问时间
p12/200.6
ma201000.2100100*0.8184ns
T0.4*0.1840.6*2500015000.0736μs 23、在一请求分页系统中页面大小为1K一作业共有7个页面为作业分配4个物理块其中页面0123分别装入到物理块2641中
试写出页面3中的语句MOV AX[2700]在执行过程中的地址变换的过程
若作业的页面走向为0 1 2 3 2 1 3 2 5 2 3 6 2 1 4 2并采用LRU页面置换算法试计算缺页中断次数
解1逻辑地址LA27001K*2652可知页号为2页内偏移W652
查页表可知页块号为4
物理地址pa1K*46524748
2LRU算法 页面号 0 1 2 3 2 1 3 2 5 2 3 6 2 1 4 2 内存块1 0 1 2 3 2 1 3 2 5 2 3 6 2 1 4 2 内存块2 0 1 2 3 2 1 3 2 5 2 3 6 2 1 4 内存块3 0 1 1 3 2 1 3 3 5 2 3 6 2 1 内存块4 0 0 0 0 0 1 1 1 5 5 3 6 6 是否缺页 × × × ×
已知页面0 1 2 3已经装入内存故一共产生缺页中断4次 24、有一矩阵VAR A:ARRAY[1..1001..100]OF integer按先行后列次序在辅存存储在一个虚拟系统中采用LRU淘汰算法一个进程有3块内存空间可以存放200个整数其中第一块存放次序且假定次序已经在内存
程序AFOR i:1 TO 100 DO
FOR j:1 TO 100 D0
A[i,j]:0
程序BFOR j:1 TO 100 DO
FOR i:1 TO 100 D0
A[i,j]:0
分别就程序A和B的执行过程计算缺页次数
解数组A共有100*100个变量每页可存放200个共占100*100/20050页
程序A对页面的访问顺序
发生缺页中断次数为50次
程序B对页面的访问顺序
发生缺页中断次序为50*1005000次 第八章输入输出管理
1、I/O设备的分类
1按操作特性分类
1存储设备存储信息的设备
2I/O设备向CPU输入信息和输出经加工处理的信息
2按信息交换单位分类如UNIX系统采用
1字符设备信息传送的单位是字节
2块设备信息传送的单位是块如512B整数倍/块
3按共享属性分类
1独占设备在一段时间内只允许一个进程访问的设备如打印机
2共享设备在一段时间内可允许多个进程访问的设备如磁盘
3虚拟设备通过虚拟技术将一台独占设备变换为若干台逻辑设备供若干个用户使用通常将经过虚拟技术处理后的设备称为虚拟设备如虚拟打印机 2、I/O设备管理的功能目标方便用户的使用提高设备利用率
1状态跟踪由设备控制块DCB动态记录设备状态的变化及有关信息
2设备存取与分配按照设备类型和相应的分配算法决定将I/O设备分配给哪一个要求该设备的进程
1静态分配作业进入系统时就进行分配退出系统时就收回全部资源
2动态分配进程需要使用某设备而提出申请时进行分配使用完毕后立即将其收回
3设备控制将用户的I/O请求转换为设备能识别的I/O指令并实施设备驱动和中断处理工作主要由设备驱动程序完成
4实现其它功能缓冲区的管理实现设备的独立性 3、设备独立性是指用户在编制程序时所使用的设备与实际使用的设备无关也就是用户程序中仅仅使用逻辑设备名 4、设备独立性的优点
1屏蔽了设备的物理特性方便用户使用
2改善了资源的利用率
3提高了系统的可扩展性和可适应性 5、设备控制块是记录设备的硬件特性、链接和使用情况等信息的数据结构当设备装入系统时DCB被创建基本内容由
1设备名
2设备属性描述设备现行状态的一组属性如
1传输速度
2工作方式如全双工半双工
3校验方式如奇偶校验、CRC校验
4延迟时间
3指向命令转换表的指针每个I/O请求都要转换成调用一个能执行I/O操作的设备例程
4在I/O总线上的设备地址每个设备都有地址可以采用统一编址也可以采用单独编址
5设备状态如设备控制器或通道忙或空闲
6当前用户进程指针当前正在使用该设备的进程
7I/O请求队列指针指向因请求设备而未得到满足的进程队列 6、缓冲区在内存中划出一块存储区专门用来临时存放I/0数据 7、在OS中引入缓冲的主要原因
1缓和CPU和I/O设备间速度不匹配的矛盾
2减少对CPU的中断频率放宽对中断响应时间的限制eg.假设每传送1bit便中断1次如果增加一个8位的寄存器当传输1B时才中断1次否则需要中断8次
3提高CPU和I/O设备的并行性 8、缓冲技术分为
1单缓冲
2双缓冲为输入或输出分配两个缓冲区交替使用使CPU与设备的并行操作进一步提高
3环形缓冲
4缓冲池从主存中分配一组缓冲区组成缓冲池为了提高缓冲区的利用率广泛采用公共缓冲池池中缓冲区可供多个进程共享使用缓冲池的主要原因是避免消费者多次访问相同的数据时会重复产生相同数据的问题 9、缓冲区按使用情况分类
1空缓冲队列
2输入队列由装满输入数据的缓冲区所链成的队列
3输出队列由装满输出数据的缓冲区所链成的队列 10、设备分配方式及安全性
1静态分配是作业开始执行之前由系统一次分配该作业所要求的全部设备直到该作业被撤销独占设备一般采用静态分配但设备的使用效率低由于破坏“部分分配条件”静态分配方式不会出现死锁
2动态分配是进程在执行过程中需要设备时通过系统调用命令像系统提出设备请求系统按照分配策略实施分配一旦I/O完成就释放该设备共享设备采用动态分配方法有利于提高设备利用率
1当进程发出I/O请求后便立即进入阻塞状态直至I/O请求完成后才被唤醒此时一个进程只能提出一个I/O请求因而它不可能同时操作多个外部设备由于破坏了“环路条件”因此不会死锁
2允许某些进程发出I/O请求后仍可继续运行且在需要时又可发出多个请求仅当进程所请求的设备为另一个进程占用时才进入阻塞状态在一个进程同时操作多个设备的情况下是有可能出现死锁的 11、SPOOL技术外设联机同时操作技术、假脱机技术
1预输入在作业执行之前OS已将作业信息通过独占设备预先输入到磁盘上称为“预输入”此后作业执行使用数据时不必再启动独占设备读入而只要从磁盘输入数据就可以了
2缓输出在作业执行时也不必直接启动独占设备输出数据而只要将作业输出数据写入磁盘中存放在作业执行完毕后由OS来组织信息输出称为“缓输出”
3特点
1提高了I/O速度缓和了CPU与低速I/O设备的矛盾
2将独占设备改造为共享设备
3实现了虚拟设备功能 12、I/O控制方式
1程序循环测试I/O方式
2中断方式
3DMA方式
4通道方式 13、控制设备I/O工作的核心模块称为设备驱动程序设备驱动程序与设备类型是一一对应的对于某一类设备OS具有相同的设备驱动程序 14、设备驱动程序包括
1I/O接口程序把逻辑设备映射为相应的物理设备检查提供给它的参数的正确性启动所需要的服务
2I/O处理进程从I/O请求队列中取出iorb启动相应的I/O操作然后进入等待状态直至I/O完成当设备的I/O完成后发出中断信号启动中断服务程序进行数据的传送然后唤醒I/O处理进程由I/O处理进程把数据送到目的地然后删除此iorb唤醒请求I/O的用户进程I/O处理进程一般处于阻塞状态
3中断服务程序可以由硬件厂商提供由程序设计人员完成 15、磁盘调度算法
1先来先服务FCFS按进程访问磁盘的先后次序进行调度缺点未对寻道进行优化
2最短寻道时间优先SSTF选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象缺点某些进程的请求总也得不到服务
3扫描算法SCAN电梯调度算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象
4循环扫描算法CSCAN它规定磁头单向移动 16、在某个运行时刻有如下表示的磁盘访问的请求队列假设磁头当前在第15个柱面磁头移动方向为从小到大 请求序列 柱面号 1 15 2 20 3 9 4 16 5 24 6 13 7 29
请给出
1最短寻道时间优先算法和电梯调度算法的柱面移动数
2分析OS并不采用效率更高的最短寻道时间优先法的原因
解1SSTF算法 请求柱面号排序 下一个磁道号 移动磁道数 9 20 11 13 9 4 -15 16 1 16 13 3 20 24 4 24 29 5 29
总共柱面移动数为28道
SCAN算法 请求柱面号排序 下一个磁道号 移动磁道数 9 13 9 4 -15 16 1 16 20 4 20 24 4 24 29 5 29 13 16
总共柱面移动数为34道
2由于磁头在读写操作的过程中可能不断有新的读写柱面的请求加入最短寻道时间优先算法会使柱面两端的请求处于“饥饿态”故一般不采用最短寻道时间优先法电梯调度算法比较公平 17、多道程序系统中供用户使用的内存空间有100KB磁带机2台打印机1台系统采用可变式分区分配方式管理内存对磁带机和打印机采用静态分配方式并假设输入/输出操作的时间忽略不计。现有一作业序列如下 作业号 到达时间 要求计算时间 要求内存量 申请磁带机数 申请打印机数 1 800 25min 15K 1台 1台 2 820 10min 30K - 1台 3 820 10min 60K 1台 - 4 830 20min 20K 1台 - 5 835 15min 10K 1台 1台
假设作业调度采用FCFS算法优先分配内存的底地址区域且不准移动已在内存中的作业在内存中的作业平分CPU时间试问
1作业调度的次序是什么
2写出所有作业的周转时间。
解1
800 J1到达J1进入内存P1执行磁带机还剩一台
820 J2到达J2后备 J3到达J3进入内存P1、P3分时执行 P1已执行20分钟还需5分钟 此时还剩磁带机0台打印机0台
830 P1终止J1完成 P3已执行5分钟还需15分钟 归还设备此时还剩磁带机1台打印机1台 J4到达J4进入内存P3、P4分时执行 此时还剩磁带机0台打印机1台
835 J5到达J5后备
900 P3终止J3完成 P4已执行15分钟还需5分钟 归还设备此时还剩磁带机1台打印机1台 J2进入内存P2、P4分时执行 此时还剩磁带机1台打印机0台
910 P4终止J4完成 P2已执行5分钟还需5分钟 归还设备此时还剩磁带机2台打印机0台
915 P2终止J2完成 归还设备此时还剩磁带机2台打印机1台 J5进入内存P5执行
930 P5终止P5完成
故作业调度的次序是1、3、4、2、5
2
作业1的周转时间为830-80030min
作业2的周转时间为915-82055min
作业3的周转时间为900-82030min
作业4的周转时间为910-83040min
作业1的周转时间为930-83555min 第九章文件系统
1、文件是具有文件名的且在逻辑上具有完整意义的信息的集合 2、文件系统是OS中负责管理和存取文件信息的软件机构它由管理文件内所需的数据结构如文件控制块、目录表、存储分配表和相应的管理软件以及访问文件的一组操作所组成 3、文件系统的功能
1用户可以对文件进行操作如创建、删除、读写文件等
2可以共享彼此的文件如链接
3提供存取控制如R、W、X等权限
4实现辅存空间的自动管理
5按文件名访问
6提供后备与复原能力如回收站
7保密功能如文件口令、文件加密
8界面友好 4、文件的逻辑结构这是从用户观点出发所观察到的文件组织形式是用户可以直接处理的数据及其结构它独立于物理特性 5、文件的物理结构是指文件在外存上的存储组织形式它与存储介质的存储特性有关存储介质通常划分为大小相同的物理块物理块是分配和存储信息的基本单位如磁盘块的大小是512B的整数倍1KB/块、4KB/块为便于管理一般也把文件信息划分为与物理块大小相等的逻辑块 6、文件的逻辑结构可以分为
1记录式文件有结构的文件由一组相关记录组成记录的长度可分为定长和不定长两类
1定长记录文件文件中所有记录的长度都是相同的如数据库中的表文件
2不定长记录文件文件中各记录的长度不尽相同
2流式文件无结构的文件流式文件是相关的有序字符的集合文件的长度即为所含字符数如C语言的源程序、写字板的.TXT文件等 7、文件的存取方式
1顺序存取如磁带文件
2随机存取如磁盘文件 8、文件的物理结构可分为
1连续文件将文件信息依次存放在外存连续的物理块中特点顺序存取速度快但文件存储要求连续的存储空间会产生碎片同时也不利于文件的动态扩充
2串联文件文件存储的物理块不必连续在每个物理块的最后一个字做为指针指向下一个物理块的位置特点没有外存碎片动态增删比较方便但串联文件只能按照文件的指针顺序访问因而查找效率较低
3索引文件为了能随机的访问文件的任何一部分可以采用索引文件结构每个文件需建立一个索引表索引表中的每个表项为文件的逻辑块号和与之对应的物理块号可以存储文件的最大长度直接寻址一次间址二次间址三次间址如何提高存储文件的最大长度系统安装时增加磁盘块的大小如4KB、8KB或16KB 9、索引文件在存储区占两个区索引区和数据区访问索引文件的步骤
1查索引表由逻辑块号得物理块号
2由物理块号访外存获得所要求的信息
3特点可以随机访问易于进行文件的增删但索引表的使用增加了存储空间的开销文件操作需要两次访问外存 10、文件映照结构文件分配表FAT 引导块 文件目录区 文件映照图文件分配表 数据区
1系统有文件映照图图中每个表项用来记录磁盘块号勾链字
2每个文件的文件目录项中用户描述文件物理结构的表项指向文件映照图的某个位置其内容为该文件的第一块的块号其后的各块在文件映照图中依次勾链文件的最后一块用尾标记表示
3特点存储链指针需要一定的存储空间文件映照图一般比较大不宜保存在主存在最坏情况下可能要把整个文件映照图全部读入主存才能找到文件在磁盘中的所有物理块所以把文件所占的磁盘空间尽量靠近是有利的而不应将文件散布在整个磁盘上如定期做碎片整理工作 11、文件存储空间的管理实质上是空闲块的组织与管理等它包括空闲块的组织、分配和回收等 12、空闲文件目录空闲表
1思想外村上一片连续的空闲区可以看成是被一个空闲文件所占用系统为所有的空闲文件单独建立一个目录表目中的内容包括第一个空闲块的地址和空闲块的个数
2空闲文件目录方法适用于连续文件的分配和回收
3空闲文件目录的分配和回收与内存管理中的分区存储管理的空闲块的分配和回收类似
4缺点当空闲块较碎时会造成表很大从而影响文件分配时查找表的速度另外还存在碎片问题 13、空闲块链
1思想把文件存储设备上所有的空闲块链接在一起当申请者需要空闲块时分配程序从链头开始摘取所需要的空闲块然后调整链首指针当回收空闲块时把释放的空闲块插入链中
2方法一每个空闲块中包含指向下一空闲块的指针特点每申请一块都要读出空闲块并取得指针申请多次时读盘
3方法二将空闲块号组成空闲块链每个结点的内容包括当前或下一个空闲块号和指向下一个结点的指针 14、位示图大小磁盘容量/磁盘块大小/8
1思想每个磁盘块都对应1bit“1”表示已分配“0”表示未分配
2利用位示图来进行空闲块分配时只需查找图中的“0”位并将其置为“1”位反之回收时只需把相应的位由“1”改为“0”即可
如何减少位示图的大小增加磁盘块的大小 15、UNIX空闲块的管理成组链接法
1UNIX的文件系统文件卷由四个部分组成 引导块 管理块 索引节点区 数据区 ……
管理块也称超级块它记载着文件卷的使用情况
2思想从尾向前空闲块每100块一组最后一组99块其余的就是直接管理的盘块号和盘块数放入S_free[]和S_nfree中每一组的最后一块作为索引表用来登记下一组100块的盘块号和盘块数
3假设空闲块数为N那么组数int(N/100)1直接管理的空闲块数(N mod 100)1 16、文件目录
1是一张记录所有文件的名字及其存放地址的目录表表中还应包括文件的说明和控制方面的信息
2文件控制块FCB的有序集合即为文件目录 17、UNIX的FCB内容索引节点或i节点
1文件所有者标识
1i_uid文件的所有者号
2i_gid文件所属组号
2文件类型i_type
1d目录文件
2-普通文件正规文件
3b块设备文件
4c字符设备文件
5p管道文件
3文件存取权限i_mode
系统按用户、用户组、其它用户三类对文件进行保护每类都具有R、W、X的存取权并且可以用chmod命令进行设置默认权限普通文件664可执行文件775
4文件链接计数i_link
初值为1同一文件系统中每建立一个硬链接i_link1删除一个文件时i_link-1当i_link0时才能真正删除该文件链接文件和被链接文件具有相同的i节点号
5文件存取时间(i_time)
1i_atime最后一次访问时间
2i_mtime最后一次修改时间
3i_ctime创建时间
6文件长度i_size
7磁盘地址索引表i_addr[13]
在i节点中缺少文件的什么信息该信息放在何处缺少文件名文件名在数据区 18、一级文件目录为了实现“按名存取”的功能在整个文件系统中只建立一张目录表每个文件占一项表目主要由文件名和文件说明信息组成。一级目录结构易于实现管理简单但当系统中文件数增多时查找时间较长且易于发生重名问题 19、二级文件目录二级目录可以解决重名问题并可获得较高的查找速度但二级目录缺乏灵活性无法反映真实世界复杂的文件结构形式如一个用户不能定义同名文件
将文件目录分成主文件目录和用户文件目录两级
1主文件目录MFD记录用户名及相应用户目录所在的储存位置
2用户文件目录UFD登记该用户的文件控制块的信息 20、多级文件目录树形目录结构
1在多级目录结构中第一级目录称为根目录目录树中非叶节点称为子目录叶节点为文件
2在多级目录中用户要访问某个文件时需要指出访问路径从根目录出发的路程称为绝对路径从当前目录出发的路径称为相对路径
3当采用多级目录组织后不同用户可以给不同文件起相同的名字可以把文件组织的有条有理非常便于管理
4文件目录的查询方法
1线性检索算法
2哈希检索算法即目录信息存放在一个哈希表中冲突
3采用B树存储目录信息可以使磁盘访问次数减少到最小 21、文件共享是指某一个或某一部分文件可以让实现规定的某些用户共同使用例如基于索引节点的文件共享 22、文件的安全文件保护机制
1设置文件的存取权限
2口令
3加密技术 23、文件操作文件系统提供一组使用文件的系统调用
1打开文件把该文件的有关目录表复制到主存中约定的区域建立用户和这个文件的联系
2关闭文件系统将其在主存中相应的目录表删去切断用户与该文件的联系若在文件打开期间该文件做过某种修改则应将其写回辅存 24、文件的备份为了能在软、硬件失效的意外情况下恢复文件保证数据的连续可用性文件系统应当提供适当的机构以便复制备份建立文件拷贝的基本方法由两种
1周期性转储全量转储按固定的时间周期把外存中所有的文件的内容转存到某种介质上在系统失效时使用这些转存磁带或磁盘将所有文件重新建立并恢复到最后一次转存时的状态
1缺点费时在转储过程中要停止使用文件系统
2优点把文件进行重新组合使分散分布的文件变为连续分布
2增量转储每隔一段时间将上次转储后修改过的文件和新增加的文件转储到某种介质上实际工作中两种转储方式常配合使用当文件系统失效时可以采用的恢复办法
1从最近一次的全量转储盘中转入全部系统文件使系统得以重新启动进行后续的恢复操作
2从最近一次全量转储盘中恢复所有数据文件
3由近及远从增量盘上恢复文件 25、某个文件系统中外存为硬盘物理块大小为512字节有文件A包含589个记录每个记录占255个字节每个物理块放2个记录文件A所在的目录如图所示文件目录采用多级树型目录结构由根目录节点、作为目录文件的中间结点和作为信息文件的树叶组成每个目录项占127字节每个物理块放4个目录项根目录的第一块常驻内存 1若文件的物理结构采用链式存储方式链占2个字节那么要将文件A读入内存至少需要存取几次硬盘
2若文件为连续文件那么要读文件A的第487个记录至少要存取几次硬盘
3一般减少读盘次数可采用什么措施此时可减少几次存取次数
解1文件589个记录每个物理块2个记录共需要295个物理块
需存取4295299或3295298次硬盘
2第487个记录在第244块中需存取4244248次硬盘
3减少目录将A放在根目录下可减少3次
