北工大 操作系统 作业合集.docx
《北工大 操作系统 作业合集.docx》由会员分享，可在线阅读，更多相关《北工大 操作系统 作业合集.docx（23页珍藏版）》请在冰点文库上搜索。
北工大操作系统作业合集
第八次作业
基础作业
1.假设一个磁盘驱动器有5000个柱面，从0到4999。
驱动器正在为143的一个请求服务，且前面的一个请求在125。
按照FIFO的顺序，即将到来的请求是86，1470，913，1774，948，1509，1022，1750，130。
请按照FCFS、SSTF、SCAN、LOOK、C-SCAN、C-LOOK，要满足队列中的服务要求磁头总的移动距离是多少。
1438614709131774948150910221750130
a.FCFS:
143,86,1470,913,1774,948,1509,1022,1750,130.
总寻道距离7081.
b.SSTF:
143,130,86,913,948,1022,1470,1509,1750,1774.
总寻道距离1745.
c.SCAN：
143,913,948,1022,1470,1509,1750,1774,4999,130,86.
总寻道距离9769.
d.LOOK:
143,913,948,1022,1470,1509,1750,1774,130,86.
总寻道距离3319.
e.C-SCAN:
143,913,948,1022,1470,1509,1750,1774,4999,0,86,130.
总寻道距离9813
f.C-LOOK:
143,913,948,1022,1470,1509,1750,1774,86,130.
总寻道距离3363.
2.为什么文件分配的位图必须保存在大容量存储器中，而不是主存中？
答：
因为如果保存在内存中，当系统崩溃时，这些空闲区间的信息将会被丢失，而如果保存在大容量存储器中就可以解决这个问题。
3．假设要为一个文件换一个名字。
一种选择是使用操作系统提供的RENAME方法，另一种方法是：
把文件复制为新文件，然后删除原来的文件以实现重命名。
请问，这两种方法在实现上有什么不同？
答：
RENAME方法是修改目录文件的文件名部分，而删除原来文件再重命名则需要再创立一个新文件，目录文件中增加一项，分配新空间；删除目录文件中的文件项目，然后回收占用的空间。
4．请解释使用索引节点有什么好处
答：
减小目录文件的大小，提高查找文件的效率
5．在UNIX中open系统调用绝对需要么？
如果没有会产生什么结果。
答：
如果没有open命令，那么每个read命令都需要确定要打开的文件名。
系统必须找到文件的i节点，虽然这个数据放入cache可以减少一些时间，但是当数据变化的时候，i节点的数据需要刷新到磁盘上。
6．UNIX系统中有关盘块的分配与释放是借助超级块中的栈来进行的。
假如某个时刻系统状况如下图所示，若此时某个进程要删除文件A，并归还它所占用的盘块220，110，645，549，176。
请说明过程，并给出删除完毕后有关数据及表目的更改情况。
100
199
786
278
…
80
230
110
645
2
549
176
…
7.考虑一个索引节点所表示的UNIX文件的组织。
假设有12个直接块指针，在每个索引节点中有一个单重、双重和三重间接指针。
此外，假设系统块大小和磁盘扇区大小都是8K，如果磁盘块指针是32位，其中8位表示物理磁盘，24位表示物理块，那么
a.该系统支持的最大文件大小是多少？
b.该系统支持的最大文件分区是多少？
c.假设主存中除了文件索引节点外没有其他信息，访问在位置12423956中的字节需要多少磁盘访问？
答：
a.通过用块大小除以指针大小得到盘块指针的数目：
每块8K/4=2K
这样I节点可以支持的最大文件容量是:
12+2k+2k*2k+2k*2k*2k=（12+2K+4M+8G）*8K（块大小）=96KB+16MB+32GB+64TB
直接寻址一级间接寻址二级间接寻址三级间接寻址
b.在一个分区中识别一个块需要24位。
所以:
*8K=16M*8K=128GB
c.使用从（a）得到的信息,发现直接块只能表示96KB,而一次间接块表示16MB.题目中要求的请求位置在13M左右，使用一次间接块.就可以了。
所以要用两次磁盘访问，一次访问一次间接块，另一次访问包含数据的盘块
第七次作业
1．什么是设备无关性？
应用程序只按套路调用操作系统提供的功能即可，不关心实际的设备是什么，这就是与设备无关性
2．以下各项工作由I/O软件的哪一层完成？
a.为一个磁盘读操作计算磁道、扇区、磁头；设备驱动程序
b.向设备寄存器写命令；中断处理程序
c.检查用户是否允许使用设备；设备独立性软件
d.将二进制整数转换成ASCII码以便打印硬件
3．为什么在要打印的文件通常都假脱机输出到磁盘上？
答：
达到缓冲的目的，实现提高I/O设备性能的目的。
为了打印一个文件，一个进程首先要生成需要打印的整个文件并把它放在假脱机目录里。
由守护进程打印该目录下的文件，该进程是允许使用打印机设备文件的唯一进程。
通过保护设备文件来防止用户直接使用，可以解决某些进程不必要地长期空占打印机的问题。
第六次作业
1．假设页表在内存保存的分页系统，
a.如果一次访问内存用200ns，那么访问一个页内的一次数据访问用多少时间？
b.如果加入TLB，有75%的命中率，那么内存有效访问时间是多少？
a）访问一个页内数据需要访问两次内存，第一次访问内存中的页表，第二次根据页表中的信息形成的物理地址访问内存访问数据，所以要用200*2=400ns
b）加入TLB，获得物理地址的过程为：
先在TLB中查找，如果TLB中命中，则直接获得物理地址，如果TLB中不存在，则去访问页表，所以需要的访问时间为0.25*200=50ns
总共需要的时间为50ns+200ns=250ns
2.在一个虚拟存储管理系统中采用页式方法对内存空间进行管理，它有24位的虚拟地址空间，而实际的物理地址空间是16位，页框大小为2k。
假设有两个进程A和B。
其中A进程的0、2页已经调入到内存的2、3号页框；B进程的1、3页已经调入到内存的7、8号页框。
请问：
A进程的虚拟地址12FF可以转换成什么物理地址？
B进程的虚拟地址17BA可以转换成什么物理地址？
如果不能转换，操作系统会执行什么操作？
页框大小为2k=2^11,有11位的位移。
A进程：
12FF=0001001011111111,00010=2,A进程中2页调进3号框，因此物理地址为：
0001101011111111
B进程：
17BA=0001011110111010，在进程2中没有2号页，需要的页面不在内存时，请求调入所需的页面
判断对错
如果缺页率太高，通常说明一个进程分得的页框太多了。
X
第五次作业
基础作业
1．内部碎片与外部碎片之间的区别？
内部碎片：
内存分页时，最后一页未装满的部分就是内部碎片。
或因调入的数据小于分区而产生分区空间的浪费，称为内部碎片。
外部碎片：
共享时要分段，在段的换入换出时未使用的部分就是外部碎片。
一开始运行得很好，但是在执行一段时间后,会出现一些小的洞。
这种在分区外的洞称为外部碎片。
内存按顺序有100k，500k，200k，300k，600k，用首次适应、最佳适应和最差适应如何放置212k，417k，112k，426k的进程？
首次适应：
212k分配给500k，417k分配给600k，112k分配给200k，426k没有可分配
最佳适应：
首先将212k分配给300k，将417k分配给500k，将112k分配给200k，将426k分配给600k；
最差适应：
将212k分配给600k，将417分配给500k，将112分配给300k，最后426没有可分配的。
2．假设一个有8个1k页面的逻辑地址空间，映射到一个32个页框的物理内存，问：
逻辑地址多少位？
物理地址多少位？
逻辑地址：
13位
物理地址：
15位
4．（8.12）有段表
段基地址长度
0219600
1230014
290100
31327580
4195296
下面的物理地址是多少？
a）0,430;b）1,10;c）2,500;d）3,400;e）4,122
a、649b、2310c、590d、1727e、2074
5．在页面大小为4k的系统中，根据图中所示
页表，下面的逻辑地址经过重定位之后的物理地址是什么？
a）20;b）4100;c）8300
A、49172b、53252c、61548
6．一台计算机为每个进程提供65536字节的地址空间，页面的大小为4k。
一个程序有32768字节的正文，16386字节的数据，15870字节的堆栈，此程序是否能装入此地址空间？
若页面大小为512字节呢？
4k不能，512字节可以；
解析过程：
65536/4096=16，共计16个页面；
正文需要页面：
32768/4096=8
数据需要页面：
16386/4096=5
对战需要：
15870/4096=4
共需17个页面，所以不能装入
512字节同理可得正好能够装入
补充作业
判断对错
编译时绑定是大多数通用操作系统使用的地址绑定方法。
X
最佳适配法可以在内存分配过程中留下最小的洞。
√
为解决内存分配时导致的外部碎片可以采用压缩的方法来解决，因此需要在地址绑定的时候采用静态重定位方法。
X
如果现在基地址寄存器的值是1200，界限寄存器的值是350，那么当前进程产生对绝对地址1551的访问是合法的。
X
可重入代码不可以被共享。
X
基础作业
1．考虑下面一组进程，进程占用的CPU区间长度以毫秒计算。
假设在0时刻进程以P1,P2,P3,P4,P5的顺序到达。
进程区间时间优先级
P1103
P211
P323
P414
P552
（1）画出4个Gantt图，分别演示使用FCFS,SJF,非抢占优先级（数字越小表示优先级越高）和RR（时间片=1）算法调度时进程的执行过程。
（2）每个进程的周转时间是多少？
（3）每个进程在每种调度算法下的等待时间是多少？
解：
（1）GANTT图
FCFS：
P1P2P3P4P5
SJF：
P2P4P3P5P1
非抢占优先级：
P2P5P1P3P4
RR：
P1P2P3P4P5P1P3P5P1P5P1P5P1P5P1
（2）周转时间：
FCFS
SJF
非抢占优先级
RR
P1
10
19
16
19
P2
11
1
1
2
P3
13
4
18
7
P4
14
2
19
4
P5
19
9
6
14
（3）等待时间：
FCFS
SJF
非抢占优先级
RR
P1
0
9
6
9
P2
10
0
0
1
P3
11
2
16
5
P4
13
1
18
3
P5
14
4
1
9
2．考虑下面一个系统在某一个时刻的状态。
AllocationMaxAvailable
ABCDABCDABCD
P0001200121520
P110001750
P213542356
P306320652
P400140656
使用银行家算法回答下面的问题：
（1）Need矩阵的内容
（2）系统是否处于安全状态
（3）如果从进程P1发来一个请求（0，4，2，0），这个请求是否可以立即满足？
解：
（1）Need矩阵
A
B
C
D
P0
0
0
0
0
P1
0
7
5
0
P2
1
0
0
2
P3
0
0
2
0
P4
0
6
4
2
（2）处于安全状态，先是P0完成，之后P3，之后P2，之后P1，之后P4。
（3）可以立即满足，满足后仍处于安全状态。
补充作业
判断对错
在RR调度中，上下文切换的时间应该小于时间片的长度。
X
SJF调度算法是最适合分时系统的调度算法。
X
FCFS调度算法只能是非抢占式的。
√
如果资源分配图中有环，那么就一定有死锁。
X
死锁的时候系统一定处于非安全状态。
√
第三次作业
一、基础作业
1.什么是忙等待？
持续地检测一个变量直到它具有某一个特定值称为忙等待。
2．吸烟者问题：
有3个吸烟者和一个供应者。
第一个吸烟者有自己的烟草；第二个吸
烟者有自己的纸；第三个吸烟者有自己的火柴。
供应者每次随机放两样东西到桌子上
提供给3个吸烟者之中的一个以完成吸烟。
请用信号量为吸烟者和供应者进程编写程
序。
Semaphoren[2]={0};
Semaphores=1;
0代表烟草，1代表纸，2代表火柴.
//供应者程序
Voidprocucer（）
{
While
（1）
{
随机生成一个在0~2之间的数ｉ;
Wait（s）;
将除了ｉ表示的另外两件东西放在桌子上;
Signal（n[i]）;
}
//吸烟者程序
Voidsmoker（inti）
{
While
（1）
{
Wait（n[i]）;
Somke（）;
Signal（s）;
}
｝
二、补充作业
1．假设有三个进程R、W1、W2共享缓冲区B。
B中只能存放一个数。
R每次从输入设备中读一个整数放入B中。
如果这个整数是奇数，由W1取出打印。
如果这个整数是偶数，则由W2取出打印。
规定仅当B中没有数据或数据已经被打印才会启动R去读数。
W1、W2对B中的数据不能重复打印，当B中没有数据时也不能打印。
要求用信号量操作写出R、W1、W2三个进程的程序。
（请详细描述所使用变量的含义）
Semaphores=1;//进程R可以存入缓冲区B的数据个数信号量
Semaphoren[2]={0};//n[0]/n[1]表示进程W1/W2可以从缓冲区B中取出的数据个数；
//进程R
VoidR（）
{
While
（1）
{
读入一个正数m;
Wait（s）;
将m放入B中；
if（m/2!
=0）
Signa（[n[0]）;
Else
Signal（n[1]）;
}
}
Voidw1（）
{
While
（1）;
{
Wait（n[0]）;
从缓冲区B取数据k;
Signal（s）;
打印K;
}
}
Voidw1（）
{
While
（1）;
{
Wait（n[1]）;
从缓冲区B取数据k;
Signal（s）;
打印K;
}
}
2．有一个铁笼子，猎手放入老虎，农民放入猪，动物园等待取走老虎，饭店等待取走猪。
笼子中只能放入一个动物。
请使用信号量方法为猎手、农民、动物园、饭店进程编写程序。
Semaphorecage=1;//可以放入笼子中的动物数量
Semaphoretiger=0;//动物园从笼子中取出老虎的数量
Semaphorepig=0;//饭店从笼子中取出猪的数量
////////////////////猎手进程
Voidhunter（）
{
While
（1）
{
Wait（cage）;
将老虎放入笼子;
Signal（tiger）;
}
}
Voidfarmer（）
{
While
（1）
{
Wait（cage）;
将猪放入笼子;
Signal（pig）;
}
}
Voidzoo（）
{
While
（1）
{
wait（tiger）;
从笼子中取出老虎;
signal（cage）;
}
}
Voidrestaurant（）
{
While
（1）
{
waitl（pig）;
从笼子中取出猪；
signal（cage）;
}
}
3．某寺庙，有小、老和尚若干。
有一个水缸，由小和尚提水入缸供老和尚饮用。
水缸可容10桶水。
水取自一个井中，水井窄，每次只能容一个水桶。
水桶总数为3。
水缸每次进出也仅1桶水，不可以同时进行。
请设置合适的信号量描述小和尚、老和尚取水、入水的算法。
Semaphorebucket=3;//水桶的数量
Semaphoretank=1;//水缸每次能容水桶的数量;
Semaphores=10;//水缸容水桶水量;
Semaphorewell=1;//井每次能容水桶的数量；
Semaphoreempty=0;//水缸中现有的水量；
Voidyoungmonk（）
{
While
（1）
{
Wait（bucket）;
获得水桶;
Wait（well）;
井中取水；
signal（well）;
Wait（s）;
Wait（tank）;
倒水入水缸;
Signal（tank）;
Signal（bucket）;
Signal（empty）;
}
}
Voidoldmonk（）
{
While
（1）
{
Wait（empty）;
Wait（bucket）;
获得水桶；
Wait（tank）;
从水缸中取水；
Signal（tank）;
Signal（s）;
Signal（bucket）;
}
}
4.判断对错
（1）一个系统中进程之间可能是独立的也可能是合作的。
√
（2）如果用锁来保护临界区可以防止竞争条件。
√
（3）一个计数信号量的值只能取0或者1.X
（4）在管程中本地变量只能由本地过程来访问。
√
5.选择题
（1）关于竞争条件那句话是对的？
B
A.几个线程要并发访问同样的数据
B.几个线程要并发访问并修改同样的数据
C.只有在执行结果与执行顺序无关的时候发生
（2）关于原子指令那句话是对的？
B
A.原子指令只能由一条机器指令组成
B.作为一个单独的，不可以中断的单元执行
C.不能用于解决临界区问题
（3）一个临界区的解决方案不需要实现下面的哪一条？
C
A.互斥B.有空让进
C.原子性D.有限等待
（4）当低优先级的进程正在访问一个数据的时候，若一个高优先级的进程需要访问同样的数据，可能发生A
A.优先级反转B.死锁
C.竞争条件D.临界区
附加题：
1．独木桥问题：
某条河上只有一座独木桥，两边都有人要过河，为保证安全，一个方向有人过河另一个方向的人就要等待，并且允许一个方向上的人连续过河。
请使用信号量实现正确的管理。
Semaphores=1;//两岸过河能使用的桥的数量；
Semaphoreleft=1,right=1;
Intleftcount=0,rightcount=0;
//////////////左岸过河进程
VoidLeft（）
{
While
（1）
{
Wait（left）;
Leftcount++;
If（leftcount==1）
Wait（s）;
Signal（left）;
左岸过河；
Wait（left）;
Leftcount--;
If（leftcount==0）
Signal（s）;
Signal（left）;
}
}
////////////////右岸进程
Voidright（）
{
While
（1）
{
Wait（right）;
Rightcount++;
If（rightcount==1）
Wait（s）;
Signal（right）;
右岸过河;
Wait（right）;
Rightcount--;
If（rightcount==0）
Signal（s）;
Signal（right）;
}
}
第二次作业
一、基础作业
1.论述短期、中期、长期调度之间的区别
短期调度—从就绪队列中选择进程执行并把CPU分配给它。
中期调度—主要在分时系统中使用。
将内存中的作业换出到外存中等到内存允许的情况下再换入到内存中执行。
长期调度—确定把哪个作业放到内存中执行。
它们之间的主要区别是执行的频率不同。
短期调度执行频率高而长期调度执行频率低。
2.两个进程进行上下文切换的操作
通常，操作系统必须保存当前运行进程的状态并恢复下一个要调度的进程的状态。
保存一个进程的状态通常包括CPU所有寄存器的值和内存的分配情况。
3.用户级线程和内核级线程之间的区别？
相互对比的优势在哪里？
（1）内核不知道用户级线程的存在，但内核知道内核级线程的存在
（2）内核调度内核级线程，而用户级线程则由线程库调度在要体现系统灵活性的时候使用用户级线程好，因为用户级线程可以自己设计自己的调度。
内核级线程则被内核知道，所以可以保证一个线程阻塞时可以调度一个进程的另一个线程，减少系统开销。
三、补充作业
1．假设有一个进程，它的工作流程是先运行150ms，然后进行I/O，最后执行250ms结束。
如果系统中的进程有三个状态，当时间片为200ms时，请写出进程A从被系统接纳到运行结束所经历的状态转换并说明原因。
答：
被系统接纳之后：
就绪-运行（原因：
被调度执行）、运行-阻塞（原因：
执行I/O操作）、阻塞-就绪（原因：
I/O操作完成）、就绪-运行（原因：
被调度执行）、运行-就绪（原因：
时间片到）、就绪-运行（原因：
被调度执行）、结束。
2.图中程序的运行结果。
Value=10
3.图中程序运行完共有多少进程？
8
4.判断对错
（1）程序是活动的实体，进程是被动的实体。
X
（2）对于一个单处理器系统，最多只能有一个进程处于运行状态。
√
（3）状态切换负责保存当前的运行进程并回恢复下一个要运行进程的状态。
√
（4）共享内存通常比消息传递要慢。
X
（5）命名管道不允许双工通信。
X
（6）进程只有一条运行线。
X
5.选择题
在一个子进程创建的时候，下面关于子进程的话哪一个可能是对的？
D
A.子进程与父进程并发执行；B.子进程调入一个新的程序；
C.子进程是父进程的副本；D.以上都是
第一次作业
一、基础作业
1.操作系统的两个主要目标是什么
答：
操作系统的主要目标是方便性和有效性。
方便性指使计算机更易于使用，有效性指操作系统允许以更有效的方式使用计算机系统资源。
2.多道程序设计的主要优点是什么？
答:
（1）资源利用率高，多道程序共享计算机资源，从而使各种资源得到充分利用；
（2）系统吞吐量大，CPU和其他资源保持“忙碌”状态。
3.监督程序模式和用户模式之间的区别？
答：
通过只能在系统模式
升级会员 