发表于 | 阅读次数:
字数统计: | 阅读时长 ≈

操作系统

进程线程模型

对于进程和线程的理解和把握可以说基本奠定了对系统的认知和把控能力。==其核心意义绝不仅仅是“线程是调度的基本单位，进程是资源分配的基本单位”这么简单。==

多线程

特征：

  1. 一个进程下有多个线程
  2. 所有线程共享同一个进程的内存空间
  3. 由于线程的访问顺序不同，需要注意对临界变量的访问—> 产生冒险 相同的代码由于调度的顺序不同导致不同的结果

好处：

  1. 不同的线程可以独立的完成工作
  2. 线程的切换的效率要高很多

关键点：

  1. 线程之间有无先后访问的顺序 （线程的依赖关系）
  2. 线程共享访问同一变量（同步互斥问题）
进程

一个可执行文件(程序)的内容：

  • 二进制格式标识
  • 机器语言指令
  • 程序的入口地址
  • 数据
  • 符号表及重定位表
  • 共享库和动态链接信息
  • 其他信息：程序文件包含很多其他信息

进程内存布局

  • 进程的内存分配 P96

    1. 文本段
    2. 初始化数据段
    3. 未初始化数据段
    4. 堆
    5. 栈-（为每个函数设置栈帧，包括函数的地址，变量）
    6. argv 和 environ
    7. 映射到内核的数据结构

  • 虚拟内存管理 P98

    1. 为什么可以用虚拟内存进行管理，局部性原理
      1. 时间局部性
      2. 空间局部性
    2. 内核为每一个进程维护一个页表

  • 栈和栈帧

    栈 为 每个调用的函数分配一个栈帧，其中包括

    • 函数实参和局部变量
    • 调用的链接信息 （CPU寄存器，程序计数器，下一条机器指令的地址）。当调用另一函数时，会在被调用的栈帧中保存这个寄存器的副本，以便函数返回时能为函数调用者将寄存器恢复。

  • 跳转和优化编译器的问题

    • 优化编译器会导致部分变量存储在CPU寄存器中，在执行跳转命令时，类似于(goto)会发生错误，volatile会避免这种优化
系统限制和选项
系统和进程信息
  • 进程信息：/proc/PID/
    • /proc/PID/fd 打开的文件描述符
    • /proc/PID/task 目录
      • /proc/PID/task/TID 为进程下的每个线程建立的一个目录
  • 系统信息：
文件I/O缓冲

  1. 为什么要有对文件I/O进行缓存？

    采用这样的操作主要是因为磁盘操作的速度太慢，这样不需要等待磁盘的操作。

  2. 控制文件I/O的内核缓存

    1. 设置为完整的同步IO – 直接同步到磁盘
    2. 绕过内核的高速缓存：直接I/O
文件系统
目录与链接

  1. 目录

    • i-node表中，会将目录记录为一种文件类型
    • 作为文件的目录，本质上是一个表格，包含文件名和i-node编号

  2. 硬链接

    定义： 在相同或者不同目录的文件，指向同一个i-node编号，这样就可以实现硬链接

    方法： ln abc xyz

    实质：在对应的目录文件中，多记录一个文件，指向同一个i-node ，i-node有一个字段记录了当前链接的目录的个数，只有当删除所有链接时，该文件的数据块才被删除

  3. 符号链接

    定义：一种特殊的文件类型，数据是另外一个文件的文件名

    方法： ln -s test.txt newtest.txt

    实质：在目录下新建了一个文件，数据为该文件的全路径文件名

  4. 硬链接和软链接的差别

    1. 硬链接由于必须指向同一个文件系统内的i-node，所以只能在同一文件系统中建立硬链接
    2. 不能为目录创建硬链接，容易形成环

信号

  1. 概念和概述

    • 信号是事件发生时对进程的通知机制，也叫软件中断。
    • 通常是，内核为进程产生信号：
      1. 硬件异常
      2. 特殊终端字符 (Ctrl-Z or Ctrl-C)
      3. 发生软件事件
    • 信号的分类：
      1. 标准信号：内核向进程通知事件，编号范围1-31
      2. 实时信号：

    // TO-DO

    // 待完善 执行

  2. 进程的创建

    1. pid_t fork()
      • 对父进程内存相应部分的完全复制
      • 父子进程的文件共享，得益于文件描述符记录表和系统级的打开文件表
      • 写时复制的内存语义，刚fork()的时候，内存都是只读状态，这样共享同样的物理内存页，当需要加载新的程序，或者修改对应的内存块时，会新建新的物理内存块，修改对应的虚拟地址对应的页。
      • vfork()
        • 无需为子进程虚拟内页或页表，和父进程共享内存，知道成功的执行exec()或调用了_exit()退出。
        • 在子进程调用exec()或是调用_exit()之前暂停执行父进程
        • 系统保障子进程先收到CPU的调度
      • fork() 后存在竞争状态，如果有同步的需要，可以用信号，或者进程间通信的方式，进行同步

    2. 进程终止exit()

      • _exit()
      • 分为正常关闭和异常关闭
      • 都会执行多个清理的步骤，包括文件相关，进程间通信相关、内存释放相关和Stdio缓存的刷新

    3. pid_t wait(&status)

      • 当存在未被等待返回的子进程时，会一直阻塞。

      • 当所有的子进程都已被等待返回，则会产生错误 等于 -1， 并且使 errno 为 ECHILD，可以用来等待所有子进程释放

      • 正常返回子进程的pid

      • waitpid() 指定对应的pid，进行等待，补充上述的系统调用的不足之处

      • 孤儿进程和僵尸进程

        • 由于父子进程的时间长度不同，必然会导致一些父进程会先于子进程退出，这样就会由众进程之祖(init)接管。

          这样的进程就是孤儿进程

        • 在父进程执行wait()之前，子进程就已经终止，系统任然允许父进程在之后执行wait()操作，来确定子进程是如何终止的。内核通过将子进程转化为僵尸进程来处理这种情况。子进程会释放大部分的内存，唯一保留的是，内核进程表中的一条记录。

    4. exec() 程序的执行

      将新程序加载到某一进程的内存。

      • 文件描述符和exec()
      • system()的实现

    5. 详述进程创建和程序执行

      • 进程记账 在进程终止时，写入一条记录信息
      • 系统调用clone()，也可以创建新的进程，对步骤的控制更加精准
      • exec()和fork()对进程属性的影响

线程

概述 包含线程的进程内存模型
  • 相对多进程的优势
    1. 多进程数据段和代码段都不复用、内存不共享
    2. fork()来创建子进程的代价比较高
互斥量
  1. 加锁和解锁
  2. 只有一个线程能够加锁，其他的会处于阻塞的状态
条件变量

允许一个线程就某个共享变量的状态通知其他线程，并让其他线程等待（堵塞于）这一通知

  1. 通知和等待条件变量。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    condition_variable notfull;
    condition_variable notempty;
    mutex lock;

    void deposit(int data){
        // 先获取共享变量的锁
        unique_lock<mutex> lk(lock);    
        while(deq.size() == capacity){
            // 当不满足生产条件是，会将这个线程放进 等待状态的线程池，在放进去之前会释放获得的锁
            // 当被唤醒后，依然会检查是否可以生产
            not_full.wait(lk);    
        }
        deq.push_back(data);
        lk.unlock();
        not_empty.notify_one();
    }

    notfull.wait(lk);
    notfull.

信号量

