Use the same form in corresponding uses of new and delete

动机

提出这一点的原因是，delete时被删除的内存之中究竟有多少个对象，这关乎我们需要进行多少次析构函数。往往地，如果我们new与delete不匹配就会发生内存泄漏或者未定义的行为

方法

很简单：new时用了[]，delete也必须带[],否则两个都不带。

还有如果需要注意的，尽量不要对数组做typedef动作，诸如

1
2

typedef std::string Addr[4];
std::string pal = new Addr;//就像new string[4]一样

因为在这种情况下，我们不知道应该匹配数组形式的delete

建议

• new与delete的形式匹配

provide access to raw resources in resource-managing classes

动机

在条款13中，我们使用智能指针去保存一个原始资源，但有些时候AP需要绕过诸如智能指针这类资源管理对象去获得原始资源，因此我们需要留下一个途径让API有机会去使用原始资源

方法

• get()方法

在shared_ptr和auto_ptr中都提供了一个get成员函数，用来显式地返回智能指针内部的资源

1

int days = daysHeld(pInv.get())//shared_ptr<Investment> pInv

• 提供隐式转换

1
2
3
4
5
6
7

class Font{
public:
  explict Font(FontHandle fh):f(fh){}
  ~Font() {releaseFont(f);}
private:
  FontHandle f;
}

在上述RAII类中，每次要使用原始资源，都必须要利用get()方法；因此我们可以提供一个隐式的转换

1
2
3
4
5
6

class Font{
public:
  ...
  operator FontHandle() const{return f;}
  ...
}

建议

• RAII类应该提供一个访问原始资源的接口，这虽然会破环类的封装，但因为RAII的目的是保证资源的正确释放，所以影响不大
• 对资源的访问可以通过显示转换或隐式转换，个人建议显式转换，比较安全

Main memory

Background

首先提两个概念,这两个寄存器是由操作系统载入的：

• base register：存着最小的合法物理地址
• limit register：存着可用范围

• address binding：用户程序的相对地址被绑定到物理地址上，可以在编译期、加载期和运行期进行
• logical address：由CPU定义的，用户程序生成
• physical address：真实的物理地址
• memory-management unit(MMU)：负责将逻辑地址映射到物理地址
• dynamic loading：为了更好地管理内存，使得进程不受物理内存的限制
• dynamically linked libraries：通常是系统库，在执行前动态链接进来，避免占用太多内存

swapping

进程可以在内存和后台存储区（通常是磁盘）中交换。把需要的进程换进来，把暂时不用的进程替换出去

• swapping是非常耗时间的，因为在内存和外存之间的传输非常耗时间

contiguous memory allocation

通常而言，贮存会被分为两部分，一部分是给操作系统，另一部分给用户空间。

• 内存保护：limit register有一个地址空间范围，在进程被CPU执行时，这个范围会被加载进去，由操作系统进行验证；
• multiple-partition allocation：给每个进程分一个分区
• fixed partition（固定分区）
  • 超过内存大小的进程无法进行
  • 分区内部无法利用的内存变成内碎片，无法解决
• dynamic partition（动态分区）
  • 在程序装载进内存时，系统将内存划分一块大小适合的连续区域给进程
  • 操作系统自行管理已分配和空闲分区
  • 为了减少碎片：可以通过紧缩和拼接的方法
  • 三种分配算法：
    • first fit：逐个寻找适合的分区
    • best fit：选择剩下内存最小的适合分区
    • worst fit：选择剩下内存最大的分区
    • next fit：从上次查找结束并内存足够大的区域开始划分

paging

概念先行：

• frames：将物理内存分成帧
• pages：将逻辑地址分为页
  • 每个地址被分为了page number(代表着页表的项数)和page offset（代表着页的大小）
  • page number构成了page table的索引表，表中存着frame number，对应着内存中的frame

• 分页不会产生外部碎片，但有可能产生内部碎片，即每一页中的缺失

TLB

访问过程：

• 传统上需要访问物理内存两次，一次是访问获取页表的内容，另外一次是根据页表的指引去访问内存
• TLB是页表的一部分，只存有页表的部分条目，但不同于页表，TLB一般是存在cache，这样满足快速读取。
• 在进程被加载进来时，TLB会被填充，寻找frame时，CPU同时在TLB和page table中寻找。找到则返回frame，找不到则在page table中寻找

• 有效访问时间
  • TLB访问时间a
  • 内存页表访问时间b
  • 命中率c
  • 平均访问时间（有TLB）：(a+b)c + (b+b+a)(1-c)
  • 没有TLB：2*b
