操作系统笔记

by

https://www.bilibili.com/video/BV1CP4y1k7i8/?spm_id_from=333.337.search-card.all.click&vd_source=78951f3f7dcd752bebcfd9734a584537

并发：一段时间内可以同时执行多个程序

并行：一个时刻时可以同时执行多个程序

操作系统的虚拟化技术：CPU的虚拟（时分复用）和磁盘的虚拟（空分复用）

分时操作系统：允许多用户同时操作系统，微观来看是时间切片（CPU的虚拟）

实时操作系统：分时操作系统没有重要性的概念，实时操作系统会对高优先级的程序实时响应

用户空间与内核空间：

所谓用户态与内核态的切换指的是：cpu执行的是用户空间的程序指令和内核空间的程序指令间的切换，例如我开发出一个程序，这个程序生成的指令都是用户空间的指令，如果程序需要调用文件资源，就会切换到内核空间的文件管理器指令，本质上是切换到了另一个程序，由于这个程序是内核空间的，因此这里需要一次用户态与内核态的切换。

用户态切换到内核态只能通过中断实现

为什么需要中断机制？

提高并发情况下CPU的利用率，例如某程序执行io时，可以中断切换到其他程序

外中断与内中断：外部设备引发的中断为外中断，例如敲击键盘。而内中断是指令执行过程中自己发出的，例如程序需要读取文件时会发送一个中断（陷入指令）切换到内核态的文件管理器程序，或者程序出现异常情况等。

中断处理流程：

  1. 保存当前上下文：保存当前执行的寄存器中的内容，并找到中断程序地址
  2. 执行中断程序
  3. 恢复原始上下文

什么是原语：一小段程序，由多条指令组合在一起，执行过程中不能被中断，就可以理解为一个函数或指令

高内聚低耦合：

  1. 高内聚：模块内的代码高度相关
  2. 低耦合：模块间的关系独立性好

进程管理

进程是程序一次执行过程的实体，是系统进行资源分配的最小单位

线程（轻量级进程）：必须存在于进程中，是操作系统运算调度的最小单位

为什么引入线程？

为了提高OS的并发性

注意：进程中多个线程共享进程资源，线程并不拥有资源，只有资源的使用权，如此一来线程的切换开销比进程小很多

进程是如何运行的

进程状态

三种基本状态：就绪（可以运行，等待CPU执行时间片）、执行、阻塞（等待IO操作、同步操作等完成）

另外还有创建和终止状态，创建完成后就会进入就绪状态，执行完成后或者出现异常退出就会进入终止状态

进程控制

OS通过原语操作实现进程控制（创建、撤销、挂起、阻塞、唤醒、切换），原语是由若干条指令组成的原子操作。可以理解为一个事务函数

例如，要将执行状态的进程转换为阻塞状态，则可以使用block原语，由阻塞转换到就绪使用wakeup原语

为了系统和用户观察分析进程，或者暂时不需要使用某进程，就可以使用suspend原语将进程挂起。例如，edge浏览器中，每次开启一个新的tab都会创建一个进程，假如某个tab长时间没打开，系统就会将该tab的进程挂起

与挂起相对的就是激活

只有创建、就绪、阻塞这三个状态才能被挂起，执行和终止状态不行。

挂起状态和另五种状态的不同在于，挂起状态会将进程所占的内存转移到外存（磁盘）上去，所以它不属于进程运行的状态（进程运行必须在内存）

进程调度

只有进程数远远大于内核数，才会出现进程调度。进程调度的目的是减少cpu空闲时间

调度方式：

  1. 抢占式调度：立即暂停当前进程，将cpu分配给其他进程，这种情况一般有 出现优先权更高的进程、时间片到了、有些进程所需时间很短，可能会先让它执行
  2. 非抢占式调度：等待当前进程完成或阻塞才执行

调度过程：

  1. 保存当前进程的context
  2. 切换进程
  3. 恢复原进程

