2012年2月4日星期六
awk & sed命令总结
awk
file 整个文件
record 文件中一行转为一个record，awk每次处理一个record
field record由field组成，如$1,$2，$0表示真个record
例子：
file s.c
1 2
3 4
awk '{d=($1 + $2); print d}' s.c
输出：
3
7
awk匹配模式从流中提取自己需要的内容：
awk -F "\"" '{printf "msgid ""\""$2"\"""\n""msgstr \"\"\n\n"}' pc_err.c
在线资料
http://sed.sourceforge.net/sed1line_zh-CN.html
sed(stream editor)
commands = pattern + action.
$ matches the end of line
^ matches the beginning of the line
sed -e '1,10d'
删除stdin输入中的前10行，并将其余输出stdout
-e 把 '1,10d'当作sed语句来执行
1,10 pattern
d action
sed -n -e '/1/p' z.c
输出z.c中匹配1的行
-n 不输出test.txt原文的内容
sed -e '3,$d'
sed -n -e '1,2p'
sed -e '2q'
$表示文本的最后一样，d表示delete
q表示quit
输出流的前两行
sed -e '1,2d' -e '4,5d' z.c
同时指定多个-e
grep 'foo' log | grep -v 'debug' == sed -n -e '/debug/d' -e '/foo/p' log
sed -e 's/PC_NO_MATCH) goto ret;/PC_NO_MATCH) {ret = PC_ERR_RECORD_REPEAT; goto ret;}/' -i *.c
sed -e 's/str1/str2/' -i *.c
把当前目录下所有c文件中的str1替换为str2
在线资料
http://www.tsnc.edu.cn/default/tsnc_wgrj/doc/abs-3.9.1_cn/html/sedawk.html
2012年2月3日星期五
折半查找的实现
折半查找又成为二分查找，常用来对有序的线性表做元素查找。适用于一经建立，很少改变并且经常查找的场景。
实现如下：
使用二分思想，求平方根的函数：
实现如下：
/**
* Function binary_search (number, array, array_len)
*
* Returns
* -1,if not found.index of array,if found.
*
* Parameters
* @number: the nubmer waiting for search
* @array: search array pointer
* @array_len: esarch array len
*
* Description
* premise that array is orderly.
*
**/
static int binary_search(int number, int *array, int array_len)
{
int mid, start = 0, end = array_len - 1;
while (start <= end) {
mid = (start + end) / 2;
if (array[mid] < number)
start = mid + 1;
else if (array[mid] > number)
end = mid - 1;
else
return mid;
}
return -1;
}
* Function binary_search (number, array, array_len)
*
* Returns
* -1,if not found.index of array,if found.
*
* Parameters
* @number: the nubmer waiting for search
* @array: search array pointer
* @array_len: esarch array len
*
* Description
* premise that array is orderly.
*
**/
static int binary_search(int number, int *array, int array_len)
{
int mid, start = 0, end = array_len - 1;
while (start <= end) {
mid = (start + end) / 2;
if (array[mid] < number)
start = mid + 1;
else if (array[mid] > number)
end = mid - 1;
else
return mid;
}
return -1;
}
使用二分思想，求平方根的函数：
/**
* Function mysqrt (y, precision)
*
* Returns
*
*
* Parameters
* @y:
* @precision:
*
* Description
* 求y的平方根,x*x == y
*
**/
static double mysqrt(double y, double precision)
{
double x, start = 0.0, end = y;
assert(y > 0.0);
while (1) {
x = (start + end) / 2;
if (x*x < y)
start = x;
else
end = x;
if (fabs(x*x - y) < precision)
break;
}
return x;
}
* Function mysqrt (y, precision)
*
* Returns
*
*
* Parameters
* @y:
* @precision:
*
* Description
* 求y的平方根,x*x == y
*
**/
static double mysqrt(double y, double precision)
{
double x, start = 0.0, end = y;
assert(y > 0.0);
while (1) {
x = (start + end) / 2;
if (x*x < y)
start = x;
else
end = x;
if (fabs(x*x - y) < precision)
break;
}
return x;
}
TCP/IP详解卷一摘抄
算下来，这是我第四次读《TCP/IP详解-卷一》了，读大学时读过一遍，那时懵懵懂懂，工作后又读过三遍，加上工作中的实践，理解渐渐加深。我想这样的经典读十遍也不为过。
UDP
11.10 限制最大UDP长度的因素
1、IP数据包长度字段，16位的限制。最大为65535 - 20 - 8
2、sockt API接口限制，用户可以修改此值，APUE上有讲
3、内核TCP/IP协议栈的实现。
UDP为数据报协议，需要由应用层控制UDP单包大小，避免IP分片提高效率。
TCP
半关闭：TCP提供一种结束一端发送，但还可以继续接收数据的能力。
半打开：如果一端已经关闭或异常终结，而另一端还不知道，则称这种状态为半打开。
呼入连接请求队列(listen)
1、完成三次握手后，TCP会把连接放入请求队列，应用层从队列中取连接。
2、当队列满之后，TCP不会理会新到的SYN请求，且不发送RST回复。
交互数据包特性（小包）
1、经受时延的确认ACK；实现数据包捎带ACK，减少包数量。
2、Nagle算法；算法要求一个TCP连接上最多只能有一个未被确认的未完成的小分组，该分组的确认到达之前不能发送其它小分组。这样，TCP可以收集多个小分组，等到确认ACK到达时，一并发出去。这样减少了网络上小分组的数量，减轻了慢速网络的压力。算法自适应特点：确认到达的越快，数据发送的也越快。这是一种流量控制的算法。
Nagle算法并不适用所有环境，如X环境下需要关闭Nagle算法。
成块数据包特性（大包）
滑动窗口（通告窗口）：
是TCP的一种流量控制方法，其中窗口的大小由应用程序控制。
慢启动：
增加拥塞窗口，简称cwnd；一种在连接上发起数据流的方法。窗口初始化为1个报文单位，收到一个ack则增加1个报文单位，发送窗口取拥塞窗口和通告窗口（滑动窗口）的最小值。
拥塞窗口是发送方的流量控制，通告窗口是接收方的拥塞控制。
超时与重传：
发送包后设置一个定时器（重传定时器），若定时器超时时间内未收到ACK确认，则重传数据包。
当定时器超时、收到重复的ACK时，则认为网络发生了拥塞，就需要启动拥塞避免算法。
拥塞避免算法：
一种处理丢失分组的方法。算法假定分组受损坏而丢失的可能性是非常少的，分组丢失就意味着在源目的地址中间发生了拥塞。
拥塞避免算法和慢启动算法维护两个变量，一个拥塞窗口cwnd，一个慢启动门限ssthresh。
1）对一个新连接，cwnd初始化为1个报文段，ssthresh初始化为65535字节。
2）TCP的输出不能超过拥塞窗口cwnd和接收方的通告窗口。
3）当拥塞发生时，ssthresh被置为当前窗口的一半（cwnd和通告窗口的最小值，不小于两个报文段），当因为超时引起拥塞时，将cwnd置为1个报文段（启动慢启动）。
4）当收到新的数据的确认ACK时则增加cwnd。如果cwnd小于等于ssthresh，则执行慢启动，每个ACK确认cwnd增1；当cwnd大于ssthresh时，则执行拥塞避免每个ACK确认cwnd增加1/cwnd。
Jacobson快速重传算法：
当收到3个ACK时，就假定那个报文已经丢失，并重传ACK序号开始的那个报文段。
Jacobson快速重传算法、快速恢复算法（两个算法，常配合使用）
当收到3个重复的ACK时，不等待超时，马上重传丢失报文，这是快速重传算法。
重传之后，不执行慢启动而执行拥塞避免算法，这称为快速恢复算法。
1）当收到3个重复ACK后，将ssthresh设置为拥塞窗口cwnd的一半，重传丢失的报文。设置cwnd为ssthresh加三倍报文段大小。(根据图21-10、21-11并没有将cwnd设置为ssthresh加三倍报文？)
2）每收到一个重复的ACK，则cwnd加1并发送1个分组（如果新的cwnd允许发送）。
3）当下一个确认新数据的ACK达到时，设置cwnd为ssthresh（第1步中设置的值）。这一步采用的拥塞避免，因为分组丢失时我们将当前速率减半。
ssthresh立即设置为当重传发生 时正在起作用的窗口大小的一半,但是在接收到重复 ACK的过程中cwnd允许保持增加,这是 因为每个重复的 ACK表示1个报文段已离开了网络(接收 TCP已缓存了这个报文段,等待所缺 数据的到达)。这就是快速恢复算法。
坚持定时器
能够处理TCP打开窗口ACK丢失的情况。由发送方来维护坚持定时器，来周期性的查询（使用指数退避算法）窗口大小。TCP从不放弃窗口探测。
糊涂窗口综合征
接收方通告一个小的窗口，而发送方也可以发送小量的数据。造成频繁发送小包。
保活定时器
发现一个TCP连接何时断掉。主要用在服务器。
TCP特性：
1、流量控制；Nagle算法、滑动窗口、慢启动
2、拥塞控制；慢启动、拥塞避免、快速重传
问题：
Nagle算法和滑动窗口的选择
TCP内核有mytcp_nagle_testv函数，此函数来判断这个数据包是否使用nagle算法，之后再调用tcp_cwnd_test判断是否使用滑动窗口算法。
是否使用nagle算法和包的属性（SYN、FIN），包的大小有关。一半认为小于MSS的数据包都属于小包。
http://blog.sina.com.cn/s/blog_54b5ea250100g2xu.html
LAST_ACK 状态有超时机制吗？这个状态合适消失？
这个和普通数据包的超时机制相同，发送FIN包之后进入LAST_ACK状态，如果超时之前没有收到ACK，则会重发FIN包。
留下一个疑问没有解决，上文标红快速恢复算法图21-10问题，不急，等下次重读再说。
UDP
11.10 限制最大UDP长度的因素
1、IP数据包长度字段，16位的限制。最大为65535 - 20 - 8
2、sockt API接口限制，用户可以修改此值，APUE上有讲
3、内核TCP/IP协议栈的实现。
UDP为数据报协议，需要由应用层控制UDP单包大小，避免IP分片提高效率。
TCP
半关闭：TCP提供一种结束一端发送，但还可以继续接收数据的能力。
半打开：如果一端已经关闭或异常终结，而另一端还不知道，则称这种状态为半打开。
呼入连接请求队列(listen)
1、完成三次握手后，TCP会把连接放入请求队列，应用层从队列中取连接。
2、当队列满之后，TCP不会理会新到的SYN请求，且不发送RST回复。
交互数据包特性（小包）
1、经受时延的确认ACK；实现数据包捎带ACK，减少包数量。
2、Nagle算法；算法要求一个TCP连接上最多只能有一个未被确认的未完成的小分组，该分组的确认到达之前不能发送其它小分组。这样，TCP可以收集多个小分组，等到确认ACK到达时，一并发出去。这样减少了网络上小分组的数量，减轻了慢速网络的压力。算法自适应特点：确认到达的越快，数据发送的也越快。这是一种流量控制的算法。
Nagle算法并不适用所有环境，如X环境下需要关闭Nagle算法。
成块数据包特性（大包）
滑动窗口（通告窗口）：
是TCP的一种流量控制方法，其中窗口的大小由应用程序控制。
慢启动：
增加拥塞窗口，简称cwnd；一种在连接上发起数据流的方法。窗口初始化为1个报文单位，收到一个ack则增加1个报文单位，发送窗口取拥塞窗口和通告窗口（滑动窗口）的最小值。
拥塞窗口是发送方的流量控制，通告窗口是接收方的拥塞控制。
超时与重传：
发送包后设置一个定时器（重传定时器），若定时器超时时间内未收到ACK确认，则重传数据包。
当定时器超时、收到重复的ACK时，则认为网络发生了拥塞，就需要启动拥塞避免算法。
拥塞避免算法：
一种处理丢失分组的方法。算法假定分组受损坏而丢失的可能性是非常少的，分组丢失就意味着在源目的地址中间发生了拥塞。
拥塞避免算法和慢启动算法维护两个变量，一个拥塞窗口cwnd，一个慢启动门限ssthresh。
1）对一个新连接，cwnd初始化为1个报文段，ssthresh初始化为65535字节。
2）TCP的输出不能超过拥塞窗口cwnd和接收方的通告窗口。
3）当拥塞发生时，ssthresh被置为当前窗口的一半（cwnd和通告窗口的最小值，不小于两个报文段），当因为超时引起拥塞时，将cwnd置为1个报文段（启动慢启动）。
4）当收到新的数据的确认ACK时则增加cwnd。如果cwnd小于等于ssthresh，则执行慢启动，每个ACK确认cwnd增1；当cwnd大于ssthresh时，则执行拥塞避免每个ACK确认cwnd增加1/cwnd。
Jacobson快速重传算法：
当收到3个ACK时，就假定那个报文已经丢失，并重传ACK序号开始的那个报文段。
Jacobson快速重传算法、快速恢复算法（两个算法，常配合使用）
当收到3个重复的ACK时，不等待超时，马上重传丢失报文，这是快速重传算法。
重传之后，不执行慢启动而执行拥塞避免算法，这称为快速恢复算法。
1）当收到3个重复ACK后，将ssthresh设置为拥塞窗口cwnd的一半，重传丢失的报文。设置cwnd为ssthresh加三倍报文段大小。(根据图21-10、21-11并没有将cwnd设置为ssthresh加三倍报文？)
2）每收到一个重复的ACK，则cwnd加1并发送1个分组（如果新的cwnd允许发送）。
3）当下一个确认新数据的ACK达到时，设置cwnd为ssthresh（第1步中设置的值）。这一步采用的拥塞避免，因为分组丢失时我们将当前速率减半。
ssthresh立即设置为当重传发生 时正在起作用的窗口大小的一半,但是在接收到重复 ACK的过程中cwnd允许保持增加,这是 因为每个重复的 ACK表示1个报文段已离开了网络(接收 TCP已缓存了这个报文段,等待所缺 数据的到达)。这就是快速恢复算法。
坚持定时器
能够处理TCP打开窗口ACK丢失的情况。由发送方来维护坚持定时器，来周期性的查询（使用指数退避算法）窗口大小。TCP从不放弃窗口探测。
糊涂窗口综合征
接收方通告一个小的窗口，而发送方也可以发送小量的数据。造成频繁发送小包。
保活定时器
发现一个TCP连接何时断掉。主要用在服务器。
TCP特性：
1、流量控制；Nagle算法、滑动窗口、慢启动
2、拥塞控制；慢启动、拥塞避免、快速重传
问题：
Nagle算法和滑动窗口的选择
TCP内核有mytcp_nagle_testv函数，此函数来判断这个数据包是否使用nagle算法，之后再调用tcp_cwnd_test判断是否使用滑动窗口算法。
是否使用nagle算法和包的属性（SYN、FIN），包的大小有关。一半认为小于MSS的数据包都属于小包。
http://blog.sina.com.cn/s/blog_54b5ea250100g2xu.html
LAST_ACK 状态有超时机制吗？这个状态合适消失？
这个和普通数据包的超时机制相同，发送FIN包之后进入LAST_ACK状态，如果超时之前没有收到ACK，则会重发FIN包。
留下一个疑问没有解决，上文标红快速恢复算法图21-10问题，不急，等下次重读再说。
订阅：
博文 (Atom)