一个信号量是一个由内核维护的整数，其值被限制为大于或等于0。在信号量上可以执行各种系统调用：

  1. 将信号量设置为一个绝对值
  2. 当前值的基础上加上一个数量
  3. 当前值得基础上减去一个数量
  4. 等待信号量的值等于0

后面两个操作，可能会导致进程的阻塞。

信号量的系统调用：

  1. semget() 创建信号量
  2. semctl() 初始化信号量
  3. semop() 操作信号量
  4. semctl IPC_RMID 关闭信号量

二元信号量的操作：

  1. 预留p
  2. 释放v

Socket介绍

  1. fd = socket(domain, type, protocal)
    • Domain unix、ip_v4 、ip_v6
    • Type: 流 数据报 分别对应tcp协议和udp协议
流socket
  1. 主动socket (客户端 用connect()发起链接) 和被动socket( 服务器端用listen()将socket设置为被动，及接收请求)
  2. 监听接入连接：int listen(int sockfd, int backlog)
    • sockfd 指定了接收连接的文件socket
    • backlog指定了未决连接的数量，实际上是维护了一个待连接请求的队列。这是由于一个连接只能有一个当前的链接导致的，其他的链接只能阻塞。所以在这个限制内的链接请求会立即成功，因为还维护了一个已连接成功的队列。
  3. 接收连接：int accept(int sockfd, struct sockaddr addr, socklen_t addrlen)
    • 在fd引用的监听流socket上接收一个接入连接。如果没有未决连接就会阻塞
    • 会创建一个新的socket，并且正式这个新的socket会与执行connect()的对等socket进行连接。所以其返回的是已连接的socket的文件描述符。

  4. 连接到对等的socket: int connect(int sockfd, struct sockaddr, len) return 0 success -1 fail

  5. 流socket I/O

    • read() and write () 双向的通信
    • close() 关闭
数据报socket
  1. Socket(): 创建一个数据包socket
  2. Bind(): 允许另外的客户端发送数据报到这里，所以需要绑定一个唯一的地址
  3. Sendto(): 输入指定的地址，发送数据报到指定的地址
  4. Recvfrom(): 在接收数据报的同事，会获得客户端的地址，可以在需要的时候发一个响应，这在客户端为绑定唯一地址的情况下也是允许的。
  5. close()

TCP/IP 网络基础

  1. 物理层
  2. 数据链路层
    • 将IP层的数据报封装为帧进行传输
    • MTU 帧大小的上限
  3. 网络层
    • 本机到目标主机之间IP包的传输
    • IP传输数据报
      • 数据报的大小有上限
      • 这个上限至少有576字节 对于ipv4
    • IP是无连接和不可靠的
    • IP可能会对数据报进行分段
      • ipv4的最大的数据包大小为65535字节 + 40 字节头信息
      • 定义了路径MTU的概念
      • 分段对于客户端来说是透明的，收到后会进行重组
    • IP地址
  4. 传输层
    1. 端口号
      1. 特殊端口 1- 1023
      2. 普通端口
    2. 用户数据包协议
      1. 在数据包前只添加了端口号和一个数据校验和
      2. 无连接和不安全的
    3. 传输控制协议
      1. 流量控制
      2. 慢启动和拥塞控制
Internet Domain

  1. 网络字节序

    多字节整数的存储顺序

    • 大端模式 1234 先存12 再存34
    • 小端模式 1234 先存34 再存12
    • 小端架构是x86架构的机器
    • 其他主要的硬件架构的字节序都是大端架构
    • 网络字节序也是大端的
    • socket的地址结构中的整数，应该按网络字节序进行存储

  2. 数据表示

    对传输数据进行的编码

  3. 主机和服务转换函数

  4. 域名系统(DNS)
深入探讨TCP协议

  1. TCP报文的格式

    1. 源端口号 + 目标端口号 (16 + 16)
    2. 序列号（32）
    3. 确认号（32）
    4. 首部长度 + 保留位 + 控制位 + 窗口大小 (4 + 4 + 8 + 16)
    5. 数据校验和 + 紧急指针 (16 + 16)
    6. 选项
    7. 数据

    控制位：

    1. CWR 减小窗口大小
    2. ECE 拥塞控制回显
    3. URG 紧急包
    4. ACK 确认包标识
    5. PSH
    6. RST 重置连接
    7. SYN 同步信号标识
    8. FIN 完成发送任务

  2. TCP的序列号和确认机制

    确保面向连接和安全的

  3. TCP协议的状态机和状态迁移图

  4. shutdown()支持只关闭一端的通道，变成半双工

  5. TTL 生成时间字段

  6. 为什么TIME_WAIT的时间为2MSL

    1. 防止对方重发可以收到该重发的包
    2. 将上一个连接的包彻底清除

  7. 监控套接字的cmd

    netstat -a

  8. 使用tcpdump来监视TCP流量

其他备选的IO模型

应用大多数都需要2个方面的要求：

  1. 用非阻塞的方式去进行IO操作
  2. 同时检查多个文件描述符，也就是同时处理多个IO

这里有三个满足上述要求的选项：

  1. IO多路复用
  2. 信号驱动I/O
  3. epoll
IO多路复用

  1. int select(int nfds, fd_set readfds, fd_set wfds, fd_set *exceptfdts, struct timeval time_out)

    将自己需要控制的IO，放到对应的读事件，写事件，异常事件的集合中。

    FD_ZERO and FD_SET对集合进行初始化

    FD_ISSET检查是否就绪

  2. int poll(struct pollfd fds[], nfds_t fds_t, timeval timeout)

    fds[] 输入了我们想要监控的fd，以及对应请求的时间，返回中记录了就绪的事件

  3. select 和 poll的缺陷

    1. 内核必须检查所有被指定的文件描述符
    2. 在调用的时候。每次都要讲文件描述符的数据结构拷贝到内核
    3. 调用完成后还必须检查所有的文件描述符是否处于就绪态
信号驱动IO
  1. 为内核发送的通知信号安装一个信号处理函数
  2. 设定文件描述符的属主
  3. 使能非阻塞IO
  4. 使能信号驱动IO O_ASYNC
  5. 调用进程可以执行其他的任务
  6. 信号驱动IO使用的是边沿触发，当事件状态发成改变时，发送信号，中断当前的进程，执行信号处理函数
epoll

epoll由三个系统调用组成

  1. 系统调用epoll_create()创建了一个epoll实例，返回代表该实例的文件描述符
  2. epoll_ctl() 操作和epoll相关联的兴趣列表，增加，删除、修改新的文件描述符到列表中
  3. epoll_wait() 返回就绪列表中的成员

发表于 | 阅读次数:
字数统计: | 阅读时长 ≈

leetcode列表

序号 题目 代码 解答
1 二叉搜索树的第k大节点 😊 😊
2 实现LRU内存模型 😊 😊
3 并查集实现最小生成树 😊 😊
4 最短路径算法 🙂 🙂
5 重载赋值运算符 😀 😀
6 调整数组使奇数位于偶数前面 😀 😀
7 第一个只出现一次的字符 😂 😂
8 奇偶升降序数组重组

