在操作系统中，并发是指一个时间段中有几个程序都处于已启动运行到运行完毕之间，且这几个程序都是在同一个处理机上运行，但任一个时刻点上只有一个程序在处理机上运行。

其安易持，其未兆易谋；其脆易泮，其微易散。为之于未有，治之于未乱。合抱之木，生于毫末；九层之台，起于垒土；千里之行，始于足下。为者败之，执者失之。是以圣人无为故无败，无执故无失。民之从事，常于几成而败之。慎终如始，则无败事。是以圣人欲不欲，不贵难得之货，学不学，复众人之所过，以辅万物之自然而不敢为。 —— 《老子·道德经·第六十四章》

抄袭其实不叫抄袭，语文上说是借鉴，数学上叫类比，英语上叫copy，地理上是迁移，生物上是转录，物理上是参考系，化学上叫同分异构体，政治上叫求同存异，历史上就是文化大统一。

内存管理的一种页面置换算法，对于在内存中但又不用的数据块(内存块)叫做LRU，操作系统会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另外的数据，常用于页面置换算法，是为虚拟页式存储管理服务的。

一、基础

      内存(Memory)也被称为内存储器、主存储器，其作用是用于暂时存放CPU中的运算数据，以及与硬盘等外部存储器交换的数据。它是外存与CPU进行沟通的桥梁，计算机中所有程序的运行都是在内存中进行的。

      计算机管理内存的基本方式有两种：段式管理和页式管理。而在使用80x86微处理器时，内存地址分为三个不同的地址：逻辑地址，线性地址，物理地址。

页表的根本功能是提供从虚拟页面到物理页面的映射。因此，页表的记录条数与虚拟页面数相同

二、虚拟内存

1. 虚拟内存，也称虚拟存储器(Virtual Memory)，是计算机系统内存管理的一种技术。电脑中所运行的程序均需经由内存执行，若执行的程序占用内存很大或很多，则会导致内存消耗殆尽。当内存耗尽时，电脑就会自动调用硬盘来充当内存，以缓解内存的紧张。目前，大多数操作系统都使用了虚拟内存，如Windows家族的“虚拟内存”，Linux的“交换空间”等。

2. 工作原理：虚拟存储器是由硬件和操作系统自动实现存储信息调度和管理的，它的工作过程包括6个步骤：

   • ①中央处理器访问主存的逻辑地址分解成组号a和组内地址b，并对组号a进行地址变换，即将逻辑组号a作为索引查地址变换表，以确定该组信息是否存放在主存内。
   • ②如该组号已在主存内，则转而执行④；如果该组号不在主存内，则检查主存中是否有空闲区，如果没有便将某个暂时不用的组调出送往辅存，以便将这组信息调入主存。
   • ③从辅存读出所要的组，并送到主存空闲区，然后将那个空闲的物理组号a和逻辑组号a登录在地址变换表中。
   • ④从地址变换表读出与逻辑组号a对应的物理组号a。
   • ⑤从物理组号a和组内字节地址b得到物理地址。
   • ⑥根据物理地址从主存中存取必要的信息。

3. 调度方式：调度方式有分页式、段式、段页式3种。

   • 页式调度是将逻辑和物理地址空间都分成固定大小的页，主存按页顺序编号。每个独立编址的程序空间有自己的页号顺序，通过调度辅存中程序的各页可以离散装入主存中不同的页面位置，并可据表一一对应检索。
   • 段式调度是按程序的逻辑结构划分地址空间，段的长度是随意的，并且允许伸长。
   • 段页式调度是把物理空间分成页，程序按模块分段，每个段再分成与物理空间页同样小的页面。

4. 虚拟存储地址变换

   • 全联想变换：任何逻辑空间页面能够变换到物理空间任何页面位置的方式称为全联想变换。
   • 直接变换：每个逻辑空间页面只能变换到物理空间一个特定页面的方式称为直接变换。
   • 组联想变换：组联想变换是指各组之间是直接变换，而组内各页间则是全联想变换。

5. 替换规则：替换规则用来确定替换主存中哪一部分，以便腾空部分主存，存放来自辅存要调入的那部分内容。常见的替换算法有4种：

   • 随机算法：用软件或硬件随机数产生器确定替换的页面。
   • 先进先出：先调入主存的页面先替换。
   • 近期最少使用算法(LRU，Least Recently Used)：替换最长时间不用的页面。
   • 最优算法：替换最长时间以后才使用的页面。这是理想化的算法，只能作为衡量其他各种算法优劣的标准。

