发表于

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的资源），而边是可以动态变化的。一旦分配成功，即从请求边转化为分配边。

如下图：

img

那么如何检测死锁呢？

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

img

解决办法

目前有三种：

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

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

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

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

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

发表于

Have assignment operators return a reference to *this

为什么

其实返回void，返回对象本身等都是可以的，返回引用是为了一下两个原因：

  • 允许连续赋值
  • 防止返回对象时因为调用拷贝构造函数和析构函数带了不必要的开销（而且如果对象没有自定义拷贝构造函数，可能会产生错误）

场景

  • 连续赋值如下，因此为了实现连续赋值，必须返回一个引用指向自身，这样后面的赋值才能生效；
1
2
int x, y, z;
x = y = z = 15;//等价于x = (y = (z = 15))
  • 有些场景下，必须返回指向自身的引用
1
2
3
4
5
6
7
8
9
10
11
12
class Widget{
public:
	...
	Widget& operator+=(const Widget& rhs){//此举是因为该操作符本身的意义就是自增，然后返回自身值
      ...
      return *this;
	}
	Widget& operator=(const Widget& rhs){
      ...
      return *this;
	}
}

Handle assignment to self in operator=

动机

client在操作时很可能会出现，自我赋值的情况，比如：

1
2
a[i] = a[j]; // i == j时
*px = *py; //px与py恰好指向同一对象时

这种情况下，往往会出现安全性缺失的问题

1
2
3
4
5
6
7
8
9
10
class Bitmap{};
class Widget{
public:
	Widget& operator=(const Widget& rhs){
      delete pb;//如果是自我赋值，删除pb之后会连rhs里的内容也删除了
      pb = new Bitmap(*rhs.pb);
      return *this;
	}
Bitmap* pb;
};

方法

  • 检查合法性
1
2
3
4
5
6
Widget& operator=(const Widget& rhs){
  if (&rhs == this) return *this;//如果是自我赋值，不做任何操作
  delete pb;
  pb = new Bitmap(*rhs.pb);
  return *this;
}

但这个版本仍具有安全问题，如果new时抛出了异常，这样this会指向一块被删除了的内存；

  • 保证异常安全性
1
2
3
4
5
6
7
Widget& operator=(const Widget& rhs){
  Bitmap* temp = pb;
  pb = new Bitmap(*rhs.pb);
  //即便new出现了异常，但由于我们生成了副本指针，因此能够保证this指向有效内存并且影响自我赋值的安全性
  delete temp;
  return *this;
}

这个方法会降低效率，因为需要拷贝构造的函数

  • copy&swap

这是一种更加高效的做法

1
2
3
4
5
Widget& operator=(const Widget& rhs){
  Widget temp(rhs);
  swap(temp);//交换temp与this的指针
  return *this
}

建议

  • 令赋值操作返回一个reference to *this
  • 确保自我赋值时的安全性，可以采用比较两个对象的地址是否相同，调整操作里的语句顺序，使用copy&swap的方法

发表于

Prototype

目的

用原型实例指定创建对象的种类，并且通过拷贝这些原型创建新的对象

动机

假设有一个框架，并希望增加一些表示符、休止符等对象来构造。我们可以为每个对象构造一个子类，但如果对象太多，子类太多不方便管理。因此为了解决这个问题，我们可以让框架通过拷贝或克隆一个graphic子类的实例来创建一个graphic。

使用范围

  • 希望动态加载类的实例时；
  • 为了避免创建一个与产品类层次平行的工厂类层次；
  • 当一个类的实力只能有几个不同状态组合中的一种时，可以通过建立一定的数量的原型，并通过克隆其建立对象；

效果

  • 动态添加和删除产品（客户能直接接触产品）
  • 随时改变结构，只需要通过修改参数值就可以生成新的对象；
  • 与factory method相比，子类的构造会更少；

由于是基于clone操作，因此内部存在不支持拷贝的对象会难以实现

代码示例

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

class Prototype {
protected:
	Prototype() { std::cout << "Prototype" << std::endl; }
public:
	virtual Prototype* clone() const= 0;
	virtual ~Prototype() { std::cout << "~Prototype" << std::endl; }
};

class ConcretePrototype1 : public Prototype{
public:
	ConcretePrototype1(){ std::cout << "Prototype---A" << std::endl; }
	virtual ~ConcretePrototype1() { std::cout << "~Prototype---A" << std::endl; }
	ConcretePrototype1(const ConcretePrototype1&) { std::cout << "copy PrototypeA" << std::endl; }
	virtual Prototype* clone() const{
		return new ConcretePrototype1(*this);
	}
};

