Geek猫的自留地

愿你出走半生，归来仍是少年

0%

发表于 分类于 Disqus：

高速缓存存储器 Cache
E = 1：直接映射高速缓存（direct-mapped cache）
E > 1：组相联高速缓存（set associative cache）
E = C/B：全相联高速缓存（fully associative cache）

存储器层次结构(memory hierarchy )

缓存命中（cache hit）

缓存不命中（cache miss）

写的情况要复杂一些。假设我们要写一个已经缓存了的字 w（写命中 ，write hit）。在高速缓存更新了它的 w 的副本之后，怎么更新 w 在层次结构中紧接着低一层中的副本呢？

最简单的方法，称为直写（write-through），就是立即将 w 的高速缓存块写回到紧接着的低一层中。虽然简单，但是直写的缺点是每次都会引起总线流量。

另一种方法，称为写回（write-back），尽可能地推迟更新，只有当替换算法要驱逐这个更新过的块的时候，才把它写到紧接着的低一层中。由于局部性，写回能显著地减少总线流量，但是它的缺点是增加了复杂性。高速缓存必须为每个高速缓存行维护一个额外的修改位（dirty bit），表明这个高速缓存块是否被修改过。

另一个问题是如何处理写不命中。一种方法，称为写分配（write-allocate），加载相应的低一层中的块到高速缓存中，然后更新这个高速缓存块。写分配试图利用写的空间局部性，但是缺点是每次不命中都会导致一个块从低一层传送到高速缓存。另一种方法，称为非写分配（not-write-allocate），避开高速缓存，直接把这个字写到低一层（主存）中。直写是非写分配的，写回是写分配的。

存储器层次解耦股中较低层的缓存更可能使用写回，而不是直写。

Cost of Cache Misses

阅读全文 »

发表于 更新于 分类于 ， ， ， Disqus：

虚拟内存(VM) 部分

TLB(Translation lookaside buffer)

A translation lookaside buffer (TLB) is a memory cache that stores the recent translations of virtual memory to physical memory.

TLB 是翻译后备缓冲器(translation lookaside buffer)的缩写，是 MMU 中关于 PTE 的小的缓存，目的是加速虚拟地址到物理地址的翻译

TLB 的一个例子

4.png

虚拟地址中用以访问 TLB 的组成部分

所有的地址翻译步骤都是在芯片上的 MMU(memory management unit) 中执行的

地址翻译步骤：

阅读全文 »

发表于 更新于 分类于 ， ， ， ， ， Disqus：

Cogito,ergo sum.
- René Descartes

《理想国》(The Republic)全景式地展现了柏拉图一生所有重要的思想而成为他颇丰的著作中最具代表性的一部。
《苏菲的世界》也是一本很好的哲学入门读物，从《苏菲的世界》到柏拉图《理想国》的阅读，哲学对人的影响是潜移默化的,对人的心灵启发也是极为震撼的。
苏格拉底为了更好的阐述他所提出的相论，他分别提出了 太阳(Analogy of the sun) 、 线段(Analogy of the divided line) 以及 洞穴(Allegory of the cave) 三个比喻。

太阳比喻(Analogy of the sun)

The analogy of the sun (or simile of the sun or metaphor of the sun) is found in the sixth book of The Republic (507b–509c).

柏拉图认为理念是事物的本原，而最高的理念是善，善统摄所有的理念。善的定义却是很笼统的，每个人心目中都有他/她关于善的标准，善是一切美德和知识的来源，是许多人为之共同努力的目标。

Socrates compares the “Good” with the sun. Plato might be using the image of the sun to help bring life to his arguments or to make the argument more clearly understood.

太阳照耀万物，让世界有了光明，光和视觉让人们看到了这些可见的、美好的事物；善也是如此，善一直是人们所追求的，美好的东西让我们感受到善的存在，比如真理和知识，这些人类的智慧，因为这些善指引着人们追求好的事物，就像灯塔一样，也会感染其他人追求真理、知识和正义。

但我们不能说真理和知识就是善，它们只是善纯在的形式，这就好像视觉和光线可以让人看见世界万物，但是太阳才是这个至高无上存在的具体存在。

阅读全文 »

发表于 更新于 分类于 ， ， ， ， ， Disqus：

无论从世界局势还是技术革新等层面，当今世界正在经历百年未有之大变局，移动互联的底层技术、算法，数学世界微妙的定理，可知世界那些看不见的事物，却往往成为现代社会不可替代的数字化和信息化互联网的基石。

从ESP8266自组织网络谈起 ESP-WIFI-MESH

