北工大操作系统作业合集

1、第八次作业基础作业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 130a. FCFS : 143, 86, 1470, 913, 1774, 948, 1509, 1022, 1

2、750, 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

3、, 4999, 0, 86, 130.总寻道距离 9813f. C-LOOK : 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 86, 130.总寻道距离 3363.2. 为什么文件分配的位图必须保存在大容量存储器中，而不是主存中？ 答：因为如果保存在内存中，当系统崩溃时， 这些空闲区间的信息将会被丢失，而如果保存 在大容量存储器中就可以解决这个问题。3假设要为一个文件换一个名字。一种选择是使用操作系统提供的RENAME 方法，另一种方法是：把文件复制为新文件，然后删除原来的文件以实现重命名。请问，这两种方法在 实现上有什么不同？答：RENAME方法

4、是修改目录文件的文件名部分， 而删除原来文件再重命名则需要再创立一 个新文件， 目录文件中增加一项，分配新空间；删除目录文件中的文件项目，然后回收占用 的空间。4请解释使用索引节点有什么好处 答：减小目录文件的大小，提高查找文件的效率 5在 UNIX 中 open 系统调用绝对需要么？如果没有会产生什么结果。答：如果没有 open 命令， 那么每个 read 命令都需要确定要打开的文件名。系统必须找到文 件的 i 节点， 虽然这个数据放入 cache 可以减少一些时间， 但是当数据变化的时候， i 节点的 数据需要刷新到磁盘上。6UNIX 系统中有关盘块的分配与释放是借助超级块中的栈来进行的。

5、假如某个时刻系统状况如下图所示， 若此时某个进程要删除文件 A，并归还它所占用的盘块 220，110，645，549， 176。请说明过程，并给出删除完毕后有关数据及表目的更改情况。786278802301106457. 考虑一个索引节点所表示的 UNIX文件的组织。 假设有 12 个直接块指针，在每个索引节 点中有一个单重、双重和三重间接指针。此外，假设系统块大小和磁盘扇区大小都是8K，如果磁盘块指针是 32 位，其中 8 位表示物理磁盘， 24 位表示物理块，那么a. 该系统支持的最大文件大小是多少？b. 该系统支持的最大文件分区是多少？c. 假设主存中除了文件索引节点外没有其他信息，访问

6、在位置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=128GBc. 使用从 (a) 得到的信息 , 发现直接块只能表示 96KB, 而一次间接块表示 16MB. 题目中要求的 请求位置在 13M 左右，使用一次间

7、接块 .就可以了。所以要用两次磁盘访问，一次访问一次 间接块，另一次访问包含数据的盘块第七次作业1什么是设备无关性？ 应用程序只按套路调用操作系统提供的功能即可，不关心实际的设备是什么，这就是 与设备无关性2以下各项工作由 I/O 软件的哪一层完成？a. 为一个磁盘读操作计算磁道、扇区、磁头；设备驱动程序b. 向设备寄存器写命令；中断处理程序c. 检查用户是否允许使用设备；设备独立性软件d. 将二进制整数转换成 ASCII码以便打印硬件3为什么在要打印的文件通常都假脱机输出到磁盘上？答：达到缓冲的目的，实现提高 I/O 设备性能的目的。为了打印一个文件，一个进程首先要生成需要打印的整个文件并把

8、它放在假脱机目录里。由守护进程打印该目录下的文件， 该进程是允许使用打印机设备文件的唯一进程。 通过保护设备文件来防止用户直接使用， 可以解决某些进程不必要地长期空占打印机的问题。第六次作业1假设页表在内存保存的分页系统，a.如果一次访问内存用 200ns，那么访问一个页内的一次数据访问用多少时间？b.如果加入 TLB，有 75%的命中率，那么内存有效访问时间是多少？ a）访问一个页内数据需要访问两次内存，第一次访问内存中的页表，第二次根据页表中的信息形成的物理地址访问内存访问数据，所以要用 200*2=400nsb）加入 TLB，获得物理地址的过程为：先在 TLB 中查找，如果 TLB中命中

9、，则直接获得 物理地址，如果 TLB 中不存在，则去访问页表，所以需要的访问时间为0.25*200=50ns总共需要的时间为 50ns+200ns=250ns2. 在一个虚拟存储管理系统中采用页式方法对内存空间进行管理，它有 24 位的虚拟地址 空间，而实际的物理地址空间是 16 位，页框大小为 2k。假设有两个进程 A 和 B。其中 A 进 程的 0、2页已经调入到内存的 2、3 号页框； B进程的 1、3页已经调入到内存的 7、8 号页 框。请问： A 进程的虚拟地址 12FF可以转换成什么物理地址？ B进程的虚拟地址 17BA可以 转换成什么物理地址？如果不能转换，操作系统会执行什么操作

