操作系统

操作系统的演进

1.png

多道程序设计

• 早期批处理系统只能一次处理一个任务
• 多道程序设计使得批处理系统可以一次处理多个任务
• 多道程序设计是指在计算机内存中同时存放多个程序
• 多道程序在计算机的管理程序之下相互穿插运行

操作系统相关概念

• 并发性

  • 并行是指两个或多个事件可以在同一时刻发生
  • 并发是指两个或多个事件可以在同一时间间隔发生

• 共享性

  • 共享性表现为操作系统中的资源可供多个并发的程序共同使用
  • 这种共同使用的形式称之为资源共享
    • 多个程序可以同时使用主存资源
    • 资源共享根据属性可分为两种方式(互斥共享形式，同时访问形式)
    • 同时访问：某种资源在一段时间内并发的被多个程序访问，是宏观的

• 虚拟性

  • 虚拟性表现为把一个物理实体转变为若干个逻辑实体
  • 物理实体是真实存在的，逻辑实体是虚拟的
  • 虚拟的技术主要分为：时分复用技术和空分复用技术
    • 时分复用技术：资源在时间上进行复用，不同程序并发使用，多道程序分时使用计算机硬件资源，提高资源利用率
    • 空分复用技术：实现虚拟磁盘，虚拟内存，提高资源利用率
      • 虚拟磁盘：物理磁盘虚拟为逻辑磁盘，例如C盘
      • 虚拟内存：逻辑上扩大程序的存储容量，使用比实际内存更大的容量

• 异步性

  • 在多道程序环境下，允许多个进程并发执行
  • 进程在使用资源时可能需要等待或放弃
  • 进程的执行并不是一气呵成，而是走走停停形式推进

操作系统五大功能

进程管理

为什么需要进程？

• 进程是系统进行资源分配和调度的基本单位(多道程序设计)
• 进程作为程序独立运行的载体保障程序正常运行
• 进程的存在使得操作系统资源的利用率大幅提升

进程管理之进程实体

2.png

主存中的进程形态

• 标识符：唯一标记一个进程，用于区别其他进程
• 状态：标记进程的进程状态，例如：运行态
• 程序计数器：进程即将被执行的下一条指令的地址
• 内存指针：程序代码、进程数据相关指针
• 上下文数据：进程执行时处理器存储的数据
• IO状态信息：被进程IO操作所占用的文件列表
• 记账信息：进程使用处理器时间、时钟数总和等

进程控制块(PCB)

• 每个进程都有PCB
• 用于描述和控制进程运行的通用数据结构
• 记录进程当前状态和控制进程运行的全部信息
• PCB的使得进程是能够独立运行的基本单元

进程与线程

• 一个进程可以有一个或多个线程
• 进程是系统进行资源分配和调度的基本单位
• 线程是操作系统进行运行调度的最小单位
• 线程包含在进程之中，是进程中实际运行工作的单位
• 线程共享进程资源

描述	进程	线程
资源	资源分配的基本单位	不拥有资源
调度	系统调度的基本单元	独立调度的最小单位
系统开销	进程系统开销大	线程系统开销小
通信	进程IPC	读写同一进程数据通信

进程管理之五状态模型

• 创建
  • 创建进程时拥有PCB但其他资源尚未就绪的状态称为创建状态
• 就绪
  • 当进程被分配到除CPU以外所有必要的资源后
  • 只要再获得CPU的使用权，就可以立即运行
  • 其他资源都准备好，只差CPU资源的状态为就绪状态
• 阻塞
  • 进程因某种原因如：其他设备未就绪就无法继续运行
  • 从而放弃CPU的状态称为阻塞状态
• 执行
  • 例如进行IO请求，则可能执行状态可能变化为阻塞状态
• 终止

  • 进程结束由系统清理或者归还PCB的状态称为终止状态

    
    3.png

进程管理之进程同步

为什么需要进程间同步

• 对竞争资源在多进程间进行使用次序的协调
• 使得并发执行的多个进程之间可以有效使用资源和相互合作

进程间同步原则

临界资源:指的是一些虽作为共享资源却又无法同时被多个线程共同访问的共享资源。当有进程在使用临界资源时，其他进程必须依据
操作系统的同步机制等待占用进程释放该共享资源才可重新竞争使用共享资源。

• 空闲让进：资源无占用，允许使用
• 忙则等待：资源有占用，请求进程等待
• 有限等待：保证有限等待时间能够使用资源
• 让权等待：等待时，进程需要让出CPU

进程同步的方法

• 消息队列
• 共享存储
• 信号量

线程同步

• 互斥量
• 读写锁
• 自旋锁
• 条件变量

