1.进程线程概念

  • 进程：
    • 进程是操作系统中资源分配的基本单位。
    • 每个进程都有独立的内存空间、文件描述符、代码和数据段等。
    • 一个程序可以启动多个进程，每个进程运行一个独立的任务。
    • 进程之间相互独立，切换需要操作系统开销。
  • 线程：
    • 线程是进程中的执行单位，一个进程可以包含多个线程。
    • 线程共享进程的资源（如内存、文件描述符等），但有独立的执行栈和寄存器。
    • 线程之间的通信更高效，但也更容易引发资源竞争问题。

区别：

  • 进程之间是“重量级”操作，切换开销大，线程切换较轻量。
  • 进程隔离性强，线程共享资源易出现同步问题。

2.进程间通信方式

进程之间需要通过特定方式共享数据或传递信息，主要方式有：

  1. 管道（Pipe）：
    • 单向通信，父子进程常用。
    • 数据从写端输入，从读端输出。
  2. 消息队列：
    • 内核支持的消息传递方式，带有消息队列 ID。
    • 适合在多进程间传递结构化信息。
  3. 共享内存：
    • 多个进程映射到同一块内存区域，实现数据共享。
    • 需要借助同步机制（如信号量）避免数据竞争。
  4. 信号量（Semaphore）：
    • 用于控制多进程对共享资源的访问。
    • 类似“计数器”机制，可以实现资源的互斥访问。
  5. 套接字（Socket）：
    • 基于网络的通信方式，可用于本地进程间通信（如 UNIX Socket）或跨网络进程通信。

STL容器时间复杂度

1. 顺序容器

(1) vector

  • 特点：动态数组，支持快速随机访问，插入和删除需要移动元素。

  • 时间复杂度

    ：

    操作 时间复杂度 说明
    随机访问 (operator[]) O(1) 支持快速随机访问
    尾部插入 (push_back) 均摊 O(1) 需要时动态扩容，扩容的时间为 O(n)
    尾部删除 (pop_back) O(1) 删除最后一个元素
    插入或删除(中间/头部) O(n) 需要移动元素
    查找元素 O(n) 无法直接查找，只能遍历

(2) deque

  • 特点：双端队列，支持快速的头尾插入和删除，随机访问较快。

  • 时间复杂度

    ：

    操作 时间复杂度 说明
    随机访问 (operator[]) O(1) 支持快速随机访问
    头尾插入 (push_front/push_back) O(1) 不需要移动元素
    头尾删除 (pop_front/pop_back) O(1) 删除头部或尾部元素
    插入或删除（中间） O(n) 需要移动元素
    查找元素 O(n) 无法直接查找，只能遍历

(3) list

  • 特点：双向链表，支持快速的插入和删除，但随机访问较慢。

  • 时间复杂度

    ：

    操作 时间复杂度 说明
    随机访问 (operator[]) O(n) 只能从头/尾遍历
    插入或删除（任意位置） O(1) 已有迭代器定位到目标位置
    查找元素 O(n) 无法直接查找，只能遍历

2. 关联容器

(1) set 和 multiset

  • 特点：基于红黑树实现，元素有序，支持高效的查找、插入和删除。

  • 时间复杂度

    ：

    操作 时间复杂度 说明
    插入 (insert) O(log⁡n) 基于红黑树的平衡特性
    删除 (erase) O(log⁡n) 同上
    查找 (find) O(log⁡n) 同上
    范围查询（区间迭代） O(k) k为区间大小

(2) map 和 multimap

  • 特点：基于红黑树实现，键值对有序存储，支持按键高效查找。

  • 时间复杂度

    ：

    操作 时间复杂度 说明
    插入 (insert) O(log⁡n) 基于红黑树的平衡特性
    删除 (erase) O(log⁡n) 同上
    查找 (find) O(log⁡n) 同上
    范围查询（区间迭代） O(k) k 为区间大小

(3) unordered_set 和 unordered_multiset

  • 特点：基于哈希表实现，元素无序，查找和插入平均效率高，但最坏情况较差。

  • 时间复杂度

    ：

    操作 平均时间复杂度 最坏时间复杂度
    插入 (insert) O(1) O(n)
    删除 (erase) O(1) O(n)
    查找 (find) O(1) O(n)

