期末复习篇

可加载内核模块：不是独立可执行文件，是具有独立功能的程序可以被单独编译，但不能单独运行。运行时被链接到内核的一部分在内核空间运行

Makefile文件：告诉头文件放在哪些地方。定义三个变量：路径的变量（当前的路径），内核源代码所在路径的变量，内核版本号的变量

系统调用

接口的类型

图形接口 给任何人

命令级接口 系统管理员，程序员

程序接口 程序开发者

系统调用定义

操作系统提供给用户程序的一组接口

系统调用分类

1. 进程控制类 对进程（创建，终止，获取设置属性，等待事件）

2. 文件操纵类 对文件（创建删除，打开关闭，读写文件）

3. 进程通信类

系统调用一般涉及CPU状态转换：用户态到内核态

系统调用和API

系统调用：通过中断向内核发请求，实现内核提高的某些服务

API：函数的定义，规定函数功能，与内核无关

从用户态跟踪一个系统调用到内核态

1. 从用户程序中调用fork()

2. 在libc库中把fork()对应的系统调用号“2”放入寄存器eax

3. 通过 int 0x80陷入内核

4. 在中断描述表IDT中查到系统调用的入口"0x80"

5. 进入Linux内核的entry_32(64).S文件，从系统调用表sys_call_table中找到sys_fork的入口地址

6. 将控制权转交给系统调用，执行fork.c中的do_fork代码

7. 执行结束后通过iret或者sysiret返回

8. 最后检查切换回用户空间之前需要完成的任务，如果没有则恢复用户进程的状态，并将控制权交还给用户程序

进程

进程是CPU分配资源的基本单位

从程序到可执行代码

源程序 (汇编成) 汇编程序 (编译成) 目标代码 (链接成) 可执行代码

win下：exe

Linux：ELF

进程控制块（PCB）

管理进程的数据结构，用来记录进程的外部特征，描述进程的运行变化的全过程。

包含的信息

1. 进程标识信息 唯一的标识进程，PID（进程标识符）
2. 处理器现场信息 用于执行中断处理程序前，保存当前执行的处理器现场信息。
   1. 通用寄存器 8到32个寄存器，RISC结构中超过100个寄存器
   2. 指令技术器 存放下一条指令地址
   3. 状态寄存器 程序状态字PSW，如x86中的EFLAGS寄存器
   4. 用户栈指针 存放过程和系统调用参数及地址
3. 进程调度信息
   1. 进程的状态 运行，就绪，阻塞
   2. 优先级 静态优先级和动态优先级
   3. 进程等待的事件 进程阻塞的原因
   4. 其他信息 等待的总时间，执行的总时间
4. 进程控制信息
   1. 程序和数据的地址 程序和数据所在的内存或外存地址
   2. 进程间同步和通信机制 需要的消息队列指针和信号量
   3. 资源清单及使用情况 除CPU外的资源
   4. 家族关系 父子进程关系

PCB的具体结构

task_struct

1. 定义

task_struct 结构体在内核源码中被定义在 include/linux/sched.h 文件中。它是一个非常庞大的结构体，包含了进程的几乎所有信息。

2. 核心字段分类

(1) 进程标识相关

• pid
  • 进程的唯一标识符 (Process ID)。
• tgid
  • 线程组ID，用于线程共享一个进程ID的场景。
• parent
  • 指向父进程的指针。

(2) 进程状态相关

• state
  • 表示进程的当前状态，可能的状态包括：
    • TASK_RUNNING: 正在运行或准备运行。
    • TASK_INTERRUPTIBLE: 可中断的睡眠状态。
    • TASK_UNINTERRUPTIBLE: 不可中断的睡眠状态。
    • TASK_STOPPED: 停止状态。
    • TASK_DEAD: 已退出状态。
• exit_state
  • 保存进程退出时的状态。

(3) 调度相关

• prio
  • 进程的优先级。
• rt_priority
  • 实时优先级。
• sched_class
  • 调度类，定义了不同调度策略（如CFS、实时调度）。
• se和 rt
  • 分别用于表示进程在CFS调度器和实时调度器中的实体。

(4) 内存管理相关

