操作系统基础知识

引论

操作系统基础概念

1. 操作系统基本特性

   • 并发
   • 异步：进程以不可预知的速度向前推进，第一个进入系统的程序并不是第一个完成的
   • 共享：系统中的资源可以被内存中并发执行的多个进程共享
   • 虚拟
     • 时分复用：
     • 空分复用：利用存储器的空闲空间分区域存放和运行多道程序

2. 并行与并发的区别

• 并发是指一个处理器同时处理多个任务。并行是指多个处理器或者是多核的处理器同时处理多个不同的任务。并发是逻辑上的同时发生（simultaneous），而并行是物理上的同时发生。来个比喻：并发是一个人同时吃三个馒头，而并行是三个人同时吃三个馒头。

• 并发性是指两个或者多个事件在同一时刻发生。而并行性是指两个或者多个事件在同一时间间隔内发生。并发指在同一时刻只能有一条指令执行，但多个进程指令被快速的轮换执行，使得在宏观上具有多个进程同时执行的效果，但在微观上并不是同时执行的，只是把时间分成若干段，使多个进程快速交替的执行。

• 当有多个线程在操作时，如果系统只有一个CPU，则它根本不可能真正同时进行一个以上的线程，它只能把CPU运行时间划分成若干个时间段，再将时间段分配给各个线程执行，在一个时间段的线程代码运行时，其它线程处于挂起状态。这种方式我们称之为并发（Concurrent）。当系统有一个以上CPU时，则线程的操作有可能非并发**。当一个CPU执行一个线程时，另一个CPU可以执行另一个线程，两个线程互不抢占CPU资源，可以同时进行，这种方式我们称之为并行（Parallel）。**

3. 什么是操作系统及操作系统的功能。

4. 操作系统是管理计算机硬件与软件资源的程序，是计算机的基石。

5. 操作系统本质上是一个运行在计算机上的软件程序，用于管理计算机硬件和软件资源。

6. 操作系统的存在屏蔽了硬件层的复杂性。

7. ==操作系统的内核是操作系统的核心部分，它负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。==

内核

1. 操作系统内核及其作用

   • **内核，是操作系统的基础模块，用于管理系统资源。**例如提供对软件层面的抽象（例如对进程、文件系统、同步、内存、网络协议等对象的操作和权限控制），和对硬件访问的抽象（例如磁盘，显示，网络接口卡（NIC））；操作系统，在内核的基础上有延伸，包括了提供基础服务的系统组件。
   • 提供CPU时间片管理、中断、内存管理、IO管理等等。
   • 内核程序一直占据内存中的一段内存，这样处理器可以随时调用这些内核程序；
   • 在系统中，运行的应用程序通过***系统调用***来与***内核***通信。

2. 操作系统内核的功能

• OS内核：紧靠着硬件的软件层次，常驻内存

  • 与硬件紧密相关的模块如中断处理程序
  • 常用设备的驱动程序
  • 运行频率较快的模块：时钟管理，进程调度

• 为了防止OS本身及其关键数据如PCB等遭到应用程序的恶意或无意破坏，将处理机的执行状态分为系统态和用户态。

  • 管态：较高特权，能够执行一切指令，访问所有寄存器和存储区。
  • 目态：仅能执行规定的指令，访问指定的寄存器和存储区。

• 支撑功能

  • 中断处理：
  • 时钟管理
  • 原语操作：原子操作，在执行过程中不允许被中断。

• 资源管理功能

  • 进程管理：进程同步原语，进程通信原语
  • 存储器管理：地址转换机构，内存分配与回收，对换功能。
  • 设备管理：缓冲管理，驱动程序，设备独立性功能的软件。

系统调用

用户态：用户态运行的进程或可以直接读取用户程序的数据。

系统态：可以简单地理解系统态运行的进程或程序几乎可以访问计算机的任何资源，不受限制。

==我们运行的程序基本上都是运行在用户态，如果我们调用操作系统提供的系统态级别的子功能，需要使用到系统调用。==

也就是说在我们运行的用户程序中，凡是与系统态级别的资源有关的操作==（文件管理，进程控制，内存管理等）==，都必须通过系统调用的方式向操作系统提出服务请求，并由操作系统代为完成。

系统调用按照功能分类：

• 设备管理：完成设备的请求或者释放，以及设备的启动等功能。

• 文件管理：完成文件的读，写，创建及删除等功能。

• 进程控制：完成进程的创建，撤销，阻塞或者唤醒等功能。

• 进程通信：完成进程之间的消息传递或者信号传递等功能。

• 内存管理：完成内存的分配，回收以及获取作业占用内存区大小及地址等功能。

Linux 的系统调用主要有以下这些：

Task	Commands
进程控制	fork(); exit(); wait();
进程通信	pipe(); shmget(); mmap();
文件操作	open(); read(); write();
设备操作	ioctl(); read(); write();
信息维护	getpid(); alarm(); sleep();
安全	chmod(); umask(); chown();

进程

程序并发和前趋图

程序并发执行的特征：

• 间断性：并发执行的程序如果存在相互制约的关系，将会导致并发程序具有执行-暂停-执行这种间断性的活动规律。

• 失去封闭性：系统中的资源共享，

• 不可再现性：失去封闭性导致了不可再现性。

进程的描述

进程

• 进程是进程实体的运行过程。
• 进程是程序的一次执行
• 特征
  • 动态性，并发性，独立性，异步性，具有PCB结构

进程有哪几种状态？

• 就绪状态：进程已获得除处理机（CPU）以外的所需资源，等待分配处理机资源
• 运行状态：占用处理机资源运行，处于此状态的进程数小于等于CPU数
• 阻塞状态： 进程等待某种条件，在条件满足之前无法执行-----I/O请求，申请缓冲区失败，

