这些习题为学校老师布置的习题，这些答案有些是我自己总结的，有些是来源于网上，不保证正确，如果有地方有问题，欢迎在评论区与我交流，谢谢各位了。

进程

1. 在操作系统中为什么要引入进程概念？它与程序的差别和关系是怎样的

早期的计算机一次只能执行一个程序，这种程序完全控制系统，并且访问所有资源，相比之下，现代计算机系统允许加载多个程序到内存，以便并发执行，而这种改进要求：对各种程序提供更严的控制和更好的划分，这些需求导致了进程。进程是程序的一次执行。

2. PCB的作用是什么？它是怎样描述进程的动态性质的

PCB(Process Control Block)进程控制块，在操作系统内用来维护每个进程的信息，包括：进程状态、程序计数器、CPU寄存器、CPU调度信息、内存管理信息、记账信息、I/O状态信息等。由于PCB中保存了进程状态，就绪态、等待态、运行态等等，通过进程状态的切换来描述进程的动态性质。

3. 进程的基本状态有哪几种？试描绘进程状态转换图

进程的基本状态包括：就绪态、阻塞态和运行态

4. 什么是进程的互斥和同步？

  • 同步：确保共享同一逻辑地址空间的协作进程有序执行，从而维护数据的一致性
  • 互斥：同步的特殊情况，当一个进程在临界区内执行时，其他进程都不能在临界区执行。

5. 什么是临界区和临界资源？进程进入临界区的调度原则是什么？是否所有的共享资源都是临界资源？为什么？

  • 临界区：每个进程有一段代码，这段访问临界资源的代码，就称为临界区
  • 临界资源：一次只允许一个进程访问的资源，称为临界资源
  • 进程进入临界区的调度原则：
    • 如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。
    • 任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其他所有试图进入临界区的进程必须等待。
    • 进入临界区的进程要在有限时间内退出，以便其他进程能及时进入自己的临界区。
    • 如果进程不能进入自己的临界区，则应让出CPU，避免进程出现忙等现象。
  • 不是所有的共享资源都是临界资源。因为临界资源是一次仅允许一个进程使用的资源，而系统中有很多资源可以让多个进程同时使用，例如硬盘、正文段等。

6. 简述计数信号量的定义和作用。P、V操作原语是如何定义的？（伪代码描述）

定义：相当一个信号灯，表示状态，是在多线程环境下使用的一种设施，是可以用来保证两个或多个关键代码段不被并发调用。主要用来解决进程同步与互斥问题的机制。

pv操作原语定义：

void P(semaphore s) {
	s.count--;
	if(s.count < 0) {
		1. 该进程阻塞
		2. 插入等待队列中
		3. 转进程调度程序
	}
}

void V(semaphore s) {
	s.count++;
	if(s.count <= 0) {
		1. 唤醒相应的等待队列中的进程
		2. 将进程的状态改为就绪态
		3. 返回或转进程调度程序
	}
}

7. 系统中只有一台打印机，有三个用户的程序在执行过程中都要使用打印机输出计算结果。设每个用户程序对应一个进程。问：这三个进程间有什么样的制约关系？试用P，V操作写出这些进程使用打印机的算法。

三个进程为互斥的制约关系，所以定义mutex为互斥信号量，初值为1

mutex = 1

//打印机1：
P(mutex)
使用打印机
V(mutex)

//打印机2：
P(mutex)
使用打印机
V(mutex)

//打印机3：
P(mutex)
使用打印机
V(mutex)

8. 设有无穷多个信息，输入进程把信息逐个写入缓冲区，输出进程逐个从缓冲区中取出信息。针对下述两种情况：（1）缓冲区是环形的，最多可容纳n个信息；（2）缓冲区是无穷大的。试分别回答下列问题：（1）输入、输出两组进程读\写缓冲区需要什么条件？（2）用P，V操作写出输入、输出两组进程的同步算法，并给出信号量含义及初值。