• mm
  • 指向进程的内存描述符（mm_struct）。
  • 包含进程的虚拟地址空间信息。
• active_mm
  • 当前激活的内存描述符，通常在内核线程中使用。

(5) 文件系统相关

• fs

  • 与进程相关的文件系统信息（fs_struct），如根目录和当前工作目录。

• files

  • 指向打开文件表的指针（files_struct），记录进程打开的文件信息。

(6) 信号相关

• signal

  • 与进程相关的信号描述符。

• blocked

  • 当前被阻塞的信号集。

(7) 线程相关

• thread

  • 进程的CPU上下文信息，保存寄存器状态、栈指针等，用于进程切换。

(8) 时间相关

• start_time

  • 进程创建时间。

• utime和 stime

  • 用户态和内核态下的CPU时间。

(9) 资源限制相关

• rlim

  • 资源限制信息（rlimit），如最大文件描述符数、内存使用量等。

(10) 其他

• comm

  • 进程名称，长度为16字节。

• flags

  • 进程的标志位，用于描述进程的一些特性，如是否为内核线程。

进程控制

用户态切换到内核态的情况

CPU状态通过OSW（程序状态字）进行标识 X86的PSW有2位二进制 00系统态，11用户态

1. 用户程序中通过系统调用访问操作系统服务 例如打开一个文件

2. 设备终端 I/O设备操作完成后会触发中断让操作系统介入执行中断处理程序

3. 程序执行异常

内核态切换到用户态

系统调用，中断，异常返回时发生内核态到用户态的切换

也可以通过直接修改PSW切换回用户态

进程控制-原语操作

CPU切换时将现场保存到PCB中

原语操作就是原子操作

类型：

1. 进程创建

   1. 用户登录时，由OS为合法终端创建一个进程

   2. 调度到某个批处理作业时，由作业调度程序创建

   3. 运行程序请求提供服务，由OS创建

   4. 运行中进程因自己的需要，由它自己创建子进程

2. 进程树 操作系统允许进程创建子进程，从而形成树形进程家族

   1. 资源分配严格 子进程仅能分配到父进程拥有的资源

   2. 进程控制灵活 一个进程可以将任务分为独立的多个子任务，由他创建多个子进程，并发完成操作

   3. 层次清晰，关系明确

3. 进程的阻塞

   1. 等待某种操作的晚餐

   2. 新数据尚未到达

   3. 等待新任务的到达

   4. 向系统请求共享资源失败

4. 进程的唤醒

   1. 若事件是等待I/O完成，则由硬件提出中断请求，CPU响应中断，暂停当前进程的执行，转去中断处理。检查有无等待该I/O完成的进程，有，中断处理程序将它唤醒。然后结束中断处理，返回被中断进程或重新调度

   2. 若事件是等待某进程发一个信息，则由发送进程把该等待进程唤醒

5. 进程的挂起与激活

6. 进程的终止

   1. 正常结束

   2. 异常结束

   3. 外界干预（死锁，父进程请求等）

线程

操作系统系统调度的基本单位

进程和线程区别

1. 组成不同，进程的实体是程序，PCB与进程一一对应；线程的实体是函数，TCB与线程一一对应
2. 进程是资源的分配单位，也是独立调度的单位，而线程仅是独立调度的单位
3. 与线程相比，进程的并发度要低
4. 每个进程拥有自己的资源，而线程共享进程的资源，只拥有堆栈和寄存器等少量资源

线程的分类

用户级线程 仅存在于用户空间中，由应用程序通过线程库完成。所有线程的创建，撤销，调度等管理活动。

优点是可以运行在任何支持线程库的操作系统上， 缺点是内核只将处理器分配给进程。同一进程的两个线程不能同时运行在两个处理器上。

内核级线程 所有线程的管理由内核完成的线程。内核维护进程和线程的上下文。

优点是对多处理器，内核可以同时调度同一进程的多个线程，多个线程可以同时运行于多个处理器上，阻塞是在线程一级上完成的。缺点是同一进程的线程切换要进入内核，切换代价较大

线程模型

1. 多对一模型 将多个用户级线程映射到一个内核级线程
2. 一对一模型 将一个用户级线程映射到一个内核级线程
3. 多对多模型 任意数量N的用户线程映射到等于或小于数量N的内核线程的多路复用