调度算法：

  1. 先来先服务：就绪队列中，先进来的先分配cpu。有利于CPU繁忙进程，不利于io繁忙进程
  2. 短作业优先：先估算各进程所需时间，选择时间短的进程先执行。周转时间短，但估计可能不准确，长时间进程长时间得不到执行
  3. 高响应比优先：（等待时间+预估耗时）/预估耗时，值越大优先级越高
  4. 优先级调度：可以手动或自动设置调度优先级，低优先级可能长时间得不到执行
  5. *时间片轮转调度：给就绪队列中的每个进程分配一个时间片，时间片到了就执行下一个进程的时间片，由时钟中断确定时间片是不是到了。本质上仍然需要排队。因此时间片设置多长就很重要。
  6. *多级反馈队列调度：结合了上面 1、2、3、5 的优点，解释如下：

多级反馈队列调度：

初始化多个就绪队列，每个队列的优先级从高到低，每个队列中进程分配的时间片长度由短到长。新创建的进程都会放在优先级最高的队列中。cpu每次都从不为空的最高优先队列中pop出队顶进程，执行当前队列对应的时间片后将其放到下一级的就绪队列队尾。

如此一来有几个好处：

  1. 所有的进程都会被快速执行一次，不存在长时间得不到执行
  2. 也符合先到先服务原则，更公平，响应速度更快
  3. 耗时较长的进程优先级会逐渐降低，耗时较短的进程会更优先完成
  4. 也满足一定的实时性要求，一般来说，有实时性要求的作业大部分都是短作业，这个算法对短作业的优先级较高

进程协作

进程通信
  1. 共享空间：由操作系统提供一块公共的内存区域（提供一个队列数据结构或直接提供一块内存）。由于所有进程都可见，可能不安全
  2. 消息传递：每个进程维护一个消息缓冲队列，其他进程给它发消息就能放到这个队列中
  3. 管道通信：类似共享空间的方式，给两个进程之间创建一个管道（固定大小的缓冲区），不同点在于这个管道只能单向读写，并且读写过程互斥。若要双向读写则需要创建两个管道。
进程同步

互斥资源访问过程

  1. 申明访问：加锁，其他要访问的进程进入阻塞队列，原则上，进入阻塞队列的进程应该让出cpu的执行权
  2. 访问资源
  3. 释放锁，并唤醒其他阻塞进程
软件如何实现两个进程互斥访问共享资源（锁设计）？
  1. 单标志法：共享资源维护一个允许访问的进程id，只有等于该id的进程才能访问，一个进程访问后将该id修改为另一个进程id，但这种方法局限性非常严重，两个进程必须交替访问才行
  2. 双标志法：共享资源维护两个标识分别表示两个进程id是否正在访问资源。可能出现第一个进程判断第二个进程没访问后，还没来得及修改访问标记，第二个进程就开始判断第一个进程的访问标识了，如果先修改标识再检查，可能出现死锁
  3. 皮特森算法：同时使用单双标志法，共享资源维护一个是否正在访问资源的列表，和一个允许访问资源的进程id，当一个进程要访问该资源时，先将该进程id标记为正在访问，然后将允许访问的进程id设置为另一个进程，下一步使用while循环不停检测另一个进程是否正在访问以及允许访问的进程id是否为另一个进程的id，如果是，则忙循环，否则就执行访问共享资源代码，以下为伪代码：
# 皮特森算法伪代码

# 共享进程维护的两个变量
visiting = {进程1: False, 进程2: False}
competitor = 进程1


# 进程1 访问的流程，进程2同理
visiting[进程1] = True
competitor = 进程2
# 忙循环
while visiting[进程2] and competitor == 进程2:
    continue
visite_res()
visiting[进程1] = False

# 这样不会出现死锁，但会出现忙循环，如果忙循环时间过长则对cpu是一种浪费
硬件实现互斥操作：

