线程编程 王晓东 wangxiaodong@ouc.edu.cn 中国海洋大学 November 6, 2018 大纲 线程基础 线程控制 线程的同步 学习目标 1. 线程基础：理解任务调度、进程和线程，掌握其联系和区别； 掌握 Java 的线程模型，以及如何创建线程；理解后台线程。 2. 线程控制：理解线程的生命周期，明白各阶段的含义；掌握 线程控制方法，理解各线程控制方法对线程状态切换的作 相关知识回顾 线程的概念模型 创建线程 后台线程 线程控制 线程生命的周期 线程优先级 线程串行化 线程休眠 线程让步 线程挂起与恢复 线程等待与通知 线程的同步 大纲 线程基础 线程控制 线程的同步 ���� 线程基础 相关知识回顾 线程的概念模型 创建线程 后台线程 线程控制 线程生命的周期 线程优先级 线程串行化 线程休眠 线程让步 线程挂起与恢复 线程等待与通知 线程的同步 线程生命的周期 线程优先级 线程串行化 线程休眠 线程让步 线程挂起与恢复 线程等待与通知 线程的同步 大纲 线程基础 线程控制 线程的同步 相关知识回顾 概念回顾 O 任务调度 ▶ 大部分操作系统的任务调度是采用时间片轮转的抢占式调度 方式，一个任务执行一小段时间后强制暂停去执行下一个任 务，每个任务轮流执行。 ▶ CPU 的执行效率非常高，时间片非常短，在各个任务之间 快速地切换，

. . . 189 14.2.1 线程的生命周期 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 14.2.2 线程优先级 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 14.2.3 线程串行化 . . . . . . . . . . . 265 21.3.1 过滤器生命周期 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 21.4 过滤器的主要任务 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 xv 21.4.1 处理 HTTP 请求 . . . . 用来使程序从方法（函数）中返回，可返回一个值。 2.3 课后习题 . O 简答题 1. Java 语言定义类哪些基本数据类型？其存储结构分别是什么样的？ 2. 自动类型转换的前提是什么？转换时的优先级顺序如何？ 3. 数字字符串转换为数值类型数据时，可以使用的方法有哪些？ . O 小编程 1. 编写程序，从键盘输入一个浮点数，然后将该浮点数的整数部分输出。 2. 编写程序，从键盘输入 2

最差、最佳、平均时间复杂度 某些算法的时间复杂度不是固定的，而是与输入数据的分布有关。例如，假设输入一个长度为 ? 的数组 nums ，其中 nums 由从 1 至 ? 的数字组成，但元素顺序是随机打乱的；算法的任务是返回元素 1 的索引。我们可 以得出以下结论： ‧ 当 nums = [?, ?, ..., 1] ，即当末尾元素是 1 时，需要完整遍历数组，此时达到 最差时间复杂度 ?(?) 。 ‧ 当 要快速找到最近最少使用的数据，以及支持快速地添 加和删除节点。这时候使用双向链表就非常合适。 循环链表常被用于需要周期性操作的场景，比如操作系统的资源调度。 ‧ 时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一 组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循 环的操作就可以通过循环链表来实现。 ‧ 淘宝订单。购物者下单后，订单将加入队列中，系统随后会根据顺序依次处理队列中的订单。在双十一 期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。 ‧ 各类待办事项。任何需要实现“先来后到”功能的场景，例如打印机的任务队列、餐厅的出餐队列等。 队列在这些场景中可以有效地维护处理顺序。 5.3. 双向队列 对于队列，我们仅能在头部删除或在尾部添加元素。然而，「双向队列 Deque」提供了更高的灵活性，允许 在头部和尾部执行元素的添加或删除操作。

够完成简单算 法的复杂度分析。 2.2 迭代与递归 在算法中，重复执行某个任务是很常见的，它与复杂度分析息息相关。因此，在介绍时间复杂度和空间复杂 度之前，我们先来了解如何在程序中实现重复执行任务，即两种基本的程序控制结构：迭代、递归。 2.2.1 迭代 「迭代 iteration」是一种重复执行某个任务的控制结构。在迭代中，程序会在满足一定的条件下重复执行某 段代码，直到这个条件不再满足。 求和函数的递归过程 虽然从计算角度看，迭代与递归可以得到相同的结果，但它们代表了两种完全不同的思考和解决问题的范 式。 ‧ 迭代：“自下而上”地解决问题。从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成。 ‧ 递归：“自上而下”地解决问题。将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式。 接下来将子问题继续分解为更小的子问题，直到基本情况时停止（基本情况的解是已知的）。 以上述求和函数为例，设问题 函数调用自身 时间效 率 效率通常较高，无函数调用开销 每次函数调用都会产生开销 内存使 用 通常使用固定大小的内存空间 累积函数调用可能使用大量的栈帧空间 适用问 题 适用于简单循环任务，代码直观、可读性 好 适用于子问题分解，如树、图、分治、回溯等，代码结构简洁、 清晰 � 如果感觉以下内容理解困难，可以在读完“栈”章节后再来复习。 那么，迭代和递归具有什么内在联系呢