（1）第一种情况：输入输出两组进程读/写缓冲区需要满足的条件：

  • 读写需要同步
  • 写入的数据不能超过缓冲区的大小

第二种情况：输入输出两组进程读/写缓冲区需要满足的条件：

  • 读写需要同步

（2）第一种情况PV操作： 首先设置信号量：一个信号量mutex用来做为互斥信号量，初值为1，两个同步信号量：empty和full，分别表示空和满的缓冲区数量，empty初始化为n，full初始化为0。 设置输入输出进程表示的指针in和out

do {
	P(empty);
	P(mutex);
	queue.push(数据);
	in = (in + 1) % n;
	V(mutex);
	V(full);	
}while(true);

//读取出缓冲区
do {
	P(full);
	P(mutex);
	queue.pop(数据);
	out = (out + 1) % n;
	V(mutex);
	V(empty);	
}while(true);

第二种情况PV操作：由于缓冲区无限大，所以不需要设置empty信号量；缓冲区不成环，所以in和out的更行方式也需要改变

//写入缓冲区
do {
	P(mutex);
	queue.push(数据);
	in = in + 1;
	V(mutex);
	V(full);	
}while(true);

//读取出缓冲区
do {
	P(full);
	P(mutex);
	queue.pop(数据);
	out = out + 1; 
	V(mutex);	
}while(true);

9. 为什么要引入高级通信机制？它有什么优点？说明消息缓冲通信机制的基本工作原理和过程

(1) 低级通信机制如信号量效率太低，一次只能唤醒一个进程，而且如果程序员没有正确使用信号量来解决临界区问题时，很容易生成各种类型的错误，所以需要引入高级通信机制来解决这些问题。

(2) 优点：不仅能够保证相互制约的进程之间的相互关系，还同时实现了进程之间的信息交换。其基本思想是：根据“生产者-消费者”原理，利用内存中公用消息缓冲区实现进程之间的信息交换。

(3)基本工作原理和过程：内存中开辟了若干消息缓存区，用以存放消息，每当一个进程（发送进程）向另一个进程（接收进程）发送消息时，便申请一个消息缓冲区，并把已准备好的消息发送到缓冲区中，然后把该消息缓冲区插入到接受进程的消息队列中，最后通知接受进程，接收进程收到发送进程发送到的通知后，从本进程的消息队列中摘下一消息缓冲区，取出所需的消息，然后把消息缓冲区还给系统。

10. 某高校计算机系开设网络课，安排了上机实习。假设机房共有2m台机器，有2n名学生选该课，规定：（1）每两个学生为一组，各占一台机器，协同完成上机实习；（2）只有一组两个学生都到齐，并且此时机房有空闲机器时，该组学生才能进入机房；（3）上机实习由一名教师检查，检查完毕，一组学生同时离开机房。试用P，V操作模拟上机实习过程。

  • 互斥与同步规则：
    • 检查是否可进：只有凑够两个学生，并且此时机房有空闲机器时，才能将计算机分配给学生，允许该组学生进入机房
    • 学生实验：只有学生被分配完电脑后，才能进入机房上机操作，老师检查完毕后，才能离开
    • 老师检查：只有老师检查完学生的实习，才准学生离开
  • 设置信号量:
    • student为是否有学生，初值为0
    • enter为是否凑够两个学生，初值为0
    • computer为剩余电脑个数，初值为2m
    • finish为是否有学生完成实验，初值为0
    • test为老师是否在检查学生，初值为0
//是否能进入实验室进程
do {
	P(student); //等待第一个学生到达
	P(student); //等待第二个学生到达，此时两个学生student阻塞
	P(computer); //看看是否有空闲电脑
	P(computer); //看看是否有空闲电脑
	学生进入实验室
	V(enter); //学生一可进标志
	V(enter); //学生二可进标志
}while(true);