解答：

  1. 二叉搜索树的第K大节点

    • 解答：二叉搜索树的中序遍历有序的特点

    • 代码

      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
      #include <iostream>
      #include <stack>

      using namespace std;

      int midTravelKthest(TreeNode* root, int k){
          TreeNode* p = root;
          stack<TreeNode*> s;
      	int count = 0;   
          while(p || !s.empty()){
              if(p){
                s.push(p);
                p = p->left;  
              }else{
                  p = s.top();
                  s.pop();
                  count++;
                  if (count == k) {
                      cout << p->val << endl;
                      return;
                  }
                  p = p->right;
              }    
          }
      }

  2. 实现LRU内存模型

    • 解答：

      • get操作，先检查pos 优先级set里面是否有该元素，如果有则重新put该k-value。
      • put操作，先检查其中pos是否有该key，如果有，则erase该元素 通过iterator，如果没有，则检查元素的个数是否达到了capacity，如果到了就要将list队尾元素erase掉；最后统一的在队列最前面插入元素，并在pos中记录其位置

    • 代码：

      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
      28
      29
      30
      class LRU {
      public:
          LRU : capacity(int ca){}

          int Get(int key){
              if(pos.find(key) != pos.end()){
                  Put(key, recent[pos[key].second]);
                  return recent[pos[key]].second;
              }

              return -1;
          }

          int Put(int key, int val){
              if(pos.find(key) != pos.end()){
                  recent.erase(pos[key]);
              }else if (pos.size() >= capacity){
                  pos.erase(recent.back().first);
                  recent.pop_back();
              }

              recent.push_front({key, val});
              pos[key] = recent.begin();
          }

      private:
          int capacity;
          list<pair<int, int>> recent;
          unordered_map<int, list< pair<int, int> >::iterator> pos;
      };

  3. 并查集生成找到最小生成树

    • 标签：并查集

    • 解答：最小生成树，是将一个图形成一个连接分量，而这个连接分量的边的权值之和最小。采用贪心法，首先将边按权值大小进行排序。边按大小顺序进行连通，连通前检查该连通的头是否相同，即是否形成环，若形成环则取消该边的加入，若不形成环则将该边加入到连通分量，当连通了所有的点之后，则形成了左右的最小的生成树

    • 代码：

      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
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      #include <iostream>
      #include <vector>

      using namespace std;
      //第一部分完成并查集类的设计

      class UnionFindSet {
      public:
          UnionFindSet(int s){
              size = s;
              parents = vector<int>(-1, s);
          }
          
          int Find(int x){
              if(parents[x] < 0) return x;
              return parents[x] = Find(parents[x]);
          }
          
          void Union(int root1, int root2){
              if(root1 == root2) return;
              if(parents[root1] < parents[root2]){
                  parents[root2] = root1;
                  parents[root1] -= 1;
              }else {
                  parents[root1] = root2;
                  parents[root2] -= 1;
              }
              return;    
          }    
          private:
          vector<int> parents;
          int size;    
      }


      struct Edge {
          int begin;
          int end;
          int val;
      }


      vector<Edge> krus(vector<Edge> edges, int n){
          vector<Edge> res;    
          UnionFindSet ufs = new UnionFindSet(n+1);
          for(auto edge : edges){
              q.push(edge);
          }
          int i= 0;
          while(i < n){
      		Edge temp = q.top();
              q.pop();
              
              if(ufs.Find(temp.begin) == ufs.Find(temp.end)){
                  continue;
              }else{
                 	ufs.Union(ufs.Find(temp.begin), ufs.Find(temp.end));
                 	res.push_back(temp);
                 	i++;
              }
          }
          return res;
      }

  4. 最短路径算法-dijskra算法

    标签：priority_queue

    解答：算法有几个辅助的存储，

    • dis保存每个点到起点的距离的数组
    • vis记录是否拜访过
    • pre记录通过该点的上一个拜访点
    • priority_queue记录了可访问点的集合，保存的是pair<dis, node_id> 该点到起点的最小距离，通过优先级对列每次都将最小距离的点先拜访，这样就形成了最短路径，到该点的距离最短

    代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int Dijkstra(int x){
        while(!q.empty()){
            pair<int, int> temp;
            temp = q.top();
            q.pop();

            if( vis[temp->second] != 0) continue;
            vis[temp->second]++;

            for(int i = 1; i <= M; i++){
                if(graph[temp->second][i] < INT_MAX && vis[i] != 0 && dis[i] > dis[temp->second] + graph[temp->second][i]){
                    dis[i] = dis[temp->second] + graph[temp->second][i];
                    pre[i] = temp->second;
                    q.push_back(make_pair(dis[i], i));
                }
            }
         }
    }

错题集