步的了解，以便能够完成简单算 法的复杂度分析。 2.2 迭代与递归 在数据结构与算法中，重复执行某个任务是很常见的，其与算法的复杂度密切相关。而要重复执行某个任务， 我们通常会选用两种基本的程序结构：迭代和递归。 2.2.1 迭代 「迭代 iteration」是一种重复执行某个任务的控制结构。在迭代中，程序会在满足一定的条件下重复执行某 段代码，直到这个条件不再满足。 1. for 求和函数的递归过程 虽然从计算角度看，迭代与递归可以得到相同的结果，但它们代表了两种完全不同的思考和解决问题的范 式。 ‧ 迭代：“自下而上”地解决问题。从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成。 ‧ 递归：“自上而下”地解决问题。将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式。 接下来将子问题继续分解为更小的子问题，直到基本情况时停止（基本情况的解是已知的）。 以上述的求和函数为例，设问题 最差、最佳、平均时间复杂度 算法的时间效率往往不是固定的，而是与输入数据的分布有关。假设输入一个长度为 ? 的数组 nums ，其中 nums 由从 1 至 ? 的数字组成，每个数字只出现一次；但元素顺序是随机打乱的，任务目标是返回元素 1 的 索引。我们可以得出以下结论。 ‧ 当 nums = [?, ?, ..., 1] ，即当末尾元素是 1 时，需要完整遍历数组，达到最差时间复杂度 ?(?) 。 ‧ 当 nums

信息计算其所属的 Distro 责任节点， 并将该请求转发到所属的 Distro 责任节点上。  责任节点上的 Controller 将写请求进行解析。  Distro 协议定期执行 Sync 任务，将本机所负责的所有的实例信息同步到其他节点上。 读操作 由于每台机器上都存放了全量数据，因此在每⼀次读操作中，Distro 机器会直接从本地拉取数据。 快速响应。 41 > Nacos 架构 配置⼀致性模型 sdk-server ⼀致性 53 > Nacos 架构 server 间⼀致性 Server 间同步消息接收处理轻量级实现，重试失败时，监控告警。 断网：断网太久，重试任务队列爆满时，无剔除策略。 2. 服务⼀致性模型 Nacos 架构 < 54 sdk-server 间⼀致性 server 间⼀致性 55 > Nacos 架构 六、核心模型组件设计 ​ 版本中，我们除了提供基于健康检查和权重的负载均衡方式外，还新提供了基于第 三方 CMDB 的标签负载均衡器，具体可以参考 CMDB 功能介绍文章。使用基于标签的负载均衡器， 目前可以实现同标签优先访问的流量调度策略，实际的应用场景中，可以用来实现服务的就近访问， 当您的服务部署在多个地域时，这非常有用。使用这个标签负载均衡器，可以支持非常多的场景， 这不是本文要详细介绍的。虽然目前 Nacos 里支持

能够完成简单算 法的复杂度分析。 2.2 迭代与递归 在算法中，重复执行某个任务是很常见的，它与复杂度分析息息相关。因此，在介绍时间复杂度和空间复杂 度之前，我们先来了解如何在程序中实现重复执行任务，即两种基本的程序控制结构：迭代、递归。 2.2.1 迭代 迭代（iteration）是一种重复执行某个任务的控制结构。在迭代中，程序会在满足一定的条件下重复执行某段 代码，直到这个条件不再满足。 求和函数的递归过程 虽然从计算角度看，迭代与递归可以得到相同的结果，但它们代表了两种完全不同的思考和解决问题的范 式。 ‧ 迭代：“自下而上”地解决问题。从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成。 ‧ 递归：“自上而下”地解决问题。将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式。 接下来将子问题继续分解为更小的子问题，直到基本情况时停止（基本情况的解是已知的）。 以上述求和函数为例，设问题 函数调用自身 时间效 率 效率通常较高，无函数调用开销 每次函数调用都会产生开销 内存使 用 通常使用固定大小的内存空间 累积函数调用可能使用大量的栈帧空间 适用问 题 适用于简单循环任务，代码直观、可读性 好 适用于子问题分解，如树、图、分治、回溯等，代码结构简洁、 清晰 Tip 如果感觉以下内容理解困难，可以在读完“栈”章节后再来复习。 那么，迭代和递归具有什么内在联

