Chapter 1

• 什么是操作系统

  1. 运行在内核态的软件 （software that runs in kernel space）
  2. 扩展机器 （extended machine）
  3. 资源管理器 （source manager）
  4. 用户和计算机硬件之间交互的接口 （interface between user and software）

• 什么是系统调用

  系统调用是操作系统提供给应用程序的一组接口，使应用程序可以直接使用操作系统的功能而不需要访问底层硬件和内核代码。操作系统会在接收到系统调用请求后执行相应的操作，并返回结果给应用程序。系统调用是操作系统与应用程序之间的桥梁，提供了一种安全、可靠的方式来访问系统资源和执行核心功能。

• 操作系统结构分类

  1. 单体系统结构
     所有的系统功能和服务都集中在一个单一的软件实体（内核）中。结构简单、性能高效、可维护性与可扩展性较差。
  2. 层次式系统结构
     系统被分为多层次的架构模式，每个层次提供特定的功能和服务，并且只与其上下相邻的层次进行通信。模块化、可维护性和可扩展性强。
  3. 微内核结构
     将操作系统内核划分为最小的核心功能集的架构模式。微内核只提供最基本的服务，如进程管理。高级功能如文件系统为用户空间的服务。微内核通过消息传递进行不同模块之间的通信，模块间彼此独立运行。高度模块化、可扩展性好，同时也提高了系统的可靠性和安全性。但是涉及到频繁的上下文切换和消息传递，微内核的性能相对较低。

$\color{red}{}$

• 什么是shell
  命令解释器

Chapter 2

• 什么是进程
  进程是正在运行的程序的实例

• 进程包括哪三部分
  1. 程序计数器
  2. 栈
  3. 数据段

• 进程创建的四种情况

  1. 系统初始化
  2. 正在运行的进程执行一个创建新进程的系统调用（fork()）
  3. 用户请求创建一个新进程
  4. 批处理作业初始化

• 什么是PCB* 进程终止的四种情况

  1. 正常退出 （自愿）
  2. 错误退出 （自愿）
  3. 严重错误 （非自愿）
  4. 被其他进程杀死 （非自愿） PCB（Process Control Block）进程控制块
     每个进程对应一个PCB，PCB是进程存在的唯一标志 包含：寄存器、程序寄存器、程序状态字psw、堆栈指针、进程ID

• 进程与程序的区别

  1. 进程是程序在内存中的执行实例，程序是静态的代码文件
  2. 进程是程序在计算机上运行时占用的资源，程序是开发人员编写的，用于实现特定功能
  3. 程序只需要存储在磁盘或其他存储介质上，而进程需要占用计算机的内存、处理器等资源
  4. 一个程序可以同时创建多个进程，每个进程都是相互独立的，并且可以并行运行

• 什么是线程
  线程是进程中的执行单元，是轻量级进程，是操作系统中进行调度的最小单位，是cpu的调用者

• 线程由哪三部分组成（这三部分也是线程私有的）

  1. 程序计数器（Program Counter）
  2. 寄存器集合（Register Set）
  3. 堆栈空间 （Stack Space）

• 线程间有哪几样是共享的 （我觉得这里有争议）
  1. 代码段 （code section）
  2. 数据段 （data section）
  3. 操作系统资源 （OS resources）

  4. ---

  5. 地址空间 （address space）
  6. 全局变量 （global varibles）
  7. 打开文件 （open files）

• 线程和进程的区别

  1. 进程是程序的执行实例，包含了程序、数据和资源的集合，是操作系统进行资源分配和调度的基本单位。线程是进程中的执行单元，是操作系统进行调度的最小单位，共享进程的资源。

  2. 进程是操作系统进行资源调度的基本单位，进程切换的开销较大。线程是在进程内部进行调度的，线程切换的开销较小。

  3. 进程是独立的实体，每个进程都有自己的地址空间、文件和设备等资源。每个进程拥有独立的内存空间，彼此之间的通信需要通过进程间通信（IPC）机制。线程是在进程内部创建和调度的，多个线程共享进程的内存空间、文件和设备等资源，线程之间可以直接访问共享数据，通信更加方便和高效。

• 进程五状态
  1. 创建
  2. 就绪
  3. 运行
  4. 阻塞
  5. 终止

• 进程转移图

• 什么时候切换进程

  1. 时间片用完了
  2. I/O中断
  3. 内存错误
  4. 陷阱
  5. 管理程序调用