Linux的进程管理

进程的类型

• 前台进程
• 后台进程
• 守护进程

进程的标记

• 进程ID
  • 进程ID是进程的唯一标记，每个进程拥有不同的ID
  • 进程ID表现为一个非负整数，最大值由操作系统限定
• 进程的状态标记
  • ID 为0的进程为idle进程，是系统创建的第一个进程
  • ID为1的进程为init进程，是0号进程的子进程，完成系统的初始化

  • init进程是所有用户进程的祖先进程

    
    4.png

作业管理

作业管理之进程调度

• 进程调度：计算机通过决策决定哪个就绪进程可以获得CPU使用权(依赖多道程序设计)

  • 保留旧进程的运行信息，请出旧进程
  • 选择新进程，准备运行环境并分配CPU
  • 非抢占式调度
    • 处理器一旦分配给某个进程，就让该进程一直使用下去
    • 调度程序不以任何原因抢占正在被使用的处理器
    • 直到进程完成工作或者因为IO阻塞才会让出处理器
  • 抢占式调取
    • 允许调度程序以一定的策略暂停当前的运行的进程

    • 保存好旧进程的上下文信息，分配处理器给新进程

      
      5.png

• 进程调度算法

  • 先来先服务的调度算法
  • 短进程有限调度算法
    • 调度程序优先选择就绪队列中估计运行时间最短的进程
    • 不利于长作业进程的执行
  • 高优先权优先调度算法
    • 进程附带优先权，调度程序优先选择权重高的进程
  • 时间片轮转调度算法
    • 按先来先服务的原则排列就绪进程
    • 每次从队列头部去除待执行进程，分配一个时间片执行
    • 相对公平的调度算法，但不能保证及时响应用户

作业管理之死锁

思索是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象
若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或者系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

解决死锁：使用银行家算法

存储管理

• 确保计算机有足够的内存处理数据
• 确保计算机可以从可用内存中获取一部分内存使用
• 确保计算机可以归还使用后的内存以供其他程序使用

存储管理之内存分配与回收

内存分配

• 单一连续分配
  • 单一连续分配是最简单的内存分配方式
  • 只能在单用户、单进程的操作系统中使用
  • 内存分为系统区和用户区
• 固定分区分配
  • 固定分区分配是支持多道程序的最简单存储分配方式
  • 内存空间被划分为若干固定大小的区域
  • 每个区域只提供给一个程序使用，互不干扰
• 动态分区分配
  • 根据进程实际需要，动态分配内存空间
  • 涉及数据结构、分配算法

动态分区数据结构

1.png 2.png

动态分区分配算法

• 首次适应算法(FF算法)->循环适应算法(避免每次都从头部开始，变为从上一次被分配地方开始)
• 最佳适应算法(BF算法)

• 快速适应算法(QF算法)

  
  3.png

4.png 5.png

内存回收的四种情况

6.png 7.png 8.png 9.png

存储管理之段页式存储管理

• 页式存储管理
  • 字块是相对物理设备的定义
  • 页面则是相对逻辑空间的定义
  • 将进程逻辑空间等分成若干大小的页面
  • 相应的把物理内存空间分成与页面大小的物理块
  • 以页面为单位把进程空间装进物理内存中分散的物理块

  • 缺点：有一段连续的逻辑分布在多个页面中，将大大降低执行效率

    
    10.png

11.png 12.png

• 段式存储管理
  • 将进程逻辑空间划分成若干段(非等分)
  • 段的长度由连续逻辑的长度决定
  • 例如：主函数MAIN，子函数Y肯定分配不同的长度

13.png

• 对比
  • 段式存储和页式存储都离散的管理了进程的逻辑空间
  • 页是物理单位，段是逻辑单位
  • 分页是为了合理利用空间，分段是满足用户需求
  • 页大小由硬件固定，段长度可动态变化
  • 页表信息一维，段表信息是二维的

• 段页式存储管理
  • 分页可以有效提高内存利用率(虽说存在页内碎片)
  • 分段可以更好满足用户
  • 先将逻辑空间按段式管理分成若干段

  • 再把段内空间按页式管理等分成若干页

    
    14.png

15.png

存储管理之虚拟内存

虚拟内存概述

• 有些进程实际需要的内存很大，超过物理内存的容量
• 多道程序设计，使得每个进程可用物理内存更加稀缺
• 不可能无限增加物理内存，物理内存总有不够的时候
• 虚拟内存是操作系统内存管理的关键技术
• 使得多道程序运行和大程序运行成为现实

• 把程序使用内存划分，将部分暂时不使用的内存放置在辅存

  
  16.png

程序的局部性原理