虚拟存储器的效率是系统性能评价的重要内容，它与主存容量、页面大小、命中率，程序局部性和替换算法等因素有关。

三、内存寻址

四、缓冲区

1. 缓冲区(buffer)就是在内存中预留指定大小的存储空间用来对输入/输出(I/O)的数据作临时存储，这部分预留的内存空间就叫做缓冲区，也可称缓存(内核也需要缓冲区，即内核缓冲区)。缓冲区根据其对应的是输入设备还是输出设备，分为输入缓冲区和输出缓冲区。

2. 作用

   • 减少频繁I/O操作而引起频繁的系统调用
   • 在创建时就被分配内存且可以重用，从而减少动态分配和回收内存的次数

3. 组成：所有缓冲区都有4个属性：capacity、limit、position、mark，并遵循：mark <= position <= limit <= capacity.

4. 四个I/O事件

   • 模拟情形：假设有一个管道，进程A为管道的写入方，Ｂ为管道的读出方：

     • 假设一开始内核缓冲区是空的，B作为读出方被阻塞着；然后首先A往管道写入，这时候内核缓冲区由空的状态变到非空状态，内核就会产生一个事件告诉Ｂ该醒来了，这个事件称之为“缓冲区非空”。
     • “缓冲区非空”事件通知B后，B却还没有读出数据，且内核许诺了不能把写入管道中的数据丢掉，这个时候Ａ写入的数据会滞留在内核缓冲区中；如果内核缓冲区也满了，B仍未开始读数据，这个时候会产生一个I/O事件，告诉进程A你该等等(阻塞)了，这个事件定义为“缓冲区满”。
     • 假设后来Ｂ终于开始读数据了，于是内核的缓冲区空了出来，这时候内核会告诉A内核缓冲区有空位了，你可以从长眠中醒来继续写数据了，这个事件定义为“缓冲区非满”。
     • 也许事件“缓冲区非满”已经通知了A，但是A也没有数据写入了，而Ｂ继续读出数据，一直到内核缓冲区空了。这个时候内核就告诉B，你需要阻塞了，这个事件定义为“缓冲区空”。

   • 这四个情形涵盖了四个I/O事件：缓冲区满，缓冲区空，缓冲区非空，缓冲区非满，这四个I/O事件是进行阻塞同步的根本。阻塞I/O模式下一个线程只能处理一个流的I/O事件，如果想要同时处理多个流，要么多进程(fork)，要么多线程(pthread_create)，这两种方法效率都不高。阻塞模式下，内核对于I/O事件的处理是阻塞或者唤醒，而非阻塞模式下则把I/O事件交给其他对象。

   • 于是再来考虑非阻塞忙轮询的I/O方式，我们发现可以同时处理多个流了：

     1 2 3 4 5 6

     while true { for i in stream[]; { if i has data read until unavailable } }

     • 我们只要不停的把所有流从头到尾问一遍就可以处理多个流了。但这样的做法显然不好，因为如果所有的流都没有数据，那么只会白白浪费CPU。为了避免CPU空转，可以引进了一个代理，它可以同时观察许多流的I/O事件，在空闲的时候会把当前线程阻塞掉，当有一个或多个流有I/O事件时就从阻塞态中醒来，于是我们的程序就会轮询一遍所有的流。

     1 2 3 4 5 6 7

     while true { select(streams[]) for i in streams[] { if i has data read until unavailable } }

     • 如果没有I/O事件产生，程序就会阻塞在select处。但是依然有个问题，我们从select那里仅仅知道了有I/O事件发生了，但却并不知道是哪几个流(可能有一个，多个，甚至全部)，我们只能无差别轮询所有流，找出能读出数据或写入数据的流，对他们进行操作。使用select有O(n)的无差别轮询复杂度，同时处理的流越多，每一次无差别轮询时间就越长。
     • select/poll是通过轮询的方法来获得就绪的状态，调用select/poll后就阻塞住，直到有就绪的文件描述符，或者超时，或者被中断。返回值是就绪的文件描述符的个数，需要遍历作为参数传入的文件描述符的位域或数组获得哪个文件描述符。

五、参考

1. 参考一
2. 参考二