• 线程的三种实现方式以及各自优缺点

  1. 用户级线程（User-Level Threads）：用户级线程是完全由用户程序管理的线程，操作系统对其一无所知。
     • 优点：
       1. 用户级线程的切换不需要内核介入，切换开销小。
       2. 允许各进程拥有自己的调度算法，良好的可扩展性
       3. 可利用的表空间和堆栈空间较内核级线程多
     • 缺点：
       1. 一个用户级线程的阻塞将会引起整个进程的阻塞
       2. 一个进程中只能有一个用户级线程在运行
       3. 多核处理器上无法实现真正的并行执行，因为操作系统只看到单个线程。
  2. 内核级线程（Kernel-Level Threads）：由操作系统内核直接支持和管理的线程。
     • 优点：
       1. 阻塞一个线程不会影响整个进程，因为内核可以独立地调度其他线程。
       2. 可以实现真正的并行执行，因为每个线程都由操作系统内核调度。
     • 缺点：
       1. 由内核参与调度，资源开销大
  3. 混合型线程（Hybrid Threads）：结合了用户级线程和内核级线程的优点。每个用户级线程对应一个或多个内核级线程，用户级线程库负责线程的创建和调度，内核级线程由操作系统内核管理。
     • 优点（两者优点都有）：
       1. 线程切换开销小
       2. 可以利用操作系统的调度和资源管理功能，实现真正的并行执行
     • 缺点：
       1. 需要同时管理用户级线程和内核级线程，增加了复杂性。
       2. 可能存在用户级线程和内核级线程之间的不匹配和不均衡。

• 父子进程间的三种共享情况

  1. 共享所有资源
  2. 子共享父部分资源
  3. 父子间无共享资源

• 求CPU利用率的题

• 哪三种情况下父进程会杀死子进程

  1. 子进程超量分配资源
  2. 子进程的任务不再被需要
  3. 父进程的终止

• 软硬链接的区别

  1. 硬链接：硬链接和源文件inode节点号相同，两者互为硬链接
  2. 软链接：软链接和源文件inode节点号不同，进而指向的块也不同，软链接指向的块中存放的是源文件的路径名，类似于快捷方式，存储着源文件的位置信息用于指向

• 知识补充

  1. 单核计算机不适合多线程
  2. （同一进程内）所有线程有相同地址空间和全局变量（All threads have exactly the same address space and global variables）
  3. 线程之间没有保护（一个线程可以读、写甚至清空另一个线程的栈）
  4. 线程更容易创建和摧毁（效率高10-100倍）

• 调度算法

• 调度算法例题

平均周转时间表

算法	A	B	C	D	E	平均周转时间
RR	16	28	22	15	20	20.2
priority	15	28	6	9	15	14.6
FCFS	5	12	17	20	24	15.6
SJF	5	28	12	5	15	13
Note: SJF的平均周转时间是最短的，可以根据这一性质来完成

• 一个好的实现互斥的解决方案，需要满足以下4个条件：

  1. 任何两个进程不能同时处于临界区
  2. 不应对CPU的速度和数量作出假设
  3. 临界区外运行的进程不能阻塞其他进程
  4. 不能使进程无期限等待进入临界区