序号 题目 代码 解答
1 清除注释代码 😊 😊
2 空缺的第一个正整数 😢 😢
3 数组组成最小的整数 😭 😭
4 Knight走棋的最小步骤 🙂 🙂

  1. remove comments from a given c/c++ program

    • 标签：c++, string
    • 解答：指定单行注释标示和多行注释标示，当处理流程为判断当前的是否处在注释期间，处理流程为：
      • 如果在单行注释区间，是否当了行尾
      • 如果在多行注释区间，是否在多行注释结尾
      • 如果在注释区间，当前字符丢弃
      • 如果不在注释区间，而找到了单行注释的开头，改变单行注释的标示
      • 不在注释区间，找到了多行注释的开头，改变多行注释的标示
      • 如果不在注释区间，也没找到标示，则留下当前字符
    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    #include <iostream>
    using namespace std;

    string removeComments(string prgm)
    {
        int n = prgm.length();
        string res;

        // Flags to indicate that single line and multpile line comments
        // have started or not.
        bool s_cmt = false;
        bool m_cmt = false;

        // Traverse the given program
        for (int i=0; i<n; i++)
        {
            // If single line comment flag is on, then check for end of it
            if (s_cmt == true && prgm[i] == '\n')
                s_cmt = false;

                // If multiple line comment is on, then check for end of it
            else if  (m_cmt == true && prgm[i] == '*' && prgm[i+1] == '/')
                m_cmt = false,  i++;

                // If this character is in a comment, ignore it
            else if (s_cmt || m_cmt)
                continue;

                // Check for beginning of comments and set the approproate flags
            else if (prgm[i] == '/' && prgm[i+1] == '/')
                s_cmt = true, i++;
            else if (prgm[i] == '/' && prgm[i+1] == '*')
                m_cmt = true,  i++;

                // If current character is a non-comment character, append it to res
            else  res += prgm[i];
        }
        return res;
    }

    // Driver program to test above functions 
    int main() 
    { 
        string prgm = "   /* Test program */ \n"
                      "   int main()  \n"
                      "   {           \n"
                      "      // variable declaration \n"
                      "      int a, b, c;    \n"
                      "      /* This is a test  \n"
                      "          multiline     \n"
                      "          comment for   \n"
                      "          testing */      \n"
                      "      a = b + c;       \n"
                      "   }           \n"; 
        cout << "Given Program \n"; 
        cout << prgm << endl; 
        cout << " Modified Program "; 
        cout << removeComments(prgm); 
        return 0; 
    }

  2. 空缺的第一个正整数

    • 标签：array

    • 解答：

      • 位图法：将每个正整数进行按顺序进行标记
      • 转换位置法：将数据按其大小放到该放的位置上，速度上较快，缺点：当不是从0开始计数时，则需要先找到最大的数据
      • 去重后的最小堆：将数据一个个放出，是否满足规则，但是比较慢

    • 代码：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      int firstMissingPositive(vector<int> &nums){
          int n = nums.size();
          for(int i = 0; i < n; i++){
              while(nums[i] != i + 1){
                  int v = nums[i];
                  // 针对从0开始的第一个缺失的数，大于0的数据即可丢失
                  if(v > n || v <= 0) break;
                  else{
                      if(nums[v-1] == v) break;
                      swap(nums[v - 1], nums[i]);
                  }
              }
          }
          
          for(int i=0; i < n; i++){
              if(nums[i] != i + 1) return i +1;
          }
         
          return n + 1;    
      }

  3. 数组组成最小的整数

    标签: string

    解法：理解比较算法，通过字符串大小的比较得到字符串相对的位置，最后将字符串的位置串起来就可以得到最后组成的最小的字符串，由于算法题需要证明字符串比较的各种延展和传递性，这里不展开比较。

    代码：

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    //
    // Created by zhanGGe on 2018/10/23.
    //

    #include <iostream>
    #include <string>
    #include <vector>

    using namespace std;


    int main(){

        int N;
        cin >> N;
        vector<string> data_s(N, "");
        for(int i = 0; i < N; i++){
            cin >> data_s[i];
        }

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N - i - 1; j++){
                if(data_s[i] > data_s[i+1]){
                    string temp = data_s[i];
                    data_s[i] = data_s[i + 1];
                    data_s[i + 1] = temp;
                }
            }
        }

        string res = "";

        for(int i = 0 ; i < N; i++){
            res += data_s[i];
        }

        cout << res << endl;


        return 0;

    }

    反思：对string还是不是很熟悉，默认的库里已经对string的各种操作符进行了重载完全可以重新使用包括“+”， “>”等等。对于剑指offer的题目的理解和练习漏洞太多了。

  4. knight的最小步数

    关键词： bfs

    解析：当处理图中最小步数问题的时候，直接想到最短路劲问题，最短路径的实现实际上就是利用的bfs，分层去探索不同的路，当找到重点时反馈行走的步数，若队列都pop完了还是没找到，则不可能到达改点返回-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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    //
    // Created by zhanGGe on 2018/10/23.
    //

    #include <iostream>
    #include <vector>
    #include <queue>

    using namespace std;

    int moves[][2] = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};

    struct pos{
        int x;
        int y;
        pos(int m, int n){
            x = m;
            y = n;
        }
    };

    int main(){
        queue<pos> q;
        pos start(2, 2);
        q.push(start);
        int D_x = 0;
        int D_y = 1;
        int M = 5;
        int N = 5;
        int count = 0;

        if(start.x == D_x && start.y == D_y) {
            cout << 0;
            return 0;
        }

        while(!q.empty()){
            count++;
            pos temp = q.front();
            q.pop();
            for(auto move : moves){
                int x = temp.x + move[0];
                int y = temp.y + move[1];

                if(x== D_x && y == D_y){
                    cout << count << endl;
                    return 0;
                }

                if(x >=0 && x < M && y >= 0 && y < M){
                    q.push(pos(x, y));
                }
            }
        }
        cout << -1 << endl;
        return 0;
    }

    反思：

    • 对queue的几个操作还不熟悉
      • front() 返回 队列的头
      • back() 返回队列的尾
      • push() 插入元素在尾部
      • pop() 在头部删除元素
    • 对于图或者树的BFS的理解不够
      • BFS肯定类似于层次遍历，肯定不能采用递归的方法，需要使用非递归加queue的方法去使用

  5. 重载赋值运算符

    解答：这里考虑的主要问题是带类成员变量的类的赋值运算函数的重载要考虑深复制，这里先

    • 复习一下：

      • 赋值运算函数和复制构造函数的区别和运用的场景的不同。

      • 复制构造函数： 用于将一个对象复制到新创建的对象中。用于初始化过程中

        • 何时调用：新建一个对象并将其初始化为同类的现有对象时

          1
          2
          string metoo = motto; // 调用复制构造函数
          string also = String(motto); // 先复制构造函数

          每当程序生成一个对象的复本，编译器都会先调用的复制构造函数，具体说就是按值传递或函数返回对象的时候，就是说产生临时复本的时候都会调用复制构造函数，所以用值传递减少复制构造函数的调用

        • 有何功能：

          • 默认的复制构造函数会逐个复制非静态的成员函数，复制的是成员的值，所以默认的复制构造函数只是浅复制
          • 一般要定制显示构造函数进行深度复制

      • 赋值运算符的重构

        • 定义：类对象赋值。通过类重载赋值运算符实现。
        • 何时使用：将已有的一个对象赋值给另外一个对象的时候，将使用重载的运算符
        • 有何功能：
          • 复制数据前会将以前的分配的空间进行释放
          • 函数应该避免将值赋给自身，因为赋值前会将自己空间进行释放
          • 函数指向一个指向调用对象的引用，因为需要进行连续的赋值

      • 引出关于运算符的话题

        • 重载的运算符是选择成为成员函数还是非成员函数

          • 成员函数通过成员进行调动

          • 非成员对象不需要成员调动，左边的操作数对应于运算符函数的第一个参数，右边的操作符对应于第二个参数，问题是非成员函数不能访问类的私有数据

            Friend Time operator*(double m, const Time &t);

        • 双向操作符和单向操作符在重载的时候有区别吗？

    • 解法：按上述的三个要点

    • 代码：

      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
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      class string {
      public:
      	string(const char* s);
          string();
          ~string();
      private:
          char* str;
          int len;
      }
      // 1. 返回string &， 这样才可以连续赋值
      // 2. 输入的参数为常量引用，引用可以减少复制构造函数调用，由于函数内不会变更实例的状态，需要将输入参数的定义为常量
      // 3. 需要将原先对象占据的空间清除
      // 4. 赋值操作需要避免赋值给自己，需要检查是否赋值给自己


      string & string::operator=(const string & st){
          if(this == &st) return *this; //避免自己赋值给自己    
          delete[] str;
          len = st.len;
          str = new char[len + 1];
          std::strcpy(str, st.str);
          return *this;
      }

      // 升级的代码考虑了异常安全性的原则， 赋值函数内部抛出异常的时候，str由于delete了，会指向不定的地址，导致异常安全性问题，完美的方案是不让空指针产生，让临时的string变量承接输入变量，置换内部的指针和变量，临时变量调用正常调用析构函数释放空间
      string& string::operator=(const string & st){
          if(this != &st){
              string temp(st);
              char* pTemp = temp.str;
              temp.str = str;
              str = pTemp;
              
              int lenTemp = temp.len;
              temp.len = len;
              len = lenTemp;
          }    
          return *this;
      }

  6. 奇偶升降序数组重组

    题目：一个数组奇数位是降序，偶数位是升序，重组数组，将数组从小到大排列，算法复杂度要求是O(n)。

    解法：可以将奇数位数组想成一个带顺序的数组，偶数位数组也是一个带顺序的数组，题目就是一个合并两个排序数组的题目。

    代码:

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    //
    // Created by 张哲 on 2018/11/8.
    //

    #include <vector>
    #include <iostream>

    using namespace std;

    vector<int> MySort(vector<int> data){
        int len = data.size();
        int i = 0;
        int j = (len % 2 == 0) ? len -1 : len - 2;

        cout << "i: " << i << endl;
        cout << "j: " << j << endl;
        vector<int> res;

        while( i <= (len - 1) && (j >= 0)){
            if(data[i] < data[j]){
                res.push_back(data[i]);
                i = i + 2;
            }else{
                res.push_back(data[j]);
                j = j - 2;
            }
        }

        while(i <= len - 1){
            res.push_back(data[i]);
            i = i+ 2;
        }

        while(j >= 0){
            res.push_back(data[j]);
            j= j - 2;
        }

        return res;

    }

    int main(){
        vector<int> data = {0, 10, 1, 9, 2, 5, 4, 4, 5, 3, 10, 2, 20, -1};

        for(auto v : MySort(data)){
            cout << v << " " ;
        }
        cout << endl;
        return 1;
    }