ESP-WIFI-MESH 是一种无线通信网络，采用树状拓扑结构，其节点具有乐鑫 SoC 的 AP-STA 特性。ESP-WIFI-MESH 能够提供一个易于部署、自动组网并自我修复的网络。它无需部署 Wi-Fi 基础设施，就能在更大范围内部署节点，基于这种网络拓扑结构，它最多可以扩展到 1000 个节点。这样一来，ESP-WIFI-MESH 也可用于在家庭部署中覆盖 Wi-Fi 信号无法到达的盲点。

esp8266，wifi模块，玩嵌入式的应该都不陌生，一个esp8266作为一个node，可以部署一个自组织的网络，此网络少数node掉线不会影响整个网络的通信，设备能够根据节点信号的强度值自动连接信号强的节点，在网络故障时仍保证网络的稳定性，这也是ESP-WIFI-MESH的自我修复特性。

分布式、去中心化、共识

在计算机技术领域，去中心化结构使用分布式核算和存储，不存在中心化的节点，任意节点的权利和义务都是均等的，系统中的数据块由整个系统中具有维护功能的节点来共同维护，任一节点停止工作都不会影响系统整体的运作。
去中心化是分布式网络结构中的一种，所有的去中心化都是采用分布式网络结构的，而分布式网络结构可能是“中心化”也可能是“去中心化”的

1.png

去中心化和共识是两个不同的概念，两者结合才是真正意义上的“去中心化”，去中心化有了共识才具备了完全的可信度，否则只是狭义概念的数据共享，没人知道这些共享的数据是否真实，或者被集体认可，仅仅只是拥有这些信息；共识有了去中心化，就具备了安全性，系统很难被攻破，信息也难被篡改；再加上特殊的数据结构，而这一切的实现就是区块链。

阅读全文 »

发表于 更新于 分类于 ， ， Disqus：

openwrt

OpenWrt项目是一个针对嵌入式设备的Linux操作系统。OpenWrt不是一个单一且不可更改的固件，而是提供了具有软件包管理功能的完全可写的文件系统。这使您可以从供应商提供的应用范围和配置中解脱出来，并且让您通过使用适配任何应用的软件包来定制设备。对于开发人员来说，OpenWrt是一个无需围绕它构建完整固件就能开发应用程序的框架; 对于普通用户来说，这意味着拥有了完全定制的能力，能以意想不到的方式使用该设备。

项目地址

openwrt.org

为什么要完整备份openwrt?

为了无缝升级！为了能在升级的同时不丢失配置文件及软件包

总所周知，openwrt的文件系统的精华思想是overlay

/overlay 是什么意思呢？

OpenWRT 一般使用的文件系统是 SquashFS ，这个文件系统的特点就是：只读。
那，一个只读的文件系统，是怎么做到保存设置和安装软件的呢？
这里就是使用一个 /overlay 的分区，overlay顾名思义就是覆盖在上面一层的意思。
虽然原来的文件不能修改，但我们把修改的部分放在 overlay 分区上，然后映射到原来的位置，读取的时候就可以读到我们修改过的文件了。
但为什么要用这么复杂的方法呢？ OpenWRT 当然也可以使用 EXT4 文件系统，但使用 SquashFS + overlay 的方式有一定的优点。
首先 SquashFS 是经过压缩的，在路由器这种小型 ROM 的设备可以放下更多的东西。
然后 OpenWRT 的恢复出厂设置也要依赖于这个方式。在你捅 Reset 重置的时候，它只需要把 overlay 分区清空就可以了，一切都回到了刚刷进去的样子。
如果是 EXT4 文件系统，就只能够备份每个修改的文件，在恢复出厂设置的时候复制回来，十分复杂。
当然，SquashFS + overlay 也有它的缺点，修改文件的时候会占用更多的空间。
首先你不能够删除文件，因为删除文件实际上是在 overlay 分区中写入一个删除的标识，反而占用更多的空间。
另外在修改文件的时候相当于增加了一份文件的副本，占用了双份的空间。

阅读全文 »

发表于 更新于 分类于 ， Disqus：

#骑行# #旅行志# #天气#
5月22日，一个冷涡在甘肃抛下大量冷空气，在乌鞘岭余脉上诱发了致命的狂风冰雨，多位久负盛名的越野“跑神”永远失去生命。这场狂风冰雨到底有多极端，才能酿成如此灾难？

事情还是要从那个靠近我国的巨型冷涡说起。5月20-21日，它来到新疆；5月22-23日，它先后掠过西北、华北，23日晚已来到黑龙江西界。冷涡所到之处，北方皆有降温，其中新疆、内蒙古降温猛烈，阿勒泰一度逼近0度，内蒙古发布了寒潮预警。


5月21-22日，河西五市将会有降温，幅度为4-6度；景泰气象台也发了大风蓝色预警。而在此之前，白银市景泰县阳光普照，气温节节攀升，5月21日下午最高已达25.6度，站在太阳下，是妥妥的夏天感觉。