//学生实验进程
do {
	V(student); //学生进入，通知enter进程
	P(enter);   //是否可以进入
	开始实验
	V(finish); //实习结束，通知老师检查
	P(test);   //等待老师检查
    V(computer)//释放电脑资源
}while(true);

//老师检查进程
do {
	P(finish); //是否有学生实验完毕
    P(finish); //第二个学生完成
	检查实验
	V(test);  //检查完成
	V(test);  //检查完成
}while(true);

11. 把一个长度为ｎ的有界缓冲区（n>0)与一群生产者进程Ｐ1，Ｐ2，…，Ｐm和一群消费者进程Ｃ1，Ｃ2，…，Ｃk联系起来，如图：

各生产者进程使用的过程deposit(data) 各消费者使用过程remove(data)可描述如下： 生产者和消费者之间满足如下条件： (1) 消费者想接收数据时，有界缓冲区中至少有一个单元是满的； (2) 生产者想发送数据时，有界缓冲区中至少有一个单元是空的。 (3) 有界缓冲区是临界资源，因此，生产者进程和消费者进程之间必须互斥执行

  • 设置信号量
    • empty表示有界缓冲区空的个数
    • full表示有界缓冲区满的个数
    • mutex为互斥信号量，表示生产者和消费者必须互斥执行
//生产者进程
do {
    while(P1,P2,...Pm中还有要生产的) {
        P(empty);
        P(mutex);
        deposit(data);
        V(mutex);
        V(full);
    }
}while(true);

//消费者进程
do{
	while(C1,C2,...,Ck中还有要消费的) {
		P(full);
        P(mutex);
        remove(data);
        V(mutex);
        V(empty);
    }
}while(true);

12. 某工厂有两个生产车间，两个生产车间分别生产A,B两种零件，装配车间的任务是把A,B两种零件组装成产品。两个生产车间每生产一个零件后都要分别把它们送到装配车间的货架F1，F2上，F1存放零件A，F2存放零件B，F1和F2的容量均为可存放10个零件，装配工人每次从货架上取一个零件A和一个零件B，然后组装成产品，请用P，V操作进行正确的管理。

  • 设置信号量：
    • emptyA表示货架F1上空的单元数，初值为10，fullA表示货架F1上满的单元数，初值为0，因为生产A零件和取下A零件必须互斥执行，所以设置mutexA为互斥信号量，初值为1
    • emptyB表示货架F2上空的单元数，初值为10，fullB表示货架F2上慢的单元数，初值为0，因为生产B零件和取下B零件必须互斥执行，所以设置mutexB为互斥信号量，初值为1
//A生产车间生产：
do {
	P(emptyA);
 	P(mutexA);
  	生产零件A并放到F1上
  	V(mutexA);
  	V(fullA);
}while(true);

//B生产车间生产：
do {
  	P(emptyB);
  	P(mutexB);
  	生产B零件并放到F2上
  	V(mutexB);
  	V(fullB);
}while(true);

//从货架上取下数据，并进行组装
do {
  	P(fullA);
  	P(mutexA);
  	从F1货架上取下数据
  	V(mutexA);
  	V(emptyA);
  	
  	P(fullB);
  	P(mutexB);
  	从F1货架上取下数据
  	V(mutexB);
  	V(emptyB);
  	
  	组装操作 	
}while(true);

13.什么是线程？它与进程有什么关系？实现线程主要有哪两种方式？各有何优缺点？

  • 线程是进程的进一步划分，是cpu独立运行和独立调度的最小单位。
  • 一个线程可以创建和撤销另一个线程，同一个进程中的多个线程可以并发执行，且可以共享数据。
  • 在Java中，实现线程可以通过继承Thread类和实现Runnable接口。
  • 继承Thread类优点：实现简单；缺点：该类无法集成别的类。
  • 实现Runnable接口优点：继承其他类， 同一实现该接口的实例可以共享资源；缺点：代码复杂。

