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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

#include<pthread.h>
#include<inttypes.h>
#include<stdio.h>
#include<unistd.h>

#define CONSUMER_COUNT 1000
#define PRODUCTOR_COUNT 100

pthread_mutex_t mq_lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t mq_not_full_cond = PTHREAD_COND_INITIALIZER;
pthread_cond_t mq_not_empty_cond = PTHREAD_COND_INITIALIZER;

class Mq;
class QNode;

class QNode{
};

class Mq{
public:
    Mq() = default;
    Mq(uint32_t s):mq_size(s),mq_count(0){
        mq = new QNode[mq_size];
        head = 0;
        tail = 0;
    }

    void addMg(const QNode& n){
        pthread_mutex_lock(&mq_lock); 
        while(mq_count == mq_size){
            pthread_cond_wait(&mq_not_full_cond,&mq_lock); 
        }
        mq[tail++] = n;
        if(tail >= mq_size) tail = 0;
        printf("add a product \n");
        if(mq_count++ >= 0) pthread_cond_signal(&mq_not_empty_cond);
        pthread_mutex_unlock(&mq_lock);
    }
    
    QNode takeMg(){
        QNode result;
        pthread_mutex_lock(&mq_lock);
        while(!mq_count){
            pthread_cond_wait(&mq_not_empty_cond,&mq_lock);
        }
        result = mq[head++];
        if(head >= mq_size) head = 0;
        printf("take a product \n");
        if(mq_count-- <= mq_size) pthread_cond_signal(&mq_not_full_cond);
        pthread_mutex_unlock(&mq_lock);
        return result;
    }
private:
    uint32_t mq_size;
    uint32_t mq_count;
    QNode* mq;
    uint32_t head;
    uint32_t tail;
};


void* product(void* arg){
    Mq& mq = *(Mq*)arg;
    for(int i = 0;i < 1000;i++){
        mq.addMg(QNode());
    }
    return NULL;
} 

void* consume(void* arg){
    Mq& mq = *(Mq*)arg;
    for(int i = 0;i < 100;i++){
        QNode node = mq.takeMg();
    }
    return NULL;
}

Mq mq(100);

int main(){
    pthread_t productor[PRODUCTOR_COUNT];
    pthread_t consumer[CONSUMER_COUNT];

    for(int i = 0;i < PRODUCTOR_COUNT;i++){
        pthread_create(productor+i,NULL,product,(void*)(&mq)); 
    }
    for(int i = 0;i < CONSUMER_COUNT;i++){
        pthread_create(consumer+i,NULL,consume,(void*)(&mq));
    }

    for(int i = 0;i < CONSUMER_COUNT;i++){
        pthread_join(consumer[i],NULL);
    }
    for(int i = 0;i < PRODUCTOR_COUNT;i++){
        pthread_join(productor[i],NULL);
    }

}

这是一个简单的消息队列，开启多个生产者多个消费者线程使用该消息队列，使用互斥锁和条件变量进行同步。以上是通过测试的最终版本，在实际写的过程中遇到了一些小问题。

1
2
3
4
5
6
7

//takeMg
if(mq_count-- <= mq_size) pthread_cond_signal(&mq_not_full_cond);//最终版
if(mq_count-- == mq_size) pthread_cond_signal(&mq_not_full_cond);//有问题

//addMg
if(mq_count++ >= 0) pthread_cond_signal(&mq_not_empty_cond);//最终版
if(mq_count++ == 0) pthread_cond_signal(&mq_not_empty_cond);//有问题

以上是错误代码和最终代码的对比。可以看到，仅仅是修改了比较符，但影响很大。

在刚开始，写有问题的那段代码时，我是这样想的，需要把非空条件的集合唤醒，说明当前肯定是空变为非空了。比方说A、B都在等待非空条件，C投入一个资源，队列由空变为非空，唤醒A、B中的一个，比如说A。然后A拿走资源，队列再次变为空。C再投入一个资源，发现队列又由空变为非空，再次唤醒B。

似乎运行的很好。但是问题在于pthread_cond_signal的含义，由于我们是在锁内唤醒，即使唤醒也不能立刻拿到锁。所以pthread_cond_signal的含义是把线程从等待条件队列中移到等待互斥锁的队列里，并不是意味着唤醒就代表着它会是下一个拿到锁的线程，还是得经过在互斥锁队列里的竞争。

所以在刚才的步骤里就可能出现这种情况，C投入资源唤醒了A，A加入互斥锁队列，C再一次抢到了锁，这次因为资源数由1变为2，所以没有唤醒过程，如果C不再投入资源，那么B将永远醒不过来，一直在条件队列里。这也是我在实验的时候，程序一直停不下来。

JOS总结

操作系统的启动

BIOS

机器在启动时，首先运行BIOS，负责初始化中断向量，以及对设备进行检查。随后将boot loader程序加载到0x7c00处，boot loader在磁盘的第一个扇区。

Boot Loader

在加载进内存后，跳转到boot loader执行，boot loader主要负责对内核的引导。

在执行boot loader代码时，首先初始化一些寄存器，包括ds，es，ss等等，然后设置代码段选择子和数据段选择子，接着调用 lgdt gdtdesc加载全局描述符表，这时cpu还处于实模式状态，只能访问1MB以下的内存，这时boot loader需要开启保护模式以访问高地址内存，调用lcr0 开启保护模式。然后调转到 PROT_MODE_CSEG： protcseg执行。注意这时的PROT_MODE_CSEG为0，也就是说，内核的加载地址即是实际地址。

protcseg处的代码便是读入内核的ELF文件，将ELF头读入地址0处，根据ELF头，将相应内核段读入相应的地址。在加载完成后，跳转至e_entry执行内核代码。

需要牢记的是，在代码中的地址我们称之为虚拟地址或链接地址，在开启了保护模式后(设置cr0的低位为1)，会经过全局描述符表项来生成线性地址，如果开启了分页(设置cr3的低位为1)，则会将线性地址经过分页转换为物理地址，否则，线性地址就等于物理地址。

此时我们只是开启了保护模式，但是并没有开启分页。所以在内核的开始部分，第一件事就是开启分页，将初始的页目录加载进cr3，这个初始的页目录很简单，单纯的将[KERNBASE，KERNBASE+4MB]映射到[0，4MB]，开启分页后，在访问地址时会经过CPU中MMU的转换，并会对权限进行检测。

到这里，boot loader工作就全部结束了，剩下的就是把控制权转交给内核，并对其他的操作系统组件进行初始化。

内存管理

这是我们目前的物理内存分布。

此时，我们的虚拟内存只是简单的映射了KERNBASE开始的4MB空间，我们需要对内存做更多的管理。

首先，不管虚拟内存怎样映射，我们首先需要对物理内存做管理，关于物理内存怎样分配，物理内存分配情况的记录等等。

JOS里面用struct PageInfo来记录物理页的分配情况

1
2
3
4

struct PageInfo{
  	struct PageInfo* pp_link;
  	int pp_ref;
};

其中，pp_link记录着上一页可用页面的地址，pp_ref则记录着该物理页面被多少虚拟页映射。通过这个结构便可以很容易的维护物理页信息。分配时将空闲页从链表中剔除，释放时嵌入链表。

现在我们的虚拟内存表还过于简单，我们需要做更复杂的映射。

这是我们虚拟内存的布局，我们需要完成部分的映射。

首先是[UPAGES，UPAGES+PTSIZE]映射到我们的pages管理部分，也就是一系列PageInfo结构。

然后是映射[KERNTOP-KSTKSIZE，KSTACKTOP]到[bootstack，bootstack+32KB]处。

再然后将[KERNBASE，KERNBASE+256MB]映射到[0，256MB处]，这样也覆盖了之前的简单映射部分（向后兼容？）

映射完后，将cr3寄存器的值换成新的目录表地址。

（疑问，bootstack具体地址？vupt映射）

进程管理

类似于struct PageInfo记录物理页信息，用Env来记录进程信息。

1
2
3
4
5
6
7
8
9
10
11
12

struct Env {
    struct Trapframe env_tf;    // Saved registers
    struct Env *env_link;       // Next free Env
    envid_t env_id;         // Unique environment identifier
    envid_t env_parent_id;      // env_id of this env's parent
    enum EnvType env_type;      // Indicates special system environments
    unsigned env_status;        // Status of the environment
    uint32_t env_runs;      // Number of times environment has run

    // Address space
    pde_t *env_pgdir;       // Kernel virtual address of page dir
};

首先需要对PCB表进行内存分配，这个表的大小决定了进程的数目，表里存放的也是Env信息，这些信息都是由内核进行管理，所以访问权限是用户只读。

之前的gdt表里只有内核数据段和内核代码段（虽然基地址都是0），现在多了用户进程，需要为用户环境段分配相应的gdt描述符。于是多了用户数据段和用户代码段。然后加载新的描述符表。

（在jos里，段基地址都是0，只是权限不同）

这些初始化工作完成后，就可以正式创建进程了。

创建进程调用env_create函数，先调用env_alloc为进程分配Env结构并初始化相应信息，然后为进程创建页表，该页表拷贝kern_dir，将UVPT重新映射到自己的页表。env_tf表示进程运行时的寄存器信息，我们在创建进程时也需要初始化这些信息。初始化完成后，就可以等待调度了，因为运行时的一些必要信息已经准备好了。

调用env_run()运行进程，下面是env_run()的代码

1
2
3
4
5
6
7
8
9
10
11
12

void
env_run(struct Env *e)
{
    if(curenv && curenv->env_status == ENV_RUNNING)
    		curenv->env_status = ENV_RUNNABLE;
    curenv = e;
    e->env_status = ENV_RUNNING;
    e->env_runs++;
    lcr3(PADDR(e->env_pgdir));
    unlock_kernel();
    env_pop_tf(&e->env_tf);
}

env_pop_tf()将进程保存的环境复原，开始运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void
env_pop_tf(struct Trapframe *tf)
{
	// Record the CPU we are running on for user-space debugging
	curenv->env_cpunum = cpunum();

	asm volatile(
		"\tmovl %0,%%esp\n"
		"\tpopal\n"
		"\tpopl %%es\n"
		"\tpopl %%ds\n"
		"\taddl $0x8,%%esp\n" /* skip tf_trapno and tf_errcode */
		"\tiret\n"
		: : "g" (tf) : "memory");
	panic("iret failed");  /* mostly to placate the compiler */
}

关于优先级

优先级有三种存在方式，分别是CPL、RPL、DPL。CPL是当前的优先级，由当前的cs段的最后三位体现。RPL是请求权限，在用户环境中，RPL和CPL相同。但是因为请求资源切换到内核环境，就会不一样。这是为了防止用户进程在通过内核请求资源时，访问到本不属于它的资源。DPL很好理解，就是某段的访问级别，存在于描述符中。

中断

到目前为止，我们都没有一个有效的办法来暂停一个进程，我们需要Unix中类似中断、trap等机制来实现异常的控制流。

中断和异常都是”保护控制机制”（PCT），它们将处理器从用户模式转移到内核模式。在CSAPP中叫做异常控制流，有4种，分别是中断、陷阱（trap）、异常、终止。其中中断是异步的，随时都可能发生，而其他的则是当前指令引发的。

