操作系统概念

Posted by Xuan Peng on August 13, 2019

Linux内核设计与实现

  • 一切皆文件：使得对设备和对数据的操作可以通过同一套系统调用去实现：open(), read(), write(), lseek()

    • 似乎Socket不是文件
  • 任何CPU在任何时间点一定在做三者之一：
    • 1565675023793
    • 用户空间执行用户进程
    • 内核空间执行系统调用（处于进程上下文，代表某个特定的进程执行）
    • 内核空间执行中断上下文，处理某个特定的中断
  • 单内核与微内核：
    • 单内核将所有的内核服务都以单个静态二进制文件的形式存放于磁盘，在同一个大内核地址空间上运行。简单、性能高、内核间通信微不足道（直接通过内存共享来通信，因为在同一个地址空间）。大多数Unix系统都是单内核
    • 微内核的功能被划分为多个独立的过程，每个过程叫做一个server。所有服务器都保持独立运行在各自的地址空间上。因此不是像单模块内核那样直接调用函数，而是通过消息传递处理微内核通信。采用IPC机制。开销大

  • Linux是单内核系统，但吸取了微内核的精华，带来模块式设计、抢占式内核、支持内核线程以及动态装在内核模块的能力。通过函数调用来进行通信

  • 内核特点：
    1. 抢占式
    2. 线程支持
    3. 动态内核加载
    4. SMP

  • 用户态的mode bit 1 . 内核态的mode bit 0

  • 单内核OS的arch: 1565731940619

    （服务全部位于内核态，通过system call向外界开放）

  • 微内核OS的arch： 1565749847322

  • system call：nThree most common APIs are Win32 API for Windows, POSIX API for POSIX-based systems (including virtually all versions of UNIX, Linux, and Mac OS X), and Java API for the Java virtual machine (JVM)

    • 系统调用的三种传参方式
      1. 直接传入寄存器
      2. 参数值存入内存，然后将块地址/页地址作为参数传递
      3. 参数直接压入程序内存栈中

  • Process

    1. Program Code: text section
    2. Program Counter
    3. Stack:temporary data
    4. Data section
    5. Heap
    6. register set

  • 进程的内存布局： 1565751579935

  • 进程五状态：

    • start
    • ready
    • running
    • waiting
    • terminated
    • 1565751702873

  • 操作系统用PCB来代表一个进程Process Control Block

    • 1565751759063

  • 上下文切换： 1565752233325

  • CPU调度怎么实现：
    • 维持一些进程调度队列:
      1. 任务队列（所有的Process）
      2. 就绪队列
      3. 正在I/O队列
  • 短期调度器（CPU Scheduler）：选择下一步该执行的进程并且分配CPU
  • 长期调度器(Job Scheduler)：选择放入就绪队列的进程，用来控制并发度？？？
  • 进程份以下两种：
    • I/O bound process：做IO时间比占用CPU时间多
    • CPU bound process：反之
  • UNIX:整个进程创建的过程：0号进程->1号内核进程->1号用户进程（init进程）->getty进程->shell进程
  • 1号init内核进程是处于内核态的0号进程的子进程。 pstree在看的时候看不到0号进程，因为是内核态进程。实际上0号进程也是所有进程的祖先‘
  • 另一个一号进程：用户态一号进程

  • 孤儿进程被用户态一号进程领养

  • fork(), exec()(给子进程重新分配地址空间)
  • 子进程调用exit()死亡，父进程调用wait()为其回收资源
  • 父进程也可以调用abort()来杀死紫禁城

  • 孤儿进程、僵尸进程

  • IPC方式
    • message passing
      • direct pass
        • send(p,message)
        • receive(q)
      • indirect pass
        • 以邮箱做中介：
        • send(mailbox,message)
        • receive(mailbox,message)
        • 这种方式也叫buffering
  • Thread
    • Thread ID
    • PC
    • register set
    • stack
    • 一些数据在同进程线程间共享共享
    • 1565759979657
    • 线程的创建要轻量级很多
  • 多线程模型：
    • 首先线程分为用户线程和内核线程
      • 用户线程：
        1. 由用户程序创建
        2. 线程间切换，不需要进入内核态
        3. OS不知道线程的存在
        4. 一个线程阻塞，其他线程也一并阻塞
        5. OS并没有分配额外的资源，相当于多个线程共用原进程资源
      • 内核线程：
        1. 由OS提供支持创建
        2. 线程间切换采用内核态，速度会慢一点
        3. OS可以为每个线程分配各自资源，（如更多的利用多核CPU）
        4. ！！！难怪自己写的多线程程序，其实都是单线程…比如python的假多线程
    • 用户线程和内核线程之间有如下数量关系（这个没看懂）
    • 线程是独立调度的基本单位，进程是资源拥有的基本单位
      • 多对一
      • 一对一 1565807022110
      • 一对多
  • Unix信号
    • 信号是UNIX系统中用来通知进程特定发生了特定事件的机制
    • 信号句柄：接收到信号后的处理函数
      • OS对每种信号句柄都有一种默认的实现
      • 用户可以自定义实现去重写OS的信号句柄
  • thread-local storage(TLS)：允许每一个线程拥有一份数据拷贝
  • Linux通过clone()系统调用来创建一个线程

