操作系统

2 minutes read
计算机体系知识
面试 • 操作系统

面试CS基础——操作系统笔记

一、操作系统概述

操作系统四个特性

  • 并发：同一段时间内多个程序执行。并行（同一时刻多个事件）和并发（同一个时间段多个事件）
    • 并发：同一时间段运行多个程序，操作系统通过进程和线程实现
    • 并行：同一时刻运行多个指令，需要硬件支持，流水线、多核、分布式
  • 共享：系统资源可以被内存中的多个并发执行的进程共用
    • 互斥共享（临界资源，比如打印机）和同时共享
  • 虚拟：通过 时分复用（多道程序技术 分时系统）和空分复用（虚拟内存）技术把一个物理实体虚拟为多个实体
    • 时分复用：多进程在一个处理器并发执行，让每个进程轮流占有处理器，用小时间片快速切换
    • 空分复用：虚拟内存，物理内存抽象为地址空间。
      • 地址空间的页不需要全部在物理内存中，若使用到 不在物理内存 的页时，执行页面置换算法，把页置换到内存中
  • 异步：进程是走走停停的方式执行的，以一种不可预知的速度推进

操作系统主要功能

  • 进程管理：进程控制、进程同步、进程通信、死锁处理、处理机调度
  • 内存管理：内存分配、地址映射、内存保护和共享、虚拟内存
  • 文件管理：存储空间、目录、读写管理和保护
  • 设备管理：处理用户的IO请求、缓冲管理、设备分配、设备管理等

中断和轮询

轮询

早期计算机系统对 I/O 设备的管理方式。

定时对各种设备轮流询问，有无处理请求。轮询完之后，有请求就加以处理。

轮询速度比I/O快，所以一般可以及时处理。

但是轮询占用CPU处理时间，效率较低，现代操作系统很少使用

中断容易遗漏一些问题，但是CPU利用率高

中断

系统执行程序过程中，出现某些事情，而使得

  • CPU暂停对程序A的执行
  • 转而去执行这一段事件
  • 特殊事件处理完后再返回执行程序A
  1. 外中断：外部设备请求
  2. 异常：硬件异常或故障引起的中断
  3. 陷入（软中断）：**程序中调用中断

二、进程和线程

QQ和浏览器时两个进程，内部有很多线程：HTTP请求线程、事件响应线程、渲染线程等等

进程和线程以及它们的区别

  • 进程是 运行程序的封装，系统进行资源调度和分配的基本单位，实现操作系统的并发
  • 线程是 进程的子任务，CPU进行调度和分配的基本单位，用于保证实时性，实现进程内部的并发
  • 一个程序至少有一个进程，一个进程至少有一个线程，线程依赖于进程而存在
  • 进程拥有独立的内存单元，线程共享进程的内存（拥有自己的栈和局部变量 和 执行序列程序计数器、一组寄存器）

归纳记法：

  1. 一个程序至少有一个进程，一个进程至少有一个线程
  2. 线程划分尺度小于进程，使得多线程程序并发性高
  3. 进程拥有独立的内存单元，线程共享内存，极大提高运行效率
  4. 执行过程：独立的线程必须有：一个程序运行入口、顺序执行序列、程序出口。但线程不能独立执行，必须依存在应用程序中，应用程序提供多个线程执行控制
  5. 多线程意义在于：一个程序中多个可执行部分同时执行，但操作系统没有把线程看作独立的应用来进行调度和管理资源分配。
  6. 线程开销小但是不利于资源的管理和保护；进程开销大易管理管理

记法二：

  1. 拥有资源：进程是资源分配的基本单位，线程共享进程的资源
  2. 调度：线程是独立调度的基本单位，进程内线程切换不会引起进程切换，线程从一个进程切换到另一个，会引起进程切换
  3. 系统开销：
    • 进程：创建和撤销时，系统都要分配或回收资源，内存、IO等，付出的开销远大于创建或撤销线程的开销
    • 线程：创建、切换时只需要保存和设置少了寄存器内容
  4. 通信方面
    • 线程间通信可以通过直接读写同一进程数据进行通信
    • 进程通信需要借助IPC

进程状态切换

  • 就绪：等待被调度

  • 运行

  • 阻塞：等待资源

注意：

  1. 只有就绪态和运行态可以双向转换，其它都是单向
    • 就绪态 —-调度算法获得CPU时间——->运行态
    • 运行态—–时间用完——–>就绪态
  2. 运行态——–缺少资源（不是CPU）———>阻塞

进程调度算法