14.什么是管程？它由哪些部分组成？有什么基本特性？

  • 管程是一种高级同步工具，高级程序设计语言中使用抽象数据类型的思想，将其进行封装。
  • 管程类型提供一组由程序员定义的、在管程内互斥的操作，管程类型也包括一组变量，用于定义这一类型的实例状态，也包括操作这些变量的函数实现。
  • 基本特性：
    • 局部于管程的数据只能被局部于管程内的过程所访问
    • 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
    • 每次仅允许一个进程在管程内执行某个内部过程。

处理机调度

1. 处理机调度的主要目的是什么？处理机调度一般分为哪三级？各自作用是什么？

处理机调度的主要目的是根据不同的系统，提供不同的处理机管理策略，以提高资源的利用率和整个系统的效率

  • 短期调度：在内存作业中选择就绪执行的作业，并为他们分配CPU
  • 中期调度：作为一种中等程度的调度程序，尤其被用于分时系统，将部分运行程序移出内存，之后，从中断处继续执行
  • 长期调度：确定哪些作业调入内存以执行

2.在确定调度方式和调度算法时，常用的评价指标有哪些？

cpu利用率，吞吐量，周转时间，就绪等待时间和响应时间。

3.解释一下术语：中断、中断源、中断请求、中断向量

  • 中断：指CPU对系统发生的某个时间作出一系列反应，CPU暂停正在执行的程序，保留现场后自动执行相应的处理程序，处理完该事件后，如被中断进程的优先级最高，则返回断点继续执行被“打断”的程序。
  • 中断源：引起中断的事件或发出中断请求的来源
  • 中断请求：中断源向CPU提出进行处理的请求
  • 中断向量：中断向量表的表项，通常包括相应中断处理程序入口地址和中断处理时处理机状态字PSW。

4.中断响应主要做哪些工作？由谁来完成？中断处理的主要步骤是什么？

  • 主要做的工作：
    • 停止当前程序的执行
    • 保存源程序的断点信息
    • 转到响应的处理程序
  • 硬件来完成
  • 保存被中断程序的现场，分析中断原因，转入相应处理程序进行处理，中断返回。。

5.下表给出作业1，2，3到达时间和运行时间。采用短作业优先调度算法和先来先服务调度算法，试问平均周转时间各位多少？是否还有更好的调度策略存在？

作业号到达时间运行时间
10.08.0
20.44.0
31.01.0

结束时间：进程结束运行的时间，周转时间：进程总共完成的时间
带权周转时间 = 周转时间/运行时间
相应比R = 周转时间/运行时间 = (等待时间+运行时间) / 运行时间 = 1 + 等待/运行

先来先服务：

作业号到达时间运行时间结束时间周转时间平均周转时间
10.08.08810.53
20.44.01211.6
31.01.01312

FIFS：平均周转时间：(8 + 11.6 + 12) / 3 = 10.53s

短作业优先：

作业号到达时间运行时间结束时间周转时间平均周转时间
10.08.0889.53
20.44.01312.6
31.01.098

SJF：平均周转时间：(8 + 12.6 + 8) / 3 = 9.53s

更优的选择：

作业号到达时间运行时间结束时间周转时间平均周转时间
10.08.013.213.26.46
20.44.05.65.2
31.01.021

SRTN：平均周转时间：(13.2 + 5.2 + 1) / 3 = 6.46

6.假设有四个作业，它们提交、运行时间如下表所示。若采用响应比高者优先调度算法，试问平均周转时间和带权周转时间为多少？

作业号到达时间运行时间
18.02.0
28.30.5
38.50.1
49.00.4

响应比=作业响应时间/运行时间的估计值=1+作业等待时间/运行时间的估计值 在8:00时，由于只有作业1到达，系统将作业1投入运行。作业1运行2小时，10:00完成。作业1完成后，剩余3个作业的响应比为：