进程的创建

fork()

创建的子进程是父进程的完整副本(写时复制)

vfork()

创建的子进程与父进程共享数据段，由vfork()创建的子进程将先于父进程运行

与fork()的区别：fork子进程拷贝父进程的数据段，代码段，vfork子进程与父进程共享数据段

fork父子进程的执行次序不确定，vfork保证子进程先运行

clone()

临界资源

互斥资源，一次只允许一个进程（线程）访问的资源，一旦分配，不能强制剥夺

临界区

在并发执行的进程，访问临界资源必须互斥执行的程序段叫临界区

进程间通信

1. 管道
2. 共享内存
3. 消息队列

处理机调度

对于支持线程的操作系统，操作系统实际调度的是内核线程而非进程

处理机调度模型

高级调度：作业调度 系统根据作业调度算法创建进程，分配资源，该进程进入就绪队列

低级调度：系统根据进程调度算法，选择就绪队列中的某个进程将处理机分配给他，使选中的进程执行

中级调度：不是所有多道OS都需要配置。提高内存利用率和系统吞吐量（负载均衡）

切换进程的过程

1. 保存进程A的CPU现场
2. 修改进程A的PCB（将进程状态改为阻塞态）
3. A进入阻塞队列
4. 挑选准备占用CPU运行的就绪进程B
5. 修改B的PCB（就绪态改为运行态）
6. 恢复进程B的CPU现场

OS采用的剥夺策略

抢占式调度方式

1. 优先权原则
2. 短进程优先原则
3. 时间片原则

非抢占式调度方式

周转时间

作业周转时间：完成时间-提交时间

平均作业周转时间：（每个作业的周转时间的和）/ n

调度算法

先来先服务FCFS 利于长作业，利于CPU繁忙的进程，不利于I/O繁忙的进程

短进程优先 对长进程不利

优先权调度

优先权有两种：静态优先权和动态优先权

高响应比优先调度 响应比R（优先权）=（等待时间+要求服务时间）/要求服务时间

时间片轮转 时间片过长：退化成先来先服务，过短：进程等待时间变长，CPU现场切换次数增加。

多级反馈队列

1. 设置多个就绪队列，每个队列优先级不同，时间片不同。队列1优先级最高，其他逐级降低，优先级越低，时间片越长。

2. 新进程就绪后，先投入队列1的末尾，按FCFS调度。若一个时间片未能执行完，投入到队列2的末尾，降低到最后的队列，按照时间片轮转调度直到完成

3. 进程由于等待事件放弃CPU，进入等待队列，一旦等待事件发生，则回到原来的就绪队列

4. 仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。执行时如果有新进程进入较高优先级队列，则抢先执行新进程，并把被抢占的投入原队列的末尾

避免死锁

银行家算法

1. 可用资源向量 描述系统当前可用的空闲资源量 Available[j]=k表示系统中第j类资源空闲数为k个
2. 最大需求矩阵 Max[n,m]进程对资源的最大需求量 Max[i,j]=k表示进程i获得j类资源的数目为k个
3. 分配矩阵Allocation[n,m] 描述进程已分配的资源量 Allocation[i,j]=k表示进程i获得j类资源的数目为k个
4. 需求矩阵Need[n,m]描述了进程还需要的资源量Need[i,j]=k表示进程i还需要j类资源k个

内存

内存分配方式

固定分区分配

动态分区分配

1. 首次适配
2. 循环首次适配算法 分配时不再从表头找，从上次找到空闲区的下一个空闲开始找
3. 最佳适配 将所有空闲区按大小排序后，以递增顺序形成一个空白链。
4. 最差适配 从大到小，每次查找时只看第一个空闲分区是否满足
5. 快速适配

可变分区回收

上邻接 回收的分区与低地址空闲分区邻接，需合并成一个分区

下邻接 回收分区与高地址空闲分区邻接

上下均邻接 既与高地址又与低地址空闲分区相邻接，三者合并

上下均不邻接 分区表中增加一个新回收的分区信息

分页存储管理

页号 ： 页号=虚地址/页大小

位移量：位移量=虚地址 mod 页大小

快表