动态规划专题

  1. 最长有效括号对

  2. Unique Path II 有障碍物情况下，一点到另外一点的走法

序号 题目 解答 代码
1 将数据尽量平均的分到两个数组 🤣 🤣

  1. 将数据尽量平均的分到两个数组

    关键词： 动态规划

    解答： 将数组尽量平均的分配到两个数组，可以转化为将数据放到zongzhizongzhi

海量数据处理

TopN的问题
  1. 海量数据中找到重复次数最多的一个
内存可以放下的TopN问题
  1. 快排降低排序数量
  2. 堆排序，保留topN

位图法

  1. 在2.5亿数字中找出不重复的数字
    • 使用2-bit位图法，00表示不存在，01表示出现一次， 10表示出现多次，11表示无意义。这样需要1G内存
    • 或者hash划分小文件，小文件使用hash_set检查各个元素，得到不重复的整数

  2. 如何在40亿数字中判断是否有某个数

    • 位图法标记某个数是否存在，check标记数组

  3. 设计题： 设计长链接转短链接

  4. 基于范围的查找的数据结构： B+树 和跳表
  5. 散列表扩容的方案
  6. static 其他文件调用的方法

哈夫曼树

  • 是什么？

    霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+…+WnLn），N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。

  • 怎么用？

    1. 怎么构建哈夫曼树？

      演算过程[编辑]

      进行霍夫曼编码前，我们先创建一个霍夫曼树。

      ⒈将每个英文字母依照出现频率由小排到大，最小在左，如Fig.1。

      ⒉每个字母都代表一个终端节点（叶节点），比较F.O.R.G.E.T六个字母中每个字母的出现频率，将最小的两个字母频率相加合成一个新的节点。如Fig.2所示，发现F与O的频率最小，故相加2+3=5。

      ⒊比较5.R.G.E.T，发现R与G的频率最小，故相加4+4=8。

      ⒋比较5.8.E.T，发现5与E的频率最小，故相加5+5=10。

      ⒌比较8.10.T，发现8与T的频率最小，故相加8+7=15。

      ⒍最后剩10.15，没有可以比较的对象，相加10+15=25。
      进行编码

      1.给霍夫曼树的所有左链接’0’与右链接’1’。

      2.从树根至树叶依序记录所有字母的编码，如Fig.3。

发表于 | 阅读次数:
字数统计: | 阅读时长 ≈

C++细节探究

  1. 模板在编译的时候是怎么编译的?

    • 什么是模板？为什么会有模板？

      继承和包含并不总是满足重用代码的需要。所以会有模板

      C++的类模板是一种生成通用类声明的更好的方法。

    • 模板怎么提供通用的类声明

      方法是通过提供参数化类型，将类型名作为参数传给接收方来建立类或函数

    • 函数模板和类模板的举例

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      //函数模板
      template<typename T>
      int compare(const T& left, const T& right) {
          if (left < right) {
              return -1; 
          }
          if (right < left) {
              return 1; 
          }
          return 0;
      }

      compare<int>(1, 2); //使用模板函数

      // 类模板
      template<class T>
          class Human {
              T t;
          public:
              Human(T test) : t(test){}
          }
      Human<int>(1); //使用类模板

  2. 零值比较

    • bool: if(ok)
    • int: if(ok == 0)
    • pointer: if(ok == null)
    • float: if(ok <= 1e-5 && ok >= -1e-5)
  3. sizeof 和 strlen的不同
    • 运算符 和 标准库函数
    • sizeof 可以运算任何类型的大小 strlen只能得到”\0”结尾的字符串的大小
    • sizeof的大小要提前指定好，因为在编译期间就要确定下来
  4. 对象之间的复制(类默认赋值函数)
    • 可以赋值，当存在指针成员变量时，要提前的深拷贝
    • 深拷贝和浅拷贝的区别
  5. static的作用
    • 全局静态变量 限制了变量的作用域，只能在本文件中被使用
    • 局部静态变量 由于存储在静态区，延长了变量的使用时间，只有程序结束的时候，该变量的生命周期才结束。
    • 修饰类成员(变量 和 函数) 所有的实例共有
    • 满足函数在不同调用期的通信，满足不同类对象之间的通信-> 单例模式
    • static的默认值是0

  6. 结构体和类的区别

    • 结构体的默认访问权限是pubic 类是private
  7. malloc 和 new 的区别
    • malloc和free 是标准库函数， new和delete是运算符
    • malloc分配空间后，不能吊起构造函数， free也不能吊起构造函数； new吊起构造函数， delete调起析构函数
    • malloc返回void指针， new返回对应类指针
  8. 指针和引用的区别
    • 引用只是给变量起了一个别名，不占内存空间。 指针是新分配了一个指针的空间
    • 引用声明时必须初始化，指针可以先申明再初始化
    • 引用只能指定一个变量，指针可以先指向一个变量，然后再指向另一个变量
    • 引用必须指向一个变量的实体，指针可以是一个空指针
  9. 宏定义和函数的区别
    • 宏定义在预编译时就替换了代码，相当于直接插入了代码，运行时不需要跳转；函数运行需要跳转
    • 宏定义没有类型检查；函数有类型的检查
  10. 宏定义和const的区别
    • 宏定义在预编译阶段；const在编译的阶段
    • 宏没有类型检查； const有类型检查
    • 没有分配空间，直接代码插入； const要占据内存空间
  11. 宏定义和typedef的区别
    • 宏定义主要用于常量和复杂函数的表示；typedef主要用于类型的别名
    • 编译前替换；typedef还是在编译期间
  12. 宏定义和内联函数的区别
    • 内联函数也是函数，在编译期间起作用，也可以做类型检查
    • 具有函数的重载等功能
    • 内联函数可以作为类的成员函数使用类的保护成员和私有成员
  13. 数组名和指针的区别
    • 可以将数组名理解为常量指针，所以没有自增和自减的操作
    • 数组名传递给一般指针后就退化了，sizeof就计算不出整个数组的大小