• 页表有一个有效位，指示该页是否在内存中有映射，否则都需要到磁盘中去找

structure of the page table

Hierarchical Paging

假如有一个32位的系统，页表大小是4KB(2^{12)，那么一个页表会含有1MB(2}20)条索引，如果一条索引4个字节，那么会产生4MB大小的页表

因此，我们可以使用二级页表，将页表分页。一个地址将会如下图所示：页目录是页表的索引，页表是进程物理空间本身的索引。

(P1是外部表的索引，P2是二级表的索引)

hashed page tables

超过32位地址空间通常是使用哈希页表

哈希页表的每一条目都包括一个链表的元素，每个元素有三个域：虚拟页码，物理帧号，指向下一个元素的指针。

通过页码途径哈希函数得到对应的条目，从而获得物理帧号。

inverted page tables

真正被使用的帧才会记录到在反向表的条目中。整个系统只有一张页表，对每个物理内存帧都只有一个条目，包括了逻辑地址和进程号。

Think carefully about copying behavior in resource-managing classes

动机

这是接上一个条款讲述的，当我们用一个对象去管理资源类的时候，我们需要注意该资源是否应该被复制。比如，一个互斥锁，是不应该拥有副本的。因此我们需要某些方法来保证管理这个锁的对象不会被复制，或者我们希望RAII对象被复制时追踪它的使用。

管理方法

• 禁止复制

使用条款6的方法，即继承一个uncopyable的类。具体可以看条款6

1
2
3
4

class Lock: private Uncopyable{
  public:
   ...
};

• 对底层资源进行“reference-count”（引用计数）

这种管理方法是因为我们希望保有资源，知道最后一个使用者被销毁时，才销毁资源。这种缘由恰好可以用shared_ptr来管理。但有一个问题是，假如我们希望管理的资源是一个互斥锁，那么我们并不希望该资源在引用计数为0时被销毁，而是解锁。

这时就需要用到删除器了。

1
2
3
4
5
6
7
8

class Lock{//这个类可以不析构，因为非静态变量在对象销毁时被析构函数收回
  public:
  	explicit Lock(Mutex* pm):mutexPtr(pm, unlock){//在引用计数为0时自动调用单参数函数unlock()
      lock(mutexPtr.get());
  	}
  private:
  	std::trl::shared_ptr<Mutex> mutexPtr;
}

• 转移底部资源的控制权

这里可以使用先前提及的auto_ptr<>

建议

• 复制RAII对象时，必须一并复制它所管理的资源
• RAII class copying的行为通常有：禁止复制，使用引用计数，转移资源的控制

操作系统结构

operating system services

• 用户接口
• 程序
• IO操作
• 文件系统
• 通讯
• 错误检测
• 资源分配
• 安全

User Operating System Interface

• command interface
  • CIL: command-line interface
  • GUI: graphics user interface
• program interface(System call)

system call

• 定义：系统调用是在用户进程和系统内核之间的程序接口
• 多数情况下，用户进程通过API而不是系统调用与内核打交道。
  • API是一组函数定义，提供了一个特定的服务；而一个系统调用时通过软中断向内核发送一个请求；
  • API可能需要一个或多个系统调用来完成其功能，如果不与内核打交道，则不需要用到系统调用；
  • 系统调用是在内核态中运行的，而API是在用户态中运行；
• 系统调用如何传递参数？有三种：
  • 在寄存器中传递，适用于参数比较少的，因此会限制参数长度；
  • 在block、table或者内存中，然后再寄存器存着所在block的地址；
  • 存在stack中，需要时则pop；

Operating system structure

• simple structure: MS-DOS
• Microkernel system structure: 由“微”内核和若个个服务组成，基本功能由中央内核提供，其它功能由独立进程提供
  • windows、Macos
• Monolithic Kernels: 内核的所有代码，包括子系统都被打包进一个文件中，内核中的每个函数都可以访问内核中所有部分
  • linux

virtual machines

虚拟机是在硬件上的一层服务，物理机的资源被用来创建虚拟机。虚拟机很好地避免了与硬件资源的直接访问

IO复用：select和poll函数

需求

当一个TCP客户同时处理两个输入：标准输入和套接字时，由于客户端阻塞于标准输入，此时服务端进程可能会被杀死。那是因为此时虽然服务端给客户端发了一个FIN，但由于客户端正在阻塞于标准输入，没看到EOF。这样的进程需要一种能力，告知内核一旦发现一个或者多个IO条件准备就绪的话，内核就要通知进程；