CPU调度

  • CPU burst的概念：一个CPU burst代表占用CPU一个执行cycle的时间

  • CPU-burst的分布： 1565810308043

  • CPU调度器：

    • 短期调度器
    • 中期调度器
    • 长期调度器

  • 抢占式/非抢占式的调度：

    1565810454001

    • 简单来说，非抢占式调度下一个占据CPU的线程会一直被执行直到终止或者做I/O。而抢占式调度下，如果出现高优先级或者xxx的进程，可以直接把原进程挤出CPU，变成ready进程

  • Dispatcher：进程分派器，在running进程切换时发挥以下作用：

    1. 进程上下文切换
    2. 切换到用户态
    3. PC跳转到下一个进程的起始位置

  • CPU调度原则：

    • CPU利用率
    • 吞吐量
    • 周转时间turnaround time:执行特定进程的时间（包含运行时间和等待时间）
    • 等待时间
    • 响应时间

  • 例题： 1565811137672

CPU调度算法

  1. FIFS先来先服务：非抢占式；缺点会导致短耗时进程等待过长时间
  2. Shortest job First：如果时间相同，则按照FCFS原则处理，然而很难知道每个job的time
  3. Shortest remaining time first：同上。然而不能知道每个job的remaining time
  4. 优先级调度：数越小优先级越高，分为抢占式和非抢占式两种；缺点：低优先级进程会挨饿starvation，解决方案：aging，随着时间增加优先级
  5. 时间片轮转：进程用完一段时间就插入ready queue末尾；根据经验，80％的CPUburst应该比time quantum短。
  6. 多级队列:比如：就绪队列分为前端和后台两个队列。每个队列有其各自的调度算法：前端RR，后端FCFS
  7. 多级反馈队列：在多级队列基础上，允许进程在队列间切换 1565812753634
  • 多CPU情况下的调度：
    • 非对称多进程：一个CPU处理所有CPU的调度
    • 对称多进程SMP：每个CPU负责各自的调度，这个用的比较多
      • 在SMP系统中，CPU之间的负载均衡非常重要
  • Windows使用优先级队列的抢占式调度

Synchronization

  • race condition:为了避免race conditions,并发进程/线程必须要进行同步处理
  • critical section:资源临界区，一次只能被一个对象访问.需满足的条件
    1. Mutual Exclusion:互斥、忙则等待
    2. Progress：空闲让进
    3. Bounded waiting：有限等待
  • 同步机制
    1. Software-based
    2. Hardware-based
    3. Semaphore
      • wait()和signal()。P()V()操作
    4. Monitor管程，即提供好同步的实现，提供API
  • 死锁的必要条件
    1. 互斥
    2. hold and wait
    3. No preemption
    4. Circular wait
  • 如何预防死锁：从四个必要条件入手
  • 银行家算法：计算一系列资源请求是否安全，寻找安全序列是否存在

