秋招总结之简历精解

zhyjc6于2020-11-16发布 约35195字·约78分钟 本文总阅读量次

自我介绍

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

基础

十大排序

  1. 冒泡排序

    void bubbleSort(vector<int> &arr) {
    if (arr.empty()) return;
	int n = arr.size();
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n - 1 - i; j++) {
			if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
			}
		}
	}
}

  2. 选择排序

    void selectSort(vector<int> &arr) {
    int n = arr.size();
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            swap(arr[minIndex], arr[i]);
        }
    }
}

  3. 插入排序

    void insertSort(vector<int> &arr){
    if (arr.empty()) return;
    for (int i = 1; i < arr.size(); i++) {
        int temp = arr[i];
        int j = i;
        while (j > 0 && temp < arr[j-1]){
            arr[j] = arr[j-1];
            j--;
        }   
        arr[j] = temp;
    }   
}

  4. 希尔排序

    void shellSort(vector<int> &arr) {
    if (arr.empty()) return;
    int n = arr.size();
    for (int gap = n/2; gap > 0; gap >>= 1) {
        for (int i = gap; i < n; i++) {//插入排序
            int temp = arr[i];
            int j = i;
            while (j-gap >= 0 && arr[j] < arr[j-gap]) {
                arr[j] = arr[j-gap];
                j -= gap;
            }
            arr[j] = temp;
        }   
    }
}

  5. 归并排序

    void merge(vector<int> &arr, int left, int mid, int right) {
    vector<int> temp(right-left+1);
    int i = left, j = mid+1, k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    //下面这两个while只会执行其中一个
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    for (int idx = 0; idx < temp.size(); idx++) {
        arr[left+idx] = temp[idx];
    }
}
void mergesort(vector<int> &arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right-left)/2;
    mergesort(arr, left, mid);
    mergesort(arr, mid+1, right);
    merge(arr, left, mid, right);
}
void mergeSort(vector<int> &arr) {
	if (arr.empty()) return;
    mergesort(arr, 0, arr.size()-1);
}

  6. 快速排序

    int partition(vector<int> &arr, int left, int right) {
    int pivot = left;
    int less = left + 1;
    for (int i = left+1; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr[less++], arr[i]);
        }
    }
    swap(arr[--less], arr[pivot]);
    return less;
}
void quicksort(vector<int> &arr, int left, int right) {
    if (left >= right) return;
    int mid = partition(arr, left, right);
    quicksort(arr, left, mid-1);
    quicksort(arr, mid+1, right);
}
void quickSort(vector<int> &arr) {
    if (arr.empty()) return;
    quicksort(arr, 0, arr.size()-1);
}

  7. 堆排序

    建堆的时间复杂度为O(n)

    void heapfy(vector<int> &arr, int root, int curLen) {//curLen是当前堆长度，也是堆外第一个元素索引
    int max_idx = root,
        left = 2 * root,
        right = 2 * root + 1;
    if (left < curLen && arr[left] > arr[max_idx]) {
        max_idx = left;
    }
    if (right < curLen && arr[right] > arr[max_idx]) {
        max_idx = right;
    }
    if (max_idx != root) {
        swap(arr[root], arr[max_idx]);
        heapfy(arr, max_idx, curLen);
    }
}
   
void buildHeap(vector<int> & arr) {
    for (int i = arr.size()/2-1; i >= 0; i--) {//0--n/2为中间结点
        heapfy(arr, i, arr.size());
    }
}
   
void heapSort(vector<int> &arr) {
    buildHeap(arr);
    for (int i = arr.size()-1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapfy(arr, 0, i);
    }
}

  8. 计数排序

    void countSort(vector<int> &arr) {
    if (arr.empty()) return;
    int max_ = arr[0];
    for (auto &num : arr) {
        max_ = max(max_, num);
    }   
    vector<int> count(max_+1, 0); 
    for (auto &num : arr) {
        count[num]++;
    }   
    int k = 0;
    for (int i = 0; i <= max_; i++) {
        for (int j = 0; j < count[i]; j++) {
            arr[k++] = i;
        }   
    }
}

  9. 基数排序

    void radixSort(vector<int> &arr) {
    if (arr.empty()) return;
    int maxNum = arr[0];
    for (int &num : arr) {
        maxNum = max(maxNum, num);
    }
    int keys = 0;//关键字个数，即最长位数
    while (maxNum) {
        keys++;
        maxNum /= 10;
    }
   
    vector<vector<int>> bucket(10);//每一个关键字里只有10个不同元素（0-9）
    for (int i = 0; i < keys; i++) {//按照每一个关键字对所有待排元素排序
        for (int j = 0; j < arr.size(); j++) {
            int whichone = arr[j] / (int)(pow(10, i)) % 10;
            bucket[whichone].push_back(arr[j]);//将元素放入对应的桶中
        }
        int k = 0;
        for (int idx = 0; idx < 10; idx++) {//排序每一个桶，并按序放回原数组，清空每一个桶
            stable_sort(bucket[idx].begin(), bucket[idx].end());//稳定排序
            for (int num : bucket[idx]) {
                arr[k++] = num;//放回原数组
            }
            bucket[idx].clear();//清空桶
        }
    }
}

  10. 桶排序

   void bucketSort(vector<int> &arr) {
       if (arr.empty()) return;
       int min_ = arr[0], max_ = arr[0];
       for (int &num : arr) {
           min_ = min(min_, num);
           max_ = max(max_, num);
       }
       const int count_of_bucket = min(10, max_ - min_ + 1);
       const int size_of_bucket = (max_ - min_ + 1) / count_of_bucket + 1;
       vector<vector<int>> bucket(count_of_bucket);
   
       for (int &num : arr) {
           int whichone = (num - min_) / size_of_bucket;
           bucket[whichone].push_back(num);
       }
       int k = 0;//回填原数组
       for (int i = 0; i < count_of_bucket; i++) {
           sort(bucket[i].begin(), bucket[i].end());
           for (auto &num : bucket[i]) {
               arr[k++] = num;
           }
       }
   }

Linux常用命令

文件操作

命令 用途
ls 列出文件和文件夹
cd 更改当前路径
pwd 显示当前所在路径
mkdir 创建文件夹
touch 创建文件
mv 移动或重命名文件/文件夹
cp 复制文件/文件夹
rm 删除文件/文件夹
cat 显示文件内容
tar 压缩和解压缩成.tar包
head 显示文件开头10行内容
tail 显示文件结尾10行内容

系统信息

命令 用途
uname 查看Linux系统信息
uptime 查看系统运行时间和负载
hostname 查看主机名
last reboot 查看系统重启历史
last 查看当前用户上一次登录信息
whoami 查看当前我的登录名
w 查看当前登录用户的信息以及在做什么
free 查看内存使用情况
df (-h) 查看磁盘使用情况
du 查看磁盘使用情况
cat /proc/cpuinfo 查看cpu信息
cat /proc/meminfo 查看内存信息
top 查看进程信息
lsof 查看活跃进程打开的文件
ps 查看进程状态
   

网络操作

命令 用途
ifconfig 查看网络端口和ip地址
ping 检查主机网络是否连通
whois 查看域名信息
dig 查看域名或ip地址DNS信息
host 查看域名对应的ip地址
netstat 查看网络连接情况
wget 下载文件
   
   
   
   
   

搜索