trap执行完处理程序后，执行的是下一条指令，异常执行完处理程序后返回的是发生异常的指令。

中断描述表存储有中断向量和中断门描述符，中断描述表的地址存储在IDT寄存器中。当发生中断时，由IDT找到中断描述表，再根据中断向量作为索引找到中断门描述符，描述符中存有处理程序的选择子和DPL，再由处理程序的选择子在GDT中找到具体处理程序地址。

x86使用0-31号作为处理器内部的同步异常，像除零异常、缺页异常等。使用32号之上的中断号用于软件中断或硬件中断。

在中断跳转到中断处理程序前，我们需要保存运行环境，并且这部分不能被用户代码访问到。当遇到异常时，经过中断门后，特权级由用户级变为内核级，这个过程中会将用户栈切换为内核栈，内核栈的位置由TSS来存储，切换到内核栈后，会在内核栈中压入发生中断时的寄存器信息，像esp、ss、cs、eip、eflags等等，(如果中断处理程序需要，可能还要压入些额外信息，比如页异常需要压入error code。)然后将中断处理程序的cs、eip加载进寄存器中，开始运行处理程序。

（疑问：内核栈中压入的值是什么时候出栈的；内核态转变为用户态的时机）

内核栈中的值不见得弹出，下次直接被覆盖就好了

内核态在调用iret后转变为用户态

系统调用

用户特权级下，需要通过系统调用来访问内核资源。系统调用把参数存在通用寄存器里，然后通过int SYS_CALL软中断被中断处理程序处理，并成功进入内核环境。中断处理程序根据保存的寄存器信息提取出系统调用的参数，包括系统调用号，参数等等。并将返回值保存在待恢复寄存器信息中的eax中。

SMP

SMP指所有处理器都是平等的，包括内存平等和IO平等。虽然所有处理器都是平等的，但是可以分为BSP和AP，前者用于系统的boot过程以及初始化各个AP，至于哪个cpu是BSP的信息以及其他的关于SMP的配置信息都放在BIOS中。

每个cpu都有一个LAPIC单元，用于传递和相应中断，LAPIC为与它相连的cpu提供了唯一ID。我们只使用到了LAPIC的部分功能，读取LAPIC判断当前cpu ID；从BSP发送IPI给AP，用于初始化AP；用内置的计时器来支持抢占式多任务。

cpu访问它的LAPIC通过MMIO，有部分内存连线硬连接到LAPIC。我们将这部分物理地址映射到0xEF800000开始的4MB

AP启动流程

在启动AP前，BSP需要从BIOS中读取有关于多处理器的配置信息，比如说cpu的数目，LAPIC的MMIO地址等等。调用boot_aps()来初始化AP，AP以实模式启动，类似于boot过程，区别是我们的BSP可以控制AP执行代码的加载地址。在我们实验里，我们将其加载至0x7000处。

之后，boot_aps()向各个AP发送STARTUP IPIs来依次激活各个cpu，并为每个cpu指定了内核栈，cpu通过执行0x7000处的初始化代码完成初始化，包括启动保护模式，开启分页，加载gdt等等，并依次调用lapic_init()，env_init_percpu()，trap_init_percpu()完成初始化工作，完成后向BSP发送完成初始化的信号。

CPU初始化

• 内核栈。每个cpu都有一个内核栈，以保证互不干扰。
• TSS和TSS描述符。TSS用于保存内核栈DS、ESP，TSS的段选择子在cpus[i].cpu_ts中，通过段选择子在gdt中可找到TSS。
• 当前进程指针。每个cpu都保存着当前运行的进程Env
• 所有寄存器。寄存器在每个cpu上都有一份

内核锁

为了防止多CPU同时执行内核代码对内核数据产生影戏那个，我们必须保证每次只有一个cpu运行在内核环境。我们采用内核锁的方式，保证最多只有一个CPU处在内核状态。

调度

在多CPU环境配置好后，我们需要对进程进行调度，用户进程可以通过系统调用主动让出cpu，在释放进程时会进行调度，在进程调用ipc_recv时也会进行调度，在trap中，发现中断进程已经终止时也会进行调度。

Fork

我们现在有了基本的进程模型，还需要类似于Unix中的fork机制来完成更复杂的任务。我们可以先设计一个简单的fork模型，用户通过系统调用进入内核空间，内核通过拷贝进程的内存空间完成复制，并通过将子进程的tf->eax设置为0达到一次调用、两次返回的效果。

但是我们可以看到，对于父进程内存空间的复制，进行全部的拷贝，这是一种浪费，因为父子进程内存大部分都是相同的。考虑到这点，我们采用一种叫做写时复制的技术。

写时复制是说fork后，父子进程共享相同的物理内存，并给相应的虚拟页面写上COW标志，当某一方试图写共享页面时，就会触发页异常，调用相应的异常处理程序，将发生写异常的页面拷贝一份。

页面异常处理程序和中断过程有点区别，在发生页面异常后，先是触发异常中断，将寄存器值压入内核栈中，而后dispatch发现是页面中断，于是把压入内核栈的数据压入异常栈，并设置用户进程的eip为用户级的处理程序，继而调用env_run转变为用户级并运行页面处理程序，在处理完后，从异常栈中恢复寄存器的数据。也就是说真正的处理过程实际上是在用户环境执行的。

IPC

jos的IPC有几种，首先是基于系统调用sys_page_map，将进程A的页面映射到进程B的某页，实现页面的共享。还有一种是ipc_recv和ipc_try_send，ipc_recv系统调用告诉内核，我想收到数据，并且把数据放在哪个地址，然后就重新调度，等待其资源准备好。ipc_try_send系统调用向目标进程发送数据，如果目标进程没准备好收，返回错误信息。否则把数据送到目标进程，并且把目标进程设置为可运行。最后一种是文件系统中即将介绍的pipe，也是基于sys_page_map的原理。

文件系统

文件系统在磁盘上的存储有如下几个部分，超级块、位图、Inode、实际文件内容。其中超级块用于描述文件系统根目录的元信息，位图记录磁盘的分配情况，Inode是描述文件的元信息。但是jos里面没有将Inode和实际文件内容分开，而是将文件的元信息存在所在目录的目录项里。简化了很多。

jos的文件系统还有一个特别之处在于对于文件的管理是由一个特殊的进程来完成的，关于底层对磁盘的读写不用了解太多（主要是我也不懂），抽象出来就是，这个特殊的文件管理进程可以读出某一磁盘块的内容，它读出的内容映射在它自己的虚拟内存里面，从0x10000000～0xD0000000，正好3G，也就是说jos支持的最大磁盘也就是3G。

接下来介绍几个关键的数据结构

1
2
3
4
5
6
7
8
9
10

struct File{
  char f_name[MAXNAMELEN];	// filename
	off_t f_size;			// file size in bytes
	uint32_t f_type;		// file type

	// Block pointers.
	// A block is allocated iff its value is != 0.
	uint32_t f_direct[NDIRECT];	// direct blocks
	uint32_t f_indirect;		// indirect block
};

File用于记录文件的信息，算是基于磁盘块的一层抽象。通过它可以知道一个文件的基本信息，比如说文件名、大小、具体在哪几个块里。

我们可以把文件系统找文件的过程分为如下几步：

1. 从Super块开始，根据目录名和待查询文件名的比对，一层层往下
2. 找到期待的文件后，保存File信息，通过File就可以很容易读出文件对应的块了

1
2
3
4
5
6
7
8

struct Fd{
  int fd_dev_id;
  off_t fd_offset;
  int fd_omode;
  union{
    struct FdFile fd_file;
  }
};

Fd用于描述打开文件，文件对应的设备ID，当前的偏移量，打开方式，文件id等等。从普通进程的0xD0000000开始，有一段空间用于保存Fd，最多可达32个。

1
2
3
4
5
6

struct OpenFile{
  uint32_t o_fileid;
  struct File* o_file;
  int o_mode;
  struct Fd* o_fd;
};

OpenFile将File和Fd联系起来，通过o_fileid可以得到OpenFile数组的下标，这个值保存在Fd的fd_file中。因此，当我们在普通用户程序中通过Fd读文件时，可以通过fd_file在文件管理进程中找到对应的OpenFile结构，然后通过OpenFile里的File结构完成实际文件操作。

在普通进程和文件管理进程中各有一个fsipc结构，用于传递打开文件的信息。

我们来看看具体的流程

打开文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 Regular env           FS env
   +---------------+   +---------------+
   |      open     |   |   file_read   |
   |   (lib/fd.c)  |   |   (fs/fs.c)   |
...|.......|.......|...|.......^.......|...............
   |       |       |   |       |       | RPC mechanism
   |       |       |   |  serve_open   |
   |       |       |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |     fsipc     |   |     serve     |
   |  (lib/file.c) |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |   ipc_send    |   |   ipc_recv    |
   |       |       |   |       ^       |
   +-------|-------+   +-------|-------+
           |                   |
           +-------------------+

读取文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 Regular env           FS env
   +---------------+   +---------------+
   |      read     |   |   file_read   |
   |   (lib/fd.c)  |   |   (fs/fs.c)   |
...|.......|.......|...|.......^.......|...............
   |       v       |   |       |       | RPC mechanism
   |  devfile_read |   |  serve_read   |
   |  (lib/file.c) |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |     fsipc     |   |     serve     |
   |  (lib/file.c) |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |   ipc_send    |   |   ipc_recv    |
   |       |       |   |       ^       |
   +-------|-------+   +-------|-------+
           |                   |
           +-------------------+

可以看到的是，用户通过调用read，执行实际操作的是对应的设备文件，因为不同类型的文件对用户而言都是相同的（Fd），但是实际read却有区别。比如对管道文件的读和对普通文件的读肯定不一样。这种区别由不同的设备文件来体现。devfile_read把请求读取的文件的信息保存在fsipc中，通过ipc向Fs serv请求数据，fs serv一直在等待请求到来，在读到请求后，根据请求返还对应的文件内容，通过ipc的方式写回。

Spawning进程

spawning用于创建子进程，有点类似于Unix中的fork+exec过程，但是有点区别，因为我们的spawning过程运行在用户空间。

在fork和spawning中，父子进程需要共享文件描述符，之前的COW字段并不能满足要求，我们需要的是共享。

Spawning的流程如下：

1. 打开文件，获取文件描述符Fd
2. 读取ELF文件
3. 调用fork创建子进程
4. 设置child_tf，设置子进程eip为elf文件的入口点e_entry，设置esp为init_stack分配的栈空间
5. 将ELF文件映射到子进程地址空间，并根据ELF来设置访问权限
6. 拷贝共享的页
7. 调用sys_env_set_trapframe()设置子进程的env_tf位child_tf。
8. 调用 sys_env_set_status() 设置子进程为RUNNABLE状态。

pipe

pipe过程很简单，分配两个描述符，每个描述符会携带对应的数据区，将两个描述符的数据区映射到同一段物理内存，该段内存保存有r_offset、w_offset以及实际数据。也就是说pipe虽然和文件相关，但是并不涉及到实际的文件。

信号

常见信号

