Operation System Notes

Posted on Edited on In

操作系统

2024.4.21

内核

操作系统的核心就是内核，内核作为应用连接硬件设备的桥梁，应用程序只需要与内核进行交互即可，不用关心硬件细节

  • 内核的基本能力：
    • 进程调度能力，管理进程/线程
    • 内存管理能力，管理内存，决定内存分配与回收
    • 管理硬件设备，为进程和设备之间提供硬件通信能力
    • 提供系统调用，如果程序要用一些系统功能，可以通过内核为中介来使用
  • 操作系统的内存可以分为两部分：
    • 内核空间：这个内存空间只有内核能够访问
    • 用户空间：专门给应用程序使用
    • 用户空间的代码只能访问一个局部的内存空间，而内核空间的代码可以访问所有内存空间。当程序使用用户空间时，则该程序在用户态执行，当程序使内核空间时，则在内核态执行
    • 应用程序如果要进入内核空间，就需要通过系统调用

Linux内核

  • 包括下面几个方面
    • MultiTask，多任务
    • SMP，对称多处理
    • ELF，可执行文件格式
    • Monolithic Kernel，宏内核：系统内核的所有模块，比如进程调度、内存管理、文件系统、设备驱动等，都运行在内核（也有微内核，混合类型内核）

Windows内核（Windows NT）

  • 是混合类型内核，在内核中有一个最小版本的内核MicroKernel
  • 可执行文件类型是PE，称为可移植执行文件，常见拓展名有.exe, .dll, .sys

硬件结构

  • 冯诺依曼计算机结构：Control unit, Memory, Arithmetice logic unit, input, output
  • 总线Bus: 控制总线（中断，复位），数据总线（读写内存数据），地址总线（传送操作的内存地址）
  • 寄存器种类：通用寄存器，程序寄存器，指令寄存器
  • Pipeline CPU: 把一个任务拆分成多个小任务，每个阶段可以独立工作，实现指令的并行处理。通常分为：取指令(fetch instruction), 指令解码(instruction decode), 执行(execution), 访存(memory access), 写回(write back)

存储结构

  • 存储器的结构（速度从快到慢）
    • 寄存器Register
    • CPU Cache(static random-access memory): L1 Cache(最快，分为指令缓存和数据缓存), L2 Cache, L3 Cache
    • 内存Memory(dynamic random access memory)
    • 硬盘HDD/SSD
  • 64位CPU中寄存器一般可以存储64位（8字节）

内存管理

  • 内存的使用分为系统空间：存放操作系统本身以及相关系统数据，用户空间，存放用户程序和数据
  • 存储管理要有内存空间管理、地址转换、内存扩充、内存共享和保护等功能
    • 内存空间管理：负责内存的分配与回收，内存分配有静态和动态两种
    • 地址转换：用户程序编译后每个目标模块都以0为基地址进行编址，称为相对地址或逻辑地址。相对应有绝对地址或物理地址。重定位：内存分配确定后，将逻辑地址转换为物理地址
  • 虚拟存储器：逻辑容量由内存和外存之和决定，运行速度接近实际内存速度
  • 进行分段和分页的作用：
    • 逻辑隔离：让不同的功能模块和数据类型可以被单独的保护和管理，提高安全性
    • 内存保护：可以将段和页设置为可读，不可读等状态，提高系统稳定性，防止错误访问和修改
    • 虚拟内存
    • 内存共享
    • 内存管理
  • 分页存储管理(Page)：
    • 将进程的逻辑地址空间划分为若干个大小相等的页，将内存空间划分为与页面大小相同的存储块
    • 地址结构为： 页号 | 页内位移
    • 快表（TLB），如果在快表中命中，则只访问一次内存，否则访问两次
    • 纯分页系统与请求式分页系统
    • 缺页中断可能会带来系统“抖动”（thrashing）现象
    • 可以提高内存利用率
  • 分段存储管理(Segment)：
    • 将程序的地址空间分为不相等的段，各个段的长度可以不同
    • 地址结构： 段号 | 段内地址
    • 快表（TLB），如果在快表中命中，则只访问一次内存，否则访问两次
    • 优点：允许段长动态增长，分段式存储管理便于对具有完整逻辑功能的信息段进行共享，便于实现动态链接
  • 分页和分段的比较：
    • 页是信息的物理单位，段是信息的逻辑单位，分段可以更好地满足用户需要。页对用户不可见，段对用户是可见的
    • 分页式管理的作业地址空间是一维的，而分段式是二维的
    • 页的程度由系统确定，等长的；段的长度是不固定的
    • 分页（单级页表）和分段访问一个逻辑地址都需要两次访问内存
  • 优缺点比较：
    • 分页：空间利用率高，不会产生外部碎片，产生内部碎片
    • 分段：产生外部碎片，可以按照逻辑关系实现信息的共享和保护
  • 段页式：
    • 将内存分为大小相同的内存块页
    • 将作业或进行分段，段内分页
    • 地址结构： 段号 | 段内页号 | 页内地址
    • 获得一条指令，需要访问三次内存：访问段表，访问页表，取出指令或数据