使用场景

• 客户处理多个描述符（网络套接字和交互式输入），必须使用；
• 既要处理监听套接字又要处理已连接套接字；
• 既要处理TCP又要处理UDP；
• 处理多个协议；

模型描述

IO多路复用模型是单个线程，通过追踪每个IO流(socket)的状态，从而达到管理多个IO流。有了这个模型，我们可以通过select或poll来具体实现这个模型，这样我们只会阻塞在这些函数的调用上，而不会阻塞在真正的IO上。

select

1
2
3

#include <sys/select.h>
#include <sys/time.h>
int select(int maxfdpl, fd_set* readset, fd_set* writeset, fd_set* exceptset, const struct timeval& timeout);

• timeout:告诉内核等待指定描述符中任意一个就绪的最长等待时间；
• 中间三个指定我们让内核测试读写和异常的文件描述符；可以通过宏来设置；
• maxfdpl则是指定待测试的文件描述符个数，选取的值是待测试的文件描述符加一；

描述符的就绪条件

• 可读
  • 该套接字的接收缓冲区中的字节数大于等于套接字接收缓冲区低水位标记的当前大小。TCP和UDP中默认为1；
  • 该套接字是一个监听套接字，且连接数不为0；
  • 该连接的读半部关闭（即接收了FIN的TCP连接）；
  • 有一个套接字错误在等待处理；
• 可写
  • 该套接字的发送缓冲区中的字节数大于等于套接字发送缓冲区低水位标记的当前大小。TCP和UDP中默认为2048；
  • 写半部关闭；
  • 使用非阻塞connect的套接字已经建立了连接，或者connect失败；
  • 有一个套接字错误待处理；

poll

1
2
3
4
5
6
7
8

#include<poll.h>
int poll(struct pollfd* fdarray, unsigned long nfds, int timeout);

struct pollfd{
  int fd;
  short events;//指定测试条件
  short revents;//返回描述符的状态
};

以下条件引起poll返回特定的revent:

• 所有正规TCP和UDP数据都被认为普通数据；
• TCP的带外数据被认为是优先级带数据；
• TCP连接的读半部关闭，即接收了对端的FIN，普通数据；
• TCP存在错误时可以认为是普通数据，也可以是错误；
• 在监听套接字上有新的连接可用，可认为是普通数据或者错误；
• 非阻塞connect的完成；

poll识别三类数据：normal、priority band和high priority

结论

IO复用模型中最常用的函数是select，我们告知select函数就读写和异常三种条件所关心的描述符、最长等待时间和最大描述符号。缺点是单个进程能够监管的文件描述符数量较少，一般为1024；

poll函数提供类似于select的功能，不过能为流设备提供额外信息。

目前来说，select函数会更加频繁。

Use objects to manage resources

动机

内存管理在C++中是非常重要而且常见的，往往会因为管理不当而出现灾难性的内存泄漏情况。首先来看一个例子：

1
2
3
4
5
6
7
8
9

class Investment;
Investment* createInvestment();

void f()
{
  Investment* pInv = createInvestment();
  ...
  delete pInv;
}

在上面的例子中，乍一看很好地管理分配的资源，但闻题在...这里，如果在delete之前函数提前返回，或者发生了异常被抛出来，那么就会导致delete语句没有被访问到，也就是发生了内存泄漏的情况。

解决方法

因此为了确保createInvestment()分配的资源被正确释放，可以把资源放到对象中进行管理，从而控制其在离开区块时因为调用析构函数而释放资源。

• auto_ptr
  • auto_ptr是一个智能指针，该指针管理的对象在析构函数时会调用delete;
  • 这是一种RAII的使用方法，即获得资源的第一时间则将其用来初始化某个对象；
  • 但这个智能指针有两个特点：
    • 会转移控制权，若通过copy构造函数或者copy赋值函数取赋值该指针，原指针会指向一个null；
    • 不能有多个auto_ptr指向同一个对象，因为这样容易导致多次delete或者未定义行为；

1
2
3
4
5

void f()
{
  std::auto_ptr<Investment> pInv(createInvestment());
  std::auto_ptr<Investment> pInv1(pInv);//pInv指向null
}

• share_ptr
  • 这类智能指针允许对象被多个指针指向，并维持一个引用计数，具体使用参考：http://www.lucienxian.top/2017/11/16/%E6%99%BA%E8%83%BD%E6%8C%87%E9%92%88%E7%9A%84%E5%AD%A6%E4%B9%A0%E2%80%94%E2%80%94CPP/

