Posts

题目： Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1. Example 1: Input: 1 2 3 [[0,0,0], [0,1,0], [0,0,0]] Output: 1 2 3 [[0,0,0], [0,1,0], [0,0,0]] Example 2: 1 2 3 4 Input: [[0,0,0], [0,1,0], [1,1,1]] Output: 1 2 3 [[0,0,0], [0,1,0], [1,2,1]] Note: The number of elements of the given matrix will not exceed 10,000. There are at least one 0 in the given matrix. The cells are adjacent in only four directions: up, down, left and right. 解题： 1. BFS: ...

题目： An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535). Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, “flood fill” the image. To perform a “flood fill”, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor. ...

/proc/swaps 文件 1 2 3 # cat /proc/swaps Filename Type Size Used Priority /dev/dm-1 partition 4194300 0 -2 /proc/meminfo 文件 1 2 3 4 # grep Swap /proc/meminfo SwapCached: 0 kB SwapTotal: 4194300 kB SwapFree: 4194300 kB swapon 1 2 3 # swapon -s Filename Type Size Used Priority /dev/dm-1 partition 4194300 0 -2 free free -g/-k/-m 1 2 3 4 # free -g total used free shared buff/cache available Mem: 1 0 0 0 1 1 Swap: 3 0 3 vmstat 1 2 3 4 # vmstat procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu----- r b swpd free buff cache si so bi bo in cs us sy id wa st 1 0 0 130536 172 1654888 0 0 0 3 1 23 0 0 100 0 0 top/atop/htop/glance 参考引用 How To Check Swap Usage Size and Utilization in Linux

这篇文章Open Sourcing Mantis: A Platform For Building Cost-Effective, Realtime, Operations-Focused Applications 是出自 Netflix Technology Blog。 作为流式微服务生态系统，Mantis平台为工程师提供将观察和操作复杂分布式系统的成本降至最低的功能。 Mantis已开源 特点： 解决问题变得容易 开发人员可以根据需要从任何检测的应用程序中获取事件流。 解决问题成本降低 能够在事件上实现基于流的可观察性，同时使工程师能够使用工具来降低原本会对业务造成不利影响的成本。 指导原则 访问原始事件 实时访问这些事件 对获取数据进行新维度分析 保证最小花费，不抢占正常业务使用资源 Mantis 一些应用 Netflix流健康实时监控 上下文报警 Raven,MQL Mantis查询语言 Cassandra 健康检查 日志监控 Chaos监控 PII快速识别敏感数据。

物理内存组织方式 SMP: CPU 通过总线访问内存, 称为 SMP 对称多处理器, 采用平坦内存模型, 物理页号连续, 总线成为瓶颈 NUMA: CPU 都有本地内存, 访问内存不用总线, 称为 NUMA 非一致内存访问 采用非连续内存模型，页号不连续 稀疏内存模型 下面以NUMA 为例. 节点 数据结构 pglist_data 表示 NUMA 节点 包括 id，page 数组,起始页号, 总页数, 可用页数 区域 zone 节点分为多个区域 zone ZONE_DMA; ZONE_NORMAL; ZONE_HIGHMEM, ZONE_MOVABLE 数据结构 zone 表示 区域 包含第一个页页号; 区域总页数; 区域实际页数; 被伙伴系统管理的页数; 用 per_cpu_pageset 区分冷热页(热页, 被 CPU 缓存的页) 页 数据结构 page 表示, 分配方式： 匿名页分配; 分配小块内存: Linux 采用 slab allocator 技术; 申请一整页, 分为多个小块存储池, 用队列维护其状态(较复杂) slub allocator 更简单 slob allocator 用于嵌入式 page 记录: 第一个 slab 对象; 空闲列表; 待释放列表 页分配 使用伙伴系统 进行管理分配 Linux 把空闲页分组为 11 个页块链表, 链表管理大小不同的页块(页大小 2^i * 4KB)

