发表于

Declare data members private

动机

  • 首先是避免程序员考虑应该使用括号还是不需要使用，保证一致性
  • 其次是可以保证对成员变量的精确控制，细微划分访问控制

根据书中观点：封装性与“当其内容改变时可能造成的代码破坏量”成反比

建议

  • 切记将成员声明为private，这可赋予客户访问数据的一致性，可细微划分访问控制，允诺约束条件得到保证，并提供class作者以充分的实现弹性
  • protected并不比public更具封装性

发表于

linux进程管理

概念

  • 资源分配的基本单位；
  • 调度的基本单位
  • 当程序在系统中运行时，形成一个进程
  • 组成：
    • text：代码
    • 用户数据段：进程处理的数据
    • 系统数据段：包括PCB
  • 进程状态
    • TASK_RUNNING
    • TASK_INTERRUPTIBLE
    • TASK_UNINTERRUPTIBLE
    • TASK_STOPPED
    • TASK_TRACED：被跟踪，一般调式时用到
    • EXIT_ZOMBIE：进程结束前的状态
  • EXIT_DEAD

task_struct

  • PCB的数据结构，进程存在的唯一标识
  • 进程创建时，就会建立一个task_struct，在专门存储task_struct的地方存放着。有最多进程数限制
  • 主要组成：
    • 进程标识号，pid；
    • 进程的虚拟内存信息：struct mm_struct* mm
    • 进程打开的文件：struct files_struct *files
    • 进程映像所在的文件系统：struct files_struct *files
  • 内核2.8后用thread_info替代了task_struct的位置，该结构内部有一个指向task_struct的指针

进程创建

  • 通过fork()创建
  • 子进程继承了父进程的资源（只读）
  • 写时拷贝
  • 子进程通过exec()执行真正的任务
  • 注意：
    • 父进程执行fork()返回的是子进程的pid
    • 子进程执行fork()返回的是0

linux内核线程

  • linux中线程也有自己的task_struct结果
  • 但其共享进程的资源
  • 内核线程：在内核态下创建，独立执行的一个内核函数

linux的进程调度

  • 抢占式，无论是内核态还是用户态都可以抢占

  • 分时技术：根据进程优先级去分配时间片

  • 时间片轮转：对于优先级相同的进程，使用时间片轮转的方法

  • linux有两种进程：普通进程（100149）和实时进程（099）

    • 实时进程优先级更高：有FIFO和RR两种策略
    • 普通进程只有时间片轮转算法

发表于

linux内存管理

虚拟内存空间的管理

  • linux操作系统采用的是请求式分页虚拟内存管理
  • 每个进程有独立的4GB的虚拟内存空间

IA32体系结构具有两种内存管理模式：

实模式

保护模式

  • 逻辑地址到物理地址的转换：
    • 逻辑地址——>线性地址（虚拟地址）——>物理地址
  • 内核空间到物理内存的映射
    • 内核空间由所有进程共享，存放着内核代码和数据
    • 内核空间映射到物理内存总是从最低地址开始，建立线性关系
    • 系统启动时，内核映像被装载到物理地址1MB开始的地方

进程用户空间

linux把进程的用户空间划分成一个个区间。

  • 一个进程的用户进程空间由mm_struct结构描述（对进行的整个用户空间进行描述，memory descriptor）
  • vm_area_struct结构是虚存空间的一个连续区域，所有的该结构体组成一个单链表，在这个区域里的信息具有相同的操作和访问特性。vm_mm指针指向mm_struct结构体；vm_strart和vm_end是虚拟区域的开始和终止地址

创建进程用户空间

  • 通过fork()系统调用，在创建新进程的同时，也为该进程创建完整的用户空间
  • 新进程的用户空间——copy_mm()，通过写时复制技术创建的

linux的分页内存管理机制

linux总是假定处理器支持三级页表结构（对于IA32，把PGD和PMD合二为一）：

  • 页目录PGD
  • 页中间目录PMD
  • 页表PTE