进程控制块（PCB）的信息

• 进程标识符
• 处理机状态
• 进程调度信息：进程状态，进程优先级，事件即阻塞原因
• 进程控制信息：程序和数据的地址，进程同步和通信机制，资源清单，链接指针：本进程所在队列的下一个进程PCB的首地址

PCB的作用

• 作为独立运行基本单位的标志
• 能够实现间断性运行方式：当进程因为阻塞而暂停运行，系统可以讲CPU现场信息保存在被中断进程的PCB中，可以供该进程再次被调度执行时恢复CPU现场时使用。
• 提供进程管理所需要的信息：
• 提供进程调度所需要的信息：只有处于就绪状态的进程才能够被调度执行，而且在PCB中就提供了进程处于何种状态的信息。
• 实现与其他进程的同步与通信：同步信号量，进程通信区域和通信队列指针。

进程控制块的组织形式

• 线性方式：
• 链接方式：相同状态进程的PCB分别通过PCB中的链接指针链接为一个队列，如就绪队列，阻塞队列，空白队列。
• 索引方式：就绪索引表，阻塞索引表

进程控制

1. 进程的创建过程及原语

   • Creat原语，fork()函数
   • 申请空白PCB
   • 为新进程分配其运行需要的资源：从操作系统或者仅从父进程获得。内存，I/O设备，文件，CPU时间。
   • 初始化进程控制块PCB：标识信息，状态机信息，控制信息
   • 将新进程插入到就绪队列中

2. 引起进程创建的事件

   • 用户登录
   • 作业调度：当作业被调度并且装入内存时，为作业创建进程，并且插入到就绪队列中。
   • 提供服务：创建进程提供用户需要的服务。
   • 应用请求：以上情况，都是系统内核为用户创建一个新进程。这类是由用户自己创建新进程。并发完成特定任务。

3. 进程的终止过程（Holt指令）

   • 根据被终止进程的标识符，从PCB集合中检索该进程的PCB，从中读出该进程的状态。
   • 若被终止的进程处于执行状态，应该立即终止该进程的执行，并且置调度标志为真，用于指示该进程可被再次立即调度。
   • 若该进程还有子孙进程，还应该将所有的子孙进程都终止，防止成为不可控的进程。
   • 将被终止进程拥有的全部资源后者归还给父进程 ，或者归还为系统
   • 将被终止进程从所在队列中移除，等待其他程序来搜集信息。

4. 进程阻塞的过程

   • block原语
   • 进程自身的主动行为
   • 如果进程处于执行状态，应该立即停止执行。
   • 将进程控制块中的现行状态由执行改为阻塞，并且将PCB插入阻塞队列。

5. 引起进程阻塞和唤醒的事件

   • 向系统请求共享资源失败
   • 等待某种操作的完成：I/O操作
   • 新数据尚未到达：进程同步约束，进程A用于输入数据，进程B用于对输入数据进行加工。
   • 等待新任务的到达：一些特定的系统进程，每当这种进程完成任务后便将自己阻塞起来，等待新任务的到来。

6. 进程唤醒的过程

   • wakeup原语，被阻塞的进程所期待的事件发生时。
   • 首先进被阻塞的进程从等待该事件的阻塞队列中移出。
   • 将进程PCB中的现行状态由阻塞改为就绪
   • 将该PCB插入到就绪队列中。

进程同步

1. 同步机制遵循的原则

   • 空闲让进
   • 忙则等待：
   • 有限等待：应该保证在有限时间内可以进入自己的临界区，以免进程陷入“死等”的状态。
   • 让权等待：权指CPU。当进程不能进入自己的临界区，应该立即释放处理机，以免陷入“忙等”状态。

2. 进程同步的机制：

• 硬件同步机制：关中断，测试并建立指令---》其他访问进程必须不断进行测试，处于一种忙等的状态，不符合让权等待的原则。

• 信号量机制：一个信号量对应一个临界资源，初始时有资源，所以信号量初始值一般都是1

  • P操作：将sem变量减一，相减后，如果sem<0，则线程/进程进入阻塞等待，否则继续，表明P操作可能会阻塞。

  • V操作，将sem变量+1，相加后，如果sem<=0，则唤醒一个等待中的线程/进程，表明V操作不会阻塞。

当有进程占用临界区时，-1
当信号量 <= 0 代表已有进程占用临界区
m个进程，最多 -(m -1) 代表有m -1个进程在等待临界区资源，即处于等待队列 当信号量 > 0 即 = 1，代表没有进程进入临界区

• 管程机制：有自己名字的特殊模块，由关于共享资源的数据结构和在其上的操作过程组成，进程可调用管程的过程以操作管程中的数据结构；编译器复杂管程的互斥，设置条件变量及等待唤醒操作解决同步问题。每次只有一个进程进入管程，执行这组过程，使用共享资源，达到对共享资源访问的统一管理

  • 管程提出的原因：信号量机制中，每个要访问临界资源的进程必须自备同步操作，这样使得大量的同步操作分散在各个进程中。这会给系统的管理带来麻烦，也会因为同步操作的使用不当而导致系统死锁。

  • 利用共享数据结构抽象地表示系统中的共享资源，并且将对该共享数据结构实施的特定操作定义为一组过程。

3. 信号量的作用

   • 实现进程互斥
   • 实现前驱关系

进程通信