命令 用途
grep 在不打开文件的情况下搜索文件中对应的字符串
locate 在数据库中查找对应的文件
find 在磁盘中查找文件
   
   
   
   

Linux下进程环境

进程终止

有8种方式使进程终止（termination），其中 5种为正常终止，它们是：

  1. 从main 返回
  2. 调用exit
  3. 调用 _exit或_Exit
  4. 最后一个线程从其启动例程返回
  5. 从最后一个线程调用pthread_exit

异常终止有3种方式，它们是：

  1. 调用abort
  2. 接到一个信号
  3. 最后一个线程对取消请求做出响应

函数atexit

按照ISO C的规定，一个进程可以登记多至32个函数，这些函数将由exit自动调用。我们称这些函数为终止处理程序（exit handler），并调用atexit函数来登记这些函数。

#include <stdlib.h>
int atexit(void (*func)(void)); //返回值：若成功，返回0；若出错，返回非0

其中，atexit 的参数是一个函数地址，当调用此函数时无需向它传递任何参数，也不期望它返回一个值。exit调用这些函数的顺序与它们登记时候的顺序相反。同一函数如若登记多次，也会被调用多次。

C程序的存储空间布局

存储空间分配函数

#include <stdlib.h>
void *malloc(size_t size);
void *calloc(size_t nobj, size_t size);
void *realloc(void *ptr, size_t newsize);
//3个函数返回值：若成功，返回非空指针；若出错，返回NULL

//函数free 释放ptr指向的存储空间
void free(void *ptr);

ISO C说明了3个用于存储空间动态分配的函数。

  1. malloc，分配指定字节数的存储区。此存储区中的初始值不确定。
  2. calloc，为指定数量指定长度的对象分配存储空间。该空间中的每一位（bit）都 初始化为0。
  3. realloc，增加或减少以前分配区的长度。当增加长度时，可能需将以前分配区 的内容 移到另一个足够大的区域，以便在尾端提供增加的存储区，而新增区域内的初始值则不确定。

Linux下进程间通信

管道

这个匿名管道是特殊的文件，只存在于内存，不存于文件系统中。

局限性

创建管道

通过pipe函数创建，经由参数 fd 返回两个文件描述符：fd[0]为读而打开，fd[1]为写而打开。fd[1]的输出是 fd[0]的输入。

#include <unistd.h>
int pipe(int fd[2]);
//返回值：若成功，返回0，若出错，返回-1

应用

单个进程中的管道几乎没有任何用处。通常，进程会先调用pipe，接着调用fork，从 而创建从父进程到子进程的IPC通道，反之亦然。图15-3显示了这种情况。

fork 之后做什么取决于我们想要的数据流的方向。对于从父进程到子进程的管道，父 进程关闭管道的读端（fd[0]），子进程关闭写端（fd[1]）。图15-4显示了在此之后描述符 的状态结果。

对于一个从子进程到父进程的管道，父进程关闭fd[1]，子进程关闭fd[0]。

当管道的一端被关闭后，下列两条规则起作用。

  1. 当读（read）一个写端已被关闭的管道时，在所有数据都被读取后，read返回 0，表示文件结束。（从技术上来讲，如果管道的写端还有进程，就不会产生文件的结束。可以复制一个管道的描述符，使得有多个进程对它具有写打开文件描述符。）
  2. 如果写（write）一个读端已被关闭的管道，则产生信号SIGPIPE。如果忽略该信号或者捕捉该信号并从其处理程序返回，则write返回−1，errno设置为EPIPE。 在写管道时，常量 PIPE_BUF 规定了内核的管道缓冲区大小。如果对管道调用write，而且要求写的字节数小于等于 PIPE_BUF，则此操作不会与其他进程对同一 管道（或FIFO）的 write 操作交叉进行。但是，若有多个进程同时写一个管道（或 FIFO），而且我们要求写的字节数超过PIPE_BUF，那么我们所写的数据可能会与其他进 程所写的数据相互交叉。用pathconf或fpathconf函数可以确定PIPE_BUF的 值。

消息队列

消息队列是消息的链接表，存储在内核中，由消息队列标识符标识。

msgget 用于创建一个新队列或打开一个现有队列。msgsnd 将新消息添加到队列尾端。每个消息包含一个正的长整型类型的字段、一个非负的长度以及实际数据字节数（对应于长度），所有这些都在将消息添加到队列时，传送给 msgsnd。msgrcv 用于从队列中取消息。我们并不一定要以先进先出次序取消息，也可以按消息的类型字段取消息。

msgget

#include <sys/msg.h>
int msgget(key_t key, int flag);
//返回值：若成功，返回消息队列ID；若出错，返回−1

msgsnd

#include <sys/msg.h>
int msgsnd(int msqid, const void *ptr, size_t nbytes, int flag);
//返回值：若成功，返回0；若出错，返回−1

ptr参数指向一个长整型数，它包含了正的整型消息类型，其后紧接着的是消息数据 （若nbytes是0，则无消息数据）。若发送的最长消息是512字节的，则可定义下列结构：

struct mymesg {
    long mtype;　　　 /* positive message type */
    char mtext[512]; /* message data, of length nbytes */ };
	//ptr就是一个指向mymesg结构的指针。接收者

msgrcv

msgrcv从队列中取用消息。

include <sys/msg.h>
ssize_t msgrcv(int msqid, void *ptr, size_t nbytes, long type, int flag);
//返回值：若成功，返回消息数据部分的长度；若出错，返回-1

共享内存

共享存储允许两个或多个进程共享一个给定的存储区。因为数据不需要在客户进程和服务器进程之间复制，所以这是最快的一种 IPC。使用共享存储时要掌握的唯一窍门是， 在多个进程之间同步访问一个给定的存储区。若服务器进程正在将数据放入共享存储区， 则在它做完这一操作之前，客户进程不应当去取这些数据。通常，信号量用于同步共享存储访问。

信号量

用了共享内存通信方式，带来新的问题，那就是如果多个进程同时修改同一个共享内存，很有可能就冲突了。例如两个进程都同时写一个地址，那先写的那个进程会发现内容被别人覆盖了。

为了防止多进程竞争共享资源，而造成的数据错乱，所以需要保护机制，使得共享的资源，在任意时刻只能被一个进程访问。正好，信号量就实现了这一保护机制。

信号量与已经介绍过的 IPC 机构（管道、FIFO 以及消息列队）不同。它是一个计数器，主要用于实现进程间的互斥与同步，而不是用于缓存进程间通信的数据。当进程不再使用由一个信号量控制的共享资源时，该信号量值增 1。如果有进程正在休眠等待此信号量，则唤醒它们。 为了正确地实现信号量，信号量值的测试及减1操作应当是原子操作。为此，信号量通常是在内核中实现的。

信号量表示资源的数量，控制信号量的方式有两种原子操作：

P 操作是用在进入共享资源之前，V 操作是用在离开共享资源之后，这两个操作是必须成对出现的。

信号

上面说的进程间通信，都是常规状态下的工作模式。对于异常情况下的工作模式，就需要用「信号」的方式来通知进程。

在 Linux 操作系统中， 为了响应各种各样的事件，提供了几十种信号，分别代表不同的意义。我们可以通过 kill -l 命令，查看所有的信号：

$ kill -l
 1) SIGHUP       2) SIGINT       3) SIGQUIT      4) SIGILL       5) SIGTRAP
 6) SIGABRT      7) SIGBUS       8) SIGFPE       9) SIGKILL     10) SIGUSR1
