0%

操作系统

Posted on Edited on
Symbols count in article: 3.6k Reading time ≈ 3 mins.

用来记录一些系统相关

概览

  1. 操作系统的四个特性是：并行、共享、异步、虚拟
  2. 进程的状态分为：创建态、就绪态、运行态、阻塞态、终止态、就绪挂起、阻塞挂起

进程管理

  1. 进程控制由原语（内核程序）支持实现，原语的操作具有”原子性”,执行期间不可被中断
  2. 原语通过 开中断指令和关中断指令 实现原子性
  3. 进程调度层次分为作业调度、内存调度、进程调度
  4. 进程切换的时机：运行的进程主动放弃、时间片到达、更高优先级的中断和程序
  5. 不能进行进程切换：处理中断的过程中、操作系统内核临界区中、原子操作过程中
  6. 调度算法评价指标：CPU利用率、系统吞吐量、周转时间、等待时间、相应时间

调度算法

  1. 在所有进程都几乎同时到达时，采用短作业/进程 优先算法的平均等待时间、平均周转时间最少
  2. 高响应比优先 （等待时间+服务时间）/服务时间

多级反馈队列调度算法

  1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
  2. 新进程达到时先进入第一级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
  3. 只有第k级队列为空时，才会为K+1级队头的进程分配时间片

进程互斥软件实现

  1. 进程互斥四原则：忙则等待、空闲让进、有限等待、让权等待（没有获取则让出cpu执行）
  2. 单标志法:如使用一个变量值记录允许执行的进程ID，违反了空闲进入
  3. 双标志先检查法:用数组标记各进程想进入临界区的意愿，先检查再标记，分多步骤，没有原子性，违反了忙则等待
  4. 双标志后检查法:用数组标记各进程想进入临界区的意愿，先标记再检查，分多步骤，没有原子性，违反了空闲进入、有限等待
  5. peterson 算法: 使用数据表示意愿+单变量表示谦让，先占位说自己要用，然后表示谦让，进入前判断对方是否想用以及是否是自己做出了谦让的动作，最后谦让的人等待，可以实现软件层面的互斥

peterson 算法

  1. 当只使用一个变量（A：值为进程ID）控制准许谁进入时，只能两个进程交互进入，此时如果不是交互进入，则会阻塞，违背了空闲等待，所以需要增加一个变量（数组 B）告诉对方，我是不是需要使用。增加了之后，判断对方是否需要使用，如果不需要则自己可以进入，但是如果在进入前没有修改 A 的状态，会导致双方都可以进入，需要在检查是否等待前就设置好这两个变量（A，B），如果将每个进程还是将值设置为本身，无法达到效果，需要把A值设置为对方的值，这样如果对方没有要上锁，则自己可以使用，如果对方也想要并发上锁，则在等待区间，对方会将值改回来，最后还是先到先得获取到锁。（你要用我就等你用完，你不用我就用）

进程互斥硬件实现

  1. 中断屏蔽方法（内核进程）
  2. TestAndSetLock 指令（TSL), 检查上锁原子化，不满足让权等待
  3. Swap （XCHG）指令, 检查上锁原子化，不满足让权等待

信号量

  1. 整形信号量：不满足让权等待
  2. 记录型信号量，资源不够时，会将对应信息加到相应的等待队列当中，当别的进程释放资源时，唤醒对应的进程
  3. 使用信号量做进程的同步时，设置信号量的资源数为0，并实行前V后P操作（P：获取资源；V：放回资源）
  4. 使用信号量做进程的互斥时，设置信号量的资源数为1
  5. 实现互斥的操作要在同步的操作之后，以避免死锁的场景发生
  6. 多进程读写文件互斥满足并发，可以通过设置额外变量处理，且对该变量本身也是一个互斥触发条件

进程同步之哲学家问题

  1. 5个哲学家围成圆桌，左右两边各放一根筷子，一共5根，要吃饭就需要拿起两根筷子
  2. 如果互斥按顺序拿筷子，会导致相互依赖而死锁，此时为了打破僵局可以有以下解法
  3. 同时只允许四个人上桌，避免循环依赖
  4. 编号为奇数的人从左边开始拿，编号为偶数的人从右边拿，让冲突在第一层发生阻塞
  5. 5个人互斥拿筷子

管程

  1. 互斥机制由编译器实现
  2. 外部进程/线程只能通过管程提供的特定入口才能访问共享数据
  3. 每次仅允许一个进程在管程内执行某个内部过程

死锁产生的必要条件

  1. 互斥条件
  2. 不剥夺条件:进程保持的资源只能主动释放，不可被强行剥夺
  3. 请求和保持条件:保持着某些资源不放手的同时，请求别的资源
  4. 循环等待条件：存在一种资源的循环等待链（有等待链不一定发生死锁）

死锁的处理策略

  1. 预防死锁: 破坏锁死产生的四个必要条件
  2. 避免死锁: 避免系统进入不安全状态（银行家算法），如果预先知道各个进程总共需要使用的资源总数，则可以在分配时，计算当前剩余的资源是否能够按照一定的序列让全部进程都执行完成，如果不可以，则是进入了不安全状态
  3. 死锁的检测和解除：允许死锁发生，系统负责检测出死锁并解除
  4. 死锁检测算法：数据结构（资源分配图）、检测算法：逐步检测当前可以抢占资源完成任务并释放资源的进程，去除后不断检查其余进程，如果最后所有进程都能获取资源并完成，则不会死锁