class ConcretePrototype2 : public Prototype {
public:
	ConcretePrototype2() { std::cout << "Prototype---B" << std::endl; }
	virtual ~ConcretePrototype2() { std::cout << "~Prototype---B" << std::endl; }
	ConcretePrototype2(const ConcretePrototype2&) { std::cout << "copy PrototypeB" << std::endl; }
	virtual Prototype* clone() const {
		return new ConcretePrototype2(*this);
	}
};

class Manager {
public:
	Prototype* _prototype1;
	Prototype* _prototype2;
public:
	Manager(){}
	void register_protype(Prototype* p1, Prototype* p2) {
		_prototype1 = p1->clone();
		_prototype2 = p2->clone();
	}
	~Manager() {
		/***It's safe to delete null pointer******/

		/*	_GLIBCXX_WEAK_DEFINITION void  
		 *	operator delete(void* ptr) throw ()  
		 *	{  
		 *	  if (ptr)  
		 *	  std::free(ptr);  
		 *	}  
		 */
		delete _prototype1;
		delete _prototype2;
	}
};

int main()
{
	Manager manager;
	Prototype* p1 = new ConcretePrototype1();
	Prototype* p2 = new ConcretePrototype2();
	manager.register_protype(p1, p2);
	delete p1;
	delete p2;
    return 0;
}


发表于

Never call virtual functions during constructions or destructions

声明结论：不应该在构造函数和析构函数执行期间调用虚函数

动机

如果基类中定义了一个虚函数，那么在派生类中

  • 如果是构造函数调用了该虚函数
    • 那么虚函数起不到多态作用，原因是派生类的构造顺序是先基类后派生类，而此时基类中如果调用了虚函数，那么该虚函数的调用版本为基类的版本。因为在基类构造时，派生类的成员变量还没初始化，因此C++拒绝调用派生类版本的虚函数；
  • 如果是析构函数调用了该虚函数
    • 同理，析构函数的析构顺序是先派生类后基类，如果派生类析构完成员变量后，这些成员变量变成了未定义的。而此时如果到基类的析构函数，那么调用的版本变成了基类版本；

方法

如果真的要在构造函数中调用一个动态函数，那么可以把该函数改造为non-virtual，然后将该函数的信息向上传给基类的构造函数。

1
2
3
4
5
6
7
8
9
10
11
12
class Transaction{
public:
  explict Transaction(const std::string& logInfo){logTransaction(logInfo);}
  void logTransaction(const std::string& logInfo) const;
};

class BuyTransaction:public Transaction{
public:
	BuyTransaction(para):Transaction(createLogString(parameters)){}//向上传递信息
private:
	static std::string createLogString(para)
}

建议

  • 构造和析构函数期间不要调用virtual函数。。。。

发表于

Prevent exceptions from leaving destructions

动机

  • 一种情况下，如果析构函数抛出了异常，则该异常点后面的程序将无法执行，而如果这些对象不能正常释放，则有可能造成内存泄漏的情况；
  • 另一种情况则是，假设前面有异常被抛出，而后面的对象仍在执行正常的销毁，而此时后面的对象也抛出了异常，在两个异常同时存在的情况下，会导致不明确行为，程序崩溃。

方法

如果析构函数不得已执行一个有可能抛出异常的动作，那可以用两个方法解决：

  • 让析构函数自行处理
1
2
3
4
5
6
7
DBConn::~DBConn()
{
  try{db.close();}
  catch(...){
    ....//处理掉异常，并做记录
  }
}
  • 直接结束程序
1
2
3
4
5
6
7
8
DBConn::~DBConn()
{
  try{db.close();}
  catch(...){
    ....//处理掉异常，并做记录
    std::abort();
  }
}

有时候，析构函数处理掉异常不是一件好事，因为我们不知道“某些行为失败了”；但有时为了让程序忽略掉错误继续运行，这又是一件好事。

  • 也可以重新设计接口，让客户自身去处理异常，比如上面代码的close()函数；
1
2
3
4
5
6
7
8
9
10
11
12
class DBConn{
  public:
  	void close(){
      db.close();
      closed = true;
  	}
  ~DBCconn(){
    if (!closed){
      try....
    }
  }
}

建议

  • 析构函数不能抛出异常。如果实在要抛出异常，可以选择让析构函数捕捉该异常，并使其限制在析构函数内或者直接结束函数；
  • 如果客户需要对某个操作函数的异常做出反应，我们应该为其提供一个普通函数，而不是在析构函数中执行该操作；