内存管理

  • 内存的最小单位是字，一个字是固定的若干个byte

  • 进程的内存保护

    • 两个寄存器：base 和 limit
      • base代表当前进程起始地址位置
      • limit代表当前进程内存的size

  • 地址绑定：

    • 即将进程的相对内存地址转化为物理内存的绝对地址
    • 可分为：
      • 编译时绑定（需要在编译时知道进程的基地址）
      • 运行时绑定
      • 执行时绑定：如果进程在执行时可以在内存中移动。这种情况比较罕见，需要硬件支持
    • MMU内存管理单元：做地址绑定的硬件： 1566509896359
    • 动态加载：库/函数直到被调用再加载
    • swapping：内存换入换出
      • 当内存空间不够的时候，把内存中优先级低的进程暂时换出去
    • OS内核通常在内存的低地址
    • 用户进程通常在高地址
    • Hole：进程内存空间之间的空洞（因为上一个使用这里的内存已经结束了）
    • External Fragmentation和Internal Fragmentation以及compaction

    分页

    • 页表：

1566510812009

  • 页表存在于内存中，PTBR页表基准寄存器指向页表，PTLR存储页表size

  • 每一页的大小大概是4-8KB

  • 分页模式下，每次访问进程的内存，都需要两次访存

    • 解决方法：TLB（translation look-aside buffers），也叫快表
    • TLB的本质类似于cache。访问TLB比访问内存快很多

  • 分页下的内存保护：每一个页表entry都带一个valid-invalid-bit

  • 分级页表

    1566512173632

  • 哈希页表

    1566512188737

TODO: 什么是TLB

Virtual Memory

  • 是对真实存放在RAM中内存和暂时存储在硬盘交换区的内存的统一抽象
  • 这种情况下的page table，会有一个标志位来表示当前页在内存/硬盘(Valid-invalid bit)
    • 如果是Valid，那么直接访存
    • 如果是invalid，那么产生一个page fault，缺页中断。
  • handle Page Fault：
    1. 查页表
    2. 页不在RAM中，给OS发送trap
    3. 在内存中找到一个空闲桢
    4. 将磁盘中的页换入到空闲桢
    5. 修改页表中的地址以及修改标志位为V
    6. 重新从页表开始执行访存
  • 缺页中断太耗时了！！！ 1566577932276
  • 引入locality of reference
  • 硬件支持：
    1. 页表需要标志位
    2. 交换设备（device for swap），我一直以为这应该是软件层面的东西？？？ Thesecondary memory is usually a high-speed disk. It is known as the swap device, and the section of disk used for this purpose is known as swap space.
      • 交换设备的I/O比一般的硬盘I/O要快

1566579461864

这个modify bit是什么意思

  • 如果缺页中断时内存没有空桢，置换算法（受害者算法）
    1. FIFO
      • Belady’s Anomaly:加入更多的空页有时反而导致更多缺页中断
    2. OPT：最优替换，不可行，因为不知道将来的事
    3. LRU
    4. Second-chance algo：广义是FIFO，不过内存中的potential受害页都有一次机会，增加一个标志位..。
    5. Enhanced second-chance algo:标志元组，增加一个标志位代表最近是否被使用
  • 内存分配算法：
  • 1566579531973

  • 抖动thrashing

  • 内存访问的本地性

文件系统接口

文件系统接口一览：

  1. Create
  2. Write（在write指针处写）
  3. Read（在Read指针处写）
  4. Seek
  5. Delete
  6. Truncate

文件系统锁：

  • 从可读性
    • 共享锁
    • 互斥锁
  • 从机制
    • 强制锁
    • 非强制锁
  • 文件目录会记录目录下所有文件信息， 1566609688502

  • 目录和文件都存放在磁盘中。目录也被叫做FCB 文件控制块

  • 磁盘IO慢，因为现在的magnetic disk，磁头有一个寻找和定位的时间，很长很长，也叫seek time和rotation time
  • SSD快就是因为电子材料做成，不需要寻找定位的时间
  • 磁盘调度的目的，就是要最小化seek time
  • 调度算法：
    1. FCFS
    2. SSTF最短seek time优先
    3. 电梯算法Scan，C-Scan（想想两张图就行）
    4. Look和C-Look
FEATURED TAGS
FRIENDS