面向对象基础

  1. 三大特性
    • 封装性
    • 继承性
    • 多态性
    • 模板特性(c++)
  2. public/protected/private的区别
    • public ，类的内部和外部都可以访问
    • protected，只有类的内部成员或者派生类中可以访问
    • private， 类的内部成员访问派生类内部不可以访问
  3. 对象的存储空间
    • 非静态成员的数据类型大小之和
    • 编译器额外加入的虚函数指针变量，指向虚表，虚表保存的是虚函数的地址的列表
    • 还有一些对齐的padding
  4. 空类的大小和有哪些成员函数？
    • 空类的大小为1字节
    • 成员函数有：
      • 构造函数
      • 析构函数
      • 默认拷贝函数
      • 默认赋值运算符
      • 取地址函数
  5. 构造函数和析构函数必须是基类指针吗？
    • 构造函数
      • 构造函数不能是虚函数，虚函数的作用在于通过子类的指针或引用来调用父类的那个成员函数。而构造函数是在创建对象时自己主动调用的，不可能通过子类的指针或者引用去调用。
    • 析构函数
      • 析构函数一般都要为虚函数，
      • 只有当析构函数为虚函数时，delete调一个基类指针的类时，才会调起对应的子类的析构函数
  6. 构造函数和析构函数的调用顺序是？
    • 构造函数(从初始化列表的运行顺序可看出)
      • 基类构造函数：多层基类则先构造最上层的基类，依次向外，如果是多继承则从左到右
      • 成员变量的构造函数： 先构造成员变量的构造函数，然后调用本类的构造函数
      • 派生类的构造函数
    • 析构函数
      • 析构顺序与构造顺序相反
  7. 拷贝构造函数和赋值运算函数的区别？
    • 拷贝构造函数是函数，赋值运算符是运算符重载。
    • 拷贝构造函数会生成新的对像，赋值运算符不会
    • 在形参传递的时候是调用拷贝构造函数，因为生成了本地的新对象
  8. 覆盖、隐藏和重载的区别
    • 重载，在相同的类或作用域下，当函数名相同，参数不同的情况就发生了函数的重载
    • 覆盖，当虚函数在派生类中对虚函数进行了实现的时候，派生类的虚函数地址对原虚函数的地址进行了覆盖
    • 隐藏，派生类本来是集成了基类的成员函数，当派生类又实现了基类函数，而且这个基类成员函数还不是虚函数的情况下，就会把基类成员函数给隐藏，不管参数时候相同。
  9. 哪几种情况需要用到初始化列表
    • 初始化const成员
    • 初始化一个reference成员
    • 调用基类的构造函数，并且该函数需要参数
    • 调用数据成员对象的构造函数，而该函数需要参数

STL(标准模板库)

  1. Vector

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    定义：
    	vector<T> vec;
    插入元素：
    	vec.push_back(T);
    	vec.insert(iterator, T);
    删除元素：
    	vec.pop_back();
    	vec.erase(iterator);
    修改元素:
    	vec[position] = T;
    遍历容器：
    for(auto it = vec.begin(); it < vec.end(); it++){

    }
    其他：
    	vec.empty();
    	vec.size();
    	vec.capacity();
    	vec.begin();
    	vec.end();

    实现：

    • 线性表，数组实现：
      • 支持随机访问
      • 插入删除操作需要大量的移动元素
    • 需要连续的物理存储空间
    • 当空间不够及 size < capacity 的时候，需要空间拓展*2

    迭代器失效：

    • 插入元素：
      • 尾后插入，当size < capacity时， 首迭代器不失效，其他失效。

  2. map

    实现：

    • 树状结构，插入和删除操作不需要数据的复制，不连续的内存空间
    • 操作复杂度和树的高度相关

    红黑树的基本概念：

    • 红黑树是二叉排序树

      • 左子树的所有元素都比根节点小
      • 右子树所有节点都比根节点大
      • 左右子树也都是二叉排序树

    • 而且还要满足几点要求

      • 树中所有节点非黑即红
      • 根节点必须是黑色
      • 红色节点的子节点必须为黑
      • 从根到NULL的任何路径上黑节点的数量必须相同

    • 查找时间都是O(logn)

    • 红黑树节点的定义

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      enum Color {
          red 	= 0;
          black 	= 1;
      };
      struct RBTreeNode{
          struct RBTreeNode* left, *right, *parent;
          int key;
          int data;
          Color col;
      };
      1. 相对于平衡二叉树，平衡性稍差但是旋转次数会降低
      2. 相对于普通的二叉查找树，平衡性要好，查找效率要高

  3. set

    常用操作

    1
    2
    3
    4
    5
    6
    unordered_set<int> st;
    st.insert(1);
    st.erase(1);

    st.find(1);
    st.count(1);

编程基础

  1. 为什么会有C++，相对于C语言的升级在哪？
    • 添加了了面向对象编程
    • 继承了C语言高效、简洁、快速和可移植的特点。
    • 添加了泛型编程方法
  2. C/C++语言的历史发展和必要性
  3. 条件编译#ifdef, #else, #endif作用？
    • 通过#ifdef来判断，将某些具体的模块包括到要编译的内容 ，只判断之前是否有该宏定义
    • 子程序前加#define DEBUG 用于程序调试
    • 应对硬件的设置
    • 条件编译可以减少被编译的语句

编译和调试

编译

预处理

  • 宏定义的替换 #define

  • 条件编译语句过滤代码 #ifdef

  • 处理#include指令，插入对应的文件到指令的位置 #include

  • 过滤所有的注释的语句

  • 添加行号和文件名标识
  • 保留所有的#program编译器指令 #program
编译
  • 词法分析
    • 读取源程序的字符，生成词法单元序列
  • 语法分析
  • 语义分析
  • 中间语言生成 汇编
  • 目标代码生成与优化 二进制代码
链接

各个源代码模块独立的被编译，然后将他们组整起来，组装的过程就是链接。将所有目标文件的代码段拼接到一起，然后将所有对符号地址的引用加以修正。

  • 静态链接

    在编译时和静态库(lib**.a)链接在一起成为完成的程序。通常静态库就是对多目标文件(.o)文件的打包。细节：静态链接被用到的目标文件都会复制到最终生成的可执行文件中。这种方式的好处是在运行时，可执行文件已尽装载完毕，速度比较快。

    静态文件是对多目标文件的打包，这里介绍些打包命令。

    1
    2
    3
    gcc -c test1.c // 生成test1.c
    gcc -c test2.c // 生test2.c
    ar cr libtest.a test1.o test2.o

    在生成可执行文件需要使用到它的时候只需要在编译时加上即可。

    1
    gcc -o main main.c -ltest

  • 动态链接

    多个程序都需要某个静态库，在每个程序中都需要拷贝一份，所以出现动态链接来解决这个问题。

    首先打包成动态库，文件名为lib + 动态库名+ .so 后缀。编译时加上-fPIC选项，打包时加上-shared选项。

    1
    2
    3
    gcc -fPIC -c test1.c
    gcc -fPIC -c test2.c
    gcc -shared test1.o test2.o libtest.so

    使用动态链接的用法和静态链接相同

    1
    gcc -o main main.c -ltest

  • 静态链接库和动态链接库的对比

    • 动态链接库运行时会先检查内存中是否存在该库的拷贝，若有则共享拷贝，标准模版库就是动态链接库。
    • 动态链接库的升级更新很容易
    • 静态链接库执行效率会比较高

  • 静态联编和动态联编的区别

makefile编写

自动化编译的工具

  • 基本规则

    1
    2
    A:B
    (tab)<command>

    A是语句最后生成的文件，B是生成A所依赖的文件，比如生成test.o依赖test.c 和 test.h, 则写成 test.o:test.c test.h。接下来一行的开头必须是tab ，再往下就是实际的命令, 比如 gcc.c -c test.c -o test.o 。

  • 变量

    在文件中可以定义变量，在之后需要使用的时候只需要写一个$符号加上变量名即可。

  • 自动寻找依赖

    第一条目标即为编译输出的目标，程序会依次寻找依赖的关系，当依赖不存在时，贼寻找下面的生成目标形成隐形的依赖生成

调试

符号解析

  • 可重定位目标文件 (relocatable file)

    独立编译后的(.o)文件，其ELF文件格式包括：

    • ELF头，指定文件的大小及字节序
    • .text， 代码段
    • .rodata, 只读数据区
    • .data，已初始化数据区
    • .bss，未初始化数据区
    • .symtab，符号表

  • 解析符号表

    • 将每个引用和文件中的符号表的一个符号定义联系起来