页面置换算法

  • 先进先出FIFO：即使被访问，也不影响，淘汰最老的页面。Belady现象(随着给进程分配的页面数增加，却页的情况反而增多)
  • 最近最少使用页面置换算法LRU：淘汰最长时间没被访问的页面，比较适合频繁访问的场景，因为最近访问过的页面很有可能再次访问。性能相比于FIFO较优，但是由于实现的时候需要维护链表，开销较大，实际比较少使用
  • 时钟算法：Clock算法，基于一个环形列表或者循环队列。使用一个时钟指针在环形的数据结构上遍历。当需要进行页面置换的时候，从时钟指针位置开始遍历，当访问到的页面访问位为0，进行置换，修改为1（当前访问页面最久未访问）；当访问到页面访问位置为1，表示当前页面最近被访问过，修改为0，继续进行遍历
  • OPT算法：只是一个理想的算法，通常无法实现
  • 例题：计算系统开销，Clock算法，每个时间片长度250ms，CPU切换时间12ms。
    则每个进程再调度中的时间是250+12=262ms
    • 系统开销比例公式
      $$
      开销比例 = \frac{切换时间}{切换时间+进程时间片}
      $$
      故答案为$\frac{12}{262} = 4.58%$

基本知识

用户态，核心态

  • 是操作系统中两种不同的执⾏模式，⽤于控制进程
    或程序对计算机硬件资源的访问权限和操作范围
  • 用户态User mode:
    在用户态下，进程或程序只能访问受限的资源和执行受限的指令集，不能直接访问操作系统的核心部分，也不能直接访问硬件资源，用户态下的 CPU 不允许独占，也就是说 CPU 能够被其他程序获取。
  • 核心态Kernal mode:
    核心态是操作系统的特权级别，允许进程或程序执行特权指令和访问操作系统的核心部分。在核心态下，进程可以直接访问硬件资源，执行系统调用，管理内存、文件系统等操作。处于内核态的 CPU 可以从一个程序切换到另外一个程序，并且占用 CPU 不会发生抢占情况，一般处于特权级 0 的状态我们称之为内核态。

进程

进程的所有状态如下，创建状态（new），结束状态（exit），运行状态（running），就绪状态（ready），阻塞状态（blocked正在等待某一事件发生而暂时停止运行），挂起状态（suspend描述进程没有占用实际的物理内存空间的情况）

  • 进程控制块（process control block，PCB）可以用来描述一个进程，PCB是进程存在的唯一标识，包括
    • 进程描述信息
    • 进程控制和管理信息
    • 资源分配清单
    • CPU相关信息
  • 把PCB通过链表连接，可以构成就绪队列或阻塞队列

线程

  • 有三种线程实现方式：
    • 用户线程(User Thread):在用户空间实现的线程，不是由内核管理的线程，是由用户态的线程库来完成线程的管理
    • 内核线程(Kernel Thread):在内核中实现的线程，是由内核管理的线程。相当于也是由操作系统进行管理
    • 轻量级进程(LightWeight Process):在内核中来支持用户线程

