Grace Koo's Blog

One thing at a time

0%

操作系统

Posted on Edited on In
Symbols count in article: 12k Reading time ≈ 11 mins.

同步，异步，阻塞，非阻塞？

同步： 多个任务之间有先后顺序执行，一个执行完下个才能执行。

异步： 多个任务之间没有先后顺序，可以同时执行，有时候一个任务可能要在必要的时候获取另一个同时执行的任务的结果，这个就叫回调！

阻塞： 如果卡住了调用者，调用者不能继续往下执行，就是说调用者阻塞了。

非阻塞： 如果不会卡住，可以继续执行，就是说非阻塞的。

同步异步相对于多任务而言，阻塞非阻塞相对于代码执行而言。

同步阻塞、同步非阻塞、多路I/O复用、异步I/O

  • 同步阻塞I/O:

    当进程调用某些涉及I/O操作的系统调用或库函数时，比如send()、accept()等，进程便暂停下来，等I/O操作完成后再继续运行。

  • 同步非阻塞I/O: (轮询)

    1. 不会等待数据就绪，而是结合反复轮询来尝试数据是否就绪

    2. 与同步阻塞相比，同步非阻塞好处是在一个进程中可以同时处理多个I/O操作，而不是阻塞在一个I/O操作上

  • 多路I/O复用

    1. 允许进程通过一种方法来同时监听所有文件描述符，并可以快速获得所有就绪的文件描述符，然后只针对这些文件描述符进行数据访问。select、poll、epoll等函数使用了I/O 复用模型

  • 异步I/O

    1. 启动某个操作，并让内核在整个操作（包括等待数据和将数据从内核复制到用户空间）完成后通知应用进程。应用进程在整个操作期间都不会被阻塞。

Python异步使用场景有哪些

异步的使用场景:

1、 不涉及共享资源，获对共享资源只读，即非互斥操作

2、 没有时序上的严格关系

3、 不需要原子操作，或可以通过其他方式控制原子性

4、 常用于IO操作等耗时操作，因为比较影响客户体验和使用性能

5、 不影响主线程逻辑

select,poll和epoll

进程监视多个描述符

进程监视多个描述符

进程监视多个描述符

Select、poll、epoll都是I/O多路复用的机制。I/O多路复用就是通过一种机制，一个进程可以监视多个描述符，一旦某个描述符就绪（通常是读写操作），能够通知程序进行相应的读写操作。

都是I/O轮询的方法（同步I/O），它们都需要在读写事件就绪后自己负责读写。

聊聊I/O多路复用之select、poll、epoll

关于epoll的: http://www.cnblogs.com/my_life/articles/3968782.html

基本上select有3个缺点:

  1. 连接数受限：单个进程所打开的fd是有一定限制的
  2. 查找配对速度慢：对socket进行轮询扫描时是线性扫描，效率较低。
  3. 数据由内核拷贝到用户态：维护一个用来存放大量fd的数据结构，这样会使得用户空间和内核空间在传递该结构时复制开销大。

poll改善了第一个缺点：原因是它是基于链表来存储的

epoll改了三个缺点：epoll通过内核和用户空间共享一块内存来实现。通知机制需要很多函数回调。

边沿触发和水平触发

水平触发是只要满足条件就发生一个 io 事件，边缘触发是指每当状态变化时发生一个 io 事件。

如：epoll也是实现I/O多路复用的一种方法。

epoll有水平触发（level trigger，LT，LT为epoll的默认工作模式）与边缘触发（edge trigger，ET）两种工作模式。

  • 水平触发
  1. 对于读操作

只要缓冲内容不为空，LT模式返回读就绪。

  1. 对于写操作

只要缓冲区还不满，LT模式会返回写就绪。

  • 边缘触发
  1. 对于读操作

（1）当缓冲区由不可读变为可读的时候，即缓冲区由空变为不空的时候。

（2）当有新数据到达时，即缓冲区中的待读数据变多的时候。

（3）当缓冲区有数据可读，且应用进程对相应的描述符进行EPOLL_CTL_MOD 修改EPOLLIN事件时。

  1. 对于写操作

（1）当缓冲区由不可写变为可写时。

（2）当有旧数据被发送走，即缓冲区中的内容变少的时候。