局部性原理是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中

• 程序运行时，无需全部装入内存，装载部分即可
• 如果访问页不在内存中，则发出缺页中断，发起页面置换
• 从用户层面看，程序拥有很大的空间，即虚拟内存
• 虚拟内存实际是对物理内存的补充，速度接近于内存，成本接近于辅存

虚拟内存的置换算法

• 先进先出算法(FIFO)
• 最不经常使用算法(LFU)
• 最近最少使用算法(LRU)

Linux的存储管理

Buddy内存管理算法

• Buddy算法是经典的内存管理算法
• 算法基于计算机处理二进制的优势具有极高的效率
• 算法主要为了解决内存外碎片的问题

• 其实是把内存外碎片转化为内存内碎片问题

  
  17.png

算法细节

• 创建一系列空闲块的链表，每一种都是2的幂
• 伙伴系统

  • 一片连续内存的伙伴是相邻的另一片大小一样的连续内存

    
    18.png

19.png 20.png

Linux交换空间

• 交换空间(Swap)是磁盘的一个分区
• Linux物理内存满时，会把一些内存交换至Swap空间
• Swap空间时初始化系统时配置的

交换空间使用场景

• 因为存储在物理磁盘，所以内存较慢一般不建议使用
• 冷启动内存依赖
• 系统睡眠依赖

• 大进程空间依赖

  
  21.png

文件管理

操作系统的文件管理

文件的逻辑结构

• 逻辑结构的文件类型
  • 有结构文件(文本,文档,媒体文件)
    • 文件内容由定长记录和可变长记录组成
    • 定长记录存储文件格式，文件描述等结构化数据项
    • 可变长记录存储文件具体内容
  • 无结构文件(二进制文件,链接库)
    • 也称为流式文件
    • 文件内容长度以字节为单位
• 顺序文件
  • 顺序文件是指按顺序存放在存储介质中的文件
  • 磁带的存储特性使得磁带文件只能存储顺序文件
  • 顺序文件是所有逻辑文件当中存储效率最高的
• 索引文件
  • 可变长文件不适合使用顺序文件格式存储
  • 索引文件是为了解决可变长文件存储而发明的一种文件格式
  • 索引文件需要配合索引表完成存储的操作

辅存的存储空间分配

• 辅存的分配方式

  • 连续分配

    • 顺序读取文件内容非常容易，速度很快
    • 对存储要求高，要求满足容量的连续存储空间

  • 链接分配

    • 链接分配可以将文件存储在离散的盘块中
    • 需要额外的存储空间存储文件的盘块链接顺序
    • 根据额外存储空间的不同，分为：

      • 隐式链接

        
        1.png

      • 显式链接

        • 不支持高效的直接存储(FAT记录项多)

        • 检索时FAT表占用较大的存储空间(需要将整个FAT加载到内存)

          
          2.png

  • 索引分配

    • 把文件的所有盘块集中存储(索引)在某个盘块中
    • 读取某个文件时，将文件索引读取进内存即可
    • 每个文件拥有一个索引块，记录所有盘块信息
    • 索引分配方式支持直接访问盘块

    • 文件较大时，索引分配方式有很大优势

      
      3.png

• 存储空间的管理

  • 空闲表

    
    4.png

  • 空闲链表

    • 空闲链表把所有空闲盘区组成一个空闲链表
    • 每个链表节点存储空闲盘块和空闲的数目

  • 位示图

    • 位示图维护成本很低
    • 位示图可以非常容易找到空闲盘块

    • 位示图使用0/1比特位，占用空间很小

      
      5.png

目录管理

6.png

Linux的文件系统

文件系统概览

• FAT
  • FAT16/32等，微软Dos/Windows使用的文件系统
  • 使用一张表保存盘块的信息
• NTFS
  • WindowsNT环境的文件系统
  • NTFS对FAT进行了改进，取代了旧的文件系统
• EXT2/3/4
  • 扩展文件系统
  • Linux的文件系统

Ext文件系统

• 文件名不是存放在Inode节点上的，而是存放在目录的Inode节点

• 列出目录文件的时候无需加载文件的Inode

  
  1.png

2.png 3.png 4.png 5.png 6.png 7.png
8.png

设备管理

广义的IO设备

• 对CPU而言，凡是对CPU进行数据输入的都是输入设备
• 对CPU而言，凡是CPU进行数据输出的都是输出设备
• 按使用特性分类
  • 存储设备
  • 交互IO设备
• 按信息交换的单位分类
  • 块设备(磁盘，SD卡等)
  • 字符设备(打印机，Shell终端)
• 按设备的共享属性分类
  • 独占设备
  • 共享设备
  • 虚拟设备
