Jepson's Blog

CSMA/CD 协议

CSMA/CD 表示载波监听多点接入 / 碰撞检测。

多点接入 ：说明这是总线型网络，许多主机以多点的方式连接到总线上。
载波监听 ：每个主机都必须不停地监听信道。在发送前，如果监听到信道正在使用，就必须等待。
碰撞检测 ：在发送中，如果监听到信道已有其它主机正在发送数据，就表示发生了碰撞。虽然每个主机在发送数据之前都已经监听到信道为空闲，但是由于电磁波的传播时延的存在，还是有可能会发生碰撞。

记端到端的传播时延为 τ，最先发送的站点最多经过 2τ 就可以知道是否发生了碰撞，称 2τ 为 争用期 。只有经过争用期之后还没有检测到碰撞，才能肯定这次发送不会发生碰撞。

当发生碰撞时，站点要停止发送，等待一段时间再发送。这个时间采用 截断二进制指数退避算法 来确定。从离散的整数集合 {0, 1, .., (2k-1)} 中随机取出一个数，记作 r，然后取 r 倍的争用期作为重传等待时间。

五层协议

1. 应用层 ：为特定应用程序提供数据传输服务，例如 HTTP、DNS 等协议。数据单位为报文。

2. 传输层 ：为进程提供通用数据传输服务。由于应用层协议很多，定义通用的传输层协议就可以支持不断增多的应用层协议。运输层包括两种协议：传输控制协议 TCP，提供面向连接、可靠的数据传输服务，数据单位为报文段；用户数据报协议 UDP，提供无连接、尽最大努力的数据传输服务，数据单位为用户数据报。TCP 主要提供完整性服务，UDP 主要提供及时性服务。

3. 网络层 ：为主机提供数据传输服务。而传输层协议是为主机中的进程提供数据传输服务。网络层把传输层传递下来的报文段或者用户数据报封装成分组。

4. 数据链路层 ：网络层针对的还是主机之间的数据传输服务，而主机之间可以有很多链路，链路层协议就是为同一链路的主机提供数据传输服务。数据链路层把网络层传下来的分组封装成帧。

5. 物理层 ：考虑的是怎样在传输媒体上传输数据比特流，而不是指具体的传输媒体。物理层的作用是尽可能屏蔽传输媒体和通信手段的差异，使数据链路层感觉不到这些差异。

七层协议

七层协议就是把五层协议中的应用层拆分成会话层、表示层和应用层。

1. 表示层 ：数据压缩、加密以及数据描述，这使得应用程序不必关心在各台主机中数据内部格式不同的问题。

2. 会话层 ：建立及管理会话。

磁盘调度算法

读写一个磁盘块的时间的影响因素有：

旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）
寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
实际的数据传输时间

其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

1. 先来先服务

   FCFS, First Come First Served

   按照磁盘请求的顺序进行调度。

   优点是公平和简单。缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。

2. 最短寻道时间优先

   SSTF, Shortest Seek Time First

   优先调度与当前磁头所在磁道距离最近的磁道。

   虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。

   

3. 电梯算法

   电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。

   电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。

   因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。

   

连续中值

随机产生数字并传递给一个方法。你能否完成这个方法，在每次产生新值时，寻找当前所有值的中间值（中位数）并保存。

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

示例：

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2

思路

数组分两半，左边建大顶堆维护左半部分的最大值，右边建小顶堆维护右半部分的最小值，两个堆顶的均值就是数组的中值。每次插入数据的时候判断一下：

如果要插入的数据比右边小顶堆堆顶小，则插到左边；
如果要插入的数据比左边大顶堆堆顶大，则插到右边；
如果介于二者中间，也插到右边，

同时要保证右边的小顶堆长度最多比左边的大顶堆大1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
priority_queue<int, vector<int>, less<int> >bigheap;
priority_queue<int, vector<int>, greater<int> >smallheap;

MedianFinder() {

}

void addNum(int num) {
    if(bigheap.size()==0&&smallheap.size()<=1) smallheap.push(num);
    else if(num<smallheap.top()) bigheap.push(num);
    else if(num>bigheap.top()) smallheap.push(num);
    else bigheap.push(num);

    if(smallheap.size()>bigheap.size()+1){
        bigheap.push(smallheap.top());
        smallheap.pop();
    }
    if(bigheap.size()>smallheap.size()){
        smallheap.push(bigheap.top());
        bigheap.pop();
    }
}

double findMedian() {
    if(smallheap.size()>bigheap.size()) return smallheap.top();
    return 1.0*(smallheap.top()+bigheap.top())/2;
}