发表于 | 更新于 | 分类于

关键段

关键段(critical section)是一小段代码，它在执行之前需要独占对一些共享资源的访问权。

1
2
3
4
5
6
7
8
9
CRITICAL_SECTION g_cs;
int g_nSum = 0;
InitializeCriticalSection(&g_cs);

EnterCriticalSection(&g_cs);
g_nSum++;
LeaveCriticalSection(&g_cs);

DeleteCriticalSection(&g_cs);

Slim读/写锁

SRWLock的目的和关键段相同，对同一资源进行保护，不让其他线程访问它。但是，与关键段不同的是，SRWLock允许我们区分那些（读取者线程）和（写入者线程）。让所有的读取者线程在同一时刻访问共享资源应该是可行的，这是因为仅仅读取资源的值并不存在破坏数据的风险。

1
2
3
4
5
6
7
8
SRWLOCK g_srwLock;
InitializeSRWLock(&g_srwLock);
//写入者线程调用
AcquireSRWLockExclusive(&g_srwLock);
ReleaseSRWLockExclusive(&g_srwLock);
//读取者线程调用
AcquireSRWLockShared(&g_srwLock);
ReleaseSRWLockShared(&g_srwLock);

发表于 | 更新于 | 分类于

UNIX体系结构

UNIX的体系结构大致分为以下几个层次：
第一层：内核
第二层：系统调用
第三层：shell和库函数
第四层：应用软件

输入和输出

每当运行一个新程序时，所有的shell都为其打开三个文件描述符：标准输入、标准输出、标准出错。

1
./a.out < in file > outfile

出错处理

当UNIX函数出错时，常常返回一个负值。文件errno.h中定义了符号errno以及可以赋予它的各种变量。

1
2
3
4
5
6
7
8
// 单线程
#include <errno>
extern int errno;

// 多线程
#include <errno>
extern int *__errno_location(void);
#define errno (*__errno_location())

errno的打印函数

1
2
3
4
5
#include <string.h>
char *strerror(int errnum);

#include <stdio.h>
void perror(const char *msg);

发表于 | 更新于 | 分类于

GDI原理

图形显示主要由动态链接库GDI32.DLL中导出的函数处理，这些动态链接库会调用你安装的视频显示器和打印机的设备驱动程序中的一些函数。各种各样的显示设备都可以与PC兼容机连接。因此，GDI的一个主要目的就是支持与设备无关的图形。GDI提供了一种特殊的机制来彻底隔离应用程序和不同输出设备的特性，这样就可以支持与设备无关的图形。
GDI函数的调用

GDI包含有几百个函数，可以分成下面几大类

获取和释放设备环境的函数

获取设备环境信息的函数

绘图函数

设置和获取设备环境属性的函数

使用GDI”对象”的函数

GDI的基本图形

线条和曲线

可被填充的封闭区域

位图

文本

其他

映射模式和转换

图元文件

区域

路径

剪裁

调色板

打印

设备环境

如果希望在图形输出设备上绘制图形，必须首先获取设备环境的句柄。

GetDC

有时候，仅需要获取一下关于设备环境的信息，而不需要在上面绘制任何东西。

CreateIC

CreateCimpatibleDC内存设备环境

保存设备环境

通常，当调用GetDC或者BeginPaint函数时，Windows返回一个设备环境，它的所有属性都被设定为默认值。当设备环境调用ReleaseDC或者EndPaint函数时，对属性所做的任何改变都会丢失。如果程序需要使用非默认的设备环境属性，则必须在每次获取一个新的设备环境句柄时初始化这个设备环境。

我们可以通过SaveDC来保存设备环境状态。

发表于 | 更新于 | 分类于

程序的执行

当执行Windows程序的时候，加载器加载该程序，然后调用C startup code，再调用程序中WinMain函数入口。

初始化

WinMain函数首先通过CreateWindow函数创建窗口，并对窗口进行初始化配置;

消息的处理

程序通过循环GetMessage函数不断的从消息队列中抓取消息;