这篇文章 Timers and time management in the Linux kernel. Part 4. 是出自 linux-insides一书中 Timers and time management 章节 Introduction to timers 内核版本比对5.4-rc2 进行了相关调整, 增加相关备注 Linux内核中的定时器和时间管理.Part 4. 定时器 这是本章的第四部分，通过前一部分描述了Linux内核中与计时器和时间管理相关的内容，我们知道Linux内核中的tick broadcase框架和NO_HZ模式。我们将在这一部分继续研究与Linux内核中与时间管理相关的内容，并熟悉Linux内核中的另一个概念-timers。在研究Linux内核中的计时器之前，我们必须学习一些有关此概念的理论。请注意，我们将在本部分中考虑软件计时器。 Linux内核提供了软件计时器的概念，以允许将来可以调用内核功能。计时器在Linux内核中被广泛使用。例如，查看源代码文件 net/netfilter/ipset/ip_set_list_set.c。此源代码文件提供了用于管理IP地址组的框架的实现。 在 list_set 结构中包含了 time_list 变量 gc : 1 2 3 4 5 struct list_set { ... struct timer_list gc; ... }; 并非gc字段具有timer_list类型。 在include/linux/timer.h 头文件中定义的结构，该结构的要点是存储 Linux内核中的动态计时器。 实际上，Linux内核提供了两种类型的计时器，称为动态计时器和间隔计时器。 内核使用第一种计时器，用户模式使用第二种计时器。timer_list结构包含实际的dynamic定时器。 在我们的示例中，list_set包含gc计时器代表垃圾收集的计时器。 该计时器将在list_set_gc_init函数中初始化： 1 2 3 4 5 6 7 8 static void list_set_gc_init(struct ip_set *set, void (*gc)(struct timer_list *t)) { struct list_set *map = set->data; timer_setup(&map->gc, gc, 0); mod_timer(&map->gc, jiffies + IPSET_GC_PERIOD(set->timeout) * HZ); } 按照现有版本进行调整 由gc指针指向的函数,将在超时时间等于map->gc.expires后被调用。 timer_setup设置gc指向的函数， mod_timer设置超时时间 ...

内存管理包含: 物理内存管理 虚拟内存管理 物理内存与虚拟内存的映射 除了内存管理模块, 其他模块都使用虚拟地址(包括内核) 虚拟内存空间包含: 内核空间(高地址) 用户空间(低地址) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 +--------------+ | kernel space | high address +--------------+ ^ | stack | | +--------------+ | ^ | | user | | space | | v +--------------+ | heap | +--------------+ | bss | +--------------+ | | data | | +--------------+ | | text | v +--------------+ low address 空间存放内容 用户空间:多个进程看到的用户空间是独立的 从低到高布局为: 代码段 数据段 BSS段(未初始化静态变量) 堆 内存映射段 栈地址空间段 内核空间: 多个进程看到同一内核空间, 但内核栈每个进程不一样 内核代码也仅能访问内核空间 内核也有内核代码段, DATA 段, 和 BSS 段; 位于内核空间低地址 内核代码也是 ELF 格式, 只是所处的位置不同 内存映射 分段 虚拟地址 = 段选择子(段寄存器) + 段内偏移量 段选择子 = 段号(段表索引) + 标识位 段表 = 物理基地址 + 段界限(偏移量范围) + 特权等级 段表称为段描述符表, 放在全局标识符表中 Linux 将段基地址都初始化为 0, 不用于地址映射 Linux 分段功能主要用于权限检查 分页 物理内存被换分为大小固定(4KB)的页, 物理页可在内存与硬盘间换出/换入 ...

进程内存布局 可以通过一下方法查看: 命令： pmap 文件： proc filesystem maps 使用 pmap 可以从其说明看到 -X 也是从/proc/PID/smaps获取了更详细的信息 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 [root@centosgpt ~]# pmap 1704 1704: -bash 0000000000400000 884K r-x-- bash 00000000006dd000 4K r---- bash 00000000006de000 36K rw--- bash ... 00007f3c65515000 28K r--s- gconv-modules.cache 00007f3c6551c000 4K rw--- [ anon ] 00007f3c6551d000 4K r---- ld-2.17.so 00007f3c6551e000 4K rw--- ld-2.17.so 00007f3c6551f000 4K rw--- [ anon ] 00007ffd64655000 132K rw--- [ stack ] 00007ffd64769000 12K r---- [ anon ] 00007ffd6476c000 4K r-x-- [ anon ] ffffffffff600000 4K r-x-- [ anon ] total 115580K 查看 proc filesystem maps /proc/PID/smaps ...