建议

• 为防止资源泄漏，应使用RAII对象，在构造函数中获得资源，在析构函数中释放资源；
• 两个常用的RAII类是：auto_ptr和shared_ptr;

Adapter

目的

将一个类的接口转换成client希望使用的另外一个接口。通过Adapter模式，两个接口不兼容的类得以协同工作。

动机

假如有一个绘图编辑器，它通过一堆图形对象为客户所操作，而这些图形对象的接口由一个Shape的抽象类定义。当我们希望使用textshape这一个子类来编辑显示正文时，难以实现，因为其涉及到了诸如缓冲刷新的问题。而此时工具包中已经提供了一个textview的类拥有这个功能，但当时工具的设计者没有提供到互相兼容的接口。

因此为了解决这个问题，我们可以使用adapter模式来使其兼容。

使用范围

• 希望使用一个已经存在的类；
• 希望创建一个可以复用的类，但该类可以与其它不相干（接口不兼容）的类协同工作；
• （仅仅适用于对象adapter）希望使用已经存在的子类，但又不希望对每一个子类匹配接口。可以使用对象adapter；

效果

针对类adapter和对象adapter，会产生不同的效果

类adapter

• 一般情况下，将adapter公共继承target，私有继承adaptee，这样就可以部分重定义adaptee的行为，也不需要额外的指针去指向adaptee

对象adapter

• 允许一个adapter和多个adaptee交互同时工作，只需要在adapter类内存有相关指针变量即可；
• 但这种方法难以重定义adaptee；

代码实例

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

// Adapter.cpp : 定义控制台应用程序的入口点。
//

#include <iostream>

using namespace std;

class Target {
public:
	Target(){}
	virtual void Request(){ cout << "Target::Request..." << endl; }
	virtual ~Target(){}
};

class Adaptee {
public:
	Adaptee(){}
	void SpecificRequest() { cout << "Adaptee::SpecificRequest..." << endl; }

};

class Adapter_class : public Target, private Adaptee{
public:
	Adapter_class() {}
	virtual void Request(){
		Adaptee::SpecificRequest();
	}
};

class Adapter_obj : public Target
{
public:
	Adapter_obj(Adaptee* adaptee) {
		_adaptee = adaptee;
	}
	virtual void Request() {
		_adaptee->SpecificRequest();
	}
private:
	Adaptee* _adaptee;
};



int main()
{
	Adapter_class adapter;//class adapter
	adapter.Request();
	cout << "............................" << endl;
	Adaptee *adaptee = new Adaptee();
	Adapter_obj adapter_o(adaptee);//object adapter
	adapter_o.Request();
	delete adaptee;
    return 0;
}

copy all parts of an object

动机

• 局部的拷贝，编译器是允许的。假如你自定义了一个拷贝构造函数或者拷贝复制函数，但函数内部只复制了部分的成员变量，那么编译器并不会报错。
• 另一个问题是在继承时，由于子类无法访问基类的私有变量，那么拷贝构造函数可能会没有拷贝所有成员变量，而是由基类的default constructor初始化成员变量；

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

class Customer{
  public:
  	...
  private:
  std::string name;
  Date last;
};

class PriorityCustomer: public Customer{
public:
  PriorityCustomer(const PriorityCustomer& rhs):priority(rhs.prioruty){}
  //在这种情况，基类成员的初始化是在default constructor中完成的
  PriorityCustomer& operator=(const PriorityCustomer& rhs){
    priority = rhs.priority;
    return *this;
  }
private:
  int priority;
};

解决方法

• 针对第一种情况，要注意在修改类之后，要同时修改两个拷贝函数；
• 第二情况，则需要让派生类去调用基类的copy函数；

1
2
3
4
5
6
7

PriorityCustomer(const PriorityCustomer& rhs):Customer(rhs) ,priority(rhs.prioruty){}
//分别调用基类的copy函数
PriorityCustomer& operator=(const PriorityCustomer& rhs){
	Customer::operator=(rhs);
  priority = rhs.priority;
  return *this;
}

注意问题

• 不应该在copy assignment操作符函数中调用copy构造函数，因为这相当于初始化一个已经存在存在的对象，这没意义，并且增加复杂度；
• 也不应该在copy构造函数中调用copy assignment操作符，这相当于在一个尚未初始化的对象身上做“对已经初始化的对象的操作”；
• 往往以上两种操作都很有可能造成循环调用；

deadlock

定义