进程（Process）与线程（Thread）

  • 进程 是运行时程序的封装，是系统进行资源调度和分配的基本单位，实现了操作系统的并发
    进程间通信可以使用：管道（pipeline）、系统IPC（消息队列、信号量Semaphore、信号、共享内存）以及套接字socket
  • 线程 是进程的子任务，是CPU调度和分派的基本单位，用于保证程序的实时性，实现进程内部的并发；线程是操作系统可识别的最小执行和调度单位。每个线程都独占一个虚拟处理器：独自的寄存器组，指令计数器和处理器状态。每个线程共享同一地址空间，共享同一块内存，打开的文件队列和其他内核资源。
    线程间通信的方式有临界区，互斥量Synchronized/Lock，信号量semaphore，事件（信号）wait/notify
  • 进程与线程的区别：
    • 进程是资源分配的最小单位，线程是CPU调度的最小单位
    • 进程在执行过程中拥有独立的内存单元，而多个线程共享进程的内存
    • 一个线程只能属于一个进程，而一个进程可以有多个线程；
    • 系统开销：进程切换的开销也远大于线程切换的开销
  • 资源开销:
    • 进程:由于每个进程都有独立的内存空间，创建和销毁进程的开销较大。进程间切换需要保存和恢复整个进程的状态，因此上下文切换的开销较高。
    • 线程:线程共享相同的内存空间，创建和销毁线程的开销较小。线程间切换只需要保存和恢复少量的线程上下文，因此上下文切换的开销较小。
  • 通信与同步:
    • 进程:由于进程间相互隔离，进程之间的通信需要使用一些特殊机制，如管道、消息队列、共享内存等。
    • 线程:由于线程共享相同的内存空间，它们之间可以直接访问共享数据，线程间通信更加方便。
  • 安全性:
    • 进程:由于进程间相互隔离，一个进程的崩溃不会直接影响其他进程的稳定性
    • 线程:由于线程共享相同的内存空间，一个线程的错误可能会影响整个进程的稳定性。
  • 进程通信
    • 管道pipeline：（分为匿名管道和命名管道）半双工，只能在有父子关系进程间使用。只能传输无格式的字节流
    • 信号量Semaphore：类似计数器，用来控制多个进程对共享资源的访问。主要作为进程间以及一个进程中不同线程的同步手段，可以使用P操作和V操作
    • 信号：和信号量完全不一样！是进程通信中唯一的异步通信手段。可以在任何时候发送信号给某个进程，迫使进程进行信号处理程序
    • 消息队列：本质是内存中存放消息的链表，存放在内核中。可能需要频繁的交换数据。很方便但是不适合大数据的传输，同时会有拷贝开销
    • 共享内存Shared Memory：最快的进程通信方式。由一个进程映射一段能被其他进程访问的内存，多个进程都可以访问这段内存。可以与信号量配合使用，实现同步与通信
    • Socket：支持TCP/IP，用于客户端与服务器之间的通信，可以跨网络与不同主机上的进程之间通信，可以实现TCP或UDP的通信

进程调度算法

  • 评价指标
    • CPU利用率CPU Utilization：调度程序应始终保持CPU处于繁忙状态运行，以提高CPU的利用率。公式 = 忙碌时间 / 总时间
    • 系统吞吐率System Throughput：系统吞吐率是指在一定时间内完成的进程数量。调度程序应尽量选择能够快速完成的进程，以提高系统的吞吐率。公式 = 完成作业数量 / 总时间
    • 周转时间Turnaround Time：指一个进程从创建到完成的总时间。周转时间 = 完成时间 - 创建时间
    • 平均周转时间Average Turnaround Time = 各作业周转时间之和 / 作业数
    • 带权周转时间Weighted Turnaround Time = 作业周转时间 / 作业实际运行时间
    • 平均带权周转时间 = 各作业带权周转时间之和 / 作业数
    • 等待时间Waiting Time：等待时间并不是所谓的阻塞时间，而是在就绪队列中等待被执行的时间。公式 = 周转时间 - 运行时间 或者作业开始执行时间 - 到达时间
    • 平均等待时间 Average Waiting Time：各作业等待时间之和 / 作业数
    • 响应时间Response Time：指用户发出请求后系统作出响应的时间。用户与其交互这之间所产生的消耗时间越少，响应越好
  • 两大种调度算法
    • 非抢占式调度算法：所有进程都排队等待，只有前面的进程都执行完了或者自己主动让出CPU，才可以轮到后面的进程执行。如FCFS(First Come First Serve), SJF(Shortest Job First)
    • 抢占式调度算法：即时间片机制，每个进程都只占用CPU的一个时间片操作，执行完了就必须让出CPU使用权限给下一个进程使用。如Round Robin(轮转调度)，SRTF(Shortest Remaining Time First最短剩余时间优先)，优先级调度(Priority Scheduling)
    • FCFS：最简单，先来先服务，类似队列FIFO，先进先出。对长作业有利，适用于 CPU 繁忙型作业的系统，而不适用于I/O繁忙型作业的系统
    • SJF：根据进程执行时间长短进行排序，作业时间短的排在前面（分为抢占式和非抢占式）
    • HRRN（Highest Response Ratio Next）：响应比 = （等待时间 + 要求服务时间）/ 要求服务时间。非抢占式算法。相应比会不断更新的，响应比越高越先执行
    • Round Robin: 将CPU时间划分为固定大小的时间片，每个进程占用一个时间片进行执行，时间片结束后若未执行完，则回到就绪队列末尾，等待下一轮调度。若在时间片内执行完，则直接交出CPU权限让下一个进程执行。时间片长度一般在20ms-50ms
    • SRTF：基于SJF和抢占式调度算法的改进版本。根据进程剩余执行时间进行排序，让剩余时间最少的进程先执行
    • 优先级调度：可以分为非抢占式和抢占式。每一个进程都有优先级，相同优先级则FCFS。在抢占式优先级调度中，如果高优先级的来了，当前执行的进程会被中断，切换高优先级进程执行
    • 多级反馈队列调度（Priority Scheduling, Multilevel Feedback Queue）：结合优先级调度和Round Robin, 设置多个队列，时间片从小到大，优先级从高到低
  • 系统开销：调度过程中，CPU切换进程也会消耗时间。系统开销比例 = CPU切换时间 / （进程执行总时间+CPU切换时间）

