第八次作业
基础作业
1.假设一个磁盘驱动器有5000个柱面，从0到4999。驱动器正在为143的一个请求服务，且前面的一个请求在125。按照FIFO的顺序，即将到来的请求是86，1470，913，1774，948，1509，1022，1750，130。请按照FCFS、SSTF、SCAN、LOOK、C-SCAN、C-LOOK， 要满足队列中的服务要求磁头总的移动距离是多少。 143 86 1470 913 1774 948 1509 1022 1750 130
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=0001 0010 1111 1111 ,00010=2,A进程中2页调进3号框，因此物理地址为：0001 1010 1111 1111
B进程：17BA=0001 0111 1011 1010，在进程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）有段表
段 基地址 长度 0 219 600 1 2300 14 2 90 100 3 1327 580 4 1952 96 下面的物理地址是多少？
a)0,430; b)1,10; c)2,500; d)3,400; e)4,122
a、649 b、2310 c、590 d、1727 e、2074 5．在页面大小为4k的系统中，根据图中所示
页表，下面的逻辑地址经过重定位之后的物理地址是什么？ a)20; b)4100; c)8300
A、49172 b、53252 c、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的顺序到达。
进程 区间时间 优先级 P1 10 3 P2 1 1 P3 2 3 P4 1 4 P5 5 2
（1）画出4个Gantt图，分别演示使用FCFS, SJF, 非抢占优先级（数字越小表示优先级越高）和RR（时间片=1）算法调度时进程的执行过程。 （2）每个进程的周转时间是多少？
（3）每个进程在每种调度算法下的等待时间是多少？ 解：（1）GANTT图 FCFS：P1 P2 P3 P4 P5 SJF：P2 P4 P3 P5 P1
非抢占优先级：P2 P5 P1 P3 P4
RR：P1 P2 P3 P4 P5 P1 P3 P5 P1 P5 P1 P5 P1 P5 P1 (2)周转时间： P1 FCFS 10 SJF 19 非抢占优先级 16 RR 19 P2 P3 P4 P5
(3)等待时间： P1 P2 P3 P4 P5 11 13 14 19 1 4 2 9 1 18 19 6 2 7 4 14 FCFS 0 10 11 13 14 SJF 9 0 2 1 4 非抢占优先级 6 0 16 18 1 RR 9 1 5 3 9 2．考虑下面一个系统在某一个时刻的状态。
Allocation Max Available A B C D A B C D A B C D P0 0 0 1 2 0 0 1 2 1 5 2 0 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 6 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 使用银行家算法回答下面的问题： （1） Need矩阵的内容
（2） 系统是否处于安全状态
（3） 如果从进程P1发来一个请求（0，4，2，0），这个请求是否可以立即满足？ 解：
（1）Need矩阵 P0 P1 P2 P3 P4 A 0 0 1 0 0 B 0 7 0 0 6 C 0 5 0 2 4 D 0 0 2 0 2 （2）处于安全状态，先是P0完成，之后P3，之后P2，之后P1，之后P4。 （3）可以立即满足，满足后仍处于安全状态。 补充作业 判断对错
在RR调度中，上下文切换的时间应该小于时间片的长度。 SJF调度算法是最适合分时系统的调度算法。 FCFS调度算法只能是非抢占式的。 如果资源分配图中有环，那么就一定有死锁。 死锁的时候系统一定处于非安全状态。
X X
√
X
√
第三次作业
一、基础作业
1.什么是忙等待？
持续地检测一个变量直到它具有某一个特定值称为忙等待。
2．吸烟者问题：有3个吸烟者和一个供应者。第一个吸烟者有自己的烟草；第二个吸 烟者有自己的纸；第三个吸烟者有自己的火柴。供应者每次随机放两样东西到桌子上 提供给3个吸烟者之中的一个以完成吸烟。请用信号量为吸烟者和供应者进程编写程 序。
Semaphore n[2]={0}; Semaphore s=1;
0代表烟草，1代表纸，2代表火柴. //供应者程序 Void procucer() {
While(1) {
随机生成一个在0~2之间的数ｉ; Wait(s);
将除了ｉ表示的另外两件东西放在桌子上; Signal(n[i]); }
//吸烟者程序 Void smoker(int i) {
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三个进程的程序。（请详细描述所使用变量的含义）
Semaphore s=1;//进程R可以存入缓冲区B的数据个数信号量
Semaphore n[2]={0};//n[0]/n[1]表示进程W1/W2可以从缓冲区B中取出的数据个数； //进程R Void R()
{
While(1) {
读入一个正数m; Wait(s);
将m放入B中； if(m/2!=0) Signa([n[0]); Else
Signal(n[1]); } }
Void w1() {
While(1); {
Wait(n[0]);
从缓冲区B 取数据k; Signal(s); 打印K; } }
Void w1() {
While(1); {
Wait(n[1]);
从缓冲区B 取数据k; Signal(s); 打印K; } }
2．有一个铁笼子，猎手放入老虎，农民放入猪，动物园等待取走老虎，饭店等待取走猪。笼子中只能放入一个动物。请使用信号量方法为猎手、农民、动物园、饭店进程编写程序。
Semaphore cage=1;//可以放入笼子中的动物数量
Semaphore tiger=0;//动物园从笼子中取出老虎的数量 Semaphore pig=0;//饭店从笼子中取出猪的数量 ////////////////////猎手进程 Void hunter() {
While(1)
{
Wait(cage);
将老虎放入笼子; Signal(tiger); } }
Void farmer() {
While(1) {
Wait(cage); 将猪放入笼子; Signal(pig); } }
Void zoo() {
While(1) {
wait(tiger);
从笼子中取出老虎; signal(cage); } }
Void restaurant() {
While(1) {
waitl(pig);
从笼子中取出猪； signal(cage); } }
3．某寺庙，有小、老和尚若干。有一个水缸，由小和尚提水入缸供老和尚饮用。水缸可容10桶水。水取自一个井中，水井窄，每次只能容一个水桶。水桶总数为3。水缸每次进出也仅1桶水，不可以同时进行。请设置合适的信号量描述小和尚、老和尚取水、入水的算法。
Semaphore bucket=3;//水桶的数量
Semaphore tank=1;//水缸每次能容水桶的数量; Semaphore s=10;//水缸容水桶水量;
Semaphore well=1;//井每次能容水桶的数量； Semaphore empty=0;//水缸中现有的水量； Void youngmonk() {
While(1) {
Wait(bucket); 获得水桶; Wait(well); 井中取水； signal(well); Wait(s); Wait(tank); 倒水入水缸; Signal(tank); Signal(bucket); Signal(empty); } }
Void oldmonk() {
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．独木桥问题：某条河上只有一座独木桥，两边都有人要过河，为保证安全，一个方向有人过河另一个方向的人就要等待，并且允许一个方向上的人连续过河。请使用信号量实现正确的管理。
Semaphore s=1;//两岸过河能使用的桥的数量； Semaphore left=1,right=1; Int leftcount=0,rightcount=0; //////////////左岸过河进程 Void Left() {
While(1) {
Wait(left); Leftcount++; If(leftcount==1) Wait(s); Signal(left); 左岸过河； Wait(left); Leftcount--; If(leftcount==0) Signal(s); Signal(left); } }
////////////////右岸进程 Void right() {
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.监督程序模式和用户模式之间的区别？
答：通过只能在系统模式（或者称为监督程序模式）下执行特权指令可以保证操作系统时刻控制整个计算机系统，并保证关键数据的安全。
4.陷阱与中断之间的区别？
答：中断是一个系统中由硬件产生的用于改变执行流程的信号。一个中断控制程序来处理中断，执行完成后返回被中断的程序指令。
陷阱是一个软件产生的中断。例如可以用陷阱提示I/O操作的完成，或者调用操作系统的系统调用，或者捕获算术运算错误。
5.下面哪些指令是特权指令？ a c d e a)设置定时器的值； b)读时钟； c)清除内存； d)关闭中断；
e)从用户模式切换到监督程序模式。 四、 补充作业
1.把下面的应用程序分为交互性和批处理两类： (a)字处理
(b)按月生成银行报表、
(c)计算圆周率到百万分位 (d)飞行模拟器
交互性：字处理、飞行模拟器
批处理：按月生成银行报表、计算圆周率到百万分位 2.判断对错
（1）陷阱可以被硬件触发也可以被软件触发。×
（2）一个操作系统的内核由一台机器上所有的系统软件和应用程序组成。× （3）交互性应用程序在程序运行过程中很少进行输入输出操作。× （4）系统调用既可以在用户模式下运行也可以在系统模式下运行。√