能够完成简单算 法的复杂度分析。 2.2 迭代与递归 在算法中，重复执行某个任务是很常见的，它与复杂度分析息息相关。因此，在介绍时间复杂度和空间复杂 度之前，我们先来了解如何在程序中实现重复执行任务，即两种基本的程序控制结构：迭代、递归。 2.2.1 迭代 迭代（iteration）是一种重复执行某个任务的控制结构。在迭代中，程序会在满足一定的条件下重复执行某段 代码，直到这个条件不再满足。 求和函数的递归过程 虽然从计算角度看，迭代与递归可以得到相同的结果，但它们代表了两种完全不同的思考和解决问题的范 式。 ‧ 迭代：“自下而上”地解决问题。从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成。 ‧ 递归：“自上而下”地解决问题。将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式。 接下来将子问题继续分解为更小的子问题，直到基本情况时停止（基本情况的解是已知的）。 以上述求和函数为例，设问题 函数调用自身 时间效 率 效率通常较高，无函数调用开销 每次函数调用都会产生开销 内存使 用 通常使用固定大小的内存空间 累积函数调用可能使用大量的栈帧空间 适用问 题 适用于简单循环任务，代码直观、可读性 好 适用于子问题分解，如树、图、分治、回溯等，代码结构简洁、 清晰 Tip 如果感觉以下内容理解困难，可以在读完“栈”章节后再来复习。 那么，迭代和递归具有什么内在联

口。 FOAAS. http://www.foaas.com/ Linux的特点 n Linux is free n 开放性 n 可靠的系统安全 n 良好的可移植性 n 多用户性 n 多任务 n 良好的用户界面 n 设备独立性 n 强大的网络功能 n Linux的版本一般指内核版本； n Linux通过不通的命名机制来区分内核类别，采用三个由“.”分割的数字来表示内核 版本号 它是一个实时的Linux版本。由于Linux2.6版本之前是不可 抢占式，不能真正实现实时应用。RT-Linux用巧妙的方式解决了此 问题，它并没有重写Linux的内核，而是实现了一个高效的可抢占式 实时调度核心并把Linux作为此核心的一个优先级最低的进程运行， 用户可以编写自己的实时进程，和标准的Linux共同运行。 Android n 架构 Linux Kernel Google vs Oracle：Java版权之争 采用该种方式的发行版有Ubuntu（6.10 and later），Fedora（9.10 and later）， Debian（optional）。 n Upstart基于事件机制，系统的所有服务、任务都是由事件驱动的。 System V 启动流程依赖/etc/inittab，init进程启动后第一时间找inittab，根据inittab中的配置初 始化系统，设置系统runlevel及进入各runlevel对应要执行的命令。

最差、最佳、平均时间复杂度 某些算法的时间复杂度不是恒定的，而是与输入数据的分布有关。举一个例子，输入一个长度为 ? 数组 nums ， 其中 nums 由从 1 至 ? 的数字组成，但元素顺序是随机打乱的；算法的任务是返回元素 1 的索引。我们可以得 出以下结论： ‧ 当 nums = [?, ?, ..., 1]，即当末尾元素是 1 时，则需完整遍历数组，此时达到 最差时间复杂度 ?(?) ； ‧ 当 后系统再根据顺序依次处理队列中的订单。在 双十一时，在短时间内会产生海量的订单，如何处理「高并发」则是工程师们需要重点思考的问题。 ‧ 各种待办事项。任何需要实现“先来后到”的功能，例如打印机的任务队列、餐厅的出餐队列等等。 5.3. 双向队列 对于队列，我们只能在头部删除或在尾部添加元素，而「双向队列 Deque」更加灵活，在其头部和尾部都能 执行元素添加或删除操作。 5. 栈与队列 null) return; // 访问优先级：根结点 -> 左子树 -> 右子树 list.add(root.val); preOrder(root.left); preOrder(root.right); } /* 中序遍历 */ void inOrder(TreeNode root) { if (root == null) return; // 访问优先级：左子树 -> 根结点 -> 右子树