11) SIGSEGV     12) SIGUSR2     13) SIGPIPE     14) SIGALRM     15) SIGTERM
16) SIGSTKFLT   17) SIGCHLD     18) SIGCONT     19) SIGSTOP     20) SIGTSTP
21) SIGTTIN     22) SIGTTOU     23) SIGURG      24) SIGXCPU     25) SIGXFSZ
26) SIGVTALRM   27) SIGPROF     28) SIGWINCH    29) SIGIO       30) SIGPWR
31) SIGSYS      34) SIGRTMIN    35) SIGRTMIN+1  36) SIGRTMIN+2  37) SIGRTMIN+3
38) SIGRTMIN+4  39) SIGRTMIN+5  40) SIGRTMIN+6  41) SIGRTMIN+7  42) SIGRTMIN+8
43) SIGRTMIN+9  44) SIGRTMIN+10 45) SIGRTMIN+11 46) SIGRTMIN+12 47) SIGRTMIN+13
48) SIGRTMIN+14 49) SIGRTMIN+15 50) SIGRTMAX-14 51) SIGRTMAX-13 52) SIGRTMAX-12
53) SIGRTMAX-11 54) SIGRTMAX-10 55) SIGRTMAX-9  56) SIGRTMAX-8  57) SIGRTMAX-7
58) SIGRTMAX-6  59) SIGRTMAX-5  60) SIGRTMAX-4  61) SIGRTMAX-3  62) SIGRTMAX-2
63) SIGRTMAX-1  64) SIGRTMAX

运行在 shell 终端的进程，我们可以通过键盘输入某些组合键的时候，给进程发送信号。例如

如果进程在后台运行，可以通过 kill 命令的方式给进程发送信号，但前提需要知道运行中的进程 PID 号，例如：

所以，信号事件的来源主要有硬件来源（如键盘 Cltr+C ）和软件来源（如 kill 命令）。

信号是进程间通信机制中唯一的异步通信机制，因为可以在任何时候发送信号给某一进程，一旦有信号产生，我们就有下面这几种，用户进程对信号的处理方式。

1.执行默认操作。Linux 对每种信号都规定了默认操作，例如，上面列表中的 SIGTERM 信号，就是终止进程的意思。Core 的意思是 Core Dump，也即终止进程后，通过 Core Dump 将当前进程的运行状态保存在文件里面，方便程序员事后进行分析问题在哪里。

2.捕捉信号。我们可以为信号定义一个信号处理函数。当信号发生时，我们就执行相应的信号处理函数。

3.忽略信号。当我们不希望处理某些信号的时候，就可以忽略该信号，不做任何处理。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP，它们用于在任何时候中断或结束某一进程。

Socket

前面提到的管道、共享内存、信号量和信号都是在同一台主机上进行进程间通信，那要想跨网络与不同主机上的进程之间通信，就需要 Socket 通信了。实际上，Socket 通信不仅可以跨网络与不同主机的进程间通信，还可以在同主机上进程间通信。

我们来看看创建 socket 的系统调用：

int socket(int domain, int type, int protocal);
//domain 参数用来指定协议族，比如 AF_INET 用于 IPV4、AF_INET6 用于 IPV6、AF_LOCAL/AF_UNIX 用于本机；
//type 参数用来指定通信特性，比如 SOCK_STREAM 表示的是字节流，对应 TCP；SOCK_DGRAM 表示的是数据报，对应 UDP；SOCK_RAW 表示的是原始套接字；
//protocal 参数原本是用来指定通信协议的，但现在基本废弃。因为协议已经通过前面两个参数指定完成，protocol 目前一般写成 0 即可；

TCP

  1. 服务端和客户端初始化 socket，得到文件描述符；
  2. 服务端调用 bind，将绑定在 IP 地址和端口;
  3. 服务端调用 listen，进行监听；
  4. 服务端调用 accept，等待客户端连接（这里使用监听socket得到一个新的连接socket用于通信）；
  5. 客户端调用 connect，向服务器端的地址和端口发起连接请求；
  6. 服务端 accept 返回用于传输的 socket 的文件描述符；
  7. 客户端调用 write 写入数据；服务端调用 read 读取数据；
  8. 客户端断开连接时，会调用 close，那么服务端 read 读取数据的时候，就会读取到了 EOF，待处理完数据后，服务端调用 close，表示连接关闭。

UDP

UDP 是没有连接的，所以不需要三次握手，也就不需要像 TCP 调用 listen 和 connect，但是 UDP 的交互仍然需要 IP 地址和端口号，因此也需要 bind。每次通信时，调用 sendto 和 recvfrom，都要传入目标主机的 IP 地址和端口。

C++智能指针

网络

网络分层

网络为什么要分层？

网络分层指的是一个标准。任何计算机只要遵循这个标准，就能很方便的与其它计算机进行互联和交换数据。

五层协议的体系结构只是为了介绍网络原理而设计的，实际应用的还是 TCP/IP 四层体系结构。

OSI七层体系结构

OSI划分的七个层次由高到低依次为：Application(应用层)、Presentation(表示层)、Session(会话层)、Transport(传输层)、Network(网络层)、DataLink(数据链路层)和Physical(物理层)。其中应用层、表示层和会话层可以视为应用层，而剩余层则可视为数据流动层

应用层(Application)

与其它计算机进行通讯的一个应用，它是对应应用程序的通信服务的。是允许访问OSI环境的手段，传输单位为APDU，主要包括的协议为 TELNET，HTTP，FTP，NFS，SMTP等。

表示层(Presentation)

这一层的主要功能是定义数据格式及加密。对数据进行翻译、加密和压缩，传输单位为PPDU，主要包括的协议为JPEG ASII

会话层(Session)

它定义了如何开始、控制和结束一个会话，传输单位为SPDU，主要包括的协议为RPC NFS

传输层(Transport)

提供端到端的可靠报文传递和错误恢复，传输单位为报文，主要包括的协议为TCP UDP

网络层(Network)

负责数据包从源到宿的传递和网际互连，传输单位为包，主要包括的协议为IP ARP ICMP

数据链路层(Data Link)

它定义了在单个链路上如何传输数据。将比特组装成帧和点到点的传递，传输单位为帧，主要包括的协议为MAC VLAN PPP

物理层(Physical)

物理层: 通过媒介传输比特,确定机械及电气规范，传输单位为bit，主要包括的协议为：IEE802.3 CLOCK RJ45

TCP/IP四层体系结构

TCP/IP是一组用于实现网络互连的通信协议。Internet网络体系结构以TCP/IP为核心。基于TCP/IP的参考模型将协议分成四个层次，它们分别是：网络访问层、网际互联层（主机到主机）、传输层、和应用层。

应用层

应用层对应于OSI参考模型的最高层，为用户提供所需要的各种服务，例如：FTP、Telnet、DNS、SMTP等.

传输层

传输层对应于OSI参考模型的传输层，为应用层实体提供端到端的通信功能，保证了数据包的顺序传送及数据的完整性。该层定义了两个主要的协议：传输控制协议（TCP）和用户数据报协议（UDP).

TCP协议提供的是一种可靠的、通过“三次握手”来连接的数据传输服务；而UDP协议提供的则是不保证可靠的（并不是不可靠）、无连接的数据传输服务.

网际互联层