• 几种实现互斥的方法（都用了忙等待busy waiting）

  1. 屏蔽中断
     每个进程在刚刚进入临界区后立即屏蔽所有中断，并在就要离开之前再打开中断。屏蔽中断后，时钟中断也被屏蔽。CPU只有发生时钟中断或其他中断时才会进行进程切换，这样，在屏蔽中断之后CPU将不会被切换到其他进程。于是，一旦某个进程屏蔽中断之后，它就可以检查和修改共享内存，而不必担心其他进程介入。
     优点：简单高效
     缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开关中断指令只能运行在内核态，开关中断命令如让用户随意使用会很危险）

  2. 锁变量
     设想有一个共享 (锁) 变量，其初始值为0。当一个进程想进入其临界区时，它首先测试这把锁。如果该锁的值为0, 则该进程将其设置为1并进入临界区。若这把锁的值已经为1, 则该进程将等待直到其值变为0。于是，0就表示临界区内没有进程，1表示已经有某个进程进入临界区。但是，这种想法也包含了与假脱机目录一样的疏漏。假设一个进程读出锁变量的值并发现它为0,而恰好在它将其值设置为1之前，另一个进程被调度运行，将该锁变量设置为1。当第一个进程再次运行时，它同样也将该锁设置为1, 则此时同时有两个进程进入临界区中

  3. 严格轮换法
     自旋锁spin lock （也叫忙等锁busy waiting lock）

     

  4. Peterson解法

     情况1： 情况2：

  5. TSL指令
     TSL测试并加锁（test and set lock），它将一个内存字lock读到寄存器RX中，然后在该内存地址上存一个非零值。读字和写字操作保证是不可分割的，即该指令结束之前其他处理器均不允许访问该内存字lock。执行TSL指令的CPU将锁住内存总线，以禁止其他CPU在本指令结束之前访问内存。

     XCHG REGISTER, LOCK 能否替换为以下代码

         MOV REGISTER2, LOCK
         MOV LOCK, REGISTER
         MOV REISTER, REGISTER2
     

     不可以替换
     XCHG是一个原子操作，可以原子地交换两个操作数的值。但给出的替换代码并不能实现原子性操作，可能被中断或暂停，存在线程之间的竞争

     在多线程环境下，如果两个线程同时执行这段代码，可能会导致竞态条件和数据不一致的问题。
     因此，为了确保对共享变量的安全访问和修改，在多线程环境下，应该使用原子操作指令（如XCHG指令）或专门提供的同步原语（如锁、互斥量等）。这些机制可以确保多个线程之间对共享数据的原子操作，避免竞态条件和数据不一致问题。

• 信号量

  • 生产者消费者
    P -- down -- wait V -- up -- signal 考过一模一样的题，生产者消费者很重要：
    

  • 利用线程实现生产者消费者 (代码填空，很对称)
    

• 什么是管程
  管程是一个由进程、变量和数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。
  进程可以在任何需要的时候调用管程中的内容，但它们不能在管程之外声明的过程中直接访问管程内的数据结构。任意时刻管程中只能有一个活跃进程。这一进程使管程能有效地完成互斥。

• 经典IPC问题
  • 哲学家就餐问题
  • 读者写者问题
    

chapter 3

• 死锁产生的原因

  1. 系统资源不足
  2. 资源分配不当
  3. 进程运行推进顺序不合适

• 为什么程序初始化时分配资源不会导致死锁？

  1. 初始分配资源量小
  2. 初始分配资源有序
  3. 初始分配采用一些策略保证不会死锁，如池资源技术

• ❤️产生死锁四必要条件❤️

  1. 互斥条件
  2. 请求与保持条件
  3. 不可剥夺条件
  4. 循环等待条件

• 解决死锁的四种方式

  1. 忽略所有问题
  2. 检测与恢复
  3. 动态避免
  4. 预防

• 死锁预防

  1. 攻击互斥条件
  2. 攻击保持等待情况
  3. 攻击不可剥夺条件
  4. 工具循环等待条件

• 大题

chapter 4

• 内存：程序在执行前要先放到内存中，才能被cpu处理。内存可以缓和cpu与磁盘之间的速度矛盾。
• 存储单位

  • 位（bit， 比特）：一个二进制位，计算机数据存储最小单位

  • 字节（Byte、B）：八个bit

  • 字（word）：十六个bit

    

• 内存管理系统分为两类：
  1. 执行时将进程在内存和磁盘之间移动的系统（使用了swapping和paging的）：固定分区的多道程序设计
  2. 没有使用swapping和paging的：无交换或分页的单道程序设计方式

• cpu利用率计算： cpu利用率 = 1 - （I/O占比）^ 用户个数

• 有时内存空间不够装下所有的活跃进程，则有两种方法处理内存超载：

  1. swapping交换技术
  2. virtual memory虚拟内存技术

• 内存分配在两种情况下改变：

  1. 进程进入内存
  2. 进程离开内存

• memory compaction内存紧缩

• 跟踪内存使用情况的两种方法

  • 位图
  • 空闲区链表

• 如何将装入模块（就是可执行文件.exe）中的逻辑地址转换为在内存中的物理地址

  1. 绝对装入
     在编译时如果就知道该程序将要存放在内存中的位置，则让编译程序直接将装入模块中的地址修改为接下来在内存中的绝对地址 缺点：灵活性差，只适用于单道程序环境（一个时刻只能完成一个程序）。在别的计算机上内存起始位置又有不同，可移植性差

  2. 可重定位装入（静态重定位）
     装入模块在装入内存时进行重定位，也就是在装入内存的时候进行地址转换。若没有足够内存则无法装入。注意：若使用静态重定位，装入内存后地址不能再变化，在内存中位置不能移动

     

  3. 动态运行时装入（动态重定位）
     装入模块在装入内存之后，用的都还是相对地址，借助重定位寄存器来实现该装入模块在内存中位置的移动。

     