（3）当缓冲区有空间可写，且应用进程对相应的描述符进行EPOLL_CTL_MOD 修改EPOLLOUT事件时。

进程与线程

进程总结

进程：程序运行在操作系统上的一个实例，就称之为进程。进程需要相应的系统资源：内存、时间片、pid。
创建进程：
首先要导入multiprocessing中的Process：
创建一个Process对象;
创建Process对象时，可以传递参数;

1
2
3
p = Process(target=XXX,args=(tuple,),kwargs={key:value})
target = XXX 指定的任务函数，不用加(),
args=(tuple,)kwargs={key:value}给任务函数传递的参数

使用start()启动进程
结束进程
给子进程指定函数传递参数Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import os
from mulitprocessing import Process
import time

def pro_func(name,age,**kwargs):
    for i in range(5):
        print("子进程正在运行中，name=%s,age=%d,pid=%d"%(name,age,os.getpid()))
        print(kwargs)
        time.sleep(0.2)
if __name__ =="__main__":
    #创建Process对象
    p = Process(target=pro_func,args=('小明',18),kwargs={'m':20})
    #启动进程
    p.start()
    time.sleep(1)
    #1秒钟之后，立刻结束子进程
    p.terminate()
    p.join()

注意：进程间不共享全局变量

进程之间的通信-Queue

在初始化Queue()对象时（例如q=Queue(),若在括号中没有指定最大可接受的消息数量，获数量为负值时，那么就代表可接受的消息数量没有上限一直到内存尽头）

Queue.qsize():返回当前队列包含的消息数量

Queue.empty():如果队列为空，返回True，反之False

Queue.full():如果队列满了，返回True,反之False

Queue.get([block[,timeout]]):获取队列中的一条消息，然后将其从队列中移除，

block默认值为True。

如果block使用默认值，且没有设置timeout（单位秒),消息队列如果为空，此时程序将被阻塞（停在读中状态），直到消息队列读到消息为止，如果设置了timeout，则会等待timeout秒，若还没读取到任何消息，则抛出“Queue.Empty”异常：

Queue.get_nowait()相当于Queue.get(False)

Queue.put(item,[block[,timeout]]):将item消息写入队列，block默认值为True;
如果block使用默认值，且没有设置timeout（单位秒），消息队列如果已经没有空间可写入，此时程序将被阻塞（停在写入状态），直到从消息队列腾出空间为止，如果设置了timeout，则会等待timeout秒，若还没空间，则抛出”Queue.Full”异常
如果block值为False，消息队列如果没有空间可写入，则会立刻抛出”Queue.Full”异常;
Queue.put_nowait(item):相当Queue.put(item,False)

进程间通信Demo:

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
from multiprocessing import Process.Queue
import os,time,random
#写数据进程执行的代码：
def write(q):
    for value in ['A','B','C']:
        print("Put %s to queue...",%value)
        q.put(value)
        time.sleep(random.random())
#读数据进程执行的代码
def read(q):
    while True:
        if not q.empty():
            value = q.get(True)
            print("Get %s from queue.",%value)
            time.sleep(random.random())
        else:
            break
if __name__=='__main__':
    #父进程创建Queue，并传给各个子进程
    q = Queue()
    pw = Process(target=write,args=(q,))
    pr = Process(target=read,args=(q,))
    #启动子进程pw ，写入：
    pw.start()
    #等待pw结束
    pw.join()
    #启动子进程pr，读取：
    pr.start()
    pr.join()
    #pr 进程里是死循环，无法等待其结束，只能强行终止:
    print('')
    print('所有数据都写入并且读完')
进程池Pool

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#coding:utf-8
from multiprocessing import Pool
import os,time,random