网际互联层对应于OSI参考模型的网络层，主要解决主机到主机的通信问题。它所包含的协议设计数据包在整个网络上的逻辑传输。注重重新赋予主机一个IP地址来完成对主机的寻址，它还负责数据包在多种网络中的路由。该层有三个主要协议：网际协议（IP）、互联网组管理协议（IGMP）和互联网控制报文协议（ICMP）。

IP协议是网际互联层最重要的协议，它提供的是一个可靠、无连接的数据报传递服务。

网络接入层（即主机-网络层）

网络接入层与OSI参考模型中的物理层和数据链路层相对应。它负责监视数据在主机和网络之间的交换。事实上，TCP/IP本身并未定义该层的协议，而由参与互连的各网络使用自己的物理层和数据链路层协议，然后与TCP/IP的网络接入层进行连接。地址解析协议（ARP）工作在此层，即OSI参考模型的数据链路层。

网络协议

ARP

地址解析协议，即ARP（Address Resolution Protocol）。是根据IP地址获取物理地址的一个TCP/IP协议。位于网络层。

ARP协议位于哪一层？

位于网络层。

IP地址在OSI模型的第三层，MAC地址在第二层，彼此不直接打交道。在通过以太网发送IP数据包时，需要先封装第三层（32位IP地址）、第二层（48位MAC地址）的报头，但由于发送时只知道目标IP地址，不知道其MAC地址，又不能跨第二、三层，所以需要使用地址解析协议。使用地址解析协议，可根据网络层IP数据包包头中的IP地址信息解析出目标硬件地址（MAC地址）信息，以保证通信的顺利进行。

主机发送信息时将包含目标IP地址的ARP请求广播到局域网络上的所有主机，并接收返回消息，以此确定目标的物理地址；收到返回消息后将该IP地址和物理地址存入本机ARP缓存中并保留一定时间，下次请求时直接查询ARP缓存以节约资源。

地址解析协议是建立在网络中各个主机互相信任的基础上的，局域网络上的主机可以自主发送ARP应答消息，其他主机收到应答报文时不会检测该报文的真实性就会将其记入本机ARP缓存；由此攻击者就可以向某一主机发送伪ARP应答报文，使其发送的信息无法到达预期的主机或到达错误的主机，这就构成了一个ARP欺骗。

报文格式

工作过程

  1. 主机A想和主机B通信，就先在主机A的ARP高速缓冲中，查看有无主机B的IP地址。如果有，就查出主机B对应的MAC地址。如果没有，主机A会发送一个ARP请求广播包，此包内包含着主机B的IP地址（除目的端硬件地址外的所有其他的字段都有填充值）。本局域网上的所有主机都将收到这个ARP请求。
  2. 除了主机B，其余主机都不理睬这个ARP请求。主机B在ARP请求分组中看到自己的IP地址，它就把自己的硬件地址填进去，然后用两个目的端地址分别替换两个发送端地址，并把操作字段置为 2，最后就向主机A发送回去。同时为了提高效率，主机B还把主机A的IP地址和MAC地址的映射关系保存到自己的高速缓存中。
  3. 主机A收到主机B的ARP响应后，就在其ARP高速缓存中写入主机B的IP地址到硬件地址的映射。这样，主机A、B都有了彼此的IP和硬件地址，双方可以通信了！

缺陷

IP

IP是Internet Protocol（网际互连协议）的缩写，是TCP/IP体系中的网络层协议。

IP 协议为上层协议提供无状态、无连接、不可靠的服务。

无状态是指IP通信双方不同步传输数据的状态信息，因此所有的IP数据报的发送、传输和接收都是相互独立、没有上下文关系的。这种服务的最大缺点是无法处理乱序和重复的IP数据报。接收端的IP模块只要收到了完整的IP数据报（如果是分片，IP模块将先执行重组），就将其数据部分（TCP报文段或UDP数据段或ICMP报文）上交给上层协议。那么从上层协议来看，这些数据就可能是乱序的、重复的。无状态服务的优点也很明显：简单、高效。我们无须为保持通信的状态而分配一些内核资源，也无须每次传输数据时都携带状态信息。

无连接是指IP通信双方都不长久地维持对方地任何信息。这样，上层协议每次发送数据地时候，都必须明确指定对方地IP地址。

不可靠是指IP协议不能保证IP数据报准确地到达接收端，它只是承诺尽最大努力。有很多情况都能导致IP数据报发送失败，但无论哪种情况，发送端地IP模块一旦检测到IP数据报发送失败，就通知上层协议发送失败，而不会试图重传。因此，使用IP服务的上层协议（比如TCP协议）需要自己实现数据确认、超时重传等机制以达到可靠传输的目的。

IPv4报文格式

ICMP

ICMP（Internet Control Message Protocol）Internet控制报文协议。ICMP经常被认为是 IP层的一个组成部分（位于网络层）。用于在IP主机、路由器之间传递控制消息。控制消息是指网络通不通、主机是否可达、路由是否可用等网络本身的消息。这些控制消息虽然并不传输用户数据，但是对于用户数据的传递起着重要的作用。

报文格式

ICMP类型

已经定义的ICMP消息类型大约有10多种，每种ICMP数据类型都被封装在一个IP数据包中。主要的ICMP消息类型包括以下几种。

         
TYPE CODE Description Query Error
0 0 Echo Reply——回显应答（Ping应答） x  
3 0 Network Unreachable——网络不可达   x
3 1 Host Unreachable——主机不可达   x
3 2 Protocol Unreachable——协议不可达   x
3 3 Port Unreachable——端口不可达   x
3 4 Fragmentation needed but no frag. bit set——需要进行分片但设置不分片比特   x
3 5 Source routing failed——源站选路失败   x
3 6 Destination network unknown——目的网络未知   x
3 7 Destination host unknown——目的主机未知   x
3 8 Source host isolated (obsolete)——源主机被隔离（作废不用）   x
3 9 Destination network administratively prohibited——目的网络被强制禁止   x
3 10 Destination host administratively prohibited——目的主机被强制禁止   x
3 11 Network unreachable for TOS——由于服务类型TOS，网络不可达   x
3 12 Host unreachable for TOS——由于服务类型TOS，主机不可达   x
3 13 Communication administratively prohibited by filtering——由于过滤，通信被强制禁止   x
3 14 Host precedence violation——主机越权   x
3 15 Precedence cutoff in effect——优先中止生效   x
4 0 Source quench——源端被关闭（基本流控制）    
5 0 Redirect for network——对网络重定向    
5 1 Redirect for host——对主机重定向    
5 2 Redirect for TOS and network——对服务类型和网络重定向    
5 3 Redirect for TOS and host——对服务类型和主机重定向    
8 0 Echo request——回显请求（Ping请求） x  
9 0 Router advertisement——路由器通告    
10 0 Route solicitation——路由器请求    
11 0 TTL equals 0 during transit——传输期间生存时间为0   x
11 1 TTL equals 0 during reassembly——在数据报组装期间生存时间为0   x
12 0 IP header bad (catchall error)——坏的IP首部（包括各种差错）   x
12 1 Required options missing——缺少必需的选项   x
13 0 Timestamp request (obsolete)——时间戳请求（作废不用） x  
14   Timestamp reply (obsolete)——时间戳应答（作废不用） x  
15 0 Information request (obsolete)——信息请求（作废不用） x  
16 0 Information reply (obsolete)——信息应答（作废不用） x  
17 0 Address mask request——地址掩码请求 x  
18 0 Address mask reply——地址掩码应答    

TCP