不同环境调度算法不同

  • 批处理系统

    没有太多的用户，目的：保证吞吐量和周转时间

    • 先来先服务（FCFS）：按照请求的顺序调度
      • 有利于长作业，因为短作业要一直等待
    • 短作业优先（SJF）：按照运行时间最短的调度
      • 长作业有可能饿死，因为一直是短作业执行，如果一直有，会一直等待
    • 最短剩余时间优先（SRTN）：按估计剩余时间最短的顺序进行调度

  • 交互式系统

    大量用户交互操作，目的：快速响应

    • 时间片轮转：

      1568012106561

      • 按照FCFS拍成队列
      • CPU时间分配给队首，可执行一个时间片
      • 时间片用完，由计时器发出时钟中断，调度程序使停止，回到队末，然后是下个队首

      算法效率和时间片大小关系很大：

      • 进程切换都要保存进程信息，再载入新的进程信息。—-> 时间片太小：切换太频繁，进程切换上耗时过多
      • 时间片太长：实时性不能得到保证

    • 优先级调度：给每个进程分配优先级，按照优先级调度

      • 为了防止低优先级被饿死，会随时间推移增加等待进程的优先级

    • 多级反馈队列：

      • 解决的问题：一个进程要100个时间片，那么用时间片轮转，那么要交换100次。
      • 效果：既能使高优先级得到响应，又能使短作业迅速完成
      • 思想：设置多个就绪队列，优先级不同。==优先级越高 – 时间片越少==
        • 自己的时间片内没运行完，肯定要换到下一个队列了，自己则移到队尾

  • 实时系统

    请求在确定的时间内响应

    • 硬实时（满足绝对截止时间）和软实时（容忍一定的超时）

并发性：互斥和同步

1.临界区

对临界资源进行访问的 那段代码 称为临界区，为了互斥访问临界资源，每个进程进入临界区前都要进行检查

2.同步与互斥

  • 同步：多个进程按照一定顺序进行
  • 互斥：多个进程同一时刻，只有一个能进入临界区

3.信号量

一个信号量S是一个 整型变量，除了被初始化，还能被两个标准原子操作：wait()和signal()

  • wait()：P操作，down操作，lock，一负再负

    wait(S){
    if(S > 0)
        S--;
    if(S==0)
        挂起，等待S大于0();
}

  • signal()：V操作，up操作，unlock：增强信心。

    • 有进程因为S而挂起，那么使之恢复运行。
    • 如果没有进程等待S而挂起，加1
     signal(S){
     if(有进程因为S而挂起)
         使运行();
     else
         S++;
 }

4.互斥信号量（Mutex）

如果信号量只能取1或0，那么成为 互斥量（Mutex），0表示加锁，1表示临界区解锁

typedef int semaphore;
semaphore mutex = 1;
void P1(){
    wait(&mutex);
    // 临界区
    signal(&mutex);
}

void P2(){
    wait(&mutex);
    // 临界区
    signal(&mutex);
}
5.管程

使用信号量实现生产者消费者需要很多代码控制，管程把控制的代码独立出来了，不容易出错，方便调用

重要特性：一个时刻只能由一个进程使用管程

进程间通信的方式

进程同步和进程通信的区别

  • 进程同步：系统控制多个进程按一定的顺序进行
  • 进程通信：进程间传输信息

通信的方式

  • 管道 只能接收，半双工

    • 匿名管道（pipe）

      • 半双工、父子进程使用
      • nestat -tulnp | grep6080，|就是管道，前一条命令的输出作为后一条命令的输入
      • pipe函数创建并打开

    • 命名管道（FIFO）：

      • 去除了只能在父子进程使用的限制
      • 由mkfifo函数创建，打开用open
      # 创建一个命名管道
mkfifo test
    
# 用一个进程向管道里面写数据
# 如果内容没有被读出，那么命令会一直停在这里，直到内容被读出后结束
echo "this is a pipe">test
    
# 另外一个进程读取数据
cat <test

    • 生命周期随内核（不手动释放就不会消失）

    • 面向字节流

    • 自带同步互斥机制

    • 单向传输，双向通信需要建立两个。半双工

  • 管道的机制类似于缓存，放在缓冲区然后等另外的进程去拿

  • 效率低下

  • 简单，能保证数据真的被拿走

  • 消息队列

    实现双向通信，读写独立

    • 可被看作一个全局链表，放着数据类型和内容。由消息队列标识进行标记
    • 允许一个或多个进程写入或读取消息
    • 可实现双向通信
    • 生命周期随内核（不手动释放就不会消失）

  • 把进程的数据放到某个内存，然后马上让进程返回

  • a要给b发消息，a需要把消息放在对应的消息队列，b再去对应的消息队列取出来

  • 如果发送消息（拷贝）的数据占用内存较大，发送消息就需要很多时间读内存，消息队列就不再合适，使用共享内存

  • 共享内存

    • 解决拷贝所耗时间
    • 两个进程各自拿出一块虚拟地址空间，映射到相同的物理内存，实现内存共享机制
    • 进程之间会竞争内存，称之线程安全问题
      • 需要用信号量来同步对共享内存的访问

  • 信号量

    • P操作减1，V操作加1
      • PV操作用于同一进程，实现互斥。
      • PV操作用于不同进程，实现同步。
    • 本身就是一个计数器，实现进程间的互斥和同步
    • 有进程访问内存，就把信号量设置为0，其他进程就访问不了

  • Socket

    • 不同机器间的进程通信

  • 总结

    1. 管道：速度慢，容量有限，只有父子进程能通讯
    2. FIFO：任何进程间都能通讯，但速度慢
    3. 消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题
    4. 信号量：不能传递复杂消息，只能用来同步
    5. 共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存