10、？页框大小为 2k=211, 有 11 位的位移 。A 进程： 12FF=0001 0010 1111 1111 ,00010=2,A 进程中 2 页调进 3 号框，因此物理地址为： 0001 1010 1111 1111B 进程： 17BA=0001 0111 1011 1010 ，在进程 2 中没有 2 号页，需要的页面不在内存时，请 求调入所需的页面 判断对错如果缺页率太高，通常说明一个进程分得的页框太多了。第五次作业基础作业1内部碎片与外部碎片之间的区别？内部碎片： 内存分页时， 最后一页未装满的部分就是内部碎片。 或因调入的数据小于分 区而产生分区空间的浪费，称为内部碎片。外部碎片：

11、 共享时要分段， 在段的换入换出时未使用的部分就是外部碎片。 一开始运行 得很好，但是在执行一段时间后 , 会出现一些小的洞。这种在分区外的洞称为外部碎片。内 存按顺序有 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

12、 分配给 600k ，将 417 分配给 500k ，将 112 分配给 300k ，最后 426 没有可分配的。2假设一个有 8 个 1k 页面的逻辑地址空间，映射到一个32 个页框的物理内存，问：逻辑地址多少位？物理地址多少位？逻辑地址： 13 位物理地址： 15 位4（ 8.12 ）有段表段基地址长度02196001230014290100313275804195296下面的物理地址是多少？a)0,430; b)1,10; c)2,500; d)3,400; e)4,122a、 649 b 、 2310 c 、 590 d 、1727 e 、 2074 5在页面大小为 4k 的系统中，根

13、据图中所示 页表，下面的逻辑地址经过重定位之后的物理地址是什么？a)20; b)4100; c)8300A、49172 b 、 53252 c 、615486一台计算机为每个进程提供 65536 字节的地址空间，页面的大小为 4k。 一个程序有 32768 字节的正文， 16386 字节的数据， 15870 字节的堆栈，此 程序是否能装入此地址空间？若页面大小为 512 字节呢？4k 不能， 512 字节可以；解析过程：65536/4096=16 ，共计 16 个页面；正文需要页面： 32768/4096=8数据需要页面： 16386/4096=5对战需要： 15870/4096=4共需 17

14、 个页面，所以不能装入512 字节同理可得正好能够装入 补充作业判断对错 编译时绑定是大多数通用操作系统使用的地址绑定方法。 X 最佳适配法可以在内存分配过程中留下最小的洞。 为解决内存分配时导致的外部碎片可以采用压缩的方法来解决， 因此需要在地址绑定的时候 采用静态重定位方法。 X如果现在基地址寄存器的值是 1200，界限寄存器的值是 350，那么当前进程产生对绝对地址 1551 的访问是合法的。 X可重入代码不可以被共享。 X基础作业1考虑下面一组进程， 进程占用的 CPU区间长度以毫秒计算。 假设在 0时刻进程以 P1, P2,P3, P4, P5的顺序到达。进程区间时间优先级P1103

15、P211P323P414P552（1）画出 4 个 Gantt 图，分别演示使用 FCFS, SJF, 非抢占优先级（数字越小表示优先级 越高）和 RR（时间片 =1）算法调度时进程的执行过程。（2）每个进程的周转时间是多少？（3）每个进程在每种调度算法下的等待时间是多少？解：（ 1） GANTT图FCFS：P1 P2 P3 P4 P5SJF：P2 P4 P3 P5 P1非抢占优先级： P2 P5 P1 P3 P4RR：P1 P2 P3 P4 P5 P1 P3 P5 P1 P5 P1 P5 P1 P5 P1（2）周转时间：FCFSSJF非抢占优先级RRP110191619P211112P313

16、4187P4142194P5199614（3） 等待时间：FCFSSJF非抢占优先级RRP10969P210001P3112165P4131183P5144192考虑下面一个系统在某一个时刻的状态。AllocationMax AvailableA B C DA B C DA B C DP00 0 1 20 0 1 2 1 5 2 0P11 0 0 01 7 5 0P21 3 5 42 3 5 6P30 6 3 20 6 5 2P40 0 1 40 6 5 6使用银行家算法回答下面的问题：（1） Need 矩阵的内容（2） 系统是否处于安全状态（3） 如果从进程 P1 发来一个请求（ 0，4，2

17、， 0），这个请求是否可以立即满足？解：1） Need 矩阵ABCDP00000P10750P21002P30020P406422)处于安全状态，先是 P0完成，之后 P3，之后 P2，之后 P1，之后 P4。(3) 可以立即满足，满足后仍处于安全状态。补充作业判断对错在 RR调度中，上下文切换的时间应该小于时间片的长度。XSJF调度算法是最适合分时系统的调度算法。XFCFS调度算法只能是非抢占式的。如果资源分配图中有环，那么就一定有死锁。X死锁的时候系统一定处于非安全状态。第三次作业一、基础作业1. 什么是忙等待？ 持续地检测一个变量直到它具有某一个特定值称为忙等待。2吸烟者问题：有 3 个