• SIGABRT：异常终止，默认动作：终止+core.
• SIGALRM：定时器超时，终止
• SIGCHLD：子进程状态改变，忽略
• SIGINT：终端中断符，终止
• SIGKILL：终止，终止
• SIGPIPE：写至无读进程的管道，终止
• SIGQUIT：中断推出符，终止+core
• SIGSTOP：停止，停止进程
• SIGTERM：终止，终止

值得注意的是，我们可以为很多信号编写自己的信号处理函数，但是对于SIGSTOP和SIGKILL，它们既不能被捕捉也不能被忽略。

几种终止信号的比较

SIGINT：当用户按中断键，终端驱动程序产生此信号并发送到前台进程组中每一个进程。

SIGABRT：调用abort产生此信号，进程异常终止。

SIGKILL：不能被忽略或捕捉的信号，杀死一个进程可靠的方法。

SIGQUIT：相比于SIGINT，同时产生一个core文件。

SIGTERM：kill命令的默认终止信号。SIGTERM让程序有机会在推出前做好清理工作，从而优雅的终止。

SIGSTOP：作业控制信号，停止一个进程，类似于交互停止信号。不能被忽略或捕捉。

常用Api

1
2
3

#include<signal.h>
void (*signal(int signo, void (*func)(int)))(int);
				//返回值：若成功，返回以前的信号处理配置；若出错，返回SIG_ERR.

1
2
3
4

#include<signal.h>
int kill(pid_t pid, int signo);
int raise(int signo);
				//返回值：若成功，返回0；若出错，返回-1.

raise(signo)等价于调用kill(getpid(),signo)

进程将信号发送给其他进程需要权限，超级用户可以将信号发送给任一进程。对于非超级用户，基本规则是发送者的实际用户ID或有效用户ID必须等于接收者的实际用户ID或有效用户ID。(谁登录，执行进程的实际ID就是谁)

1
2
3

#include<unistd.h>
unsigned int alarm(unsigned int seconds);
				//返回：0或以前设置过的闹钟时间的余留时间。

每个进程只能有一个闹钟时间，以前注册的时间将作为新闹钟的返回值返回。如果seconds为0，相当于取消以前的闹钟。alarm的默认动作是终止进程，我们必须在alarm之前安装处理程序，不然可能出现意外情况。

1
2
3

#include<unistd.h>
int pause(void);
				//返回：-1，errno设置为EINTR

只有执行了信号处理程序并从其返回时，pause才返回。

1
2
3
4
5
6
7
8

#include<signal.h>
int sigemptyset(sigset_t *set);
int sigfillset(sigset_t *set);
int sigaddset(sigset_t *set);
int sigdelset(sigset_t *set, int signo);
				//返回：若成功，返回0；若出错，返回-1
int sigismember(const sigset_t *set, int signo);
				//返回：若真，返回1；若假，返回0

1
2
3

#include<signal.h>
int sigprocmask(int how, const sigset_t *set, sigset_t *oset);
				//返回值：若成功，返回0，若出错，返回-1.

how是可选的选项，包括SIG_BLOCK，SIG_UNBLOCK，SIG_SETMASK。注意：不能阻塞SIGKILL和SIGSTOP信号。

1
2
3

#include<signal.h>
int sigpending(sigset_t *set);
				//返回值：若成功，返回0，若出错，返回-1.

sigpending返回当前未决的信号。

1
2
3
4
5
6
7
8
9
10

#include<signal.h>
int sigaction(int signo, const struct sigaction *act, struct sigaction *oact);
				//返回值：若成功，返回0；若出错，返回-1.

struct sigaction{
    void (*sa_handler)(int); //addr of signal handler.
    sigset_t sa_mask;//additional signals to block
    int sa_flags;//signal options, 
    void (*sa_sigaction)(int,siginfo_t *,void *);//alternate handler.
};

在信号处理期间将sa_mask加入阻塞集，在调用完后恢复。若同一个信号发生多次，通常不会将它们加入队列，被阻塞的信号发生多次，在恢复后通常只会被调用一次。sa_flags能决定对于信号中断的系统调用是否重启，通过设置SA_INTERRUPT或SA_RESTART.

1
2
3
4

#include<setjmp.h>
int sigsetjmp(sigjmp_buf env, int savemask);
				//返回值：若直接调用，返回0；若从siglongjmp调用返回，则返回非0.
void siglongjmp(sigjmp_buf env, int val);

之所以增加对于信号的跳转函数的特殊处理，是因为在信号处理函数里的屏蔽信号跟进程环境是有区别的。当savemask非0，则调用sigsetjmp时在env中保存当前信号屏蔽字。在siglongjmp后恢复。

1
2
3

#include<signal.h>
int sigsuspend(const sigset_t *sigmask);
				//返回值：-1，并将errno设置为EINTR

这个函数是为了表达进入休眠，期待被期望的信号唤醒的语义。假想在没有该函数时，我们该如何实现。为期待的信号设置阻塞，然后解除阻塞后紧接着调用pause()?那要是确实有期待的信号被阻塞了，但是在接触阻塞后，调用pause前解除了，可能就存在永远唤不醒的情况。

进程的信号屏蔽字设置为由sigmask指向的值。如果捕捉到一个信号而且从信号处理程序返回，则sigsuspend返回，并恢复原来的屏蔽字。

1
2

#include<stdlib.h>
void abort(void);

调用此函数将给进程发送一个SIGABRT信号。让进程捕捉SIGABRT意图是：在进程终止之前由其执行所需的清理操作。如果进程不在信号处理程序中终止自己，POSIX对此的要求是当信号处理程序返回时，abort终止该进程。POSIX对终止进程提出的要求是，所有打开的标准流应当与对每个流调用fclose相同。

1
2
3

#include<unistd.h>
unsigned int sleep(unsigned int seconds);
				//返回值：0或未休眠完的秒数。

函数使进程被挂起直到满足下列两个条件之一：

• 过了seconds指定的时间。
• 调用进程捕捉到了一个信号并从信号处理程序返回。

有关信号的一些小内容

可重入函数

​ 我对信号处理函数的理解是像线程一样，它和主线程是共享全局环境的。因此在信号处理函数中调用可重入函数就显得很重要。函数的不可重入性往往是因为如下原因a)使用静态数据结构；b)调用malloc或free；c)它们是标准I/O函数，标准I/O库很多都使用全局数据结构。

​ 信号处理函数虽然像线程，但是线程保存着errno的副本，互不干扰。但信号处理函数不一样，因此，我们在调用一些系统函数时，需要先保存errno值，在调用完后恢复。

SIGCLD语义

​ SIGCLD和SIGCHLD不一样，前者时System V的信号名，与POSIX采用的SIGCHLD不同。System V的该信号有如下特点。

1. 如果进程明确将信号配置为SIG_IGN，则调用进程的子进程不产生将死进程。
2. 如果SIGCLD被设置为捕捉，则内核会立即检查是否有子进程准备好。如果是，调用SIGCLD。

可靠信号语义

​ 当一个信号产生时，内核通常在进程表中以某种形式设置一个标志。在信号产生和递送之间的时间间隔里，信号是未决的。内核在将信号递给进程时，才决定处理方式，在此之前可以任意修改对此信号的处理动作。在进程解除对某个信号的阻塞前，这种信号发生多次，Posix允许递送信号一次或多次。除非支持Posix实时扩展，否则大多数UNIX不对信号排队，只递送信号一次。

IPC

1. 匿名管道

1
2
3

#include<unistd.h>
int pipe(int fd[2]);
		//返回：若成功则为0，若失败返回-1

匿名管道仅能用于存在关系的进程间，并且匿名管道是半双工的，也就是说数据在管道的流动是单向的。当需要两个双向数据流时，必须创建两个管道。并且匿名管道是随进程持续的，也就是说当进程结束时，这种形式的IPC结构便不再存在，这有别于我们后面介绍的其他的IPC结构。

标准I/O函数库提供了popen函数，它创建一个管道并启动另一个进程，该进程要么从该管道读出标准输入，要么往该管道写入标准输入。

1
2
3
4
5

#include<stdio.h>
FILE *popen(const char *command,const char *type);
			//返回：若成功则为文件指针，若出错则为NULL
int pclose(FILE *stream);
			//返回：若成功则为shell的终止状态，若出错则为-1

其中command时一个shell命令行。由sh程序处理，因此PATH环境变量可用于定位该command。popen在调用进程和所指定的命令之间创建一个管道。由popen返回的值是一个标准I/O FILE的指针，该指针可理解为对调用进程关心的管道一端。比方说当命令是cat /etc/shadow，type是“r”，意味着子进程将执行该命令，并将结果写进管道。对于父进程也就是调用进程来说，它能通过读管道的另一端得到这些结果，而这个所谓的管道另一端就是返回的FILE*.

而pclose则关闭由popen创建的标准I/O流，等待其中命令终止，然后返回shell的最终状态。

后面将会在github上具体实现这两个函数。

2. 命名管道(FIFO)

我们可以看到，匿名管道没有名字，因此它们只能用于有一个公共祖先进程的各个进程之间。无法在无亲缘关系的两个进程间创建一个管道。

FIFO指代先进先出，类似于管道，它也是一个单向的数据流。不同于管道的是，每个FIFO有一个路径名相关联，类似于一个文件，从而允许不相关进程访问同一个FIFO。

1
2
3
4
5

#include<sys/types.h>
#include<sys/stat.h>

int mkfifo(const char *pathname, mode_t mode);
			//返回：若成功则为0，若出错则为-1

pathname是普通的Unix路径名，是该FIFO的名字。mode参数指定文件权限位，类似于open的参数。

mkfifo函数已隐含指定O_CREATE|O_EXCL。也就是说要么创建一个新的FIFO，要么返回一个EEXIST错误。

对于FIFO的打开或者读或者写，不能既读又写，因为它是半双工的。对FIFO的写总是往末尾添加数据，对它们的读总是从开头返回数据。对FIFO调用lseek将返回ESPIPE错误。

管道在所有进程最终都关闭它之后自动消失。FIFO的名字则只有通过调用unlink才从文件系统删除。内核为管道和FIFO维护了引用计数器，它是访问同一个描述符的个数。这种引用计数器的存在有一个性质，假设在还存在进程引用该文件时，调用unlink删除该文件，不会对现在还在使用该文件的进程造成影响，对文件的删除将推迟到引用计数器为0的时刻。这有别于System V对于部分IPC方式的处理。

值得注意的是，默认情况下，对于FIFO的读(写)打开会阻塞到有写(读)的打开。倘若对于一个没有读者的FIFO写，会长生SIGPIPE信号。对于没有写着的FIFO读会检查可用数据量，只返回可用数据。另外，对于管道的写(包括匿名管道和FIFO)在一次写入内容小于PIPE_BUF时会保证原子性。因此，在以非阻塞的方式向管道中写小于PIPE_BUF的数据时，倘若空间不够，为了保证原子性则会以错误的形式告诉进程以后再试，不会存在部分写情况。有别于我们习惯理解的非阻塞写。倘若大于PIPE_BUF，这时原子性本就得不到保证，所以进程会写入能容纳的数据。

3. POSIX 消息队列

消息队列可以认为是一个消息链表。有足够写权限的线程可以往队列中放置消息，有足够读权限的线程可以从队列中取走消息。每个消息就是一个记录(有点类似于UDP数据报，有边界)。由发送者赋予优先级。在某个进程往队列中写入消息前，不需要另外某个进程在该队列上等待消息。

