首页  思维导图  详情

Knowledge

2020-08-26 10:27:40   0  举报





AI智能生成

为你推荐

查看更多



Knowledge Gap

ehrs

How to Enjoy Life!

APQC Template

Succession Planning and Knowledge Transfer

Knowledge Gap

Drupal Knowledge Development

knowledge

str2

Secondary Sources of Brand Knowledge

知识

计算机

作者其他创作

大纲/内容

Knowledge

linux

概念

linux面试题

文件系统

硬链接/软链接

硬链接: 直接链接到inode上(故删除原文件并不会导致链接失效)

软链接: 用目录作链接(故原文件不在对应目录下则链接失效)

inode(索引节点):Linux 文件系统通过把 inode 节点和文件名进行连.需要读取该文件时，文件系统在当前目录表中查找该文件名对应的项，由此得到该文件相对应的 inode 节点号.通过该 inode 节点的磁盘地址表把分散存放的文件物理块连接成文件的逻辑结构。

安全

CC攻击: 多个不同用户不停访问

shell

常用命令

文件管理

文件处理

查找

find:find pathname -options [-print -exec -ok ...]

which:查看可执行文件的位置(搜PATH)

whereis: whereis 查看文件的位置

文件内容查看

head

less

grep:grep [option] pattern file|dir

sed: 文件编辑命令

sed

ln: 建立链接ln -sv source.log link.log

chmod:文件类型/文件所有者/用户组/其他_/rwx/rwx/rwx

chown:chown <所有者>:<用户组> <文件名>

磁盘命令

df: 磁盘使用情况

du: 查看文件和目录的使用空间

mkdir: 创建文件夹-p创建整个路径rmdir: 删除文件夹

pwd: 当前工作路径

读取用户输入: read <变量名>

用户/用户组管理

添加组: groupadd <组名>

添加用户: useradd -g <组名> <用户名>

删除用户: userdel -r <用户名>

网络命令

ifconfig: 查看网络接口(-a表示所有)使用 up 和 down 命令启动或停止某个接口: ifconfig eth0 up 和 ifconfig eth0 down

netstat: 显示网络状态netstat [-acCeFghilMnNoprstuvVwx][-A<网络类型>][--ip]

ping: 检测主机

telnet: 远端登录telnet 192.168.0.5

系统管理命令

date: 时间

free: 内存使用情况

kill: 发送指定的信号到相应进程.不指定型号将发送SIGTERM（15）终止指定进程.

ps: 进程状态

pstree: 进程树

top: 系统状态包括进程 ID、内存占用率、CPU 占用率等

定时执行

crontab

压缩/解压

bzip2: 创建 *.bz2 压缩文件：bzip2 test.txt 。解压 *.bz2 文件：bzip2 -d test.txt.bz2 。

gzip: 创建一个 *.gz 的压缩文件：gzip test.txt 解压 *.gz 文件：gzip -d test.txt.gz 显示压缩的比率：gzip -l *.gz

uzip

打包解包

tar

程序/编程

ulimit -a: 数据段大小之类的

参数/变量