线程通信和同步

线程的同步方式

多个线程访问一个变量或对象时，既有读也有写，会导致变量值或对象的状态出现混乱（线程安全）

所以使用全局变量容易引起线程安全

Java使用synchronizd加锁

Java使用Volatile实现线程同步，即A对变量的修改，其他线程获取都是最新的

  1. 互斥量 Synchronizd/Lock：采用互斥对象机制，只有拥有互斥对象的线程才能访问公共资源。就是上锁，只有自己可以访问
  2. 信号量：允许多个进程同时访问资源，但是要控制最大线程数量
  3. 事件（信号）：通过通知操作的方式保持同步
线程通信
  • 全局变量，最好声明为Volatile
  • 消息队列
  • CEvent类

守护进程、孤儿进程、僵尸进程

僵尸进程 kill -i PID都杀不死

fork之后，如果父进程没有 wait/waitPID等待子进程，子进程完毕后就变成了僵尸进程

孤儿进程：父进程退出，而他的一个或多个子进程还在运行，那么这些子进程称为孤儿进程。会被Init收养，对其完成收集工作

守护进程：运行在后台，周期性执行某项任务或等待某些发生的事件

三、并发：死锁和饥饿

死锁产生原因

互相等待对方手里的资源，自己又不释放

资源的竞争导致系统资源不足，以及资源分配不当，导致死锁

进程在运行的过程中请求和释放资源的顺序不当，导致死锁

死锁的必要条件

  1. 互斥：一个资源同一时间只能被一个进程使用，其它进程要用，只能等待。
  2. 占有和等待：进程以及保持了一个资源，但又提出新的资源请求。但资源已经被其它进程占有，自己手上的也不释放。
  3. 不可抢占：已经被分配的资源不能被强制性地抢占，它只能被占有它的进程主动释放
  4. 环路等待：有两个或以上进程组成一条环路，环路中每个进程等待下一个进程占有资源。A需要B的，B需要A的

处理方法

鸵鸟策略

把头埋在啥子里面，假装没发生问题

因为 解决死锁的代价极高，所以选择性忽略会获得更高的性能。

当 死锁不会对用户造成多大影响，或发生概率低，可以采用鸵鸟策略

死锁检测和恢复

检测
  • 每种类型一个资源 的死锁检测，通过有向图是否有环实现，深度优先搜索访问到了本身
  • 每种类型多个资源 的死锁检测
    • 每个进程开始都不标记，执行过程可能被标记。若算法结束，没有被标记的进程就是死锁进程

死锁预防

程序运行之前预防死锁

  1. 破坏互斥条件：
  2. 破坏占有等待条件：a.进程执行时就申请他所需的全部资源 b.申请所需资源时不占用系统资源
  3. 破坏不可抢占条件：A访问资源，但是不能全部获得，那么A进入等待，这个资源加入资源列表，可以被其它进程使用。A只有重新获得这个资源以及申请新的资源才能重新启动和执行。
  4. 破坏环路等待：将资源编号，紧缺和稀少的编较大的编号，申请资源按照顺序进行，进程获得较小编号的进程才能申请较大编号进程

死锁避免

银行家算法：

一句话：预测分配给A资源后，剩下的资源能不能满足其它消费者的需求，如果剩下的过少，不能满足其他的需求，那么就不给A分配资源。

也就是，分配资源后，系统是否是 安全状态，是的话再分配-

  • 按照顺序分配资源，直到所有进程都可以顺利完成，那么是 安全状态
  • 这种顺序称为安全序列
  • 不存在这样的序列，那么不安全（不安全不一定是死锁）
  • 安全不安全都是静态的预测或评价

解除死锁

  1. 抢占资源：从一个或多个进程抢占足够多的资源，分配给死锁，以解除
  2. 终止进程：终止死锁进程，打破环路
  3. 进程回滚

四、内存

虚拟内存

让物理内存扩充成更大的逻辑内存

每个程序拥有自己的地址空间，这个地址空间被为很多块，每块称为一页。