注：以下三种方法都是硬件方式实现，看起来可能步骤多，但实际很高效

  1. 关/开中断：多进程访问同一资源本质上还是因为在某个小的时间段，多个进程获取到了cpu的执行权限它才可以访问，而获取执行权限的前提就是有中断信号，而cpu提供了 关中断 指令来禁止后面执行过程发生中断，反之可以使用开中断。故在资源访问前后分别加上 关、开中断 指令即可实现独享资源。但仅局限于单核处理器
  2. Test-And-Set（TS指令）：见下述伪代码
  3. Swap指令：类似TS指令功能，都是读取当前锁状态并执行忙等待的操作
# Test-And-Set 伪代码
# 该方法为原子操作
bool TestAndSet(bool lock):
    if lock:
        return True
    else:
        lock = True
        return False

# 以下为访问共享资源流程
# 自旋等锁
while TestAndSet(lock):
    continue
visite_res()
lock = False
信号量实现互斥访问共享资源（多进程访问多个共享资源）
class Semaphore:
    res_num  # 资源数量，所谓的信号量，指的就是它
    blocked_process # 阻塞队列

# 原语，判断是否可以访问共享资源，如果能访问，就直接访问，不能访问就加入阻塞队列等待唤醒
def wait():
    res_num -= 1
    if res_num < 0:
        blocked_process.append(current_process)  # 将当前进程加入阻塞队列并阻塞

# 原语，资源访问结束后释放资源并唤醒阻塞队列首部进程
def signal():
    res_nums += 1
    if res_nums >= 0:
        wakeup(blocked_process.pop(0))


# 资源访问流程
...
wait()  # 加入阻塞队列和忙等效果相同，进程（线程）都会在这里暂停等待
visite_res()
signal()
...

上述代码使用两个变量（res_num，blocked_process）实现信号量控制，为了便于理解，我将其修改为以下更简单的方式便于理解：

# 等待队列，队列中如果有元素，则队列的首元素表示正在访问资源的进程，其它进程处于阻塞被唤醒状态
wait_queue = []
res_num  # 资源数量，对于单个资源来说，它等于1，效果就是排它锁

def wait():
    wait_queue.append(current_process)
    if len(wait_queue) > res_num:
        block(current_process)

def signal():
    wait_queue.pop(0)
    if len(wait_queue) > res_num-1:
        wakeup(wait_queue.pop(0))
管程

多进程在访问共享资源时，有上述三种方法可以实现互斥访问，为了便于操作，这些东西可以统一抽取出来单独封装成一个共享资源管理器的对象，称之为管程。管程可以看作是对共享资源以及互斥操作的封装，当进程要访问共享资源时，它可以直接调用管程提供的访问方法，不用自己去实现互斥细节。在java中，每个类也都算是一个共享资源，所以每个类都会绑定一个管程对象。

死锁

多进程竞争资源可能造成所有进程都发生阻塞的现象，不同于饥饿，饥饿只是等待时间过长，仍然能获取cpu执行权，而死锁则是完全不会执行任何进程

必要条件（同时满足这4个条件就会发生死锁）：

  1. 需要互斥访问
  2. 访问共享资源的进程不会被强制剥夺访问权限，只能自行释放锁
  3. 访问当前共享资源过程中又去访问另一个共享资源（注：这里说的是狭义的死锁情况，也就是两个进程相互等待对方释放锁，所以需要有两个共享资源。访问当前资源因为其他原因而发生阻塞无法释放锁不属于该狭义死锁范围）
  4. 而另一个资源的当前访问进程和当前进程处于循环等待情况

死锁的预防：

1. 如何在程序运行前避免死锁

破坏上述任意条件即可：

  1. 使得资源可以共享访问，例如读取操作就不需要加锁
  2. 请求新资源时必须释放当前资源，或者可以由其他进程或OS强制释放当前进程的锁
  3. 一次性申请所有所需资源的锁
  4. 给所有资源编号，所有进程要访问任何共享资源时，都必须从0号资源开始申请。

