学习笔记7

• 顺序算法与并行算法
• 线程的原理与优缺点
• 线程管理函数
• 线程同步
• 实践过程

顺序算法与并行算法

顺序算法（Sequential Algorithm）

• 原理：顺序算法是一种线性执行的算法，它按照顺序一步一步地解决问题。这意味着每个操作都依赖于前一个操作的结果，只有在前一个操作完成之后才能进行下一步。顺序算法通常是串行执行的，因此运行时间与输入规模成正比。
• 内容：顺序算法的设计通常包括以下步骤：
  a. 确定问题的输入和输出。
  b. 制定算法的逻辑和流程。
  c. 编写代码以按照顺序执行算法步骤。
  d. 进行测试和优化以确保算法的正确性和效率。

并行算法（Parallel Algorithm）

• 原理：并行算法是一种同时利用多个处理单元（例如多核处理器、分布式系统、GPU等）来解决问题的算法。它的原理是将问题分成多个子问题，然后并行地处理这些子问题，最后将它们的结果合并以得到最终的解决方案。并行算法的目标是通过充分利用并行性来提高算法的性能和效率。
• 内容：并行算法的设计通常包括以下步骤：
  a. 划分问题：将问题分成多个独立的子问题。
  b. 分配任务：将子问题分配给不同的处理单元。
  c. 并行执行：各个处理单元并行地解决子问题。
  d. 合并结果：将各个处理单元的结果合并以获得最终的解决方案。
  e. 处理同步和通信：确保处理单元之间的同步和通信，以协调任务的执行。

线程的原理与优缺点

线程的原理

1.线程基本概念： 线程是进程内的一个独立执行流。每个进程可以包含多个线程，这些线程共享进程的资源，如内存空间和文件句柄，但每个线程有自己的栈空间和程序计数器。
2.线程的调度： 操作系统负责线程的调度，为每个线程分配 CPU 时间片。多个线程可以并发执行，轮流分享 CPU 资源，实现并发性。
3.线程间通信： 线程可以通过共享内存来进行通信，这种通信方式相对快速。但也需要谨慎处理共享数据，以避免数据竞争和同步问题。
4.线程的创建与销毁： 线程的创建和销毁相对轻量，通常比进程创建和销毁更快速，因为线程共享进程资源。

线程的优点

1.线程创建和切换速度更快： 进程的上下文复杂而庞大。其复杂性主要来自管理进程映像的需要。要想创建新的进程，操作系统必须为进程分配内存并构建页表。若要在某个进程中创建线程，操作系统不必为新的线程分配内存和创建页表，因为线程与进程共用同一个地址空间。所以线程比进程创建更快。 进程切换涉及将一个进程的复杂分页环境替换为另一个进程的复杂分页环境，需要大量的操作和时间。相比之下，同一个进程中的线程切换要简单得多也快得多，因为操作系统内核只需要切换执行点，而不需要更改进程映像。
2.线程响应速度更快： 一个进程只有一个执行路径。当某个进程被挂起时，整个进程都将停止执行。相反，当某个线程被挂起时，同一进程中的其他线程可以继续执行。这使得有多个线程的程序响应速度更快。
3.线程更适合并行计算： 在进程模型中，各进程不能有效共享数据，因为它们的地址空间都不一样。为了解决这个问题，进程必须使用 进程间通信（IPC） 来交换数据或使用其他方法将公用数据区包含到其他地址空间中。相反，同一进程中的所有线程共享同一地址空间中的所有（全局）数据。因此，使用线程编写并行执行的程序比使用进程编写更简单、更自然。

线程的缺点

• 竞争条件：多线程共享数据可能导致竞争条件（Race Condition）和死锁（Deadlock）等并发性问题，需要使用同步机制（如锁）来解决，但这可能导致性能下降和编程复杂性增加。

• 复杂性：多线程编程更复杂，需要谨慎处理同步和共享数据，以避免潜在的错误和难以调试的问题。

• 局部性问题：线程之间的竞争可能导致缓存不一致，降低性能，因此需要精心设计线程的访问模式。

• 安全性问题：线程之间的错误可能导致数据损坏、程序崩溃等问题，因此需要谨慎处理异常情况。

线程管理函数

线程管理函数是用于创建、控制和管理线程的API函数，通常由操作系统或线程库提供。这些函数允许程序员在应用程序中创建、启动、停止和同步线程。不同的操作系统和编程语言可能提供不同的线程管理函数，但通常它们有一些共同的功能和概念。常见的线程管理函数有：