r2=1+(10.0-8.3)/0.5=4.4; r3=1+(10.0-8.5)/0.1=16 r4=1+(10.0-9.0)/0.4=3.5 r3最大，所以让作业3运行。作业3运行0.1小时在10:10完成，此时作业2、作业4的响应比为： r2=1+(10.1-8.3)/0.5=4.6 r4=1+(10.1-9.0)/0.4=3.75 r2最大，所以让作业2运行。 所以，四个作业的调度次序为：作业1，作业3，作业2，作业4。 平均周转时间：T=(2.0+2.3+1.6+2.0)/4=1.975 平均带权周转时间：W=(1+4.6+16+5) /4=6.65

7、在单CPU和两台输入输出设备（I1，I2）的多道程序设计环境下同时投入三个作业job1，job2，job3运行。这三个作业对CPU和输入输出设备的使用顺序和时间如下所示：

job1：I2(30ms)；CPU(10ms)；I1(30ms)；CPU(10ms)；I2(20ms)

job2：I1(20ms)；CPU(20ms)；I2(40ms)

job3： CPU(30ms)；I1(20ms)；CPU(10ms)；I1(10ms)

假定CPU，I1，I2都能并行工作，job1优先级最高，job2次之，job3最低，优先级高的作业可以抢占优先级低的作业的CPU，但不能抢占I1和I2。试求：

1） 三个作业从投入到完成分别需要的时间

job1执行完需要：

2） 从投入到完成的CPU利用率

3） I/O设备利用率

内存管理

1. 解释下列概念：物理地址，逻辑地址，逻辑地址空间，内存空间，重定位，静态重定位，动态重定位，碎片，紧缩。

  • 物理地址：内存中各种物理存储单元的地址是从统一的基地址开始顺序编址的，这种地址称为物理地址
  • 逻辑地址：用户程序经过编译之后的每个目标模块都以0为基地址顺序编址，这种地址称为逻辑地址
  • 逻辑地址空间：由程序中逻辑地址组成的地址范围叫做逻辑地址空间
  • 内存空间：由内存中一系列存储单元所限定的地址范围称为内存空间
  • 重定位：程序和数据装入内存时，需要对目标程序中的地址进行修改，这种把逻辑地址转变为内存物理地址的过程称作重定位。
  • 静态重定位：在目标程序装入内存时，由装入程序对目标程序中的指令和数据的地址进行修改，即把程序的逻辑地址都改为实际的内存地址
  • 碎片：内存中容量太小，无法被利用的小分区
  • 紧缩：为了解决碎片问题，移动某些已分配区的内容，使所有进程的分区紧挨在一起，而把空闲区留在另一端。这种技术称为紧缩

2. 解释固定分区发和动态分区法的基本原理

  • 固定分区：内存中分区的个数固定不变，各个分区的大小也固定不变，但不同分区的大小可以不同，每个分区只可装入一道作业。
  • 动态分区：各个分区是在相应作业要进入内存时才建立的，使其恰好适应作业的大小。

3.说明内部碎片和外部碎片的不同

  • 外碎片指的是还没有被分配出去但由于太小而无法分配给申请内存空间的新进程的内存空闲区域
  • 内碎片是出于区域内部或页面内部的存储块，占有这些区域或页面的进程并不使用这个存储块，而在进程占有这块存储时，系统无法利用它，直到进程释放它，或进程结束时，系统才能利用这个进程块。

4.什么是虚拟存储器？它有哪些特征？

  • 虚拟存储器是指具有调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。
  • 特征：多次性，对换性，虚拟性

5. 什么是分页？什么是分段？两者的基本原理和主要区别？

  • 分页就是将一个进程空间划分成许多页面，每个页面大小相同
  • 分段将进程空间划分成许多段，每一段内部的数据或代码关联性比较强，段的大小并不相同
  • 主要区别：
    • 分页的作业地址空间是一维的，分段是二维的
    • 页是信息的物理单位，段是信息的逻辑单位
    • 分页是出于系统管理的需要，分段是为了满足用户的需要
    • 页的大小固定且由系统决定，一个系统内只可能有一种页面大小，段的长度不固定，段含有一组意义相对完整的信息，段的长度取决于信息组的长度。