内存管理

  1. 从逻辑地址到内存地址之间的转换三种方式：绝对装入、可重定位装入、动态运行时装入
  2. 内存覆盖分为固定区和覆盖区，固定区的程序段在运行过程中不会调出，覆盖区会
  3. 内存交换技术将内存调出到磁盘的交换区，交互区io比其他磁盘区域要快
  4. 内部碎片指分配给进程的内存没有用上
  5. 外部碎片指内存中的空闲空间太小而无法利用

内存分配算法

  1. 首次适应：内存空间以地址递增排列，每次从低地址开始，好处是不需要重新排序，坏处是每次都需要遍历低地址，综合性能最好
  2. 最佳适应：内存空间按照内存大小排列，好处是保留大内存，不好是产生外部碎片，分配完需要重新排序
  3. 最坏适应：内存空间按照内存大小从大到小排序，优先使用更大的分区，减少产生不可用的碎片，但是对大进程不太友好
  4. 临近适应：内存空间以地址递增排列，但是每次从上次查找介绍的地方开始寻找，优点是不用每次遍历低地址，但是会导致高地址的大分区也被用掉

逻辑地址映射到内存地址

  1. 将内存进行分片，每一片的大小固定，并做好编号。
  2. 程序的逻辑地址从0开始，是连续的，也可以将逻辑地址进行分片
  3. 将程序申请得到的不连续的物理内存地址，用数组存下对应内存的编号，物理内存和逻辑地址一一对应
  4. 物理内存通过页表存储起来
  5. cpu 有页表寄存器，将页表的起始地址记录。程序计算出逻辑地址对应的页号后，根据编号本身占用大小和起始地址算法偏移量，然后得到物理内存编号，根据编号和页块大小和页内偏移量，最终得到最后的物理内存地址。

多级页表结构

  1. N级页表访问一个逻辑地址，需要N+1次内存访问
  2. 各级页表的大小不能超过一个页面

段页式存储

  1. 逻辑地址由段号+段内页号+页面偏移组成
  2. 根据段号判断是否段越界
  3. 根据段号和起始地址找到对应的段表项
  4. 根据段表项的最大页号检查页号是否越界
  5. 根据段表项得到页表
  6. 根据页号的到具体页面的物理页号
  7. 根据页号和页面偏移得到最终的物理地址

虚拟内存

  1. 基于空间局部性和时间局部性原理，我们可以分多次将进程的内容加载进入内存
  2. 允许将作业换进换出内存
  3. 虚拟性：让用户看见的物理内存大于实际的物理内存

内存置换算法

  1. 最佳置换算法：每次淘汰的页面都是以后永不使用或者在最长时间内不会使用的（不可实现）
  2. 优先淘汰最先进入内存的页面：实现简单，性能很差
  3. 优先淘汰最久没访问的页面：性能很好，但是需要硬件支持，算法开销大
  4. CLOCK（NRU）：设置一个访问位，扫描时重置该访问问，优先淘汰没有被访问过的，最多需要进行两轮循环，而且没有考虑到写操作（涉及需要写入外存）
  5. 改进CLOCK：设置访问位和修改位，淘汰的优先级为：（无访问无修改；无访问有修改；有访问无修改；有访问有修改）最多需要4轮查找。(是否访问，是否修改)第一轮查找（0，0），第二轮查找（0，1）并将访问位重置，第三次查找（0，0），第四轮查找（0，1）,综合性能最好

页面分配置换策略

  1. 固定分配局部变换
  2. 可变分配全局变换：缺页必分配新的物理块
  3. 可变分配局部变换：根据缺页率分配物理块
  4. 抖动（颠簸）：刚刚换出的页面马上又要换入内存，刚换入的页面马上就要换出内存
  5. 工作集：某段时间间隔内，进程实际访问页面的集合
  6. 驻留集大小不能小于工作集大小，否则会导致进程运行过程频繁缺页

文件管理

  1. 有结构文件：顺序文件、索引文件、索引顺序文件
  2. 树形结构目录不利于文件共享，所以需要使用无环图目录结构（实现文件的软连接，需要增加一个共享计数器）
  3. 文件的物理结构：文件的分配和进程内存分配类似，逻辑地址和物理地址的映射也类似，不同的地方是两者一个是进程独有的，一个是多个进程会访问同一个文件，所以组织形式也会不同
  4. 文件的索引分配（和内存分配类似）可以采用链接分案、多层索引、混合索引
  5. 文件的逻辑地址和物理地址不同，用户只需要关心逻辑地址
  6. Unix 系统采用成组链接法组织空余碎片
  7. 磁盘调度算法：先来先服务算法、最短寻找时间优先、扫描算法、循环扫描算法
  8. 磁头读取完一块扇区后，需要一段时间的处理才可以继续读入下一个扇区，所以需要采用交替编号和错位命名
  9. 磁盘地址的结构命名是：柱面号（磁道号）、盘面号、扇区号：尽量减少磁头的移动次序
  10. 假脱机技术：将一个独占式设备变成一个逻辑上可共享的设备，为每个进程分配一个缓冲区，然后串行处理