什么是naive bayes 朴素贝叶斯 naive bayes，是一种概率类的机器学习算法，主要用于解决分类问题 为什么被称为朴素贝叶斯？ 为什么被称为朴素，难道仅仅是因为贝叶斯很天真吗？实际上是因为，朴素贝叶斯会假设数据属性之间具有很强的的独立性。即该模型中的所有属性彼此之间都是独立的，改变一个属性的值，不会直接影响或改变算法中其他的属性的值 贝叶斯定理 了解朴素贝叶斯之前，需要掌握一些概念才可继续 条件概率 Conditional probability：在另一个事件已经发生的情况下，另外一个时间发生的概率。如，==在多云天气，下雨的概率是多少？== 这是一个条件概率 联合概率 Joint Probability：计算两个或多个事件同时发生的可能性 边界概率 Marginal Probability：事件发生的概率，与另一个变量的结果无关 比例 Proportionality 贝叶斯定理 Bayes' Theorem：概率的公式；贝叶斯定律是指根据可能与事件的先验概率描述了事件的后验概率 边界概率 边界概率是指事件发生的概率，可以认为是无条件概率。不以另一个事件为条件；用公式表示为 $P(X)$ 如：抽到的牌是红色的概率是 $P(red) = 0.5$ ； 联合概率 联合概率是指两个事件在同一时间点发生的可能性，公式可以表示为 $P(A \cap B)$ A 和 B 是两个不同的事件相同相交，$P(A \and B)$ $P(A,B)$ = A 和 B 的联合概率 概率用于处理事件或现象发生的可能性。它被量化为介于 0 和 1 之间的数字，其中 0 表示不可能发生的机会，1 表示事件的一定结果。 如，从一副牌中抽到一张红牌的概率是 $\frac{1}{2}$。这意味着抽到红色和抽到黑色的概率相同；因为一副牌中有52张牌，其中 26 张是红色的，26 张是黑色的，所以抽到一张红牌与抽到一张黑牌的概率是 50%。 而联合概率是对测量同时发生的两个事件，只能应用于可能同时发生多个情况。例如，从一副52张牌扑克中，拿起一张既是红色又是6的牌的联合概率是 $P(6\cap red) = \frac{2}{52} = \frac{1}{26}$ ；这个是怎么得到的呢？因为抽到红色的概率为50%，而一副牌中有两个红色6（红桃6，方片6），而6和红色是两个独立的概率，那么计算公式就为：$P(6 \cap red) = P(6) \times P(red) = \frac{4}{52} \times \frac{26}{52} = \frac{1}{26}$...