内核2.6.11之后采用四级页表模型

  • 线性地址到物理地址映射（以IA32为例）
    • 页目录：高10位
    • 页表：中间10位
    • 偏移：低12位，用来表示在一个页帧中的偏移
    • 每个进程都有一个页目录。由寄存器CR3指向该页目录的基地址
  • 缺页异常：
    • 编程错误
    • 操作系统故意引发的异常
    • 缺页异常的处理程序是do_page_fault()函数：该函数有两个参数：一个是发送异常地址；一个是错误码；
    • do_page_fault()执行过程：从CR2得到发送异常的线性地址；使用LRU去换页，为每个页面设置一个age，年纪越大，越容易被换
  • 交换机制：当物理内存小于一个固定的极限时，就会执行换出操作

物理内存的管理

定义

页帧：物理内存是以页帧为基本单位的，IA32为4kb

结点：访问速度相同的一个内存区域，与处理器相关联

zone：根据用途不同，将不同结点的物理内存分成不同的zone

linux对于zone曹勇buddy system管理

page结构

页帧是由page结构体表示的。

物理内存的分配和回收

  • buddy分配

物理内存采用的是buddy分配算法，最小的分配单位是页帧，目的是分配一组连续的物理页帧。

buddy：两组连续的页帧，满足——大小相同；物理地址连续；第2个页块后面的页帧必须是2n的倍数。

buddy算法把内存中的所有页帧按照2^n划分，分成1，2，4，8.。。。。1024一共11种页块，每个页块组用一个双向循环链表进行管理，也就是一共有11个链表

比如free_area[0]指向1页帧块的链表

比如free_area[2]指向4页帧块的链表

  • 内存回收
    • 回收时需要检查与该页帧相邻的空闲页块，若存在则需要合成一个连续的空闲区，按buddy算法重新分组
  • slab分配器
    • 为了解决buddy算法以页帧为基本分配单位可能造成的内部碎片
    • 基本思想：为经常使用的小对象建立缓冲，小对象的申请和释放由slab分配器管理，不与buddy系统打交道

发表于

linux文件系统

定义

linux文件系统是一种机制或者说是一种协议，它用来组织存储设备上的数据和元数据。在linux文件系统中采用了多级目录的树型层次结构去管理文件，用/表示。linux系统的文件系统都会安装到一个目录下，并隐藏了该目录的原有内容，这个目录叫做安装目录或者安装点。

linux缺省的文件系统是ext2/ext3/ext4，继承自unix，这种文件系统把文件名和文件控制信息分开管理，文件控制信息组成一个inode结构。

文件类型

  • 普通文件，文件名不超过255字符
  • 目录文件：. 为目录本身，.. 为父目录
  • 字符设备文件/块设备文件：linux把设备的I/O作为对文件读写
  • 管道文件：进程间通信
  • 链接文件：符号链接文件，可以实现共享文件
  • socket：网络文件

/proc文件系统

  • 虚拟文件系统，用来获取系统的状态信息，并且可以改变系统的配置信息

VFS虚拟文件系统

为了使得各种物理文件系统能够转换成具有统一共性的文件系统，对各种文件系统进行抽象，linux使用了一种虚拟文件系统。

另外VFS其实不是一种实际的文件系统，因为它不是存在于外存的，VFS是仅仅存在于内存。

作用

假如用户输入 cp /floopy/TEST /tmp/test，其中前者是MS-DOS磁盘的挂载点，后者是ext2文件系统的一个目录，但因为VFS提供了系统调用接口，使得cp不用理会两者的文件系统而进行文件操作

VFS文件系统的结构

文件模型：

  • superblock：存储了已安装系统的信息，对应于物理文件系统的文件系统超级块
    • VFS把不同的文件系统中的组织结构信息进行抽象，形成了统一的、兼顾各种不同文件系统的统一的超级块。
    • 在具体文件系统安装时建立，在卸载时删除
    • 结构内有两个重要变量
      • s_type：指向文件系统类型的指针
      • s_op：指向超级块（一个叫super_operations的结构）操作的指针，通过指向的那个操作结构，就可以得到包含着的一系列操作指针
  • inode object：存储文件信息
    • VFS的inode对象存在于内存。而物理文件系统的inode对象存在于外存，并长期存在
    • 有一个i_op指向inode_operations的结构
  • dentry object：描述一个目录项
    • 为了加速访问，VFS文件系统维护着一个目录项的缓冲
  • file object：存储一个打开文件和一个进程的关联信息
    • 与进程相关
    • 在open()时创建，close()时销毁