一边是阳光烘烤下的夏天气息，一边是有寒冬实力的巨大冷涡，极端天气就此酝酿。5月22日早晨，冷涡中心来到毛乌素沙漠以北，大量寒冷空气从几千米的高空“跳伞”，俯冲进入黄河上游地区，一道巨大的冷锋云带在甘肃、宁夏和内蒙古形成。

————以上内容摘自中国气象爱好者—————–

欧洲中期天气预报中心（European Centre for Medium-Range Weather Forecasts 简称 ECMWF）是一个包括34个国家支持的国际性组织，是当今全球独树一帜的国际性天气预报研究和业务机构

ECMWF与世界各国气象预报机构在天气预报领域有广泛的联系。ECMWF主要提供10天的中期数值预报产品，各成员国通过专用的区域气象数据通信网络得到这些产品后做出各自的中期预报，同时ECMWF也通过由世界气象组织（WMO）维护的全球通信网络向世界所有国家发送部分有用的中期数值预报产品。其使用的模式充分利用四维同化资料，可提供全球在65公里高度内60层的40公里网格密度共20，911，680个点的风、温、湿预报

如果我们用欧洲中期天气ECMWF预报的模型再来重现一下当时的天气，分析这次事故的天气大环境,这样的极端天气是否能被预测到呢？又有哪些措施可以防止悲剧再次发生呢？

借助于ECMWF强大的再分析模型，我们选择时间点为2021年5月22日上午8点 ，地点黄河石林景区入口

此时，根据数值预报模型，西边几十公里的新堡乡下起了小雪，而此时景泰县和比赛地也下起了小雨，如下图（白点为黄河石林景区入口，比赛起点）

阅读全文 »

发表于 更新于 分类于 ， ， Disqus：

you can open another file while vim is open with :tabe filename and to switch to the other file you type :tabn or :tabp for next and previous accordingly.
The keyboard shortcuts gT and gt can also be used to switch tabs when you are not in editing mode (i.e. not in insert, replace etc modes). On some systems Ctrl+Alt+Page Up and Ctrl+Alt+Page Down also allow tab-switching, but this does not always work (for example, it won’t work in the OS X terminal ‘out of the box’).

shortcut function
:tabn :tabp next and previous accordingly
gt gT switch tabs when you are not in editing mode
Ctrl+Alt+Page DownORUp tab-switching
:tabe filename open another file

发表于 更新于 分类于 ， ， ， ， ， Disqus：

对于计算机中的死锁，我们有四种处理的方法，分别为预防死锁、避免死锁、检测死锁和解除死锁

The banker’s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes an “s-state” check to test for possible activities, before deciding whether allocation should be allowed to continue.

银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹赫尔·戴克斯特拉在1965年为T.H.E系统设计的一种避免死结产生的演算法.它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行.

银行家算法的名字来源于该算法原本是为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况，在OS中可以用它来避免死锁.

银行家算法的实质就是要设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁

  • 为实现银行家算法，在系统中必须设置这样四个数据结构:

  1. 可利用资源向量Avaliable.这是一个含有m个元素的数组，其中每一个元素代表一类可利用的资源数目，其初始值是系统所配置的该类全部可用资源的数目，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态的改变.如果$Available[j]=K$，则表示系统中现有$R_j$类资源的最大数目为K.

  2. 最大需求矩阵Max.是一个n×m的矩阵，定义了系统中n个进程中的每一个进程对m类资源的最大需求.如果$Max[i, j]=K$，则表示进程i需要$R_j$类资源的最大数目为K.

  3. 分配矩阵Allocation.是一个n×m的矩阵，定义了系统中每一类资源当前已分配给每一进程的资源数.如果Allocation[i, j]=K，则表示进程i当前已分得$R_j$类资源的数目为K.

  4. 需求矩阵Need.是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数.如果$Need[i, j]=K$，则表示进程i还需要$R_j$类资源K个方能完成其任务.

它们之间的关系为: $Need[i, j]=Max[i, j]-Allocation[i,j]$

银行家算法

设 Request i是进程 $P_i$的请求向量，如果 $Request i[j]=K$，表示进程 $P_i$需要 K 个 $R_j$类型的资源.当 $P_i$发出资源请求后，系统按下述步骤进行检查:

阅读全文 »

发表于 更新于 分类于 ， ， ， ， Disqus：

哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌中间有一大碗意大利面，每位哲学家之间各有一支餐叉。因为用一支餐叉很难吃到意大利面，所以假设哲学家必须用两支餐叉吃东西。他们只能使用自己左右手边的那两支餐叉。哲学家就餐问题有时也用米饭和五根筷子而不是意大利面和餐叉来描述，因为吃米饭必须用两根筷子。
如何设计一套规则，使得在哲学家们在完全不交谈，也就是无法知道其他人可能在什么时候要吃饭或者思考的情况下，可以在这两种状态下永远交替下去。

