考研复试计算机系统笔记

操作系统

操作系统组成

内核态与用户态

**内核态（Kernel Mode)**与 **用户态（User Mode)**：是CPU运行的两种模式。

• 内核态是操作系统核心代码运行的特权级别。在内核态中，操作系统有完全的访问权限和控制权限，可以执行任意指令、使用任意寄存器、访问系统内存和硬件资源。内核态可以执行系统级别的操作，如创建和销毁进程、分配内存、读写硬件设备等等。由于内核态具有最高的特权级别，因此在该模式下执行的代码具有非常高的安全风险，因此只有操作系统核心代码可以运行在内核态中。
• 用户态是应用程序运行的特权级别。在用户态中，应用程序只能访问到分配给它的资源和内存，不能直接访问系统内存或硬件资源。应用程序不能执行特权指令或系统调用，这些操作只能通过操作系统提供的接口来实现。用户态运行的程序具有较低的特权级别，因此不能访问内核态中的数据或资源。

CPU工作状态的切换：

• 用户态 -> 内核态：通常是使用访管（Trap)命令实现，也就是常说的陷入机制。同时还可以通过中断、异常来实现切换。

• 内核态 -> 用户态：由一条改变 psw（程序状态字寄存器) 值的特权指令来实现。

微内核（Micro kernel)

微内核是操作系统的一种内核架构模式，相较于宏内核，在微内核架构的操作系统中，只有操作系统的核心功能例如：时钟管理、中断处理、原语操作被放入内核内部，而例如进程管理、存储管理、设备管理等功能则在用户态中实现。

微内核具有更高的可扩展性与可靠性，操作系统中一个模块的崩溃并不会导致整个操作系统的崩溃，同时微内核还是采用客户/服务器模式，内核看做客户端，用户态的进程看做服务器端，两者通过消息传递机制实现通信。

但是相较于宏内核设计模式，微内核服务的实现需要频繁切换用户态与核心态，且用户态的各个功能模块不能直接调用，而是通过内核的**”消息传递机制”**实现，这回导致相较于宏内核架构模式，微内核的性能更低。

系统调用

什么是系统调用？

知识点回顾：

操作系统作为用户和计算机硬件之间的接口，需要向上提供一些简单易用的服务。主要包括命令接口和程序接口。其中，程序接口由一组系统调用组成。

联机命令接口（输入一个执行一个)：用户可以使用联机控制命令来对自己的作业进行控制，联机用户接口可以实现用户与计算机的交互

脱机命令接口（输入一堆执行一堆)：也称为批处理用户接口，用户使用JCL（用户控制语言)写好作业说明书，将其和作用的程序和数据一起提交给计算机，OS将逐条按JCL自动控制作业的执行。

系统调用（仅程序能调用)：操作系统提供给应用程序（程序员/编程人员)使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以通过系统调用来请求获得操作系统内核的服务。**

小例子：为什么系统调用是必须的？

什么功能要用系统调用实现？

应用程序通过系统调用请求操作系统的服务。而系统中的各种共享资源都由操作系统内核统一掌管，因此凡是与共享资源有关的操作（如存储分配、I/O操作、文件管理等)，都必须通过系统调用的方式向操作系统内核提出服务请求，由操作系统内核代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作。

系统调用相关处理涉及到对系统资源的管理、对进程的控制,这些功能需要执行一些特权指令才能完成,因此系统调用的相关处理需要在核心态下进行。

系统调用的过程

系统调用与库函数的区别

系统调用与过程调用的区别与联系

区别：

1. 目的不同：系统调用是为了访问操作系统内核中提供的功能而调用的，而过程（函数)调用是为了执行程序中的某些特定代码块而调用的。
2. 调用方式不同：系统调用需要使用软件中断（int 0x80)等方式进行调用，进入内核空间进行相应的操作；而过程（函数)调用只需要使用CALL指令即可。
3. 运行环境不同：系统调用是在内核态下运行的，需要切换用户态与内核态，进入内核空间运行，而过程（函数)调用是在用户态下运行的。
4. 运行效率不同：由于需要进行用户态与内核态的切换，系统调用的效率相对较低，而过程（函数)调用则无需进行此操作，相对更快。
5. 安全性不同：系统调用需要进入内核空间进行操作，可以实现对硬件资源的管理和保护，因此比过程（函数)调用更加安全可靠。

联系：

1. 参数传递方式相同：系统调用和过程调用都需要将参数传递给被调用的函数或服务。
2. 返回值方式相同：系统调用和过程调用都需要返回值来告诉调用者执行的结果。

