数组基础

  从概念上说，数组就是把数据码成一排进行存放。

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

int main()
{
	int arr[10];
	for (int i = 0; i < 10; i++) {
		arr[i] = i;
	}

	int* arr2 = new int[10];
	for (size_t index = 0; index < 10; index++) {
		arr2[index] = index;
	}

	delete[] arr2;

	int scores[] = { 100,99,98 };

	for (auto score : scores) {
		cout << score << endl;
	}

	scores[1] = 66;

	for (size_t i = 0; i < sizeof(scores) / sizeof(scores[0]); i++) {
		cout << scores[i] << endl;
	}
	
	return 0;
}

  数组最重要的就是就是它的索引。索引可以有语义，也可以没有语义。数组最大的优点就是可以快速查询，直接用数组下标就可以找到元素，因此数组最好应用于“索引有语义”的情况，通俗的说就是我们最好知道我们要查什么。但也要注意并非所有有语义的索引都适用于数组，比如当我们要存储人员信息，索引是身份证号的话，需要为索引信息开辟大量的空间。

自己封装数组

  使用原生的数组会有很多限制，比如数组开辟了连续的空间，但只有很少的空间存储了信息，如果索引没有语义，那么那些没有信息的空间如何表示呢？还有如何向数组添加元素，如何删除元素等等。所以我们需要编写自己的动态数组类。

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200

//动态数组，支持增删改查
template<typename T>
class Array
{
public:
	//构造函数传入数组容量capacity构造array
	Array(int capacity)
	{
		m_nCapacity = capacity;
		m_nSize = 0;
		m_arrData = new T[m_nCapacity];
	}

	//默认构造函数,默认容量为10
	Array()
	{
		m_nSize = 0;
		m_nCapacity = 10;
		m_arrData = new T[10];
	}

	~Array()
	{
		if (m_arrData) {
			delete[] m_arrData;
			m_arrData = nullptr;
		}
		m_nSize = 0;
	}

public:
	int GetSize() { return m_nSize; }
	int GetCapacity() { return m_nCapacity; }
	bool IsEmpty() { return m_nSize == 0; }

	//向指定的位置添加元素
	void Add(int index, T e)
	{
		assert(index >=0 && index <=m_nSize);

		//动态扩容，添加元素时如果size当前元素已经占满内存空间，则容量翻倍
		//此处使用翻倍策略，而不是加上一个常数
		//如果只是简单加一个固定常数，这个常数不好确定
		//很容易出现当前Capacity小但加了一个很大的常数，或当前Capacity很大却加了一个很小的常数
		//造成效率低或资源浪费
		if (m_nSize == m_nCapacity)
			Resize(2 * m_nCapacity);

		//index开始后面的元素全部后移
		for (int i = m_nSize - 1; i >= index; i--) {
			m_arrData[i + 1] = m_arrData[i];
		}
		m_arrData[index] = e;
		m_nSize++;
	}

	void AddLast(T e)
	{
		Add(m_nSize, e);
	}

	void AddFirst(T e)
	{
		Add(0, e);
	}

	//获取index位置的元素
	T Get(int index)
	{
		assert(index >= 0 && index < m_nSize);
		return m_arrData[index];
	}

	//更新数组元素
	void Set(int index, T e)
	{
		assert(index >= 0 && index < m_nSize);
		m_arrData[index] = e;
	}

	//判断数组中是否存在元素e
	bool Contains(T e)
	{
		for (int i = 0; i < m_nSize; i++) {
			if (m_arrData[i] == e)
				return true;
		}
		return false;
	}

	//查找元素，找到时返回索引，否则返回-1
	int Find(T e)
	{
		for (int i = 0; i < m_nSize; i++) {
			if (m_arrData[i] == e)
				return i;
		}
		return -1;
	}

	//删除index位置的元素，返回删除的元素
	T Remove(int index)
	{
		assert(index >= 0 && index < m_nSize);
		T ret = m_arrData[index];
		for (int i = index + 1; i < m_nSize; i++) {
			m_arrData[i - 1] = m_arrData[i];
		}
		m_nSize--;
		//m_arrData[m_nSize] = NULL; //这句可以不加，主要是为了清空垃圾值

		//动态缩减空间
		if (m_nSize == m_nCapacity / 2)
			Resize(m_nCapacity / 2);
		return ret;
	}

	int RemoveFirst()
	{
		return Remove(0);
	}

