参考博客
进程和线程
- 进程是对运行时程序的封装，是系统进行资源调度和分配的基本单位，实现操作系统并发
线程是进程的子任务，是CPU调度和分派的基本单位，用于保证程序的实时性（对并发的用户操作做出实时响应），实现进程内部并发
一个程序至少有一个进程，一个进程至少有一个线程，线程依赖于进程
进程在执行过程中有独立的内存单元，而多个线程共享进程的内存
多线程优势
- 解耦合，简化程序开发：将不同种类任务分配专门线程，形成串行假象
- 提高资源利用率：对于多CPU来说，多个线程可以调度到多个CPU上运行，提高系统吞吐率
多线程风险
- 安全问题：当多个线程访问某个类时，不管运行时环境采用何种调度方式或者这些线程将如何交替执行，并且在主调代码中不需要任何额外的同步或协同，这个类都能表现出正确的行为，那么这个类就是线程安全的
- 活跃性问题：死锁、饥饿
- 性能问题：吞吐率过低、资源消耗过高。当线程调度器临时挂起活跃线程并转而运行另一个线程时，就会频繁出现上下文切换操作(Context Switch)，这种操作会导致 CPU 时间更多的花在线程调度上而非线程的运行上。
进程间通信 IPC
- 管道及命名管道
- 管道：半双工通信方式，数据只能单向流动（父进程关闭fd[0]，子进程关闭fd[1]，父进程写，子进程读），且只能在具有亲缘关系（父子进程）的进程间使用。
- 高级管道：将另一个程序当作一个新的进程在当前程序进程中启动，则它算是当前程序的子进程
- 命名管道 (named pipe) ：命名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
- 消息队列：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
- 信号量通信：计数器，控制多个程序共享资源的访问
- 信号：通知接收进程某个事件已经发生
- 共享内存：最快的通信方式，映射一段能被其他进程访问的内存，由一个进程创建，多个进程访问。通常与信号量配合使用，来实现进程间的同步和通信
- 套接字 (socket)：可用于不同机器间的进程通信，可简单归纳为命名、绑定、监听、连接、数据交互、断开连接这几个步骤
线程同步方式
- 互斥锁 mutex：通过对共享资源进行加锁和解锁的操作，标记资源是否可用，无锁资源阻塞，知道互斥量被解锁
- 条件变量：自动阻塞某个线程，直到特殊情况发生为止。条件变量通常和互斥锁一起使用。条件变量使线程可以睡眠等待某种条件出现。条件变量是利用线程间共享的全局变量进行同步的机制，包括“等待条件成立而挂起”和“另一个线程使条件成立”两个动作。
- 信号量 sem：同一时刻允许多个线程访问同一资源，但是通过信号量控制最大线程数量，通过一个整型S和一个队列表现
- PV操作：不可被打断的操作系统原语，P检查信号量是否可用，V释放信号量，主要用于完成互斥控制和同步
死锁
- 在两个或者多个并发进程中，进程间产生了互相等待对方资源释放的情况。通俗的讲，就是两个或多个进程无限期的阻塞、相互等待的一种状态。
必要条件
- 互斥：至少有一个资源一次只能有一个进程使用
占有并等待：进程至少占有一个资源，且正在等待另一个被占有的资源释放
非抢占：资源不能被抢占，只能等到占有者完成当前任务后才能占有
- 循环等待：若干进程间形成头尾相接的环形资源等待关系
处理策略
预防死锁、避免死锁、检测死锁、解除死锁 、鸵鸟策略
- 预防死锁：确保四个必要条件至少有一个不成立就能预防死锁发生
- 打破互斥条件：资源的互斥与否经常是由其本身决定的，因此通常不适用这种办法
- 打破占有并等待：预先占有所有资源，若不能完全占有则暂时挂起不执行，但是资源往往是动态分配的，不可预知，而且这样的策略会大大降低资源利用率和并发性
- 打破非抢占条件：进程在申请新资源得不到满足时，必须释放当前占有资源，以供给其他进程使用。实现起来较为困难，且降低了系统性能
- 打破循环等待：实行资源有序分配，对所有资源排序编号，只有在申请到小号资源的情况下才能申请大号的资源，这样就避免了环路的产生，预防死锁
- 死锁避免
- 进程启动拒绝：如果进程的请求会导致死锁，则不启动进程
- 资源分配拒绝：如果进程增加的资源请求会导致死锁，则不允许分配
- 安全状态：系统能按照某种进程顺序，为每个进程分配资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利完成
- 银行家算法：根据当前资源分配状态，试探性分配所需资源后，检查系统是否仍处于安全状态，是则分配，否则撤销试探性分配，令进程等待
死锁检测：资源分配图
死锁解除
- 资源抢占：从一个或多个死锁进程那里抢占一个或多个资源，此处需要避免饥饿问题（某个进程总是被抢占资源导致无法继续）
- 终止进程：一次性终止所有死锁进程或逐个终止死锁进程直至死锁解除
进程状态
- 就绪状态：获得处理机以外所有所需资源，等待分配处理机资源
- 运行状态：占用处理机资源运行，处于此状态的进程数要小于CPU数
- 阻塞状态：进程等待某种条件，在满足前无法执行
- 状态转换
- 就绪->运行：进程调度程序为就绪进程分配了处理机
- 执行->就绪：进程分配的时间片用完
- 执行->阻塞：进程等待某种事件发生（IO请求等）无法继续执行，编程阻塞状态
- 阻塞->就绪：所等待的事件已经发生，变成就绪状态
Python中的多线程
Python多线程编程常用threading模块。启动一个多线程需要创建一个Thread对象
1
2
3
4t = Thread(target=countdown, args=(10,), daemon=True) # 后台线程
t.start() # 启动线程
t.is_alive() # 查询线程对象的状态，返回布尔值
t.join() # 将线程加入到当前线程，并等待其终止GIL是CPython特性，同一时刻只能运行一个线程，不能利用多核资源。Cpython的多线程适用于I/O密集型问题，计算密集型问题可使用多进程编程。
- 线程同步原语有Event / Condition / Semaphore / Barrier。Event用于常用语通知全部线程，condition和Semapher常用于通知一定数量的线程， Barrier用于多个线程必须完成某些步骤再一起执行。Lock / Rlock / Event / Condition / Semaphore 支持上下文管理协议（with语句，好用）。
- 线程间通信可以用queue模块中的Queue队列，get()和put()已加锁，是线程安全的
进程调度策略
- FCFS 先来先服务：先请求CPU的进程先分配CPU
- SJF 最短作业优先调度：从备选作业队列中选出一个或若干个估计运行时间最短的作业优先调度，一直运行至结束或因发生事件阻塞放弃处理机
- FPF 高优先权优先调度：照顾优先级较高的作业优先调度。
- 抢占式：当有优先级更高的进程出现时，停止当前进程，将处理机分配给优先级更高进程。适合对性能要求较高的批处理和分时系统
- 非抢占式：当进程占有处理机时，只能运行至结束或因发生事件阻塞放弃处理机。用于某些对实时性要求不严的实时系统
- 优先级倒置问题：由于一个高优先级和一个低优先级进程之间的相互等待资源的情况，导致中优先级抢先于高优先级进程运行。
- 解决办法
- 设置优先级上限：为临界区设置一个优先级上限，企图进入临界区的进程优先级需要低于这个上限
- 优先级继承：当高优先级进程等待低优先级进程资源时，低优先级进程暂时继承高优先级进程优先级，直到资源被释放后恢复低优先级
- 临界区禁止中断：系统优先级分为可抢占优先级和中断禁止优先级，将运行于临界区的进程通过中断禁止保护起来，防止在访问互斥数据时被高优先级任务抢占处理机
- 解决办法
- 高响应比优先调度：响应比 = （等待时间 + 服务时间）/ 服务时间，对长作业的运行得不到保证，但是避免了最短作业优先调度中长作业饥饿的问题。在调度之前需要计算响应比，增加系统开销
- 时间片轮转法
- 将所有就绪进程按照原先的服务原则排成一个队列，每次调度时，把CPU分配给队首进程，并执行一个时间片
- 时间片用完，计时器发出中断请求，调度程序把进程送到就绪队列队尾，然后将处理机分配给就绪队列队首进程
- 由此循环，系统能够在给定时间内响应所有用户的请求
- 多级反馈队列：多级反馈队列对长短进程均有照顾，可满足各种类型进程的需要
- 设置一个优先级从高到低的n个队列，优先级越高，时间片约短
- 当有新进程进入时，放入最高优先级队列，在一个时间片内，若执行完成，则跳出队列；若不能执行完成，放入下一级队列队尾
- 只有当前面i-1个队列为空时，才能执行第i个队列；若在第i个队列的一个时间片内不能执行完成，则落入i+1队列队尾；第n个队列使用时间片轮转法进行调度
- 当有新进程需要调度时，立即把正在运行的进程放回当前队列的队尾，然后把处理机分给高优先级进程。当再度运行到当前队列的该进程时，仅分配上次还未完成的时间片，不再分配该队列对应的完整时间片。
页面置换算法
- FIFO先进先出：按照队列顺序，先进先出
- LRU 最近最少使用：按照最近一次的使用时间
- LFU 最少使用：按照截至目前使用的总次数
- OPT 最优置换：理论的最优，理论；就是要保证置换出去的是不再被使用的页，或者是在实际内存中最晚使用的算法
局部性原理
- 时间上的局部性：最近被访问的页在不久的将来还会被访问；
- 空间上的局部性：内存中被访问的页周围的页也很可能被访问。