中断与异常

中断与异常的概念

• 中断（Interruption) 也称外中断，指外部事件打断了CPU正在执行的程序的执行流程，使得CPU需要立即响应事件，执行特定的操作。

• 异常（Exception) 也称内中断，是指来自CPU执行指令内部的事件。

中断与异常的分类

• 中断包括：可屏蔽中断（INTR) 和 不可屏蔽中断（NMI)
• 异常包括：故障（Fault)、自陷（Trap)、终止（Abort)。故障是由指令执行时引起的异常，例如缺页故障、除数为0，自陷是一种是先安排好的“异常”事件，而终止是出现了使 CPU 终止的硬件故障。

异常种类	例子	返回位置
故障（软件中断)	非法操作码、访存缺段、访存缺页、地址越界、除数为 0、浮点运算上溢	当前指令
自陷（软件中断)	通过执行陷入指令来进行系统调用，此时 CPU 从用户态陷入到内核态；调试、断点事件；访管指令或陷入指令	下一条指令
终止（硬件中断)	控制器出错、存储器校验错	无法返回（程序终止）

【注意】

• 异常不可被屏蔽。
• Cache 缺失不会引起异常，因为 Cache 缺失和虚拟存储器缺页缺段不是一个原理。
• 软件中断又称为程序性异常。

中断与异常的响应时间

• 中断：只能在指令周期中的中断周期被响应，即一条指令的最后
• 异常：能够在发起异常的下一个时钟周期就得到响应，应该是很快或者是立刻。

中断与异常的返回位置

• 中断：返回下一条指令
• 异常：故障返回当前指令，自陷返回下一条指令，终止无法执行指令。

线程进程

问题1、进程和程序的比较

• 程序是存放在文件系统的比特信息，是永存的；而进程是暂时的，是程序在数据集上的一次执行；
• 程序是静态的观念；进程是动态的观念，其可以被创建、阻塞、终止。
• 进程具有并发性，而程序没有；
• 进程是计算机资源的分配基本单位，程序不是。

问题2、什么是进程,什么是线程?

进程是操作系统中资源分配基本单位，表示一个正在运行的应用程序或任务。每个进程都有一个独立的地址空间，可以独立地运行并占用系统资源。

线程是操作系统中的调度单位，是程序执行流的最小单元。每个线程有独立的程序计数器、调用栈和寄存器，但共享同一进程的其他资源。

进程与线程的区别在于，进程是独立的资源分配单位，线程是进程的一部分，是进程内部的执行流。因此，创建和管理进程的代价比较大，但每个进程独立运行，它们之间互不干扰。而创建和管理线程的代价较小，但它们共享同一进程内的资源，如果一个线程发生异常，可能会影响到其他线程的正常运行。

补充 : 父子进程可以共享资源但不共享存储空间，而进程与线程既可以共享资源也可以共享空间。

问题3、有了进程为什么需要线程?

答 ：在引入线程之前，进程是操作系统中资源分配和调度的基本单位，它可以独立运行并占用系统资源，但是进程的创建和切换都是有代价的，因此，对于一些需要高效执行的任务，如果使用进程进行处理，就可能带来较大的开销。

引入线程之后，线程是进程的一个执行单元，它成为了调度的基本单位，它可以共享进程的资源，而不需要独占系统资源，因此创建和切换线程的开销要远小于进程。同时，由于线程的轻量级特性，系统可以快速切换线程，从而使程序具有较好的响应速度。

问题4、同步互斥机制遵循的原则

答：1、空闲让进 2、忙则等待 3、有限等待 4、让权等待

问题5、死锁

• 死锁的定义：两个或多个进程因竞争资源或者互相等待对方释放资源而造成的一种僵局现象。在死锁状态下，进程们会一直等待对方释放资源，不能继续执行，占用的系统资源也无法释放，导致系统长时间处于不可用状态。

• 死锁产生的原因：互斥、不可剥夺、请求与保持、循环等待。

• 死锁解除的方式：

  • 死锁预防：破坏互斥条件（不可行)，破坏不可剥夺条件（请求得不到满足时放弃所有不可剥夺资源)，破坏请求与保持条件（一次分配所有进程需要的资源)，破坏循环等待条件（顺序资源分配法，只能按照编号递增的顺序分配资源)
  • 死锁避免：银行家算法判断分配后是否处于系统安全状态
  • 死锁检测 + 死锁解除：利用资源分配图检测死锁，利用资源剥夺、进程撤销、进程回退的方式解除死锁。