传输控制协议（TCP，Transmission Control Protocol）是一种面向连接的、可靠的、基于字节流的传输层通信协议。

TCP为应用层提供全双工服务。这意味数据能在两个方向上独立地进行传输。因此，连接的每一端必须保持每个方向上的传输数据序号。

TCP协议的这种连接是一对一的，所以基于广播和多播（目标是多个主机地址）的应用程序不能使用TCP服务。而无连接协议UDP则非常适合于广播和多播。

报文格式

定时器

对每个连接，TCP管理4个不同的定时器。

  1. 重传定时器。使用于当希望收到另一端的确认。在本章我们将详细讨论这个定时器以及一些相关的问题，如拥塞避免。
  2. 坚持( persist )定时器。使窗口大小信息保持不断流动，即使另一端关闭了其接收窗口。
  3. 保活( keepalive )定时器。可检测到一个空闲连接的另一端何时崩溃或重启。
  4. 2MSL定时器。测量一个连接处于 TIME_WAIT状态的时间。

UDP

用户数据报协议（UDP，User Datagram Protocol）是一个无连接的传输协议。UDP 为应用程序提供了一种无需建立连接就可以发送封装的 IP 数据包的方法。RFC 768 描述了 UDP。

报文格式

HTTP

报文结构

HTTP协议的请求和响应报文中必定包含HTTP首部。首部内容为客户端和服务器分别处理请求和响应提供所需要的信息。

请求报文

在请求中，HTTP报文首部由方法、URI、HTTP版本、HTTP首部字段构成。

响应报文

在响应中，HTTP报文首部由HTTP版本、状态码、HTTP首部字段这3部分构成。

在HTTP报文众多的字段中，HTTP首部字段包含的信息最为丰富。首部字段同时存在于请求和响应报文中。首部字段可支持的字段内容因HTTP版本的不同而不同。

4种HTTP首部字段类型

HTTP1.0

HTTP是一个简单的请求-响应协议，它通常运行在TCP之上。它指定了客户端可能发送给服务器什么样的消息以及得到什么样的响应。请求和响应消息的头以ASCII码形式给出；而消息内容则具有一个类似MIME的格式。

主要特征

C/S工作模式

在HTTP协议中, 作为客户的WWW浏览器与作为提供WWW网页数据服务的服务器之间传递请求, 应答数据。一个服务器可接受和处理世界范围内多个客户浏览器的同时访问, 一个浏览器同样也可访问世界范围内的WWW服务器。

无连接

HTTP使用了面向连接的TCP作为传输层协议，保证了数据的可靠传输，使得HTTP不必考虑数据在传输过程中被丢弃后应该怎么重传。但是HTTP本身是无连接的协议，通信双方在交换HTTP报文之前无需先建立HTTP连接。

这种方式的优点是对HTTP服务器一方来说实现起来简单, 避免服务器由于保持和维护过多的TCP连接而浪费服务器资源。

无状态

服务器向客户发送被请求的文件，而不存储任何关于该客户的状态信息。 假如某个特定的客户在短短的几秒钟内两次请求同一个对象，服务器并不会因为刚刚为该客户提供了该对象就不再做出反应，而是重新发送该对象，就像服务器已经完全忘记不久之前所 做过的事一样。 因为 HTTP 服务器并不保存关于客户的任何信息，所以我们说 HTTP 是一个无状态协议 (stateless protocol) 。

这样做的优点是HTTP服务器实现起来比较简单、程序规模小, 大大加快了服务器响应速度, 对于早期WWW注重于信息发布的情况是比较合适的。

传输数据灵活

虽然被称为超文本传输协议, HTTP实际上允许传输任意类型的数据对象, 这功归于请求信息与响应信息中都具有的消息首部 (message-header) 。信息首部的内容就是关于被传递的数据的信息。

易于扩充

作为一个公开发布使用协议, HTTP具有良好的可扩充性, 如前述, 它传输的已不仅仅是超文本数据。在此基础上针对应用开发者的研究、开发要求, 可以很容易地增加请求方法和响应状态, 运行于用户定制的系统之中。经过扩充的服务器, 能够响应原有标准的浏览器, 也能够区别出用户自己开发的专用客户程序, 作出相应的响应处理。

存在的问题

HTTP原本定位在规模不是太大的分布式超媒体信息系统上的, 它的设计目标很大程度上是出于寻找能解决问题的、简单实用的方案, 而非建立一个精致、完美的协议。况且设计者当时也并未考虑到日后WWW会发展得如此庞大以至于国际互联网络日益拥挤。HTTP0.9、HTTP1.0则是在原有基础上进行一些修补, 其基本的无连接性、无状态性都未改变。

但是, 随着网络应用的发展, 以及网络带宽的日益拥挤, HTTP1.0的缺陷也随之体现出来。HTTP的无状态性使得客户与服务器交互的许多历史数据不能保留, 缺少历史状态数据意味着如果后续处理需要前面的信息, 则它必须重传, 这样可能会导致每次连接传送的数据量增大, 从而造成浪费。HTTP1.0也没有完善地考虑多级传送代理、缓存机制。这可以概括为两个方面:

①HTTP协议对事务处理、网络贸易、网络安全的支持不足;

②HTTP协议的运作机制加剧网络传输带宽的不足。

报文结构

请求报文：客户端向服务器发送请求报文。

响应报文：服务器回应客户端的报文。

由于HTTP是面向文本(text-oriented)，因此在报文中的每一个字段都是一些ASCII码串，因而各个字段的长度都是不确定的。

HTTP报文分为请求报文和响应报文，它们都分为3个部分：开始行、首部行和实体主体。它们的区别就是开始行，请求报文的开始行叫做请求行，由请求方法、请求资源的URL、HTTP版本组成；响应报文的开始行叫做状态行，由HTTP版本、状态码和短语组成。

请求方法

序号 方法 描述
1 get 请求指定的页面信息并返回实体主体
2 head 类似get，不过返回的响应无内容，用于获取报头
3 post 向指定资源提交数据（如提交表单或上传文件）
4 put 从客户端向服务器传送的数据取代指定的文档的内容
5 delete 请求服务器删除指定的页面
6 connect HTTP/1.1 协议中预留给能够将连接改为管道方式的代理服务器
7 options 允许客户端查看服务器的性能
8 trace 回显服务器收到的请求，主要用于测试或诊断
9 patch 是对 PUT 方法的补充，用来对已知资源进行局部更新

状态码

状态码 类别 原因短语
1XX Informational（信息性状态码） 接收的请求正在处理
2XX Success（成功状态码） 请求正常处理完毕
3XX Redirection（重定向状态码） 需要进行附加操作以完成请求
4XX Client Error（客户端错误状态码） 服务器无法处理请求
5XX Server Error（服务器错误状态码） 服务器处理请求出错
HTTP1.1

针对HTTP1.0及其以前版本存在的问题, HTTP1.1作了较大的改进工作, 它的扩充主要集中在以下几个方面:

长连接

HTTP 1.1支持长连接（PersistentConnection）和请求的流水线（Pipelining）处理，在一个TCP连接上可以传送多个HTTP请求和响应，减少了建立和关闭连接的消耗和延迟，在HTTP1.1中默认开启Connection： keep-alive，一定程度上弥补了HTTP1.0每次请求都要创建连接的缺点。

