Knowledge
2020-08-26 10:27:40 0 举报AI智能生成
知识
作者其他创作
大纲/内容
Knowledge
linux
概念
linux面试题
文件系统
硬链接/软链接
硬链接: 直接链接到inode上(故删除原文件并不会导致链接失效)
软链接: 用目录作链接(故原文件不在对应目录下则链接失效)
inode(索引节点):Linux 文件系统通过把 inode 节点和文件名进行连.需要读取该文件时，文件系统在当前目录表中查找该文件名对应的项，由此得到该文件相对应的 inode 节点号.通过该 inode 节点的磁盘地址表把分散存放的文件物理块连接成文件的逻辑结构。
安全
CC攻击: 多个不同用户不停访问
shell
常用命令
文件管理
文件处理
cp
mv
rm
查找
find:find pathname -options [-print -exec -ok ...]
which:查看可执行文件的位置(搜PATH)
whereis: whereis 查看文件的位置
文件内容查看
head
more
less
grep:grep [option] pattern file|dir
wc
sed: 文件编辑命令
sed
ln: 建立链接ln -sv source.log link.log
chmod:文件类型/文件所有者/用户组/其他_/rwx/rwx/rwx
chown:chown <所有者>:<用户组> <文件名>
磁盘命令
cd
df: 磁盘使用情况
du: 查看文件和目录的使用空间
ls
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
re
.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分布-百度百科
数字特征
均值
方差
协方差/协方差矩阵
相关系数
平均绝对差 E|X-EX|
矩母函数: g(t)=E exp{tX}
特征函数: Φ(t)=E exp{itX}两个变量分布相同⇔特征函数相同
极限理论
大数定律
Markov不等式
Chebyshev不等式
中心极限定理
中心极限定理推广(研究生课程)(不需要i.i.d. 而是Linderberg条件)
数理统计
基础
样本的两重性
统计量
样本均值
样本方差
样本矩
样本原点矩
样本中心矩
样本中位数
样本极值
正态总体
四个推论
三大分布
χ²分布
F分布
参数估计
点估计
矩估计
极大似然估计
区间估计
单正态总体
二正态总体
假设检验
参数检验
显著性水平
拒绝域
功效函数:β(θ)=P(H0被拒绝|θ)
拟合优度检验:检验分布
卡方拟合优度检验(Karl Pearson提出)
离散情形拟合优度检验
p-value: 对应卡方分布上的P(t>统计量T)
应用
独立性检验问题
H0: 属性A与属性B独立
齐一性检验: 检验一个属性A各个水平对应的另一个属性B的分布完全相同
数理逻辑
命题演算 L
语法对公式运算¬¬x≠x
L1: P→(q→p)——肯定后件律
L2: (p→(q→r))→((p→q)→(p→r))——蕴含词分配律
L3: (¬p→¬q)→(q→p)——换位律
P21
1). 同一律: ⊢p→p
2). 否定前件律: ⊢¬q→(q→p)
5). 否定肯定律(P24): ⊢(¬p→p)→p
8). 双否律: ⊢¬¬p→p9). 第二双否律⊢p→¬¬p
真值指派: v₀: X→Z₂
各种律——P41
语义演绎定理——P42
(主)析取范式与(主)合取范式——1.5.2(P50)
谓词演算 K
语法
公式集——P64
公理——P67
(K1) p→(q→p)
(K2) (p→(q→r))→((p→q)→(p→r))
(K3) (¬p→¬q)→(q→p)
证明——P67
MP
Gen
一些定理或永真式
∃1规则——P69
演绎定理——P70
∃2规则——P71
等价判定(P72): Γ⊢p↔q ⇔ Γ⊢p→q且Γ⊢q→p
子公式的等价可替换性——P74
对偶律——P75
前束范式
2.
3. ⊢¬Qxp ↔ Q*x¬p
涉及合取析取(P78-80)
⊢(∀xp∧∀xq) ↔ ∀x(p∧q)
⊢(∃xp∨∃xq) ↔ ∃x(p∨q)
⊢(p∨Qxq) ↔ Qx(p∨q)
⊢(p∧Qxq) ↔ Qx(p∧q)
语义
项解释——P83
个体变元指派
变元变通——解释含量词公式
公式的赋值函数——P85
闭式的语义特征
任一闭式在给定M中恒真/恒假必居其一
全称闭式——P90
|p|=1⇔|∀xp|=1⇔|p'|=1
|p|=0 ⇒ |∀xp|=0|p|=0 ⇒ |p'|=0
语义推论与有效式——P92
M可满足的
存在I(p)=t
M有效的
模型: Γ的每个公式都在M恒真:r∈Γ ⇒ |r|_M=1
语义推论/语义后承: Γ⊧p
UG有效性: Γ⊧p ⇔ Γ⊧∀xp
K的可靠性和完全性
形式算数与递归函数
等词公理(P105)
(E1) t≈t
E ⊢ t≈tE ⊢ t≈u → u≈tE ⊢ t≈u → (u≈v → t≈v)
等项替换(P108)
(E2推广) E ⊢ u≈v → t(u)≈t(v)
(E3推广) E ⊢ t≈u → (p(t) → p(u))(t和u的变元不在替换出受约束)
正规模型: 等词解释为相等
符号
set
∩
∪
⊆
∈
∅
⁰ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹
₀ ₁ ₂ ₃ ₄ ₅ ₆ ₇ ₈ ₉
ᵢ ⱼ ₖ ₗ ₘ ₙ
logic
→
⇒
⇔
↔
∧
∨
¬
⊧
⊢
∀
∃
≠
数理方程
建立方程的问题
物理定律
牛顿第二定律(F=ma)
物体内温度升高所需热量与物体内源产生热量之和
Gauss定律通过任意闭合曲面的电通量等于这个闭曲面所包围的自由电荷的电量/ε0
初始条件个数=t的导数的阶数
边界条件
第一类: u在边界上=φ
固定端
第二类: 偏导在边界上=φ
绝热自由端
第三类: αu+β偏导=φ
热交换
泛定方程
分类
Δu=f (Poisson方程)(非齐次)
Lu=0
Lu=f
抛物(发展方程)
u_{t}=Δu (齐次)
u_{t}=Δu+f (非齐次)
u_{t}=Lu+f (齐次)
u_{t}=Lu (非齐次)
双曲(发展方程)
u_{tt}=Δu (齐次)
u_{tt}=Δu+f (非齐次)
u_{tt}=Lu (齐次)
u_{tt}=Lu+f (非齐次)
齐次泛定方程
有界区域
步骤:分离变量解固有值问题写出级数解
分离变量法
普通方程(Sturm-Liouville方程)
贝塞尔方程(柱坐标系)
勒让德方程(球坐标系)
非齐次泛定方程
边界条件齐次
固有函数展开法后再分离变量法
叠加原理
特殊函数法
边界条件非齐次
泊松方程第一边值问题
基本解法
不考虑边界条件齐次性
Laplace变换主要半无界问题ODE都可求span style=\"font-size: inherit;\
√有关于趋于无穷的条件
变量取值范围为全无穷
傅里叶变换(291-296)
变量取值范围为半无穷
第一类边界条件(延拓为奇函数)
傅里叶正弦变换
第二类边界条件(延拓为偶函数)
傅里叶余弦变换(P296例3)
第三类边界条件(超出本书学习范围)
×无关于无穷点的条件
Laplace变换要求有变换变量<通常是t>对应各低阶导数在0+的条件无穷处一般应有界(问题的物理意义)半无界(因此通常对t)
叠加原理和齐次化原理
无界区域
一维无界
行波法(达朗贝尔公式)
一维半无界
尝试延拓第一类边界条件奇延拓第二类边界条件偶延拓
一维无界区域弦振动
一维半无界区域
行波法作奇偶延拓
非齐次发展方程
齐次化原理
方程非齐次的方程
边界条件非齐次的方程
齐次有界区域方程
齐次有界区域方程——极坐标下Δu=0的周期性问题
套用公式
运筹学基础
规划问题
线性规划
凸组合理论
线性规划可行域必为凸集
基可行解对应于可行域的顶点
目标函数在可行域(有界情况下)的顶点上达到最优
单纯形法
表格描述
矩阵描述
对偶理论
对偶单纯形法
原问题max zn个变量≥0≤0无约束m个约束≤≥=
对偶问题min ωn个约束≥≤=m个变量≥0≤0无约束
性质(P68 3..4.2)
对称性: 对偶问题的对偶是原问题
检验数和基解的对应: 原问题单纯形表的检验数行对应对偶问题的一个基解
灵敏度分析(本质还是单纯形法)
运输问题
确定初始基可行解
西北角法: 每次取西北角的
最小元素法: 每次取最小运价的确定
最优解的判别(本质是要算出检验数)
调整方法
线性目标规划
解法: 主要为图解法或单纯形表法
整数线性规划
普通整数线性规划
0-1型整数线性规划
指派问题
理论基础
解法
排队论
数学模型: Kendall记号: X/Y/Z(后扩充为X/Y/Z/A/B/C本书只讨论X/Y/Z/∞/∞/FCFS)
X: 相继顾客到达间隔时间的分布
Y: 服务时间的分布
Z: 服务台的个数
A: 系统容量限制NB: 顾客源数目mC: 服务规则(FCFS/LCFS等)
各种分布
M: 负指数分布
D: 确定型
E_k: k阶爱尔朗分布(erlang)
GI: 一般相互独立的时间间隔分布
G: 一般服务时间的分布
基本概念符号
排队系统概念
队长: 系统中顾客数. 期望为L_s排队长: 系统中排队等待的顾客数. 期望为L_q
逗留时间: 一个顾客在系统中停留时间. 期望为W_s等待时间: 一个顾客在系统中排队等待的时间. 期望为W_q
忙期: 服务机构连续繁忙时间长度(关系到服务员工作强度)
系统的状态: 系统中顾客数(期望为L_s)系统中有n个顾客就称系统状态为nt时刻状态为n概率为P_n(t)
一些平均值概念
平均间隔时间=总间隔时间/到达次数=总时间/到达次数
平均到达率=到达人数/总时间
平均服务时间=总服务时间/总人数
平均服务率=总人数/总服务时间
常用分布
泊松流
形成泊松流的条件
无后效性: 不重叠时间区间顾客到达独立.
泊松流概率公式
数学期望: E[N(t)] = λt方差: Var[N(t)] = λt
负指数分布
负指数分布概率密度函数
负指数分布函数
负指数分布数字特征
其他性质
Markov性
相继到达的时间间隔是独立相同的负指数分布(参数为λ)与输入过程为泊松流(参数为λ)是等价的.所以在Kendall记号中都用M表示
爱尔朗分布(Erlang):参数为kμ的k个指数分布和
Erlang分布的概率密度函数
Erlang分布的数字特征
Little公式
逗留时间(W_s)内有效到达的顾客数(λ_e*W_s)为队列长(L_s)？
存储论
主要符号:需求速度R; 生产速度P; 经济订购批量Q0; 最大存储量S0; 最大缺货量B0存储费C1; 缺货费C2; 订购费C3货物单价K;
基本概念
需求: 从存储中间断式或连续式地取出一定量
补充: 备货时间(或称提前时间)
存储策略
模型
价格有折扣的存储问题
订货方式
定点订货定时订货定量订货
计算机组成原理
CPU
技术指标
CPI
IC
主频
加速比(Amdahl定律)
部件加速比
可改进比例
周期
机器周期
时钟周期: 包含多个机器周期
指令周期: 包含多个时钟周期
流水线
还没复习
相关
冲突
结构相关
数据相关
控制相关
吞吐率
加速比
效率
数据通路(2020-03-312020-04-03)
控制信号(2020-03-312020-04-03)
相关(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)
OS
进程管理
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>
<script>
<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: 组合表单数据
注释: <!--注释内容-->
收藏
职业：undergraduate
0 条评论
回复 删除
下一页