$0: 脚本本身文件名称$1～$n: 各参数值$*: 所有参数列表(\"1 2 3\")$@: 所有参数列表(\"1\" \"2\" \"3\")$#: 参数个数$$: 脚本运行时的PID$! : Shell最后运行的后台Process的PID$?: 脚本退出码

Shell脚本中$0、$?、$!、$$、$*、$#、$@等的意义

取消变量: unset <参数名>

列表/数组

调用seq: $(seq 1 30)

直接空格隔开: A B C

用括号: a=(Shirley 2 Hank)遍历时可用${a[*]};访问特定索引可用: ${a[1]}对特定索引赋值: a[1]=loves获取长度: ${#variable[*]}

shell之列表的定义与循环

${}操作

shell中${}和()的使用

数字运算:$[16 + 4]expr 16 + 4

语句

均可使用break和continue

比较运算符: ==-gt-lt

if语句:if [ $x -gt $y ] then 命令else if [ 条件 ] then 命令 else 命令 fifi

循环

for循环:for 变量 in 循环列表do 命令done

也可以这样:for((i=1;i<51;i++))

while循环:while [ 条件 ]do 命令done

函数

Shell 函数

gcc

-c: 直接生成.o文件

系统调用

进程

fork()

Shared Memory(POSIX)

int shm_unlink(const char *name)// unlink and remove

管道

Anonymous Pipe

Named Pipe

内存管理

brk()// 在malloc()时要用到// grow and shrink memory area

进程调度

CFS通过虚拟运行时间vruntime(与基于优先级的衰减因子有关)调度程序选择具有最小vruntime值的任务运行这里用红黑树维护任务

并行编程

OpenMP

基本操作

并行块

Clauses

#pragma omp parallel num_threads(N)// N个线程并行执行后续程序

同步

#pragma omp barrier\t\t// Wait for all threads reaching here

#pragma omp critical// The following codes can be accessed by only ont thread at one time

for循环并行

#pragma omp for

#pramga omp for reduction(op:list)// The elements in list will be identity of op// Elements are copied as local variable// and finally be reducted

work sharing

master结构

#pragma omp master// Only the master will execute codes in this structure.

single结构

#pragma omp single// Only 1 thread (the first one gets here) // will do the codes

#pragma omp single nowait

section结构

#pragma omp sections{ #pragma omp section do_x(); #pragma omp section do_y();}

锁omp_lock_t

omp_init_lock()

omp_set_lock()

omp_unset_lock()

omp_destroy_lock()

omp_test_lock()

Runtime Library

threads numbers

omp_set_num_threads()

omp_get_num_threads()// You won't get the threads number // unless you've entered the parallel region

omp_get_thread_num()

omp_get_max_threads()

omp_in_parallel()// To check if running in parallel region

dynamic mode:Threads given may differ

omp_set_dynamic(int _Dynamic_threads)

omp_get_dynamic()

omp_num_procs()// Get how many processors available

Environment Variables

OMP_STACKSIZETell the system the stacksize needed

OMP_WAIT_POLICYACTIVE | PASSIVEACTIVE: actively spin till available(cost almost nothing)PASSIVE: put it sleep(cost a lot)

Data Environment

pivate// This clause won't initialize the variable

firstprivate// Will be initialized as the global value

lastprivate// The value will be copied to the global variable

shared

Tasks

#pragma omp task// Create a task to execute following codes

#pragma omp taskwait

Memory Model

#pragma omp flush(list)// Rs and Ws overlaping after the flush// don't executed until after the flush.

implicit flushesentry/exit of parallel regionimplicit/explicit barrierentry/exit of critical sectiona lock is set/unset

#pragma omp atomic [read|write|update|capture]

Thread Private

copyin(xxx)// copy in the main thread's xxx

书

Using OpenMP

Patterns For Parallel Programmingby Tim Mattson

Concurrency in Programming Languages(About the histroy)

The Art of Concurrency

pthread(POSIX标准)

pthread_create()

pthread_exit()// 可以给出返回值

pthread_join()

pthread_kill()

结构体为: pthread_t

pthread_cancel()pthread_testcancel()

模式(Patterns)

SIMD(Single Instruction Multiple Data)

for parallel

编程语言

Python

.group(num).groups().span(num) # 返回索引

Sequential ConsistencyProgram Order = Code Order = Commit Order

Relaxed Consistency

Algorithm

关联性

Apriori系

FP Tree

FP Tree算法原理总结

从零实现机器学习算法（十四）FP-growth

近邻算法

KNN

CNN

强化学习

Markov 决策过程

Q-Learning

SARSA

一致性哈希(Consistent Hashing)

K-V Store

Data Structures

Log-Structured Merge Tree (LSM-tree)

Advantages:high write efficiencylow costs as a tiered storage

Disadvantages:slow compactions(much I/O)

background compaction operations(a.k.a merge)

Paper

fast20: FPGA-Accelerated Compactions for LSM-based Key-Value Store

数据中心

Fat Tree

All Reduce

Parameter Server有一个服务器来弄

Collective AllReduce

Halving-Doubling

ring

double binary tree

Hierachical Aggregation

Math

概率论与数理统计

概率论

常见分布

离散

二项分布

Poisson分布

泊松分布-百度百科

均匀分布

连续

正态分布

正态分布-百度百科

指数分布

指数分布-百度百科

卡方分布

卡方分布-百度百科

t分布

t分布-百度百科

数字特征

均值

方差

协方差/协方差矩阵

相关(2020-04-032020-04-072020-04-10)

例子

MEM和IF同时需要访问存储器

解决方案

Stall

哈佛结构

写后读(RAW)

写后写(WAW)

读后写(WAR)

解决方案(2020-04-07)

停顿(Stall)

硬件实现流水线互锁(interlock)

编译器实现

转发(Forwarding)(或称旁路(bypassing))

控制相关(2020-04-10)

调度来源:分支前指令填充: 分支指令前的指令(选择不会有依赖关系错误的放到分支指令后做)分支目标指令填充分支失败指令填充

编译器优化

分支预测技术

静态

动态

饱和计数器

多发技术(2020-04-10)

超标量技术

超长指令字

超流水线

SIMD技术

存储

主存

DRAM

分散刷新: 穿插在读写中(每次访问都要等一次之类刷新之类的)

异步刷新: 有选择地结合上述两种

访存周期: 100~200ns

存储容量

存取时间: 命令发出到完成及数据放到总线上的时间

存储周期: 连续两次读写最少间隔时间

存储器带宽

构成

控制线

读写

片选

译码驱动

扩展

位扩展

字扩展

与CPU的连接

数据线连接: 存储器扩展到和CPU的一样大来连接

命令控制线

提高速度的方法

双端口

并行访问存储器: 交叉访问比如: 一个存储器具有独立的两组读写电路

低位交叉编址: 易于利用局部性原理提高性能

高位交叉编址: 易于扩展

结构化的存储系统(加缓存)

可靠性

信息冗余

海明码

CRC(Cyclic Redundancy Check)循环冗余校验

奇偶校验码

时间冗余

回滚

空间冗余

RAID

Cache

加速(局部性原理)解决冲突

锁存器

评价指标

命中率: 与容量和块长有关

访问效率: e=t_{访问cache总时间} / t_{总时间}

单一/多级

统一/分离(指令和数据是否分开放)

地址映射

优点: 冲突概率小缺点: 需要相联存储器(代价高)

直接映射:{Cache块号 i} = {主存块号 j} mod {Cache块数 m}

优点: 比较电路少缺点: 冲突概率高

替换策略

FIFO

随机法

读写策略

读

写

写不失效时

写直达法:写入Cache和内存. 时间为写内存时间

写回法:写入Cache. 时间为访问Cache时间但替换的时候需要写回主存多核的时候也会有问题

写失效时

写分配法

绕写法

虚存

组成结构

页表基址寄存器(CPU中)

页表(内存中)

二级页表

反向页表(逻辑页数大于物理页数)

TLB(Translation Look-aside Buffer)(快表): 缓存页表

段式

段表基址寄存器

段表:段起址+有效位+段长

段页式:先分段再每段自己分页

虚地址: 基号(程序的序号)+段号+页号+偏移量

替换策略(由操作系统支持)

FIFO+LRU

总线

并行/串行总线

计算机总线测控总线网络通信总线...

同步/异步/半同步/分离式总线

常见总线

infinibandnvlink

VPXVME

ISA

EISA

VESA

PCI

AGP(Accelerated Graphics Port): 加速图形接口

STD

SCSI(Small Computer System Interface): 小型计算机系统接口

USB总线

连硬盘的IDESATA

结构

多总线结构: 还可加DMA(Direct Memory Access

仲裁方式

集中式仲裁: 如CPU总线仲裁器设备和仲裁器之间有送往仲裁器的请求信号BR仲裁器送出的授权信号BG

计数定时: 仲裁器计数决定设备地址

独立请求

分布式仲裁

自举分布式仲裁: 各个设备通过请求总结果判断自己是否可以使用总线(独立判断自己是否具有最高优先级)

冲突检测分布式仲裁: 检测到冲突则按某种规则选择一个设备

并行竞争分布式仲裁

猝发式传送(Burst)

写后读: 校验

读后写: 保护共享资源

广播/广集

总线周期

申请分配

寻址

传送

结束(撤除总线占用)

通信方式

同步/异步波特率(单位: bps): 总传输速率比特率(单位: bps): 有效传输速率

同步通信: 需要取决于最低频时钟

异步通信

不互锁

半互锁: 等从设备应答

分离式: 分为两个子周期发送请求后放弃使用权准备好了再次申请使用权

IO系统

控制方式

CPU指令控制通道指令控制

发展阶段(2020-05-19)

接口模块和DMA:

具有通道结构:专门的通道指令

具有IO处理机

编址方式(2020-05-19)

统一编址: 看作存储器地址的一部分

独立编址: 专门的IO指令

接口与端口(2020-05-19)

接口: 若干端口加上逻辑控制组成

功能

选址

传送命令

传送数据

反映IO设备状态

类型

并行/串行

可编程/不可编程

通用/专用

程序型/DMA

信息交换方式(2020-05-19)

程序查询方式

程序中断方式

软件: 设置中断服务程序

DMA方式

DMA和CPU同时访存冲突怎么处理？

停止CPU访问

周期挪用(窃取): CPU为主

交替访存: 固定每个访问一周期之类的

组成

内存地址寄存器(计数器)AR：用于存放内存中要交换的数据的地址，DMA传送时，每交换一次数据，寄存器值加“1”

字计数器WC：用于记录传送数据块长度

数据缓冲寄存器BR：用于暂存每次传送的数据

设备地址寄存器DAR：IO设备码或辅存寻址信息

控制/状态逻辑：负责管理DMA传送过程，用于修改相关信息和状态

通道方式

接受CPU专门的IO指令

IO设备(2020-05-19)

辅助存储器(2020-05-22)

磁盘

柱面(cylinder)

轨道(track)

扇区(sector)

道密度: 沿半径方向单位长度的磁道数

位密度: 单位长度磁道所记录的数据位数

存储总量=盘面数*磁道数*每道代码数

寻址时间=寻道时间+等待时间

传输率 = 记录密度 * 介质运行速度误码率 = 出错位数 / 总读位数

柱面数=磁道数(同磁道在同一柱面)

记录方式

方式

归零制(NZ)

不归零制(NRZ)

见1就翻制(NRZ1)

调频制(FM)

改进调频制(MFM)

编码效率

自同步能力

RAID技术

RAID 0 (无差别控制的区组)

RAID 2 (带海明码检验)

RAID 3 (带奇偶校验(独立一个磁盘)的并行传送)

RAID 4 (按数据块访问数据)

RAID 10 (RAID 0 和 RAID 1 一起用(多体并行 + 镜像))

光盘

Flash闪存器

写之前必须有额外擦除操作(原有数据先放在Buffer里)

固态硬盘(用的是NAND)

进程管理

X程

进程(process)

状态

new

running

waiting

ready

terminated

进程状态(process state)

程序计数器(program counter)

CPU寄存器(CPU registers)

CPU调度信息(CPU-scheduling information)(优先级等)

进程终止时:

用SIGCHLD唤醒父进程

IPC 进程间通信(Inter-Process Communication)

共享内存(POSIX shm)

A Producer Process

Buffer

A Consumer Process

send

recv

直接/间接

直接

间接(相当于有个信箱)

同步/异步(阻塞/非阻塞)

Buffer大小

Zero Capacity

Bounded Capacity

Unbounded Capacity

实现

socket

pipe

Ordinary Pipe父子进程间单向

Named Pipe存在直到显式删除双向半双工

进程同步

临界区(Critical Section)

实现方法

硬件(原子指令)

test_and_set()

compare_and_swap()

软件

禁止中断禁止中断临界区允许中断

优点便于kernel的简单操作缺点在用户进程不允许中断不合理(如恶意代码)只对单处理器有效

strict alternation(严格轮转)

缺点访问次序太过严格忙等

peterson's solution(限于指令不同)

缺点忙等优先权翻转(如果有优先权的话)

mutex lock

semaphore

操作

wait()——P

signal()——V

up()

down()

Binary Semaphore(二进制信号量)相当于互斥锁

Counting Semaphore(计数信号量)

要求

互斥(Mutual Exclusion)

无过多约束(要求两个CPU之类的)

进步(Progress): 进程要有进展

有限等待(bounded waiting)一个进程请求临界区过程中允许其他进程进入次数有上限

死锁

条件

Mutual Exclusion

Hold and Wait

Circular Wait

描述

资源分配图

点边类型

进程结点P_i

资源类型R_j

申请边P_i -> R_j

分配边R_j -> P_i

定理

无环⇒无死锁

有环 ∧ 所有资源各只有一个 ⇒ 死锁(否则不一定)

检测和分配

单资源: DFS找环

多资源: 银行家算法

处理方法

通过协议来预防避免死锁: 破坏死锁的四个条件

可共享资源不要求互斥访问

抢占: 通常适用于状态可保存恢复的资源(CPU寄存器和内存等)

检测死锁并加以恢复

经典案例

生产者消费者问题

Pipe

Binary Semaphoresemaphore mutex = 1;semaphore empty = N;semaphore full = 0;

哲学家用餐问题

Semaphore

读者写者问题

semaphore db;semaphore mutex; // 对read_count的锁int read_count = 0;

线程(thread)

Many-to-Many Model:并不严格一一对应

协程(coroutine)

纤程(fiber)通常特指Windows对协程的实现

调度方案

普通Schedule(调度)

Context Switch(上下文切换):各种寄存器内存等状态的保存

不可抢占: 只能自己释放优点减少了切换开销缺点相应延迟等

可抢占优点延迟小缺点上下文切换开销

性能指标

CPU使用率(通常达到40%~90%)

吞吐量: 每秒做多少xx(事务啥的)

等待时间: 在queue里等的时间

响应时间: 提交开始到第一次运行的时间

调度算法

FIFO/FCFS(先到先服务)

Priority Scheduling(优先级调度)

优先级定义依据

时间限制

内存需要

打开文件数

CPU burst

I/O burst

缺点存在极端无限等待block(可随等待时间调整优先级)

Priority Scheduling with Multiple QueuesMultilevel Feedback Queue(多级反馈队列)

参数

队列数量

每个队列的调度算法

确定升级优先级的方法

确定降级优先级的方法

确定进程需要服务时进入哪个队列的方法

多处理器调度

方法

非对称多处理(asymmetric multiprocessing)

软亲和性

硬亲和性

负载均衡

实时CPU调度即有DDL之类的

软实时系统(soft real-time system)只保证关键进程优先级高点

硬实时系统(hard real-time system)要求一个任务在截止期限前必须完成

案例

算法评估

仿真使用实际负载例子跑一遍

逻辑地址空间

分配

最优适配(Best-Fit): 满足要求的剩余最小的孔

最差适应(Worst-Fit): 分配最大的孔

段错误: 读写非法区域

空闲块组织形式

隐式空闲链表(相当于要遍历所有块)

显式空闲链表(free时加next和prev指针)

MMU(On-CPU Device)

页表

frame(帧)地址

按需调页(Demanding Page)访问的时候若invalid就触发Page Fault中断来分配一个Page

页表替换算法

FIFO页面置换: 置换最旧的页面

LRU(最近最少使用)页面置换

实现方式

计数器

堆栈

近似LRU页面置换

需多次访存怎么缓解？

扩大页表

内部碎片化

重复数据删除(Deduplication)机会变小

TLB缓存(相联存储器)

有效内存访问时间EAT=(t+ε)α+(2t+ε)(1-α)

其他类型页表

多级页表: 将页号进一步分

Hash页表

Inverted Page Table(倒置页表)

帧分配

分配算法

比例分配根据进程大小的比例分配可结合考虑优先权

系统抖动(thrashing)

工作集模型: 估计需要帧数

工作集大小WSS其和大于m就会抖动

内核内存管理

伙伴系统

slab分配

大容量管理

磁盘管理

坏块管理正常来说有个上限

Sector Sparing/Forwarding调到别的地方可能影响调度效率

Sector Slipping坏了就写到接下来一个扇区可能出现数据移动但这样能够使队磁盘调度的影响小

扇区结构

数据区域(通常512KB)

使用

分区

磁盘调度

FCFS调度(先到先服务)

固态硬盘SSD

特点

non-volatile

shock resisting

high speed

low energy consumption

外部接口

Flash Controller

软件层

Flush Mux/Demux

通道连接芯片(闪存颗粒)

erase(只能以block为单位)

逻辑上

读的时候(写就反过来)Page-->registers-[bus]->(controller)

Overwrite: no in-place overwrite

Address Mapping

Sector Mapping

Block Mapping

Hybrid Mapping

Log-Structured Mapping

Garbage Collection

Wear-leveling

RISC V

Instruction Formats

I-type

ADDI

SLTI: Set Less Than Imm

shift instructions

R-type

S-type

branch

UJ-type

J/JAL

HTML

速查手册

文本类

html: 描述网页

body: 网页可见内容

背景色信息: bgcolor=\"yellow\"

对齐方式: align=\"center\"

p: 段落

br: 换行

<hr />: 分割线

链接类

a: 链接

href: 链接地址

图表类

img: 图像

src: 图源

width: 宽

height: 高

area: 定义可点击区域

table: 表格

<tr></tr>: 行

<td></td>: 行内单元格

board: 边框

<th></th>: 表头单元格(大多数浏览器作加粗居中处理)

<td> </td>: 空格占位格

响应式设计: 随屏幕大小调整(bootstrap)

框架: 显示多个html文档内联框架: 页面内显示页面

头部元素

<title>

<base>

<link>

<meta>

<style>

字符实体

字符实体大全

表单: 各种input元素

input: 输入

文本框: <input type=\"text\" name=\"firstname\">

单选按钮: <input type=\"radio\" name=\"sex\" value=\"male\" checked>Male

提交: <input type=\"submit\" value=\"Submit\">

method: 指定http方法(GET/POST)

name: 设置该属性每个字段才能正确提交

input的输入类型

select: 下拉列表

textarea: 多行文本框

button: 可点击按钮

fieldset: 组合表单数据

注释:

 收藏

立即使用

Knowledge

RabbitWhite

职业：undergraduate

去主页





0 条评论

回复删除



取消

下一页