新增加了请求方式

  1. OPTIONS

    OPTIONS操作用以请求与Request-URI所标识的HTTP请求/应答链接的信息。浏览器使用该操作可以在不对资源实体进行操作或传递实体的情况下获得对某一个实体的操作要求、功能选项或服务的能力。

  2. PUT

    PUT操作请求把携带的资源存放于Request-URI指向的位置, 如果已有资源存在, 则PUT消息的实体将作为原资源的更新版本, 如不存在, 则生成新的URI资源。

  3. DELETE

    DELETE操作请求WWW服务器删除由Request-URI指向的资源。

  4. TRACE

    TRACE操作用以探察请求路径, 即HTTP请求经历了哪些中间传输代理, 返回报文由最后一个接收者送回。

身份认证

HTTP1.0提出一种简单的“提问-回答”式的基本访问授权方法 (Basic Authentication Scheme) 。该方案的过程是：先由服务器向客户发出身份鉴别请求, 再由客户发出确认信息。这种用户口令验证过程最为致命的危险在于, 窃听者可以通过物理网络介质或路由设备、中继设备, 获取用户名及用户口令明文, 为此, HTTP1.1提供了一种基于MD5算法的身份鉴别方案DAA (Digest Access Authentication) [RFC2069], 在传输层加密或封装消息包。下面将描述DAA的运作方法。

当客户方第一次申请资源时，若未提供合适的DAA认证，服务器将在响应中指明一个特有值nonce，DAA建议这个特有值是H (clientIP“:”time-stamp“:”private-key) 。

其中：clientIP是失败请求者的IP地址；time-stamp是服务器时间；private-key则是服务器资源的特有值, 此值只为该服务器知道；H表示对值进行加密变换，其中缺省加密算法为MD5。众所周知，MD5的解密时间为天文数字，因而即使知道密文格式也无法有效求出内容。

客户方在收到该特有值后，用它产生一个响应串，放在随后的请求之中，响应串应形如：

H(H(A1)“:”nonce“:”H(A2))

其中：A1为username“:”realm-value“:”password

A2为method“:”URI-value

realm用于提示用户应该使用哪一个范围的用户名, 其形式应该是:用户类名@服务器名。

这样传送出去的请求将不再包括显式的密码, 而是把加密后的编码传送给服务器。服务器再次收到请求时, 请求中取出usernamerealm, nonce, url再查找该用户的正确密码, 用同样的公式计算出密码值response, 与请求中的response相比, 若完全相同就表明身份已经证实有效。

由于在nonce中加入了时间, 故而不同时间段中的nonce不同, 中间的偷听者即使原封不动地把response照抄下来供下一次使用, 也会因时间已过期而不能得逞。

DAA有着一定的缺陷，它对于传送内容不加密, 这就无法保证用户信息的私有性, 如在电子商务中, 信用卡和号是敏感信息，不应明文传送，对于这样的要求DAA就无能为力了，但它总强于基本认证方式。

内容协商

当服务器能够对客户的请求提供多种表示形式应答时, 需要使用内容协商机制, 使Web服务器可以从中挑选出能满足用户要求的具有最适合表达形式的资源实体。因为很多时候源服务器或提供缓存的中间服务器并不会有一个统一的最佳资源形式标准, 而用户端浏览器也不一定有能力处理所有的实体类型。为此, HTTP1.1规定任何包含信息实体的应答形式都是可协商的, 包括出错信息。内容协商机制有三种类型, 分别为服务器驱动 (server-driven) 、用户代理驱动 (agent-driven) 与透明驱动 (transparent driven) , 这几类协商互不影响, 可独立或结合使用。

缓存机制

缓存机制提供的功能如下:将先前的客户请求以及请求所对应的Web服务器响应的内容暂时保存在机器的内存或物理存储器中, 使得在处理新的客户请求时可以利用。如果新的客户请求与所保存的某个客户请求相同, 则缓存机制可提供已保存的该请求所对应的Web服务器的响应, 无需再访问Request-URI所标识的源服务器, 这样就可以减轻源服务器的响应负担以及网络拥塞。

状态控制

目前HTTP协议中是没有状态性的, HTTP服务器仅仅根据当前申请决定响应而不关心以前的查询, 服务器也不企图在以后的请求中得到更进一步信息。但是在电子商务等实际应用中, 将会用到历史信息来决定进一步的响应, 比如, 用户在选购的过程中会一件件积聚要购买的物品, 当最后付款时, 需要给出一个物品列表, 这个物品列表就是已有动作的状态记录。由此可见, 在现在HTTP基础上, 还必须提供描述一个状态系列变迁的手段, 在RFC2109中给出了这样一个标准。

RFC2109把状态的变化定义为一个会话 ,一个会话由一系列相关联的请求和响应组成 , 一个会话应具有四个特征: 每个会话都应有起始和结束;每个会话应尽量只存在于一个较短的 时间内;客户方和服务器都可以主动地结束一个会话;一个会话的标识应含于一系列的状态信 息中。 为了定义一个会话 ,新产生了两种头部: cookie和 set- cookie,其中 set- cookie包含于服 务器响应中, cookie含在客户请求中,会话由服务器提议建立。请注意 ,一个会话并不是一个连续不 间隔的客户方到服务器的连接,在会话期间 ,双方仍然采用 HT TP的一问一答方式 ,需要每次建立 连接。对于一个未包含会话的普通请求,服务器可以给出一个包含 set- cookie的响应。客户在收 到 set- cookie之后 ,可以通过响应 cookie建立会话,或者简单忽略 set- cookie而拒绝建立会话; 服务器也可以对 cookie响应以更新的状态 set- cookie或者把 set- cookiemax- Age域改为 0, 从而结束一个会话 ,双方就是用这样自愿的方式建立和维持一个会话。

HTTP2.0

HTTP/2（超文本传输协议第2版，最初命名为HTTP 2.0），是HTTP协议自1999年HTTP 1.1发布后的首个更新，主要基于SPDY协议。HTTP/2标准于2015年5月以RFC 7540正式发表。

HTTP2.0的目标主要是改善用户在使用Web时的速度体验。

HTTP1.x有以下几个主要缺点：

我们可以通过一个链接来对比一下HTTP2.0到底比HTTP1.x快了多少。对比链接

HTTP2.0的改进

HTTPS

HTTPS就是使用TLS/SSL的HTTP通信。Web中可以通过TLS/SSL（Transport Layer Security/Secure Sockets Layer。由网景公司最早提出的名称叫SSL，标准化以后被称作TLS。有时两者统称为SSL） 对HTTP通信进行加密。

HTTPS中采用对称加密方式。而在发送其公共密钥时采用的则是公钥加密方式：

确认公钥是否正确主要使用认证中心（CA（Certificate Authority））签发的证书，而主要的认证中心的信息已经嵌入到浏览器的出厂设置中。如果Web浏览器中尚未加入某个认证中心，那么会在页面上提示一个警告信息。此时，判断认证中心合法与否就要由用户自己决定了。

数字签名流程

不管是 RSA 数字签名算法还是 DSA 数字签名算法，数字签名处理流程是差不多的，主要分为签名生成和签名验证，接下来分别描述这两个过程。

签名生成流程如图 2-17 所示。

  • 发送者对消息计算摘要值 。
  • 发送者用私钥对摘要值进行签名得到签名值。
  • 发送者将原始消息和签名值一 同发给接收者。

数字签名技术的本质不是为了加密，所以和签名值一同传递的消息是不用加密的，当 然也可以对消息加密后再计算签名值。