• 链接的三种方式
  1. 静态链接：将各个目标模块连接成一个完整的装入模块，然后再放入内存，该装入模块之后不会被拆开
  2. 装入时动态链接：目标模块在装入内存之前是分散的，在装入内存之后模块才会链接起来
  3. 运行时动态链接：在程序执行的时候，要用到哪个模块，才把这个模块装入到内存中，再进行链接。不用的就不会被装入内存。
• 内存保护：不能出现一个进程能擅自访问另一个进程内存空间的情况。两种实现方法：
  1. 在cpu中设置一对上下限寄存器，存放一个进程的上限地址和下限地址。当进程要访问内存中的某个地址时，cpu会检查待访问的那个内存地址是否越界 2. 采用重定位寄存器和界地址寄存器，记录起始物理地址和该进程分配的地址数量
• 内存空间扩充的三种方法
  • 为什么要扩充内存？因为程序大小远大于物理内存！

  1. 覆盖技术：将程序分为多个段，常用的段一直放在内存里，不常用的在用的时候再调入内存

  2. 交换技术：内存空间紧张时，系统将内存中某些进程暂时换出内存，把外存中准备运行的进程换入内存（注意：PCB需要常驻内存不换出，因为它记录了进程的运行到哪个状态）
     暂时被换出内存的进程进入挂起状态

• 内存空间分配与回收

  • 连续分配：为用户进程分配的必须是一个连续的内存空间。

    • 单一连续分配：同一时刻内存中只能有一道用户程序，不支持多道程序并发运行

    • 固定分区分配：

    • 动态分区分配：不会预先划分内存分区，而是进程在进入内存之后再根据进程大小动态建立分区 动态分区分配使用的数据结构

      动态分区分配算法：first-fit best-fit

  • 非连续分配管理方式

    • 基本分页存储

      那么又该如和将进程的页和内存中的页框一一对应呢？使用页表！页表存放在PCB中

      每一个页表项几个字节？（注意！页表项中的页号不占空间哦）页面=页 求页内偏移量

      

      

      

      逻辑地址转物理地址例题!

• 什么是TLB
  TLB是一种小型的硬件设备，称为转换检测缓冲区（Translation lookaside buffer），一种访问速度比内存快很多的高速缓存，可以加快虚拟地址到物理地址的转换。用来存放最近访问的页表项的副本，如果该页号在页表中对应的页表项在TLB中，就无须再访问页表，直接访问TLB，加速地址变换的速度。块表的查询速度比页表快很多。
  下面的访问过程很重要

• 可以将整个页表都放在TLB中吗？
  tlb这种高速缓存，造价高，成本高

• 单级页表的问题：
  • 页表必须连续存放，页表很大时，需要占用多个连续页框
  • 局部性原理，页表无需常驻内存

• 引入多级页表的原因：避免把全部页表一直保存在内存中，特别是从不需要的页表就不应保留

• 基本分段存储管理方式

  

• 存储管理器（memory manager）：在操作系统中管理分层存储体系

• MMU：memory management unit内存管理单元，将虚拟地址映射到物理内存地址上，将虚拟地址转换为物理地址

• 虚拟地址空间被分成的一个个小的单元叫做页表
• 物理内存中相应的地址单元被称作页框
• 当MMU注意到页面未映射并导致CPU捕获到操作系统时。此陷阱称为页面错误

• 页表的目的：将虚拟页映射到页框上

• 两种实现大而快速的页映射的设计：

  1. 使用由“快速硬件寄存器”阵列组成的单一页表，每一个页表项对应一个虚拟页面，虚拟页号作为索引，在启动一个进程时，操作系统将保存在内存中的进程页表的副本载入到寄存器中。

  • 优点：实现简单，映射过程中无需访问内存

  • 缺点：页表很大时，造价昂贵，每次上下文切换必须装载整个页表，降低性能

  2. 整个页表都在内存中，此时所需硬件只有一个只想页表起始位置的寄存器，这样在上下文切换时
  • 优点：完成“虚拟地址到物理地址的映射”仅需重新装入一个寄存器
  • 缺点：执行每条指令时，，都需要一次或多次内存访问来完成页表项的读入，速度很慢