进程同步与互斥

  • 同步：多个并发执行的进程，协调并管理他们的执行顺序，确保他们按照一定的顺序或者时间执行
  • 互斥：在某一个时刻只允许一个进程访问某个共享资源。当一个进程在使用共享资源时，其他进程不能使用
  • 常见方法：
    • 信号量，PV操作Semaphore。信号量可以表示系统某种资源的数量或者状态，PV操作可以增减信号量
    • 临界区Critical Section。容易引发互斥问题的代码段。进程进入前获取锁，退出后释放锁
    • 互斥锁Mutex。共享资源关联一个互斥锁，当进程访问的时候获取互斥锁，使用完后释放
    • 条件变量Conditional Variable。用于在进程之间传递消息，以便在特定条件下等待或唤醒，通常与互斥锁一起使用，保证在正确的时间执行（类似Flag）

线程的同步

  • 同步是指在多线程编程中，为了保证线程的互不干扰，有以下线程同步的方法
    • 互斥锁
    • 条件变量
    • 读写锁：多个读，一个写
    • 信号量：semaphore

虚拟内存

  • 在进程创建加载中，会分配一个连续虚拟地址空间，通过映射与实际地址空间对应
  • 虚拟内存：让程序拥有超过系统物理内存大小的可用内存空间。虚拟内存为每一个进程提供了一个一致的、私有的地址空间，它让每个进程产生了一种自己在独享储存的错觉（每个内存拥有一片连续完整的内存空间），定义了一个连续的虚拟地址空间，并把内存扩展到硬盘空间

死锁/锁

  • 死锁是指两个或多个进程在争夺系统资源时，由于互相等待对方释放资源而无法继续执行的状态。
  • 死锁只有同时满足以下四个条件才会发生:
    • 互斥条件:一个进程占用了某个资源时，其他进程无法同时占用该资源，
    • 请求保持条件:一个线程因为请求资源而阻塞的时候，不会释放自己的资源。
    • 不可剥夺条件:资源不能被强制性地从一个进程中剥夺，只能由持有者自愿释放。
    • 环路等待条件:多个进程之间形成一个循环等待资源的链，每个进程都在等待下一个进程所占有的资源。
  • 只需要破坏上面一个条件就可以破坏死锁。
    • 破坏请求与保持条件:一次性申请所有的资源
    • 破坏不可剥夺条件:占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源。
    • 破坏循环等待条件:靠按序申请资源来预防。让所有进程按照相同的顺序请求资源，释放资源则反序释放。

