bc's club

This is Bc's club

操作系统

一、并发#

1 协程、线程、进程#

  • 进程是资源分配和拥有的基本单位。运行一个可执行程序会创建一个或多个进程，进程就是运行起来的可执行程序
  • 线程是程序执行的基本单位，是轻量级的进程。每个进程都有唯一的主线程，且只能有一个，主线程和进程是相互依存的关系，主线程结束进程也会结束。
  • 协程是用户态的轻量级线程，是线程内部调度的基本单位。

2 进程调度算法#

  • 先到先服务：FCFS
  • 短作业优先
  • 最短剩余时间优先
  • 时间片轮转
    • 所有进程按到达时间排队，每次分配一个时间片给队首进程，执行完放到队尾。
    • 时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
    • 时间片太长，实时性不能得到保证
  • 优先级调度
    • 每个进程分配一个优先级，按优先级进行调度。
    • 为了防止饿死，随着时间的推移增加等待进程的优先级
  • 多级反馈队列
    • 多个队列，1，2，4，8，…个时间片。进程在第一个队列没执行完，就会被移到下一个队列。
    • 最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。
    • 能解决时间片多的进程的切换成本。

3 阻塞IO、非阻塞IO、多路复用IO。#

blog.csdn.net/Chen4852010…

  • 阻塞IO
    • 当用户线程发出IO请求后，内核会去查看数据是否就绪，未就绪的话就会等待。用户线程处于阻塞状态，用户线程交出CPU。
  • 非阻塞IO
    • 用户线程不断询问内核，数据是否就绪，不会交出CPU，而是一直占用CPU
  • 多路复用IO
    • 单个线程就可以同时处理多个IO请求，单个线程可以监视多个文件句柄，一旦某个文件句柄就绪，就能够通知应用程序进行相应的读写操作。没有文件句柄就绪时，会阻塞应用程序，交出cpu。
  • 如何实现多路复用IO
    • 在linux中有三种机制可以实现多路复用IO，select，poll，epoll

4 select、poll、epoll#

blog.csdn.net/dolly_baby/…

  • select
    1. 会修改传入的参数数组。
    2. 扫描是轮询
    3. 非线程安全。
  • poll
    1. 不修改传入数组；
    2. 扫描也是轮询
    3. 非线程安全
    4. 如果报告了fd后，没有被处理，那么下次poll时会再次报告这个fd。
  • epoll
    1. 仅支持linux
    2. 支持边缘触发和水平触发
    3. 底层的红黑树用于查找，底层的双向链表用于就绪事件的通知
  • epoll的水平触发和边缘触发的区别
    • 边沿触发：
      1. socket的接收缓冲区状态变化时触发读事件，即空的接收缓冲区刚接收到数据时触发读事件
      2. socket的发送缓冲区状态变化时触发写事件，即满的缓冲区刚空出空间时触发读事件
      3. 仅在缓冲区状态变化时触发事件
    • 水平触发：
      1. socket接收缓冲区不为空，有数据可读，则读事件一直触发
      2. socket发送缓冲区不满可以继续写入数据，则写一直触发

5 进程间通信方式#

  1. 管道：用于具有亲缘关系的进程之间的通信。
  2. 有名管道：遵循先进先出。以磁盘文件的方式存在，可以实现本机任意两个进程通信。
  3. 共享内存：不同进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据的更新。需要依靠同步操作，如互斥锁和信号量。
  4. 消息队列：消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识。也是先进先出。
  5. 信号：用于通知接收进程某个事件已经发生
  6. 信号量：信号量是一个计数器，用于控制多个进程对共享数据的访问。
  7. 套接字：用于在客户端和服务器之间通过网络进行通信。

同一台机器进程通信最快的方式是什么，为什么。

  • 共享内存通信最快，共享内存的消息复制只有两次。

6 死锁的必要条件#

  1. 互斥
  2. 请求和保持
  3. 不可抢占
  4. 循环等待

7 进程状态#

  • 运行态：包括就绪
  • 阻塞态/睡眠态：等待IO操作
  • 死亡态
  • 僵尸态：子进程退出，父进程没有处理完子进程退出信息

8 用户态和内核态#

  • 内核态可以访问所有数据
  • 用户态只能受限的访问内存

需要限制不同的程序之间的访问能力

  • 如何避免频繁切换用户态和内核态
    1. 减少线程切换，释放锁和加锁会引起较多上下文切换
    2. 用CAS算法，避免阻塞现场
    3. 使用协程

二、内存#

1 页面置换算法#

  • 最佳页面置换算法：OPT
    • 选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。无法实现，是衡量其他算法的参考。
  • 先进先出页面置换算法：FIFO
    • 总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰。
  • 最近最久未使用页面置换算法：LRU
    • 记录每个页面上一次被访问到现在的时间，选最久未被使用的淘汰。
  • 最少使用页面置换算法：LFU
    • 选择之前使用次数最少的页面进行淘汰
  • 时钟置换算法：CLOCK

最佳置换算法性OPT能最好，但无法实现；
先进先出置换算法FIFO实现简单，但算法性能差；
最近最久未使用置换算法LRU性能好，但是实现起来需要专门的硬件支持，算法开销大。

2 栈上分配内存快还是堆上分配内存快#

栈上分配内存更快，因为栈上只需要移动栈指针

  1. 操作系统会在底层对栈提供支持，会分配专门的寄存器，存放栈的地址
  2. 栈的入栈出栈操作简单，有专门的指令执行，栈效率高
  3. 堆生长空间向上，地址越来越大，栈的生长空间向下，地址越来越小

3 内存分段分页#

  • 分段
    • 将程序分为代码段、数据段、堆栈段等。
  • 分页
    • 将段分成均匀的小块
    • 通过页表映射物理内存