一组能够按照内容访问的相连快速存储器，又称“联想寄存器”，用它保存最近频繁访问的页表项。快表是通过硬件电路一次比对，而且页表项不需要连续存放，而是按照内容查找

访问内存有效时间：

EAT = 2t +T-t*a T为查找快表所需的时间，a为快表命中率，t为访问一次内存所需的时间

虚拟存储管理

虚拟存储器

定义 具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储系统。逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本又接近外存

请求分页存储

请求调入：

进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态请求调入其他页面。

置换功能

当内存空间已满，而又需要装入新的页面时，就要根据某种算法置换出某个页面到外存，以便腾出内存空间装入新页面

页面置换算法

最佳置换算法 在未来最长时间内不再被访问的页面

先进先出置换算法 淘汰最先进入内存的页面

最近未使用（LRU）

时钟算法

I/O控制方式

程序直接控制

中断控制方式

直接存储器访问（DMA）减少CPU对高速外设的干预

I/O通道控制方式 比DMA需要的CPU干预更少

I/O系统接口

块设备接口 以数据块为单位传输，磁盘设备的I/O常采用DMA方式，常用write和read函数

流设备接口 以字符为单位 传输速率较低，不可寻址，常采用中断驱动方式，常用get和put函数

网络通信接口 OS提供相应的网络软件和网络通信接口 send/receive函数

块设备：以数据块为单位来组织和传送数据信息的设备。用于存储信息，有磁盘和磁带等。典型块设备是磁盘，基本特征：传输速率高，可寻址，磁盘设备的io采用DMA方式

字符设备 以单个字符为单位传输，用于数据的输入和输出。有交互式终端，打印机等。传输速率低，不可寻址，字符设备的io采用中断驱动方式

中断具体处理步骤

1. 唤醒被阻塞的驱动（程序）进程
2. 保护被中断进程的CPU环境（保存在栈中）
3. 转入相应的设备中断处理程序
4. 中断处理

假脱机（SPOOLing）

将独占设备改造成共享设备的技术

文件控制块FCB

存储的信息

1. 基本信息类 文件名，文件物理地址，文件逻辑结构，文件物理结构 主要保存了文件逻辑和物理的存储信息
2. 存取控制信息类 文件主，核准用户，一般用户的存取权限 保证文件安全性
3. 使用信息类 文件的创建，修改日期及时间，当前使用信息

inode

文件名。索引节点编号

FCB与唯一的inode节点对应

I/O层次结构

1. 用户进程 调用I/O操作的程序，例如cp
2. 文件系统 对文件的逻辑管理 路径解析，文件打开，读写等
3. 设备驱动程序 将逻辑请求转换为设备操作，如磁盘块读取
4. 设备控制器 直接与设备硬件交互
5. 设备 磁盘，显示器等具体硬件

缺页中断的过程

1. CPU访问内存

CPU向内存请求一个虚拟地址的数据。

硬件（通常是MMU，Memory Management Unit）将虚拟地址与页表进行对比，检查页面是否在内存中。

2. 页表检查

如果页表中发现页面不在内存（页面标记为“无效”或未加载），触发缺页中断。

3. 中断处理

CPU暂停当前程序的执行，保存上下文，跳转到操作系统内核的缺页中断处理程序。

4. 操作系统处理缺页

1. 查找页面
   1. 操作系统根据页表或虚拟内存的元信息定位需要加载的页面（通常在磁盘上）。
2. 分配内存页框
   1. 检查内存是否有空闲的页框：
      1. 如果有空闲页框：直接分配。
      2. 如果没有空闲页框：使用页面替换算法（如LRU、FIFO等）将某些页面置换出去。
3. 写回和清空（如必要）
4. 如果被置换的页面被修改过（脏页），将其写回磁盘。
5. 清空并重新初始化页框。

5. 加载页面

从磁盘或其他存储设备将所需页面加载到内存中的页框。

6. 更新页表

操作系统更新页表：

将页面标记为“有效”。

更新页面与页框的映射关系。

设置访问权限（如只读、可写等）。

7. 恢复程序执行

操作系统返回到缺页中断的指令，重新执行触发中断的指令。

程序继续执行，用户无感知页面调度过程。