消息队列具有内核的持续性，也就是说在不显示删除的情况下，即使当前唯一进程退出后，在后续仍然可以由其他进程读入该队列的消息。

mq_open函数创建一个新的消息队列或打开一个已存在的消息队列。

1
2
3

#include<mqueue.h>
mqd_t mq_open(const char *name, int oflag, /*mode_t mode, struct mq_attr *attr */);
			//返回：若成功则为消息队列描述符，若出错则为-1.

已打开的消息队列由mq_close关闭。关闭不等于删除。

1
2
3

#include<mqueue.h>
int mq_close(mqd_t mqdes);
			//返回：若成功则为0，若出错则为-1

要从系统中删除用作mq_open第一个参数的某个name，必须调用mq_unlink。

1
2
3

#include<mqueue.h>
int mq_unlink(const char *name);
			//返回，若成功则为0，若出错则为-1

正如前面谈到过的引用计数，每个消息队列有一个保存其当前打开着描述符数的引用计数器(有点像文件)，因而本函数能够实现类似于unlink函数删除一个文件的机制：当一个消息队列的引用计数仍大于0时，其name就能删除，但该队列的析构要到最后一个mq_close发生时才进行。

1
2
3
4
5
6
7
8
9
10
11

struct mq_attr{
    long mq_flags; /* message queue flag: 0, O_NONBLOCK */
    long mq_maxmsg; /* max number of messages allowed on queue */
    long mq_msgsize; /* max size of a message (in bytes) */
    long mq_curmsgs; /* number of messages currently on queue */
};

#include<mqueue.h>
int mq_getattr(mqd_t mqdes, struct mq_attr *attr);
int mq_setattr(mqd_t mqdes, const struct mq_attr *attr, struct mq_attr *oattr);
			//返回：若成功则为0，若出错则为-1

mq_setattr只能设置mq_flags，其他参数需在创建时指定。

下面两个函数用于放置消息和取走消息。每个消息有个优先级，小于MQ_PRIO_MAX的无符号整数。

1
2
3
4
5

#include<mqueue.h>
int mq_send(mqd_t mqdts, const char *ptr, size_t len, unsigned int prio);
			//返回：若成功则为0，若出错则为-1
ssize_t mq_receive(mqd_t mqdes, char *ptr, size_t len, unsigned int *priop);
			//返回：若成功则为消息字节数，若出错则为-1

4. POSIX 信号量

信号量是一种用于提供不同进程间或一个给定进程的不同线程间同步手段的原语。POSIX信号量有两种。

• POSIX有名信号量：使用POSIX IPC名字进行标识，可用于进程或线程间的同步。
• POSIX基于内存的信号量：存放在共享内存区中，可用于进程或线程间的同步。

POSIX的有名信号量是由可能与文件系统中的路径对应的名字来标识的，但是并不要求它们真正存放在文件系统内的某个文件中。

函数sem_open创建一个新的有名信号量或打开一个已存在的有名信号量。有名信号量总是既可用于线程间同步，又可用于进程间的同步。

1
2
3

#include<semaphore.h>
sem_t *sem_open(const char *name, int oflag, /* mode_t mode, unsigned int value */);
			//返回：若成功则为指向信号量的指针，若出错则为SEM_FAILED

使用sem_open打开的有名信号量，使用sem_close将其关闭。

1
2

#include<semaphore.h>
int sem_close(sem_t *sem);

Posix有名信号量是内核持续的，即使当前没有进程打开着某个信号量，它的值仍然保持。

有名信号量使用sem_unlink从系统中删除。

1
2
3

#include<semaphore.h>
int sem_unlink(const char *name);
			//返回：若成功则为0，若出错则为-1

类似于消息队列中的操作，不再赘述。

sem_wait函数测试所指定信号量的值，如果该值大于0，那就将它减1并立即返回。如果该值等于0，调用线程就被投入睡眠，直到该值变为大于0.

1
2
3
4

#include<semaphore.h>
int sem_wait(sem_t *sem);
int sem_trywait(sem_t *sem);
			//返回：若成功则为0，若出错则为-1

sem_trywait于sem_wait可以类比为非阻塞read于阻塞read。如果被某个信号中断，sem_wait可能过早返回，返回错误为EINTR。

当线程使用完某个信号量时，调用sem_post。把指定信号量值加1，然后唤醒正在等待该信号量变为正数的任意线程。

1
2
3
4

#include<semaphore.h>
int sem_post(sem_t *sem);
int sem_getvalue(sem_t *sem, int *valp);
			//返回：若成功则为0，若出错则为-1

sem_getvalue在由valp指向的整数中返回所指定信号量的当前值。如果该信号量当前已上锁，那么返回值或为0，或为某个负数，其绝对值为等待该信号量解锁的线程数。

前面提到的是Posix有名信号量。这些信号量由一个name参数标识，它通常指代文件系统中的某个文件。Posix也提供基于内存的信号量，它们由应用程序分配信号量的内存空间，然后由系统初始化它们的值。可以这样理解，信号量作为一种控制进程间同步的机制，它需要的是一种全局的环境。这种于所有进程的全局环境可以是文件系统，也可以是进程共享的内存。前者是有名信号量，后者是基于内存信号量。

1
2
3
4
5

#include<semaphore.h>
int sem_init(sem_t *sem, int shared, unsigned int value);
			//返回：若出错则为-1
int sem_destroy(sem_t *sem);
			//返回：若成功则为0，若出错则为-1

如果shared为0，那么待初始化的信号量是在同一进程的各个线程间共享的，否则该信号量在进程间共享。基于内存的信号量至少具有随进程的持续性，真正的持续性取决于存放信号量的内存区类型。只要含有某个基于内存信号量的内存区有效，信号量就一直存在。

1
2

Destroying a semaphore that other processes or threads are currently blocked on produces undefined behavior.
Using a semaphore that has been destroyed produces undefined results, until the semaphore has been reinitialized using sem_init(3).

补充：生产者与消费者(多个)，其他方式的同步方式，多个缓冲区。

5. 共享内存区

共享内存区是可用IPC形式中最快的。一旦这样的内存区映射到共享它的进程的地址空间。这些进程间数据的传递就不再涉及内核。然而不同于管道、消息队列利用阻塞自带的同步机制，在共享内存区间实现同步就得用到我们前面提到的同步方式。

mmap函数把一个文件或一个Posix共享内存区对象映射到调用进程的地址空间。使用该函数有三个目的：

1. 使用普通文件以提供内存映射I/O；
2. 使用特殊文件以提供匿名内存映射；
3. 使用shm_open提供无亲缘关系进程间的Posix共享内存区。

1
2
3

#include<sys/mman.h>
void *mmap(void *addr, size_t len, int prot, int flags, int fd, off_t offset);
		//返回：若成功则为被映射区的起始地址，若出错则为MAP_FAILED.

len为映射到调用进程地址空间中的字节数。内存映射区的保护由prot指定。

flags必须指定MAP_SHARED或MAP_PRIVATE中的一个，可有选择或上MAP_FIXED。如果指定了MAP_PRIVATE，那么调用进程对被映射数据所作修改支队该进程可见，不修改底层支撑对象。(或是一个文件对象，或是一个共享内存区对象)。如果指定了MAP_SHARED，那么调用进程对被映射数据所作的修改对于共享该对象的所有进程都可见，而且确实改变了底层对象。MAP_FIXED说明addr不为空，由自己指定。

从进程地址空间删除映射关系，调用munmap。

1
2
3

#include<sys/mman.h>
int munmap(void *addr, size_t len);
			//返回：若成功则为0，若出错则为-1.

如果映射区使用MAP_PRIVATE标志映射，进程做出的变动都会被丢弃。

有时候我们希望确信硬盘上的文件内容与内存映射区的内容一致，调用msync来执行这种同步。

1
2
3

#include<sys/mman.h>
int msync(void *addr, size_t len, int flags);
			//返回：若成功则为0，若出错则为-1.

addr和len可以为映射内存一个子集。对于flags，MS_ASYNC和MS_SYNC必须指定一个。一旦写操作已由内核排入队列，MS_ASYNC即返回，而MS_SYNC则要等到写操作完成后才返回。

BSD提供匿名内存映射，把flags参数指定成MAP_SHARED | MAP_ANON，把fd指定为-1。offset参数被忽略。

为了在无亲缘关系进程间共享内存区，有如下方法。

• 内存映射文件。

• 共享内存区对象。

Posix共享内存区涉及以下两个步骤：

1. 指定一个名字参数调用shm_open，创建一个新的共享内存区对象或打开一个已存在的共享内存区对象。
2. 调用mmap把这个共享内存区映射到调用进程的地址空间。

1
2
3
4
5

#include<sys/mman.h>
int shm_open(const char *name, int oflag, mode_t mode);
			//返回：若成功则为非负描述符，若出错则为-1.
int shm_unlink(const char *name);
			//返回：若成功则为0，若出错则为-1.

与mq_open和sem_open函数不同，mode参数必须指定。如果没有指定O_CREATE标志则可以为0。可能是因为对于虚拟内存来讲，段的访问权限是必须的吧。

ftruncate可用于设定共享内存区大小。

1
2
3
4
5
6
7
8

#include<unistd.h>
int ftruncate(int fd, off_t length);
			//返回：若成功则为0，若出错则为-1.

#include<sys/types.h>
#include<sys/stat.h>
int fstat(int fd, struct stat *buf);
			//返回：若成功则为0，若出错则为-1.

C++面试语法总结

static

1. static能够限制全局变量的作用域。在某一cpp文件中，我能通过extern的方式来访问其他cpp文件的全局变量。而static就断绝了这种可能性。

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   /*A.cpp*/ int a = 1; extern const int b = 1; //const在cpp文件中默认是当前文件可见，若需要扩展可见性需要加上extern关键字 static int c = 1; /*B.cpp*/ extern int a; extern const int b; extern int c; int main(){ std::cout<<a<<std::endl;//Success. std::cout<<b<<std::endl;//Success. std::cout<<c<<std::endl;//Link error. }

2. static表示数据的唯一性。在C++类里的static成员以及static成员函数，这些成员他们的归属不是对象，而是这个类本身，因此我们可以通过static成员来记录当前实例对象的数目。

   对于static成员的初始化，在类外进行。

3. 局部变量的static能够为函数加上状态。

extern

1. 正如在static中所说的，通过extern声明可以访问其他cpp文件中的全局变量。通常在头文件中声明，在源文件中定义。比方说在一个项目里，我想定义一些可以供其他代码使用的常量。我可以通过宏的方式，在一个单独的头文件里进行宏的定义，在需要使用到某一变量时便引入该头文件。但这种使用一个便要引入全部的方式可能并不是太理想。我们可以换种其他的方式，在一个cpp文件里面定义所有的常量，然后每次需要使用的时候便通过extern引入该变量。使代码更简洁。