文件类型的注册

linux支持的文件系统必须先注册后才能使用，注册有两种方式：

  • 在系统引导时在VFS中注册
  • 把文件系统做成可装载模块，在安装时在VFS中注册

注册后的文件系统会登记在file_system_type结构中，从而组成一个注册链表

文件系统的安装

把ext2/3/4文件系统的磁盘分区作为系统的根文件系统，其它文件系统则安装在根文件系统下的某个目录下，成为系统树形结构的分支

安装命令： mount -t vfat /dev/hda5 /mnt/win；

mount -t ext2 -i loop ./myfs /mnt

文件的管理与操作

对于打开的文件，有两种管理方式：

  • 通过系统打开文件表进行统一管理
    • 把所有进程打开的文件集中管理，组成一个双向链表，每个结点就是一个file结构
  • 进程的私有数据结构进行管理
    • fs_struct结构记录进程所在文件系统的根目录和当前目录
    • files_struct结构包含着进程的打开文件表，打开的文件会建立一个file结构，该结构的地址会写到fd[]数组的第一个空闲元素，因此fd数组的下标则为文件描述符

文件的open操作

  • 对应的内核函数是sys_open()

文件的read操作

  • page cache：由于需要减少IO的次数，linux在读写文件时采用了页缓冲，对文件的读写需要经过页缓冲

ext2文件系统

  • 实现了符号链接的方式
  • ext2分区的第一个磁盘块用于引导

发表于

linux系统调用

WHY

  • 系统调用时内核向用户进程服务的唯一方式；
  • 通过系统调用，用户程序从用户态切换到核心态，从而访问内核资源
  • 好处：
    • 安全，避免访问内核资源
    • 抽象：使得编程更加方便
    • 统一：接口统一，便于移植

x86的运行模式、地址空间与上下文

  • linux使用了两个运行模式
    • 特权级0：内核模式
    • 特权级3：用户模式
  • 地址空间
    • 用户空间
    • 内核空间：3G~4G
  • 上下文
    • 用户级上下文：代码、数据、用户栈、共享存储区
    • 系统级上下文：PCB（task_struct）、MMU、内核栈
    • 存储器上下文：各种存储器、栈指针

系统调用、API库和C库

  • API是一组函数定义，遵循POSIX标准，说明了如何获取一个特定服务；
  • 系统调用则是通过软中断向内核发出请求，每个系统调用对应于一个内核函数，系统调用被使用时，会切换到内核态去找内核函数执行；
  • C库函数中包含了部分系统调用，实现了linux主要的API；
  • 操作系统命令则比API更高一层，包含了一个或多个API

系统调用处理过程

  • 应用程序调用C库函数
  • 通过软中断int 0x80进入内核，中断程序将参数，一般是系统调用号放在寄存器eax上传到内核
  • 调用system_call函数，保存系统调用号和所有需要的寄存器到栈中；保存PCB的地址；检查系统调用号；有效则根据系统调用号表去调用内核函数（特定的服务程序）
  • 转入ret_from_sys_call例程，返回

发表于

virtual memory

background

执行一个只有部分大小在物理内存中的程序，好处是：

  • 程序不受物理内存限制，用户能够随意地在虚拟内存中编写程序
  • 因为用户程序使用了更少的物理内存，因此有更多程序同时运行，提高CPU利用率
  • I/O的操作更少了

虚拟内存允许文件共享：

  • 系统库能被多个进程共享，尽管每个进程都视系统库为自己的部分，但实际上系统库是在物理内存上的一块空间中；
  • 多个进程能够共享数据，某个进程能在真实的物理内存中开辟一块空间与其它进程共享；
  • pages在进程创建时能被共享，提高创建进程效率

demand paging