1. 进程通信的途径？管道、信号量、消息队列、共享内存区等等

   消息传递（管道、FIFO、消息队列）

   同步（互斥量、条件变量、读写锁、文件和写记录锁、信号量）

   共享内存（匿名的和具名的）

   远程过程调用（Solaris门和Sun RPC）

   • 信号量
   • 管道：用于连接一个读进程和一个写进程以实现它们之间的通信的一个共享文件。按字符流读写，先进先出，解决互斥同步
   • 消息队列：send原语，陷入内核，操作系统复制到消息缓冲区，并挂接消息到接受进程的消息队列指针；receive原语，操作系统将消息复制到接收进程的地址空间
   • 共享内存区：物理内存中建立一块能够共享的内存空间，将物理内存空间映射到两个进程的地址空间；利用读者/写者问题解决互斥

2. 消息传递系统

   • 直接通信方式：发送进程利用OS提供的发送原语（send），直接将消息发送给目标系统。
   • 间接通信方式：发送和接收进程，都通过共享中间实体（邮箱）的方式进行消息的发送和接收，完成进程间通信。

3. 进程通信的方式

   （1）管道（Pipe）：管道可用于具有亲缘关系进程间的通信，允许一个进程和另一个与它有共同祖先的进程之间进行通信。只支持半双工通信（单向交替传输）；

   （2）命名管道（named pipe）（又叫FIFO）：命名管道克服了管道没有名字的限制，因此，除具有管道所具有的功能外，它还允许无亲缘关系进程间的通信。命名管道在文件系统中有对应的文件名。命名管道通过命令mkfifo或系统调用mkfifo来创建。有名管道严格遵循先进先出(first in first out)。有名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信。

   （3）信号（Signal）：信号是比较复杂的通信方式，用于通知接受进程有某种事件发生，除了用于进程间通信外，进程还可以发送信号给进程本身；linux除了支持Unix早期信号语义函数sigal外，还支持语义符合Posix.1标准的信号函数sigaction（实际上，该函数是基于BSD的，BSD为了实现可靠信号机制，又能够统一对外接口，用sigaction函数重新实现了signal函数）。

   （4）消息（Message）队列：消息队列是消息的链接表，包括Posix消息队列system V消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。

   • 消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；
   • 避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法；
   • 读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。

   （5）共享内存：使得多个进程可以访问同一块内存空间，是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。==同进程可以及时看到对方进程中对共享内存中数据的更新。==往往与其它通信机制，如信号量结合使用，来达到进程间的同步及互斥。

   （6）信号量（semaphore）：主要作为进程间以及同一进程不同线程之间的同步手段。信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。

   （7）套接字（Socket）：更为一般的进程间通信机制，可用于不同机器之间的进程间通信。起初是由Unix系统的BSD分支开发出来的，但现在一般可以移植到其它类Unix系统上：Linux和System V的变种都支持套接字。

   ==（8）管道与消息队列的联系和区别：==管道和消息队列的通信数据都是先进先出的原则。与管道（无名管道：只存在于内存中的文件；命名管道：存在于实际的磁盘介质或者文件系统）不同的是消息队列存放在内核中，只有在内核重启(即，操作系统重启)或者显示地删除一个消息队列时，该消息队列才会被真正的删除。消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取.比 FIFO 更有优势。

线程

线程和进程的区别

请分别简单说一说进程和线程以及它们的区别。

• 进程是具有一定功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源调度和分配的一个独立单位。
• 线程是进程的实体，是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位。
• 一个进程可以有多个线程，多个线程也可以并发执行

线程的实现

线程的实现

• pthread_create：linux下创建线程的函数

• 内核支持级线程

  • 缺点：对于用户线程切换来说，其模式切换的开销较大，在同一个进程中，从一个线程切换到另一个线程时，需要从用户态转到核心态进行。因为用户进程的线程是在用户态运行的，而线程调度和管理是在内核实现的，系统开销大。

• 用户级线程

  • 对于用户级线程的系统，调度仍然是以进程为单位进行的。
  • 对于内核支持线程，调度则是以线程为单位进行的。
  • 缺点：系统调用的阻塞问题：当线程执行一个系统调用时，不仅该线程被阻塞，而且进程内的所有线程都被阻塞。

• 组合方式：

线程间的同步方式

线程同步是两个或多个共享关键资源的线程的并发执行。应该同步线程以避免关键的资源使用冲突。操作系统一般有下面三种线程同步的方式：

1. 互斥量(Mutex)：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。
2. 信号量(Semphares) ：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量
3. 事件(Event) :Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。

处理机调度与死锁

处理机调度的层次

1. 处理机调度的层次

   • 高级调度：作业调度-》分时系统和实时系统没有作业调度。将外存后备队列中的作业调入内存，并且为它们创建进程，分配必要的资源
   • 低级调度：进程调度-》决定就绪队列中的哪个进程获得处理机
   • 中级调度：内存调度-》存储器管理中的对换功能

2. 周转时间和响应时间

   • 周转时间：作业在后备队列等待时间+在就绪队列等待时间+在CPU执行时间+等待I/O操作时间
   • 响应时间：请求信息发出到送到处理机+处理机对请求信息进行处理+响应信息回送终端

作业调度

• FCFS：先来先服务
• SJF：短作业优先
• 缺点：完全忽略作业的等待时间，会出现饥饿现象
• 人机交互无法实现
• PSA：优先级调度
• 基于作业的紧迫程度
• HRRN：高响应比优先级调度算法
• 优先权=等待时间+要求服务时间/要求服务时间。

进程调度

1. 进程调度的任务

   1. 保存处理机的现场信息
   2. 按照某种算法选取进程
   3. 把处理器分配给进程。