发表于

Factory method

目的

定义一个用于创建对象的接口，让子类去决定实例化哪一个类

动机

一个框架通过抽象类来定义对象之间的关系，并且客户通过子类来定义相关对象的实现。假设有一个应用框架来显示文档，画图框架显示画图文档等，我们需要具体的子类来重定义创建文档的操作，而这个操作就叫做抽象方法。

使用范围

  • 当一个类不知道它所创建的对象的类的时候；
  • 当一个类希望它的子类来指定创建哪个对象的时候；

效果

  • 工厂方法不会将与特定的应用有关的类绑定到代码中，代码仅仅处理product的接口；
  • 客户为了创建一个product，往往需要创建一个具体的creator；

与abstract factory不同的是，factory method的工厂仅仅是一个方法，而抽象工厂里的工厂是一个类。因此抽象工厂里，客户在使用时，产品本身是固定死的；而工厂方法则需要使用到产品本身（接口）。总结就是，抽象工厂看不到产品，因此需要使用客户端和更换工程，而工厂方法直接使用产品，从而生产产品；

代码示范

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
// Factory_method.cpp : 定义控制台应用程序的入口点。
//

#include <iostream>

using namespace std;

class Product {
public:
	Product() { cout << "Product..." << endl; }
	virtual void partA() { cout << "partA..." << endl; }
	virtual void partB() { cout << "partB..." << endl; }
};

class derivedPro : public Product {
public:
	derivedPro() { cout << "derived Product..." << endl; }
	virtual void partA() { cout << "derived partA..." << endl; }
	virtual void partB() { cout << "derived partB..." << endl; }
};

class Creator {
public:
	Product* getProduct() {
		if (_product == 0) {
			_product = createProduct();
		}
		return _product;
	}
protected:
	virtual Product* createProduct() = 0;
private:
	Product* _product;
};

template <class TheProduct>
class standardCreator :public Creator {
public:
	virtual Product* createProduct();
};

template <class TheProduct>
Product* standardCreator<TheProduct>::createProduct() {
	return new TheProduct;
}

int main()
{
	standardCreator<Product> myCreator1;
	Product* p = myCreator1.getProduct();
	p->partA();
	p->partB();

	standardCreator<derivedPro> myCreator2;
	Product* q = myCreator2.getProduct();
	q->partA();
	q->partB();
    return 0;
}

发表于

Declare destructions virtual in polymorphic base classes

动机

在某些情况下，当一个derived class对象是经由一个base class指针被删除时，而base class着一个non-virtual 的析构函数。此时实际执行的效果是，对象的derived成分并有被销毁，销毁的是base成分。这种局部销毁会造成资源泄漏。

方法

  • 一个意图被用作base class的class，应该令其析构函数为virtual。

具体用法和原因参考：虚函数的学习

  • 另外需要注意的是，一个不打算被用作base class的class，不应该令其析构函数为virtual。原因是：
    • 实现virtual函数的类的体积往往会增大50%到100%，这就造成一个问题是，该类的对象不能被塞到一个预先定义好的缓冲器里面，并传给其它语言的函数，也不能和其他语言（如C）的相同声明有着同样的结构；
    • 因此往往是只有当class内至少包含一个virtual函数，才为其声明virtual析构函数；

建议

  • 多态性质的基类应该声明virtual 函数；
  • 不作为基类使用的类，就不应该声明virtual函数；

发表于

Explicitly disallow the use of complier-generated functions you do not want

动机

在某些时候，我们不希望某个对象能被拷贝或者赋值，因此我们需要某些方法来阻止对象被拷贝或复制。

方法

  • 将成员函数定义为private，并且不去具体实现它们；这样可以避免friend函数和member函数取调用它们；
1
2
3
4
5
6
7
8
class myClass{
  public:
  	...
  private:
  	...
  	myClass(const myClass&);
  	myClass& operator=(const myClass&);
};

此时如果client试图拷贝类对象，编译器会报错；而当friend函数和member函数试图去调用，链接器则会报错；

  • 另一种方法则是定义一个uncopyable的基类，让那些不希望被拷贝的类继承该基类
1
2
3
4
5
6
7
8
9
10
11
12
13
class unCopyable{
  public:
  	unCopyable();
  	~unCopyable();//允许派生对象去构造和析构
  private:
  	...
  	unCopyable(const unCopyable&);
  	unCopyable& operator=(const unCopyable&);
};

