Posts

进程通信的类型 共享存储器系统 相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信 基于共享数据结构的通信方式 在这种通信方式中，要求诸进程公用某些数据结构，借以实现诸进程间的信息交换。如在生产者—消费者问题中，就是用 有界缓冲区 这种数据结构来实现通信的。 基于共享存储区的通信方式 为了传输大量数据，在存储器中划出了一块 共享存储区，诸进程可通过对共享存储区中数据的读或写来实现通信。这种通信方式属于高级通信。进程在通信前，先向系统申请获得共享存储区中的一个分区，并指定该分区的关键字；若系统已经给其他进程分配了这样的分区，则将该分区的描述符返回给申请者，继之，由申请者把获得的共享存储分区连接到本进程上；此后，便可像读、写普通存储器一样地读、写该公用存储分区。 消息传递系统 进程间的数据交换是以格式化的消息(message)为单位的 直接通信方式 这是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显式方式提供对方的标识符。通常，系统提供下述两条通信命令(原语)： Send(Receiver，message)； 发送一个消息给接收进程； Receive(Sender，message)； 接收 Sender 发来的消息； 间接通信方式 间接通信方式指进程之间的通信需要通过作为共享数据结构的实体。该实体用来暂存发送进程发送给目标进程的消息；接收进程则从该实体中取出对方发送给自己的消息。通常把这种中间实体称为信箱。消息在信箱中可以安全地保存，只允许核准的目标用户随时读取。因此，利用信箱通信方式，既可实现实时通信，又可实现非实时通信 Send(mailbox，message)； 将一个消息发送到指定信箱； Receive(mailbox，message)； 从指定信箱中接收一个消息； 信箱的分类 私用信箱 信箱的拥有者有权从信箱中读取消息，其他用户则只能将自己构成的消息发送到该信箱中。 公用信箱 它由操作系统创建，并提供给系统中的所有核准进程使用。核准进程既可把消息发送到该信箱中，也可从信箱中读取发送给自己的消息 共享信箱 它由某进程创建，在创建时或创建后指明它是可共享的，同时须指出共享进程(用户)的名字。信箱的拥有者和共享者都有权从信箱中取走发送给自己的消息。可以是一对一关系、多对一关系、一对多关系、多对多关系 管道通信系统 所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。向管道(共享文件)提供输入的发送进程(即写进程)，以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)，则从管道中接收(读)数据。由于发送进程和接收进程是利用管道进行通信的，故又称为管道通信。 管道机制必须提供以下三方面的协调能力: 互斥 当一个进程正在对 pipe执行读/写操作时，其它(另一)进程必须等待。 同步...

连续分配存储管理方式 固定分区分配 将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业，这样，把用户空间划分为几个分区，便允许有几道作业并发运行。当有一空闲分区时，便可以再从外存的后备作业队列中选择一个适当大小的作业装入该分区，当该作业结束时，又可再从后备作业队列中找出另一作业调入该分区。 划分分区的方法 分区大小相等，即使所有的内存分区大小相等。其缺点是缺乏灵活性，即当程序太小时，会造成内存空间的浪费；当程序太大时，一个分区又不足以装入该程序，致使该程序无法运行。尽管如此，这种划分方式仍被用于利用一台计算机去控制多个相同对象的场合，因为这些对象所需的内存空间是大小相等的。例 分区大小不等。为了克服分区大小相等而缺乏灵活性的这个缺点，可把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。这样，便可根据程序的大小为之分配适当的分区。 内存分配 为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)，当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。 动态分区分配 分区分配中的数据结构 系统中配置着相应的数据结构，用来描述空闲分区和已分配分区的情况，为分配提供依据。常用的数据结构有以下两种形式 空闲分区表 在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区的大小等数据项。 空闲分区链 为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，通过前、后向链接指针，可将所有的空闲分区链接成一个双向链 分区分配算法 为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。 首次适应算法(first fit) 我们以空闲分区链为例来说明采用FF算法时的分配情况。FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。这给为以后到达的大作业分配大的内存空间创造了条件。其缺点是低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，而每次查找又都是从低址部分开始，这无疑会增加查找可用空闲分区时的开销。 循环首次适应算法(next fit) 该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，即如果最后一个(链尾)空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应调整起始查寻指针。该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。 最佳适应算法(best fit) 所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区，必然是最佳的。孤立地看，最佳适应算法似乎是最佳的，然而在宏观上却不一定。因为每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的小空闲区。 最坏适应算法(worst fit) 最坏适应分配算法要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，对中、小作业有利，同时最坏适应分配算法查找效率很高。该算法要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。但是该算法的缺点也是明显的，它会使存储器中缺乏大的空闲分区。最坏适应算法与前面所述的首次适应算法、循环首次适应算法、最佳适应算法一起，也称为顺序搜索法。 快速适应算法(quick fit) 该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。空闲分区的分类是根据进程常用的空间大小进行划分，如 2 KB、4 KB、8 KB 等，对于其它大小的分区，如 7 KB 这样的空闲区，既可以放在 8 KB 的链表中，也可以放在一个特殊的空闲区链表中。...