当抓取到消息后，通过DispatchMessage函数将消息分发出去，在DispatchMessage中根据switch/case语句对消息进行判别，并做相应的处理;

程序的结束

当收到WM_CLOSE消息的时候，调用DestoryWindow将窗口销毁掉，再调用PostQuitMessage，退出抓取循环。

发表于 | 更新于 | 分类于

进程是执行中的程序。当启动可执行文件，并被启动被装载到内存中，一个程序就成为了进程。
进程包括代码段，堆栈段（用于保存临时数据，局部变量等），数据段（用于保存全局变量），堆（运行时动态分配的内存），当前进程的活动状态。

  1. 进程控制块
    进程在操作系统中用数据控制块这样的一个数据结构表示，包含了进程的相关信息。在CPU调度进程进行切换的时候，会将信息保存到进程控制块中。进程状态、程序计数器(要执行的下个指令)、CPU寄存器、CPU调度信息(进程优先级，调度队列的指针和其他调度参数)、内存管理信息、记账信息(CPU时间，时间界限等)、I/O状态信息。

  2. 调度程序
    对于当前CPU执行的进程的选择是由相应的调度程序来执行的。

  3. 进程间通信
    进程间通信有两种基本模式：1.共享内存；2.消息传递。
    共享内存：创建一块共享的内存区域，其他进程通过这个共享区域来交换信息。
    消息传递的方式有多种
    直接/间接通信：直接根据标示通信/通过端口来通信。
    同步/异步通信
    队列缓冲，在消息传递中，不管是直接或者间接通信，进程的消息都保存在临时队列中，临时队列的缓冲有三种方法：1.零容量；2.有限容量；3.无限容量。

发表于 | 更新于 | 分类于

内存是现代计算机运行的中心。内存由很大一组字或字节组成，每个字或字节都有它们自己的地址。CPU根据程序计数器（PC）的值从内存中提取指令，这些指令可能会引起进一步对特定内存地址的读取和写入。

发表于 | 更新于 | 分类于

##概念
kubernetes，简称K8s，是用8代替8个字符”ubernete”而成的缩写。是一个开源的，用于管理云平台中多个主机上的容器化的应用，Kubernetes的目标是让部署容器化的应用简单并且高效(powerful),Kubernetes提供了应用部署，规划，更新，维护的一种机制。

Master

k8s里的Master指的是集群控制节点，每个k8s集群里需要有一个Master节点来负责整个集群的管理和控制，基本上k8s所有的控制命令都是发给它，它来负责具体的执行过程。
Master节点上运行着以下一组关键进程。

  1. kube-apiserver
    提供了Http Rest接口的关键服务进程，是k8s里所有资源的增删改查等操作的唯一入口，也是集群控制的入口进程。

  2. kube-controller-manager
    k8s里所有资源对象的自动化控制中心。

  3. kube-scheduler
    负责资源调度(Pod调度)的进行。

  4. etcd Server
    k8s里的所有资源对象的数据全部是保存在etcd中。

Node

除了Master, k8s集群中的其他机器被称为Node节点，在较早的版本中也被成为Minion。Node节点是k8s集群中的工作负载节点，每个Node都会被Master分配一些工作负载(Docker容器)，当某个Node宕机时，其上的工作负载会被Master自动转移到其他节点上去。
Node节点上运行着以下一组关键进程。

  1. kubelet
    负责Pod对应的容器的创建、启停等任务，同时与Master节点密切协作，实现集群管理的基本功能。

  2. kube-proxy
    实现K8s Service的通信与负载均衡机制的重要组件。

  3. Docker Engine
    Docker引擎，负责本机的容器创建和管理工作。

默认情况下kubelet会向Master注册自己，并定时向Master节点汇报自身的情况。当某个Node超过指定的时间不上报信息时，会被Master判定为”失联”。

Pod

Pod是k8s的最重要也最基本的概念。每个Pod都有一个特殊的被称为”根容器”的Pause容器。Pause容器对应的镜像属于k8s平台的一部分，除了Pause容器，每个Pod还包含一个或多个紧密相关的用户业务容器。