• 页面置换算法
  OPT、FIFO、LRU

• 内存动态分区分配 首次适应、最好适应、最坏适应、领近适应

chapter 5

• I/O设备分类
  • 块设备：信息被存储在大小固定的块中，每个块有自己的地址。每个块可以单独的进行读写。如硬盘
  • 字符设备：发出或接收一个字符串流，没有标注地址，没有任何寻找操作。如打印机、网络接口、鼠标

• io设备有两个组成部分：机械部分和电子部分，电子部分是设备控制器，它可以控制一个或多个设备。设备控制器的任务：
  1. 将 比特流 转换为 字节块
  2. 执行任何必要的错误更正
  3. 将其复制到主存（其是啥啊）

• 内存映射io

  • 每一个设备控制器都有几个用来和cpu交流的寄存器
  • 写入这些寄存器：操作系统可以命令控制设备传送数据、接收数据、打开或关闭自己
  • 从这些寄存器读出：操作系统可以知道设备当前的状态，比如该设备是否准备好接受新指令
  • 除 控制寄存器（就是上面用来和cpu交流的寄存器） 之外，很多的设备都有一个可以让操作系统来进行读写的缓冲区（如显卡的显存）
  • 问题：CPU如何与控制寄存器、数据缓冲区交流的
  • （a）分离开的io和内存空间
    • 每一个控制寄存器被分配了一个io端口号
    • 内存和io的地址数是不同的

  • （b）内存映射io

    

    • 将所有的控制寄存器映射到内存空间
    • 每一个控制寄存器被分配到一个 专属的内存地址
    • 优点：
      1. 拥有内存映射io后，一个io设备驱动可以被一整个写入C。此外，也需要用到一些装配代码
      2. 不需要特殊的保护机制来阻止用户进程执行io
      3. 每一条可以访问内存的指令也可以访问控制存储器
    • 缺点：
      1. 现在的大多数计算机都有某种形式的内存字缓存。而缓存一个设备控制寄存器将是灾难性的。选择性地禁用缓存又会增加额外的复杂度。 2.如果只有一个地址空间，那么所有的内存模块和所有的io设备一定会检查所有的内存访问来看看哪些需要相应。大多数现代计算机都有一个专用的高速内存总线，于是io设备经过内存总线时不能查看内存地址

  • （c）前两种的混合型

• DMA 直接存储器访问
  • CPU需要寻址设备控制器以与它们交换数据，如果一次请求一个字节的数据，浪费CPU的时间。
  • DMA控制器可以独立于CPU访问系统总线。它包含几个可以由CPU写入和读取的寄存器。
  • 在低端（嵌入式）计算机中，通常不使用DMA，而让比DMA控制器快得多的CPU直接做所有的工作

• 终端回访
  • 当I/O设备完成了指定给它的工作时，它会导致中断。
  • 该信号由母板上的中断控制器芯片检测。如果没有其他中断挂起，则中断控制器立即处理该中断
  • 为了处理中断，控制器在地址线上加上一个数字，指定哪个设备需要注意，并断言一个中断CPU的信号
  • 中断信号使CPU停止它正在做的事情并开始做其他事情。

• io软件的目标

  • 设备独立
    • 程序可以访问任何I/O设备，而无需事先指定设备（从软盘、硬盘或CD-ROM读取文件）
  • 统一命名
    • 文件或设备的名称、字符串或整数
    • 不取决于哪台计算机（/usr/ast/backup）
  • 错误处理
    • 尽可能靠近硬件处理
  • 同步传输与异步传输（Synchronous vs. asynchronous transfers）
    • 阻止传输与中断驱动
  • 缓存
    • 来自设备的数据不能存储在最终目的地（VOD）
  • 可共享设备与专用设备
    • 磁盘是可共享的，CD-Rom/打印机将不会
    • 操作系统必须能够以避免问题的方式处理共享设备和专用设备

chapter 8

• 安全包含哪些方面
  1. 保密性
  2. 完整性
  3. 可用性
• 对称加密和非对称加密
  1. 对称加密：加密解密共用一密钥，该密钥称为私钥
  2. 非对称加密：公钥加密，私钥解密