假设我们要求哲学家遵守以下规则：

1. 哲学家在左边的叉子可用（没有其他人拿起）之前处于思考状态。如果左边的叉子可用，就拿起来。
2. 哲学家等待右边的叉子可用。如果右边的叉子可用，就拿起来。
3. 如果两个叉子都已经拿起来，开始吃意大利面，每次吃面都花费同样的时间。
4. 吃完后先放下左边的叉子。
5. 然后放下右边的叉子。
6. 开始思考（进入一个循环）

1
2
3
4
5
6
7
8
9
10
11
	semaphore chopstick[5] = {1,1,1,1,1}; //定义信号量数组chopstick[5],并初始化
Pi(){  //i号哲学家的进程
	while(1){
		P(chopstick[i]); //取左边筷子
		P(chopstick[(i+1)%5]);  //取右边篌子
		eat;
		V(chopstick[i]); //放回左边筷子
		V(chopstick[(i+1)%5]);  //放回右边筷子
		think;
	}
}

这个解法是失败的，当每个哲学家都拿起左侧的叉子，等待右侧的叉子可用时，就会进入死锁状态，每个哲学家将永远都在等待（右边的）另一个哲学家放下叉子。

正确的解法

  • 解法一
    假设当一个哲学家左右两边的筷子都可用时，才允许他抓起筷子。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
semaphore chopstick[5] = {1,1,1,1,1}; //初始化信号量
semaphore mutex=l;  //设置取筷子的信号量

Pi(){ //i号哲学家的进程
	while(1){
		P(mutex); //在取筷子前获得互斥量，一次只能由一个哲学家取筷子
		P(chopstick[i]) ; //取左边筷子
		P(chopstick[(i+1)%5]);  //取右边筷子
		V(mutex); //释放取筷子的信号量
		eat;
		V(chopstick[i]);  //放回左边筷子
		V(chopstick[(i+1)%5]);  //放回右边筷子
		think;
	}
}
  • 解法二
    至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用完时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。
阅读全文 »

发表于 更新于 分类于 ， ， ， Disqus：

volatile类型

Volatile关键字主要有三个功能：

  1. 防止重排序

  2. 保证可见性

  3. 保证单次读或写操作的原子性。

volatile修饰的变量发生修改时，volatile会强制刷新主内存.

在CSAPP的12.16节，有一个badcnt.c示例程序

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
 * badcnt.c - An improperly synchronized counter program
 */
/* $begin badcnt */
/* WARNING: This code is buggy! */
#include "csapp.h"

void *thread(void *vargp);  /* Thread routine prototype */

/* Global shared variable */
volatile long cnt = 0; /* Counter */

int main(int argc, char **argv)
{
	long niters;
	pthread_t tid1, tid2;

	/* Check input argument */
	if (argc != 2) {
		printf("usage: %s <niters>\n", argv[0]);
		exit(0);
	}
	niters = atoi(argv[1]);

	/* Create threads and wait for them to finish */
	Pthread_create(&tid1, NULL, thread, &niters);
	Pthread_create(&tid2, NULL, thread, &niters);
	Pthread_join(tid1, NULL);
	Pthread_join(tid2, NULL);

	/* Check result */
	if (cnt != (2 * niters))
		printf("BOOM! cnt=%ld\n", cnt);
	else
	printf("OK cnt=%ld\n", cnt);
	exit(0);
}

/* Thread routine */
void *thread(void *vargp)
{
long i, niters = *((long *)vargp);

	for (i = 0; i < niters; i++) //line:conc:badcnt:beginloop
	cnt++;                   //line:conc:badcnt:endloop

	return NULL;
}
/* $end badcnt */

  • $H_i$: The block of instructions at the head of the loop
  • $L_i$: The instruction that loads the shared variable cnt into register %$rdx_i$, where %$rdx_i$ denotes the value of register %$rdx$ in thread i
  • $U_i$: The instruction that updates (increments) %$rdx_i$
  • $S_i$: The instruction that stores the updated value of %$rdx_i$ back to the shared variable cnt
  • $T_i$: The block of instructions at the tail of the loop

其中关于%$rdx_i$汇编语言中就能看出volatile类型的特性：从Memory读取变量到寄存器，在寄存器中改变值后，立马写回内存

volatile关键字首先具有“易变性”，声明为volatile变量编译器会强制要求读内存，相关语句不会直接使用上一条语句对应的的寄存器内容，而是重新从内存中读取。

并发和并行的区别

阅读全文 »