Golang与Java的区别 1. 结构体 -> 类 // 包名即为包含该文件的目录名字 package collection // 声明一个结构体，类似Java中的类 type Stack struct { data []string } // 声明一个Push函数，并通过一个Stack的指针对象实现该方法 // 类似声明了Stack的成员方法 func (s *Stack) Push(x string) { s.data = append(s.data, x) } func (s *Stack) Pop() string { n := len(s.data) - 1 res := s.data[n] s.data[n] = "" // to avoid memory leak s.data = s.data[:n] return res } func (s *Stack) Size() int { return len(s.data) } 结构体对应Java里的类, 但结构体里只能有变量，不能有方法...

基于内容寻址 点对点 IPFS就是提供了一套协议？ 一种内容可寻址的对等超媒体分发协议 Filecoin 加密货币，支付系统，是一套激励机制 提供数据存储和获取的方式 数据监管 存储的性能，不同的底层系统，性能怎么保证？ 按存储量卖钱？按性能卖钱 Filecoin和法币的汇率 lotus是filecoin的实现 filecoin怎么保证数据不丢？ 鼓励矿工执行winning post，大家来保证你的数据是不是存储正确的 Window PoSt 是矿工在对应的周期内对已经提交的扇区进行证明，证明扇区保存的数据依然存在。 Winning PoSt 是矿工在出块时对已经提交的扇区进行证明，证明扇区保存的数据依然存在。 存储的是密封的数据 密封，增加算力成本 window post 证明存储的可用性和可靠性 sector：扇区，32GiB 或 64GiB Partition：一个parition 2349或2300个sector Deadline：每半小时一个，一天48个Deadline 一个Deadline证明1或多个Partition 多轮证明 存储商要押钱 算力降低，出块概率低 惩罚高，所以留下来的供应商都比较优质 检索服务商 目前没有读的能力

poolChain是poolDequeue的动态大小版本，本质上也是个双向链表，特别之处在于，它每次出队的元素个数是前一次出队的两倍。一旦出队满了m // poolChain is a dynamically-sized version of poolDequeue. // // This is implemented as a doubly-linked list queue of poolDequeues // where each dequeue is double the size of the previous one. Once a // dequeue fills up, this allocates a new one and only ever pushes to // the latest dequeue. Pops happen from the other end of the list and // once a dequeue is exhausted, it gets removed from the list....