一个程序在被加载进内存时有两种方法：一个是整个装载进去，一个是当你有需要的时候再从disk读到memory，而后者就是demand paging。

为了实现这个方法，我们需要硬件来支持该页是否在内存中，因此可以在page table中设置一个有效位。

访问到一个标记为invalid的页，则叫page fault。此时系统中断，操作系统去从disk中加载该页进内存中。

performance of demand paging

  • p：page fault的概率
  • ma：访问内存的时间
  • pft：发生page fault需要处理的时间（主要是读取page）

有效访问时间 = (1-p) * ma + p*pft

copy-on-write

这个方法的提出是基于系统调用fork()导致的性能下降。在子进程fork一个父进程之后，如果直接将父进程的内存复制一份，考虑到子进程与父进程之间有不少数据内容是一样的，因此可以共享这部分数据，这就是copy-on-write。

步骤如下：

  • 子进程从父进程fork出来，此时两个进程共享同一份内存；
  • 当子进程要修改该共享内存的内容时，则先copy需要修改的页，接着修改复制出来的page；

如下图，当process1要修改pageC的内容时，会先复制一份pageC

img

由于copy-on-write需要找到一个可用的page，所以操作系统的做法是维护一个pool，随时取出来；

linux系统下提供了vfork()，这个系统调用并不会copy-on-write，而只是共享内存，因此要保证子系统不会轻易修改数据；

page replacement

当一个进程在执行时发生了page fault，当此时没有可用的内存，那么操作系统需要决定去替换一个页，至于替换方法有两种：

一种是直接terminate那个进程，但这不是一个好的方法，因为分页操作应该对用户是透明的（不懂？）

另一种则是交换进程，先把某个进程所有的frame释放了，降低cpu利用率

现在我们来考虑第三种方法page replacement

basic page replacement

发送basic page replacement时，操作系统会做以下操作：

  • 在disk发现自己想要的page；

  • 如果内存中没有可用frame，则用replacement 算法去置换一个frame；

  • 将内存中选中的victim frame写进disk

  • 修改page和frame的表内容

  • 将disk中想要的page写进空出来的frame

  • 重启进程

    但这里会有一个问题：每次发生置换都需要两个pages的传送，需要大量的IO操作，因此为了提高效率，可以在page中增加一个modify bit(dirty page)

    这个bit用来指示，该page在上一次从disk都出来之后有没有被修改过

    因此就可以在replacement时检测这个bit，只有dirty的才会需要被写回disk，否则直接从disk读取想要的pages覆盖那个frame即可；

reference string

  • 这个概念是用来评估replacement算法效率的（还需要知道内存的frame大小），用来记录每次对memory的引用
  • 通常是page number
  • 例如访问的地址为0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105
  • reference string就是1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1

FIFO page replacement

这是最基本的置换算法，很简单，就是维护一个队列，队列按时间连接，即最新的frame在队列尾。每次置换队列头的frame；

但这个算法有一个bug，具体可以参考Belady’s anomaly。即它可能会随着分配的内存即frame增多，它的page fault rate反而增大。

optimal page replacement

这是效率最高的算法，也是发送page fault可能性最小的一个算法。简单概括就是：

置换内存中某个frame，该frame在这时候很久才会被再次引用，这里的很久指的是相对其它frame要久

但这个算法不好实现，因为很难去判断未来在什么时候才会再次引用该frame

LRU page replacement

  • least recently used algorithm

这是综合以上两种算法的算法，往前追溯reference string，找到距离现在最久的frame，置换该frame

这里介绍两种实现方法：

  • counter

    • 设置一个时钟，每次内存访问的时候，时钟就会加一；
    • 所访问的page，就会在page table里面的time to use设置时钟值；
    • 这样，只要每次遍历一下page table，即可找到最小的page，这就是我们要置换出去的frame；

  • stack

    • 其实是一个双向列表。。
    • 即维护这样一个stack，每次引用到page时，则从stack中抽取该page放到stack的顶部；
    • 那样，最下面的page则是要置换出去的frame；

    ​

LRU-Approximate Page Replacement

多数硬件都会提供一个支持——reference bit，用来指示该page是否被使用过（读写）