1.线程创建函数：

• pthread_create（POSIX线程）：用于创建新线程。它需要指定线程的属性、入口函数和参数，并返回一个线程标识符。
• CreateThread（Windows API）：在Windows操作系统上创建线程。与pthread_create类似，需要指定线程的属性和入口函数。

2.线程终止函数：

• pthread_exit（POSIX线程）：用于线程的正常退出。线程执行完成后调用此函数，以释放资源并通知系统线程已经结束。
• ExitThread（Windows API）：在Windows操作系统上用于线程的正常退出。

3.线程等待函数：

• pthread_join（POSIX线程）：主线程可以使用此函数等待子线程完成。这是一种线程同步机制，确保主线程等待子线程执行完毕后再继续执行。
• WaitForSingleObject（Windows API）：在Windows上等待线程或其他内核对象的状态变为 signaled。

4.线程同步函数：

• pthread_mutex_init/pthread_mutex_lock/pthread_mutex_unlock（POSIX线程）：用于创建互斥锁，锁定和解锁共享资源，以确保多个线程之间的数据同步。
• CreateMutex/WaitForSingleObject/ReleaseMutex（Windows API）：Windows提供的互斥锁函数，类似于POSIX的互斥锁操作。

5.线程销毁函数：

• pthread_cancel（POSIX线程）：用于终止指定线程。不同于pthread_exit，pthread_cancel可以用于强制终止线程。
• TerminateThread（Windows API）：在Windows上用于强制终止线程的函数。

6.线程属性设置函数：

• pthread_attr_init/pthread_attr_set...（POSIX线程）：用于设置线程的属性，如栈大小、调度策略等。
• SetThreadPriority/SetThreadAffinityMask（Windows API）：在Windows上设置线程的优先级和亲和力。

7.线程睡眠函数：

• sleep/usleep（POSIX线程）：用于让线程休眠指定的时间。
• Sleep（Windows API）：在Windows上使线程休眠指定的毫秒数。

线程同步

线程同步是一种多线程编程中的重要概念，用于协调多个线程之间的操作，以确保数据的一致性和避免并发性问题，如竞争条件和死锁。

1.互斥锁（Mutex）：

• 互斥锁是一种最常用的同步机制，用于确保在任何时刻只有一个线程可以访问共享资源。线程尝试获得锁时，如果锁已被其他线程持有，它将被阻塞直到锁可用。
• 常见的互斥锁函数包括：
  • pthread_mutex_init：初始化互斥锁。
  • pthread_mutex_lock：锁定互斥锁。
  • pthread_mutex_unlock：解锁互斥锁。
  • pthread_mutex_destroy：销毁互斥锁。

2. 条件变量（Condition Variable）：

• 条件变量用于在线程之间进行通信，以便一个线程可以等待某个条件的发生，而其他线程可以通知条件的发生。

• 常见的条件变量函数包括：

  • pthread_cond_init：初始化条件变量。
  • pthread_cond_wait：等待条件的发生。
  • pthread_cond_signal：通知一个等待的线程条件已满足。
  • pthread_cond_broadcast：通知所有等待的线程条件已满足。
  • pthread_cond_destroy：销毁条件变量。

3. 信号量（Semaphore）：

• 信号量是一种计数器，用于控制多个线程对共享资源的访问。它允许多个线程同时访问资源，但可以限制同时访问的线程数量。

• 常见的信号量函数包括：

  • sem_init：初始化信号量。
  • sem_wait：等待信号量减小。
  • sem_post：增加信号量。
  • sem_destroy：销毁信号量。

4. 读写锁（Read-Write Lock）：

• 读写锁允许多个线程同时读取共享数据，但只允许一个线程写入数据。这有助于提高读取操作的并发性能。

• 常见的读写锁函数包括：

  • pthread_rwlock_init：初始化读写锁。
  • pthread_rwlock_rdlock：获取读取锁。
  • pthread_rwlock_wrlock：获取写入锁。
  • pthread_rwlock_unlock：释放锁。
  • pthread_rwlock_destroy：销毁读写锁。

5. 原子操作：

• 原子操作是不可中断的操作，通常由硬件提供支持。原子操作可以用来确保多线程环境下的数据一致性。

• 常见的原子操作包括原子增加、减少、比较并交换等。

实践过程