问题6、PV操作

6.1 司机售票员问题

6.2 哲学家进餐问题

semaphore chopstick[6] = {1, 1, 1, 1, 1, 1};
semaphore mutex = 1;

// i 号哲学家进程
pi（) {
     while（true) {
          p（mutex);
          p（chopstick[i]);
          p（chopstick[（i + 1) % 6]);
          进餐;
          v（chopstick[i]);
          v（chopstick[（i + 1) % 6]);
          v（mutex);
          思考;
     }
}

问题7、PCB中存有哪些数据

问题8、线程的实现方式

1、用户级线程

1.1 用户级线程实现方式

在用户级线程中，有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在. 应用程序可以通过使用线程库设计成多线程程序. 通常，应用程序从单线程起始，在该线程中开始运行，在其运行的任何时刻，可以通过调用线程库中的派生例程创建一个在相同进程中运行的新线程。

对于设计了用户级线程的系统，其调度仍是以进程为单位进行的，各个进程执行一个时间片。

例如下面的代码模拟了定义了用户级线程：

int mian（) {
  int i = 0;
  while（1) {
       if （i % 3 == 0) {处理视频聊天的代码;}
       if （i % 3 == 1) {处理文字聊天的代码;}
       if （i % 3 == 2) {处理文件传输的代码;}
  }
}

如果将每一个操作都比作一个线程，看上去线程之间并发执行，单其实这些线程公用一个进程的处理机资源，线程的切换也只是在用户层用条件判断语句来控制，如果一个用户级线程阻塞（例如在某个代码处打上断点)，整个进程中的所有用户级线程均无法运行。同时，拥有更多代码行的用户级进程能更多地占用处理机资源，这显然是不公平的。

1.2 用户级线程的优势

1. 可以在不支持线程的操作系统中实现。
2. 创建和销毁线程、线程切换代价等线程管理的代价比内核线程少得多, 因为保存线程状态的过程和调用程序都只是本地过程
3. 允许每个进程定制自己的调度算法，线程管理比较灵活。这就是必须自己写管理程序，与内核线程的区别
4. 线程能够利用的表空间和堆栈空间比内核级线程多
5. 不需要陷阱，不需要上下文切换，也不需要对内存高速缓存进行刷新，使得线程调用非常快捷
6. 线程的调度不需要内核直接参与，控制简单。

1.3 用户级线程的缺陷

1. 线程发生I/O或页面故障引起的阻塞时，如果调用阻塞系统调用则内核由于不知道有多线程的存在，而会阻塞整个进程从而阻塞所有线程, 因此同一进程中只能同时有一个线程在运行
2. 一个单独的进程内部，没有时钟中断，所以不可能用轮转调度的方式调度线程
3. 资源调度按照进程进行，多个处理机下，不能充分发挥处理机的优势

2、内核级线程

2.1 内核级线程的实现方式

在内核级线程中，内核线程建立和销毁都是由操作系统负责、通过系统调用完成的。在内核的支持下运行，无论是用户进程的线程，或者是系统进程的线程，他们的创建、撤销、切换都是依靠内核实现的。
内核线程驻留在内核空间，它们是内核对象。有了内核线程，每个用户线程被映射或绑定到一个内核线程。用户线程在其生命期内都会绑定到该内核线程。一旦用户线程终止，两个线程都将离开系统。这被称作”一对一”线程映射，

1. 线程的创建、撤销和切换等，都需要内核直接实现，即内核了解每一个作为可调度实体的线程
2. 这些线程可以在全系统内进行资源的竞争
3. 内核空间内为每一个内核支持线程设置了一个线程控制块（TCB)，内核根据该控制块，感知线程的存在，并进行控制

如图所示,即内核级线程的实现方式, 每个用户线程都直接与一个内核线程相关联.

2.2 内核级线程的优势

①能发挥多处理机的优势，内核能同时调度同一进程中的多个线程并行执行。

②如果进程中的一个线程被阻塞，内核可以调度该进程中的其他线程占用处理机，也可运行其他进程中的线程。

③内核支持线程具有很小的数据结构和堆栈，线程切换比较快、开销小。

④内核本身也可采用多线程技术，可以提高系统的执行速度和效率。

2.3 内核级线程的缺陷

相较于用户级线程，同一进程钟的线程切换，需要从用户态切换到核心态进行，系统的开销更大。

3、组合方式