2. 进程调度算法

   • RR：轮转调度算法-》就绪队列中的线程每次仅运行一个时间片

     • 时间片较小，意味着频繁地执行进程调度和进程上下文的切换，无疑增加系统的开销。

     • 时间片较大，每个进程都能在一个时间片内完成，无法满足短作业和交互式用户的需求。

     • 时间片大小的确定：略大于一次交互所需要的时间

   • 多级反馈队列

     • 设置多个就绪队列。
     • 每个队列采用FCFS算法：在前一个队列未完成，转入下一个队列的队尾。最后第n个队列中采用RR轮转调度方式运行。
     • 按照队列优先级调度。仅当第一队列空闲时才调度第二队列中的进程运行。

3. 进程的调度算法

• 先到先服务(FCFS)调度算法 : 从就绪队列中选择一个最先进入该队列的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。
• 短作业优先(SJF)的调度算法 : 从就绪队列中选出一个估计运行时间最短的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。
• 时间片轮转调度算法 : 时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称 RR(Round robin)调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。
• 多级反馈队列调度算法 ：前面介绍的几种进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程 。多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。，因而它是目前被公认的一种较好的进程调度算法，UNIX 操作系统采取的便是这种调度算法。
• 优先级调度 ： 为每个流程分配优先级，首先执行具有最高优先级的进程，依此类推。具有相同优先级的进程以 FCFS 方式执行。可以根据内存要求，时间要求或任何其他资源要求来确定优先级。

死锁

1. 定义：在两个或者多个并发进程中，如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗的讲就是两个或多个进程无限期的阻塞、相互等待的一种状态。

2. 引起死锁的原因：

   • 竞争不可抢占性资源
   • 竞争可消耗资源
   • 进程推进顺序不当

3. 死锁产生的四个条件（有一个条件不成立，则不会产生死锁）

   • 互斥条件：一个资源一次只能被一个进程使用
   • 请求与保持条件：一个进程因请求资源而阻塞时，对已获得资源保持不放
   • 不可剥夺条件：进程获得的资源，在未完全使用完之前，不能强行剥夺
   • 循环等待条件：若干进程之间形成一种头尾相接的环形等待资源关系

4. 处理死锁的方法

• 预防死锁：破坏四个条件之一

  • 破坏不可抢占性：进程已经占有的资源被短暂地释放
  • 破坏请求和保持条件：一个进程在请求资源时，不能持有不可抢占性资源。
  • 破坏循环等待条件：对系统的所有资源进行线性排序，并且赋予不同的序号。规定每个进程必须按照序号递增的顺序请求资源。

• 避免死锁：在资源动态分配的过程中，防止系统进入不安全状态。银行家算法

  • 安全序列：按照某种进程推进顺序为每个进程分配其所需要的资源，直至满足每个进程对资源的最大需求，使得每个进程都可以顺利地完成。
  • 可利用资源向量：
  • 最大需求矩阵
  • 分配矩阵：已分配的资源数
  • 需求矩阵
  • 请求向量
  • 工作向量：系统可以提供给进程继续运行所需要的资源数目。初始化为Avaliable向量
  • Finish：系统是否有足够的资源分配给进程

• 检测死锁

  • 保存有关资源的请求和分配信息
  • 提供算法检测是否发生死锁

• 解除死锁

  • 抢占资源：从一个或者多个进程中抢占足够数量的资源，分配给死锁进程，解除死锁状态
  • 终止进程：终止一个或者多个进程，直至打破循环环路，使得系统从死锁状态中解脱出来。

银行家算法

• 银行家算法属于避免死锁的一种方法。
• 其主要思想就是在进行进程的资源分配时判断此次分配后系统是否会进入不安全状态，如果会进入不安全状态则可能发生死锁，否则一定不会产生死锁。
• 对于如何判断系统是否进入不安全状态的核心就是看是否可以找到任意一个安全序列。所谓的安全序列就是依次检查剩余的资源是否能够满足剩余的进程，如果可以满足则继续检查下一个进程，如果所有的进程都能够得到满足则说明找到了一个安全序列，系统也将处于安全状态。
• 在进行安全状态检查时，每次在进行下一个检查时，当前可用资源为回收上一个进程资源的总值。

存储器管理

存储器的层次结构

缓存及其作用

1. 高速缓存

   • **备份主存中常用数据，减少处理机对主存储器访问次数。**进程的程序和数据存放在主存储器中，每当要访问时被临时复制在一个高速缓存中。

   • 大幅度提高程序的执行速度，有利于CPU快速访问。

   • 介于寄存器和存储器之间的存储器，相比于访问主存的速度，访问高速缓存更快。

2. 提高缓存命中率的方法

   • 将缓存用于读多写少的场景，缓存时间越长，命中率越高。

   • **缓存的粒度越小，命中率越高。**即缓存单个对象和缓存一个集合。

   • 缓存的容量。如果容量有限容易引起缓存失败，换入换出。

3. 磁盘缓存

   • 磁盘的I/O速度远远低于对主存的访问速度，为了缓和两者在速度上的不匹配，设置了磁盘缓存。

   • 主要用于暂时存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数。

   • 但是，磁盘缓存与高速缓存不同，其本身并不是一种实际存在的存储器，而是利用主存中的部分存储空间暂时存放从磁盘中读出或者写入的数据

连续分配存储管理方式

1. 为一个用户程序分配一个连续的内存空间，即程序中的代码或数据的逻辑地址相邻，体现在内存空间分配时物理地址相邻。
2. 单一连续分配：单道程序环境下，用户区内存仅有一道用户程序
3. 固定分区分配
4. 动态分区分配
   • 数据结构：空闲分区表或者空闲分区链
   • 分配内存：m.size-u.size<=size
   • 回收内存：四种情况

动态分区分配算法

1. 依次搜索空闲分区链上的空闲分区，去寻找一个某大小可以满足要求的分区。

