操作系统

2、SQL语言四大类别

3、垂直分表和水平分表

4、淘汰策略【页式系统】

5、任务（进程）调度算法

操作系统

系统调用与库函数的区别

1、系统调用

（1）操作系统提供了一组特殊接口——系统调用

通过这组接口用户程序可以使用操作系统内核提供的各种功能。例如分配内存、创建进程、实现进程之间的通信等。

（2）用户程序向操作系统提出请求的接口就是系统调用

所有的操作系统都会提供系统调用接口，只不过不同的操作系统提供的系统调用接口各不相同。

（3）系统调用按照功能分类

进程控制、进程间通信、文件系统控制、存储管理、网络管理、套接字控制、用户管理等。

2、库函数

对系统调用的一种封装，因为系统调用是面对的是操作系统，系统包括Linux、Windows等，如果直接系统调用，会影响程序的移植性，所以这里使用了库函数。

用户编程接口API：

前面提到利用系统调用接口程序可以访问各种资源，但在实际开发中程序并不直接使用系统调用接口，

而是使用用户编程接口（API）【各种库（最᯿要的就是C库）中的函数】。

不直接使用系统调用接口原因如下：

1. 系统调用接口功能非常简单，无法满足程序的需求
2. 不同操作系统的系统调用接口不兼容，程序移植时工作ᰁ大

页面淘汰算法

1、淘汰策略（页式系统）

（1）置换算法

当主存块已全部用完，添加新的一页进主存，选择淘汰哪一页的规则

（2）颠簸（抖动）

导致系统效率急剧下降的主存和辅存之间的频繁页面置换现象。

系统为每一个进入主存的程序分配的主存块数m是固定的；

2、最佳算法（OPT算法）

每次选择的淘汰页面将是以后永不使用，或者在最长时间内都不再访问的页面（保证最低的缺页率）

该算法是无法实现的

原因：操作系统无法提前判断页面访问序列

一般该算法作为衡ᰁ各种具体算法优劣的标准淘汰时参考的是未来将要执行的，但是只有在进程执行过程中才能知道接下来会访问到的是哪个页面

3、先进先出算法（FIFO算法）

每次淘汰选择在主存中居留时间最长（即进入最早）的一页淘汰。

实现的方法：

把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头；页面队列的最大长度取决于系统为进程分配了多少个内存块。

Belady异常：

当为进程分配的物理块数增大时，缺页次数不降反增的异常现象。（只有FIFO算法有该现象）

缺点：

该算法与进程实际运行时的规律不适用，因为先进入的页面可能经常被访问，算法性能较差。

4、最近最久未使用淘汰算法(Least Recently Used)（LRU算法）

每次淘汰的页面时最近最久未使用的页面。

实现方法：

（1）计数器：

赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以所经历的时间t（需要硬件支持，实现困难，开销大）

（2）堆栈（软件实现）

利用那个栈来登记主存中可淘汰的页号。每当一个页面被访问过，就立即将它的页号记载页号栈的顶部，而将栈中原有的页号依次下移。(淘汰的页面对应栈底页面)

5、LRU近似算法（软硬相结合）

在一个存储块有一个引用位：

当某块中的页面被访问时，这一位由硬件自动置1，而页面管理软件周期性（T）将所有引用位᯿新置“0”（在T内，访问过的页面为1，未访问过为0，需要置换一页时，淘汰应用那个位为0）

替换指针：