def worker(msg):
    t_start = time.time()
    print("%s 开始执行，进程号为%d"%(msg,os.getpid()))
    # random.random()随机生成0-1之间的浮点数
    time.sleep(random.random()*2)
    t_stop = time.time()
    print(msg,"执行完毕，耗时%0.2f”%（t_stop-t_start))

po = Pool(3)#定义一个进程池，最大进程数3
for i in range(0,10):
    po.apply_async(worker,(i,))
print("---start----")
po.close()
po.join()
print("----end----")

进程池中使用Queue

如果要使用Pool创建进程，就需要使用multiprocessing.Manager()中的Queue(),而不是multiprocessing.Queue(),否则会得到如下的错误信息：

RuntimeError： Queue objects should only be shared between processs through inheritance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from multiprocessing import Manager,Pool
import os,time,random
def reader(q):
    print("reader 启动(%s),父进程为（%s)"%(os.getpid(),os.getpid()))
    for i in range(q.qsize()):
        print("reader 从Queue获取到消息:%s"%q.get(True))

def writer(q):
    print("writer 启动（%s),父进程为(%s)"%(os.getpid(),os.getpid()))
    for i ini "itcast":
        q.put(i)
if __name__ == "__main__":
    print("(%s)start"%os.getpid())
    q = Manager().Queue()#使用Manager中的Queue
    po = Pool()
    po.apply_async(wrtier,(q,))
    time.sleep(1)
    po.apply_async(reader,(q,))
    po.close()
    po.join()
    print("(%s)End"%os.getpid())

多进程，多线程，协程

这个问题被问的概念相当之大。
进程：一个运行的程序（代码）就是一个进程，没有运行的代码叫程序，进程是系统资源分配的最小单位，进程拥有自己独立的内存空间，所有进程间数据不共享，开销大。

线程: cpu调度执行的最小单位，依赖进程存在，一个进程至少有一个线程，叫主线程，而多个线程共享内存（数据共享，共享全局变量), 从而极大地提高了程序的运行效率。

协程: 是一种用户态的轻量级线程，协程的调度完全由用户控制。协程拥有自己的寄存器上下文和栈。协程调度时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈，直接操作栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换非常快。

协程是进程和线程的升级版, 进程和线程都面临着内核态和用户态的切换问题而耗费许多切换时间,而协程就是用户自己控制切换的时机,不再需要陷入系统的内核态.（实际上当遇到IO操作时做切换才更有意义，（因为IO操作不用占用CPU））

Python里最常见的yield就是协程的思想!

协程：https://www.cnblogs.com/zingp/p/8678109.html

协程库：python asyncio的原理

asyncio这个库就是实现协程，底层都是基于生成器（yield）来实现的。

在生成器的基础上实现了：

  1. 现在的生成器虽然可以在暂停执行时吐出一个值，但是恢复生成器时，我们不能传入参数。 （言下之意是恢复协程时，应该需要支持传入参数）

  2. 现在的生成器不支持在 try block 中暂停（言下之意是协程应该要支持在 try block 中暂停）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> import asyncio
>>>
>>> async def hello_world():
...     print('hello world')
...
>>> async def job1():
...     print('job1 started...')
...     print('job1 paused')
...     await hello_world()
...     print('job1 resumed')
...     print('job1 finished')
...
>>> loop = asyncio.get_event_loop()
>>> loop.run_until_complete(job1())

http://cosven.me/blogs/88

僵尸进程和孤儿进程？怎么避免僵尸进程

  • 孤儿进程： 父进程退出，子进程还在运行的这些子进程都是孤儿进程，孤儿进程将被init 进程（进程号为1）所收养，并由init 进程对他们完成状态收集工作。

  • 僵尸进程： 进程使用fork 创建子进程，如果子进程退出，而父进程并没有调用wait （join方法）获waitpid 获取子进程的退出状态信息，那么子进程的进程描述符仍然保存在系统中的这些进程是僵尸进程。

避免僵尸进程的方法：

  1. 暴力法：结束父进程（主进程），父进程退出时子进程也会退出。

  2. 用wait使父进程阻塞：如join()方法来wait

  3. 使用信号量：在父进程中处理signal handler信号，在处理程序中调用waitpid, 这样父进程不用阻塞

进程与线程的使用场景

多线程适合在IO密性型操作（读写数据操作比较多的，比如爬虫）

多进程适合在CPU密集操作（cpu操作指令比较多，如位多的的浮点运算）。

IO密集型和CPU密集型区别

IO密集型： 系统运行，大部分的状况是CPU在等 I/O（硬盘/内存）的读/写

CPU密集型： 大部分时间用来做计算，逻辑判断等CPU动作的程序称之CPU密集型。