块设备初始化 kernal/blk_drv.c void blk_dev_init(void) { int i; for (i=0 ; i<NR_REQUEST ; i++) { request[i].dev = -1; request[i].next = NULL; } } kernel/blk_drv.h /* * NR_REQUEST is the number of entries in the request-queue. * NOTE that writes may use only the low 2/3 of these: reads * take precedence. * * 32 seems to be a reasonable number: enough to get some benefit * from the elevator-mechanism, but not so much as to lock a lot of * buffers when they are in the queue....

main函数 init/main.c // 下面三行分别将指定的线性地址强行转换为给定数据类型的指针，并获取指针所指 // 的内容。由于内核代码段被映射到从物理地址零开始的地方，因此这些线性地址 // 正好也是对应的物理地址。这些指定地址处内存值的含义请参见setup程序读取并保存的参数。 #define EXT_MEM_K (*(unsigned short *)0x90002) // 直接将内存地址转化为结构体指针 #define DRIVE_INFO (*(struct drive_info *)0x90080) #define ORIG_ROOT_DEV (*(unsigned short *)0x901FC) static long memory_end = 0; // 机器具有的物理内存容量（字节数） static long buffer_memory_end = 0; // 高速缓冲区末端地址 static long main_memory_start = 0; // 主内存（将用于分页）开始的位置 int ROOT_DEV = 0; // 根文件系统设备号。 struct drive_info { char dummy[32] } drive_info; // 用于存放硬盘参数表信息 // 内核初始化主程序。初始化结束后将以任务0（idle任务即空闲任务）的身份运行。 void main(void) /* This really IS void, no error here....

设置主存区域的mem_init函数 mm/memory.c // 物理内存管理初始化 // 该函数对1MB以上的内存区域以页面为单位进行管理前的初始化设置工作。一个页面长度 // 为4KB bytes.该函数把1MB以上所有物理内存划分成一个个页面，并使用一个页面映射字节 // 数组mem_map[]来管理所有这些页面。对于具有16MB内存容量的机器，该数组共有3840 // 项((16MB-1MB)/4KB)，即可管理3840个物理页面。每当一个物理内存页面被占用时就把 // mem_map[]中对应的字节值增1；若释放一个物理页面，就把对应字节值减1。若字节值为0， // 则表示对应页面空闲；若字节值大于或等于1，则表示对应页面被占用或被不同程序共享占用。 // 在该版本的Linux内核中，最多能管理16MB的物理内存，大于16MB的内存将弃之不用。 // 对于具有16MB内存的PC机系统，在没有设置虚拟盘RAMDISK的情况下start_mem通常是4MB， // end_mem是16MB。因此此时主内存区范围是4MB-16MB,共有3072个物理页面可供分配。而 // 范围0-1MB内存空间用于内核系统（其实内核只使用0-640Kb，剩下的部分被部分高速缓冲和 // 设备内存占用）。 // 参数start_mem是可用做页面分配的主内存区起始地址（已去除RANDISK所占内存空间）。 // end_mem是实际物理内存最大地址。而地址范围start_mem到end_mem是主内存区。 static long HIGH_MEMORY = 0; // 全局变量，存放实际物理内存最高端地址 // linux0.11内核默认支持的最大内存容量是16MB，可以修改这些定义适合更多的内存。 // 内存低端(1MB) #define LOW_MEM 0x100000 // 分页内存15 MB，主内存区最多15M. #define PAGING_MEMORY (15*1024*1024) // 分页后的物理内存页面数（3840） #define PAGING_PAGES (PAGING_MEMORY>>12) // 指定地址映射为页号 #define MAP_NR(addr) (((addr)-LOW_MEM)>>12) // 页面被占用标志. #define USED 100 static unsigned char mem_map [ PAGING_PAGES ] = {0,}; void mem_init(long start_mem, long end_mem) { int i; // 首先将1MB到16MB范围内所有内存页面对应的内存映射字节数组项置为已占用状态， // 即各项字节全部设置成USED(100)。PAGING_PAGES被定义为(PAGING_MEMORY>>12)， // 即1MB以上所有物理内存分页后的内存页面数(15MB/4KB = 3840)....

中断程序初始化的trap_init kernal/traps.c // 异常(陷阱)中断程序初始化子程序。设置他们的中断调用门(中断向量)。 // set_trap_gate()与set_system_gate()都使用了中断描述符表IDT中的陷阱门(Trap Gate), // 他们之间的主要区别在于前者设置的特权级为0，后者是3.因此断点陷阱中断int3、溢出中断 // overflow和边界出错中断bounds可以由任何程序产生。 // 这两个函数均是嵌入式汇编宏程序(include/asm/system.h中) // 以下定义了一些中断处理程序原型，用于在函数trap_init()中设置相应中断门描述符。 // 这些代码在kernal/asm.s或system_call.s中。 void divide_error(void); void debug(void); void nmi(void); void int3(void); void overflow(void); void bounds(void); void invalid_op(void); void device_not_available(void); void double_fault(void); void coprocessor_segment_overrun(void); void invalid_TSS(void); void segment_not_present(void); void stack_segment(void); void general_protection(void); void page_fault(void); void coprocessor_error(void); void reserved(void); void parallel_interrupt(void); void irq13(void); void trap_init(void) { int i; // 设置除操作出错的中断向量值。 set_trap_gate(0,&divide_error); set_trap_gate(1,&debug); set_trap_gate(2,&nmi); set_system_gate(3,&int3); /* int3-5 can be called from all */ set_system_gate(4,&overflow); set_system_gate(5,&bounds); set_trap_gate(6,&invalid_op); set_trap_gate(7,&device_not_available); set_trap_gate(8,&double_fault); set_trap_gate(9,&coprocessor_segment_overrun); set_trap_gate(10,&invalid_TSS); set_trap_gate(11,&segment_not_present); set_trap_gate(12,&stack_segment); set_trap_gate(13,&general_protection); set_trap_gate(14,&page_fault); set_trap_gate(15,&reserved); set_trap_gate(16,&coprocessor_error); // 下面把int17-47的陷阱门先均设置为reserved,以后各硬件初始化时会重新设置自己的陷阱门。 for (i=17;i<48;i++) set_trap_gate(i,&reserved); // 设置协处理器中断0x2d(45)陷阱门描述符，并允许其产生中断请求。设置并行口中断描述符。 set_trap_gate(45,&irq13); outb_p(inb_p(0x21)&0xfb,0x21); // 允许8259A主芯片的IRQ2中断请求。 outb(inb_p(0xA1)&0xdf,0xA1); // 允许8259A从芯片的IRQ3中断请求。 set_trap_gate(39,&parallel_interrupt); // 设置并行口1的中断0x27陷阱门的描述符。 } include/linux/head....