Overview 逻辑回归通常用于分类算法，例如预测某事是 true 还是 false（二元分类）。例如，对电子邮件进行分类，该算法将使用电子邮件中的单词作为特征，并据此预测电子邮件是否为垃圾邮件。用数学来讲就是指，假设因变量是 Y，而自变量集是 X，那么逻辑回归将预测因变量 $P(Y=1)$ 作为自变量集 X 的函数。 逻辑回归性能在线性分类中是最好的，其核心为基于样本属于某个类别的概率。这里的概率必须是连续的并且在 (0, 1) 之间（有界）。它依赖于阈值函数来做出称为 Sigmoid 或 Logistic 函数决定的。 学好逻辑回归，需要了解逻辑回归的概念、优势比 (OR) 、Logit 函数、Sigmoid 函数、 Logistic 函数及交叉熵或Log Loss Prerequisite odds ratio explain odds ratio是预测变量的影响。优势比取决于预测变量是分类变量还是连续变量。 连续预测变量：$OR > 1$ 表示，随着预测变量的增加，事件发生的可能性增加。$OR < 1$ 表示随着预测变量的增加，事件发生的可能性较小。 分类预测变量：事件发生在预测变量的 2 个不同级别的几率；如 A,B，$OR > 1$ 表示事件在 A 级别的可能性更大。$OR<1$ 表示事件更低的可能是在A。 例如，假设 X 是受影响的概率，Y 是不受影响的概率，则 $OR= \frac{X}{Y}$ ，那么 $OR = \frac{P}{(1-P)}$ ，P是事件的概率。 让概率的范围为 [0,1] ，假设 $P(success)=0.8$ ，$Q(failure) = 0.2$ ；$OR$ 则是 成功概率和失败概率的比值，如：$O(success)=\frac{P}{Q} = \frac{0....

熵和基尼指数 信息增益 信息增益 information gain 是用于训练决策树的指标。具体来说，是指这些指标衡量拆分的质量。通俗来说是通过根据随机变量的给定值拆分数据集来衡量熵。 通过描述一个事件是否"惊讶"，通常低概率事件更令人惊讶，因此具有更大的信息量。而具有相同可能性的事件的概率分布更"惊讶"并且具有更大的熵。 定义：熵 entropy是一组例子中杂质、无序或不确定性的度量。熵控制决策树如何决定拆分数据。它实际上影响了决策树如何绘制边界。 熵 熵的计算公式为：$E=-\sum^i_{i=1}(p_i\times\log_2(p_i))$ ；$P_i$ 是类别 $i$ 的概率。我们来举一个例子来更好地理解熵及其计算。假设有一个由三种颜色组成的数据集，红色、紫色和黄色。如果我们的集合中有一个红色、三个紫色和四个黄色的观测值，我们的方程变为：$E=-(p_r \times \log_2(p_r) + p_p \times \log_2(p_p) + p_y \times \log_2(p_y)$ 其中 $p_r$ 、$p_p$ 和 $p_y$ 分别是选择红色、紫色和黄色的概率。假设 $p_r=\frac{1}{8}$，$p_p=\frac{3}{8}$ ，$p_y=\frac{4}{8}$ 现在等式变为变为： $E=-(\frac{1}{8} \times \log_2(\frac{1}{8}) + \frac{3}{8} \times \log_2(\frac{3}{8}) + \frac{4}{8} \times \log_2(\frac{4}{8}))$ $0.125 \times log_2(0.125) + 0.375 \times log_2(0.375) + 0.5 \times log_2(0.375)$ $0.125 \times -3 + 0.375 \times -1.415 + 0.5 \times -1 = -0.375+-0.425 +-0.5 = 1....

决策边界 (decision boundary) 支持向量机获取这些数据点并输出最能分离标签的超平面。这条线是决策边界 决策平面 （ decision surface ），是将空间划分为不同的区域。位于决策平面一侧的数据被定义为与位于另一侧的数据属于不同的类别。决策面可以作为学习过程的结果创建或修改，它们经常用于机器学习、模式识别和分类系统。 环境空间 ( Ambient Space)，围绕数学对象即对象本身的空间，如一维 Line ，可以独立研究，这种情况下L则是L；再例如将L作为二维空间 $R^2$ 的对象进行研究，这种情况下 L 的环境空间是 $R^2$。 超平面（Hyperplane）是一个子空间， N维空间的超平面是其具有维数的平面的子集。就其性质而言，它将空间分成两个半空间，其维度比其环境空间的维度小 1。如果空间是三维的，那么它的超平面就是二维维平面，而如果空间是 2 维的，那么它的超平面就是一维线。支持向量机 (SVM) 通过找到使两个类之间的边距最大化的超平面来执行分类。 法向量 （Normal） 是垂直于该平面、另一个向量的 90° 角倾斜 什么是支持向量 支持向量 （Support vectors），靠近决策平面（超平面）的数据点。 如图所示，从一维平面来看，哪个是分离的超平面？ 一般而言，会有很多种解决方法（超平面），支持向量机就是如何找到最佳方法的解决方案。 转置运算 矩阵的转置是原始矩阵的翻转版本，可以通过转换矩阵的行和列来转置矩阵。我们用 $A^T$ 表示矩阵 A 的转置。例如， $$A=\left[ \begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ \end{matrix} \right]$$ ；那么 A 的转置就为 $$A=\left[ \begin{matrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \\ \end{matrix} \right]$$ ；...

Overview K近邻值算法 KNN (K — Nearest Neighbors) 是一种机器学习中的分类算法；K-NN是一种非参数的惰性学习算法。非参数意味着没有对基础数据分布的假设，即模型结构是从数据集确定的。 它被称为惰性算法的原因是，因为它**不需要任何训练数据点来生成模型。**所有训练数据都用于测试阶段，这使得训练更快，测试阶段更慢且成本更高。 如何工作 KNN 算法是通过计算新对象与训练数据集中所有对象之间的距离，对新实例进行分类或回归预测。然后选择训练数据集中距离最小的 K 个示例，并通过平均结果进行预测。 如图所示：一个未分类的数据（红色）和所有其他已分类的数据（黄色和紫色），每个数据都属于一个类别。因此，计算未分类数据与所有其他数据的距离，以了解哪些距离最小，因此当K= 3 （或K= 6 ）最接近的数据并检查出现最多的类，如下图所示，与新数据最接近的数据是在第一个圆圈内（圆圈内）的数据，在这个圆圈内还有 3 个其他数据（已经用黄色分类），我们将检查其中的主要类别，会被归类为紫色，因为有2个紫色球，1个黄色球。 KNN算法要执行的步骤 将数据分为训练数据和测试数据 选择一个值 K 确定要使用的距离算法 从需要分类的测试数据中选择一个样本，计算到它的 n 个训练样本的距离。 对获得的距离进行排序并取 k最近的数据样本。 根据 k 个邻居的多数票将测试类分配给该类。 影响KNN算法性能的因素 用于确定最近邻居的距离的算法 用于从 K 近邻派生分类的决策规则 用于对新示例进行分类的邻居数 如何计算距离 测量距离是KNN算法的核心，总结了问题域中两个对象之间的相对差异。比较常见的是，这两个对象是描述主题（例如人、汽车或房屋）或事件（例如购买、索赔或诊断）的数据行。 汉明距离 汉明距离（Hamming Distance）计算两个二进制向量之间的距离，也简称为二进制串 binary strings 或位串 bitstrings ；换句话说，汉明距离是将一个字符串更改为另一个字符串所需的最小替换次数，或将一个字符串转换为另一个字符串的最小错误数。 示例：如一列具有类别 “红色”、“绿色” 和 “蓝色”，您可以将每个示例独热编码为一个位串，每列一个位。 注：独热编码 one-hot encoding：将分类数据，转换成二进制向量表示，这个二进制向量用来表示一种特殊的bit（二进制位）组合，该字节里，仅容许单一bit为1，其他bit都必须为0 如： apple banana pineapple 1 0 0 0 1 0 0 0 1 100 表示苹果，100就是苹果的二进制向量 010 表示香蕉，010就是香蕉的二进制向量...

之前了解了client-go中的架构设计，也就是 tools/cache 下面的一些概念，那么下面将对informer进行分析 Controller 在client-go informer架构中存在一个 controller ，这个不是 Kubernetes 中的Controller组件；而是在 tools/cache 中的一个概念，controller 位于 informer 之下，Reflector 之上。code Config 从严格意义上来讲，controller 是作为一个 sharedInformer 使用，通过接受一个 Config ，而 Reflector 则作为 controller 的 slot。Config 则包含了这个 controller 里所有的设置。 go 1 2 3 4 5 6 7 8 9 type Config struct { Queue // DeltaFIFO ListerWatcher // 用于list watch的 Process ProcessFunc // 定义如何从DeltaFIFO中弹出数据后处理的操作 ObjectType runtime.Object // Controller处理的对象数据，实际上就是kubernetes中的资源 FullResyncPeriod time.Duration // 全量同步的周期 ShouldResync ShouldResyncFunc // Reflector通过该标记来确定是否应该重新同步 RetryOnError bool } controller 然后 controller 又为 reflertor 的上层...

Preparation debian11几乎可以使用任何旧的计算机硬件，因为最小安装的要求非常低。以下是最低要求和推荐要求： 最低要求 推荐要求 存储：10 Gigabytes 内存：512 Megabytes CPU: 1 GigaHertz 存储：10 Gigabytes内存：2 GigabytesCPU: 1 GigaHertz or more Debian11 EOL：August 31st, 2026 如何选择下载安装包 offical mirror aliyun mirror 官网提供了安装包的下载，其中CD是网络安装，DVD是离线安装 debian官方下载页面 Notes：CD安装包很小，下载下来是 debian-11.4.0-amd64-netinst.iso 如名所示，这是一个网络安装包，所以推荐下载DVD部分，可以达到离线安装的效果 安装步骤 在界面中选择“Install”，安装将开始。如果图形化安装可以选择“Graphical install”，这里选择“Install”。 欢迎页面 完成后，系统将提示选择安装时的“语言”。选择喜欢的语言，然后按“Enter”。这里选择英文 选择语言页面 这将是接下来安装步骤 安装步骤概述 选择位置与键盘布局 选择区域 选择区域 下面部署时选择键盘布局：中国大陆使用的键盘布局是美国-英语，不要选择英国-英语之类，布局是不一样的，会存在按键输出的结果会不同 选择键盘布局 完成上述操作后，将开始加载镜像。等待扫描完成。。。。 等待扫描组件 设置主机名和域名 这步骤中将配置一个“主机名”。与一个“域”名称。 配置主机名 “域” 可以选择留空确定 配置域 完成上述操作后，安装程序将提示需要设置 root 密码。输入您的 root 密码，然后在重新输入以进行验证后继续。 设置Root密码 设置非ROOT用户名、账户和密码 下一步创建一个非ROOT用户，这个步骤是必须的，并为这个新创建的帐户分配一个密码。以下截图将描述将如何完成此操作。 配置普通用户 为这个用户配置密码 为普通用户配置密码 为普通用户配置密码——二次确认 设置时钟时区 Eastern 美东时间 Central 北美中部...

Prepare Introduction 从2016年8月起，Kubernetes官方提取了与Kubernetes相关的核心源代码，形成了一个独立的项目，即client-go，作为官方提供的go客户端。Kubernetes的部分代码也是基于这个项目的。 client-go 是kubernetes中广义的客户端基础库，在Kubernetes各个组件中或多或少都有使用其功能。。也就是说，client-go可以在kubernetes集群中添加、删除和查询资源对象（包括deployment、service、pod、ns等）。 在了解client-go前，还需要掌握一些概念 在客户端验证 API 使用证书和使用令牌，来验证客户端 kubernetes集群的访问模式 使用证书和令牌来验证客户端 在访问apiserver时，会对访问者进行鉴权，因为是https请求，在请求时是需要ca的，也可以使用 -k 使用insecure模式 text 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 $ curl --cacert /etc/kubernetes/pki/ca.crt https://10.0.0.4:6443/version \{ "major": "1", "minor": "18+", "gitVersion": "v1.18.20-dirty", "gitCommit": "1f3e19b7beb1cc0110255668c4238ed63dadb7ad", "gitTreeState": "dirty", "buildDate": "2022-05-17T12:45:14Z", "goVersion": "go1.16.15", "compiler": "gc", "platform": "linux/amd64" } $ curl -k https://10....

疫情期间上网课，对于英语听力较差或者需要观看英文视频，但实际上并没有双语字幕的这种情况下需要找一个实时的翻译工具。虽然说手机上此类软件比较多，但电脑上没有特别合适的应用可以做为一个免费实时翻译。哪怕是收费翻译工具实际上翻译效果也是很差，并且语种比较单一。 电脑端有一个 speechlogger，可以做到实时翻译，但实际上也是使用的Google翻译，那么实际上我们就可以直接使用Google翻译作为一个同声翻译电脑的声音。 此时就遇到一个问题，就是Google翻译无法识别到电脑的声音，只能识别到麦克风的声音。这里就需要将电脑输出的作为麦克风的输出。使用Windows电脑的可以尝试以下操作。 以windows电脑为例： Step 1：电脑右下角调整音量图标，右键选择声音 Step2：选择录音设备，立体声混音，将其启动并设置为默认设备（可选） Step3：右键属性，选择侦听，通过此设备播放选择扬声器对应的设备。 Tips：注意，无用选择侦听此设备，这个选项勾选后的意思是，你可以通过扬声器听到扬声器声音，此时会发生混音。影响我们听到的效果。 Step4：可选步骤，如果Step2没有设置为默认设备，可以在浏览器选择对应的设备作为麦克风，如使用了立体声混音作为电脑的输入设备，那么不是默认设备情况下在浏览器选择该设备作为输入设备即可。 Tips：Google翻译的语音翻译功能貌似只能在Chrome里使用，其他有可能会出现无法使用语音设备的功能 这样就做到了一个免费，无杂音，多语种的同声翻译，不管是上网课学习，还是说做笔记（同语言下还可以作为声音转换为文字）都是一个很不错的选择。 后面再说下，科大讯飞的录音设备实际上翻译功能很差，语种也少，并且专业术语翻译的很烂，最便宜的小2000块钱，大量依赖云服务，实际上可以不用买这种产品，我是已经买过体验的，翻译结果实际上比Google翻译要差。如果不是在现场，没有网络或者声音很嘈杂（他的十几个麦克风其实效果也不咋地）的情况下可以选择其他方案，例如Google的同声翻译。 如果你需要对翻译的结果划分角色的话，还是可以使用 speechlogger，这个也是使用的Google翻译作为翻译引擎的 Reference 如何将电脑的输出作为电脑麦克风的输入 免费的实时翻译工具

背景 由于Windows10 开启WSL2后无法和 eNSP 做到兼容，但是 H3C HCL 在版本 HCL_v2.1.2.1 提供了 VirtualBox 6.0.14 作为虚拟化后端，理论上来说可以做到 WSL2 与 HCL 共存。 并且开启了WSL2后并于其他虚拟化平台（VirtualBox, Vmvare）做到兼容的情况下，这种情况大部分禁止套娃（虚拟化下在虚拟化），通过安装虚拟机的方式再安装 eNSP 发现启动不报错，但是很长时间起不来。 Notes [1]：HCL官方给的建议是，对于windows7装的版本为HCL_v2.1.1；对于Windows10 并且开启了 Hype-v 或者 Dokcer-Desktop，推荐使用 HCL_v3.0.1.1 下载地址：HCL Download 安装过程 下载好安装时，直接下一步直至完成即可，VirtualBox已被内嵌至安装包内了。 图：HCL安装界面 Notes：如果需要抓包，自行安装Wireshark，安装好后，在HCL设置中配置 wireshark.exe 的路径即可 VirtualBox启用hyper-v支持 [2] 进入VirtualBox安装目录, 确定当前目录下存在VBoxManage.exe文件, 在当前目录打开powershell. 或者你将VBoxManage.exe所在目录加入环境变量, 任意路径下打开powershell. powershell 1 2 # 或指定vbox所有虚拟系统开启 ./VBoxManage.exe setextradata global "VBoxInternal/NEM/UseRing0Runloop" 0 开启后，HCL所有的设备就工作正常了，这种情况下也不用牺牲WSL2或者Dokcer-Desktop。因为eNSP官方没有再更新，导致hype-v与VirtualBox无法兼容，暂时无解。 Reference ​[1] H3C Cloud Lab ​[2] Windows 10 (2004) 启用wsl2, 并与VirtualBox 6.0+共存

APIServer 在kubernetes架构概念层面上，Kubernetes由一些具有不同角色的服务节点组成。而master的控制平面由 Apiserver Controller-manager 和 Scheduler 组成。 Apiserver 从概念上理解可以分为 api 和 object 的集合，api 可以理解为，处理读写请求来修改相应 object 的组件；而 object 可以表示为 kubernetes 对象，如 Pod， Deployment 等 。 基于声明式的API 在命令式 API 中，会直接发送要执行的命令，例如：运行、停止 等命令。在声明式API 中，将声明希望系统执行的操作，系统将不断将自身状态朝希望状态改变。 为什么使用声明式 在分布式系统中，任何组件随时都可能发生故障，当组件故障恢复时，需要明白自己需要做什么。在使用命令式时，出现故障的组件可能在异常时错过调用，并且在恢复时需要其他外部组件进行干预。而声明式仅需要在恢复时确定当前状态以确定他需要做什么。 External APIs 在kubernetes中，控制平面是透明的，及没有internal APIs。这就意味着Kubernetes组件间使用相同的API交互。这里通过一个例子来说明外部APIs与声明式的关系。 例如，创建一个Pod对象，Scheduler 会监听 API来完成创建，创建完成后，调度程序不会命令被分配节点启动Pod。而在kubelet端，发现pod具有与自己相同的一些信息时，会监听pod状态。如改变kubelet则修改状态，如果删除掉Pod（对象资源不存在与API中），那么kubelet则将终止他。 为什么不使用Internal API 使用External API可以使kubernetes组件都使用相同的API，使得kubernetes具有可扩展性和可组合性。对于kubernetes中任何默认组件，如不足满足需求时，都可以更换为使用相同API的组件。 另外，外部API还可轻松的使用公共API来扩展kubernetes的功能 API资源 从广义上讲，kubernetes对象可以用任何数据结构来表示，如：资源实例、配置（审计策略）或持久化实体（Pod）；在使用中，常见到的就是对应YAML的资源清单。转换出来就是RESTful地址，那么应该怎么理解这个呢？即，对资源的动作（操作）如图所示。但如果需要了解Kubernetes API需要掌握一些概念才可继续。 Group 出于对kubernetes扩展性的原因，将资源类型分为了API组进行独立管理，可以通过 kubectl api-resources查看。在代码部分为 vendor/k8s.io/api 也可以通过 kubectl xxx -v 6 来查看 kubectl 命令进行了那些API调用 text 1 2 3 4 5 6 7 8 9 10 11 $ kubectl get pods -v 6 I0513 21:54:33....

本地构建 选择要构建的版本 text 1 git checkout tags/v1.19.5 将依赖包复制到对应路径下 text 1 cp staging/src/k8s.io vendor/ 调整makefile 在windows上编译的克隆下可能文件编码变了，需要手动修改下文件编码。比如说出现 \r not found 类似关键词时 这里转换编码使用了 dos2unix，需要提前安装下 text 1 apt install dos2unix 转换原因是因为对于bash 脚本执行识别不了windows的换行 text 1 find . -name '*.sh' -exec dos2unix {} \; 然后将 build/root/ 的文件复制到项目根目录 text 1 cp build/root/Makefile* ./ 编译 查看帮助 make help 编译 make all WHAT=cmd/kube-apiserver GOFLAGS=-v WHAT=cmd/kube-apiserver 为仅编译单一组件，all 为所有的组件 还可以增加其他的一些环境变量 KUBE_BUILD_PLATFORMS= 如编译的平台 更多的可以 make help 查看帮助 编译中问题 Makefile:93: recipe for target ‘all’ failed...

Overview 文件系统和文件 文件系统: 一种用于持久性存储的系统抽象，决定了辅存中的内容如何组织与存储的抽象概念 文件：文件系统中的一个单元的相关数据在操作系统中的抽象，展现给用户的抽象概念 文件系统的功能： 分配文件磁盘空间 管理文件块(哪一块属于哪一个文件) 管理空闲空间(哪一块是空闲的) 分配算法(策略) 管理文件集合 定位文件及其内容 命名：通过名字找到文件的接口 最常见：分层文件系统 文件系统类型(组织文件的不同方式) 提供的便利及特征 保护：分层来保护数据安全 可靠性，持久性：保持文件的持久即使发生崩溃,媒体错误,攻击等 为什么需要文件系统： 如果将文件放入一个房间中，整个房间都是堆积的文件 有了文件系统的存在将会改变一切 空间管理、元数据、数据加密、文件访问控制和数据完整性等等都是文件系统的职责。 文件属性 文件具有名称和数据，还存储文件创建日期和时间、当前大小、上次修改日期等元信息。所有这些信息都称为文件系统的属性。常见的文件属性有 名称：它是以人类可理解的形式。 标识符：每个文件都由文件系统中的唯一标记号标识，称为标识符。 位置：设备上的文件位置。 类型：支持各种类型文件的系统需要此属性。 大小：当前文件大小的属性。 保护：分配和控制读、写和执行文件的访问权限。 时间、日期和安全：用于对文件的保护、安全，也用于监控 文件描述符 文件头 File Header；类似于Unix的 inode，在存储元数据中保存了每个文件的信息，保存文件的属性，跟踪哪一块存储块属于逻辑上文件结构的哪个偏移 文件描述符 （file-descriptor）；是唯一标识操作系统中打开文件的数字（整形），用于用户和内核空间之间的接口，以识别 文件/Socket 资源。因此，当使用 open() 或 socket()（与内核接口的系统调用）时，会得到一个文件描述符，一个整数。因此，如果直接与内核交互，使用系统调用 read(), write() 等 close()。使用的是一个文件描述符句柄。 在 C 语言中 stdin，stdout、 和 stderr ，在 UNIX 中分别映射到文件描述符 0 1 2 text 1 2 3 4 5 f = open(name, flag); ... ....

Overview 进程间是相互保持独立的，内存管理中，就是保护进程的地址空间不被其他进程访问。而进程间通信 ( Inter-process Communication IPC) 用于在一个或多个进程间交换数据 进程间合作是那些可以影响或受其他过程影响的过程。例如网站包含 JS、H5、Flash，当有一个相应缓慢时，会发生整个网站的布局或其他功能的展示。 通常情况下进程间合作被允许的原因有： 信息共享：多个进程需要访问同一个文件。（如管道） 计算加速：将复杂功能拆分为多个子任务（多处理器时效果更佳），可以更快地解决问题 模块化：将整体系统架构分为不同功能模块，模块间相互协作 便利：单用户可以同时多任务处理，如 编辑、编译、打印等 Communications model (a) 消息队列（间接通信）                 (b) 共享内存（直接通信） Message Passing IPC背后关键的一点是消息的传递，即一个进程发消息，一个进程接收消息 而为了使进程间通信，就必须在进程间建立连接，连接可以是单/双向。连接可以使用直接通信和间接通信来实现 Direct Communication 直接通信，必须明确声明发送者或接收者的名称，通常定义为： Send(P, message)：发送信息到进程 P Receive(Q, message)：接收来自进程 Q 的信息 在直接通信中，一般连接的属性有以下特征： 一个链路与一对进程相关联 自动建立链接 链接是通用的双向链接 Indirect Communication 间接通信，为异步通信，通常情况下互通信都需要有消息队列；发送者将信息放置消息队列中，接受者从消息队列中取出消息 Send(P, message)：像消息队列发送消息 Receive(Q, message)：接受消息队列中的消息 每个进程都有唯一ID 共享一个消息队列 在间接通信中，一般连接的属性有以下特征： 一对进程共享消息队列时，才会在进程之间建立链接 链接可以被许多进程关联 链接可以是单向也可以是双向 每个进程可以有多个链接   直接通信                                            间接通信 Synchronization 从另一方面来讲，消息传递可以是阻塞 Blocking 或非阻塞 Non-Blocking 的；同步 synchronous 会阻塞一个进程，直到发送完成。异步 asynchronous 则是是非阻塞的，发送操作完成后会立即返回不等待返回结果 Buffer 消息通过队列传递，队列的容量则具有下列三种配置之一： 0容量：消息不能存储在队列中，因此发送者必须阻塞，直到接收者接受消息 有限容量：队列中有一定的预先约定大小的容量。如果队列已满，发送者必须阻塞，直到队列中有可用空间（反之为空，接受者阻塞），否则可能是阻塞的或非阻塞的 无限容量：具有无限容量的队列，发送者永远不会被迫阻塞 至此整节围绕对消息传递功能的三个方面做了介绍：...

死锁问题 死锁 deadlock；是一组阻塞的进程，每个进程都持有一个资源并等待获取另一个进程持有的资源。 死锁的示例：交通桥 如图所示，桥是资源，进程是车辆，两个不同方向的车辆同时占用桥，此时发生谁也过不去的情况（死锁的发生）； 当死锁发生时，如果一辆车倒车（抢占资源和回滚）就可以解决死锁问题 死锁发生时，可能需要后退多台车辆 饥饿，而饥饿并不一定是死锁 系统模型 在正常情况下，进程必须在使用之前请求资源，并在完成后释放它，顺序如下： 请求：如果不能立即授予请求，则进程等待，直到它需要的资源变得可用。例如，系统调用 open()、malloc()、new() 、request() 等。 使用：进程使用资源，例如文件中读取数据；使用硬件。 释放：进程完成后放弃资源，以便其可用于其他进程。如，close()、free()、delete() 、 release()。 当在集合中的每个进程都在等待当前分配给集合中另一个进程的资源时，这一组进程就会发生死锁 资源分配 通过实例来理解死锁， 一组资源： ${ R_1,\ R_2,\ R_3,\ ….,\ R_N }$；为方形，图形内的点代表资源数量 一组进程： ${ P_1,\ P_2,\ P_3,\ ….,\ P_N }$ 请求边缘 Request Edge：进程需要一些资源，被称为请求边缘；如 $P_i\ →\ R_j$ 分配边缘 Assign Edge：当资源已经被分配给进程，被称为分配边缘；如 $R_j\ →\ P_i$ 当请求被授予时，可以通过反转方向的线将请求边缘转换为分配边缘 类型 示意图 Process Resource $P_i$ 请求的 $R_j$ 实例 $P_i$ 持有一个 $R_j$ 的实例 也可以说 $R_j$ 被 $P_i$ 所持有 资源分配图 资源分配图 如图所示，资源类型为：...

Backgound 信号量 semaphores，是操作系统中非常重要的技术，通过使用一个简单的整数值来管理并发进程，信号量只是一个在线程之间共享的整数变量。该变量用于解决临界区问题并实现进程同步。 信号量具有两个原子操作： P()：sem减一，如果sem<0，等待；否则继续 V()：sem加一，如果sem≤0，唤醒一个等待的P； Semaphore 信号量的使用 型号量的特点： 两个类型信号量 二进制信号量 Binary Semaphore：也称为互斥锁。它只能有两个值0和1。它的值被初始化为1。它用于实现多进程临界区问题的解决。 计数信号量 Counting Semaphore：值可以跨越一个不受限制的域（可以取任何非负数）。它用于控制对具有多个实例的资源的访问。 信号量是被保护的变量 初始化完成后，唯一改变一个信号量的值的办法是通过P() 和 V() 操作必须是原子 P() 能够阻塞，V() 不会阻塞 信号量可以用在2个方面 互斥 条件同步(调度约束 —— 一个线程等待另一个线程的事情发生) 信号量实现的互斥 c 1 2 3 4 5 6 7 mutex = new Semaphore(1); mutex->P(); // 临界区前p ... critical section ... mutex->V(); // 临界区后v 信号量实现调度约束 c 1 2 3 4 5 6 7 8 9 10 condition = new Semaphore(0); // Thread A ....

Background 多进程作为现代操作系统的重要特性，交互则会引起同时对共享资源的访问，当这些资源访问不正确会出现冲突或产生不适当的输出（冲突、死锁、饥饿）；而在同步的基础上，进程被分为以下两种类型： 独立进程 Independent Process 不和其他进程共享资源或状态 确定性，输入状态确定结果 可重现，能够重现起始条件，I/O 调度的顺序不重要 协作进程 Cooperative Process； 多进程共享资源或状态 不确定性 probabilistic 不可重现 不确定性和不可重现意味着bug可能是间歇性发生的 Cooperation 进程的互相影响，即进程间的合作（相互或破坏）；最简单的例子就是两个进程使用同一个文件，一个进程读，一个进程写。读进程的结果会被写进程所影响。 进程需要合作的原因： 资源共享：多个进程访问相同的数据 一台电脑，多个用户 一个银行存款余额,多台ATM机 嵌入式系统（机器人手臂和收的协调） 计算加速： I/O 和 CPU计算可重叠 多处理器 - 将任务分解为子任务并分布在不同的进程中，它通常可以更快地运行（也需要多个可共享的 CPU） 模块化：复杂的任务组织成单独的子任务，让不同的进程运行 大程序分成小程序 是系统易于扩展 程序可以调用函数fork()来创建一个新的进程 操作系统需要分配一个新的并且唯一的进程ID 因此在内核中,这个系统调用会运行 new_pid = next_pid++; 翻译成机器指令: Load next_pid Reg1 STORE Reg1 new_pid INC Reg1 STORE Reg1 next_pid 假设两个进程并发执行 如果next_pid等于100, 那么其中一个进程得到的ID应该是100, 另一个进程的ID应该是101, next_pid应该增加到102 可能在INC前进行了上下文切换, 最终导致两个进程的pid都是100,而next_pid也是101 无论多个线程的指令序列怎样交替执行,程序都必须正常工作 多线程程序具有不确定性和不可重现的特点 不经过专门设计,调试难度很高 不确定性要求并行程序的正确性 先思考清楚问题，把程序的行为设计清楚 切忌给予着手编写代码，碰到问题再调试 Race Condition 竞态条件是由操作系统软件中的同步错误。出现在进程试图同时执行两个或多个操作时，这是一种不希望出现的情况。 怎么样避免竞态?...

Overview CPU调度 (cpu scheduling )，是决定在一个时间窗口内，哪个进程可以拥有CPU而另外一个个进程会被暂停的过程。CPU调度的作用是为了确保每当CPU空闲时，操作系统至少选择就绪队列中一个可用的进程执行。这个选择过程将由CPU调度器来执行。 调度程序：挑选就绪进程的内核函数 调度策略：依据什么挑选进程？ 调度时机：什么时间进行调度？ 进程从运行状态切换到等待状态 进程退出 非抢占式：当前进程主从放弃CPU时， 抢占式：当前进程被抢占 时间片用完 进程从等待切换到就绪（当前就绪进程优先级高于当前运行进程） 调度准则 CPU的调度策略 抢占式调度 抢占式调度（Preemptive）在分配进程时有对应的优先级。而在另一个较低优先级进程之前运行具有较高优先级的进程很重要，即使较低优先级的进程仍在运行。较低优先级的进程扔会等待一段时间，让较高优先级的进程完成执行后恢复。 抢占式调度主要发生在运行状态切换到就绪或等待状态 非抢占式调度 非抢占式调度 （Non-Preemptive），在这种类型的调度中，一旦将资源（CPU 周期）分配给一个进程，该进程就会持有CPU使用权，直到它被终止或达到等待状态。 抢占式调度主要发生在运行状态终止的情况下 如何确定调度是抢占式还是非抢占式？ 一般来讲，确定调度的方式是通过以下四点来确定的： 当进程从运行状态切换到等待状态；如I/O请求或调用 wait() 系统调用 当进程从运行状态切换到就绪状态；如响应中断。 当进程从等待状态切换到就绪状态；如在 I/O 完成或从 wait() 返回时。 进程完成执行并终止； 如果调度发生在1 4情况下，则为非抢占式，否则为抢占式 程序执行模型 需要关注的是进程在计算机系统中运行时存在什么状态？ 几乎所有进程都在一个连续的循环的两种模型之间交替：即CPU突发和I/O突发中交替 每个调度决定都是关于在下一个CPU突发时将哪个工作交给CPU 在时间分片机制下，线程可能在结束当前CPU突发前被迫放弃CPU CPU突发和 I/O突发的交替序列逻辑 CPU 突发型的持续时间 调度指标 在了解评价指标前，需要对CPU调度中的一些术语需要了解 CPU突发 （Burst Time BT）：进程开始执行的时间，从到达到开始执行花费的时间 到达时间 （Arrival Time AT）：进程到达就绪队列的时间 完成时间（End Time ET 或 Completion Time CT）：进程执行完成的时间 等待时间 （Waiting Time WT）：进程在就绪队列中等待轮到 CPU 占用的时间；$WT = TT - BT$ 周转时间 （Turnaround Time TT）：完成时间和到达时间的差 $TT=CT-AT$ 相应时间（Response Time RT）：开始响应请求所需的时间。第一次请求到相应的时间。 吞吐量 (Throughput)：单位时间内完成的进程数。$Throughput = (Number\ of\ processes\ completed) \div (Time\ unit)$ 一般情况下，需要的服务”越快“越好，而快的定义：...

Overview 进程的描述 进程的状态 State 线程 Thread 进程间通信 Inter-Process Communication 进程互斥与同步 死锁 DeadLock 进程的描述 在操作系统中，通常来说进程 Process 是当前正在执行的东西。因此，一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程，可以称之为进程。 程序是静态的文件 进程是程序动态执行的过程 进程的组成 进程包括 : 程序的代码 程序处理的数据 程序计数器 (PC) 中的值, 指示下一条将运行的指令 一组通用的寄存器的当前值, 堆 Heap , 栈 Stack 一组系统资源(如打开的文件、内存、网络) 而进程的主要构成如下， Stack Section Heap Section Data Section Text Section Stack Stack部分包含： 局部变量 函数和返回地址 main函数 如上图所示，Stack和 heap 以相反的方向增长，如果两者都以相同的方向增长，那么其两者可能会重叠，因此如果它们以相反的方向增长则很好。 示例：如，调用下列函数时，将存储在Stack部分，一旦函数返回，该函数堆栈部分的值将被删除。 Stack上有一个堆栈帧，其中包含main函数以及局部变量a, b sum 。使用 printf()，创建的帧以及局部变量只能在内存中访问，帧的持续时间在从函数 return 0 后释放。 c 1 2 3 4 5 6 7 8 int main(void) { int a, b, sum; a = 2; b = 3; sum = a + b; printf("%d\n", sum); return 0 } Stack是一种后进先出 (LIFO) 数据结构，最后一个被推到Stack上的内容就是从顶部弹出的第一个内容。不允许从Stack的中间插入或移除。因此Stack必须至少支持两种操作：push 和 pop ；其他操作也是可以，但不是必需的。...

Overviews 功能与目标 实验设置与评价方法 局部页面算法 最优页面置换算法 先进先出算法 最近最久未使用算法 时钟页面置换算法 最不常用置换算法 Belady现象 LRU FIFO Clock对比 全局页面置换算法 工作集模型 工作集页面置换算法 缺页率置换算法 功能与目标 功能 : 当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换。 目标 : 尽可能地减少页面的换进换出次数(即缺页中断的次数)。 具体来说，把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据来进行预测。 页面锁定 frame locking：用于描述必须常驻内存的操作系统的关键部分或时间关键（time critical）的应用进程。实现的方式是：在页表中添加锁定标记位(lock bit)。 实验设置与评价方法 实例：记录一个进程对页访问的一个轨迹 举例 : 模拟一个实验环境，记录对应的地址访问序列，虚拟地址跟踪(页号, 偏移)… (3,0) (1,9) (4,1) (2,1) (5,3) (2,0) … 而offset可以忽略（页不存在才会产生 page fault），生成的页面轨迹 3, 1, 4, 2, 5, 2, 1, …（替换为，3,1,4,2,5,2,1） 模拟一个页面置换的行为并且记录产生页缺失数的数量 更少的缺失，更好的性能 局部页面置换算法 最优页面置换算法 基本思路：当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它的下一次访问之前，还需等待多长时间，从中选择等待时间最长的那个，作为被置换的页面。 这是一种理想情况, 在实际系统中是无法实现的, 因为操作系统无法知道每一个页面要等待多长时间以后才会再次被访问. 最优页面置换算法（Optimal Page Replacement）可用作其他算法的性能评价的依据，(在一个模拟器上运行某个程序, 并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法) 在该算法中，会替换在未来最长持续时间内不会使用的页面。如下图所示有 a b c d e五个页，但是只有四个页帧。此时会产生物理页不够，会产生 Page Fault。...