重定位

  • 合并节

    多个可重定向目标文件中的相同的节合并成一个完整的聚合节，例如多个目标文件的.data节合并为可执行文件的.data节。

  • 重定位符号引用

    修改全部代码节和数据节对每个符号的引用，执行正确的运行时地址。

可执行目标文件

  • ELF头部

    描述文件的总体格式，并且包括程序的入口点，即第一条指令地址

  • 段头部表

    描述了可执行文件数据段、代码段等各段的大小、虚拟地址、段对其、执行权限等。通过段头部表描绘了虚拟存储器运行时存储映像，比如每个unix程序的代码段总从虚拟地址的Ox0804800开始。

  • 其他段

    和可重定位目标文件相同，但是完成了多个节的合并和重定位的工作

加载

  • 克隆

    新程序的执行首先要父进程fork()得到一个子进程，该子进程除了pid等标识不同其他基本均与父进程相同。

  • 重新映射

    当子进程执行自己的系统调用时，会先清空子进程现有的虚拟存储段(不再映射到父进程到各个段)，之后重新创建子进程虚拟存储器各段和可执行文件各段的映射。可理解为对复制进来的父进程页表进行重写，映射到外存中的各个段。

  • 虚页调入

    加载器跳转到入口地址_start开始执行程序，接下来的过程需要配合虚拟存储器来完成。CPU获得了指令的虚拟地址后，若该指令不再内存中，则从外存中调入。

发表于 | 阅读次数:
字数统计: | 阅读时长 ≈

网络通信

OSI七层通信协议模型

  • 物理层 电线、光纤
  • 数据链路层 网关、ARP、Mac地址 帧
  • 网络层 IP传输 数据包
  • 传输层 TCP UDP
  • 会话层
  • 表示层
  • 应用层

传输层

  1. 表示层和会话层的功能是什么

    1. 表示层，对数据的表示，编解码 (图像，视频，数据编解码)
    2. 会话层： 建立会话， 如session认证，断点续传

  2. 描述TCP的头部

    • 源端口号(16bit) 和 目的端口号(16bit)

    • 序号（32bit）： 字节流的字节编号，用于解决网络传输的乱序的问题；

    • 确认号 (32bit) : 接收方给发送方确认报文的编号，其值是收到的序号+1；
    • 首部长(4bit): 标识首部的长度为多少个4字节
    • 标志位(6bit)：
      • URG：是否紧急
      • ACK：确认报文段
      • PSH： 提示接收方理解从缓存中读取数据
      • RST: 复位报文段
      • SYN：表示请求建立一个连接
      • FIN：表示请求中断连接
    • 窗口(16bit)：接受窗口，告知对方（发送方）本方还有多少空间可以接受数据。用于流量控制
    • 校验和(16bit): 检查报文段是否有损坏

  3. TCP socket交互流程

    • 服务器：

      • 创建socket, int socket(int domain, int type,int protool)

      • 绑定socket和端口号, int bind(int sockfd, const struct sockaddr *addr, socklen_t addrlen)

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        // IPv4的sockaddr地址结构
        struct sockaddr_in {
            sa_family_t sin_family;    // 协议类型，AF_INET
            in_port_t sin_port;    // 端口号
            struct in_addr sin_addr;    // IP地址
        };
        struct in_addr {
            uint32_t s_addr;
        }

        addrlen：地址长度。

      • 监听端口号 -> int listen(int sockfd, int backlog);

        • 要监听的sock描述字
        • 可以排队的最大连接数

      • 接收用户请求 -> int accept(int sockfd, struct sockaddr addr, socklen_t addrlen);

  4. IO的分类和实现方式

    1. 同步、异步、轮询和回调的不同之处

      本质：进程间的通信的方式

      1. 信号量

        不同的信号在通信的时候，需要指定信号的通信方式，需要是同步还是一部的—linux的通信方式的复习

      • 同步：同步及单次的写入不完成就不返回，进程阻塞在单次的请求中，不去做其他的事情
      • 异步：异步，当前进程被阻塞时，先返回，请求的结构暂时不返回。
      • 轮询：异步请求返回的结果通知有很多的方式，一种是通知的方式，这样当前需要不算的轮询返回的结果，这样相当于需要不断的轮询是否有通知到达
      • 回调：异步返回的结果，通过直接告知的方式，底层可以通过信号量的方式进行实现，这样当前进程不需要不断轮询单次请求是否有结果返回。效率更高。

  5. TCP通信在底层发生了什么？

    • 建立连接后内核发生了什么？

      当建立socket连接的时候，内核省成本了两条队列：一条用了装正在请求的客户端请求；一条用来装已经建立了连接的请求

    • 系统文件中哪里有sockets相关的信息

      1. /proc/<pid>/net/tcp 目前已经激活的饿TCP连接
      2. /proc/<pid>/fd 被程序打开的文件描述符列表
      3. /proc/<pid>/net/sockstat 当前TCP连接的概述信息

    • 当socket连接被请求时，会发生什么？

      1. socket struct 的结构以及它对于套接字的意义
      2. 内核是怎么和IO的端口文件结合起来的，
      3. 在做IO的TCP的协议的具体过程是哪些方法在哪里实现的 (内核的实现)

HTTP

协议细节

发表于 | 阅读次数:
字数统计: | 阅读时长 ≈

Golang - Read a UTF-8 text file with BOM

背景

开发中遇到一个上传文件的需求，通过规定上传的文件会将账号按行排列。 Bug复现为，当上传的文件是excel (Win)系产品导出的文件时，会在文首解析出不可显的字符，导致后端在解析时会校验错误。导致文件上传失败。

bugs

用vim -b ./file 打开文件发现了文首的不可见字符 \uFEFF。搜索后才知道这个是UTF编码自带的编码顺序标记。所以本文接下来分别介绍下，1. BOM的详细信息，2. 以及我在golang的服务中是怎么处理这种兼容的状况的。

BOM (bytes order marker)

From Wikipedia, the byte order mark (BOM) is a Unicode character used to signal the endianness (byte order) of a text file or stream. It’s code point is U+FEFF. BOM use is optional, and, if used, should appear at the start of the text stream. 引用阮一峰老师的一段话：

Unicode编码中表示字节排列顺序的那个文件头，叫做BOM（byte-order mark），FFFE和FEFF就是不同的BOM。

UTF-8文件的BOM是“EF BB BF”，但是UTF-8的字节顺序是不变的，因此这个文件头实际上不起作用。有一些编程语言是ISO-8859-1编码，所以如果用UTF-8针对这些语言编程序，就必须去掉BOM，即保存成“UTF-8—无BOM”的格式才可以，PHP语言就是这样。

big endian and little endian

对于大端模式和小端模式自己之前一直没弄明白，这里又碰见算是在熟悉一遍。再引用一遍阮老师的话做记忆：

以汉字严为例，Unicode 码是4E25，需要用两个字节存储，一个字节是4E，另一个字节是25。存储的时候，4E在前，25在后，这就是 Big endian 方式；25在前，4E在后，这是 Little endian 方式。

这两个古怪的名称来自英国作家斯威夫特的《格列佛游记》。在该书中，小人国里爆发了内战，战争起因是人们争论，吃鸡蛋时究竟是从大头(Big-endian)敲开还是从小头(Little-endian)敲开。为了这件事情，前后爆发了六次战争，一个皇帝送了命，另一个皇帝丢了王位。