	int RemoveLast()
	{
		return Remove(m_nSize - 1);
	}

	//删除指定元素
	void RemoveElement(T e)
	{
		int index = Find(e);
		if (index != -1)
			Remove(index);
	}

	void Print()
	{
		assert(m_nSize > 0);
		cout << "Array:size=" << m_nSize << ",capacity=" << m_nCapacity << endl;
		cout << "[";
		for (int i = 0; i < m_nSize; i++)
		{
			cout << m_arrData[i];
			if (i != m_nSize - 1)
				cout << ",";
		}
		cout << "]" << endl;
	}

private:
	//扩容函数私有，不允许外部扩容
	void Resize(int newCapacity)
	{
		T* newData = new T[newCapacity];

		//先把旧数据拷贝过来
		for (int i = 0; i < m_nSize; i++) {
			newData[i] = m_arrData[i];
		}

		m_arrData = newData;
		m_nCapacity = newCapacity;
		newData = nullptr;
		delete[] newData;
	}
private:
	int m_nSize;	//实际存储的元素格式
	int m_nCapacity;	//数组空间最多可以装多少元素
	T* m_arrData;
};


int main()
{
	//Array myArr = 5;
	Array<int> *myArr = new Array<int>(3);
	myArr->AddLast(2);
	myArr->AddLast(3);
	myArr->AddFirst(1);
	myArr->Print();

	myArr->AddFirst(10);
	myArr->Print();

	myArr->RemoveFirst();
	myArr->Print();

	auto tmp1 = myArr->Get(1);

	bool b1 = myArr->Contains(6);
	myArr->Set(2, 6);
	b1 = myArr->Contains(6);

	if (myArr) {
		delete myArr;
		myArr = nullptr;
	}

	return 0;
}

时间复杂度分析

什么是大O

n表示数据规模，则表示运行算法所需要执行的指令数，和成正比。

一个算法有多个步骤，每个步骤规模相同但时间复杂度不同，最终的时间复杂度以最高的那个为准。

对数据规模的概念

如果想要在1s之内解决问题：

• 的算法可以处理大约级别的数据；
• 的算法可以处理大约级别的数据；
• 的算法可以处理大约级别的数据；

这个结论只是执行简单的数据操作，实际还需要再低估一下。

空间复杂度

• 多开一个辅助数组：;
• 多开一个辅助的二维数组：
• 多开常数空间：;

需要注意：递归调用是有空间代价的，递归的深度就是空间复杂度。

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

//计算n以内数据的和

//空间复杂度O(1)
int sum1(int n)
{
    assert(n >= 0);
    int ret = 0;
    for(int i=0;i<=n;i++)
    {
        ret += i;
    }
    return ret;
}

//递归调用：空间复杂度O(n)
int sum2(int n)
{
    assert(n>=0);
    if(n == 0)
        return 0;

    return n + sum2(n-1);
}

简单的时间复杂度分析

O(1)

常数级的算法很简单，没有数据规模的变化

1
2
3
4
5
6
7

// O(1)
void swapTwoInts(int &a , int &b){
    int temp = a;
    a = b;
    b = temp;
    return;
}

O(n)

O(n)的算法典型的特征就是有个循环，并且循环的次数和n相关。

其实正常来说，应该是，其中C是个常数，且不一定大于1

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

// O(n)
int sum(int n){

    assert(n >= 0);

    int ret = 0;
    for( int i = 0 ; i <= n ; i ++ )
        ret += i;
    return ret;
}

//字符串反转，只需要进行1/2次的swap操作即可
void reverse(string &s){

    int n = s.size();
    for(int i = 0 ; i < n/2 ; i ++)
        swap( s[i] , s[n-1-i] );
    return;
}

O(n^2)

见到算法内部有双重循环，每层循环都是n相关基本就八九不离十了。

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

//选择排序算法
void selectionSort(int arr[], int n){

    for(int i = 0 ; i < n ; i ++){
        int minIndex = i;
        for( int j = i + 1 ; j < n ; j ++ )
            if( arr[j] < arr[minIndex] )
                minIndex = j;

        swap( arr[i] , arr[minIndex] );
    }
}

千万要注意两层循环都要和n相关，不要看到双重循环就认为是

1
2
3
4
5
6
7
8
9
10