2. extern “C”。C++为函数实现了重载，重载的实现方式是一种叫做name mangling的处理。将函数的形参以及初始函数名结合进行编码，形成一个该函数唯一标识的函数名。比方说重载函数，因为形参不同，通过name mangling处理后，函数名便变得唯一了。

   正因为C++对于重载采取的特殊处理，当C++与C协同工作时可能会出现问题。比方说我想使用某个C的函数，我在文件进行声明，但C++编译器会对该声明进行name mangling处理，处理后在与该C函数所在obj文件链接时会出现链接错误。(名字不符了，有点被打得妈都不认识的意思。hhh)这个时候我们就需要在这段代码前加上extern “C”，用来告诉编译器，别对我进行name mangling处理。

volatile

​ 在知乎上面看到个回答觉得特别好，volatile的意思就是非CPU改内存。

​ 在程序执行的时候往往会进行某种程度的优化，比方说

1
2

int a = *ptr;
int b = *ptr;

​ 正常来讲代码需要两次访问ptr指向的内存，编译器可能就会在此基础上做出优化，在第一次访问后将该内容放在寄存器里，后面再访问时，直接访问寄存器就行，节省一次访存时间。

​ 但是这种优化的正确性在于我对没有非CPU部分改内存的假设。假若有个IO设备，修改了该内存，而程序却对此一无所知。volatile就是告诉编译器对该变量别做优化，每次访问从内存里读。

多态与虚函数

​ 我理解的多态就是一种接口，多种方法。多态分为编译期多态和运行期多态。

1. 编译期多态。谈起编译期多态，我们首先提到的便是重载。相同的函数名，因为参数的不同有着不同的方法。重载的实现是通过采用一种叫做name mangling的处理方式。因为对函数调用的绑定是在编译期决议的，因此是一种编译期多态。

   另外一种用得比较多的编译期多态便是函数模板。一个简单的函数模板，因为模板参数的不同，在编译期实例化出不同的模板实例。这也是所谓的一种接口，多种方法。

2. 运行期多态。也是我们谈起多态时的默认含义，它是通过基类的指针或引用来调用虚函数接口，实际调用的函数取决于指针(或引用)实际指向的对象。

   虚函数的实现建议阅读《深度探索C++对象模型》，以及陈皓博客

   https://blog.csdn.net/haoel/article/details/1948051/

四种类型转换

​ 在介绍C++的四种类型转换时，我们先来看看C语言的显式转换。TYPE b = (TYPE) a，这种C风格的转换存在着许多缺点。因为它可以在任意类型之间进行转换，比如你可以把一个指向const对象的指针转换成指向非 const对象的指针，把一个指向基类对象的指针转换成指向一个派生类对象的指针。这两种转换差别巨大，但是传统C语言风格的类型转换没有区分。还有就是C语言针对每一种转换的格式都一样，不容易查找。

• static_cast，主要用于以下场合：

  • 用于类层次结构中，父类和子类之间指针和引用的转换；进行上行转换，把子类对象的指针/引用转换为父类指针/引用，这种转换是安全的；进行下行转换，把父类对象的指针/引用转换成子类指针/引用，这种转换是不安全的，需要编写程序时来确认；
  • 用于基本数据类型之间的转换，例如把int转char，int转enum等，需要编写程序时来确认安全性；
  • 把void指针转换成目标类型的指针（这是极其不安全的；

• const_cast，用于移除类型的const，volatile，__unaligned属性。

  1 2	const char* pc; char *p = const_cast<char*>(pc);

• dynamic_cast， 转换仅适用于指针h或引用。

  ​ 相比static_cast，dynamic_cast会在运行时检查类型转换是否合法，具有一定的安全性。由于运行时的检查，所以会额外消耗一些性能。dynamic_cast使用场景与static相似，在类层次结构中使用时，上行转换和static_cast没有区别，都是安全的；下行转换时，dynamic_cast会检查转换的类型，相比static_cast更安全。

  ​ 在转换可能发生的前提下，dynamic_cast会尝试转换，若指针转换失败，则返回空指针，若引用转换失败，则抛出异常。

  1. 继承中的转换

     • 上行转换：在继承关系中，dynamic_cast由子类向父类转换与static_cast和隐式转换一样，都是非常安全的。

     • 下行转换：

       1 2 3 4 5 6

       class A{virtual void f(){}}; class B:public A{}; void main(){ A* pa = new B; B* pb = dynamic_cast<B*>(pa); }

       A中定义了一个虚函数，这是不可缺少的。由于运行时类型检查需要运行时类型信息，而这个信息存在类的虚函数表中，只有定义了虚函数的类才有虚函数表。

  2. void*的转换

     一些情况下，我们需要将指针转换为void，然后再合适的时候重新将void转换为目标类型指针。

     因为在多重继承里，存在着指针调整的情况，调用dynamic_cast<void*>(ptr)，可以通过查表的方式，确定ptr实际对象的初始地址。

     1 2 3 4 5 6

     class A { virtual void f(){} }; int main() { A *pA = new A; void *pV = dynamic_cast<void *>(pA); }菱形继承中的上行转换

  3. 首先，定义一组菱形继承的类：

  1 2 3 4

  class A { virtual void f() {}; }; class B :public A { void f() {}; }; class C :public A { void f() {}; }; class D :public B, public C { void f() {}; };

B继承A，C继承A。

D继承B和C。

考虑这样的情况：D对象指针能否安全的转换为A类型指针？

直觉来说是可以的，因为从子类向父类转化，无论如何都是安全的。

1
2
3
4
5
6
7
8
9
10

class A { virtual void f() {}; };
class B :public A { void f() {}; };
class C :public A { void f() {}; };
class D :public B, public C { virtual void f() {}; };

void main()
{
    D *pD = new D;
    A *pA = dynamic_cast<A *>(pD); // pA = NULL
}

但实际上，如果尝试这样的转换，只能得到一个空指针。因为B和C都继承了A，并且都实现了虚函数f()，导致在进行转换时，无法选择一条转换路径。

一种可行的方法是，自行指定一条转换路径：

1
2
3
4
5
6
7
8
9
10
11

class A { virtual void f() {}; };
class B :public A { void f() {}; };
class C :public A { void f() {}; };
class D :public B, public C { void f() {}; };

void main()
{
    D *pD = new D;
    B *pB = dynamic_cast<B *>(pD);
    A *pA = dynamic_cast<A *>(pB);
}

4. reinterpret_cast

   可以转换任意类型的指针，在编译器完成，最好别使用。

常见问题

1. 为什么析构函数不能抛出异常？

• 如果析构函数抛出异常，则异常点之后的程序不会执行，如果析构函数在异常点之后执行了某些必要的动作比如释放某些资源，则这些动作不会执行，会造成诸如资源泄漏的问题。(抛出点意味着后面的内容不会执行。)
• 通常异常发生时，c++的机制会调用已经构造对象的析构函数来释放资源，此时若析构函数本身也抛出异常，则前一个异常尚未处理，又有新的异常，会造成程序崩溃的问题。

析构函数无法保证没有异常情况怎么处理?

​ 把异常封闭在析构函数的内部，不让异常抛出函数之外。

1
2
3
4
5
6
7

~Destructor{
    try{
        do_something();
    }catch(){
        //可以什么都不做，只是确保异常不要逃出析构函数。
    }
}

2. 构造函数和析构函数中调用虚函数吗？(Effective C++ Item9)

​ 最好不要在构造函数和析构函数中调用虚函数，不见得一定会出现错误，但可能不符合你的预期。

• 在我们构造一个子类对象时，我们先执行的是父类的构造函数，然后执行子类的构造函数。倘若我们在父类构造函数里面调用虚函数。我们可以猜想到编译器可能会采取的两种处理方式：

  • Plan A，调用虚函数的基类版本，这样失去了运行时调用的正确版本的意义。
  • Plan B，调用虚函数的正确版本，倘若正确版本是子类函数，但子类这个时候还不存在，函数调用会导致未知行为。

  实际上编译器采用的是Plan A, 这种方式可以避免严重错误。但不可避免的是给使用者造成不符预期的困惑。

• 同样的道理，析构函数的调用顺序是先子类，再父类。同样存在在父类中调用所谓“正确版本”的虚函数时而子类不存在的问题。编译器采用的同样是调用虚函数的基类版本的方式。

  为了演示这只是构造函数和析构函数的特殊性，让我们来看下面的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class A{
public:
  	A(){func();}
    virtual void func(){std::cout<<"A::func";}
    void f(){func();}
};

class B:public A{
public:
  	B():A(){}
	void func() override{std::cout<<"B::func";}
};

int main(){
    A* a = new B;
    a->f();//result : A::func. B::func.
}

​ 很明显在构造函数里面和普通函数分别调用虚函数行为不一样。

3. 引用和指针的区别

   • 引用在创建时必须初始化，引用到一个有效对象；而指针在定义时不必初始化，可以在定义后的任何地方重新赋值。

   • 指针可以是NULL，引用不行

   • 引用貌似一个对象的小名，一旦初始化指向一个对象，就不能将其他对象重新赋值给该引用，这样引用和原对象的值都会被更改。

   • 引用的创建和销毁不会调用类的拷贝构造函数和析构函数。