2. 动态分区分配算法：将程序装入内存中

   • FF：首次适应：空闲分区按地址递增连接
     • 缺点：地址部分被不断划分，会留下许多难以利用的，很小的空闲分区即碎片。
   • NF：循环首次适应：上次找到的下一个空闲分区
   • BF：最佳适应：按容量大小进行链接
     • 也会产生碎片
   • WF：最坏适应：容量大小从大到小

动态可重定位分区分配

1. 紧凑

   • 将原来多个分散的小分区拼接成一个大分区的方法叫做紧凑。
   • 问题：经过紧凑后的用户程序在内存中的位置发生了变化，如果不修改可能无法执行。

2. 动态重定位

   • 重定位寄存器：存放程序或者数据在内存中的起始地址。
   • 程序要执行时，真正要访问的地址是相对地址+重定位中的地址。

对换

1. 把内存中暂时不能运行的进程或者暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，再把已经具备运行条件的进程或进程所需要的程序和数据换入内存。

2. 对换的类型

   • 整体对换：处理机中级调度，即对换是以整个进程为单位的
   • 页面（分段）对换：对换是以进程的一个页面或者分段为单位进行的。目的是为了支持虚拟存储系统。

3. 对换空间管理

   • 磁盘空间分成文件区和对换区两部分。
   • 文件区：主要目标：提高文件存储空间的利用率，然后才是提高对文件的访问速度。
   • 对换区：主要目标：提高进程换入和换出的速度，然后才是提高文件存储空间的利用率

4. 进程换入和换出

   • 时机：当一个进程由于创建多个子进程而需要更多的内存空间，但是没有足够的内存空间时，便调用对换进程实现进程的换入和换出。

分页和分段存储管理方式

1. 分页和分段有什么区别？

   • 段是信息的逻辑单位，它是根据用户的需要划分的，因此段对用户是可见的 ；页是信息的物理单位，是为了管理主存的方便而划分的，对用户是透明的。
   • 段的大小不固定，由它所完成的功能决定；页的大小固定，由系统决定
   • 段向用户提供二维地址空间；页向用户提供的是一维地址空间
   • 段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制。页是信息的物理单位。

2. 分页存储管理方式

   • 逻辑地址：页号+页内地址（位移量）

   • 页表：实现从页号到物理块号的地址映射。通常存放在主存中。

   • 地址变换机构：将用户地址空间的逻辑地址转换为内存空间的物理地址，页表寄存器：页表始址+页表长度

   • 两次访问内存：

   • 快表：联想寄存器，TLB。一次访问内存或者两次访问内存

3. 页面大小的选择：**页面大小一般是2的幂，1KB-8KB

   • 页面太小产生内部碎片，但是会导致页表太长，占用大量内存

   • 页面太大可以减少页表长度，提高页面换入换出速度，但会使内部碎片增大

4. 分段存储器管理

   • 分段的原因

     • 方便编程：
     • 信息共享：可以为该被共享的过程简历一个独立的段，简化了共享的实现。
     • 信息保护：
     • 动态增长：使用过程中，数据段不断增加
     • 动态链接：

   • 段表：段号+段长+基址

   • 作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息

   • 产生外部碎片

   • 更易于实现信息的共享和保护

5. 段页式存储管理

   • 将用户程序分成若干段，将每个段分成若干页，每个段一个段名

虚拟存储器管理

1. 从逻辑上对内存容量进行扩充：程序运行之前无需全部装入内存，而仅需要将当前要运行的少量页面或者段先装入内存便可以运行，其余留在盘上。

   • 多次性：一个作业中的程序和数据无需在作业运行时一次性地全部装入内存，允许被分成多次调入内存运行。
   • 对换性：无需作业在运行时一直常驻内存
   • 虚拟性：

2. 程序的局部性原理

   • 时间局部性：如果某数据被访问过，不久后该数据可能被再次访问
   • 空间局部性：程序在一段时间内所访问的地址可能集中在一定范围内

3. 请求分页存储管理方式

   • 在基本的分页基础上，增加了请求调页功能和页面置换功能

4. 进程正常运行所需要的最小物理块数

5. 内存分配策略：

   • 固定分配局部置换：为进程分配一组固定数目的物理块
   • 可变分配全局置换：
   • 可变分配局部置换：

6. 影响缺页率的因素

   • 页面大小：页面越大，缺页率越低
   • 进程所分配的物理块数
   • 页面置换算法
   • 程序固有属性

7. ==页面置换算法：==

   • 最佳置换算法
   • 先进先出页面置换：产生bleady现象即分配的块数越多，缺页率反而越高。
   • 最近最久未使用（LRU）
   • 最少使用
   • Clock置换算法：设置一个访问位，如果是0，则换出该页，如果是1，则将访问位置0，暂时不换出。
   • 改进型Clock置换算法：访问位和修改位

8. 抖动现象：不适当的置换算法，刚被换出的页面很快又被访问，频繁地更换页面。

9. 抖动的预防措施：

   • 采用局部置换：进程发生缺页时，只能从分配给自己的内存空间进行置换，不会对其他进程产生影响
   • 把工作集融入到处理机调度中：
   • 采用L=S准则调节缺页率：平均缺页时间，置换一个页面所需时间
   • 选择暂停的进程

10. 请求分段存储器管理

磁盘存储器管理

1. 给了一堆磁盘参数，问进行碎片整理后，对一个1M文件的访问速度何如变化

文件系统

1. 文件的逻辑结构
   • 有结构文件：记录式文件：
   • 无结构文件：流式文件：库函数，可执行文件
2. 文件的物理结构（有结构文件）
   • 顺序文件
   • 索引文件
   • 索引顺序文件
3. 文件目录（存放于磁盘中）
   • 实现按名存取
   • 提高对目录的检索速度
   • 文件共享
   • 允许文件重名

输入输出系统