18、吸烟者和一个供应者。 第一个吸烟者有自己的烟草； 第二个吸 烟者有自己的纸；第三个吸烟者有自己的火柴。供应者每次随机放两样东西到桌子上 提供给 3 个吸烟者之中的一个以完成吸烟。请用信号量为吸烟者和供应者进程编写程 序。Semaphore n2=0;Semaphore s=1;0 代表烟草， 1 代表纸， 2 代表火柴 ./ 供应者程序Void procucer()While(1)随机生成一个在 02之间的数 ;Wait(s);将除了表示的另外两件东西放在桌子上 ;Signal(ni);/ 吸烟者程序Void smoker(int i)While(1)Wait(ni);Somke();Sign

19、al(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 n2=0;/n0/n1 表示进程 W1/W2 可以从缓冲区 B 中

20、取出的数据个数；/ 进程 RVoid R()While(1)读入一个正数 m;Wait(s);将m放入 B中；if(m/2!=0)Signa(n0);ElseSignal(n1);Void w1()While(1);Wait(n0);从缓冲区 B 取数据 k;Signal(s);打印 K;Void w1()While(1);Wait(n1);从缓冲区 B 取数据 k;Signal(s);打印 K;2 有一个铁笼子， 猎手放入老虎，农民放入猪，动物园等待取走老虎，饭店等待取走 猪。笼子中只能放入一个动物。请使用信号量方法为猎手、农民、动物园、饭店进程编写程 序。Semaphore cage=1;

21、/ 可以放入笼子中的动物数量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); 从笼子中取出猪； sign

22、al(cage);3某寺庙，有小、老和尚若干。 有一个水缸，由小和尚提水入缸供老和尚饮用。水缸可容 10 桶水。水取自一个井中，水井窄，每次只能容一个水桶。水桶总数为3。水缸每次进出也仅 1 桶水， 不可以同时进行。 请设置合适的信号量描述小和尚、 老和尚取水、入水的 算法。Semaphore bucket=3;/ 水桶的数量Semaphore tank=1;/ 水缸每次能容水桶的数量 ;Semaphore s=10;/ 水缸容水桶水量 ;Semaphore well=1;/ 井每次能容水桶的数量；Semaphore empty=0;/ 水缸中现有的水量；Void youngmonk()Whi

23、le(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) 一

24、个计数信号量的值只能 取 0 或者 1. X(4) 在管程中本地变量只能由本地过程来访问。5. 选择题(1) 关于竞争条件那句话是对的？BA. 几个线程要并发访问同样的数据B. 几个线程要并发访问并修改同样的数据C. 只有在执行结果与执行顺序无关的时候发生(2) 关于原子指令那句话是对的？BA. 原子指令只能由一条机器指令组成B. 作为一个单独的，不可以中断的单元执行C. 不能用于解决临界区问题(3) 一个临界区的解决方案不需要实现下面的哪一条？CA. 互斥 B. 有空让进C. 原子性 D. 有限等待(4) 当低优先级的进程正在访问一个数据的时候，若一个高优先级的进程需要访问同样 的数据，可能

25、发生 AA. 优先级反转 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); 左岸过

26、河； 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分配给它。中期调度主要在分时系统中使用

27、。 将内存中的作业换出到外存中等到内存允许的情况下 再换入到内存中执行。长期调度确定把哪个作业放到内存中执行。 它们之间的主要区别是执行的频率不同。短期调度执行频率高而长期调度执行频率低。2. 两个进程进行上下文切换的操作通常， 操作系统必须保存当前运行进程的状态并恢复下一个要调度的进程的状态。保存一个进程的状态通常包括 CPU所有寄存器的值和内存的分配情况。3. 用户级线程和内核级线程之间的区别？相互对比的优势在哪里？(1) 内核不知道用户级线程的存在，但内核知道内核级线程的存在(2) 内核调度内核级线程，而用户级线程则由线程库调度在要体现系统灵活性的时候使用用户级线程好， 因为用户级线程可

28、以自己设计自己的调度。 内核级线程则被内核知道， 所 以可以保证一个线程阻塞时可以调度一个进程的另一个线程，减少系统开销。三、补充作业1假设有一个进程，它的工作流程是先运行150ms，然后进行 I/O，最后执行 250ms 结束。如果系统中的进程有三个状态，当时间片为 200ms 时，请写出进程 A 从被系统接纳到运行 结束所经历的状态转换并说明原因。答：被系统接纳之后：就绪 -运行（原因：被调度执行）、运行-阻塞（原因：执行 I/O 操作）、阻塞 -就绪（原因： I/O 操作完成）、就绪 -运行（原因：被调度执行）、运行 -就绪（原 因：时间片到）、就绪 -运行（原因：被调度执行）、结束。2. 图中程序的运行结果。Val