2. 如何在程序运行中避免死锁

当进程请求共享资源（这里说的都是同一个共享资源）时，由系统决定它能否访问，例如银行家算法：

step 1: 进程创建时就必须告诉系统，自己最多同时需要持有多少个资源（同一个共享资源允许多进程同时访问，对于排它锁来说，这里的资源总数就是1）

step 2: 进程在运行过程中，如果需要申请资源，则：

  1. if 最大需求 – 当前持有 > 新申请数：拒绝申请，阻塞进程
  2. if 当前系统剩余 – 新申请数 < 0：拒绝申请，阻塞进程
  3. else：通过申请，分配资源

核心就是两个拒绝申请的条件，多个进程在申请资源时，根据一个或多个顺序进行资源分配就都不会出现上述两个拒绝条件时，该顺序就可以称为安全序列（单个资源可能体现不出来，如果多个资源就能看出效果）

死锁的检测与解出

如何检测死锁？

思路为：使用有向图结构保存当前资源分配状态，然后判断该图是否可以“完全简化”，如果可以则说明没有死锁。

在这个图中，每个共享资源（每个共享资源都允许k_i个进程同时访问）表示为一类节点，每个进程表示为另一类节点。从资源指向进程的边表示该资源分配给该进程，边的权重表示分配了多少个该资源给该进程。从进程指向资源的边表示当前进程正在请求该资源，边的权重表示请求该资源数目。

简化该图过程为：不断迭代，每轮迭代都删除图中所有的安全进程节点（类似于拓扑排序，拓扑排序是每次都pop出图中入度为0的节点，直到pop出所有的节点），如果所有的进程节点都能被移除，则表示无死锁

所谓安全进程节点为：某进程节点申请资源的数目是够的，即该被申请资源节点的出度加入度大于该资源总数，例如某资源节点表示一个资源总数为5的共享资源，进程节点A有权重为2的边指向它（向它申请两个资源），同时，该资源节点有一个权重为3的边指向其他进程节点，由于 2+3<=5，所以可以认为该进程节点A是安全的。在这一轮迭代时就能删掉该节点。

下图中，以边的数量表示边的权重（即分配或请求资源数量），该图表示一个无死锁状态

死锁的解除：

  1. 挂起进程并强制释放锁，如果不挂起的话它可能又迅速获得锁
  2. kill进程
  3. 回退进程到死锁前的还原点（需先手动设置还原点）

内存管理

程序的加载过程：

  1. 编译：将代码编译成字节码
  2. 链接：将外部库和代码调用链接起来，并打包模块
  3. 装入：将链接后的程序加载进内存

链接又分为：

  1. 静态链接：程序运行前就完成链接
  2. 装入时动态链接：如果代码很多，且部分互相无关，则可以在链接打包一部分后就执行装入这部分程序过程，链接过程会继续打包其他代码，两者并行执行
  3. 运行时动态链接：进程运行过程中发送缺页中断，表明需要链接动态库

注：

  1. 代码运行过程中，使用的是逻辑地址，对所有进程来说，逻辑地址都会从0开始，系统会自动将其映射到真正的物理地址
  2. 动态库加载时，如果内存不够的话，有两种解决方式：1）系统会找一块允许覆盖的内存区域加载代码，如果有程序运行到这块代码后，同样发送缺页中断重新加载代码。2）放到硬盘的交换分区

如何给程序分配内存？

连续内存分配方式（给一整个进程分配一个连续的空间）：

进程申请多大，就分配多大，这样就会将内存区域划分为多个区块，由此产生了几个问题：

1. 如何记录内存使用情况？

维护一张空闲分区表，表记录每个空闲区块的起始位置和大小

2. 选择哪些区块？

找到连续空闲区块容量足够的那些区块

3. 如何回收区块？

向空闲分区表中插入记录，并合并相邻的空闲区块

非连续分配方式：