Additional-Reference-Bits Algorithm

假设reference有8位，每个时钟周期该8位reference bit就右移一次，如果该周期内内存有被引用，则设最高位为1，否则设为0。这样，将8位reference bit转换成无符号整数，最小的page则为LRU page

second-chance algorithm

实现这个算法的基础是维护一个循环队列和一个指针，队列中的page都有一位reference bit，指针指向要替换的page

  • 检查reference bit，如果该位为1；
  • 指针下移，直到找到reference bit为0的page；
  • 做替换

在最坏的情况下，指针会遍历一遍，将所有page的reference bit清零

enhanced second-chance algorithm

相对second-chance algorithm，这个算法添加了1bit，作为检查该bit是否被修改，即modified bit。

这样就将pages分为了四类：

  • (0, 0)：最好的选择，最近没有用过，并且没有修改过；
  • (0, 1)：次好的选择，最近没有用过，但修改过；
  • (1, 0)：次差选择；
  • (1, 1)：最差的选择

这种算法有一个好处，就是前面提过的modified bit的好处，减少了I/O的消耗。

counting-based page replacement

  • LFU
  • MFU

做一个计数，选择使用过最多次的/最少次的page。一个too expensive的算法~~

page buffering algorithm

系统维护一个free frames pool，在要被写出的帧写回disk之前，首先将想要的frame写进free frame，然后再把victim frame写回disk，据说？这样进程就能快速重启

allocation of frame

分配给每个进程的frame数量：

  • minimum number of frames：与计算机的体系结构有关
  • maximum number of frames：与内存呢大小有关

Allocation algorithm

主要是两种

  • 平均分配
  • 按权重分配：根据可用frame和进程大小和数量分配

发表于

Composite

目的

将对象组合起来，以达到能同时表达整体与局部的效果，使得用户能一致地操作单个对象和组合对象

动机

在一些系统中，用户希望通过简单的组件组合成复杂的组件，但同时由于用户认为这些组件的操作是一致的，因此不适合将组件进行区别的对待。有一种实现方法是为所有简单组件定义一些类，另外定义一些容器类来管理简单组件。但这样势必需要区别对待地操作所有组件，如果组件的组合方式很多样化，那么操作起来就很不方便。因此我们可以使用递归组合这些组件，避免用户对组件使用不同的操作。

使用范围

  • 表示对象的整体与局部的层次结构
  • 忽略组合对象与单个对象的不同，从而对其进行统一的操作

效果

  • 首先在这个设计模式中会有几个角色：component（定义公共接口），leaf（最基本的组件），composite（含有叶节点的组件）；
  • composite模式使得基本对象即叶节点可以组成复合对象，同理复合对象也可以组成更大的符合对象，从而递归下去；
  • 可以简化用户代码，因为composite和leaf的接口类似，操作也相近；
  • 方便添加新组件，无论是leaf还是composite都可以自由地添加到原来的结构中，也就不会影响客户的使用；
  • 会有一些约束：
    • 因为你无法限制其添加组件，也就无法在编译时限定哪些组件可以添加进来，只能在运行时进行判断；

代码示例

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

#include <vector>
#include <iostream>

class Component {
public:
	virtual void operation(){}
	virtual void add(Component* ){}
	virtual void remove(Component* ){}
	virtual Component* getChild(int index) { return 0; }
	virtual ~Component(){}
};

class Composite :public Component{
public:
	virtual void operation() {
		for (auto c : com)
			c->operation();
	}
	virtual void add(Component* c) {
		com.push_back(c);
	}
	virtual void remove(Component* c) {

	}
	Component* getChild(int index) {
		if (index < com.size())
			return com[index];
		return NULL;
	}
private:
	std::vector<Component* > com;
};

class Leaf :public Component {
public:
	virtual void operation() {
		std::cout << "leaf::operation()" << std::endl;
	}
};

int main()
{
	Leaf *leaf = new Leaf();
	leaf->operation();
	Composite *com = new Composite();
	com->add(leaf);
	com->operation();
	Component *leaf_ = com->getChild(0);
	leaf_->operation();

	delete leaf;
	delete com;

    return 0;
}