6. 在分页系统中页面大小由谁决定？页表的作用是什么？在分段系统中段大小由谁决定？段表的作用是什么？它们分别如何将逻辑地址转换为物理地址？

在分页系统中页面大小由硬件决定。页表的作用是实现从页号到物理块号的地址映射。逻辑地址转换成物理地址的过程是：用页号p去检索页表，从页表中得到该页的物理块号，把它装人物理地址寄存器中。同时，将页内地址直接送人物理地址寄存器的块内地址字段中。这样，物理地址寄存器中的内容就是由二者拼接成的实际访问内存的地址，从而完成了从逻辑地址到物理地址的转换。

7. 某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB，假定某时刻一个用户页表中已调入内存的页面号和物理块号如表所示，则逻辑地址0A5CH所对应的物理地址为（ ）

页面号物理块号
05
110
24
37

页式存储管理的逻辑地址分为两部分：页号和页内地址。由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为 1KB”，1K=210，可知页内地址占10位。由“内存为 16KB”，可知有16块，块号为4位。逻辑地址0A5C (H)所对应的二进制表示形式是：000 1010 0101 1100，根据上面的分析，下划线部分为页内地址，编码“000 10”为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是4，即物理块地址为：0100，拼接块内地址1001011100，得 0100 1001011100，即125C(H)。

8.已知段表如下所示，下列逻辑地址的物理地址是什么？

段号基址长度合法0/非法1
02196000
12300140
2901001
313275800
41952960

0, 430 -> 转换为物理地址：219 + 430 = 649

1, 10 -> 转换为物理地址：2300 + 10 = 2310

1, 11 -> 转换为物理地址：2300 + 11 = 2311

2, 50 -> 非法，不能转换为物理地址

3, 400 ->转换为物理地址：1327 + 400 = 1727

4, 112 -> 超出范围，不能转换为物理地址

9.考虑下述页面走向：

1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6 当内存块数分别为3和5时，试问LRU,FIFO,OPT三种置换算法的缺页次数各是多少？（所有内存块初始都为空）

FIFO12342156212376321236
16次1114446663332226
222111222777111
33355511166633
缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺
FIFO12342156212376321236
10次1111166666
222221111
33333222
4444433
555557
缺缺缺缺缺缺缺缺缺缺
LRU12342156212376321236
15次111445551177222
22222666333333
3311122226616
缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺
LRU12342156212376321236
8次11111111
2222222
333666
44433
5557
缺缺缺缺缺缺缺缺
OPT12342156212376321236
11次11111133336
2222227222
345666611
缺缺缺缺缺缺缺缺缺缺缺
OPT12342156212376321236
7次1111111
222222
33333
4466
557
缺缺缺缺缺缺缺

10.什么是驻留集？什么是工作集？它们的作用分别是什么？

驻留集是进程当前分配到物理页框中的所有页构成的集合，它受操作系统的页分配策略和内存可用状态的影响。工作集是研究进程执行过程中访问页的规律的理论模型中的一个概念，是指进程在其过去的t个虚拟执行时间中访问的页的集合。程序局部性表现为在t>t0后，进程的工作集有一段相对长时间的稳定。工作集与进程的由程序逻辑和输入条件决定，与操作系统的分配策略和内存状态无关。在虚拟分页管理中，工作集的变化规律客观上影响驻留集，为了提高内存管理效率，理想的页替换算法是总能选择不属于工作集的页替换出去，实际操作系统中，通过缺页率来调整进程的内存分配配额量。。

文件系统