*可以分配不连续的区块

  1. 基本分页存储管理方式：将所有的内存均匀划分为固定分区大小，分区要非常小，一般为4k，称为页
    逻辑空间和物理空间之间页的对应关系使用页表记录，页表存放在进程的PCB（进程头信息）中。
    页表的两种优化方式：
    快慢表：页表存放在内存中，其访问速度远小于cpu的处理速度，故会将常用的部分页表信息（例如使用lru缓存淘汰机制）存在高速缓存（cpu的三级缓存）中，该高速缓存处于cpu寄存器与内存中间位置。高速缓存中的部分页表称之为快表。快表有时没有命中，需要重新查找慢表（内存中的页表），这样反而多增加了一步查询，一个优化方法是同时查询快表和慢表，快表查到了就中断慢表的查询。
    两级页表：由于页表本身是一个数组，如果页表非常大则同样需要很大的连续空间。将页表拆分为多个分页，每个分页可以存在不同的内存区域中，然后再维护一个一级页表目录，用于记录页表各个分页的位置。如果程序规模很大，也可能出现多级页表
  2. 基本分段存储管理方式（一般不单独存在）：一个进程中可能包含多个模块，分段管理就是针对每个模块按照分页存储的思想单独分配内存（真实内存而不是逻辑内存），但不会将内存划分为固定大小，而是模块分段有多大就分多大。这样一来，如果进程使用了公共模块，则可以直接在进程的段表中加入公共模块的内存位置。段表一般不大，可以直接放到寄存器中
  3. 段页式管理方式：先分段，再分页。可以理解为在分页存储的基础上，将一个进程按模块划分为多个进程的效果

虚拟内存管理

局部性原理：最近访问过的数据很有可能在短时间内再次被访问，并且其附近的数据也很有可能会被访问，由此催生出缓存

由于多级缓存的存在，系统可用的总内存应该大于内存条的容量，例如，在物理内存不足的情况下，磁盘会被划分出一个交换分区当内存使用。

在上述的分页存储管理方式中，每个进程都维护一个页表用于做逻辑空间和物理空间内存的映射，而这里的虚拟内存指的也是这个逻辑空间，只不过它映射的不仅是从虚拟内存到物理内存，而是从虚拟内存映射到所有可用的内存空间（物理内存+交换分区+高速缓存等）。所以虚拟内存的页表比单纯的分页管理的页表要多记录一些东西，例如该虚拟内存页是否对应于物理内存页，还是对应在外存（交换分区）页中。

缺页中断机构：进程运行过程中需要用到内存中的某块内容，而这块内容以及被放到了外存中，此时就会引发一个缺页中断将外存中的内容加载进内存

页面置换：如果内存不够用了，又请求加载新的数据，则可以将当前已经加载进内存的部分页（例如使用LRU淘汰算法）放到外存，然后将新的数据加载进来，并修改分页表。

页面置换算法：LRU、时钟置换算法、改进型时钟置换算法

页面分配策略：操作系统可以选择固定分配（给进程分配固定大小的内存，程序使用置换算法加载新的数据）或可变分配（进程运行过程中可以动态申请新的内存，或者使用置换算法）

文件管理

广义上的文件包含文件和文件夹，使用一组属性信息描述，例如文件名称、标识符、类型、大小等

文件的逻辑结构：

  1. 无结构文件（流式文件）：比如写的代码文件、图片文件等，文件内容没有固定的格式，文件读取时也只能从上往下读
  2. 有结构文件（记录式文件）：例如excel文件、索引文件（文件头有个索引表）、hash文件（文件存储一个字典）等，可以直接从中间访问某部分

目录文件的逻辑结构：

目录文件其实是一个表格文件，名为文件控制块（FCB），内部保存该目录下拥有的文件名、文件类型、权限、类型（目录还是文件）等，文件索引地址存储在该目录文件的索引节点区域，它也是一个表，保存文件名和文件磁盘地址的映射（文件查找是根据文件名进行查找）

文件系统的实现