签名验证流程如图 2-18 所示。

  • 接收者接收到消息后，拆分出消息和消息签名值 A。
  • 接收者使用公钥对消息进行运算得到摘要值 B。
  • 接收者对摘要值 B 和签名值 A 进行比较，如果相同表示签名验证成功， 否则就是验证失败 。

签名生成和签名验证流程很简单，思考一个问题，为什么不直接对消息进行签名，而是对消息的摘要值进行签名？签名值除了比较之外并没有其他用途，那么基于消息生成签名和基于消息摘要值生成签名并无区别，考虑到公开密钥算法运行是相对缓慢的，数字签名算法建议对消息摘要值进行签名，因为摘要值的长度是固定的，运算的时候速度会比较快。

FTP

文件传输协议（File Transfer Protocol，FTP）是用于在网络上进行文件传输的一套标准协议，它工作在 OSI 模型的第七层， TCP 模型的第四层， 即应用层， 使用 TCP 传输而不是 UDP， 客户在和服务器建立连接前要经过一个“三次握手”的过程， 保证客户与服务器之间的连接是可靠的， 而且是面向连接， 为数据传输提供可靠保证。

FTP允许用户以文件操作的方式（如文件的增、删、改、查、传送等）与另一主机相互通信。然而， 用户并不真正登录到自己想要存取的计算机上面而成为完全用户， 可用FTP程序访问远程资源， 实现用户往返传输文件、目录管理以及访问电子邮件等等， 即使双方计算机可能配有不同的操作系统和文件存储方式。

FTP和HTTP都是文件传输协议，有很多的共同点，比如，它们都运行在TCP协议之上。但FTP使用了两个并行的TCP连接来控制和传输文件。其中一个是控制连接，一个是数据连接。当客户端向服务器发出建立FTP连接请求时，要连接服务器端的熟知端口21端口，同时还要告诉服务端自己的另一个端口号码，用于建立数据连接。接着，服务端用自己传送数据的熟知端口20端口（出于安全的考虑，普遍在数据传输用的端口号中使用随机数进行分配）与客户端提供的端口号建立数据连接。

数据连接一旦数据传输完毕就会立即关闭。即使在同一个会话期间，用户还需要传输另一个文件，FTP会打开另一个数据连接。总之，控制连接贯穿了整个用户会话期间，但数据连接则是非持续性的，每一次文件传输都需要建立一个新的数据连接。

控制用的连接，在用户要求断开之前会一直保持连接状态。不过，绝大多数FTP服务器都会对长时间没有任何新命令输入的用户的连接强制断开（在文件传输过程中不会断开连接，而是在文件已经传输完成以后，一段时间没有任何其他命令输入，则断开连接。） 。

不足

FTP 服务器必须在整个会话期间保留用户的状态( state) 。 特别是，服务器必须把特定的用户账户与控制连接联系起来，随着用户在远程目录树上徘徊，服务器必须追踪用户在远程目录树上的当前位置。对每个进行中的用户会话的状态信息进行追踪，大大限制了 FTP 同时维持的会话总数。 而 HTTP 是无状态的，即它不必对任何用户状态进行追踪。

FTP 命令和回答

从客户到服务器的命令和从服务器到客户的回答，都是以 7 比特 ASCII 格式在控制连接上传送的。 因此，与 HTTP 协议的命令类似， FTP 协议的命令也是人可读的。 为了区分连续的命令，每个命令后跟回车换行符。 每个命令由 4 个大写字母 ASCII 字符组成，有些还具有可选参数。一些较为常见的命令如下:

每个命令都对应着一个从服务器发向客户的回答。 回答是一个 3 位的数字，后跟一个可选信息。 这与 HTTP 响应报文状态行的状态码和状态信息的结构相同。 一些典型的回答连同它们可能的报文如下所示:

DNS

域名系统（Domain Name System 缩写 DNS，Domain Name被译为域名）是因特网的一项核心服务，它作为可以将域名和IP地址相互映射的一个分布式数据库，能够使人更方便的访问互联网，而不用去记住能够被机器直接读取的IP数串。

优点

DNS记录

共同实现 DNS 分布式数据库的所有 DNS 服务器存储了资源记录 (Resource Record , RR) , RR 提供了主机名到 IP 地址的映射。 每个 DNS 回答报文包含了一条或多条资源记录。

资源记录是一个包含了下列字段的 4 元组：

(Name, Value , Type , TTL)

TTL 是该记录的生存时间，它决定了资源记录应当从缓存中删除的时间。 在下面给出的记录例子中，我们忽略掉 TTL 字段。Name 和 Value 的值取决于 Type：

DNS的主要记录如下表：

DNS报文

DNS定义了一个用于查询和响应的报文格式。图 14-3显示这个报文的总体格式。

报文由12字节的首部和4个长度可变的字段组成。

DNS查询

用UDP还是TCP

注意到DNS名字服务器使用的熟知端口号无论对UDP还是TCP都是53。这意味着DNS均支持UDP和TCP访问。那么这两种协议都在什么情况下采用以及采用的理由都是什么呢？

当名字解析器发出一个查询请求，并且返回响应中的 TC（删减标志）比特被设置为1时，它就意味着响应的长度超过了512个字节，而仅返回前512个字节。在遇到这种情况时，名字解析器通常使用TCP重发原来的查询请求，它将允许返回的响应超过512个字节。既然TCP能将用户的数据流分为一些报文段，它就能用多个报文段来传送任意长度的用户数据。

此外，当一个域的辅助名字服务器在启动时，将从该域的主名字服务器执行区域传送。辅助服务器将定时（通常是3小时）向主服务器进行查询以便了解主服务器数据是否发生变动。如果有变动，将执行一次区域传送。区域传送将使用 TCP，因为这里传送的数据远比一个查询或响应多得多。既然DNS主要使用UDP，无论是名字解析器还是名字服务器都必须自己处理超时和重传。

此外，不像其他的使用 UDP的Internet应用（TFTP、BOOTP和SNMP），大部分操作集中在局域网上，DNS查询和响应通常经过广域网。分组丢失率和往返时间的不确定性在广域网上比局域网上更大。这样对于DNS客户程序，一个好的重传和超时程序就显得更重要了。

操作系统

1. 进程

进程是计算机中已运行程序的实体。程序本身只是指令的集合，进程才是程序(那些指令)的真正运行。但是进程本身不会运行，进程只是是线程的容器。若干进程有可能与同一个程序相关联，且每个进程皆可以同步(循序)或不同步(平行)的方式独立运行。进程为现今分时系统的基本运作单位。

线程是操作系统运行调度的最小单位。它被包涵在进程之中，一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程可以并行执行不同的任务。同一进程中的多条线程将共享该进程中的全部系统资源，如虚拟地址空间，文件描述符和信号处理等等。但同一进程中的多个线程有各自的调用栈(call stack)，自己的寄存器环境(register context)，自己的线程本地存储(thread-local storage)。

进程是资源分配的最小单位，线程是CPU调度的最小单位。线程和进程的区别在于，子进程和父进程有不同的代码和数据空间，而多个线程则共享数据空间，每个线程有自己的执行堆栈和程序计数器为其执行上下文。

定义

进程是对运行时程序的封装，是系统进行资源调度和分配的的基本单位，实现了操作系统的并发；

狭义定义：进程是正在运行的程序的实例（an instance of a computer program that is being executed），由进程控制块、程序段、数据段三部分组成。