第一个字节在前，就是”大头方式”（Big endian），第二个字节在前就是”小头方式”（Little endian）。

那么很自然的，就会出现一个问题：计算机怎么知道某一个文件到底采用哪一种方式编码？

Unicode 规范定义，每一个文件的最前面分别加入一个表示编码顺序的字符，这个字符的名字叫做”零宽度非换行空格”（zero width no-break space），用FEFF表示。这正好是两个字节，而且FF比FE大1。

如果一个文本文件的头两个字节是FE FF，就表示该文件采用大头方式；如果头两个字节是FF FE，就表示该文件采用小头方式。

从大头敲开，自然是先存前面字节再存后面， 从小头敲开自然是先存吃后面字节在吃前面。 这个问题又让自己重新规整了一下在操作系统中的字节序和网络通信中的字节序的不同：

  1. x86 CPU 一般都是小端字节序
  2. TCP/IP中规定采取大端字节序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
// 判断系统是大端系统还是小端系统
int main()
{
    unsigned int x = 0x12345678;

    if (*(char *)&x == 0x78)
    {
        printf("little-endian.\n");
    }
    else if (*(char *)&x == 0x12)
    {
        printf("big-endian\n");
    }
    else
    {
        printf("confused.\n");
    }

    return 0;
}

关于系统提供的主机和网络的字节序转换，留坑待填。

Golang 解决方案

我们采用的解决方案也比较的简单，就是当发现BOM时，将第一行的BOM给去掉。代码上使用了golang的strings去替换。

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
28
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)
// FEFF because this is the Unicode char represented by the UTF-8 byte order mark (EF BB BF)
func main (){
	b, err := os.Open("./src/puin.csv")

	if err != nil {
		fmt.Println(err)
		return
	}
	scanner := bufio.NewScanner(b)
	
	scanner.Scan()
	firstline := scanner.Text()
	firstline = strings.Replace(firstline, "\uFEFF", "", -1)
	fmt.Println(firstline)

	for scanner.Scan()  {
		data := scanner.Text()
		fmt.Println(data)
	}
}

当然也有一些更通用的方案在Java的生态环境。The Apache IO Commons provides some tools to handle this situation. The BOMInputStream class detects the BOM and, if required, can automatically skip it and return the subsequent byte as the first byte in the stream. 这里就不再赘述，先睡了。

参考资料

发表于 | 阅读次数:
字数统计: | 阅读时长 ≈

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

发表于 | 阅读次数:
字数统计: | 阅读时长 ≈

To the research of thermal-aware routing algorithm for optical NoC，a traffic-thermal co-simulation platform is necessary. The traditional optical NoC simulator gets the temperature distribution at first , then simulates the thermal-aware traffic activities. But more NoC simulators adopts the traffic-thermal co-simulation platform which is proposed by Shang et al.[5]. Traffic-thermal co-simulation network platform for NoC integrated the traffic of network, power model and thermal model. During the simulation, the NoC simulator do traffic activities with the adaptive routing algorithm. The power model generate the power consumption based on the traffic activites, which is a power trace file. Thermal model gets the power trace infoomation. The thermal model updates temprature dsitributions with the given power trace file. So the thermal-aware adaptive routing algorithm adjust the network traffic based on the newer temprature distributions of the optical NoC system.

We proposed a traffic-thermal co-simulation platform for the research of thermal-aware routing algorithm for optical NoC.

A Traffic-thermal Co-simulation platform

The proposed traffic-thermal co-simulaiton platform mainly consist of three parts: the optical network model, the learning based routing model and traffic-thermal co-simulation model. The optical network model is a SystemC-based cycle-accurate network simulator for optical NoC. The learning based routing model is the adaptive routing algorithm we proposed. We also implement a thraffic-thermal co-simulation platform for our optical NoC model. In our proposed work before[], we have introduced the optical network model in detail. So in this section, we will first breify introduce the structure of the learning based routing model which is adopted in the router of network. Then we will describe the structure of traffic-therml co-simulation platform.

  1. The structrue of learning based rouitng model

    We integrate the learning-based routing model in our optical NoC. When router model receive loss packets from other nodes, L-value calculator will caculate loss value based on the input loss packet and the optical thermal model. Then L-value update the corresponding the L-value in the L-Table as the algorithm which has been proposed in Section 3. When data packets is received from other nodes or processor, the Arbiter Unit will decide which port the packet go to as the input port and values in the L-Table. The arbiter unit will also send the loss packet at the same time. The whole strctrue of learning based routing model show as Figure[].

  2. The structrue of traffic-thermal co-simulation model

    The traditional simulation model computes steady temperatures in HotSpot with the power trace hased been produced before, then simulate traffic activities in the optical network model with the steady temperatures. The problem of traditioanl simulation is that the network simulator cannot update the tempeture distribution during the network simulation. Therefore, traditional simulation is unused for verifying thermal-aware designs for optical NoC. A traffic-thermal co-simulation model is more suitable for verifying thermal-aware design. The whole traffic-thermal co-simulaiton model we proposed is showed as Figure[]. The optical NoC network simulator computes a period of traffic and transfer the power trace to the tempature model. The power trace is produced by the power model of the network. Then temprature model of Hotspot update the temprature distribution of the network with the power trace. The whole co-simulaton platform forms a loop between optical network and Hotspot temperature simulation. So the co-simualtion update the temperature distribution during the network simulation. It is necessary for the research of thermal-aware designs for optical NoC.

发表于 | 阅读次数:
字数统计: | 阅读时长 ≈

协程间的通道 – 线上回滚日记(5)

  1. 概念

    通道实际上是类型化的消息队列：使得数据在协程间得以传输。

  2. 通信操作符

    1. ch <- int1 表示：用通道ch发送变量int1
    2. int2 = <- ch

  3. 默认情况下通道是同步且无缓冲的

  4. 通道阻塞

    1. 同一个通道。接受操作是阻塞的，直到发送者可用；
    2. 同一个通道，发送操作也是阻塞的，直到接受着消费了通道内的数据

发表于 | 阅读次数:
字数统计: | 阅读时长 ≈

Go中多线程(锁和sync包) — 线上回滚日记4

Go语言中是通过sync包中的mutex实现多线程的锁机制

发表于 | 阅读次数:
字数统计: | 阅读时长 ≈

regexp 包

上几节的内容中对正则有了初步的了解。只有不断的训练才会加深印象，当项目中碰到时，才可以有余力去完成项目中的挑战。

  • 简单模式： 使用Match方法便可：

    1
    ok, _ := regexp.Match(pat, []byte(searchIn))

  • 使用Compile方法，返回Regexp对像，匹配符合模式的字符串对象，指定re对象的方法

example

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
28
29
package main

import (
   "strconv"
   "regexp"
   "fmt"
)

func main() {
   SearchIn := "John: 2578.34 William: 4567.23 Steve: 5632.18"
   pat := "[0-9]+.[0-9]+"

   f := func(s string) string {
      v, _ := strconv.ParseFloat(s, 32)
      return strconv.FormatFloat(v*2, 'f', 2, 32)
   }

   if ok, _ := regexp.Match(pat, []byte(SearchIn)); ok {
      fmt.Println("Match Found!")
   }

   re, _ := regexp.Compile(pat)

   str := re.ReplaceAllString(SearchIn, "##.#")
   fmt.Println(str)
   str2 := re.ReplaceAllStringFunc(SearchIn, f)
   fmt.Println(str2)

}