磁盘调度算法

• FCFS：先来先服务
• SSTF：最短寻道时间优先：可能产生饥饿现象，在一个区域内来回移动。
• SCAN（电梯）：到达最边上时改变磁头移动方向
• C-SCAN（总是从0号向内）：磁头单向移动
• N-step-SCAN（每次服务n长子队列）
• FSCAN（两个队列，新请求入另一个队列）
• 旋转调度（旋转延迟）

I/O系统的分层：

• 中断处理程序：直接与硬件交互
• 设备驱动程序：将上层的抽象I/O请求转换为对I/O设备的具体命令和参数，并将其装入到设备控制器中的命令和参数寄存器中。
• 设备独立性软件：提高了I/O系统的可适应性和可扩展性

I/O设备的分类

• 块设备：数据的存取和传输都是以数据块为单位的设备
• 字节设备：以字符为单位
• 独占设备
• 共享设备
• 虚拟设备

I/O控制方式

• 轮询

• 直接存储器访问

  • 数据传输的基本单位是数据块
  • 所传送的数据是从设备直接到内存
  • 仅在传送一个或多个数据块的开始和结束时，才需要CPU的干预。

• 中断

  • 为什么用户处理中断前弹出系统栈并且压入用户栈
  • 屏蔽中断和嵌套中断

• I/O通道：弱鸡版的cpu

  • 把对一个数据块的读或写为单位的干预，减少为对一组数据块及有关的控制和管理为单位的干预。
  • 使一些原来由CPU处理的I/O任务转由通道来承担，从而把CPU从繁杂的I/O任务中解脱出来。
  • CPU只需要向通道发送一条I/O指令，通道在接收到该指令后，便从内存中取出本次要执行的通道程序，然后执行该通道程序，仅当通道完成了规定的I/O任务后，才向CPU发出中断信号。
  • 瓶颈问题：通道价格昂贵，导致机器中设置的通道数量较少。
  • 瓶颈问题解决：增加设备到主机间的通路而不增加通道。把一个设备连接到多个控制器上，而一个控制器连接到多个通道上。

设备分配

1. 设备分配

   • 设备控制表
   • 控制器控制表
   • 通道控制表
   • 系统设备表

2. 设备分配的步骤

   • 分配设备：设备队列
   • 分配控制器：控制器队列
   • 分配通道：通道队列

假脱机技术（spooling技术）

• 将一台物理设备虚拟为多台逻辑I/O设备
• 用软件的方法模拟脱机技术
• 输入井与输出井：（在磁盘上开辟的两个存储区域）用于收容I/O设备输入的数据和用户程序的输出数据。此外，它们分别对应于脱机的输入和输出的磁盘。
• 输入缓冲区和输出缓冲区：（在内存上开辟的两个缓冲区）缓和CPU和磁盘之间速度不匹配的矛盾。分别暂存由输入设备传送的数据之后再传送到输入井，以及暂存从输出井传送的数据之后再传送到输出设备。
• 输入进程和输出进程：分别用于模拟脱机输入输出的外围机。

缓冲区管理

• 缓和CPU和I/O设备间速度不匹配矛盾
• 减少对CPU的中断频率
• 解决数据粒度不匹配问题
• 提高CPU和I/O设备之间的并行性

面试题

1、中断和程序并发之间的关系是什么？

中断是程序并发的必要条件。如果没有中断，操作系统不能获得系统控制权，无法按调度算法对处机进行重新分配，一个程序将一直运行到结束而不会被打断。

2、spooling系统的工作原理。

在SPOOLING系统中，多台外围设备通过通道或DMA器件和主机与外存连接起来，作业的输入输出过程由主机中的操作系统控制。 操作系统中的输入程序包含两个独立的过程，一个过程负责从外部设备把信息读入缓冲区，另一个过程是写过程，负责把缓冲区中的信息送入外存输入井中。在系统输入模块收到输入作业输入请求后，输入管理模块中的读过程负责将信息从输入装置读入缓冲区。当缓冲区满时，由写过程将信息从缓冲区写到外存输入井中。读过程和写过程反复循环，直到一个作业输入完毕。当读过程读到一个硬件结束标志后，系统再次驱动写过程把最后一批信息写入外存并调用中断处理程序结束该次输入。然后，系统为该作业建立作业控制块JCB，从而使输入井中的作业进入作业等待队列，等待作业调度程序选中进入内存。

3、中断向量的内容是由操作系统程序确定的还是由用户程序确定的？

中断向量的内容是由操作系统程序确定的。向量的内容包括中断处理程序的入口地址和程序状态字（中断处理程序运行环境），中断处理程序是由操作系统装入内存的，操作系统将根据装入的实际地址和该中断处理程序的运行环境来填写中断向量。

4、硬件将处理机划分为两种状态，即管态和目态，这样做给操作系统设计带来什么好处 ?

便于设计安全可靠的操作系统。管态和目态是计算机硬件为保护操作系统免受用户程序的干扰和破坏而引入的两种状态。通常操作系统在管态下运行，可以执行所有机器指令；而用户程序在目态下运行，只能执行非特权指令。如果用户程序企图在目态下执行特权指令，将会引起保护性中断，由操作系统终止该程序的执行，从而保护了操作系统。

5、批处理系统（脱机批处理、联机批处理、执行系统的工作原理）。