4. 内存对齐的原则

   • 结构体的总大小，必须要是其内部最大成员的整数倍，不足的要补齐。

     1 2 3 4 5 6 7

     typedef struct one { char a;=====> 1 -> 4 int b;======> 4 double c;===> 8. //max char d;=====> 1 -> 8 //补齐到8的整数倍 } ONE; //结构体one总大小： 4+4+8 = 16

• 结构体或联合的数据成员，第一个数据成员要放在offset==0的地方，如果遇上子成员，要根据子成员的类型存放在对应的整数倍上。

  1 2 3 4 5 6 7

  typedef struct two { char array[2];==> 2 -> 4 int b;==========> 4 double c;=======> 8 //max float d;========> 4 -> 8 //原则1 } TWO; //结构体two总大小： 4+4+8+8 = 24

• 如果结构体作为成员，则要找到这个结构体中的最大元素，然后从这个最大成员的整数倍地址开始存储。

  1 2 3 4 5 6 7 8

  struct three { char a; ====> 1 -> 4 int b;======> 4 double c;===> 8 short d;====> 2 -> 8 //原则3 ,下面是个结构体，其中最大成员为8，则需要从8的整数倍地址存放，所以变量d补齐到8 TWO e; ==> 24 (max 8) }; //结构体two总大小： 4+4+8+8+24 = 48

《Effective C++》读书笔记<六>

Item 32：明确你的public继承塑模出is-a关系

如果令class D以public方式继承class B，相当于告诉编译器，每个类型为D的对象同时也是一个类型为B的对象。你的意思是B比D表现出更为一般的概念，而D比B表现出更特殊化的概念。凡是B对象可以派上用场的地方，D对象一样可以排上用场

Item 33：避免遮掩继承而来的名称

如果你在使用public继承，但是却不继承base的函数，便是对is-a关系的违反。

倘若你在子类D中定义了从B中继承而来的同名函数，那么从名称查找的观念来看，B中的函数便不再被继承。你在D中定义的函数遮掩了继承的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class B{
public:  
    virtual void f1() = 0;
    virtual void f1(int);
    virtual void f2();
    void f3();
    void f3(int);
};

class D:public B{
public:
    virtual void f1();//override f1(), but hide f1(int). 
    void f3();//hide f3().
    void f4();
};

你可以使用using声明解决问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class D:public B{
public:
    using B::f1;
    using B::f3;
    virtual void f1(); 
    void f3();
    void f4();
};

D d;
d.f1(); // D::f1.
d.f1(1); // B::f1.
d.f2(); // B::f2.
d.f3(); // D::f3.
d.f3(1); // B::f3.

值得注意的是，using的意思与字面有区别，不是说接下来的调用都是使用这个using指明的范围，而是说让using指明的名字在当前作用域可见。

有时候不想继承基类所有的函数，而是说只想继承一部分。当然这对于public继承是不可能的，但是对于private继承有时候可能会有这种需求。这个时候使用using会暴露父类所有该名函数，我们需要不同的技术，叫做转交函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Base{
public:
    virtual void f1() = 0;
    virtual void f1(int);
};
class Derived: private Base{
public:
    virtual void f1(){//转交函数，遮掩父类所有f1函数
        Base::f1();//暗自成为inline.
    }
};

D d;
d.f1();// 调用D::f1()->B::f1().
d.f1(1);// 错误.

Item 34：区分接口继承和实现继承

身为class设计者，有时你会希望derived classes只继承成员函数的接口；有时你又会希望derived class同时继承函数的接口和实现，但又能override它们所继承的实现；有时你希望derived classes同时继承函数的接口和实现，并且不允许覆写任何东西。

• 成员函数总是会被继承。public继承意味着is-a的关系，父类所有的函数在子类上都能施行。
• pure函数是为了让derived classes只继承函数接口。(我们可以为纯虚函数提供定义，但是意义不大)
• 声明impure virtual函数是为了让derived classes继承该函数的接口和缺省实现。它表示每个子类都必须支持这样一个函数，如果不想写，可使用缺省版本。
• 声明non-virtual函数目的是为了令derived classes继承一份接口和一份将强制性实现。

Item 35：考虑virtual函数以外的其他选择

假设我们现在写一款游戏，不同角色攻击时会释放不同的技能，可能我们会想到使用virtual函数，让特殊角色都继承于GameCharacter，GameCharacter提供了一份缺省实现，特殊角色可针对自己的情况改写攻击函数。

当然这也是我们最常规的办法，除此之外，也存在着许多其他的方式供我们选择。

• Non-Virtual Interface的手法实现Template Method模式

1
2
3
4
5
6
7
8
9
10
11
12

class GameCharacter{
public:
    void attack(){
        beforeAttack();
        doAttack();
        afterAttack();
    }
private:
    virtual void doAttack(){
        ...
    }
};

这就是所谓的NVI手法，attack是作为doAttack的外覆器。

NVI的优势在于我们可以在进行实际操作前后做些处理，正如我们beforeAttack()，afterAttack()写的那样。

• 基于Function Pointers实现的Strategy模式

我们可以让不同角色保存一个函数指针，该函数指针执行特殊攻击操作。但是这样存在一个问题，就是函数指针指向的函数可能需要访问对象的私有元素，这样可能就需要采用friend关键字来为函数特殊访问权限。

• 基于std::function实现的Strategy模式

与上面的Function Pointers相似，只不过std::function具有更好的封装，可以保存成员函数。

• 传统的Strategy模式

让不同操作封装在不同类里，并形成继承链，在不同角色中保存有这些操作的对象，并在角色的攻击函数中调用操作对象的接口。

这里只是介绍传统的Strategy模式，在这个例子里面意义不大。

Item 36：绝不重新定义继承而来的non-virtual函数

因为这个时候对于一个D对象，通过B指针访问该函数和通过D指针访问该函数的表现不再相同。也就是说用到D指针的地方不能用B指针替代，也就是违背了public继承is-a的关系。

很显然，父类的non-virtual函数体现了某种不变性，一旦子类改变定义，便是对is-a关系的违反。如果希望子类对某些函数表现出特异性，这时就需要virtual关键字，virtual函数通过虚函数表的机制，向子类提供了一种保证：你可以大可以重新定义我，我将仍然维护is-a关系。因为D对象不论是通过D指针还是通过B指针访问，表现都是相同的。

Item 37：绝不重新定义继承而来的缺省参数值

virtual函数是动态绑定的，而缺省参数值确实静态绑定的。

1
2
3
4
5
6
7
8
9
10

class A{
public:
    virtual void f(int i = 0);
}
class B:public A{
public:
	void f(int i = 1);
}
A* a = new B();
a->f();//我们可能期待参数为1，但实际上是0

在上面的例子里面，我们重新定义了继承而来的缺省参数值，但通过指针或引用来访问时，由于缺省参数值是静态绑定的，a的静态类型是A，所以我们绑定了缺省参数值0，在运行时才调用到B::f()，这就很容易造成误解，所以最好的做法是不要重新定义继承而来的缺省参数值。

之所以让绑定缺省参数在编译器进行，是为了降低运行期的开销。

Item 38：通过复合塑模出has-a或is-implemented-in-terms-of

复合有两个意义。复合意味has-a或is-implemented-in-terms-of。程序中的对象其实相当于你所塑造的世界中的某些事物，例如人、汽车、视频画面等等。这样的对象属于应用域部分。其他对象则纯粹是实现细节上的人工制品，像是缓冲区、互斥器、查找树等等。这些对象属于实现域部分。复合发生于应用域内对象之间，表现出has-a关系，当发生于实现域内则是表现is-implemented-in-terms-of关系。

Item 39：明智而谨慎地使用private继承

1
2
3
4
5
6
7
8
9

class Person{};
class Student:private Person{};
void eat(const Person&);
void study(const Student&);

Person p;
Student s;
eat(p);//正确
eat(s);//错误，没有is-a关系

private继承意味着implemented-in-terms-of。如果让D以private形式继承B，用意是采用B中已经备妥的某些特性，不是因为B和D有任何观念上的关系。

private继承与复合有点相似，我们在两者间的取舍可总结为：尽可能使用复合，必要时才使用private继承。private继承主要用于“一个意欲成为derived class者像访问一个意欲成为base class者的protected成分，或为了重新定义一或多个virtual函数”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/*private继承*/
class Timer{
public:
    explicit Timer(int tickFrequency);
    virtual void onTick() const;
};

class Widget: private Timer{
private:
    virtual void onTick() const;
}//Widget可以调用onTick().

/*普通复合*/
class Widget{
private:
    class WidgetTimer:public Timer{
    public:
        virtual void onTick() const;
    };//定义于Widget内部,让其他类无法继承WidgetTimer。
    WidgetTimer timer;
};

另外在一种激进情况涉及空间最优化，可能促使你选择”private继承”而不是”继承加复合”。

1
2
3
4
5
6
7
8
9

class Empty{};
class HoldAnInt{
private:
    int x;
    Empty e;
};//sizeof(HoldAnInt) > sizeof(int)

//独立对象大小不为零。
//sizeoff(Empty) == 1.编译器默默安插一个char到空对象里，虽然char不算大，但在复合关系里，可能存在对齐问题，导致额外的padding开销。

我们提到了独立对象不为零，如果该对象是作为另一对象的附带情况就会不一样了。

1
2
3
4
5

class HoldAnInt:private Empty{
private:
    int x;
};
//这个时候sizeof(HoldAnInt) == sizeof(int)

这就是所谓的EBO优化(empty base optimization)

Item 40：明智而谨慎的选择多继承

• 多重继承比单一继承复杂。可能导致歧义性，以及对virtual继承的需要。
• virtual继承会增加大小、速度、初始化复杂度等等成本。如果virtual base classes不带任何数据，将是最有使用价值的情况。
• 多重继承有正当用途。其中一个情节涉及”public继承某个Interface class”和“private继承某个协助实现的class“两相组合

带优先级的中缀转二叉树

在我们聊具体的算法前，我们先来看一个问题。给定中缀表达式以及各种操作数的优先级，我们如何将这个中缀表达式转换成对应的二叉树。比方说2 + 3 * 6 ，如何在这个中缀表达式的基础上构建二叉树。对于这个问题，我琢磨了很久，总结了三个简单的性质。

1. 对于中缀表达式的相邻节点L和R，如果L的优先级高于R，那么L一定是R的左孩子节点。
2. 对于中缀表达式的相邻节点L和R，如果L的优先级低于R，那么R一定是L的右子树节点。并且一旦L后续有个节点L‘的优先级小于L，那么L’后续节点不可能再是L的右子树节点了。
3. 对于一系列节点，N1，N2 …… Nx如果Nx是第一个优先级小于N1的的节点，那么N2–Nx-1都是N1的右子树节点。

在说完这几条定理以后，让我们来看看构建二叉树的具体算法。另外，我们给出一个定义，对于一个节点，在我们未能决议出它的右子树前，我们称这棵树是不稳定的。根据定理3，一旦我们为N1在找到了一个优先级小于它的节点Nx，那么N1右子树存在哪些节点便能确定了，需要的只是在遍历中缀序列时，对这些节点进行结构化的管理。接下来我们来看具体的算法。

1. 初始化：维护一个我们称作右子树库的栈，初始为一节点HＮ，优先级MIN＋１，为序列添加一节点TＮ
2. 遍历中缀序列：栈的顶部子树的根节点我们记作R(root)，当前遍历到的节点记作C(current)。
   • 如果R的优先级小于C，根据定理2，我们知道C是R的的右子树节点，因此将C推入右子树库中。
   • 如果R的优先级大于C，我们维护一个子树，初始为空，用以表示R右子树，记作RT(Right Tree)。进行如下循环，只要栈不为空并且当前R的优先级大于C，我们就将R从栈中弹出，将RT置为R的右子树，并将R任命为新的RT。在循环结束后，将RT置为C的左节点，并将C推入栈中。
3. 终止：如果序列遍历结束，ＨＮ的右子树即为我们构造成功的二叉树。

调度场算法

说完了带优先级中缀序列转二叉树，让我们来看看中缀序列转后缀序列。其实既然我们能够还原成二叉树，那么后缀序列也可以很容易得到，因此接下来我们要介绍的调度场算法，原理上其实和之前介绍的算法是有点相似的。

规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号，则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

可以看到，这个过程与先前讲到的算法过程是很像的。碰到数字就输出，因为数字的优先级最高，意味着它不可能有右子树，所有碰到它我们就输出。碰到符号我们判断与栈顶符号优先级的比较，若是优先级更高，意味着该符号是栈顶符号右子树的一部分，因此入栈；而如果优先级更低，意味着该栈中许多符号的右子树已经确定了。因此我们让所有已经确定的符号出栈输出。

对于括号的处理有点特殊，因为它无法很好的适配我们的二叉树。但是我们可以这样理解，括号意味着括号里面的内容整体就像一个数字一样，因此看到括号就意味着我们需要在一个新的环境里把这个括号里的后缀序列先产生出来，至于这个新的环境也不见得一定要用一个新的栈，只要这个新的环境不影响之前栈的内容即可。因此我们可以让括号的优先级无穷小，并且在看到括号即入栈，只有反括号能够将此括号弹出。这样可以保证这个新环境不会影响之前的环境，因为有这个无限小的括号做隔离。

接下来我们来看看示例

20[(2.44-1.8)/0.4+0.15] -> a((b-c)/d+e)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

//1. 在结尾加一结束符： a*((b-c)/d+e)#
//2. 处理过程：
输入    输出            更新后的栈内容(自底到顶)
a       a
*       a               *
(       a               *(
(       a               *((
b       ab              *((
lvl(-)=1, lvl(()=0
-       ab              *((-
c       abc             *((-
)       abc-            *(
lvl(/)=2, lvl(()=0
/       abc-            *(/
d       abc-d           *(/
lvl(+)=1, lvl(/)=2
+       abc-d/          *(+
e       abc-d/e         *(+
)       abc-d/e+        *
#       abc-d/e+*

TCP总结

MSS

The maximum segment size is the largest “chunk” of data that TCP will send to the other end.

当连接建立起来后，每一端都能通知对端自己的MSS，让对面每次发送的Segment不要太大以至于被分片。An MSS option can only appear in a SYN segment.如果没有收到对面给的MSS信息，那么默认为536.（每个主机都必须能接受小于576的数据报）

我们可以知道的是，MSS的大小往往大一点是更好的，因为可以减少IP和TCP包头的开销。MSS往往设置为网卡出口的MTU-40。在发送数据时，我们不仅要考量对端的MSS，我们考虑网卡出口的MTU。我们选择合适的MSS是为了在避免分片的情况下尽量选择更大的一次性数据发送量，但是分片极有可能在路径中间的瓶颈处进行。也就是说双方提示给对面的MSS都很大，但是中间有个路由器不够争气。（解决这种情况的方法是使用path MTU discovery）

Half-Close

由于TCP是全双工的，双方都能发送接收数据，所以存在两条数据流，是否中断那条数据流是由发送方决定的。也就是说，A能关闭它作为发送方的数据流，但仍然可以选择在另一条数据流上读取数据。在关闭一条数据流后的状态就是处于Half-Close。注意，在使用Unix Api close关闭套接字，这不是进入半关闭状态，因为这会同时关闭读和写。

TCP State Transition Diagram

2MSL Wait State

如上图所示，TIME_WAIT也叫做2MSL状态。TCP的每种实现都必须设定一个值叫做maximum segment lifetime。它代表着一个Segment 被丢弃前在网络中能存在的最长时间。

TIME_WAIT存在处于两个目的：

• 我们假设客户端作为主动关闭方，那么客户最后发送的对Fin的Ack是可能会丢失的。但是这个信息对于服务器又是关键的，不收到它会以为你还在那边听，只是我的关闭信息没发过去。倘若客户没有进入TIME_WAIT状态，只会让服务端陷入无限的自责，一直以为是自己的问题。
• 在处于2MSL阶段时，这个连接的socket pair不能被重用，直到2MSL阶段结束。大多数的实现给了一个更严格的要求，处于TIME_WAIT的一端的Socket port都不能被重用，而不只是那对socket pair。在这个阶段收到的数据包都会被丢弃，等待2MSL可以让之前连接的数据包消失殆尽，不至于影响后续的连接。

疑问：为什么滞后的数据包只影响主动关闭方，不影响被动关闭方？

任何主动关闭方试图在关闭后立刻重启并绑定相同port的都会出问题。这个问题在客户端可能影响不大，但是对于服务器的影响确实巨大的。因为服务器的端口是众所周知的，试想需要等待1-4分钟才能重启服务器的影响（

我们可以给套接字加上SO_REUSEADDR选项，让其可以绑定处于TIME_WAIT阶段端口，但即使这样，如果我们试图连接相同的服务器，还是无法连接，因为那个socket对处于2MSL阶段。但是如果是服务器主动关闭，这却可以实现。：）

Half-Open

A TCP connection is said to be half-open if one end has closed or aborted the connection without the knowledge of the other end.

没有办法在半开状态传送数据，也没有办法察觉。常见的原因可能是突然断掉电源。

Simultaneous Open

TCP was purposely designed to handle simultaneous opens and the rule is that only one connection results from this, not two connections.

同时打开需要交换4条Segments，两端都扮演着客户端和服务端。

疑问：（这种同时打开的意义在哪？还有，是不是必须得创建监听套接字）

Delayed Acknowledgments

当TCP连接用于交互式数据传输时，每次传输的数据可能会很少。为了减少包头的开销以及减少链路上的数据包的数目，通过采取一种叫做延迟确认的技术。这种技术是说，在收到数据包后，不立即确认，而是先等待一阵子，看看有没有要发的数据，把数据和确认号一起发过去。大多数实现采用200ms的延迟。

TCP的计时往往是基于心跳的，它不是说一定得准确计时200ms后再发送。就好比一个闹钟，它每隔一段时间滴答一下，用以大致估计时间。闹钟的时间是在流逝的，但我不关注，我关注的只是心跳。比方说我关心200ms的心跳，那么我收到数据时可能离上次心跳刚过去0-199ms这都不能确定，所以我的延迟不是准确的200ms，而是到下一次的心跳发生的间隔。

Nagle Algorithm

这个算法意思是说不会有数据就传，而是等之前的数据的Ack确认号收到后再传，在此之前可以将数据收集起来。这个算法用于交互式的小数据传输，可以节省数据包头并且减少网络中包的数量。

这个算法是自适应的，Nagle算法是为了减少小的数据包的数量，降低网络中的通信压力，当信路通畅时，它发的也快，当信路状况不好时，它也可以通过减少包的数量，降低发送速率来缓解线路压力。

有时候我们需要关闭Nagle算法，比方说我们的信息交互是即时的，对延迟比较敏感。另外，假如我们键入指令让远程执行，如果TCP拿到一个字节数据发给服务端，服务端靠这一个字节的数据无法产生应答，直到Delayed（200ms）时间到了，才将Ack返回。这也就是说，至少要等200ms，才能让后续的字节发过去，造成了明显的延迟。

Sliding Windows

滑动窗口是为了控制两端的流量，在两端发送和接受速率存在很大差别时，不至于让大量的数据无意义的传输。

The window advertised by receiver is called the offered window.

窗口移动有如下三种情况：

• 发送方的消息被确认时，发送窗口的左端右移。
• 当接受方的接收窗口数据被进程读取后，腾出空间，这时发送方的发送窗口右端右移。
• 发送窗口的右端左移（RFC是禁止的，但是TCP必须能与这样行为的对端成功合作）

窗口的大小往往是由进程确定的。

PUSH Flag

PUSH Flag是一个信号，用来告诉接受方，你把数据尽快递给进程，不要让数据在TCP的buffer里逗留等待额外的数据。接受方收到PUSH后，它就会知道，不需要等待额外的数据了。

现在往往没有Api去设置这个信号位，如果在数据发送后缓冲清空了的话，大多数伯克利衍生的实现会自动的加上这个标志。

Bulk Data Throughput（不太懂）

TCP重传

TCP的重传计时是以连接的RTT为基础的，而RTT又是随着时间会发生变动的，所以我们需要对RTT有一定的测量方案，并尽量反应网络状况。

第一个算法如下：

1
2

R<-αR + (1-α)M
RTO = Rβ

其中α代表着平滑因子，一般选取0.9，而β一般选取2.RTO为计算得到的超时重传时间。

这个方法看上去不错，但是有一个问题，它无法反映RTT的急剧变化。比方说RTT突然增大，但是RTO不能反映这种剧烈变化，造成的影响是RTO比理论偏小，造成了不必要的重传。

Jacobson提出了另外的一种算法：

1
2
3
4

Err = M - A
A <- A + gErr
D <- D + h(|Err| - D)
RTO = A + 4D

g，h一般分别取0.125，0.25.

D便是测定的平均变化程度，这种算法便考虑了剧烈变化的影响。

关于RTT的测量需要注意一些问题

• 如果一个报文段准备发送时，而此时timer正在被使用，那么这个报文段不计入RTT的测量。
• RTT的计时是基于500ms-timer，也就是说550ms的发出到收到ACK时间间隔，可能被计入1tick或2ticks，分别代表500ms和1000ms。
• 重传的报文段不计入RTT的测量，因为不知道这个回应是针对哪个报文段。依据Karn’s Algorithm，我们将重新使用加倍后的RTO。

具体的例子参考《TCP/IP详解 Vol1》p304

拥塞避免

Slow Start

在发送方存在另外一个窗口，叫做拥塞窗口，用来模拟当前的网络状况。拥塞窗口初始值为一个Segment，每次收到一个ACK，拥塞窗口便增加一个Segment。每次发送方能够发送advertise window和拥塞窗口中的更小值量的数据。也就是说，我开始只能发一个Segment，但当我收到ACK后，我就能发两个了。当发送的两个都收到以后，我就能发四个。意思就是每收到一个ACK，就能让我能发送的个数增加1.

拥塞避免和Slow Start是不同的算法，当拥塞发生时，我们需要减缓发送速率，需要使用拥塞避免算法和Slow Start的结合。需要维护两个变量：

• 拥塞窗口（congestion window，cwnd）
• 慢启动门槛（slow start threshold size， ssthresh）

算法具体操作如下：

1. 将cwnd初始化为1个Segment，ssthresh初始化为65535个字节。

2. TCP不会发送大于cwnd和advertised window中更小者的数据量。

3. 当拥塞发生后（超时或连续收到3个相同的ACK），将ssthresh设置为当前窗口的一半（cwnd和advertised window的更小者，但至少是2个Segment），如果拥塞发生的原因是超时，那么cwnd设置为1个segment。

4. 当新的数据被ACK后，我们需要增加cwnd，但增加的方式取决于我们在进行慢启动还是拥塞避免。

   如果cwnd小于等于ssthresh，我们做慢启动，不然我们就是处于拥塞避免阶段。Slow Start到我们拥塞发生的地方，然后拥塞避免就开始了。

   Slow Start的cwnd刚开始是1个Segment，每次收到收到一个ACK就会增加1.增长的速率是指数倍的，1，2，4…这也就是为什么拥塞发生时，ssthresh要减少至一半。拥塞避免阶段，每次收到一个ACK，增加1/cwnd。

   我们在这里提到增长以段为单元，实际上是按照字节来的。

Fast Retransmit and Fast Recovery

有时不用等到超时我们就能判断丢包，当我们连续收到3个或以上相同的ACK，我们便可以知道极大可能是发生了丢包。这叫做快重传。另外，正如在上面提到的，不会开始慢启动，而是采取叫做快恢复的方式。之所以采用快恢复是因为我们注意到还是收到了3个ACK，说明当前的网络状况不算太糟糕。没必要启用慢启动。

算法的步骤大致如下：

• 当收到重复的ACK后，设置ssthresh为窗口的一半。（cwnd和advertised window的更小者，至少是2个Segment）

  重传丢失的Segment，设置cwnd为ssthresh+3个Segment大小。

• 每次收到重复的ACK，将cwnd增加一个Segment大小，然后重传一个包。

• 当下一个对新数据的ACK到达后，将cwnd设置为ssthresh。

具体的计算实例参考《TCP/IP详解 Vol1》p314

TCP Persist Timer

假设我们有A，B双方通信，A准备给B发送消息，无奈B的接收窗口一直为0。后来B腾出了空间，将这个信息告诉A，可惜这个信息还丢了。因为这个信息不存在重传，所以导致了一个A想给B发信息发不了，B在等A信息的局面。

这时就需要使用使用Persist Timer，当A收到B的通告说接收窗口为0时，A会设置一个Persist Timer，一旦过了这个时间还没有B窗口能用的信息，它就怀疑是ACK丢了，于是它发送一个window probe，询问信息。如果ACK没丢，只是单纯的没地方，那么B的回复就重置Persist Timer，并且时间翻倍。

糊涂窗口症状

所谓的糊涂窗口症状是说，总是小的数据在传递，而不是一个满的数据段。

它的发生可能是两端的原因：接受方通告了太小的接收窗口（而不是等窗口大一点后再通告）；或者发送方发送少量数据，而不是等到积累一定数据量后一起发。为避免糊涂窗口症状，两端都在为此付出努力。

• 接受方禁止通告小窗口，一般的算法是，等到可接收窗口的大小到了min（Segment，buffer space / 2）再做通告
• 发送方只有再满足如下条件才传输数据：
  • Segment数据能够传送。
  • 能传送对端advertise过的最大窗口的一半的数据。
  • 我们能发送任何已有数据，要么我们开启了Nagle算法但不存在未确认数据了，要么禁止了Nagle算法。

这里就有可能发生一种情况，B给A通告的窗口大于一个Segment，A发送的数据为一个Segment，此时B的窗口不足以通告，但是必须通告，并且这个值不能为0，不然A的发送窗口就出现了右端左移的情况。

具体的例子参考《TCP/IP详解 Vol1》p329

TCP Keepalive Timer

通常设置keepalive选项的是服务器，为了判断当前是否是half open状态。

如果当前连接已经两个小时没有互动了，服务器就会发送一个Probe Segment到客户端，客户可能处于以下几种状态：

• 运行并可达，这时客户端会响应服务端，让它知道自己一切都好，然后服务端重新设置keepalive timer为2个小时。
• 宕机，服务器收不到回复，并且在75秒后超时。服务器一共会发10个，分隔75秒，如果一个回复都收不到，服务器都会猜测客户端已经宕机，随机关闭连接。
• 宕机又重启，这时客户端收到Probe，因为刚重启，会相应一个Reset，导致服务端终止连接。
• 运行不可达，这种情况类似第二种，TCP不能辨别。

操作系统基本算法

调度

对于操作系统来讲，何时调度是一个问题。一般来说，分为以下几种情况。1）在创建一个新进程后需要决定运行父进程还是子进程。2）在一个进程退出时做出调度决策。3）当一个进程阻塞在I/O和信号量上或由于其他原因阻塞时，必须选择另一个进程运行。4）在一个I/O中断发生时，必须做出调度决策。如果中断来自I/O设备，而现在设备完成了工作，某些被阻塞的等待该I/O的进程就成为了可运行的就绪进程了，具体运行哪个进程取决于操作系统对调度的实现。

调度算法的分类

批处理

运行批处理作业的大型计算中心的管理者通常检查三个指标：

吞吐量、周转时间以及CPU利用率。1）吞吐量是单位时间完成的作业数量。2）周转时间是一个作业完成的平均时间。3）CPU利用率。吞吐量的优秀不代表周转时间优秀。

常用的批处理调度算法：

• 先来先服务(FCFS): 很好理解，最先到的作业，先完成它。后来的排在后面。好处是实现起来比较容易，缺点是可能让其他进程的周转时间过长。
• 最短作业优先(SJF): 由于在当前作业完成前，其它的作业都在等待你，因此让完成时间最短的作业先执行可以减少其他作业的等待时间。
• 最短剩余时间优先(shortest remaining time next): 相比于SJF，这种算法表现出了抢占性，并且有着更好的周转时间。

交互式

• 轮转调度(round robin): 轮转调度为每个进程分配了时间片，允许进程在时间片内运行。如果时间片结束，由计时器发出时钟中断，调度程序便停止进程的执行，并把它送往队尾。

  时间片轮转算法的效率和时间片关系很大：时间片大小，导致进程切换频繁，在进程切换上花费时间巨大。如果时间片过长，实时性就不能得到保证。

• 优先级调度：为每个进程分配一个优先级，按优先级进行调度。为了放置低优先级的进程永远得不到调度，可以随着时间的推移增加等待进程的优先级。

• 多级反馈队列：一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。

  多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。

  每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

  可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

实时

实时系统要求一个请求在一个确定时间内得到相应，非为硬实时和软实时，前者必须满足绝对的截至时间，后者可以容忍一定的超时。

页面置换算法

最佳置换算法(OPT)

所选择的被换出页面是最长时间内不再被访问，通常可以保证获得最低的缺页率。是一种理论上的算法。因为无法知道一个页面多长时间不再被访问。举例：一个系统为某进程分配了三个物理块，并有如下页面引用序列：70120304230321201701.

开始运行时，先将 7, 0, 1 三个页面装入内存。当进程要访问页面 2 时，产生缺页中断，会将页面 7 换出，因为页面 7 再次被访问的时间最长。

最近最久未使用(LRU)

虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。

为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。

因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。

最近未使用(NRU)

每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：1)R=0，M=0,2)R=0，M=1,3)R=1，M=0，4)R=1，M=1

当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。

NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。

第二次机会算法

FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：

当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。

时钟置换算法

第二次机会算法需要在链表中移动页面，降低效率。时钟算法使用环形链表将页面链接起来，再使用指针指向最老页面。

工作集页面置换算法

一个进程当前正在使用的页面的集合叫做工作集。如果工作集都被装入了内存，那么进程在运行到下一阶段前，不会产生很多缺页中断。如果内存太小无法容纳整个工作集，运行过程会发生大量的换入换出，这叫做颠簸。（有点类似于虚拟内存的抖动现象）不少分页系统会跟踪进程的工作集，在进程运行前预先装入工作集页面也成为预先调页。

磁盘臂调度算法

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

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

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

先来先服务（FCFS）

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

优点是公平和简单。缺点是未对寻道做任何优化，使平均寻道时间较长。

最短寻道时间优先（SSTF）

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

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

电梯算法（SCAN）

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

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

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

C++对象模型总结

单一继承（含虚函数）

这种情况下的虚表结构很简单，在子类中保存一张虚表，虚表里有着父类的RTTI信息，并且排列着自己独有的虚函数地址以及被override的虚函数地址。

值得注意的是，子类生成的这张表与父类的表有着某种程度上的对应。比如说在父类里的某个虚函数，在它表里对应的slot为1，那么在子类里，即使覆盖了这个虚函数，对应的slot同样得是1。因为在编译期不能决议的仅仅是指针（或引用）具体指向的内容，但对于调用的虚函数在表里的偏移，这在编译期是已知的。（总不能连这都不知道，等到运行时去遍历虚表吧）

多重继承

多重继承相比于单一继承来说会复杂一点，复杂的点主要在于指针的调整上。我们可以想象，在单一继承里，指向父类的指针与指向子类的指针是具有相同值的；但在多重继承里，这种性质不再这么自然。

我们先来看看多重继承下的对象内存布局。这种情况下的内存布局不算复杂，按照父类的声明顺序，将父类成员堆叠起来，除此之外，为每个父类的区域，插入一个对应的虚表指针。至于为什么要为每个父类准备一个虚表指针，我们可以想象不这样做，让它们共享一个表，我们在前面提到过，在编译期是已知调用函数的slot号的，现在继承于多个父类，在共享一张表的情况下，肯定会有两个父类的不同函数对应相同slot，这就给我们造成了麻烦。

说完了对象的内存布局，我们再来看看虚函数表。可以知道的是，每个父类区域的虚表，一定是通过这个父类指针可以访问的虚函数。除此之外，对于位于最左的父类的虚表做了补充，补充的内容是最左父类访问不到，但是子类可以访问的虚函数。

聊完了虚函数表的内容，我们再来思考其他的问题。假设A，B是C的父类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class A{
public:
    virtual void f(){}
};
class B{
public:
    virtual void g(){}
};
class C:public A,public B{
public:
    void f() override{}
    void g() override{}
};

int main(){
    C* c = new C;
    B* b = c;
}

在我们的主函数的语句里，我们可以想象，C中的B部分的起始地址与C的起始地址是不同的。实际上，在编译这条语句时，编译器是做了处理的。

1

B* b = c + sizeof(A);

当我们实际输出b和c的地址时就能看到这种区别（用==判断不行，编译器做了处理）

当然，这是在编译期做的处理，也很好理解。让我们来看看其他几种类似的但是不能在编译期解决的问题。我们叫做调整this指针的负担。

1. 基类指针调用子类函数

当第二个或后继的基类调用子类的虚函数时，需要对this指针进行调整。这应该很好理解，假设不进行调整，在该函数里对子类成员的任意访问都会出现问题。但是这种调整在编译期无法做到（在编译期对你会调用哪个函数都不确定，又谈什么调用前调整指针呢），因此我们需要一种执行期调整的技术。在我了解的范围里，有两种技术。

• 扩展虚函数表。为每一个虚函数表的表项增加调整的偏移量内容。也就是说，现在每一项都包含一个函数指针和一个偏移量。在调用时便进行调整。这种办法虽然简洁，但是并不是所有的函数都需要调整呀。这样显式的为项都增加内容显得有点浪费。
• thunk技术。对于thunk我并不是太了解，但并不影响我们思考这么模型。我将thunk简单的理解成一个扩充了调整this指针的函数。只不过这个函数是一段assembly代码。现在调用时需要调整this指针的虚函数指针现在指向的便是thunk。

2. 子类指针调用第二个或后继父类函数

这个与第一种情况类似。

3. 语言扩充的性质。

允许一个virtual function的返回值类型有所变化，可能是base type，也可能是publicly derived type。

1
2

Base2 *pb1 = new Derived;
Base2 *pb2 = pb1->clone();

这有点类似于我们先前提到的子类指针赋值给父类指针。不同的是，之前可以直接在编译器加以修改，而这里因为pb1调用的函数是运行期决定的，返回值类型也是运行期决定的，所以需要进行执行期的修改。具体技术我们这里不进行讨论。

虚拟继承

就虚拟继承而言，它的内存布局是很复杂的。复杂的点在于，父类不再是子类连续内存的一部分，而是为多个子类所共享的。也就是说，对于虚基类的子类而言，虚基类的内存相对于自己的偏移是不固定的。可能现在你离我还特别近，可能在继承层次更深一点后，你离我又更远了。之前我有一个疑问就是，既然一个有虚基类的子类的布局在编译期是已知的，那直接在编译期为所有对虚基类成员的访问加上偏移不就行了吗？问题的点在于对虚基类成员的访问的访问者是谁在编译期无法确认。比方说在虚函数里访问虚基类成员，虚函数的决议本身就是运行期，况且知道是哪个虚函数也无法确定当前的偏移，所以想在编译期将一切确定下来几乎是不可能的。

这个时候我们考虑到为虚拟继承加点动态的信息。比如说B和C虚拟继承自A，D多重继承自B和C。我们可以在D的B区域加上个指针，用以指明虚基类相对于B的偏移。

这种做法固然能解决问题，但这极大增加了对象的存储负担。除此之外，我们可以直接将信息放在虚函数表里，用以指明虚基类的地址。这样就可以在运行期指明虚基类地址，并且用少量的时间换了大量的空间。

关于虚拟继承的虚表，主要是对于this的调整，关于这点建议阅读 ABI。以及下面的博客。

https://zhuanlan.zhihu.com/p/41309205