1568171283260

分页和分段

  • 页 是物理单位
    • 页大小由系统决定
    • 分页是为了实现 离散分配，虚拟内存，消减内存的零头，提高利用率。
    • 空间是一维的，程序员用一个记忆符即表示一个地址
  • 段 是逻辑单位，含有一组意义相对完整的信息
    • 段大小长度不确定，由用户编写的程序决定
    • 分段是为了能更好满足用户需要
    • 作业地址是二维的，要给出段名以及段内地址

分段

按照程序自身逻辑进行划分的，段是连续的内存空间，且不一定相邻

比如进程A ，自己本身16KB内存进行划分

1568170977587

段页式

程序地址空间划分为多个拥有独立地址空间的段，每个段上的地址空间分配为大小相同的页。这样既拥有分段系统的共享和保护，又有分页系统的虚拟内存的功能。

1568171357127

页面置换和LRU

程序运行过程中，要访问的页面不在内存，就会发生 缺页中断 从而将该页调入内存。如果内存没有空闲空间，那么系统会从内存调出一个页面到磁盘中，来腾出空间

页面值换类似缓存淘汰。页面大小不够用，需要把旧的不用的换出来

目标：使页面置换频率最低（缺页率最低）

常用缓存淘汰算法（LFU、LRU、ARC、FIFO、MRU）

[内存管理] 的一种页面置换算法，对于在内存中但又不用的 [数据块]（内存块）叫做 LRU，操作系统会根据哪些数据属于 LRU 而将其移出内存而腾出空间来加载另外的数据，常用于页面置换算法，是为虚拟页式存储管理服务的。

  • 最佳值换算法（OPT）：淘汰以后不再使用的页面（实际无法实现） 53%命中率
  • 先进先出算法（FIFO）：队列原理。使用简单，但是只能顺序写入和顺序读出。淘汰最先进入的。20%
  • 最近最少使用（LRU）：最近使用的条目存放到靠近缓存顶部，缓存达到极限，缓存底部条目被移除 40%
  • 最不常使用（LFU）：计时器统计访问频率，最低访问数的条目被移除。不常用，开始高访问后面低访问无法负责。访问的时候+1，缺页中断时淘汰最低的。
  • 时钟值换算法（CLOCK）：LRU性能接近OPT，但是实现困难，开销大。FIFO简单但是性能差。时钟算法是折中。循环链表，替换操作指针后移，进行访问的时候指针不动
  • 自适应缓存替换算法(ARC)：在IBM Almaden研究中心开发，这个缓存算法同时跟踪记录LFU和LRU，以及驱逐缓存条目，来获得可用缓存的最佳使用。
  • 最近最常使用算法（MRU）：移除最近最常使用的条目。一个MRU算法擅长处理一个条目越久，越容易被访问的情况。

LRU

图解LRU

“如果数据最近被访问过，那么将来被访问的几率也更高”。

热点数据，效率较高。偶发性周期性的操作会导致命中率急剧下降，缓存污染严重

  • 原则：

    如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

  • 实现：

    • 用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为 0 并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为 0。当数组空间已满时，将时间戳最大的数据项淘汰。

    • 利用一个链表来实现，每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。

    • 利用双链表（带头和尾）和 hashmap。最新的放到头部，缓存满去除末尾的。使用Hashmap存储key，访问和写入都是`O(1)

      当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回 - 1。这样一来在链表尾部的节点就是最近最久未访问的数据项。`

    • 对于第一种方法，需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是 O(n)。对于第二种方法，链表在定位数据的时候时间复杂度为 O(n)。所以在一般使用第三种方式来是实现 LRU 算法。

    对比：

    对比点 对比
    命中率 LRU-2 > MQ(2) > 2Q > LRU
    复杂度 LRU-2 > MQ(2) > 2Q > LRU
    代价 LRU-2 > MQ(2) > 2Q > LRU

    手撕LRU

    Windows下内存管理

    1. 虚拟内存

      最适合用来管理大型对象或结构数组

    2. 内存映射文件

      适合用来管理大型数据流（来自文件）以及单计算机内多个进程之间共享数据

    3. 内存堆栈

      管理大量的小对象

    怎么创建索引

五、磁盘调度

影响磁盘块的时间因素：

  • 旋转时间
  • 寻道事件
  • 实际的数据传输事件

寻道时间最长，可以优化

1. 先来先服务

按照请求顺序进行调度。公平但是没有优化，平均时间长

2.最短寻道时间优先

优先调度磁头附近的磁道。不公平，平均时间短。磁头两端的数据会出现饥饿（磁头附近的一直请求）

3.电梯算法

要么向前要么向后，直到该方向没有请求，然后改变方向，解决饥饿问题


分享：