class myClass : private unCopyable{
  ... //不再声明copy构造函数和copy赋值函数
}

这种操作可以使得任何调用（包括member函数和friend函数）尝试去拷贝的都会被编译器驳回，因为这种函数的“编译器生成版本”在尝试调用其基类的对应生成时发现基类的拷贝构造和拷贝赋值都是private的

建议

  • 为驳回编译自动生成的函数，可以将相应的成员函数声明为private并且不予实现；或者继承一个如上的unCopyable的基类；

发表于

Builder

目的

构造一个复杂的对象，并且构造与表示分开，同一个构建方式能达到不同的表示

动机

假设有一个富文本的编辑器，你需要将RTF转换为多种不同的正文格式（比如普通的ASCII文本或者能进行交互的窗口），倘若需要转换很多种文本格式，那么我们就需要快速实现新的转换方式。因此我们可以构建一个文本转换器，在读入不同的标记时进行不同的转换。

使用范围

  • 构建对象的算法与对象的组成部分无关；
  • 构造的对象要有不同表示，即可能由不同的组件组成；
  • 角色：
    • builder：创建一个product的各个组件时，提供接口；
    • concretebuilder：具体实现builder的接口并提供返回产品的接口；
    • director：蓝图，指导builder如何构造产品；
    • product：被构造的对象；

效果

  • 可以根据蓝图（director）随机修改产品的内部表示；
  • director可以复用builder封装的接口去生成product；
  • 精装控制product的构造，这也是与abstract factor不同的地方，后者着重在生成一系列统一风格的product，前者可以一步一步地控制product的生成；

代码示范

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
// Builder.cpp : 定义控制台应用程序的入口点。
//

#include <iostream>

using namespace std;

class Product {
public:
	Product() { cout << "A product..." << endl; }
};

class Builder {
public:
	Builder() = default;

	virtual void BuildA(){}
	virtual void BuildB(){}
	virtual void BuildC(){}

	virtual void buildPro(){}

	virtual Product* GetProduct() { return NULL; }

};

class concreteBuilder : public Builder{
public:
	concreteBuilder() { product = 0; }
	virtual void buildPro() { product = new Product; }
	virtual void BuildA() {
		cout << "build a" << endl;
	}
	virtual void BuildB() {
		cout << "build b" << endl;
	}
	virtual void BuildC() {
		cout << "build c" << endl;
	}

	virtual Product* GetProduct() {
		return product;
	}
private:
	Product* product;
};

class Director {
public:
	Product* create(Builder& builder) {
		builder.buildPro();
		builder.BuildA();
		builder.BuildA();
		builder.BuildB();
		builder.BuildC();

		return builder.GetProduct();
	}
	Director(){}
};


int main()
{
	Director director;
	concreteBuilder concretebuilder;
	director.create(concretebuilder);
	Product* pro = concretebuilder.GetProduct();

	delete pro;
    return 0;
}


发表于

Know what functions C++ silently writes and calls

关于类的构造、析构、和拷贝构造、拷贝赋值函数

  • 如果自定义类时没有创建构造函数、析构函数、拷贝构造函数和拷贝赋值函数，编译器会默认为类创建；

  • copy构造函数和copy赋值函数，编译器创建的版本只是简单地将类中每一个non-static对象拷贝到目标对象；

问题

  1. 类中的成员变量为引用类型，此时使用默认函数容易出错；
1
2
3
4
5
6
7
8
9
10
11
12
template<class T>
class NamedObj{
  public:
  	NamedObj(std::string& name, const T& value);
  private:
  	std::string& nameValue;
  	const T& objValue;
};

NamedObj<int> p("dog", 2);
NamedObj<int> q("cat", 3);
p = s;
  • 倘若该例子没有错，那么p.nameValue和s.nameValue是否指向同一个string呢？如果指向同一个对象，你们就意味着reference被改变了，但是C++不允许reference改变指向不同的对象；
  • 此时，编译器会拒绝编译这一行的赋值；

  1. 同理，对面对const成员变量也一样。由于更改const是不合法的，因此编译器也会拒绝进行赋值；

  2. 如果某个基类将copy赋值函数声明为private的，那么编译器会拒绝为派生类生成一个copy赋值函数，因为编译器需要权限去处理基类的成分（在编译时，编译器会假设copy赋值函数需要处理基类的成分）。

提醒

  • 编译器会暗自创建构造函数、析构函数、拷贝构造函数和拷贝赋值函数；