1.解释以下术语：文件、文件系统、目录项、目录文件、路径、当前目录

  • 文件：被命名的相关信息的集合体，通常放在外存上，嗯可以作为一个独立单位存放和实施相应的操作
  • 文件系统：是操作系统中负责操纵和管理文件的一套机制，它实现文件的共享和保护，方便用户按名存取
  • 目录项：为了加快对文件的检索，往往把文件控制块集中在一起进行管理，这种文件控制块的有序集合就被称为文件目录
  • 目录文件：全由目录项构成的文件就称为目录文件
  • 路径：在树形目录结构中，从根出发，经由所需子目录、到达指定文件的通路
  • 当前目录：为节省文件检索的时间，每个用户可以指定一个目录作为当前的工作目录，以后访问文件时，就从这个目录开始向下顺次检索。这个目录就被称为当前目录。

2.一般来说，文件系统应具备哪些功能？文件系统的层次结构是怎样的？

  • 一般说来，文件系统应具备以下功能：文件管理；目录管理；文件存储空间的管理；文件的共享和保护；提供方便的接口。
  • 文件系统的结构层次： 用户/应用程序--->文件目录系统--->存取控制模块--->逻辑文件系统与文件信息缓冲区--->物理文件系统。 物理文件系统<--->辅助分配模块。 物理文件系统<--->设备管理模块<--->设备。

3.什么是文件的逻辑组织和物理组织？通常，文件的逻辑结构有几种组织形式？

  • 文件的逻辑组织：用户对文件的观察和使用是从自身处理文件数据时所采用的组织方式来看待文件组织形式。这种从用户观点出发所见到的文件组织形式称为文件的逻辑组织
  • 文件的物理组织：文件存储设备上的存储组织形式称为文件的物理组织。
  • 文件的逻辑结构有以下形式：有结构文件和无结构文件和树形文件

4.文件的物理组织形式主要有哪几种？各有什么缺点？

  • 连续文件
    • 优点：顺序存储速度快
    • 缺点：创建文件时就确定它的长度很难实现，不便于文件的动态扩充，可能出现外部碎片从而造成浪费
  • 链接文件
    • 优点：克服了连续文件的缺点
    • 缺点：一般仅适用于顺序访问，而不利于对文件的随机存取；每个物理块上增加一个连接字，为信息管理增加一些麻烦
  • 索引文件：
    • 优点：除了具备链接文件的优点外，还克服了其缺点
    • 缺点：需要增加索引带来空间开销，往往以内存空间为代价换来存取速度的改善
  • 多重索引文件：
    • 优点：除具有一般索引文件的优点外，还可满足对灵活性和节省内存的要求
    • 缺点：间接索引需要多次访盘而影响速度。

5.文件系统中目录结构主要有哪几种？分别说明各自的实现思想？各有什么优缺点？

  • 单级目录结构：在这种组织方式下，全部文件都登记在同一目录中
  • 二级目录结构：在主文件目录中登载了各个用户的名称，每个用户有自己的用户文件目录
  • 属性目录结构：在这种结构中，只有一个根目录，每一级目录可以是下一级目录的说明，也可以是包含文件的说明。从根开始一层一层地扩展下去，就形成了一个树形层次结构。
  • 非循环图目录结构：树形目录结构的自然推广就是非循环图目录结构，它允许一个文件或目录可在多个父目录中占有项目，但并不构成环路。

6.什么是文件控制块？与文件有何关系？

  • 文件控制块：用于控制和管理文件的数据结构，其中包括文件名、文件类型、位置、大小等信息。
  • 文件控制块与文件一一对应，即在文件系统内部，给每个文件唯一地设置一个文件控制块，核心利用这种结构对文件实施各种管理。

7.在UNIX中，每个i节点中有10个直接地址和一、二、三级间接索引。若每个盘块512B，每个盘块地址4B，则一个1MB的文件分别占用多少间接盘块？25MB的文件呢？

10个直接盘块存放的容量为：512B * 10 / 1024 = 5KB

一次间接索引盘块存放容量为：512B * 128 / 1024 = 64KB

二次间接索引盘块存放的容量为：512B * 128 * 128 / 1024 = 8192KB

三次间接索引盘块存放的容量为：512B * 128 * 128 * 128 / 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个三次间接盘块。