并行和并发

  • 并发（concurrency)：不会在同一时刻同时运行，存在交替执行的情况。（threading）

  • 并行（parallel）： 同一时刻多个任务同时在运行（multiprocessing）

程序需要执行较多的读写、请求和回复任务的需要大量的IO操作，IO密集型操作使用并发更好（I/O密集型 - 线程 - 并发）

CPU运算量大的程序，使用并行会更好（CPU密集型 - 进程 - 并行）

线程，进程是并发还是并行

  • 线程是并发

  • 进程是并行

进程之间互相独立，是系统分配资源的最小单位，同一个线程中的所有线程共享资源。

什么是多线程竞争

  • 线程是非独立的，同一个进程里线程是数据共享的，当各个线程访问数据资源时会出现竞争状态即：数据几乎同步会被多个线程占用，造成数据混乱，即所谓的线程不安全

  • 怎么解决多线程竞争问题？—- 锁

锁的好处： 确保了某段关键代码（共享数据资源）只能由一个线程从头到尾完整地执行能解决多线程资源竞争下的原子操作问题。

锁的坏处： 阻止了多线程并发执行，包含锁的某段代码实际上只能以单线程模式执行，效率就大大地下降了

锁的致命问题: 死锁

Python的线程同步

一、 setDaemon(False)
当一个进程启动之后，会默认产生一个主线程，因为线程是程序执行的最小单位，当设置多线程时，主线程会创建多个子线程，在Python中，默认情况下就是setDaemon(False), 主线程执行完自己的任务以后，就退出了，此时子线程会继续执行自己的任务，直到自己的任务结束。

例子

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

def thread():
    time.sleep(2)
    print('---子线程结束---')

def main():
    t1 = threading.Thread(target=thread)
    t1.start()
    print('---主线程--结束')

if __name__ =='__main__':
    main()
#执行结果
---主线程--结束
---子线程结束---

二、 setDaemon（True) — 主线程结束、子线程也结束
当我们使用setDaemon(True)时，这是子线程为守护线程，主线程一旦执行结束，则全部子线程被强制终止

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import threading
import time
def thread():
    time.sleep(2)
    print(’---子线程结束---')
def main():
    t1 = threading.Thread(target=thread)
    t1.setDaemon(True)#设置子线程守护主线程
    t1.start()
    print('---主线程结束---')

if __name__ =='__main__':
    main()
#执行结果
---主线程结束--- #只有主线程结束，子线程来不及执行就被强制结束

三、 join（线程同步) — 主线程等子线程结束后再结束
join 所完成的工作就是线程同步，即主线程任务结束以后，进入堵塞状态，一直等待所有的子线程结束以后，主线程再终止。

当设置守护线程时，含义是主线程对于子线程等待timeout的时间将会杀死该子线程，最后退出程序，所以说，如果有10个子线程，全部的等待时间就是每个timeout的累加和，简单的来说，就是给每个子线程一个timeou的时间，让他去执行，时间一到，不管任务有没有完成，直接杀死。

没有设置守护线程时，主线程将会等待timeout的累加和这样的一段时间，时间一到，主线程结束，但是并没有杀死子线程，子线程依然可以继续执行，直到子线程全部结束，程序退出。

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import threading
import time

def thread():
    time.sleep(2)
    print('---子线程结束---')

def main():
    t1 = threading.Thread(target=thread)
    t1.setDaemon(True)
    t1.start()
    t1.join(timeout=1)#1 线程同步，主线程堵塞1s 然后主线程结束，子线程继续执行
                        #2 如果不设置timeout参数就等子线程结束主线程再结束
                        #3 如果设置了setDaemon=True和timeout=1主线程等待1s后会强制杀死子线程，然后主线程结束
    print('---主线程结束---')

if __name__=='__main___':
    main()

多线程交互访问数据，如果访问到了就不访问了

怎么避免重读？

创建一个已访问数据列表，用于存储已经访问过的数据，并加上互斥锁，在多线程访问数据的时候先查看数据是否在已访问的列表中，若已存在就直接跳过。

锁

锁的种类