Ceph Monitor 持有整个集群的状态，包含monitor映射，manager映射，osd映射，mds映射，crush映射，monitor必须做冗余和高可用 Manager 负责追踪运行时指标以及集群的状态，对外提供了web端的dashboard和restapi OSD 负责存储数据，处理数据多副本，数据修复，rebalance，并且提供一些监控信息给monitor，同样需要冗余和高可用 MDS 负责存储集群的数据，只有ceph文件存储才需要用到，ceph的块存储和对象存储用不到，MDS允许通过posix文件接口来访问 ceph使用一个叫逻辑存储池的方法来存储数据，数据以对象的形式存在。ceph会计算对象属于哪个group，group又属于哪个OSD，通过一个叫CRUSH的算法来实现。CRUSH算法使得ceph集群可伸缩，rebalance，可修复

三总线 地址总线： 是专门用来传送地址的，是单向的，地址从CPU传向外部存储器或IO端口。地址总线的位数决定了CPU可寻址的内存空间大小。比如16位就是2的16次方等于64KB 数据总线： 用来传输数据信息，是双向的，即可以把CPU的数据传送到存储器或IO接口等其他部件，也可以将其他部件的数据传到CPU 控制总线： 用来传送控制信号和时序信号，双向的 控制信号如微处理器送往存储器和IO接口电路的，如读写信号、片选信号、中断响应信号

内存 虚拟内存 内存空间划分 用户空间 内核空间 内存寻址 内存区域中的每一个单元都是有地址的，这些地址是由指针来标识和定位的，通过指针来寻找内存单元的操作也被称为内存寻址。 内存管理 分页式 分段式 物理内存 内存卡

寄存器

684. 冗余连接 684. 冗余连接 树可以看成是一个连通且 无环 的 无向 图。 给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。 思路： 假设对于所有的边 [[1,2], [2,3], [3,4], [1,4], [1,5]] 初始时，定义所有节点的代表节点集合parent parent[i] = i 表示i节点的代表节点是自身i 对于上面的边，五条边，则应该有6个节点，len(parent) = 6 parent = [0, 1, 2, 3, 4, 5] 循环所有的边，判断能否加入这条边到树中 对于边x-y，如果x的代表节点不等于y的代表节点，说明没有一条路径能让x直接到y，则此时x-y这条边能加入树中， func findRedundantConnection(edges [][]int) []int { // 1....

最近在看libp2p的源码，发现需要先储备一些网络方面的知识才能看得懂，如UPnP 什么是UPnP UPnP全名是Universal Plug and Play，即通用即插即用。简单的来说，UPnP 最大的愿景就是希望任何设备只要一接上网络，所有在网络上的设备马上就能知道有新设备加入，这些设备彼此之间能互相沟通，更能直接使用或控制它，一切都不需要设定，完全的Plug and Play。 组成 设备 控制点 步骤 寻址(Addressing) 开始会给所有设备或者控制点分配一个分配一个IP。 这个过程是这样的，设备或控制点向 DHCP 客户端发送一个 DHCPDISCOVER 消息，DHCP 客户端负责分配向他们分配 IP，如果局域网内没有 DHCP 服务，UPnP 设备将按照 Auto-IP 的协议通过算法呢从 169.254.1.0 to 169.254.254.255 地址范围内获取一个未被使用的 IP 地址。 对于新设备首次与网络建立连接时也会有这个寻址过程。 发现(Discovery) 这步是 UPnP 真正工作的第一步。 当一个设备被加入到网络中时，UPnP 发现协议允许它向控制点介绍自己的功能，设备会向多次向固定的地址及端口(239.255.255.250:1900)发送消息，控制点会监控给地址及端口。当一个控制点被加入到网络时，UPnP 发现协议允许它搜寻这个网络内它感兴趣的设备。这个过程内彼此交换剪短的信息，如类型、全局唯一标识符、指向详细信息的链接及当前状态(可选)。 描述(Description) 控制点通过1.发现(Discovery)过程中设备提供的指向设备详细信息的链接，获取设备的详细信息(Device description)及其提供的服务的详细信息(Service description)。 控制(Control) 控制点通过描述过程对设备的了解，控制点可以发送控制信息控制设备，设备在执行完命令后会给与控制点一个反馈。 事件(Eventing) 控制点可以监听设备的状态，这样设备的状态或信息发生了变化，只要产生一个事件广播出去，控制点即可进行响应，类似一般的订阅者模式。 展现(Presentation) 控制点可以从设备获取一个 HTML 页面，用于控制设备或展现设备信息，是对上面3.控制(Control)和4.事件(Eventing)过程的一个补充(即时展现)。

Http2