安装

kubernetes

1
2
3
4
5
6
7
8
9
10
11
systemctl stop firewalld
yum install -y docker etcd kubernetes
vi /etc/sysconfig/docker
OPTIONS='--selinux-enabled=false --log-driver=journald --signature-verification=false'
systemctl start etcd
systemctl start docker
systemctl start kube-apiserver
systemctl start kube-controller-manager
systemctl start kube-scheduler
systemctl start kubelet
systemctl start kube-proxy

minikube

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
cat <<EOF > /etc/yum.repos.d/kubernetes.repo
[kubernetes]
name=Kubernetes
baseurl=http://mirrors.aliyun.com/kubernetes/yum/repos/kubernetes-el7-x86_64
enabled=1
gpgcheck=0
repo_gpgcheck=0
gpgkey=http://mirrors.aliyun.com/kubernetes/yum/doc/yum-key.gpg http://mirrors.aliyun.com/kubernetes/yum/doc/rpm-package-key.gpg
EOF
yum install -y kubectl

curl -Lo minikube https://storage.googleapis.com/minikube/releases/latest/minikube-linux-amd64 \
  && chmod +x minikube

sudo mkdir -p /usr/local/bin/
sudo install minikube /usr/local/bin/


minikube start --vm-driver=none --image-mirror-country='cn' --image-repository='registry.cn-hangzhou.aliyuncs.com/google_containers' --apiserver-ips=['192.168.0.1'] --service-cluster-ip-range=192.168.0.0/16

例子

定义RC文件
定义SVC文件

mysql

1
2
kubectl create -f mysql-rc.yaml
kubectl create -f mysql-svc.yaml

myweb

1
2
3
4
5
kubectl create -f myweb-rc.yaml
kubectl get rc
kubectl get pod
kubectl create -f myweb-svc.yaml
kubectl get svc

FAQ

unable to create pods: No API token found for service account “default”

1
2
3
4
5
vi /etc/kubernetes/apiserver 
KUBE_ADMISSION_CONTROL="--admission-control=NamespaceLifecycle,NamespaceExists,LimitRanger,SecurityContextDeny,ServiceAccount,ResourceQuota"
# 去除SecurityContextDeny,ServiceAccount
# 重启
systemctl restart kube-apiserver

No such image: registry.access.redhat.com/rhel7/pod-infrastructure:latest”

1
2
3
4
5
6
7
8
9
10
11
12
13
docker search pod-infrastructure
docker pull docker.io/tianyebj/pod-infrastructure
docker tag docker.io/tianyebj/pod-infrastructure 10.0.2.15:5000/pod-infrastructure
docker push 10.0.2.15:5000/pod-infrastructure
# 配置基础镜像
vi /etc/kubernetes/kubelet 
KUBELET_POD_INFRA_CONTAINER="--pod-infra-container-image=10.0.2.11:5000/pod-infrastructure:latest"

systemctl restart kube-apiserver
systemctl restart kube-controller-manager
systemctl restart kube-scheduler
systemctl restart kubelet
systemctl restart kube-proxy

“cgroupfs” is different from docker cgroup driver: “systemd”

1
2
3
4
vim /etc/docker/daemon.json
"exec-opts": ["native.cgroupdriver=cgroupfs"]
# 或者
vi /usr/lib/systemd/system/docker.service

Error loading config file “/var/lib/minikube/kubeconfig”: open /var/lib/minikube/kubeconfig: permission denied

1
2
vim /etc/selinux/config
SELINUX=disabled

Failed to get system container stats for “/system.slice/kubelet.service”

1
2
3
4
/etc/systemd/system/kubelet.service.d/10-kubeadm.conf
--runtime-cgroups=/systemd/system.slice --kubelet-cgroups=/systemd/system.slice
systemctl daemon-reload
systemctl restart kubelet

Failed to list *v1.Endpoints: Get https://10.96.0.1:443/api/v1/endpoints?limit=500&resourceVersion=0:

