9.页面置换算法
页面置换：在地址映射过程中，如果在页面中发现所要访问的页面不存在于内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
分类：
全局置换：在整个内存空间置换。
a.工作集算法
b.缺失率置换算法
局部置换：在本进程中进行置换。
a.最佳置换算法(OPT)：从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。
b.先进先出置换算法(FIFO)：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。
c.最近最久未使用算法(LRU)：根据页面调入内存后的使用情况做出决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有也面中t值最大的，即最近最久未使用的页面予以淘汰。
d.时钟置换算法(Clock)：淘汰访问位为0的页框中的页面，被访问过的页面将其页框的访问位数值置1。
局部页面置换的三种算法C++代码实现：
1#include <iostream> 2using namespace std; 3int page[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1, -1}; 4 5void FIFO(); 6void OPT(); 7void RLU(); 8bool inArray(int *a, int n, int p); 9int main(void) 10{ 11 FIFO(); 12 OPT(); 13 RLU(); 14 system("pause"); 15} 16// FIFO算法 17void FIFO() 18{ 19 int temp[3] = {-1, -1, -1}; 20 int time[3] = {0, 0, 0}; 21 int num = 0; 22 int error = 0; 23 cout << "FIFO:" << endl; 24 while (page[num] != -1) 25 { 26 if (inArray(temp, 3, page[num])) 27 { 28 std::cout << page[num] << ','; 29 std::cout << endl; 30 } 31 else 32 { 33 error++; 34 bool hasChanged = false; 35 for (int i = 0; i < 3; i++) 36 { 37 if (time[i] == 0 && hasChanged == false) 38 { 39 time[i] = 2; 40 temp[i] = page[num]; 41 hasChanged = true; 42 } 43 if (time[i] != 0) 44 { 45 time[i]--; 46 } 47 } 48 std::cout << page[num] << ',' << ' '; 49 for (size_t i = 0; i < 3; i++) 50 { 51 if (temp[i] == -1) 52 { 53 std::cout << '*' << ' '; 54 } 55 else 56 { 57 std::cout << temp[i] << ' '; 58 } 59 } 60 std::cout << endl; 61 } 62 num++; 63 } 64 cout << "错误率:" << error << endl; 65} 66bool inArray(int *a, int n, int p) 67{ 68 for (int i = 0; i < n; i++) 69 { 70 if (p == a[i]) 71 { 72 return true; 73 } 74 } 75 return false; 76} 77// OPT算法 78void OPT() 79{ 80 int temp[3] = {-1, -1, -1}; 81 int num = 0; 82 int error = 0; 83 //OPT已知未来的页数为20 84 cout << "OPT:" << endl; 85 while (page[num] != -1) 86 { 87 int a = page[num]; 88 if (inArray(temp, 3, page[num])) 89 { 90 std::cout << page[num] << ','; 91 std::cout << endl; 92 } 93 else 94 { 95 error++; 96 bool fuck = false; 97 for (size_t i = 0; i < 3; i++) 98 { 99 if (temp[i] == -1) 100 { 101 temp[i] = page[num]; 102 fuck = true; 103 break; 104 } 105 } 106 107 if (fuck == false) 108 { 109 int distance[3] = {20, 20, 20}; 110 for (int i = 19; i >= num; i--) 111 { 112 for (int j = 0; j < 3; j++) 113 { 114 if (temp[j] == page[i] && (i - num) < distance[j]) 115 { 116 distance[j] = i - num; 117 } 118 } 119 } 120 int k = 0; 121 int max = -1; 122 for (size_t i = 0; i < 3; i++) 123 { 124 if (max < distance[i]) 125 { 126 max = distance[i]; 127 k = i; 128 } 129 } 130 temp[k] = page[num]; 131 } 132 std::cout << page[num] << ',' << ' '; 133 for (size_t i = 0; i < 3; i++) 134 { 135 if (temp[i] == -1) 136 { 137 std::cout << '*' << ' '; 138 } 139 else 140 { 141 std::cout << temp[i] << ' '; 142 } 143 } 144 std::cout << endl; 145 } 146 num++; 147 } 148 cout << "错误率:" << error << endl; 149} 150// RLU算法 151void RLU() 152{ 153 int temp[3] = {-1, -1, -1}; 154 int time[3] = {-1, -1, -1}; 155 int num = 0; 156 int error = 0; 157 cout << "RLU:" << endl; 158 while (page[num] != -1) 159 { 160 int a = page[num]; 161 if (inArray(temp, 3, page[num])) 162 { 163 std::cout << page[num] << ','; 164 std::cout << endl; 165 //bool Changed = false; 166 for (int i = 0; i < 3; i++) 167 { 168 if (temp[i] == page[num]) 169 { 170 time[i] = 2; 171 //Changed = true; 172 } 173 if (temp[i] != page[num] && time[i] != 0) 174 { 175 time[i]--; 176 } 177 } 178 } 179 else 180 { 181 error++; 182 //bool hasChange = false; 183 for (size_t i = 0; i < 3; i++) 184 { 185 if (temp[i] == -1) 186 { 187 temp[i] = page[num]; 188 time[i] = 2; 189 break; 190 } 191 if (time[i] == 0) 192 { 193 temp[i] = page[num]; 194 time[i] = 2; 195 } 196 else 197 { 198 time[i]--; 199 } 200 } 201 std::cout << page[num] << ',' << ' '; 202 for (size_t i = 0; i < 3; i++) 203 { 204 if (temp[i] == -1) 205 { 206 std::cout << '*' << ' '; 207 } 208 else 209 { 210 std::cout << temp[i] << ' '; 211 } 212 } 213 std::cout << endl; 214 } 215 num++; 216 } 217 cout << "错误率:" << error << endl; 218}
10.进程状态转换图
进程的五种基本状态：
创建状态：进程正在被创建；
就绪状态：进程被加入到就绪队列中等待CPU调度运行；
执行状态：进程正在被运行；
等待阻塞状态：进程因为某种原因，比如等待I/O，等待设备，而暂时不能运行；
终止状态：进程运行完毕；
11.软链接 vs 硬链接
软链接也叫符号链接，软链接文件有类似于Windows的快捷方式。它实际上是一个特殊的文件。在符号连接中，文件实际上是一个文本文件，其中包含的有另一文件的位置信息。
硬链接：通过索引节点来进行连接。在Linux的文件系统中，保存在磁盘分区中的文件不管是什么类型都给它分配一个编号，称为索引节点号(Inode Index)。在Linux中，多个文件名指向同一索引节点是存在的。一般这种连接就是硬连接。硬连接的作用是允许一个文件拥有多个有效路径名，这样用户就可以建立硬连接到重要文件，以防止“误删”的功能。其原因如上所述，因为对应该目录的索引节点有一个以上的连接。只删除一个连接并不影响索引节点本身和其它的连接，只有当最后一个连接被删除后，文件的数据块及目录的连接才会被释放。也就是说，文件真正删除的条件是与之相关的所有硬连接文件均被删除。
12.协程
定义:又称微线程，纤程，英文名Coroutine。协程看上去也是子程序，但执行过程中，在子程序内部可中断，然后转而执行别的子程序，在适当的时候再返回来接着执行。例如：
1 def A(): 2 print '1' 3 print '2' 4 print '3' 5 def B(): 6 print 'x' 7 print 'y' 8 print 'z'
上面示例程序中，协程运行结果可能是12x3yz。在执行A的过程中，可以随时中断，去执行B，B也可能在执行过程中中断再去执行A。但协程的特点在于是一个线程执行。
协程与线程的区别
a.协程最大的优势就是协程极高的执行效率。因为子程序切换不是线程切换，而是由程序自身控制。因此，没有线程切换的开销。协程和多线程相比，线程数量越多，协程的性能优势就越明显。
b.不需要多线程的锁机制，因为只有一个线程，也不存在同时写变量冲突。在协程中控制共享资源不加锁，只需要判断状态就好了，所以执行效率比多线程高很多。
13.进程同步的几种方式
信号量：用于进程间传递信号的一个整数值。在信号量上只有三种操作可以进行：初始化、P操作、V操作，这三种操作都是原子操作。P操作(递减操作)可以用于阻塞一个进程，V操作(增加操作)可以用于解除阻塞一个进程。
原理：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一位置停止，直到它接收到一个特定的信号。该信号即为信号量s。为通过信号量s传送信号，进程可执行原语semSignal(s);为通过信号量s接收信号，进程可执行原语semWait(s);如果相应的信号仍然没有发送，则进程被阻塞，直到发送完为止。可把信号量视为一个具有整数值的变量，在它之上定义三个操作：
a.一个信号量可以初始化为非负数；
b.semWait操作使信号量s减1.若值为负数，则执行semWait的进程被阻塞。否则进程继续执行；
c.semSignal操作使信号量加1，若值大于或等于零，则被semWait操作阻塞的进程被解除阻塞;
管程：由一个或多个过程、一个初始化序列和局部数据组成的软件模块，其主要特点如下：
a.局部数据变量只能被管程的过程访问，任何外部过程都不能访问；
b.一个进程通过调用管程的一个过程进入管程；
c.在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被阻塞，以等待管程可用；
消息传递：是进程间进程消息传递所需要的最小操作集。一个进程以消息的形式给另一个指定的目标进程发送消息；进程通过执行receive原语接收消息，receive原语中指明发送消息的源进程和消息。
14.线程同步的几种方式
临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。在任意时刻只允许一个线程对共享资源进行访问，如果有多个线程试图访问公共资源，那么在有一个线程进入后，其他试图访问公共资源的线程将被挂起，并一直等到进入临界区的线程离开，临界区在被释放后，其他线程才可以抢占。
互斥量:采用互斥对象机制。只有拥有互斥对象的线程才有访问公共资源的权限，因为互斥对象只有一个，所以能保证公共资源不会同时被多个线程访问。互斥不仅能实现同一应用程序的公共资源安全共享，还能实现不同应用程序的公共资源安全共享。
信号量:它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。
事件:通过通知操作的方式来保持线程的同步，还可以方便实现对多个线程的优先级比较的操作。
15.操作系统中程序的内存结构
一个程序本质上都是由BSS段、数据段(data段)、text段(代码段)三个组成的。可以看到一个可执行程序在存储（没有调入内存）时分为代码段、数据区和未初始化数据区三部分。
BSS段（未初始化数据区）：通常用来存放程序中未初始化的全局变量和静态变量的一块内存区域。BSS段属于静态分配，程序结束后静态变量资源由系统自动释放。
数据段：存放程序中已初始化的全局变量的一块内存区域。数据段也属于静态内存分配。
代码段：存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定，并且内存区域属于只读。在代码段中，也有可能包含一些只读的常数变量text段和data段在编译时已经分配了空间，而BSS段并不占用可执行文件的大小，它是由链接器来获取内存的。
a.BSS段(未进行初始化的数据)的内容并不存放在磁盘上的程序文件中，其原因是内核在程序开始运行前将它们设置为0。需要存放在程序文件中的只有正文段和初始化数据段。
b.data段(已经初始化的数据)则为数据分配空间，数据保存到目标文件中。数据段包含经过初始化的全局变量以及它们的值。BSS段的大小从可执行文件中得到，然后链接器得到这个大小的内存块，紧跟在数据段的后面。当这个内存进入程序的地址空间后全部清零。包含数据段和BSS段的整个区段此时通常称为数据区。
可执行程序在运行时又多出两个区域：栈区和堆区。
a.栈区：由编译器自动释放，存放函数的参数值、局部变量等。每当一个函数被调用时，该函数的返回类型和一些调用的信息被存放到栈中。然后这个被调用的函数再为他的自动变量和临时变量在栈上分配空间。每调用一个函数一个新的栈就会被使用。栈区是从高地址位向低地址位增长的，是一块连续的内存区域，最大容量是由系统预先定义好的，申请的栈空间超过这个界限时会提示溢出，用户能从栈中获取的空间较小。
b.堆区：用于动态分配内存，位于BSS和栈中间的地址区域。由程序员申请分配和释放。堆是从低地址位向高地址位增长，采用链式存储结构。频繁的malloc/free造成内存空间的不连续，产生碎片。当申请堆空间时库函数是按照一定的算法搜索可用的足够大的空间。因此堆的效率比栈要低的多。
16.参考资料
[1] 银行家算法原理 https://blog.csdn.net/jgm20475/article/details/81265947
[2] FIFO算法详细原理 https://blog.csdn.net/jack450250844/article/details/85019950
[3] LRU算法详细原理 https://blog.csdn.net/jack450250844/article/details/85019898
[4] Clock算法详细原理 https://blog.csdn.net/Long_H_Zhu/article/details/84184563