联机批处理：操作员将一批作业的卡片放到读卡机上，监督程序通过内存将这批作业传送到磁带机上，输入完成后，监督程序开始处理这批作业。它自动的将第一个作业读入内存，并对其程序进行汇编或编译，然后将产生的目标程序与所需要的例行子程序连接在一起，继而执行该程序，计算完成之后输出其结果。第一个作业处理完后立即处理第二个作业，如此反复直到所有作业处理完毕。然后，监督程序将第二批作业由读卡机传送到磁带机，重复以上过程。 脱机批处理：对联机批处理进行了改进。待处理的作业由卫星机负责经读卡机传送到输入磁带上，主机由输入磁带读入作业并加以处理，其结果送到输出磁带上，最后由卫星机负责将输出磁带上的结果信息在打印机上输出。 执行系统：对脱机批处理进行了改进，即引入了通道，作业由读卡机到磁带机的传输以及运行结果由磁带机到打印机的传输由通道完成。通道取代了卫星机，也免去了手工装卸磁带的麻烦。

6、网络OS与分布式OS之间的异同点。

从透明性上看，分布式操作系统优于网络操作系统。网络用户能够感觉到所访问的资源是在本地还是在远地；而在分布式系统中，用户感觉不到所访问的资源是否在本地，分布式操作系统掩盖了资源在地理位置上的差异。

从资源共享上看 ,分布式操作系统比网络操作系统能共享更多的资源。在网络操作系统中，一个计算任务不能由一台主机任意迁移到另外一台主机上运行；而在分布式操作系统中，所有作业可以由一台主机任意迁移到另外一台主机上处理，即可实现处理机资源的共享，从而达到整个系统的负载平衡。

7、在用户自行处理的中断中，为什么中断处理程序必须将系统堆栈中的现场信息弹出并压入用户堆栈。

中断发生时，被中断程序的现场信息已被压入系统堆栈中。而中断续元运行于目态，它执行完毕后将由用户堆栈区中恢复现场。 为此，操作系统在转到中断续元之前还应当将系统堆栈中的现场信息弹出并压入用户堆栈中，否则中断续元执行完毕后将无法恢复现场返回断点。

8、为什么说中断是进程切换的必要条件，但不是充分条件?

① 发生进程切换时一定发生中断。系统由一个运行进程转去运行另外一个进程，前提条件是必须进入操作系统，即处于系统态，因为处于用户态运行的进程不可能将cpu的使用权直接交给另一个进程，而中断是从用户态转换为系统态的必要条件。即中断是进程切换的前提（必要）条件。

② 发生中断时未必发生进程切换。如果中断处理完后原进程不再具有继续运行的条件，则一定会发生进程切换；反之，如果中断处理完后原进程仍具有继续运行的条件，则可能会发生进程切换，也可能不发生进程切换，这与处理机调度策略有关。

9、实现线程有几种方法？各有什么优缺点？

a. 用户级别线程

优点：（1）不依赖于操作系统，调度灵活；

（2）同一进程中的线程切换不需进入操作系统,切换速度快 缺点：（1）同一进程中多个线程不能真正并行，即使在多处理机环境中

（2）由于线程对操作系统不可见，调度在进程级别，某进程中的一个线程通过系统调用进入操作系统受阻，该进程的其它线程也不能运行

b. 核心级别线程

优点：（1）同一进程内多线程可以并行执行

（2）一线程进入核心等待，其它线程仍可执行 缺点：（1）系统开销大，同一进程内多线程切换速度慢 （2）调度算法不能灵活控制 c. 混合线程

优点：用户级线程系统不可见，系统级线程用户不可见，用户级线程与系统级线程之间通过轻进程建立联系，轻进程是用户和系统都可见的实体。

10、在某些虚拟页式存储管理系统中，内存永远保持一个空闲页面，这样做有什么好处？

在内存没有空闲页架的情况下，需要按照置换算法淘汰一个内存页架，然后读入所缺页面，缺页进程一般需要等待两次I/O传输时间。若内存总保持一个空闲页架，当发生页故障时，所缺页面可以被立即调入内存，缺页进程只需等待一次I/O传输时间。读入后立即淘汰一个内存页面，此时可能也需执行一次I/O传输，但对缺页进程来说不需等待，因而提高了响应速度。

11、覆盖与交换技术，以及解决的问题。

（1）覆盖技术是只将全局代码和数据静态地放在内存，其它部分分阶段地动态装入，后装入的对象重复使用以前对象所占有的空间，即覆盖以前的对象。动态装入的成分被称作覆盖。 解决程序大、空间小、装不下的问题。

（2）交换技术：每当发生进程切换时，总是将当前进程的所有代码、数据、栈全部从内存复制到外存（换出），再将新当前进程的所有代码、数据、栈全部从外存复制到内存（换入）。 解决程序多、空间小、装不下的问题。

12、进程通信的消息缓冲方式的实现方法。

在操作系统空间中保存有一组缓冲区，发送进程在执行send命令时，产生自愿性中断进入操作系统，操作系统为其分配一个缓冲区，并将所发送的消息内容由发送进程空间拷贝到缓冲区，然后将缓冲区连到接收进程的消息链中，便完成了发送。当接收进程执行到receive命令时，也产生自愿性中断进入操作系统，操作系统将载有消息的缓冲区由消息链中取出，并将消息内容拷贝到接收进程空间中，然后收回该空闲缓冲区，如此就完成了消息的接收。

13、死锁产生的必要条件。

a.资源独占：一个资源在同一时刻只能分配给一个进程。 b.不可剥夺：资源只能由占有者在使用完后自愿释放。

c.保持申请：进程在占有部分资源后还可申请新的资源，而且在申请新资源时并不释放已占有资源。

d.循环等待：存在一个进程等待序列{p1，p2,…,pn},其中p1等待p2所占有的某一资源，p2等待p3所占有的某一

资源，...，pn等待p1所占有的某一资源。

14、与操作系统相关的主要寄存器有哪些。

① 首址寄存器：存放当前执行指令的基地址。

② 限长寄存器：存放当前执行指令的长度。