锁(Lock)是python提供的对线程控制的对象。有互斥锁，可重入锁，死锁。

  • 死锁：死锁是一个资源被多次调用，而多次调用方都未能释放该资源就会造成死锁
  • 互斥锁：threading.Lock
  • 可重入锁：threading.RLock，为了支持在同一线程中多次请求同一资源，python提供了“可重入锁”：threading.RLock。RLock内部维护着一个Lock和一个counter变量，counter记录了acquire的次数，从而使得资源可以被多次acquire。直到一个线程所有的acquire都被release，其他的线程才能获得资源。

死锁

若干子线程在系统资源竞争时，都在等待对方对某部分资源解除占用状态，结果是谁也不愿先解锁，互相干等着，程序无法执行下去，这就是死锁。

必要条件:

  1. 互斥条件
  2. 请求和保持条件
  3. 不剥夺条件
  4. 环路等待条件

处理死锁基本方法:

  1. 预防死锁(摒弃除1以外的条件)
  2. 避免死锁(银行家算法)：当一个进程申请使用资源的时候，银行家算法通过先 试探 分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待。
  3. 检测死锁(资源分配图)
  4. 解除死锁
    1. 剥夺资源
    2. 撤销进程

死锁概念处理策略详细介绍:https://wizardforcel.gitbooks.io/wangdaokaoyan-os/content/10.html

一个死锁的例子：

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
from threading import Lock, Thread
import time


def print_numbers():
    print("1")
    s2.acquire()
    print("2")
    s1.release()


def print_char():
    print("3")
    s1.acquire()
    print("4")
    s2.release()


if __name__ == "__main__":
    # 创建锁
    s1 = Lock()
    s2 = Lock()

    # 创建两个线程
    t1 = Thread(name="打印字符", target=print_numbers)
    t2 = Thread(name="打印字母", target=print_char)
    s1.acquire()
    s2.acquire()
    t1.start()
    t2.start()

互斥锁、线程安全

每个对象都对应于一个可称为’互斥锁‘的标记，这个标记用来保证在任一时刻，只能有一个线程访问该对象。

同一进程中的多线程之间是共享系统资源的，多个线程同时对一个对象进行操作，一个线程操作尚未结束，另一线程已经对其进行操作，导致最终结果出现错误，此时需要对被操作对象添加互斥锁，保证每个线程对该对象的操作都得到正确的结果。

GIL锁 全局解释器锁

作用： 限制多线程同时执行，保证同一时间只有一个线程执行，所以cython里的多线程其实是伪多线程！

所以python里常常使用协程技术来代替多线程，协程是一种更轻量级的线程。

进程和线程的切换时由系统决定，而协程由我们程序员自己决定，而模块gevent下切换是遇到了耗时操作时才会切换

三者的关系：进程里有线程，线程里有协程。

乐观锁和悲观锁

  • 悲观锁：假定会发生并发冲突，屏蔽一切可能违反数据完整性的操作

    互斥锁、可重入锁都属于悲观锁。当你读取或者写入数据时，你都悲观地认为有别人正在改动数据，所以你希望在你 操作数据的时候上锁，防止别人改动。当然，当已经有别人上锁，你必须等待别人操作完毕。

悲观锁的业务流程:

事务开始
查询、修改数据表之前 加锁
对数据库 操作
事务提交（检测、返回冲突）

  • 乐观锁：假设不会发生并发冲突，只在提交操作时检查是否违反数据完整性。

    Redis的并发竞争解决方案，使用乐观锁，成本低，非阻塞，性能高。

    每次去取数据的时候总认为不会有其他线程对数据进行修改，因此不会上锁，但是在更新时会判断其他线程在这之前有没有对数据进行修改。

乐观锁与悲观锁的具体区别:

http://www.cnblogs.com/Bob-FD/p/3352216.html

http://blog.csdn.net/chosen0ne/article/details/18093187)

多线程共同操作同一个数据互斥锁同步？

两个线程循环打印数字和字母

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
# -*- coding: utf-8 -*-
# @Time: 2020/11/9 11:00 
# @Author: GraceKoo
# @File: test.py
# @Desc:
from threading import Lock, Thread
import time


def print_numbers():
    for i in range(1, 27):
        if s1.acquire(): # 判断是否得到锁
            print(str(i))
            s1.release() # 释放锁
            time.sleep(0.2)


def print_char():
    for i in range(65, 91):
        if s1.acquire():
            print(chr(i))
            s1.release()
            time.sleep(0.2)