题目： Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer. You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4]. ...

这是 CMMI的wiki 能力成熟度模型集成（CMMI）是一个过程级改进培训和评估程序。 它是由ISACA的子公司CMMI Institute管理的，由卡内基梅隆大学（CMU）开发。 许多美国国防部（DoD）和美国政府合同都要求这样做，尤其是在软件开发方面。 CMU声称CMMI可用于指导整个项目，部门或整个组织的流程改进。 CMMI为流程定义了以下成熟度级别：初始，已管理，已定义，已量化管理和优化中。 2.0版于2018年发布（1.3版于2010年发布，是此Wiki文章中其余信息的参考模型）。 CMMI由CMU在美国专利商标局注册。 概述 成熟度水平的特征 picture from wiki 最初，CMMI涉及三个感兴趣的领域： 产品和服务开发-CMMI for Development（CMMI-DEV）; 服务的建立，管理，—CMMI for Services (CMMI-SVC); 产品和服务获取— CMMI for Acquisition（CMMI-ACQ）。 在2.0版中，这三个区域（以前每个区域都有一个单独的模型）被合并为一个模型。 CMMI由行业，政府和CMU的软件工程学院（SEI）组成的小组开发。 CMMI模型为开发或改进满足组织业务目标的流程提供了指导。 CMMI模型也可以用作评估组织流程成熟度的框架。 到2013年1月，整个CMMI产品套件已从SEI转移到卡耐基梅隆大学新成立的组织CMMI研究所。 历史 CMMI由CMMI项目开发，旨在通过将许多不同的模型集成到一个框架中来提高成熟度模型的可用性。该项目由行业，政府和卡内基梅隆软件工程学院（SEI）的成员组成。主要赞助商包括国防部长办公室（OSD）和国防工业协会。 CMMI是功能成熟度模型（CMM）或软件CMM的后继产品。 CMM是从1987年到1997年开发的。2002年发布了1.1版，随后在2006年8月发布了1.2版，并在2010年11月发布了1.3版。CMMIV1.3的一些重大更改是对敏捷软件开发的支持， 对高成熟度实践的改进和实施流程的改进。 根据软件工程学院（SEI，2008）的说法，CMMI帮助 " 整合传统上独立的组织功能，设置流程改进目标和优先级，为质量流程提供指导，并为评估当前流程提供参考点。" 2016年3月，CMMI研究所被ISACA收购。 CMMI主题 表示 在1.3版中，CMMI有两种表示形式：连续表示和分段表示。 连续表示的目的是使用户可以专注于对组织的近期业务目标重要的特定过程，或组织为之分配高度风险的特定过程。 分阶段的表示旨在提供标准的改进顺序，并且可以用作比较不同项目和组织的成熟度的基础。 分阶段的表示还提供了从SW-CMM到CMMI的轻松迁移。 在2.0版中，以上表示分离已被取消，现在只有一个内聚模型。 模型框架（v1.3） 取决于所使用的关注领域（收购，服务，开发），其包含的过程领域将有所不同。 流程区域是组织的流程将覆盖的区域。下表列出了版本1.3中所有感兴趣的CMMI领域共有的17个CMMI核心过程领域。 缩写 名称 领域 成熟度 OT Organizational Training Process Management 3 OPP Organizational Process Performance Process Management 4 OPM Organizational Performance Management Process Management 5 OPF Organizational Process Focus Process Management 3 OPD Organizational Process Definition Process Management 3 RSKM Risk Management Project Management 3 REQM Requirements Management Project Management 2 QPM Quantitative Project Management Project Management 4 PP Project Planning Project Management 2 PMC Project Monitoring and Control Project Management 2 IPM Integrated Project Management Project Management 3 SAM Supplier Agreement Management Support 2 PPQA Process and Product Quality Assurance Support 2 MA Measurement and Analysis Support 2 DAR Decision Analysis and Resolution Support 3 CM Configuration Management Support 2 CAR Causal Analysis and Resolution Support 5 服务的成熟度级别 针对服务模型CMMI，列出了以下过程域及其成熟度级别： ...