• 按传输速率分类
  • 低速设备
  • 中速设备
  • 高速设备

IO设备的缓冲区

• 减少CPU处理IO请求的频率

• 提高CPU与IO设备之间的并行性

  
  9.png

• 专用缓冲区适用于特定的IO进程

• 当这样的IO进程比较多时，对内存的消耗也很大

• 操作系统划出可供多个进程使用的公用缓冲区称之为缓冲池

  
  10.png

SPOOLing技术

• 是关于慢速字符设备如何与计算机主机交换信息的一种技术
• 利用高速共享设备将低速的独享设备模拟为高速的共享设备
• 逻辑上，系统为每一个用户都分配一台独立的高速独享设备
• 是一种虚拟设备技术
• 在输入、输出之间增加了排队转储环节(输入井，输出井)
• SPOOLing负责输入(出)井与低速设备之间的调度

• 在逻辑上，进程直接与高速设备交互，减少了进程的等待时间

  
  11.png

线程同步

互斥量

互斥量其实就是保证了关键指令的原子性

1.png

从实现原理上来讲，Mutex（互斥锁）属于sleep-waiting类型的锁。例如在一个双核的机器上有两个线程（线程A和线程B）,它们分别运行在Core0和Core1上。假设线程A想要通过pthread_mutex_lock操作去得到一个临界区的锁，而此时这个锁正被线程B所持有，那么线程A就会被阻塞，

Core0会在此时进行上下文切换(Context Switch)将线程A置于等待队列中，此时Core0就可以运行其它的任务而不必进行忙等待。而Spin lock（自旋锁）则不然，它属于busy-waiting类型的锁，如果线程A是使用pthread_spin_lock操作去请求锁，那么线程A就会一直在Core0上进行忙等待并不停的进行锁请求，直到得到这个锁为止。

所以，互斥量有上下文切换，效率低

原子性

• 一系列操作不可被中断的特性
• 这一系列操作要么全部执行完成，要么全部没有执行
• 不存在部分执行部分未执行的情况
• 互斥量是最简单的线程同步的方法
• 互斥量(互斥锁)，处于两态之一的变量：解锁和加锁
• 两个状态可以保证资源访问的串行
• 操作系统直接提供了互斥量的api
• 开发者可以直接完成使用api完成资源的加锁、解锁操作
• 例如C的api：pthread_mutex_t

自旋锁

2.png

• 自旋锁也是一种多线程同步的变量
• 使用自旋锁的线程会反复检查锁变量是否可用
• 自旋锁不会让出CPU，是一种忙等待状态
• 自旋锁避免了进程或线程上下文切换的开销
• 操作系统内部很多地方使用的是自旋锁
• 自旋锁不适合单核CPU使用
• pthread_spinlock_t

读写锁

3.png

• 读写锁是一种特殊的自旋锁
• 允许多个读者同时访问资源以提高性能
• 对于写操作是互斥的
• pthread_rwlock_t
• pthread_rwlock_rdlock
• pthread_rwlock_wrlock

条件变量

• 条件变量是一种相对复杂的线程同步方法
• 条件变量允许线程睡眠，直到满足某种条件
• 当满足条件，可以向该线程信号，通知唤醒
• 缓冲区小于等于0时，不允许消费者消费，消费者必须等待
• 缓冲区满时，不允许生产者往缓冲区生产，生产者必须等待
• 当生产者生产一个产品时，唤醒可能等待的消费者
• 当消费者消费一个产品时，唤醒可能等待的生产者
• pthrad_cond_t
• pthrad_cond_wait

• pthrad_cond_notify

  
  4.png

使用fork系统调用创建进程

• fork系统调用时用于创建进程的
• fork创建的进程初始化状态与父进程一样
• 系统会为fork的进程分配新的资源
• fork系统调用无参数
• fork会返回两次，分别返回子进程id和0
• 返回子进程id的是父进程，返回0的是子进程

进程同步

共享内存

5.png

• 在某种程度上，多进程是共同使用物理内存的
• 由于操作系统的进程管理，进程间的内存空间是独立的
• 进程默认是不能访问进程空间之外的内存空间的
• 共享存储允许不相关的进程访问同一片物理内存
• 共享内存是两个进程之间共享和传递数据最快的方式

• 共享内不能未提供同步机制，需要借助其他机制管理并发访问

  
  6.png

Unix域套接字

• 套接字(socket)原是网络通信中使用的术语
• Unix系统提供的域套接字提供了网络套接字类似的功能
• 提供了单机简单可靠的进程通信同步服务

• 只能在单机使用，不能跨机器使用

  
  7.png