广义定义：进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。它是操作系统动态执行的基本单元。

特征

动态性：进程的实质是程序在多道程序系统中的一次执行过程，进程是动态产生，动态消亡的。

并发性：任何进程都可以同其他进程一起并发执行

独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位；

异步性：由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进

结构特征：进程由程序、数据和进程控制块三部分组成。

多个不同的进程可以包含相同的程序：一个程序在不同的数据集里就构成不同的进程，能得到不同的结果；但是执行过程中，程序不能发生改变。

状态

进程执行时的间断性，决定了进程可能具有多种状态。事实上，运行中的进程可能具有以下三种基本状态。

1）就绪状态(Ready)

进程已获得除处理器外的所需资源，等待分配处理器资源；只要分配了处理器进程就可执行。就绪进程可以按多个优先级来划分队列。例如，当一个进程由于时间片用完而进入就绪状态时，排入低优先级队列；当进程由I/O操作完成而进入就绪状态时，排入高优先级队列。

2）运行状态(Running)：

进程占用处理器资源；处于此状态的进程的数目小于等于处理器的数目。在没有其他进程可以执行时(如所有进程都在阻塞状态)，通常会自动执行系统的空闲进程。

3）阻塞状态(Blocked)：

由于进程等待某种条件（如I/O操作或进程同步），在条件满足之前无法继续执行。该事件发生前即使把处理器资源分配给该进程，也无法运行。

调度算法

进程的调度算法包括：

实时系统中：FIFO(First Input First Output，先进先出算法)，SJF(Shortest Job First，最短作业优先算法)，SRTF(Shortest Remaining Time First，最短剩余时间优先算法）。

交互式系统中：RR(Round Robin，时间片轮转算法)，HPF(Highest Priority First，最高优先级算法)，多级队列，最短进程优先，保证调度，彩票调度，公平分享调度。

2. 线程(Thread)

线程是进程的子任务，是CPU调度和分派的基本单位，用于保证程序的实时性，实现进程内部的并发。

概念

线程是进程中执行运算的最小单位，是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只拥有一点在运行中必不可少的资源，但它可与同属一个进程的其它线程共享进程所拥有的全部资源。一个线程可以创建和撤消另一个线程，同一进程中的多个线程之间可以并发执行。

特点

在多线程OS中，通常是在一个进程中包括多个线程，每个线程都是作为利用CPU的基本单位，是花费最小开销的实体。线程具有以下属性。

1）轻型实体

线程中的实体基本上不拥有系统资源，只是有一点必不可少的、能保证独立运行的资源。

线程的实体包括程序、数据和TCB。线程是动态概念，它的动态特性由线程控制块TCB（Thread Control Block）描述。TCB包括以下信息：

（1）线程状态。

（2）当线程不运行时，被保存的现场资源。

（3）一组执行堆栈。

（4）存放每个线程的局部变量主存区。

（5）访问同一个进程中的主存和其它资源。

用于指示被执行指令序列的程序计数器、保留局部变量、少数状态参数和返回地址等的一组寄存器和堆栈。

2）独立调度和分派的基本单位。

在多线程OS中，线程是能独立运行的基本单位，因而也是独立调度和分派的基本单位。由于线程很“轻”，故线程的切换非常迅速且开销小（在同一进程中的）。

3）可并发执行。

在一个进程中的多个线程之间，可以并发执行，甚至允许在一个进程中所有线程都能并发执行；同样，不同进程中的线程也能并发执行，充分利用和发挥了处理机与外围设备并行工作的能力。

4）共享进程资源。

在同一进程中的各个线程，都可以共享该进程所拥有的资源，这首先表现在：所有线程都具有相同的地址空间（进程的地址空间），这意味着，线程可以访问该地址空间的每一个虚地址；此外，还可以访问进程所拥有的已打开文件、定时器、信号量机构等。由于同一个进程内的线程共享内存和文件，所以线程之间互相通信不必调用内核。

状态变化

（1）创建线程

当创建一个新的进程时，也创建一个新的线程，进程中的线程可以在同一进程中创建新的线程。

（2）终止线程

可以正常终止自己，也可能某个线程执行错误，由其它线程强行终止。终止线程操作主要负责释放线程占有的寄存器和栈

（3）阻塞线程

当线程等待每个事件无法运行时，停止其运行。

（4）唤醒线程

当阻塞线程的事件发生时，将被阻塞的线程状态置为就绪态，将其挂到就绪队列。进程仍然具有与执行相关的状态。例如，所谓进程处于“执行”状态，实际上是指该进程中的某线程正在执行。对进程施加的与进程状态有关的操作，也对其线程起作用。例如，把某个进程挂起时，该进程中的所有线程也都被挂起，激活也是同样。

3. 死锁

4. 虚拟化

5. 内存管理

内存的基本概念

内存

内存管理的基本概念

内存管理的概念

连续分配内存管理

连续分配管理

非连续分配内存管理

内存空间的扩充

地址转换

基本地址转换

基本地址变换机构

具有快表的地址转换

具有快表的地址变换机构

页表机制

两级页表

两级页表

页面分配策略

页面分配策略

6. 一个程序从编写到运行经过的过程

编译：由编译程序将用户源代码编译成若干个目标模块（编译就是把高级语言翻译为机器语言）。

链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块。

链接又分为三种方式：

  1. 静态链接：在程序运行之前，先将各目标模块及他们所需库函数链接成一个完整的可执行文件（装入模块），之后就不再拆开。
  2. 装入时动态链接：将各目模块装入内存时，边装入边链接。
  3. 运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。

装入：又称装载，由装入程序将装入模块装入内存运行。

项目

为什么用多线程

多线程在CPU密集型的作业下的确不能提高性能甚至会降低性能，但是在IO密集型的作业下则可以提升性能（或者更准确点说叫平均响应时间）。

但线程数量不能太多，如果线程数量远远大于CPU核心数量，那么就会导致频繁的线程切换，降低性能。

为什么使用线程池

如果每个请求对应一个线程（thread-per-request），那么就会导致服务器在创建和销毁线程上花费的时间和消耗的系统资源要比花在处理实际的用户请求的时间和资源更多。活动的线程也消耗系统资源，他们会消耗大量的内存空间，导致系统的内存空间不足，影响服务器的使用。

如果线程的数目固定，并且每个线程都有很长的生命周期，那么线程切换的消耗就很小了，这样就会给服务器减轻很多压力。

进程与

1. 单进程+单线程：运行一个单线程的进程

编码简单，但是无法发挥多核计算机的计算能力。

2. 单进程+多线程：运行一个多线程的进程

编码复杂。并且与模式3相比没有什么优势。

3. 多进程+单线程：运行多个单线程的进程

分为两种子模式：

  1. 简单地将模式1中的进程运行多份
  2. 主进程+worker进程

4. 多进程+多线程：运行多个多线程的进程

不但没有集合模式2和3的优点，反而集合了模式2和3的缺点。

必须使用单线程的场合

  1. 程序可能会fork()。
  2. 线程程序的CPU占用率。

单线程程序的优缺点

优点就是编码简单，容易调试。单线程通常是一个基于IO复用的event loop ，而event loop 有一个明显的缺点，就是它是非抢占式的。

线程池

起到缓冲区作用

异步作用

主线程只需要将任务交给线程池，由线程池分配和调度该任务。

1请求1线程？

内存不足！1线程8MB，10000线程就是80GB。