③ 联想寄存器（快表）：用于保存正在运行指令中的一部分项目。

15、在段式存储管理中，段的长度可否大于内存的长度？在段页式存储管理中呢？

在段式存储管理中，段的长度不能大于内存的长度，因为一个独立的段占用一段连续的内存空间，内存分配是以段为单位进行的，如果一个段的长度大于内存的长度，那么该段将无法调入内存。在段页式存储管理中，段的长度可以大于内存的长度。因为内存分配的单位是页，一个段内逻辑上连续的页面，可以分配到不连续的内存页面中，不要求一个段的所有逻辑页都进入内存。

16、比较文件名、文件号、文件描述符之间的关系。

(1)文件名是文件的外部名字，通常是一个符号名(字符串)，同一文件可以有多个文件名(如通过link)。 (2)文件号是文件的内部名字，通常是一个整数，文件号与文件具有一对一的关系。

(3)文件描述符是文件打开时返回的整数(入口地址)，对应用户打开文件表中的一个入口。同一文件可以被多个用户同时打开，此时返回的文件描述符一般不同。同一文件也可以被同一用户多次打开，每次打开时返回的文件描述符一般也不同。

17、使用文件描述符存取打开文件与直接使用文件名相比有何优点？

首先，文件名是一个字符串，操作速度慢且占空间大，而文件描述符为一整数，其处理效率明显高于字符串。 其次，文件被打开后其控制信息 ( FCB )被缓冲到内存系统空间，文件描述符作为用户打开文件表中的入口地址直接与内存 FCB建立起联系，而文件名无法做到这一点。

18、用户打开文件表中包含那些内容？为何不能将其合并到系统打开表中？

用户打开文件表中包含以下内容： 文件描述符

打开方式

读写指针

系统打开文件表入口

由于文件是可共享的，多个进程可能会同时打开同一文件，而其打开方式可能是不同的，当前的读写位置通常也是不一样的。如果将这些信息合并到系统打开文件表中，就会导致一个共享文件占用多个系统打开文件表表目，这些表目的大部分内容是重复的。当一个进程对文件的操作导致FCB内容变化时，该进程关闭文件时就要将FCB回写到外存。增加了内外存传输的次数，也容易导致FCB内容的不一致。因此，通常将打开方式和读写指针记录在另外一个表，即用户打开文件表中。

19、文件共享的实现机制。

① 公共目录：在系统中设有若干个可被所有用户访问的公共目录，将可被所有用户共享的文件登记在这些目录中，每个用户均可访问记录于这些目录中的文件，如此可实现用户对文件的共享。

② 连接：通过连接可使一个文件具有多个名字，不同用户可使用不同名称访问同一个文件，从而实现文件共享。对共享的限制通过对于连接的限制来实现。

③ 共享说明：每个文件在创建时由文件主规定一个共享说明。 20、常用的文件物理结构。

（1）顺序结构：一个文件占有若干个连续的物理块，其首块号及块数记录于文件控制块FCB中。 优点：速度快，节省空间 缺点：长度变化困难

（2） 链接结构：一个文件占若干个不连续的存储块，各块之间以指针相连，首块号及块数记录于该文件的控制块FCB中。优点：节省空间，长度变化容易。 缺点：随机访问速度慢。

（3）索引结构：一个文件占有若干个不连续的存储块,这些块的块号记录于一个索引块中。 优点：速度快，长度变化容易 缺点：索引块占空间

（4）散列结构：适用于定长记录和按键随机查找的访问方式，常用于构造文件目录。 （5）倒排结构：以键值和记录地址构成的索引结构 优点：适合于不同的查找方式,速度很快; 缺点：索引会带来较大的系统开销。

21、常用的文件逻辑结构。

（1）记录式文件：记录的序列

a.等长记录（优点：处理方便，速度快；缺点：空间浪费） b.不等长记录（优点：省空间；缺点：处理不便，速度慢）

（2）流式文件：字节的序列

22、外围设备与内存之间常用的数据传送控制方式。

（1）程序控制查询方式：处理机代表进程向相应的设备模块发出I/O请求，处理机反复查询设备状态，直至I/O完成；可采用硬件提供的专用I/O指令，也可采取内存操作指令完成，其缺点是：忙式等待，效率较低。

（2）中断驱动方式：设备具有中断CPU的能力，可与CPU并行，既可采用硬件提供的专用I/O指令，也可采用内存映射I/O指令完成。其缺点是：当设备较多时，对CPU的打扰很多。

（3）DMA方式：硬件有DMA控制器，操作系统可采用DMA方式进行I/O操作，一个DMA可控制多个设备(并发)进行DMA传输，无论DMA位置何处，都可独立CPU直接访问总线。

（4）通道方式：通道是专门的处理机，有自己的指令系统，可实施复杂的I/O控制，一个通道程序可以控制若干设备进行多次IO传输，没有独立的存储空间,与主机共享同一个内存。

25、缓冲池管理的4个操作的原理。

系统中设有两个缓冲池管理程序,分别用于缓冲区的分配和去配。设一个缓冲池中缓冲区的总数为 N，定义描述资源的信号量：buff_num，初值=N，对缓冲池的链操作需互斥进行，定义互斥信号量：mutex，初值=1。

a.执行P（buff_num），申请一个缓冲区，当buff_num≥0，表示有空闲缓冲区，可分配，否则，不分配。

b.执行P（mutex），表示对缓冲池的链操作需互斥进行。

c.执行V（buff_num），释放一个缓冲区，当buff_num≤0，表示有进程在等待空闲缓冲区，需将等待队列中的一个进程唤醒。

d.执行V（mutex），表示释放对缓冲池的互斥权，其他进程可访问缓冲区。