结合前两种实现方式的优点，同时也更加灵活：

问题9、进程调度算法

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

1. 批处理系统

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

1.1 先来先服务 first-come first-served（FCFS）

非抢占式的调度算法，按照请求的顺序进行调度。

有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

1.2 短作业优先 shortest job first（SJF）

非抢占式的调度算法，按估计运行时间最短的顺序进行调度。

长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

1.3 最短剩余时间优先 shortest remaining time next（SRTN）

最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。 当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

2. 交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

2.1 时间片轮转

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

时间片轮转算法的效率和时间片的大小有很大关系：

• 因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
• 而如果时间片过长，那么实时性就不能得到保证。

2.2 优先级调度

为每个进程分配一个优先级，按优先级进行调度。

为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

2.3 多级反馈队列

一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。

每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

3. 实时系统

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

内存管理

空闲内存管理

连续分配管理方式

单一连续分配

一个程序独占整个用户区

特点：无外部碎片，有内部碎片

固定分区分配

将用户空间划分为若干个分区，每个分区只装入一道作业

特点：无外部碎片，有内部碎片

动态分区分配

根据进程的实际需要，动态为其分配内存空间，并使这些空间刚好够进程使用。

特点：无内部碎片，有外部碎片

动态分区分配算法：

• 首次适应算法（First Fit)：地址递增排列
• 最佳适应算法（Best Fit)：容量递增排列
• 最坏适应算法（Worst Fit)：容量递减排列
• 临近适应算法（Next Fit)：地址递增排列

程序装入内存步骤

• 预处理：预处理器可以删除注释、包含其他文件以及执行宏替代。
• 编译：编译预处理修改后的源文件生成编译程序文本（.s)。
• 汇编：汇编器将生成的汇编语言代码翻译为二进制目标程序（.o)。
• **链接（生成逻辑地址)**：将一个或多个由编译器或汇编器生成的目标文件外加库链接为一个可执行文件（.exe)。链接方式有：
  • 静态链接：运行前先将目标模块连接成一个完整的配置模块并不会再次拆开。
  • 装入时链接：在装入内存时，采用边装入，边链接的方式。
  • 运行时链接：当目标模块被使用时，才会将目标模块装入。
• **装入（生成物理地址)**：装入方式：
  • 绝对装入：只适用于单道程序，连接结束后将程序驻留在与逻辑地址相同的内存地址上不在变动。
  • 静态重定位：在装入时修改程序的指令和数据的地址，没有足够的内存空间就无法装入。
  • 动态重定位：装入内存的程序其所有地址为相对地址，当程序真正执行时再通过定位寄存器计算物理地址，只需要装入一部分程序即可投入运行。

文件管理

文件系统

问题一、文件系统的定义

文件系统是指一种组织和管理计算机存储设备上文件和目录的方式。它提供了一种标准化的方法来存储、访问、管理和维护文件和目录，使得用户可以方便地访问和管理存储在存储设备上的数据，磁盘上的每一个分区都可以拥有独自的文件系统。

常见的文件系统包括FAT、NTFS、EXT2/EXT3、HFS+等。

问题二、虚拟文件系统的定义

虚拟文件系统是一种抽象层，用于在操作系统中提供文件系统的统一接口。它可以让操作系统支持多种文件系统，并且使得不同的文件系统可以共享同一组API，使得用户和应用程序可以使用相同的接口来访问不同类型的文件系统。

虚拟文件系统向上层提供了统一的标准的系统调用接口，并要求下层的文件系统必须实现某些规定的函数功能。

问题三、操作系统的引导流程

1. CPU激活：激活CPU读取ROM中的boot程序，将指令寄存器设置为BIOS的第一条指令，执行BIOS程序。
2. BIOS自检：随后BIOS会进行自检，检查硬件设备是否正常。
3. MBR（主引导记录)程序加载：BIOS会查找硬盘的MBR 区域，并将MBR中的引导程序加载到内存中。MBR的作用是去告诉CPU去硬盘的哪一个分区去找操作系统。
4. PBR（分区引导记录)程序加载：读取活动分区的第一个扇区，这个扇区就是分区引导记录（PBR)，其作用是寻找并激活分区根目录下用于引导操作系统的程序。
5. 内核初始化：内核加载完成后，会进行一些初始化操作，例如初始化设备驱动程序、建立进程、创建根文件系统等。
6. 用户空间初始化：内核初始化完成后，会创建第一个用户进程，并将控制权转移给用户进程，从而进入用户空间。