东南大学 操作系统试卷

根据给定的文件信息，以下是对“东南大学操作系统试卷”中的关键知识点进行的详细解析。 ### 一、解释以下术语（30分） #### 1. SPOOLING SPOOLING（Simultaneous Peripheral Operations On-Line）技术是一种虚拟设备技术，它通过将独占设备改造为共享设备的方式提高设备利用率和系统效率。SPOOLING技术的核心思想是在输入或输出过程中，通过预先读取或延后写入数据来实现设备的高效利用。在输入过程中，数据首先被存储到磁盘上的缓冲区中，然后由后台进程统一处理；而在输出过程中，则是先将数据存放到磁盘上等待输出的队列中，再由专门的输出进程统一输出。 #### 2. System Call 系统调用是应用程序向操作系统请求服务的一种手段，是用户程序与操作系统之间交互的主要方式之一。系统调用通常包括但不限于：创建和管理进程、文件操作、内存分配等。当应用程序需要操作系统提供的服务时，会通过系统调用来触发内核执行相应的操作，并返回结果给用户程序。系统调用是操作系统提供给编程人员的一个接口，它是用户空间和内核空间交互的重要桥梁。 #### 3. Multi-programming 多道程序设计（Multi-programming）是指在计算机系统中同时运行多个程序的技术。这种技术可以显著提高CPU和外部设备的利用率，从而提高整个系统的吞吐量。多道程序设计的关键在于合理地安排和调度这些并发执行的程序，以避免资源竞争和死锁等问题。现代操作系统普遍采用多道程序设计的思想，通过进程管理和调度算法来实现多任务环境下的高效运行。 #### 4. Process Deadlock 进程死锁是指两个或两个以上的进程在执行过程中因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下一步。通常情况下，死锁的发生需要满足四个必要条件：互斥条件、请求与保持条件、不剥夺条件和循环等待条件。解决死锁的方法主要包括预防、避免、检测和恢复四种策略。其中，预防是最常见的方法，通过限制进程的行为来避免死锁发生的可能性。 ### 二、问答题（25分） #### 1. 为什么在读取（或写入）文件之前需要使用打开文件命令？ 在操作系统中，文件操作包括读取和写入等基本操作。为了确保文件操作的安全性和一致性，在进行读取或写入操作之前，必须先通过打开文件命令获取对该文件的访问权限。打开文件的操作主要是为了实现以下几个目的： - **获取文件句柄**：操作系统为每个打开的文件分配一个唯一的标识符（文件句柄），后续的读写操作均通过该句柄来进行。 - **检查文件权限**：确保用户拥有对文件的访问权限，防止未经授权的访问行为。 - **记录文件状态**：操作系统记录文件当前的状态，如位置指针等信息，以便于进行正确的读写操作。 - **确保文件完整性**：防止多个进程同时修改同一个文件而导致的数据损坏问题。 #### 2. 设备驱动程序向内核I/O子系统提供了哪些类型的接口命令？ 设备驱动程序作为硬件和操作系统之间的桥梁，负责实现对物理设备的具体操作。为了与内核I/O子系统交互，设备驱动程序通常提供了以下几种类型的接口命令： - **读写操作**：用于控制设备进行数据的读取和写入。 - **初始化操作**：在设备启动时进行初始化配置。 - **中断处理**：当设备完成某个操作或出现错误时，会通过中断通知内核。 - **设备控制**：如设置设备参数、查询设备状态等。 - **错误处理**：当设备发生故障时，能够及时报告错误信息并采取相应措施。 ### 三、计算题（18分） 考虑以下页面引用串：1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6。假设只有三个页面框，对于以下三种替换算法，各会发生多少次页面故障？假设所有页面框最初都是空的。 #### 1. LRU 替换算法 LRU（Least Recently Used）替换算法是一种基于页面最近被访问的时间顺序来进行替换的策略。当页面框满时，选择最久未被访问的页面进行替换。对于给定的页面引用串： - 初始状态下，依次装入1、2、3，共发生3次页面故障； - 第4次引用4时，因为页面框已满，需要根据LRU原则替换掉最久未使用的页面，即1，发生第4次页面故障； - 后续依次装入2、1、5、6，每次都会发生页面故障，共增加5次故障； - 接下来的引用序列2、1、2、3、7、6、3、2、1、2、3、6中，依据LRU规则，分别发生4次、0次、0次、1次、0次、1次、1次、0次、0次、0次、0次、1次页面故障。 - 总计：3 + 1 + 5 + 4 + 1 + 1 + 1 + 1 = 18次页面故障。 #### 2. FIFO 替换算法 FIFO（First In First Out）替换算法按照页面进入页面框的先后顺序进行替换。当页面框满时，选择最早进入的页面进行替换。对于给定的页面引用串： - 初始状态下，依次装入1、2、3，共发生3次页面故障； - 第4次引用4时，因为页面框已满，根据FIFO原则替换掉最早进入的页面1，发生第4次页面故障； - 后续依次装入2、1、5、6，每次都会发生页面故障，共增加5次故障； - 接下来的引用序列2、1、2、3、7、6、3、2、1、2、3、6中，依据FIFO规则，分别发生2次、0次、0次、1次、1次、1次、1次、0次、0次、0次、0次、1次页面故障。 - 总计：3 + 1 + 5 + 2 + 1 + 1 + 1 + 1 + 1 = 16次页面故障。 #### 3. 最佳替换算法 最佳替换算法是一种理想化的替换策略，它总是选择未来不会被引用或者距离下次被引用时间最长的页面进行替换。对于给定的页面引用串： - 初始状态下，依次装入1、2、3，共发生3次页面故障； - 第4次引用4时，因为页面框已满，根据最佳替换原则替换掉未来最晚被引用的页面3，发生第4次页面故障； - 后续依次装入2、1、5、6，每次都会发生页面故障，共增加5次故障； - 接下来的引用序列2、1、2、3、7、6、3、2、1、2、3、6中，依据最佳替换规则，分别发生2次、0次、0次、0次、1次、1次、0次、0次、0次、0次、0次、0次页面故障。 - 总计：3 + 1 + 5 + 2 + 1 + 1 + 0 = 13次页面故障。 ### 四、编程题（27分） 针对第一个读者-写者问题的解决方案未能防止等待的写者被饥饿的情况：如果数据库当前正在被读取并且存在等待的写者，后续的读者仍然会被允许读取数据库，导致写者无法完成写操作。请提出一种改进方案，使得等待的写者不会被饥饿，并编写一段Java代码来实现该方案。 #### 改进方案 为了避免等待的写者被饥饿，我们可以采用以下改进方案： 1. **优先级反转机制**：当有写者请求访问数据库时，即使当前有读者在读取数据库，也应立即阻止新的读者进入，以确保写者可以尽快完成写操作。 2. **读者等待机制**：一旦有写者请求访问数据库，所有的读者都必须等待，直到写者完成写操作。这样可以确保写者不会被饥饿。 3. **公平性保障**：在读者等待期间，如果有新的写者请求访问数据库，应该按照先进先出的原则处理请求，以避免写者之间的不公平竞争。 #### Java代码实现 ```java import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReentrantLock; public class ReaderWriterSolution { private final Lock lock = new ReentrantLock(); private int readersCount = 0; private boolean hasWriters = false; public void startRead() throws InterruptedException { lock.lock(); try { while (hasWriters) { // 如果有写者等待，读者需要等待 lock.unlock(); Thread.sleep(10); // 避免忙等 lock.lock(); } readersCount++; } finally { lock.unlock(); } } public void endRead() { lock.lock(); try { readersCount--; if (readersCount == 0) { hasWriters = true; // 没有读者了，允许写者操作 } } finally { lock.unlock(); } } public void startWrite() throws InterruptedException { lock.lock(); try { hasWriters = true; while (readersCount > 0) { // 等待所有读者完成读操作 lock.unlock(); Thread.sleep(10); // 避免忙等 lock.lock(); } } finally { lock.unlock(); } } public void endWrite() { lock.lock(); try { hasWriters = false; } finally { lock.unlock(); } } } ``` 以上代码实现了改进后的读者-写者问题解决方案，通过使用`ReentrantLock`类来管理互斥访问，并通过计数器和标志位来控制读者和写者的访问顺序，确保写者不会被饥饿。