杭电操作系统补充作业.docx
- 文档编号:11808968
- 上传时间:2023-06-02
- 格式:DOCX
- 页数:31
- 大小:2.18MB
杭电操作系统补充作业.docx
《杭电操作系统补充作业.docx》由会员分享,可在线阅读,更多相关《杭电操作系统补充作业.docx(31页珍藏版)》请在冰点文库上搜索。
杭电操作系统补充作业
第一次:
1.什么是线程?
简述与进程的区别和联系(从并发性、调度性、拥有资源及系统开销等方面阐述)。
答:
a.调度性。
在传统的操作系统中,拥有资源的基本单位和独立调度、分派的基本单位都是进程,在引入线程的OS中,则把线程作为调度和分派的基本单位,而把进程作为资源拥有的基本单位;
b.并发性。
在引入线程的OS中,不仅进程之间可以并发执行,而且在一个进程中的多个线程之间,亦可并发执行,因而使OS具有更好的并发性;
c.拥有资源。
无论是传统的操作系统,还是引入了线程的操作系统,进程始终是拥有资源的一个基本单位,而线程除了拥有一点在运行时必不可少的资源外,本身基本不拥有系统资源,但它可以访问其隶属进程的资源;
d.开销。
由于创建或撤销进程时,系统都要为之分配和回收资源,如内存空间等,进程切换时所要保存和设置的现场信息也要明显地多于线程,因此,操作系统在创建、撤消和切换进程时所付出的开销将显著地大于线程。
2.进程有哪三种基本状态?
进程在三种基本状态之间转换的典型原因是什么?
三种基本状态:
就绪状态、执行状态、阻塞状态。
(1)就绪状态→执行状态:
进程分配到CPU资源(进程调度);
(2)执行状态→就绪状态:
时间片用完
(3)执行状态→阻塞状态:
I/O请求
(4)阻塞状态→就绪状态:
I/O完成
3.同步机制应该遵循哪些基本准则?
你认为整型信号量机制遵循了同步机制的哪些基本准则?
4.在Linux系统中运行下面程序,最多可产生多少个进程?
画出进程家族树。
main()
{
fork();
fork();
fork();
}
最多可以产生7个进程。
其家族树为:
5.使用信号量实现下面的前趋图。
6.用信号量解决“独木桥”问题:
同一个方向行人可连续过桥,当某一方向有人过桥时,另一个方向的行人必须等待;当某一方向无人过桥时,另外方向的行人可以过桥。
1)写出记录型信号量的P、V操作的定义。
2)本问题中有哪些同步或互斥关系?
3)给出两个方向任一行人通过独木桥的同步算法。
7.设有两个生产者进程A、B和一个销售者进程C,他们共享一个无限大的仓库,生产者每次循环生产一个产品,然后入库供销售者销售;销售者每次循环从仓库中取出一个产品销售。
如果不允许同时入库,也不允许边入库边出库,而且要求生产A产品和B产品的件数满足以下关系:
-n≤A的件数-B的件数≤m
其中n、m是正整数,但对仓库中A产品和B产品的件数无上述要求,请用信号量机制写出A,B,C三个进程的工作流程。
第二次:
1.何为死锁?
产生死锁的原因和必要条件是什么?
所谓死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局,当进程处于这种僵持状态时,若无外力作用,它们都将无法再向前推进。
产生死锁的原因为竞争资源和进程间推进顺序非法。
其必要条件为互斥条件,请求和保持条件,不剥夺条件,环路等待条件。
2.什么是高级调度、中级调度和低级调度?
(1)高级调度:
又称作业调度。
其主要功能是根据一定的算法,从输人的一批作业中选出若干个作业,分配必要的资源,如内存、外设等,为它建立相应的用户作业进程和为其服务的系统进程(如输人、输出进程),最后把它们的程序和数据调人内存,等待进程调度程序对其执行调度,并在作业完成后作善后处理工作。
(2)中级调度:
为了使内存中同时存放的进程数目不至于太多,有时就需要把某些进程从内存中移到外存上,以减少多道程序的数目,为此设立了中级调度。
特别在采用虚拟存储技术的系统或分时系统中,往往增加中级调度这一级。
所以中级调度的功能是在内存使用情况紧张时,将一些暂时不能运行的讲程从内存对换到外存上等待。
当以后内存有足够的空闲空间时,再将合适的进程重新换人内存,等待进程调度。
引人中级调度的主要目的是为了提高内存的利用率和系统吞吐量。
它实际上就是存储器管理中的对换功能。
(3)低级调度:
又称进程调度。
其主要功能是根据一定的算法将CPU分派给就绪队列中的一个进程。
执行低级调度功能的程序称做进程调度程序,由它实现CPU在进程间的切换。
进程调度的运行频率很高,在分时系统中往往几十毫秒就要运行一次。
进程调度是操作系统中最基本的一种调度。
在一般类型的操作系统中都必须有进程调度,而且它的策略的优劣直接影响整个系统的计能。
3.简述多级反馈队列调度算法,并说明其为什么能较好地满足各方面用户的需要?
多级反馈队列调度算法是一种性能较好的作业低级调度策略,能够满足各类用户的需要。
对于分时交互型短作业,系统通常可在第一队列(高优先级队列)规定的时间片内让其完成工作,使终端型用户都感到满意;对短的批处理作业,通常,只需在第一或第一、第二队列(中优先级队列)中各执行一个时间片就能完成工作,周转时间仍然很短;对长的批处理作业,它将依次在第一、第二、……,各个队列中获得时间片并运行,决不会出现得不到处理的情况。
此系统模拟了多级反馈队列调度算法及其实现
4.系统中有一个CPU,一台输入设备,一台打印机。
现假设系统中的两个进程,进程A的运行轨迹为:
计算50ms,打印输出100ms,再计算50ms,打印输出100ms;进程B的运行轨迹为:
计算50ms,输入数据80ms,再计算100ms。
请计算CPU的利用率。
运行次序为:
0~50msA计算
50~100msB计算,A打印
100~150msA打印,B输入
150~200msA计算,其中150~180msB继续输入
200~300msA打印,B计算
运行开始后,在100~150ms时,CPU空闲等待。
CPU利用率为:
250/300=83.3%。
5.某进程中由5个进程A,B,C,D,E,它们几乎同时到达,预计它们的执行时间(单位:
ms)分别为10,1,2,1,5,其优先数分别为3,1,5,4,2,优先数越小,优先级越高。
对下列每一种调度算法,计算进程的平均周转时间。
(1)先来先服务(按A,B,C,D,E的顺序)算法。
(2)优先级调度算法。
(3)时间片轮转算法(时间片大小为1ms)。
6.设有四个进程,它们到达就绪队列的时刻、要求运行的时间如下表所示,若采用基于剩余运行时间抢占的短进程优先调度算法,试给出各进程的调度顺序、系统平均周转时间以及平均带权周转时间。
(类似例题):
7.某时刻系统的A、B、C、D四种资源状态如表所示:
(1)系统中四类资源各自的总数是多少?
(2)请写出Need矩阵。
(3)当前系统状态是否安全?
写出一个安全序列。
(4)如果P1发出请求(0,4,2,0),是否可以满足该请求?
如果可以,请给出安全序列。
(类似例题):
8.请对下列资源分配图进行简化,画出简化过程,并根据简化结果判断系统是否有死锁发生。
类似例题
9.在CPU按优先权调度的系统中,请回答以下问题:
1)没有运行进程是否一定就没有就绪进程?
2)没有运行进程,没有就绪进程,或者两者都没有,是否可能?
各是什么情况?
3)运行进程是否一定是自由进程中优先权最高的?
第三次:
1.虚拟存储器具有哪些基础特征?
实现虚拟存储器的几个关键技术是什么?
2.对于首次适应算法,请回答下列问题:
1)应如何将各空闲分区链接成空闲分区链?
2)在回收内存时,可能出现哪几种情况?
应怎样处理这些情况?
3)请对该算法的内存管理性能进行分析。
3.比较页式管理与段式管理的区别?
5.某段式存储管理采用如下表所示的段表,试计算[0,450],[1,50],[2,70]的内存地址。
其中方括号内前一元素为段号,后一元素为段内地址。
当无法进行地址转换时,请说明产生何种中断。
下面这幅图看懂了,这题也就没问题了:
[0,450]:
内存地址2000+450=2450
[1,50]:
分段越界中断
[2,70]:
缺段中断
6.某请求分页系统,用户空间为32KB,每个页面1KB,主存16KB。
某用户程序有10页长,某时刻该用户进程的页表如下:
(1)计算两个逻辑地址:
0AC5H、1AC5H对应的物理地址。
(2)已知主存的一次存取为1.5us,对于TLB表(快表)的查询时间可以忽略,则访问上述两个逻辑地址共耗费多少时间?
(1)32KB=2^15B,1KB=2^10B,所以低10位页内偏移量,再往上5位页号。
然后对着页表查就可以了。
0AC5H =0000101011000101B >>>0001001011000101B=12C5H
1AC5H =0001101011000101B >>>0000101011000101B=0AC5H
(2)由第一问中可知页号2不在快表中,页号6在快表中。
我们来看看下面这幅图:
在快表中的查到物理块号直接访问内存,1次即可,不在的要先到内存中取页表,然后查到物理块号再访问,要2次。
所以时间为:
1.5+2*1.5=4.5us
7.在某请求分页管理系统中,一个作业共5页,作业执行时一次访问如下页面:
1,4,3,1,2,5,1,4,2,1,4,5,若分配给该作业的主存块数为3,分别采用FIFO,LRU,Clock页面置换算法,试求出缺页中断的次数及缺页率。
(其他例题):
8.某虚拟存储器的用户空间共有32个页面,每页1KB,主存16KB。
假定某时刻系统为用户的第0,1,2,3页分配的物理块号为5、10、4、7,而该用户作业的长度为6页,试将十六进制的虚拟地址0A5C、103C、1A5C转换成物理地址。
9.某请求分页管理系统,假设进程的页表如下:
页面大小为4KB,一次内存的访问时间为100纳秒(ns),一次快表(TLB)的访问时间是10ns,处理一次缺页的平均时间为100毫秒(已含更新TLB和页表的时间),进程的驻留集大小固定为2个页框,采用FIFO法置换页面。
假设:
1)TLB初始为空;
2)地址转换时,先访问TLB,若TLB未命中时再访问页表(忽略TLB更新时间);
3)有效位为0表示页面不在内存中。
请问:
1)该系统中,一次访存的时间下限和上限各是多少?
(给出计算过程)
2)若已经先后访问过0、2号页面,则虚地址1565H的物理地址是多少?
(给出计算过程)
10.设某计算机的逻辑地址空间和物理地址空间均为128KB,按字节编址。
若某进程最多需要6页数据存储空间,页面大小为1KB,操作系统采用固定分配局部置换策略为该进程分配4个页框(物理块)。
在时刻300前该进程各页面的访问情况如下表所示:
当进程执行到时刻300时,要访问逻辑地址为17CAH的数据,
请回答下列问题:
(1)该逻辑地址对应的页号是多少?
(2)若采用先进先出(FIFO)置换算法,该逻辑地址对应的物理地址是多少?
要求给出计算过程。
(3)若采用时钟(CLOCK)置换算法,该逻辑地址对应的物理地址是多少?
要求给出计算过程。
设搜索下一页的指针顺时针方向移动,且当前指向2号页框,示意图如下:
11.某系统具有多级存储系统,包括Cache、RAM和disk,并且启用虚拟存储器。
已知访问Cache获取一个字word的时间为2ns,访问RAM的时间为10ns,访问磁盘的时间为10ms,并且Cache的命中率为95%,RAM的命中率为99%(Cache不命中的时候),试计算在该系统中访问一个字的平均时间。
先上张存储器的层次结构
其实不难发现题目是做了简化的。
解题如下:
2*0.95+10*(1-0.99)*0.05+10000000*(1-0.95)*(1-0.99)=5002.395ns
第四次:
1.有哪几种I/O控制方式?
各适用于什么场合?
2.引入缓冲的主要原因是什么?
3.请简述Linux的缓冲机制(选做)。
4.什么是虚拟设备?
实现虚拟设备的关键技术是什么?
5.SPOOLing系统由哪几部分组成?
简述其原理。
6.请以打印机为例说明如何使用SPOOLing技术实现多个进程对打印机的共享。
7.假设一个10MB大小的文件存储在磁盘的50号磁道上连续的扇区中,当前磁头的位置在100号磁道上。
若磁头移动至下一个磁道的时间为1ms,磁盘的转速为7200rpm,磁盘的读速度为100MB/s。
请计算读取该文件需要花费的时间。
(类似例题):
8某磁盘上有1000个柱面(编号0~999)。
假设最后服务的请求是在磁道345#上,并且读写头正在朝磁道0#移动。
在按FIFO顺序排列的队列中包含了如下磁道上的请求:
123,874,692,475,105,376。
用下面的算法计算为了满足磁盘队列中的所有请求,磁盘臂必须移动过的磁道数目。
(1)FIFO;
(2)SSTF;(3)SCAN;(4)C_SCAN
(类似例题):
第五次:
1.Linux系统有几种类型文件?
它们分别是什么?
有哪些相同点和不同点?
如果文件的类型和权限用“drwxrw-r--"表示,那么这个文件属于什么类型的文件,各类用户对这个文件拥有什么权限?
3类。
分别是普通文件,目录文件和设备文件。
相同是它们都是文件,都有一个文件名和i节点号。
不同点是,普通文件的内容为数据,目录文件的内容为目录项或文件名与i节点对应表,设备文件不占用磁盘空间,通过其i节点信息可建立与内核驱动程序的联系。
目录文件。
文件属主读写执行权限,文件属组读写权限,除属主和属组成员之外的其他用户读权限。
2.假定一个文件系统组织方式与MS-DOS相似,在FAT中可有64K个指针,磁盘的盘块大小为512B,试问该文件系统能否指引一个512MB的磁盘?
有512MB/512B=1M个盘块,64K个指针不够。
3.在UNIX中,每个i节点中有10个直接地址和一、二、三级间接索引。
若每个盘块512B,每个盘块地址4B,则一个1MB的文件分别占用多少间接盘块?
20MB的文件呢?
10个直接盘块存放的容量为:
10*512B/1024=5KB
一个盘块中可放的盘块地址数为:
512B/4B=128
一次间接索引存放的容量为:
128*512B/1024=64KB
二次间接索引存放的容量为:
128*128*512B/1024=8192KB
三次间接索引存放的容量为:
128*128*128*512B/1024=1048576KB
则:
1MB为1024KB,1024KB-64KB-5KB=955KB,955×1024B/512B=1910,所以1MB的文件分别占用128个一次间接盘块和1910个二次间接盘块。
25MB为:
25×1024KB--64KB-5KB-8192KB=17339KB,17339×1024B/512B=34678所以25MB的文件分别占用128个一次间接盘块
和128^2=16384个二次间接盘块,34678个三次间接盘块.
4.假设某文件系统的硬盘空间为3GB,盘块大小为1KB,采用显示链接分配,请回答以下问题:
(1)其FAT表(文件分配表)需占用多少存储空间?
(2)如果文件file1占用硬盘的盘块号依次为10、6、8、15、12共五个盘块,请画图示意文件file1的FCB与FAT表的关系以及FAT表中各盘块间的链接情况。
(3)假设采用一级索引分配算法,索引块上的索引项应该占几个字节?
为什么?
(1).FAT的每个表项对应于磁盘的一个盘块,其中用来存放分配给文件的下一个盘块的块号,故FAT的表项数目由物理盘块数决定,而表项的长度则由磁盘系统的最大盘块号决定(即它必须能存放最大的盘块号)。
为了地址转换的方便,FAT表项的长度通常取半个字节的整数倍,所以必要时还必须由最大盘块号获得的FAT表项长度作一些调整。
由题意可知,该硬盘共有500K个盘块,故FAT中共有500K个表项;如果盘块从1开始编号,为了能保存最大的盘块号500K,该FAT表项最少需要19位,将它扩展为半个字节的整数倍后,可知每个FAT表项需20位,即2.5个字节。
因此,FAT需占用的存储空间的大小为:
2.5×500K=1250KB
(2)如下图所示:
5.某文件系统采用单级索引文件结构,假定文件索引表的每个表项占3个字节存放一个磁盘块的块号,磁盘块的大小为1KB。
试问:
(1)该文件系统能支持的最大文件大小是多少字节?
能管理的最大磁盘空间是多大?
(2)若采用3级索引,该文件系统能支持的最大文件大小是多少字节?
能管理的最大磁盘空间是多大?
(1).由于索引表占用一个大小为512*2B的磁盘,所以该文件系统的索引表可以管理512*2/3=170个表项,而每一个表项对应一个物理块,因此该文件
系统可以支持的最大文件为:
170*512*2B=87040B=85*2KB
能管理的最大磁盘空间:
2^24*512*2B
(2).170*170*170*512*2B=2456500*2KB=2398.93*2MB
6.在某个采用混合索引分配的文件系统中,FCB中有i_addr[0]~i_addr[8]共9个物理地址项,其中i_addr[0]~i_addr[6]是7个直接地址项,i_addr[7]是1个一次间址项,i_addr[8]是1个二次间址项。
如果一个盘块的大小是4KB,每个盘块号占4个字节。
请写出将下列文件的字节偏移量转换成物理地址的过程:
(1)10000;
(2)500000。
(1).10000/(4*1024)=2余1808,第3个直接地址项指向的盘块,块内偏移1808个字节。
(2).每个盘块可以放4KB/4=1K个盘块号,500000/(4*1024)=122余288,一次间址项够用,122-7=125,一次间址项里的第125+1=126个盘块号指向的盘块,块内偏移288个字节。
7.文件目录的作用是什么?
一个文件的目录项应包括哪些信息?
当前使用最广泛的目录结构是什么?
有什么优点?
8.Linux文件系统为多个用户共享同一个文件提供了两种方便的文件共享机制,请问:
(1)Linux文件系统提供了哪两种文件共享机制?
(2)请说明
(1)中两种文件共享机制的实现原理。
(3)请比较分析
(1)中两种文件共享机制的优缺点。
9.在UNIX系统中有空闲盘块栈如下图所示:
(1)某进程要释放3个物理块,其块号为156、160、220,画出空闲盘块栈的变化。
(2)在
(1)的基础上假定某进程要求分配5个空闲块,请说明进程所分配到的盘块,并画出分配后的空闲盘块栈。
(类似题目):
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统 补充 作业