(4) unordered_map 和 unordered_multimap

  • 特点：基于哈希表实现，键值对无序存储，支持按键高效查找。

  • 时间复杂度

    ：

    操作 平均时间复杂度 最坏时间复杂度
    插入 (insert) O(1) O(n)
    删除 (erase) O(1) O(n)
    查找 (find) O(1) O(n)

3. 容器适配器

(1) stack

  • 特点：基于 deque 或 vector 实现的后进先出（LIFO）结构。

  • 时间复杂度

    ：

    操作 时间复杂度 说明
    压栈 (push) O(1)
    弹栈 (pop) O(1)
    访问栈顶 (top) O(1)

(2) queue

  • 特点：基于 deque 实现的先进先出（FIFO）结构。

  • 时间复杂度

    ：

    操作 时间复杂度 说明
    入队 (push) O(1)
    出队 (pop) O(1)
    访问队头 (front) O(1)

(3) priority_queue

  • 特点：基于堆（通常是二叉堆）实现的优先级队列。

  • 时间复杂度

    ：

    操作 时间复杂度 说明
    插入 (push) O(log⁡n) 插入后需调整堆
    删除最大/最小值 (pop) O(log⁡n) 删除后需调整堆
    访问最大/最小值 (top) O(1)

4. 总结表格

容器 插入 O 删除 O 查找 O 随机访问 O
vector 均摊 O(1) O(n) O(n) O(1)
deque O(1) O(1) O(n) O(1)
list O(1) O(1) O(n) O(n)
set / map O(log⁡n) O(log⁡n) O(log⁡n) 不支持
unordered_set / unordered_map 平均 O(1) 最坏 O(n) 平均 O(1) 最坏 O(n) 平均 O(1)最坏 O(n) 不支持

3…互斥锁和读写锁

互斥锁（Mutex）和读写锁（Read-Write Lock）都是用于多线程同步的机制，但它们的工作方式和应用场景有所不同：

1. 互斥锁（Mutex）

互斥锁是最基本的一种锁，确保在同一时间只有一个线程能够访问共享资源。它主要用于保护临界区，避免多个线程同时修改共享资源而导致数据不一致或程序崩溃。

  • 特性：
    • 当一个线程获得互斥锁时，其他线程必须等待，直到持有锁的线程释放锁。
    • 互斥锁保证了线程间的互斥访问，适用于对共享资源的写操作或修改操作。
    • 使用简单，性能较高，适用于锁的竞争不严重的情况。
  • 应用场景：
    • 当对共享资源的访问是写操作时，使用互斥锁来确保线程的安全。
    • 需要防止多个线程同时修改某个共享资源时。
  • 优点：
    • 实现简单，能有效防止数据竞争。
  • 缺点：
    • 性能较低，如果多个线程频繁争夺锁，可能会导致线程阻塞，造成性能瓶颈。

2. 读写锁（Read-Write Lock）

读写锁允许多个线程同时读取共享资源，但当有线程写共享资源时，其他线程不能进行读取或写入。读写锁分为读锁和写锁：

  • 读锁（Shared Lock）：允许多个线程同时获得该锁进行读取操作。
  • 写锁（Exclusive Lock）：只允许一个线程获得锁进行写操作，且在该线程持有写锁时，其他任何线程都不能获得读锁或写锁。
  • 特性：
    • 读锁允许多个线程同时持有锁（共享锁）。
    • 写锁是独占的，任何线程持有写锁时，其他线程无法获取任何类型的锁（读或写）。
    • 适用于读多写少的场景，能够有效提高并发性能。
  • 应用场景：
    • 数据的读操作远多于写操作时，使用读写锁可以提高并发度。例如，缓存系统、数据库查询等场景。
    • 需要保护的共享资源既有频繁的读操作，又有较少的写操作。
  • 优点：
    • 可以提高读取操作的并发性，因为多个线程可以同时读取资源。
  • 缺点：
    • 实现较为复杂，写操作的线程在竞争激烈时可能会导致较长时间的等待（写饥饿问题）。
    • 写操作的性能可能会下降，因为它需要等待所有读操作结束。