发表于

Make interface easy to use correctly and hard to use incorrectly

动机

在C++中，有各种各样可以让你与代码交互的接口，但有时候一些接口的滥用会导致不必要的麻烦，因此我们要开发一个健壮的接口。

比如一个类：

1
2
3
4
class Date{
  public:
  	Date(int month, int day, int year);
}

这种构造函数有一个问题是它可能传入一些不合法的天数或者月份，或者不小心将day和month交换

解决方法

因此我们可以用类来进行封装。

1
2
3
4
class Date{
  public:
  	Date(const Month& m,const Day& d, const Year& y);
}

另一个守则是，任何让客户必须记得做某些事情，就可能出现“不正确使用”的倾向，例如要求new出来的原始资源必须客户记得手动删除就不是一个很好的使用方式，应该用智能指针去接管资源。

建议

  • 保证接口的一致性，以及与内置类型的行为兼容；
  • “阻止误用”的方法包括建立新类型（用类去封装），限制类型上的操作（禁止对a*b赋值），束缚对象值，以及消除客户的资源管理责任（用智能智能管理资源）；

发表于

store newed objects in smart pointers in standalone statements

动机

这个条例是为了避免在“以对象管理资源”中可能出现bug

比如

1
processWidget(std::shared_ptr<Widget>(new Widget), priority());

这里可能出现的问题是，C++对于函数参数的调用次序不确定，假如顺序是：

  • 调用new widget;
  • 调用priority（）
  • 调用shared_ptr的构造函数

那么如果在priority中发生异常，new出来widget资源就会泄漏

解决方法

分离new语句：

1
2
3
std::shared_ptr<Widget> pw(new Widget)；

processWidget(pw, priority()）;

建议

  • 以独立语句将newed对象存到智能指针中；

发表于

Bridge

目的

将抽象部分与它的实现部分分离，使得它们都可以独立地完成变化

动机

当一个抽象对象有多个实现时，通常的实现方式是通过继承来构造。但在某些情况下，子类的实现可能会不够灵活，出现大量重复的代码，也很难对其进行独立的修改。例如有一个公路1，公路2类，和一个角色A、B类，我们需要实现的实例是A在公路1，A在公路2等四个组合方式。但其出现了大量冗余，因为它们的动作是重复的。这时我们可以使用桥接的方式来构造它们。

使用范围

  • 不希望在抽象和它的实现部分有有一个固定的绑定关系，甚至乎，我希望能够在程序运行时动态地切换实现部分
  • 希望对不同的抽象接口和实现部分进行组合
  • 对一个抽象的修改不会影响客户

效果

  • 由于接口和实现是独立的，因此可以分离接口及其实现部分
  • 提高可扩充性，由于抽象和实现是独立的，我可以在两个层次做扩充，但不会影响客户
  • 隐藏实现细节，客户无需知道内部具体的实现细节

代码示例

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
// Bridge.cpp : ¶¨Òå¿ØÖÆ̨ӦÓóÌÐòµÄÈë¿Úµã¡£
//

#include <iostream>

class Implementor {
public:
	virtual void OperationImp() = 0;
	virtual ~Implementor() {}
protected:
	Implementor() {}
};

class ConcreteImplementor : public Implementor {
public:
	virtual void OperationImp() {
		std::cout << "ConcreteImplementor::OperationImp()" << std::endl;
	}
};

class Abstraction {
public:
	virtual void operation() = 0;
	virtual ~Abstraction() {}
protected:
	Abstraction() {}
public:
	Implementor* imp;
};

class RefinedAbstratcion : public Abstraction{
public:
	RefinedAbstratcion(Implementor* imp) {
		_imp = imp;
	}
	virtual void operation() {
		_imp->OperationImp();
		std::cout << "RefinedAbstratcion::operation()" << std::endl;
	}
private:
	Implementor* _imp;
};



int main()
{
	Implementor* imp = new ConcreteImplementor();
	Abstraction* abs = new RefinedAbstratcion(imp);

	abs->operation();
	delete imp;
	delete abs;
    return 0;
}