if __name__ == "__main__":
    # 创建锁
    s1 = Lock()

    # 创建两个线程
    t1 = Thread(name="打印字符", target=print_numbers)
    t2 = Thread(name="打印字母", target=print_char)
    t1.start()
    t2.start()

作业调度算法

  1. 先来先服务(FCFS, First Come First Serve)

  2. 短作业优先(SJF, Shortest Job First)

  3. 最高优先权调度(Priority Scheduling)

  4. 时间片轮转(RR, Round Robin)：把CPU的时间分给各个任务用

  5. 多级反馈队列调度(multilevel feedback queue scheduling)：能使优先级高的作业得到响应又能使短作业（进程）迅速完成。

    对于优先级高的作业，首先执行；

    对于优先级低的队列，采用时间片轮询的方法。

常见的调度算法总结:http://www.jianshu.com/p/6edf8174c1eb

实时调度算法:

  1. 最早截至时间优先 EDF
  2. 最低松弛度优先 LLF

程序编译与链接

推荐: http://www.ruanyifeng.com/blog/2014/11/compiler.html

Bulid过程可以分解为4个步骤:预处理(Prepressing), 编译(Compilation)、汇编(Assembly)、链接(Linking)

以c语言为例:

1 预处理

预编译过程主要处理那些源文件中的以“#”开始的预编译指令，主要处理规则有：

  1. 将所有的“#define”删除，并展开所用的宏定义
  2. 处理所有条件预编译指令，比如“#if”、“#ifdef”、 “#elif”、“#endif”
  3. 处理“#include”预编译指令，将被包含的文件插入到该编译指令的位置，注：此过程是递归进行的
  4. 删除所有注释
  5. 添加行号和文件名标识，以便于编译时编译器产生调试用的行号信息以及用于编译时产生编译错误或警告时可显示行号
  6. 保留所有的#pragma编译器指令。

2 编译

编译过程就是把预处理完的文件进行一系列的词法分析、语法分析、语义分析及优化后生成相应的汇编代码文件。这个过程是整个程序构建的核心部分。

3 汇编

汇编器是将汇编代码转化成机器可以执行的指令，每一条汇编语句几乎都是一条机器指令。经过编译、链接、汇编输出的文件成为目标文件(Object File)

4 链接

链接的主要内容就是把各个模块之间相互引用的部分处理好，使各个模块可以正确的拼接。
链接的主要过程包块地址和空间的分配（Address and Storage Allocation）、符号决议(Symbol Resolution)和重定位(Relocation)等步骤。

静态链接和动态链接

  • 静态链接方法：静态链接的时候，载入代码就会把程序会用到的动态代码或动态代码的地址确定下来
    静态库的链接可以使用静态链接，动态链接库也可以使用这种方法链接导入库

  • 动态链接方法：使用这种方式的程序并不在一开始就完成动态链接，而是直到真正调用动态库代码时，载入程序才计算(被调用的那部分)动态代码的逻辑地址，然后等到某个时候，程序又需要调用另外某块动态代码时，载入程序又去计算这部分代码的逻辑地址，所以，这种方式使程序初始化时间较短，但运行期间的性能比不上静态链接的程序

虚拟内存技术

虚拟存储器是指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储系统.

分页和分段

分页: 用户程序的地址空间被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。

分段: 将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。

分页与分段的主要区别

  1. 页是信息的物理单位,分页是为了实现非连续分配,以便解决内存碎片问题,或者说分页是由于系统管理的需要.

    段是信息的逻辑单位,它含有一组意义相对完整的信息,分段的目的是为了更好地实现共享,满足用户的需要.

  2. 页的大小固定,由系统确定,将逻辑地址划分为页号和页内地址是由机器硬件实现的.

    而段的长度却不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时根据信息的性质来划分.

  3. 分页的作业地址空间是一维的.

    分段的地址空间是二维的.

页面置换算法

  1. 最佳置换算法OPT:不可能实现，选择的被淘汰的页面将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。采用最佳置换算法通常可保证最低的缺页率。
  2. 先进先出FIFO
  3. 最近最久未使用算法LRU: 最近一段时间里最久没有使用过的页面予以置换.
  4. clock算法