操作系统考试知识点
1.什么是操作系统？操作系统主要动力？
概念：
操作系统是指控制和管理整个计算机系统的硬件和软件管理资源，合理组织、调度计算机资源的分配，进而为用户和其他软件提供方便接口与环境的程序的集合，操作系统是计算机系统中最基本的系统软件。（操作系统是覆盖在硬件上的第一层软件，是对硬件系统的首次扩充）。
主要动力：
不断提高计算机资源利用率；方便用户；器件的不断更新换代；计算机体系结构不断发展；不断提出新的应用需求。
作用：
作为用户和计算机硬件之间的接口；系统资源的管理者；实现对计算机资源的抽象。
2、操作系统基本特性？
并发—两个或多个进程在同一时间间隔内发生
共享—系统中的资源供并发的进程共同使用
虚拟
异步。
3、处理机管理有哪些功能？进程控制、进程同步、进程通信、进程调度
4、存储器管理有哪些功能？内存保护、内存分配、内存扩充、地址映射
5、设备管理有哪些功能？缓冲管理、设备分配、设备处理。
6、文件管理有哪些功能？存储空间管理、目录管理、文件读写管理和保护。
7、用户与操作系统的接口包括？用户接口、程序接口（程序接口用系统调用实现）。
8、什么是进程？临界区、临界资源、进程互斥和同步、忙等概念、
进程：进程是正在运行的程序的实例（进程是一个具有独立功能的程序关于某个数据集合的一次运行活动/是系统进行资源分配和调度的基本单位）。
临界区：在每个进程中访问临界资源的那段代码。
临界资源：在一段时间内只允许一个进程访问的资源。
进程互斥：一组进程中的一个或多个程序段因共享某一共享资源而不许交叉执行，即不允许两个以上的共享该资源的并发进程同时进入临界区
进程同步：异步环境下的一组并发进程因直接制约相互发送消息而进行相互合作，等待，是各个进程按一定的速度执行的过程。
忙等：已经有进程进入临界区时，表明临界区资源正在被访问，其他试图进入临界区的进程都必须等待。
9、信号量机制，信号量必须设对
10、线程概念？
线程：是被系统独立调度和分派的基本运行程序单位，是比进程更小的能独立运行的基本单位，又称为轻量级线程。
11、进程和程序的区别？
进程是动态的，进程是程序的一次执行过程，是临时的有生命期的，它由创建而产生，完成任务后被撤销；
程序是静态的， 可以作为软件资源长期保存。
12、并发和并行（io和CPU、io和io）的区别？
并发是同一时间段内两个或以上的进程同时执行；
并行是同一时刻两个或以上的进程同时执行。
13、甘特图，求周转时间、吞吐量、等待时间，什么是吞吐量
吞吐量：单位时间内系统能完成的作业数。
14、可剥夺和不可剥夺算法有什么？
可剥夺（可抢占）算法：抢占式调度算法（CFS）、时间片轮转算法（Round Robin）；
不可剥夺（不可抢占）算法：实时调度算法(优先级调度算法)、死锁避免算法（银行家算法、资源分配图算法）。
15、死锁定义、四个必要条件、死锁避免、安全状态、资源分配图化简、死锁定理、银行家算法
什么是死锁：在多道程序设计中，当一组进程中的每个进程均无限期等待该组进程中其他进程才能引发的事件，系统则处于死锁状态。
形成死锁的必要条件：1互斥条件2请求和保持条件3不可抢占条件4循环等待条件。
死锁避免：系统在进行资源分配时，应该防止系统进入不安全状态。
安全状态：指系统能按进程某种推进顺序为每个进程分配其所需资源，直至满足每个进程所需数量，使每个进程都能顺利完成。
死锁定理：S为死锁状态的充分条件是当且仅当S的资源分配图是不可完全化简的。
16、如果系统中有n个进程，则在
运行状态：最多1个，最少0个；
就绪状态：最多n-1，最少0个；
等待状态：最多n个（死锁），最少0个。
17、存储管理的主要方式？实存储有几种方法填空，页式管理
分区存储管理、分页存储管理、分段存储管理、段页式存储管理、虚拟存储管理。
18、淘汰算法
最佳置换算法（optimal）、先进先出页面置换算法（FIFO）、最近最久未使用算法（LRU,least recently used）、最少使用置换算法（LFU）、Clock置换算法。
19、动态分区分配算法（基于顺序搜索）
首次适应算法FF（从链首开始查找，优先利用内存中的低地址部分空闲分区）；
循环首次适应算法NF（从上次找到的空闲分区的下个空闲分区开始查找，空闲分区分布均匀但缺乏大的空闲分区）；
最佳适应算法BF（满足要求且最小的空闲分区）--外部碎片
最坏适应算法WF（满足要求且最大的空闲分区，缺乏大空闲分区，产生碎片的可能性最小）
（FF\NF效率差不多，效率最高）
碎片：难以利用的很小的空闲分区。
20、页式管理！！！！！给页表、逻辑地址1000\2000\4000、每页大小1024，计算物理地址，取整取余。地址越界
页号P，页内偏移量W，逻辑地址A，页面大小L；
逻辑地址对页面大小取整INT[A/L]，取余
1000/1024=0 1000mod1024=1000 第0页在第i块，物理地址为：i*1024+1000
2000/1024=1 2000mod1024=976 第1页在第n块，物理地址为：n*1024+976
4000/1024=3 4000mod1024=928 第3页在第x块，物理地址为：x*1024+928>页面大小，该逻辑地址非法越界。
21、多级页表---P
22、调入:预调入、请求调入
预调页策略—以预测为基础，将那些预计在不久后被访问的页面事先调入到内存中。
请求调页策略—当进程在运行中需要访问某部分数据和程序时，若发现其所在的页面不在便立即提出请求，由操作系统将其所在的页面调入。
23、访问内存的有效时间，引入快表
求EAT
24、什么是io设备？
IO设备指输入输出设备，是数据处理系统的关键外部设备，可以和计算机交互使用。
除了内存和CPU的设备称为外设。
25、IO系统的基本功能？
隐藏物流设备的细节、与设备的无关性、提高处理机和IO设备利用率、对IO设备进行控制、确保对设备的正确共享、错误处理。
26、IO系统的软件层次结构？最上层最下层
27、块设备、字符设备是什么？
块设备是指数据的存取和传输是以数据块为单位的设备；（磁盘（一个扇区，簇为单位，有多个sector）
字符设备是指数据的存取和传输是以字符为单位的设备（键盘）。
28、输入输出的通道类型？数组选择通道、字节选择、字节通道
30、什么是内中断？
内中断指因硬件出错或运算出错引起的中断，是不可屏蔽中断。
31、数据传输的四种控制方式？、
程序轮询方式（循环指令，busy=1，尚未完成输入字符）
中断方式（CPU和io设备都处于忙碌状态，CPU用很短的时间处理中断，大大提高整个系统的资源利用率和吞吐量）---字节
DMA方式（命令/状态寄存器、地址寄存器、数据寄存器、数据计数器，减少了CPU干预）---一个数据块
通道方式（通道程序结束位P=1表示本条指令是程序最后一条，程序结束；记录结束标志R=1表示处理某记录的最后一条指令）---一组数据块
缓冲区不看
32、磁盘格式化：低格（重新划分磁道区）和高格（文件分配表，数据没有删）
低级格式化：将磁盘的各个磁道划分为扇区；
高级格式化：设置一个引导块，空闲存储管理、根目录和一个文件系统，同时在分区表中标记该分区所使用的文件系统。
33、磁盘的三个时间？
寻道时间=S+m*n(启动磁头臂的时间+跨越n个磁道的时间)
延迟时间=旋转磁盘，使磁头定位到目标扇区
平均延迟时间=1/2*1/r=1/2r，1/r是转一圈的时间=读写一个磁道的时间
传输时间=从磁盘读写数据的时间
1/r*b/N（读写一个磁道的时间*磁道数），一共b字节，每个磁道存N字节
存储容量=磁头数（盘面数）*磁道数（柱面数）*每道扇区数*每道字节数
访问时间=寻道时间+旋转延迟时间+传输时间+控制器时间
33、磁盘引臂调度算法：FCFS，SCAN，最短作业优先。有异议的不考
先到先服务FCFS
最短寻找时间优先
SCAN（从内向外移动，直到最外层再向内从大到小移动)响应频率不平均
LOOK（从内向外移动，直到没有请求再向内从大到小移动）
C-SCAN（从内向外移动，直到最外层再直接移到0号位置，再向外移动）
C-LOOK（从内向外移动，直到最外层再直接移到最内层有请求的位置，再向外移动）
34、什么是文件？什么是文件目录（fcb）？逻辑结构、物理结构（顺序、链接、索引）。
文件：指由创建者所定义的、具有文件名的一组相关元素的集合
文件目录：一种数据结构，用于标识系统中的文件及其物理地址，供检索时使用。
35、FAT会计算，课后思考题
36、文件存储空间分配管理的几种方式?
空闲表法和空闲链表法、位示图法、成组链接法。
文件逻辑结构：
按结构分类—有结构文件、无结构文件；
按组织方式分类—顺序文件、索引文件、索引顺序文件；
文件物理结构：
顺序文件、索引文件。
37、块地址在内存和块在内存不一样？
块地址指的是内存中某个块的起始地址，而块在内存空间中指的是一段连续的地址空间。
38、磁盘三维，公式(取整取余、对余数再取整取余)？6个盘面、8个扇区、200磁道数，数数也能数出来（6列，6*8=48，0-47）
柱面号=块号/（磁头数*总扇区数）
盘面号=磁头号=（块号mod（磁头数*总扇区数））/一个盘面的扇区数
扇区号=（块号mod（磁头数*扇区数））mod扇区数
39、混合索引。一个i结点对应一个文件（inode）
部分习题总结
操作系统引论
1． 分时系统的响应时间（及时性）主要是根据（A）确定的，而实时系统的响应时间则是由（B）确定的。
A， B：（1）时间片大小；（2）用户数目；（3）计算机运行速度；（4）用户所能接受的等待时间；（5）控制对象所能接受的时延；（6）实时调度
解答：A：（4）；B：（5）
2． 在分时系统中，为使多个用户能够与系统交互，最关键的问题是（A）；当用户数目为100时，为保证响应时间不超过2s，此时的时间片最大应为（B）。
A：（1）计算机具有足够高的速度；（2）内存容量足够大；（3）系统能及时接收多个用户的输入；（4）能在较短的时间内，使所有用户程序都能得到运行；（5）能快速进行内外存对换；
B：（1）10ms；（2）20ms；（3）50ms；（4）100ms；（5）200ms；
解答：A：（4）；B：（2）
3． 从下面关于模块化程序的的叙述中选出，选出五条正确的叙述。
（1） 使程序设计更为方便，但比较难维护
（2） 便于由多人分工编制大型程序
（3） 便于软件功能扩充
（4） 在内存能够容纳的前提下，应使模块尽可能大，以减少模块的个数
（5） 模块之间的接口叫数据文件
（6） 只要模块接口不变，各模块内部实现细节的修改，不会影响别的模块
（7） 使程序易于理解，也利于排错
（8） 模块间的单向调用关系，形成了模块的层次式结构
（9） 模块愈小，模块化的优点愈明显。一般来说，一个模块的大小在10行以下。
（10） 一个模块实际上是一个进程
解答：2、3、6、7、8
4． 采用（A）结构时，将OS分成用于实现OS最基本功能的内核和提供各种服务的服务器两个部分。通常，下列模块中必须包含在操作系统内核中的是（B）模块。
A：（1）整体式；（2）模块化；（3）层次式；（4）微内核；
B：（1）内存分配；（2）中断处理；（3）文件处理；（4）命令处理；
解答：A：（4）；B：（2）
进程管理习题
1． 在将CPU的执行状态分为用户态和核心态的系统中，应该在核心态下执行的指令依次为（A）、（B）、（C）。而从用户状态转换到系统状态是通过（D）实现的。
A，B，C：（1）屏蔽所有中断；（2）读时钟；（3）设置时钟的值；（4）存取内存中某地址单元的值；（5）停机。
D：（1）执行进程直接修改程序状态字；（2）中断屏蔽；（3）中断；（4）进程调度；
解答：A：（1）；B：（3）；C：（5）；D：（3）
2． 在分时系统中，导致进程创建的典型事件是（A）；在批处理系统中，导致进程创建的典型事件是（B）；由系统专门为运行中的应用进程创建新进程的事件是（C）；在创建进程时，（D）不是创建所必须的步骤。
A：（1）用户注册；（2）用户登录；（3）用户记账；（4）用户通信。
B：（1）作业录入；（2）作业调度；（3）进程调度；（4）中级调度。
C：（1）分配资源；（2）进行通信；（3）共享资源；（4）提供服务。
D：（1）为进程建立PCB；（2）为进程分配内存等资源；（3）为进程分配CPU；（4）将进程插入就绪队列；
解答：A：（2）；B：（2）；C：（4）；D：（3）
3． 从下面对临界区的论述中，选出两条正确的论述。
（1） 临界区是指进程中用于实现进程互斥的那段代码
（2） 临界区是指进程中用于实现进程同步的那段代码
（3） 临界区是指进程中用于实现进程通信的那段代码
（4） 临界区是指进程中用于访问共享资源的那段代码
（5） 临界区是指进程中访问临界资源的那段代码
（6） 临界区是指进程中用于实现进程互斥的那段代码
（7） 若进程A与进程B必须互斥地进入自己的临界区，则进程A处于对应的临界区内时，仍有可能被进程B中断
（8） 若进程A与进程B必须互斥地进入自己的临界区，则进程A处于对应的临界区内时，便不能被进程B中断
解答：5、6
4． 使用mail命令的信箱通信属于（A），因为信息是被发送到接收方的（B）中；使用write命令，实现的是（C）通信，因为信息是被发送到接收方的（D）；使用共享文件进行通信的方式属于（E）。
A，C，E：（1）共享存储器；（2）实时通信；（3）消息缓冲通信；（4）非实时通信；（5）管道通信。
B，D：（1）消息缓冲队列；（2）内存；（3）信箱；（4）消息缓冲区；（5）屏幕；（6）共享存储区
解答：A：（4）；B：（3）；C：（2）；D：（5）；E：（5）
5． 从下面的叙述中选出一条正确的叙述。
（1） 操作系统的一个重要概念是进程，不同进程所执行的代码也不同
（2） 操作系统通过PCB来控制和管理进程，用户进程可从PCB中读出与本身运行状态相关的信息
（3） 当进程由执行状态变为就绪状态时，CPU现场信息必须被保存在PCB中。
（4） 当进程申请CPU得不到满足时，它将处于阻塞状态
（5） 进程是可于其它程序并发执行的程序在一个数据集合上的运行过程，所以程序段是进程存在的唯一标志
解答：3
6． 从下面的叙述中选出4条正确的叙述。
（1） 一个进程的状态发生变化总会引起其他一些进程的状态发生变化。
（2） 进程被挂起（suspend）后，状态变为阻塞状态。
（3） 信号量的初值不能为负值。
（4） 线程是CPU调度的基本单位，但不是资源分配的基本单位。
（5） 在进程对应的代码中使用wait、signal操作后，可以防止系统发生死锁。
（6） 管程每次只允许一个进程进入。
（7） wait、signal操作可以解决一切互斥问题。
（8） 程序的顺序执行具有不可再现性。
解答：3、4、6、7
7． 试比较进程和管程的异同点
（1） 管程和进程都定义了数据结构,进程定义的是私有数据结构进程控制块;管程定义的是公共数据结构，如消息队列。
（2） 管程和进程都在各自的数据结构上进行有意义的操作。进程是由顺序程序执行有关操作，管程主要是同步操作和初启操作。
（3） 管程和进程设置的目的不同，进程是为了更好的刻画可实现系统的并发性而设置的；管程是为了解决进程进程的公共变量，解决共享资源的互斥使用问题而设置的。
（4） 进程通过调用管程中的过程对共享变量进行操作，此时该过程就如通常的子程序一样被调用而处于被动工作方式。因此称管程为被动成分，于此相对应的进程则处于主动工作方式而被称为主动成分。
（5） 由于进程是主动成分，故进程之间能被并发执行；而管程是被动成分，管程和调用它的进程不能并发执行。
（6） 进程可由“创建”而诞生、由“撤消”而消亡，即具有生命期；而管程是操作系统中的固有成分，无需进程创建，也不能被进程撤消只能被进程调用。
8． 为什么说pcb是进程的唯一标识
9． 算法
10． 某寺庙，有小、老和尚若干。有一水缸，由小和尚提水入缸供老和尚饮用。水缸可容10桶水，水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为3个。每次取、入缸水仅为1桶，且不可同时进行。试用P、V操作给出有关取水、入水的算法描述。
水缸互斥信号量：mutex1=1；井互斥信号量：mutex2=1；
同步信号量：empty=10；full=0；
水桶资源总数信号量：count=3；
11． 有一个仓库，可以存放A和B两种产品，但要求：
（1） 每次只能存入一种产品（A或B）
（2） -N<A产品数量-B产品数量<M
其中,N和M是正整数。试用P、V操作描述产品A与产品B的入库过程。
根据题意A产品数量不能比B产品数量少N个以上，A产品数量不能比B产品数量多M个以上，初始时sa为M-1，sb为N-1。当往库中存放入一个A产品数量时，则允许B产品数量也增加1；当往库中存放入一个B产品数量时，则允许A产品数量也增加1；
A 、B入库过程: (写法不唯一，也可以分开写)
Sem mutex=1
Sem sa=M-1;
Sem sb=N-1;
Main()
{
While(1)
{
取一个产品；
if(取的是A产品)
{
p(sa)
p(mutex)
将产品入库；
v(mutex)
v(sb);
}
Else
{
p(sb)
p(mutex)
将产品入库；
v(mutex)
v(sa)
}
}
}
12． 写者优先算法
Reader: writer:
p(m) p(k)
p(w) if(wc==0) {p(w) }
p(mutex) wc=wc+1
if(rc==0) { p(s)} v(k)
rc=rc+1 p(s)
v(mutex) < write>
v(w) v(s)
v(m) p(k)
<read> wc=wc-1
p(mutex) if(wc==0) {v(w)}
rc=rc-1 v(k)
if(rc==0) {v(s)} 7
v(mutex)
读者：
while (true) {
P(m);
P(w);
P(rmutex);
readcount ++;
if (readcount==1) P (s);
V(rmutex);
V(w);
V(m);
读
P(mutex);
readcount --;
if (readcount==0) V(s);
V(mutex);
};
写者：
while (true) {
P(wmutex);
if (wcount==0) P (w);
wcount ++;
V(wmutex);
P(s);
写
V(s);
P(wmutex);
wcount --;
if (wcount==0) V (w);
V(wmutex);
};
管程
Type readers_writers = Monitor;
Var rq,wq: condition;
reading_count,write_count:integer;
Define start_read,finish_read,
start_write,finish_write;
Procedure start_read;
Begin
If write_count>0 Then
wait(rq);
reading_count++;
signal(rq);
End;
Procedure finish_read;
Begin
reading_count--;
If reading_count=0
Then signal(wq)
End;
Procedure start_write
Begin
write_count++;
If (write_count>1) or
(reading_count>0)
Then
wait(wq)
End;
Procedure finish_write;
Begin
write_count--;
If write_count>0
Then signal(wq)
Else signal(rq)
End;
Begin
reading_count:=0;
write_count:=0;
End;
Var rw:readers_writers;
读者： 写者：
rw.start_read; rw.start_write;
{reading} {writing}
rw.finish_read; rw.finish_write
处理机调度与死锁习题
1． 一台计算机有8台磁带机。它们由N个进程竞争使用，每个进程最大需求为3，请问N为多少时，系统没有死锁危险，并说明原因。
N=3
2． 在一个使用多级反馈队列的系统中，一个使用CPU较多的进程需要执行50秒。如果第一个队列时间片为5，并且较低一级的时间片是上一级时间片的2倍，那么这个作业会被中断多少次，当它终止时处于哪级队列？
3次，4级
存储管理习题
1． 具有两级页表的页式存储管理与段页式存储管理有何差别？
具有两级页表的页式存储管理的地址空间依然是一维的，两级页的划分对于进程来说都是透明的。而段页式存储管理的地址空间是二维的，用户能感觉到段的划分。
2． 何谓请调？何谓预调？为何在预调系统中必须辅以请调？
所谓请调是当页故障发生时进行调度，即当被访问页面不在内存时由动态调页系统将其调入内存。显然，采用纯请调策略，被移入内存的页面一定会被用到，即不会发生无意义的页面调度。但是，请调有一个缺点：从缺页中断发生到所需页面被调入内存，这期间所对应的进程必须等待，如此将会影响进程的推进速度。
预调也称先行调度，是在页故障发生前进行调度，即当一个页面即将被访问之前就由动态调页系统将其调入内存。易见，预调可以节省进程因页故障而等待的时间。预调通常根据程序的顺序行为特性而做出：如某进程当前正访问第12页，则接下来很可能会访问第13页、第14页，此时可将第13页甚至第14页预先调入内存。这样当该进程访问第13页以至第14页时它们已经在内存中，不会发生缺页故障，从而提高进程的推进速度。
预调不一定是百分之白准确的。由于程序中存在转移语句，第13页用完后可能需要访问第10页，而该页目前可能不在内存。也就是说，预先调入的页面可能未被用到，预先未调入的页面可能被用到。当访问到预先未调入内存的页面时，仍会发生缺页中断。因而，在采用预调的系统中，必须辅以请调功能。
3． 给定某系统的各种资源使用特征如下：
CPU 低
交换设备 非常高
其他I/O设备 低
对于以下情况，说明是明显改进、明显降低了CPU利用率，还是对CPU利用率影响很小。
（11） 安装更快的CPU
（12） 安装更大的交换设备
（13） 安装更快的交换设备
（14） 安装更多的内存
（15） 安装更快的内存
（16） 增加多道编程的程度
（17） 降低多道编程的程度
（18） 安装更快的I/O设备
解答：
高的交换设备利用率和低的内存利用率，都会使系统到整个性能由于过多的交换而降低。
（a） 安装更快的CPU
更快的CPU可能降低CPU的利用率（尽管降低的很少）
（b） 安装更大的交换设备
这没有影响
（c） 安装更快的交换设备
这可能有助于提高CPU利用率。因为CPU可能由于等待交换操作完成而经常空闲。
（d） 安装更多的内存
这也可能有帮助，由于减少了需要的交换总量（因此减少了交换设备的I/O操作频率）。
（e） 安装更快的内存
没有影响。
（f） 增加多道编程的程度
由于系统颠簸得更厉害，进而会降低性能。
（g） 降低多道编程的程度
这可能是改进性能的无代价方式。多道程序的主要目标是让足够的进程进入内存，使得所有的进程都很少阻塞。由于CPU和设备的利用率很低，这降低进程数目（减少交换），然而还有就绪进程准备在CPU上运行。
（h） 安装更快的I/O设备
如果设备利用率本来就很低，安装更快的I/O设备，至多能对CPU利用率有很小的改善。
4． 给定某系统的各种资源使用特征如下：
CPU 低
交换设备 低
其他I/O设备 高
对于以下情况，说明是明显改进、明显降低了CPU利用率，还是对CPU利用率影响很小。
（19） 安装更快的CPU
（20） 安装更大的交换设备
（21） 安装更快的交换设备
（22） 安装更多的内存
（23） 安装更快的内存
（24） 增加多道编程的程度
（25） 降低多道编程的程度
（26） 安装更快的I/O设备
解答：
（a） 安装更快的CPU
轻微降低或没有影响。
（b） 安装更大的交换设备
没有影响
（c） 安装更快的交换设备
没有影响或影响很小。
（d） 安装更多的内存
影响很小或没有影响。
（e） 安装更快的内存
影响很小或没有影响。
（f） 增加多道编程的程度
可能改进。
（g） 降低多道编程的程度
在一定程度上降低性能。
（h） 安装更快的I/O设备
可能改进。
5． 已知某系统有四个页框，下面的表格表示各个页、装入时间、最后访问时间、页面重写标志位、访问位。(一定要写明原因，否则扣分)
页号
装人时间
最后访问时间
页面重写标志位
访问位
0
227
327
1
0
1
345
367
1
1
2
101
331
1
1
3
234
382
0
1
（i） FIFO算法将替换哪一页？
（j） LRU算法将替换哪一页？
（k） NRU算法将替换哪一页？
（l） SECOND CHANCE算法将替换哪一页？
FIFO算法将2页
LRU算法将0页
NRU算法将替换0页
SECOND CHANCE算法将替换0页
文件管理习题
1． 在UNIX System Ⅴ中，如果一个盘块的大小为1KB，每个盘块号占4个字节，那么一个进程要访问偏移量位263168字节处的数据时，需要经过几次间接？（写出简单计算过程）
263168/1024=257,263138mod1024=0块内偏移量为0
10<257<266,所以263168的块号在一次间接内
2． UNIX System Ⅴ系统为使文件的索引表较小，又能允许组织大文件，采用直接索引与多次间接索引（多级索引）方式，假设每个磁盘块大小为1024个字节，并且每个间接块容纳256个块号，试问
1) 直接索引、一次间接、二次间接、三次间接所能访问的文件大小分别为多少块？
2) 假设某个文件的FCB已在内存，但其他信息均在外存，为了访问该文件中某个位置的内容，最少需要几次访问磁盘？最多需要几次访问磁盘？
3) 某进程要访问字节偏移量为9000、18000和350000处的数据，应该如何找到它所在磁盘块及其块内位移量？
4) 画出简单的示意图。
直接索引：10
一次间接：10+256
二次间接： 10+256+256*256
三次间接： 10+256+256*256+256*256*256
某进程要访问字节偏移量为9000处的数据：
9000/1024=8,9000mod1024=808
直接寻址：从i-addr（8）中找到相应的物理块号，在此块号内找808字节，为所要访问的数据。
某进程要访问字节偏移量为18000处的数据
17 592
一次间址：7表目中寻找的磁盘号592单元的数据为所要访问的数据。
某进程要访问字节偏移量为350000处的数据
341 816 341-266=75 [ 75/256]=0
二次间址：二次间址0表目中寻找的磁盘号一次间址的物理块号，在一次间址75表目处得到的物理块，其816单元的数据为所要访问的数据。
3． 例子：一个FCB有48个字节，符号目录项占 8字节，文件名6字节，文件号2字节，分解前后平均访盘次数。
基本目录项占 48-6=42字节
假设，物理块大小512字节
解：分解前：占512/48=10个FCB
分解后：占512/8=64个符号目录项或512/42=12个基本目录项
假设：目录文件有128个目录项
分解前：占13块
分解后：符号文件占2块
基本文件占11块
查找一个文件的平均访盘次数
分解前：(1+13)/2=7次
分解后：(1+2)/2 +1 =2.5次
减少了访问硬盘的次数，提高了检索速度
4． 某文件系统中，根目录长驻内存。目录文件采用链接结构，普通文件采用三级索引结构。假设一个物理块放10个目录项，一个目录下最多放40个文件。如果下级文件是目录文件，则上级目录项指向该目录文件的首地址；如果下级文件是普通文件，则上级目录项指向该文件的文件控制块。又假设索引表放在FCB中，如果要读取K的第一块或最后一块，需要启动硬盘最少几次，最多几次？
（假设文件按自左向右的顺序建立）
5． 位示图
计算公式：
已知字号i，位号j
块号＝i×字长＋j
已知块号：
字号＝[ 块号/字长]
位号＝块号 mod 字长
6． 某系统使用连续分配.为了在101块的文件中添加或删除一个块应进行多少次读和写的操作?说明原因。（只写得数不说明扣分）。假设：
l 文件的第一个块的地址已经在内存中
l 要增加的信息块已经在内存中
l 在文件的末尾有空间可供扩展，而在文件的开始位置不能扩展
l 中间块是第51个块
l 不计增加一个删除块到空闲表所需要的I/O操作
1) 在开头增加一个块
2) 在中间块后增加一个块
3) 在末尾增加一个块
4) 删除开头的块
5) 删除中间块
6) 删除末尾的块
7． 在一个使用链接分配的系统中，回答和前面一题相同的问题。
8． 在使用索引分配的系统中，回答和前面一题相同的问题。假设所有需要的索引块都在内存中。如果一个索引块的内容改变了，不把修改后的信息重写到磁盘的输出操作计算在内。
1
a) 203
b) 101
c) 1
d) 0
e) 100
f) 0
2 2
a) 1
b) 53
c) 103
d) 1
e) 52
f) 101
3 3
a) 1
b) 1
c) 1
d) 0
e) 0
f) 0
9． 一个文件系统使用大小为256字节的物理块。每个文件都有一个目录项给出了文件名、第一个块的位置、文件的长度和最后一块的位置。假设目录项和最后读取的物理块已经在主存。在下面的三种情况下，在使用连续分配的系统中、链接分配的系统中、索引分配的系统中，假设索引分配系统中目录项中包括第一个索引块（不是文件中的第一个块）的位置，每一个索引块包含指向127个文件块的指针和一个指向下一个索引块的指针，除了最后读的块外，假设含有指向最后读的块的指针的索引块也在主存中，但是内存中没有其他的索引块。为了访问指定的块，需要读多少个物理块？（包括指定的块）。
1) 最后读的块号：100，将要读的块号：600。
2) 最后读的块号：20，将要读的块号：21。
3) 最后读的块号：500，将要读的块号：200。
连续分配的系统中：1；1;1
链接分配的系统中：500；1;200
索引分配的系统中：5；1;3
设备管理习题
1． 存放在磁盘上的文件以链接结构组织，假定磁盘的分块大小为每块512字节，而文件的逻辑记录的大小为每个记录250字节。现有一个文件共有10个逻辑记录，请回答：（10分）
1) 采用成组操作时，几个逻辑记录为一组较合适？
每个盘块存放两个逻辑记录。需要5个盘块。
2) 画出成组时的链接结构示意图
2． 假定有一若有一个磁盘共有100个柱面，每个柱面上有8个磁道，每个盘面被划分成4个扇区。现有一个含3200逻辑记录的文件，逻辑记录的大小与扇区的大小一致，该文件以顺序结构的形式被存放到磁盘上。柱面、磁道、扇区以及逻辑记录的编号均从“0”开始。文件信息从0柱面、0磁道、0扇区开始存放，请问
1) 如何确定该文件的第3000个逻辑记录存放在磁盘上的位置，其柱面号、磁头号、和扇区号？
扇区数=8*4=32，柱面号3000/32=93,
磁头号3000mod32=24,24/4=6,
扇区号24mod4=0
2) 第32柱面的第1磁道的第0扇区存放了该文件的第几个记录？
每个盘面4个扇区，每个柱面8个磁道，第32柱面、第1磁道、第0扇区，
0+4*（1+32*8）=1028
解答：1）93 6 0
2）1028
3． 文件分配表FAT是管理磁盘空间的一种数据结构，用在以链接方式存储文件的系统中记录磁盘分配和跟踪空白磁盘块。FAT整个磁盘仅设一张。如果文件首块号为2，查找FAT序号为2的内容得知接着物理块2的后继物理块是5；再查FAT序号为5的内容得知接着物理块5的后继物理块是7；接着继续查FAT序号为7 的内容为“^”，即改文件结束标志，所以该文件顺序由物理块2、5、7组成。假设磁盘物理块大小为1KB。
1) 对540MB的硬盘其文件分配表FAT需要占用多少存储空间？
540M/1K=540K，540K<1024K=2的20次方，20位需要2.5个字节（3个字节是24位），2.5*540K=1350K
2) 当硬盘容量为1.2G时，文件分配表又需占用多少存储空间？
1.2G/1k=1.2M,1.2M<2M=2的21次方，需要3字节，3*1.2M=3.6M
1350k 4.8M。
4． 假定有一个具有200个磁道（编号为0～199）的移动头磁盘，在完成了磁道125处的请求后，当前正在磁道143处为一个请求服务。若请求队列以FIFO次序存放，即86，147，91，177，94，150，102，175，130。对下列每一个磁盘调度算法，若要满足这些要求，则总的磁头移动次数为多少？
1) FCFS
2) SSTF
3) SCAN
4) CSCAN
5． 在单缓冲的情况下，假设T是从磁盘输入一块数据的时间，C是CPU对一块数据进行处理的时间，而M是将一块数据从缓冲区传送到用户区的时间。当一用户进程要按顺序访问的方式处理大量数据时，请问系统对一块数据的处理时间是多少？画图说明。
MAX（C，T）+M
6． 在双缓冲的情况下，假设T是从磁盘输入一块数据的时间，C是CPU对一块数据进行处理的时间，而M是将一块数据从缓冲区传送到用户区的时间。当一用户进程要按顺序访问的方式处理大量数据时，请问系统对一块数据的处理时间是多少？画图说明。
MAX（C，T）
7． I/O软件一般分为哪四个层次？每层完成哪些功能？画图说明。
层次
用户进程
进行I/O调用；格式化I/O；SPOOLing
设备无关软件
命名；保护；阻塞；缓冲；分配
设备驱动程序
建立设备寄存器；检查状态
中断处理程序
当I/O结束时唤醒驱动程序
硬件
8． 说明向设备寄存器写命令、检查用户是否有权使用设备、将二进制转换成ASCII码以便打印分别是在I/O软件的哪一层完成的？
向设备寄存器写命令：设备驱动层
检查用户是否有权使用设备：设备无关软件层
将二进制代码转换成ASCII码以便打印：用户层