文件系统的层次结构：

文件在磁盘分配方式：

磁盘也有类似于内存的区块划分，称为扇区或磁道，一个磁道一般为4kb或512kb等

  1. 连续分配：直接在磁盘分配一块连续的地址（多个连续的扇区），并将地址保存在文件索引表中。缺点是如果文件变大，则磁盘不方便扩展
  2. 链接分配：可以分配不连续的扇区，但需要另一张表记录每个扇区的下一个扇区地址（这个表称为文件分配表，即FAT，文件长度属性如果是32位的，就是FAT32，FAT32只能存储4G以内的文件是因为，FCB记录文件长度的字段是一个32bit的属性，32bit最大只能记录4G的长度），而文件索引表只记录文件的起始扇区地址。之所以要用FAT而不是扇区后面直接记录下一个扇区地址，在于：
    1）如果某扇区内容丢失了，仍然可以找到其后面扇区的内容
    2）可以实现随机访问：使用FAT可以找到一个文件所有的扇区，即可以单独访问任一个扇区
  3. 索引分配：文件仍然可以分配不连续的扇区，文件索引表不直接指向文件所在的磁盘位置，而是指向另一个索引表，该索引表存储文件包含的扇区地址（FAT是一张大表，一个磁盘只有一张，记录所有扇区的下一个扇区地址，而该子索引表是每个文件都有，记录的是该文件拥有的扇区）。如果磁盘一个扇区只有4kb，那么这个子索引表也不能太大，意味着文件不能超过4M，显然是不行的，一个解决方法是使用多级索引表，例如使用2级索引表就能存储4G的文件了。

输入输出（I/O）管理

产生IO的设备：人机交互设备（鼠标、键盘等）、存储设备、网络通信设备

IO控制器：连接CPU与外部输入输出的桥梁。狭义上它并不是整个IO设备，而是外部IO功能与CPU连接通信的部分，例如对一个显示器来说，它作为一个输出设备，不可能每个像素点都受CPU直接控制，它们中间肯定有一个桥梁，对于硬盘来说，它也有一个IO控制设备，它的一般组成部分有：

  1. 分别连接CPU和外部IO的接口，毕竟是桥梁，两边要连上
  2. IO逻辑：接收CPU发送的指令，指令一般包含 操作地址 和 操作指令，并将这些操作转换为外部IO的操作
  3. 寄存器：保存数据、状态、控制信息等（有些设备可以直接调用内存用于保存数据等）

IO控制方式

逐步发展的过程

  1. CPU不断检测状态寄存器状态，有数据则从数据寄存器读取到内存，此时CPU会不断轮询，会出现CPU资源浪费
  2. 中断方式，IO控制器要发送数据时，主动向CPU发送中断指令，避免CPU忙循环。但可能出现频繁中断
  3. *DMA（直接内存访问）方式，较中断方式两点改进：1）不再是有数据就发送中断，而是先累计一些数据再发送中断，并且这些数据是以块为单位（之前是以字节为单位，这样一来就增大了每次数据发送了）。2）数据在寄存器累计到一个程度就主动转存到内存中，避免CPU做复制
  4. 管道控制方式，即使是DMA方式，读取IO数据也是CPU亲历亲为，例如它需要自己控制读取文件的各个流程细节，而管道控制方式则是使用一个专门的设备，整个IO过程都由这个设备操作，例如要读取某个文件时，CPU可以只用给该设备发送一个读取某文件的指令，该设备就能读好文件后再给CPU发中断。

SPOOLing（假脱机）技术：磁盘的数据最终需要通过磁头（机械硬盘）读写，磁头寻道读写的效率是很低的，故会在磁盘中专门开辟一块区域用作临时读写，磁头并不会真正去寻找数据在磁盘上真正的位置，而是直接在这一块区域进行读写，后续有其他进程将这这些数据同步到真正的磁盘位置，这块区域就叫输入井或输出井

Leave a Comment