当您使用kubeadm init时，请指定pod-network-cidr。确保主机/主网络的IP不在您引用的子网中。
即如果您的网络运行在192.168..使用10.0.0.0/16
如果您的网络是10.0..使用192.168.0.0/16

1
2
3
4
5
6
--pod-network-cidr=192.168.0.0/16
# minikube
--service-cluster-ip-range=192.168.0.0/16

# 增加路由规则minikube ip查询出10.0.2.15
ip route add 192.168.0.0/16 via 10.0.2.15

发表于 | 更新于 | 分类于

如果数据装不下内存，那么就意味着要把数据结构放到磁盘上。此时磁盘的访问代价太高了，我们想要把磁盘访问次数减小到一个非常小的常数。

我们可以以与建立二叉查找树大致相同的方式建立M叉查找树。

阶位M的B树是一棵具有下列特性的树：

1.数据项存储在树叶上。

2.非叶节点存储直到M - 1个关键字以指示搜索的方向；关键字i代表子树i + 1中的最小的关键字。

3.树的根或者是一片树叶，或者其儿子数在2和M之间。

4.除根外，所有非树叶节点的儿子数在[M / 2]和M之间。

5.所有的树叶都在相同的深度上并有[L / 2]和L之间个数据项。

插入情况

如果该树叶还没有被装满则插入项。

如果该树叶装满了则分裂该树叶，当父节点也满了，则沿树向上分裂，直到树根。如果分裂树根，那么我们就得到两个树根，我们可以建立一个新的根，这个根以分裂得到的两个树根作为它的两个儿子。这就是为什么准许树根可以最少有两个儿子的特权。

删除情况

如果被删元所在的树叶的数据项数已经是最小值，那么删除后它的项树就低于最小值了。我们可以通过在邻节点本身没有达到最小值时领养一个邻项来矫正这种状况。如果相邻节点已经达到最小值，那么可以与该相邻节点联合以形成一片满叶。可是，这意味着其父节点失去一个儿子。如果失去儿子的结果又引起父节点的儿子数低于最小值，那么我们使用相同的策略继续进行。这个过程可以一直上行到根。根不可能只有一个儿子。如果这个领养过程的结果使得根只剩下一个儿子，那么删除该根并让它的这个儿子作为树的新根。

发表于 | 更新于 | 分类于

伸展树保证从空树开始连续M次对树的操作最多花费O(M log N)时间。一棵伸展树每次操作的摊还代价是O(log N)。

伸展树的基本 想法是，当一个节点被访问后，它就要经过一些列AVL树的旋转被推到根上。因为在许多应用中当一个节点被访问时，它很可能不久再被访问。

发表于 | 更新于 | 分类于

AVL树使带有平衡条件的二叉查找树。

一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树(空树的高度定为-1)。

当进行插入操作时，我们需要更新通向根节点路径上那些节点的平衡信息，而插入操作的隐含着困难的原因在于，插入一个节点可能破坏AVL树的特性。如果发生这种情况，那么就要考虑这一步插入完成之前恢复平衡的性质。事实上，这总可以通过对树进行简单的修正来做到，我们称其为旋转。

第一种情况是插入发生在“外边”的情况（即左子树-左儿子或右子树-右儿子），该情况通过对树的一次单旋转而完成调整。

第二种情况是插入发生在”内部”的情况（即左子树-右儿子或右子树-左儿子），该情况通过稍微复杂些的双旋转来处理。

  1. 单旋转 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    private AvlNode<AnyType> rotateWithLeftChild(AvlNode<AnyType> k2)
    {
        AvlNode<AnyType> k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
        k1.height = Math.max(height(k1.left), k2.height) + 1;
        return k1;
    }

  2. 双旋转 

    1
    2
    3
    4
    5
    private AvlNode<AnyType> doubleWithLeftChild(AvlNode<AnyType> k3)
    	{
    		k3.left = rotateWithLeftChild(k3.left);
    		return rotateWithLeftChild(k3);
    	}