//第二重循环哪怕循环300w次，这个也是O(n)
void printInformation(int n){

    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= 30 ; j ++ )
            cout << "Class " << i << " - " << "No. " << j << endl;
    return;
}

O(logn)

经典的二分查找法：

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

//二分查找法
int binarySearch(int arr[], int n, int target){

    int l = 0, r = n-1;
    while( l <= r ){
        int mid = l + (r-l)/2;
        if(arr[mid] == target) return mid;
        if(arr[mid] > target) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

将数字整形转化为字符串：

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

string intToString(int num){

    string s = "";
    string sign = "+";
    if(num < 0){
        num = -num;
        sign = "-";
    }

    while(num){
        s += '0' + num % 10;
        num /= 10;
    }

    if(s == "")
        s = "0";

    reverse(s);
    if(sign == "-")
        return sign + s;
    else
        return s;
}

分析算法思想，核心在" num /= 10"步中，就是n经过几次“除以10”操作后等于0，那么就是;

虽然上面两个例子，一个是以2为底，一个是以10为底，但都是，这个可以通过对数函数的换底公式来理解：有换底公式，可见和之间只相差一个常数，在时间复杂度下可以直接理解为

还需要注意，双重循环也可能出现logN的复杂度，需要注意量增长的规模：

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

//复杂度:O(nlogn)
void hello(int n){

    for( int sz = 1 ; sz < n ; sz += sz )
        for( int i = 1 ; i < n ; i ++ )
            cout << "Hello, Algorithm!" << endl;
}

//外层循环每次增长可以理解为sz*2
//其实就可以理解为n经过几次“除以2”的操作后等于1，外层循环复杂度O(logn)
//内层循环复杂度是O(n)
//合起来是O(nlogn)



//判断是否为素数
// O(sqrt(n))
bool isPrime(int num){

    if( num <= 1 ) return false;
    if( num == 2 ) return true;
    if( num % 2 == 0 ) return false;

    for(int x = 3 ; x * x <= num ; x += 2)
        if( num%x == 0 )
            return false;

    return true;
}

//

递归算法的复杂度分析

面对递归算法需要具体问题具体分析。

递归中只会进行一次递归调用

如果递归函数中只进行一次递归调用，递归深度为depth，在每个递归函数中的时间复杂度为T，则总体的时间复杂度为，既只需关注递归的深度

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

//递归调用的二分查找法
int binarySearch(int arr[], int l, int r, int target){

    if(l > r)
        return -1;

    int mid = l + (r - l) / 2;
    if(arr[mid] == target)
        return mid;
    else if(arr[mid] > target)
        return binarySearch(arr, l, mid - 1, target);
    else
        return binarySearch(arr, mid + 1, r, target);

}

  二分查找法很容易用递归实现，上述代码每次调用时，内部要么直接返回，要么数组左半边调用递归，要么数组右半边调用递归，只会调用一次，所以分析时间复杂度只有看递归的深度即可。

  每次调用数组减少一半，是典型的logn情况，所以复杂度为

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

// sum,O(n)
int sum(int n){

    assert(n >= 0);

    if(n == 0)
        return 0;
    return n + sum(n - 1);
}

// 求x的n次方：O(logn)
double pow(double x, int n){

    assert(n >= 0);

    if(n == 0)
        return 1.0;

    double t = pow(x, n / 2); //每次减半，logn
    if(n % 2)
        return x * t * t;

    return t * t;
}

递归中进行多次递归调用

当递归中有多次递归调用时，就需要关注递归调用的次数了。如果递归中只调用一次，深度就是次数，但如果调用了多次，那么深度和次数就是两个概念了。

1
2
3
4
5
6
7
8
9
10
11

//O(2^n)
//这个是指数级的算法，是个非常慢的算法
int f(int n)
{
    assert(n >= 0);

    if(n == 0)
        return 1;

    return f(n-1) + f(n-1);
}

均摊复杂度分析

  有时候会遇到这种情况：解决某个问题时运用了一系列算法，某个算法的复杂度很高，但这个算法可以降低其他算法的复杂度，这时候就需要计算分摊复杂度。

  均摊复杂度的经典问题就是动态数组vector。

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

template <typename T>
class MyVector{

private:
    T* data;
    int size;       // 存储数组中的元素个数
    int capacity;   // 存储数组中可以容纳的最大的元素个数

    // 复杂度为 O(n)
    void resize(int newCapacity){

        assert(newCapacity >= size);
        T *newData = new T[newCapacity];
        for( int i = 0 ; i < size ; i ++ )
            newData[i] = data[i];
        delete[] data;

        data = newData;
        capacity = newCapacity;
    }

public:
    MyVector(){

        data = new T[100];
        size = 0;
        capacity = 100;
    }

    ~MyVector(){

        delete[] data;
    }

    // 平均复杂度为 O(1)
    void push_back(T e){
        //当元素到达容量上限时，需要调用resize扩大空间
        if(size == capacity)
            resize(2 * capacity);

        data[size++] = e;
    }

    // 平均复杂度为 O(1)
    T pop_back(){

        assert(size > 0);
        size --;

        return data[size];
    }

};

  上面的代码只在push操作时resize了空间，但是没有在pop操作时resize空间。我们当然可以参考push操作，在pop到capacity一半时resize容量，但这里涉及一个问题，就是要防止复杂度震荡。

  考虑这个问题：当push到临界点时resize一倍空间，然后立即pop，此时又resize为一半，然后立即push，这种极端场景下时间复杂度无法均摊，会退化为。

  如果想避免这种场景，可以不再临界点处resize，当pop操作到达capacity的1/4处时，resize为1/2

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

// 平均复杂度为 O(1)
T pop_back(){

    assert(size > 0);
    T ret = data[size-1]; //这里一定要提前拿出来，resize操作会修改data
    size --;

    // 在size达到静态数组最大容量的1/4时才进行resize
    // resize的容量是当前最大容量的1/2
    // 防止复杂度的震荡
    if(size == capacity / 4)
        resize(capacity / 2);

    return ret;
}

文件的逻辑结构

文件类型

文件的逻辑结构根据文件类型可以分为两类：

1. 有结构文件：常见的有文本文件、文档、媒体文件等
2. 无结构文件：常见的有二进制文件、链接库等

  有结构文件的文件内容由定长记录和可变长记录两部分组成。定长记录存储文件的格式、编码、文件描述等结构化数据项；可变长记录存储文件的具体内容。

  无结构文件也称为流式文件，文件内容长度以字节为单位。exe、dll、so文件都是无结构文件。

顺序文件

  顺序文件是指按顺序存放在存储介质中的文件。磁带就是典型的顺序文件存储介质，只能按顺序读取和写入文件。顺序文件是所有逻辑文件当中存储效率最高的。

  但由于顺序文件只能顺序读写，所以假如我们想要对文件内容进行增、删等操作，效率极其低下。

索引文件

  可变长文件不适合适使用顺序文件格式存储，所以为了解决这个问题发明了索引文件。索引文件需要配合索引表完成存储的操作。

辅存(磁盘)的存储空间分配

分配方式

连续分配

  如果一个文件存取的时候需要连续的扇区，就会把内存中连续的扇区分配给文件。

  连续分配只要求我们顺序的读取文件即可，所以读取操作非常容易，速度很快。但是对存储要求很高，要求满足容量的连续存储空间。

链接分配

  链接分配可以将文件存储在离散的盘块中，不再需要大块连续的存储空间，但需要额外的存储空间存储文件的盘块链接顺序。根据这个额外存储空间的不同，分为隐式链接和显式链接。

  隐式链接的方法中，隐式分配的下一个链接存储在当前盘块内，就像链表结点中的next指针。隐式链接很适合顺序访问，我们只要知道起始的盘块就可以依次遍历所有的盘块，但是隐式链接的随机访问效率很低，必须从头开始寻找。并且隐式链接的可靠性差，任何一个链接出问题都将影响整个文件。

  显式链接就不在当前盘块中指定下一个盘块的位置了，而是单独有一张表，存储物理盘块以及下一个盘块的地址数据。这张表叫FAT(File Allocation Table)，也就是我们平时说的FAT文件系统，显式链接就是FAT系统的工作原理。FAT也存在一些缺点：它不支持高效的直接存储，因为FAT的记录项非常多，磁盘越大FAT记录越大，存储时需要检索FAT表找到空闲位置。而且检索FAT表时需要将整个FAT加载到内存中，占用较大的存储空间。

索引分配

  把文件的所有盘块集中存储，存储盘块的位置称为索引。每个文件都拥有一个索引块，记录当前文件所有盘块信息，当我们读取某个文件时，只需要读取索引即可，不需要把整张表都加载到内存中。通过索引分配我们可以直接找到文件对应的盘块。文件较大时，索引分配具有明显的优势。

存储空间管理

空闲表

  空闲表可以表示某个空闲的盘块号内有多少个空闲盘块数。空闲盘曲的分配与内存的分配类似，也具有首次适应算法、循环适应算法等；回收过程也和内存回收类似。

空闲链表

  空闲链表把所有空闲盘曲组成一个空闲链表，每个链表节点存储空闲盘块和空闲的数目。存储的信息和空闲表一样，操作方式也和内存的空闲链表方式类似。

位示图

  位示图横向的是盘块，纵向的是磁道，每一个具体的盘块都有0或1的标记，0表示未使用，1表示已经被使用了。位示图优点很多，首先维护成本很低，只需要维护一张表即可；其次位示图可以非常容易的找到空闲盘块；位示图内部使用0/1比特位，占用的空间很小。

目录管理

  目录系统是树形结构存储，使得任何文件或目录都只有唯一路径

内存的分配与回收

  早期的计算机编程并不需要过多的存储管理，但随着计算机和程序越来越复杂，存储管理成为必要。存储管理需要确保计算机有足够的内存处理数据、确保程序可以从内存中获取一部分内存使用，并可以归还使用后的内存以供其他程序使用。

内存分配

• 单一连续分配：

  单一连续分配是最简单的内存分配方式，只能在单用户、单进程的操作系统使用。它把系统内存分为系统区和用户区，系统区内的内存只能够被操作系统使用，用户区内的内存只能被用户程序使用。这个分配方式已经过时不再使用了。

• 固定分区分配：

  固定分区分配是支持多道程序的最简单存储分配方式。内存被划分为若干固定大小的区域，每个分区只提供给一个程序使用，互不干扰。

• 动态分区分配：

  这是操作系统中比较常用的方法。根据进程实际需要，动态地分配内存空间。要支持这种分配方法，就需要相关的数据结构和分配算法:

  数据结构：

  假设主存中有若干分区，有些分区已经被使用，有些分区空闲。动态分区空闲表这个数据结构就可以记录分区的使用情况。

  还有动态分区空闲链数据结构，用一个双向链表的结构存储来存储当前系统中的空闲区域。

  算法：

  首次适应算法(FF)：主要使用空闲链的数据结构，每次进行内存分配的时候从链表头开始顺序查找适合的内存区域。遍历结束后发现没有合适的空闲区，则该次分配失败；如果找到了合适的空闲区，则把这块内存分配给进程使用。首次使用算法有个很大的问题：由于每次都是从头部开始遍历，使得头部的地址空间不断的被划分，导致头部地址可能出现大量碎片。对于这个问题，可以优化为循环适应算法，每次遍历结束后记录位置，下次遍历从这个位置开始，而不需要每次从头开始遍历。

  最佳适应算法：空闲链表按照容量大小进行排序，每次遍历空闲区链表时可以找到最佳的合适空闲区。这种算法可以有效避免大材小用的情况。

  快速适应算法：快速适应算法要求有多个空闲区链表，每个空闲区链表存储一种容量大小的空闲区。这样当我们需要某个大小的空闲区域时，就可以快速找到对应的链表取内存。

内存回收

  内存回收的场景可能会遇到下面四种场景：

  第一种场景是需要回收的区域和空闲区连在一起且正好在空闲区后面，这个场景非常简单，不需要新建空闲链表节点，只需要把空闲区的容量增大即可，把回收区的容量包括进去。

  第二种情况是需要回收的区域和空闲区连在一起，但在空闲区前面。这个场景也是将回收区和空闲区合并，合并而成的新的空闲区使用回收区的地址。

  第三种情况回收区恰好在两个空闲区之间，回收需要将空闲区1、空闲区2和回收区一起合并，然后新的空闲区地址使用空闲区1的地址。

  最后的场景就是单一的回收区，没有连接任何的空闲区，这种情况要为回收区创建新的空闲节点，然后把回收区插入到相应的空闲区链表中去。

段页式存储管理

  每个进程都有独立的进程空间，操作系统管理进程空间有三种管理方式：

页式存储管理

  计算机组成原理中有字和字块的概念，字和字块是相对内存条等物理设备的定义，而操作系统内存管理中的页面则是相对逻辑空间的定义。字块和页面都是指大小一样的一块内存。

  页式管理是将进程的逻辑空间划分成若干大小相同的页面，把相应的物理内存空间分成与页面大小相同的物理块。以进程为单位把进程空间装进物理内存中分散的物理块中。

  页式管理系统中需要了解内存碎片的概念。如下图所示，空闲链表中存有大小不同的空闲节点，如果需要申请一个页面大小的内存，节点1不够，只能使用节点2-3的一部分，这样就造成了内存碎片。所以页式存储管理的页面大小应该适中，过大的话难以分配，过小的话又会造成内存碎片多。一般情况下，页面大小为512B~8K。

  为了知道某个页面被分配到哪个字块，还需要了解页表的概念。页表记录进程逻辑空间和物理空间的映射关系。

  在现在计算机系统中，可以支持非常大的逻辑地址空间(~)，这样页表就会变得非常大，要占用非常大的内存空间。假设具有32位逻辑地址空间(寻址空间为即4G)的分页系统，规定页面大小为4KB，则每个进程页表中的页表项可达1M(4G/4KB=)个，如果每个页表项占用1Byte，每个进程仅仅页表就要占用1MB的内存空间。为应对这种情况，有了多级页表的设计.

  单纯的页式存储管理可能遇到的问题是，假如有一段连续的逻辑分布在多个页面中，将大大降低执行的效率。

段式存储管理

  段式存储管理将进程的逻辑空间划分成若干段，这种划分是非等分的。每一段的长度由进程内连续的逻辑长度决定，比如针对MAIN函数、子程序段X、子函数Y等，根据不同的长度分配不同的内存空间。

  我们也需要一个数据结构来保存逻辑空间到物理空间的映射，段式存储结构中的数据结构叫段表，由于段长度不同，所以相比页式存储管理，段表内多了一个段长。

  页式存储管理和段式存储管理相同点在于，都离散的管理了进程的逻辑空间，它们之间的不同点在于：

1. 页是物理单位，段是逻辑单位；
2. 分页是为了合理利用空间、分段是为了满足用户需求；
3. 页的大小由硬件固定，段的长度可动态变化
4. 页表信息是一维的，段表信息是二维的(需要记录段长度)

段页式存储管理

  结合了页式存储管理和段式存储管理，产生了段页式的存储管理。分页的优点在于虽然存在页内碎片，但相比分段来说提高了内存的利用率；分段的优点在于可以更好的满足用户需求。

  段页式存储管理首先将逻辑空间按照段式管理分成若干段，再把段内空间按页式管理分成若干页。页式管理的页地址由页号和业内偏移组成，段式管理的段地址由段号和段内偏移组成，段页式结合两者，段页地址由段号、段内页号、页内地址三者组成。

虚拟内存

  有些进程实际需要的内存很大，超过了物理内存的容量，而伴随着多道程序设计的出现，使得每个进程可用的物理内存更加稀缺。但由于现实的原因，不可能无限增加物理内存，物理内存总有不够用的时候，所以诞生了虚拟内存技术。虚拟内存是操作系统内存管理的关键技术，使得多道程序运行和大程序运行成为现实。虚拟内存技术把程序使用的内存进行划分，将暂时不使用的内存放置在辅存中。

程序的局部性原理

  局部性原理是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。

  局部性原理是虚拟内存可以实现的原因之一。程序加载的时候，不需要把进程所有的逻辑空间都加载到内存中，只装载部分即可。如果需要访问页时发现页面不在内存中，则发出缺页中断，发起页面置换，置换后程序就可以继续运行下去。从用户层面看，程序仿佛拥有很大的空间，即是虚拟内存。虚拟内存实际上是对物理内存的补充，速度接近于内存，成本接近于辅存。

虚拟内存置换算法

• 先进先出算法(FIFO)
• 最不经常使用算法(LFU)
• 最近最少使用算法(LRU)

进程调度

  进程调度是指计算机通过决策决定哪个就绪进程可以获得CPU使用权。前提是多道程序设计。

  进程调度有两个步骤：

1. 保留旧进程的运行信息，请出旧进程；
2. 选择新进程，准备运行环境并分配CPU；

  操作系统提供了三个机制来负责进程调度：

• 就绪队列的排队机制：

  为了提高进程调度的效率，操作系统事先将就绪进程按照一定的方式排成队列，以便调度程序可以最快找到就绪进程。

• 选择运行进程的委派机制：

  调度程序以一定的策略选择就绪进程，将CPU资源分配给它。

• 新老进程的上下文切换机制：

  保存当前进程的上下文信息，装入被委派执行进程的运行上下文。

  如果进程调度触发时，老进程还没有执行完毕的场景怎么办？为此有两种进程调度的方式：

• 非抢占式的调度：

  处理器一旦分配给某个进程，就让该进程一直使用下去，调度程序不以任何原因抢占正在被使用的处理器。直到进程完成工作或因为IO阻塞才会让出处理器。

• 抢占式的调度：

  允许调度程序以一定的策略暂停当前运行的进程，保存好旧进程的上下文信息，分配处理器给新进程。

进程调度算法

• 先来先服务算法：

  这个算法比较简单，在就绪队列中按照先来先服务的原则，优先取出队列最前面的就绪进程来调度，之后依次执行。

• 短进程优先调度算法：

  调度程序优先选择就绪队列中估计运行时间最短的进程。短进程优先调度算法不利于长作业进程的执行。

• 高优先权优先调度算法：

  进程附带优先权，调度程序优先选择权重高的进程。这个算法使得紧迫的任务可以优先处理。

  系统中分为前台进程和后台进程，一般来说前台进程的优先级都比后台进程大，因为前台进程需要和用户交互，要保证用户使用时不会卡顿。

• 时间片轮转调度算法：

  按照先来先服务的原则排列就绪队列，然后每次从队列头部取出待执行的进程，分配一个时间片执行，每个进程分配的时间片都是一样的。这是相对公平的调度算法，但是不能保证及时响应用户操作。

死锁

  死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞现象。若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

死锁的产生

  第一个死锁产生的原因是资源竞争。当共享资源数量不满足各个进程需求时，各个进程之间就会因为共享资源的竞争而导致死锁。每个进程都在等待请求的资源被释放，但自身占用的资源又不会主动释放。如果此时增加多余的系统资源，死锁就会解开。

  第二个原因是进程调度顺序不当。如下图，进程1和进程2都要申请打印机和传真机资源。如果调度的顺序是A->B->C->D，那么就会发生死锁。如果适当的改变调度顺序，改为A->D->B->C，那么就可以正常调度。

  死锁产生的必要条件有四个，必须同时满足：

1. 互斥条件：进程对资源的使用是排他性的使用。某个资源只能由一个进程使用，其他进程需要使用只能等待。
2. 请求保持条件：进程至少保持一个资源，同时又提出新的资源请求。此时新资源被占用，请求被阻塞，但被阻塞的进程不释放自己保持的资源。
3. 不可剥夺条件：进程获得的资源在未完成使用前不能被剥夺，获得的资源只能由进程自身释放。
4. 环路等待条件：发生死锁时，必然存在“进程-资源”的环形等待链。

死锁的处理

预防死锁的方法

  死锁产生的必要条件有四个，我们只需要破坏其中一个或多个即可预防死锁产生。互斥条件我们不能破坏，其余三个我们都有方法破坏：

1. 摒弃请求保持条件：系统规定进程运行之前，一次性申请所有需要的资源。这样在进程运行期间不会再提出资源请求。
2. 摒弃不可剥夺条件：当一个进程请求新的资源得不到满足时，必须释放占有的资源。
3. 破坏环路等待条件：可用资源按照线性排列，申请必须按照需要递增申请，线性申请就不再形成环路。

银行家算法

  以银行借贷系统分配策略为基础的算法，是一个可操作的著名的避免死锁的算法。客户申请的贷款是有限的，每次申请需声明最大资金量。银行在能够满足贷款时，都应该给用户贷款；客户在使用贷款后，能够及时归还贷款。

  银行家算法需要有三个数据结构：已分配资源表、所需资源表、可分配资源表。如下图，表格中A、B、C、D四列表示可申请的四个共享资源，P1、P2、P3、P4是四个进程，第一张表内部的数字表示当前进程拥有的资源数量，第二张表内部的数字表示当前进程还需要资源的数量，第三张表内部数字表示当前系统还剩的资源数量。

  当我们把所需资源表减去已分配资源表，就可以得到一张还需要分配的资源表:

  此时我们把还需分配资源表中每个进程依次和可分配资源表比较，如果有一个进程当前满足运行条件，则直接把资源分配给它。等进程运行完毕归还资源后，重新再比较。