一个进程在得不到资源之后进入等待状态，而这个状态永远不会改变，这种情况就叫做死锁。

死锁主要发生的情况就在于资源的请求与释放不合理，而这些资源包括了physical resource和logical resource（锁，信号量，文件等）

特点

发生死锁的必要不充分条件

不是独立的四个条件

• mutual exclusion：在同一时间内只有一个进程能访问该资源
• hold and wait：一个进程必须同时拥有一个资源，并且在请求另一份被别的进程拥有着的资源
• no preemption：资源不能被抢占
• circular wait：一系列的进程在循环等待，比如p1在等待p2的资源，p2在等待p3的资源，p3在等待p1的资源

利用资源分配图可以检测是否发生了死锁

在资源分配图中，顶点分为resource(R)和process(P)两种，由R指向P的称为分配边（即P已经获得R的资源），由P指向R的称为请求边（即P在请求R的资源），而边是可以动态变化的。一旦分配成功，即从请求边转化为分配边。

如下图：

那么如何检测死锁呢？

一旦成环并且环中的每种资源只有一个实例(即没有多余的资源可用时)，就会发生死锁。如下图有两个环，其中没有多余资源。

解决办法

目前有三种：

• 采取办法去避免死锁，保证系统永远不会进入死锁状态；
• 允许系统进入死锁状态，检测出来然后恢复；
• 忽略死锁，然后假装死锁没有发生过；

大多数操作系统采用第三种。

deadlock prevention

使得前面提到的那四个死锁发生的必要不充分条件之一不成立，即可以避免死锁

• mutual exclusion：某些资源可以允许多个进程访问，比如read-only file。但互斥锁不能允许多个进程访问，因此这个方法不能采用。
• hold and wait：一个方法是实现一个协议使得进程应该一次性获得所有资源；另一种方法则是要求实现一个协议使得进程在释放所有资源之前，不能请求资源；但这两个方法有很多缺点：一是资源的调度效率很低，有些不用的资源却一直hold住。二是有可能发生饥饿，有可能想要的资源因为其它进程hold住而一直等待。
• no preemption：实现抢占式。一般应用在那些保存方便，易于重新加载的资源（比如寄存器）。但不能用在互斥锁和信号量。
• circular wait：举个例子，可以实现一个协议使得进程在请求资源时，按照资源id，从大到小去请求（也就是设置一个资源请求顺序）

deadlock avoidance

了解额外信息，决定资源如何分配

• safe state：系统以某些分配顺序去分配资源，不会发生死锁。这个顺序也叫safe sequence
• 算法一：resource-allocation-graph algorithm
  • 还是利用资源分配图表示，但此时由p指向r的虚线表示p请求资源；
  • 在多个进程请求资源资源时，系统会检测分配该资源给某个进程后，该图会否成环
• 算法二：banker's algorithm
  • 算法一 只适合于某种资源只有一个实例的情况；
  • 数据结构：available(某种资源的可用数量)、max(nxm的矩阵，某个进程Pi需要Ri资源的最大数量)、allocation(nxm的矩阵，某个进程Pi已经得到Ri资源的数量)、need(还需要多少资源)；need = max - allocation
  • safety algorithm：

1
2
3
4
5
6
7

初始化Work=avaliable和finish=false；//数组
2：找一个索引i满足：finish[i]=false && need[i]<=work[i]
如果不存在这个i，就goto4
work = work+allocation
finish[i]=true
goto2
4：如果所有都完成了，那么系统是安全状态

​ resource-request algorithm：

1
2
3
4
5

//requesti[ij]=k意味着进程i需要j类资源k个
//如果发生了请求,模拟一下操作
1. if requesti<=needi；goto 2; else 出错
2. requesti<=available;goto 3；else waiting
3. available -= request; allocation += quest; need -= quest

deadlock detection

如果系统没有采用以上两种死锁避免方法，就必须要有算法检测系统是否发生了死锁，并且使得系统从死锁中恢复

• 假如每种资源只有一个实例，可以采用wait-for 图来检测死锁是否发生（Pi指向Pj意味着Pi在等待Pj释放资源）。如果改图含有环，则意味着死锁发生了
• 假如每种资源含有多个实例，那么可以采用以上的safety算法，只要在最后检查每个finish是否都是true即可

recovery from deadlock

当检测到死锁发生时，需要从死锁中恢复

• 中断一个或多个进程的运行，打破成环
• 抢占资源：关键是要选择抢占谁的资源；实现回滚；并且如何避免饥饿的发生