中断和异常

  • 是两种不同的事件，都会导致CPU暂停当前的程序执行，转而去执行一个特定处理程序
  • 中断由外部设备产生，如鼠标键盘，可以在任何时候产生，与当前执行指令无关。
  • 异常由CPU内部产生，只会在执行某些指令时发生，与当前执行指令有关，如除法除0，访问数组越界
  • 中断可以被屏蔽或禁止，而异常不行，CPU必须马上响应并处理，保证系统的稳定性和程序的正常执行
  • 中断的作用：
    • 外设异步的通知CPU
    • CPU之间可以发送消息
    • 处理CPU异常：当CPU执行指令遇到了异常，可以向自己发送中断信号
    • 实现系统调用
  • 中断信号来源：
    • 外设：（异步的）一般也叫硬件中断，可以分为可屏蔽中断和不可屏蔽中断
    • CPU：指一个CPU向另一个CPU发送中断
    • CPU异常：（同步的）也叫做软件中断。可分为3类
      • 陷阱trap：不需要修复，处理中断后继续执行
      • 故障default：需要修复，可能可以修复，处理后重新执行
      • 中止abort：需要修复但无法修复，处理后崩溃

锁

  • 自旋锁/忙等待锁（Spinlock）： 自旋锁是一种在获取锁失败时循环检查锁状态的锁机制，不会立即将线程置于睡眠状态。自旋锁适用于临界区代码执行时间短暂的情况，可以减少线程上下文切换的开销。
  • 互斥锁（Mutex）： 互斥锁用于保护临界区代码，只允许一个线程访问共享资源，其他线程必须等待该线程释放锁。互斥锁适用于读写操作均很频繁且时间较短的场景。
  • 其他的锁都是基于自旋锁和互斥锁的
  • 读写锁（Reader-Writer Lock）： 读写锁允许多个线程同时读取共享资源，只允许一个线程写操作。读写锁可以提高并发性，适用于读操作远远多于写操作的场景。
  • 递归锁（Recursive Lock）： 递归锁允许同一个线程多次获取锁，但每次获取锁都需要对应的释放锁操作。递归锁适用于同一个线程需要递归调用临界区代码的场景。
  • 条件变量锁（Condition Variable）： 条件变量锁允许线程在某个条件满足时进入睡眠状态，等待其他线程唤醒。条件变量锁通常与互斥锁一起使用，用于实现线程之间的同步。
  • 乐观锁：不管，先修改共享资源再说，如果出现同时修改的情况，再放弃修改操作
  • 悲观锁：认为发生多线程同时修改共享资源的概率高，所以访问共享资源要先上锁

信号量

互斥

  • 可以通过原子操作（P操作，V操作）来完成互斥操作，假设资源数量是sem
    • P操作：将sem减一，相减后，如果sem < 0，则进程/线程进入阻塞等待，否则继续
    • V操作：将sem加一，相加后，如果sem <= 0，则唤醒一个等待中的进程/线程
    • P操作用在进入临界区之前，而V操作用在离开临界区后
  • 只需要在进入临界区之前使用P操作，在离开临界区时候使用V操作，就可以保证互斥了

同步

  • 可以使用信号量实现事件同步。同步的方式是设置一个信号量初值为0

磁盘调度算法

假设有下面一个请求序列，每个数字代表磁道的位置:
98，183，37，122，14，124，65，67
初始磁头当前的位置是在第53磁道。
常见的磁盘调度算法有:

  • 先来先服务算法(FIFO): 按照请求的顺序移动磁头进行寻道，最简单
  • 最短寻道时间优先算法(Shortest Seek First): 优先选择从当前磁头位置所需寻道时间最短的请求。但是这个算法可能存在饥饿问题，如果不停地有请求到来，磁头可能永远不会去访问那些离的很远的地方
  • 扫描算法(Scan)：磁头在一个方向上移动，访问所有未完成的请求直到到达该方向上最后的磁道，然后调换方向。问题是中间的磁道相比两边的磁道被响应的概率大，各个磁道响应频率存在差异
  • 循环扫描算法(Circular Scan, CSCAN): 规定磁头只在一个方向上进行扫描，当扫描到最后的磁道时候，迅速复位并重新扫描，返回途中不处理请求，只响应一个方向上的请求。相比于Scan算法响应频率比较平均
  • LOOK与C-LOOK算法：Scan算法的优化版是LOOK算法，Circular Scan算法的优化版是C-LOOK算法。这两个算法基本思想都是当磁头移动到最远处的请求后，直接返回（或者是复位）