总结对比：

特性 互斥锁（Mutex） 读写锁（Read-Write Lock）
锁类型 只有一个线程可以持有锁 支持多个线程同时持有读锁，写锁是独占的
适用场景 适用于写操作较多或频繁修改资源的情况 适用于读操作远多于写操作的情况
性能 性能较低（频繁竞争时） 读操作并发性好，但写操作可能会受到影响
锁的粒度 单一线程访问资源 读操作并发，写操作独占

总的来说，如果你有一个数据结构或资源，读操作远多于写操作，使用读写锁能够显著提高并发性能。而如果资源的修改较频繁，使用互斥锁则会更简单和高效。

4.多线程多进程

选择 多线程（Multithreading）还是 多进程（Multiprocessing）取决于你的具体需求和应用场景。两者都有各自的优势和适用场景，下面是它们的对比以及何时选择使用它们。

1. 多线程（Multithreading）

多线程指在一个进程内，多个线程共享进程的内存空间和资源，线程是程序执行的最小单位。多线程能够实现并发执行，但它们的执行是由操作系统调度的，通常是在一个处理器核心上轮流执行。

特点：

  • 共享内存空间：线程之间可以共享进程中的数据和资源，通信非常高效。
  • 轻量级：线程的创建和销毁比进程要轻便，消耗的资源较少。
  • 上下文切换成本低：线程切换时，由于共享内存，操作系统需要保存的状态信息比进程少。
  • 资源共享容易导致竞争条件：多个线程访问同一共享资源时，需要同步机制（如锁）来避免数据竞争和不一致。

优势：

  • 高效的资源共享：多个线程可以直接访问同一块内存区域，因此共享数据非常简单。
  • 更低的开销：创建和销毁线程的开销比进程要小很多。
  • 适用于 I/O 密集型任务：比如网络请求、文件操作等，多个线程可以同时进行，降低等待时间。

缺点：

  • 线程安全问题：需要使用同步机制（如互斥锁、读写锁等）来避免多个线程同时修改同一资源，导致竞态条件。
  • 有限的并行度：在 CPU 密集型任务中，由于全局解释锁（GIL）的存在（如 Python 中），多个线程不能真正并行执行。

适用场景：

  • I/O 密集型任务：多个线程可以同时等待 I/O 操作，减少阻塞时间，提升效率。
  • 实时性要求不高的任务：比如用户界面的响应、文件读写、网络通信等。

2. 多进程（Multiprocessing）

多进程指在操作系统中启动多个进程，每个进程都有独立的内存空间，进程间不能直接共享数据，进程之间的通信需要通过进程间通信（IPC）机制，如管道、消息队列等。

特点：

  • 独立的内存空间：每个进程都有自己的内存空间，进程间没有直接访问对方数据的权限，避免了线程中的共享资源问题。
  • 较重的开销：进程的创建和销毁相比线程更为耗费资源和时间，进程间的上下文切换也比线程更昂贵。
  • 更高的并行性：每个进程可以独立运行于不同的 CPU 核心，因此适合于真正的并行计算。

优势：

  • 独立的内存空间：每个进程有独立的内存和资源，进程之间不会发生内存泄漏或数据竞争。
  • 真正的并行：可以充分利用多核 CPU，使得 CPU 密集型任务能够实现真正的并行。
  • 适用于计算密集型任务：多进程能在多核 CPU 上并行处理复杂计算任务，提高性能。

缺点：

  • 通信开销较大：进程间的通信需要通过 IPC（如管道、套接字等），相比线程内存共享的方式，通信开销较大。
  • 资源占用大：每个进程都需要分配独立的资源，包括内存，因此进程的创建和销毁相对较重。
  • 无法共享内存：需要通过显式的进程间通信来传递数据，这比共享内存的线程方式要麻烦。

适用场景：

  • CPU 密集型任务：比如数据处理、图像处理、科学计算等，适合通过多进程充分利用多核 CPU。
  • 需要高稳定性：进程间互相独立，一个进程崩溃不会影响其他进程，适合于对稳定性要求高的场景。