不断的学习,我们才能不断的前进
一个好的程序员是那种过单行线马路都要往两边看的人

操作系统

1. 进程、线程、协程的区别是什么?进程和线程的通信方式?

进程

进程的本质是正在执行的一个程序实例,包括程序计数器、寄存器和变量当前的值。与每个进程相关的是地址空间,每启动一个进程,系统都会为其分配地址空间,建立数据表来维护代码段、PCB(进程控制快)和数据段。进程基本上是容纳运行一个程序所需要所有信息的容器。

PCB 包括:进程标识符、进程调度信息(优先级、进程的状态)、进程状态信息(堆栈信息、寄存器信息)
地址空间是虚拟内存,通过页表来记录虚拟内存到物理内存直接的映射关系

僵尸进程
僵尸进程是当子进程比父进程先结束,而父进程又没有回收子进程,释放子进程占用的资源,此时子进程将成为一个僵尸进程,但仍然保留一些信息,等待其父进程为其收尸。如果父进程先退出,并且没有调用wait()释放子进程的资源,子进程被init接管,子进程退出后init会回收其占用的相关资源。解决方案就是找到僵尸进程的父进程,并杀死父进程。

一个进程结束了,但是他的父进程没有等待(调用wait / waitpid)他, 那么他将变成一个僵尸进程。 但是如果该进程的父进程已经先结束了,那么该进程就不会变成僵尸进程, 因为每个进程结束的时候,系统都会扫描当前系统中所运行的所有进程, 看有没有哪个进程是刚刚结束的这个进程的子进程,如果是的话,就由Init 来接管他,成为他的父进程,并等待子进程。

线程

线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈)。

关系与区别

  • 一个线程只能属于一个进程,而一个进程可以有多个线程,但至少有一个主线程。
  • 资源分配给进程,同一进程的所有线程共享该进程的所有资源。
  • 线程作为调度和分配的基本单位,进程作为拥有资源的基本单位。
  • 不仅进程之间可以并发执行,同一个进程的多个线程之间也可以并发执行。
  • 进程是拥有资源的一个独立单位,线程不拥有系统资源,但可以访问隶属于进程的资源。
  • 线程中执行时一般都要进行同步和互斥,因为他们共享同一进程的所有资源
  • 进程拥有一个完整的虚拟地址空间,不依赖于线程而独立存在。反之,线程是进程的一部分,没有自己的地址空间,与进程内的其他线程一起共享分配给该进程的所有资
  • 线程的改变只代表了 CPU 执行过程的改变,而没有发生进程所拥有的资源变化。

进程间的通信

  1. 管道:管道是一种半双工的通信方式;匿名管道是只能用于存在父子关系的进程间通信,而且数据流向是单向的;命名管道;
    • 优点:速度快
    • 缺点:效率低,不适合进程间频繁地交换数据。
  2. 消息队列:消息队列是保存在内核中的消息链表,并由消息队列标识符标识。
    • 优点:克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
    • 缺点:通信不及时;消息大小也有限制;消息队列的读取和写入的过程,都会有发生用户态与内核态之间的消息拷贝过程。
  3. 共享内存:直接分配一个共享空间,每个进程都可以直接访问。
    • 优点:解决了消息队列通信中用户态与内核态之间数据拷贝过程带来的开销。
    • 缺点:多进程竞争同个共享资源会造成数据的错乱。
  4. 信号量:信号量其实是一个整型的计数器,主要用于实现进程间的互斥与同步,而不是用于缓存进程间通信的数据。 主要包括分别是 P 操作(把信号量减去一)和 V 操作(把信号量加上一)。
  5. 信号:对于异常情况下的工作模式,就需要用「信号」的方式来通知进程。信号是进程间通信机制中唯一的异步通信机制,因为可以在任何时候发送信号给某一进程。(SIGKILL 杀死进程、)
  6. Socket:如果要跨网络与不同主机上的进程之间通信,就需要 Socket 通信。

有哪些信号通信是不可靠的;为什么是不可靠的?
不可靠信号是指内核发送的信号可能会丢失,不进行排队处理;可靠信号是指可以实时接收,有序的,根据队列先注册的先执行。
SIGHUP(1号) 至 SIGSYS(31号)之间的信号都是继承自UNIX系统,是不可靠信号,也称为非实时信号;SIGRTMIN(33号) 与 SIGRTMAX(64号)之间的信号,它们都是可靠信号,也称为实时信号;

线程间的通信

同个进程下的线程之间都是共享进程的资源,只要是共享变量都可以做到线程间通信,比如全局变量,所以对于线程间关注的不是通信方式,而是关注多线程竞争共享资源的问题,信号量也同样可以在线程间实现互斥与同步。

协程

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

2. 讲讲同步、异步、阻塞、非阻塞?

同步和异步关注的是消息通信机制

  • 所谓同步,就是在发出一个调用时,在没有得到结果之前,该调用就不返回。但是一旦调用返回,就得到返回值了。
  • 而异步则是相反,调用在发出之后,这个调用就直接返回了,所以没有返回结果。换句话说,当一个异步过程调用发出后,调用者不会立刻得到结果。而是在调用发出后,被调用者通过状态、通知来通知调用者,或通过回调函数处理这个调用。

阻塞和非阻塞关注的是程序在等待调用结果(消息,返回值)时的状态。

  • 阻塞调用是指调用结果返回之前,当前线程会被挂起。调用线程只有在得到结果之后才会返回。
  • 非阻塞调用指在不能立刻得到结果之前,该调用不会阻塞当前线程。

3. 进程、线程切换上下文?

上下文信息是值:进程执行活动全过程的静态描述,包括PCB的内容、堆栈、寄存器的值、程序计数器的值。
上下文切换是指,CPU从一个进程或线程切换到另外一个进行或线程。上下文切换的主要步骤包括:

  1. 挂起当前进程,将当前进程的上下文信息保存到内核态里面。
  2. 在内核态里面根据进程调度方式,选择下一个进程的上下文信息并将其在 CPU 的寄存器中恢复。
  3. 跳转到程序计数器所指向的位置(即跳转到进程被中断时的代码行),以恢复该进程。

进程调度方式有:FIFO、短作业优先、非抢占式优先权算法、抢占式优先权调度算法、时间片轮询调度算法、多级反馈队列调度算法

多级反馈队列调度算法
设置多个就绪队列,并为各个队列赋予不同的优先级。第一个队列的优先级最高,第二个队列次之,其余各队列的优先权逐个降低。 在优先权愈高的队列中,为每个进程所规定的执行时间片就愈小。
当一个新进程进入内存后,首先将它放入第一队列的末尾,按FIFO原则排队等待调度,如果在分配的时间片内执行完毕之后,则可撤离系统;如果没有完成,则进入第二队列的末尾,同样按FIFO原则等待;以此内推,知道执行完毕。
仅当第一队列空闲时,调度程序才调度第二队列中的进程运行。如果处理机正在第i队列中为某进程服务时,又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列),则此时新进程将抢占正在运行进程的处理机。

进程切换与线程切换的不同

  • 进程切换涉及到虚拟地址空间的切换而线程切换则不会,因为线程是共享进程的虚拟地址空间。
  • 虚拟地址空间的切换是比较耗时的,涉及到内核态到用户态的切换。
  • 进程和线程都需要切换堆栈 和 寄存器的值。

再进行虚拟地址空间切换的时候,会刷新TLB页表缓存会重新刷新,导致内存的访问在一段时间内相当的低效。

线程上下文切换

每个线程都有一个程序计数器(记录要执行的下一条指令),一组寄存器(保存当前线程的工作变量),堆栈(记录执行历史,其中每一帧保存了一个已经调用但未返回的过程)

上下文切换会导致额外的开销,常常表现为高并发执行时速度会慢串行,因此减少上下文切换次数便可以提高多线程程序的运行效率。
线程切换的时间消耗
直接消耗:指的是CPU寄存器需要保存和加载, 系统调度器的代码需要执行, TLB实例需要重新加载, CPU 的pipeline需要刷掉
间接消耗:指的是多核的cache之间得共享数据, 间接消耗对于程序的影响要看线程工作区操作数据的大小
线程的调度

  • 抢占式调度:指的是每条线程执行的时间、线程的切换都由系统控制,系统控制指的是在系统某种运行机制下,可能每条线程都分同样的执行时间片,也可能是某些线程执行的时间片较长,甚至某些线程得不到执行的时间片。在这种机制下,一个线程的堵塞不会导致整个进程堵塞。
  • 协同式调度:指某一线程执行完后主动通知系统切换到另一线程上执行。

4. 线程阻塞几种情况?

  • 超时阻塞:当线程执行Thread.sleep()时,它一直阻塞到指定的毫秒时间之后,或者阻塞被另一个线程打断。
  • 等待阻塞:当线程碰到一条wait()语句时,它会一直阻塞到接到通知notify()。
  • 同步阻塞:线程也可以阻塞等待获取某个对象的一个排它锁。
  • I/O流阻塞:例如InputStream的read()方法,该方法一直阻塞到从流中读取一个字节的数据为止,它可以无限阻塞,因此不能指定超时时间。

并非所有的阻塞状态都是可中断的,以上阻塞状态的前两种可以被中断,后两种不会对中断做出反应.

5.线程有几种状态,线程生命周期讲讲?

  • 新建(New):创建后尚未启动的线程处于这种状态。
  • 运行(Runnable):包括操作系统线程状态中的Running和Ready,也就是说处于此状态的线程有可能正在执行,也有可能正在等待操作系统为它分配执行时间。
  • 无限期等待(Waiting):处于这种状态的线程不会被分配处理器执行时间,它们要等待被其他线程显式唤醒。Object::wait()、Thread::join()、LockSupport::park()方法会让线程进入无限期等待状态。
  • 限期等待(Timed Waiting):处于这种状态的线程也不会被分配处理器执行时间,不过无须等待被其他线程唤醒,在一定时间后由系统自动唤醒。Threa::sleep()、Object::wait(time)、Thread::join(time)、LockSupport::parknanos()、LockSupport::parkUntil()方法会让线程进入限期等待状态。
  • 阻塞(Blocked)等待:线程被阻塞了,阻塞状态与等待状态的区别是阻塞状态在等待着获取一个排它锁,这个事件在另外一个线程放弃这个锁的时候发生;而等待状态则是等待一段时间,或者唤醒动作的发生。
  • 结束(Terminated):已终止线程的线程状态。
    xian-cheng-zhuang-tai

什么是用户空间和内核空间?有什么区别?

用户空间就是用户进程所在的内存区域; 内核空间就是操作系统占据的内存区域,可以直接访问硬件设备。用户进程和系统进程的所有数据都在内存中。
内核态:当进程运行在内核空间时就处于内核态。
用户态:进程运行在用户空间时则处于用户态。

处于用户态的程序只能访问用户空间,而处于内核态的程序可以访问用户空间和内核空间
实际上一个进程有两个堆栈,分别用于用户态和内核态
内核态的权限是0,用户态的权限是3;

每个进程有两个堆栈,一个用户态堆栈,一个是内核态堆栈,用户态堆栈保存进程在用户态执行的代码,内核态堆栈保存程序进行系统调用时使用的数据 。
当线程从用户态切换到内核态时,先把用户态的状态信息保存到进程描述符中,然后把堆栈地址指向为内核态堆栈地址;当线程恢复用户态的时候, 将进程描述符中用户态的数据恢复到CPU各个寄存器内。

为什么要划分用户态和内核态?
所有的系统资源管理都是在内核空间中完成的。比如读写磁盘文件,分配回收内存,从网络接口读写数据等等。
假设没有这种内核态和用户态之分,程序随随便便就能访问硬件资源,比如说分配内存,程序能随意的读写所有的内存空间,如果程序出问题了,就很可能导致系统崩溃。

操作系统对内核级别的指令进行封装,统一管理硬件资源,然后向用户程序提供系统服务,用户程序进行系统调用后,操作系统执行一系列的检查验证,确保这次调用是安全的,再进行相应的资源访问操作。内核态能有效保护硬件资源的安全。

用户态切换到内核态的3种方式

  • 系统调用:用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作,比如fork()实际上就是执行了一个创建新进程的系统调用。
  • 异常:当CPU在执行运行在用户态下的程序时,发生了某些事先不可知的异常,这时会触发由当前运行进程切换到处理此异常的内核相关程序中,也就转到了内核态。
  • 外围设备的中断: 当外围设备完成用户请求的操作后,会向CPU发出相应的中断信号,这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序,如果先前执行的指令是用户态下的程序,那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成,系统会切换到硬盘读写的中断处理程序中执行后续操作等。

其中系统调用可以认为是用户进程主动发起的,异常和外围设备中断则是被动的。

Linux系统中,为什么要区分内核态和用户态

死锁?

死锁的定义:如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件,那么该进程集合就是死锁的。由于所有的进程都在等待,所以没有一个进程能够引发可以唤醒该进程集合中其他进程的事件,所以,所有的进程都只能无限期的等待。

产生死锁的四个条件

死锁发生的时候,下面四个条件都必须同时满足,任意一个不成立,死锁就不会发生。

  • 互斥条件:每个资源要么已经分配给了一个进程,要么就是可用的。
  • 占有和等待条件:已经得到某个资源的进程可以再请求新的资源。
  • 不可抢占条件:已经分配给一个进程的资源不能强制性地被抢占,它只能被占有它的进程显示释放。
  • 环路等待条件:死锁发送时,系统中一定有两个或两个以上的进程组成一条环路,该环路中的每个进程都在等待着下一个进程所占有的资源。

处理死锁的策略

有四种处理死锁的策略:

  • 忽略该问题:鸵鸟算法
  • 检测死锁并恢复:让死锁发生,检测他们是否发生,一旦发现死锁,则采取行动
  • 仔细对资源进行分配,动态的避免死锁。
  • 通过破坏引起死锁的四个条件之一,防止死锁发生。
    鸵鸟算法
    如果死锁很长时间才发生一次,而系统每周都会因硬件故障、编译器错误或操作系统错误而崩溃一次,那么就可以选择鸵鸟算法,忽略该死锁。
    死锁检测和死锁恢复
    允许死锁的发生,但当死锁发生后,采取措施进行恢复。
    死锁避免
    系统分配资源的时候,必须在保证安全的条件下进行资源分配。
    银行家算法:
    操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。

死锁预防
破坏死锁的四个条件之一即可。

操作系统内存管理

操作系统的内存管理主要负责内存的分配与回收(malloc 函数:申请内存,free 函数:释放内存),另外地址转换也就是将逻辑地址转换成相应的物理地址等功能也是操作系统内存管理做的事情。

内存管理简单分为连续分配管理方式和非连续分配管理方式这两种。连续分配管理方式是指为一个用户程序分配一个连续的内存空间,常见的如 块式管理 。同样地,非连续分配管理方式允许一个程序使用的内存分布在离散或者说不相邻的内存中,常见的如页式管理 和 段式管理。

  • 块式管理 : 将内存分为几个固定大小的块,每个块中只包含一个进程。如果程序运行需要内存的话,操作系统就分配给它一块,如果程序运行只需要很小的空间的话,分配的这块内存很大一部分几乎被浪费了。这些在每个块中未被利用的空间,我们称之为碎片
  • 页式管理 :把主存分为大小相等且固定的一页一页的形式,页较小,相对相比于块式管理的划分力度更大,提高了内存利用率,减少了碎片。页式管理通过页表对应逻辑地址和物理地址
  • 段式管理 : 页式管理虽然提高了内存利用率,但是页式管理其中的页实际并无任何实际意义。 段式管理把主存分为一段段的,每一段的空间又要比一页的空间小很多 。但是,最重要的是段是有实际意义的,每个段定义了一组逻辑信息,例如,有主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等。 段式管理通过段表对应逻辑地址和物理地址
  • 段页式管理机制 。段页式管理机制结合了段式管理和页式管理的优点。简单来说段页式管理机制就是把主存先分成若干段,每个段又分成若干页,也就是说 段页式管理机制 中段与段之间以及段的内部的都是离散的。

分页、分段的共同点和区别
共同点 :

  • 分页机制和分段机制都是为了提高内存利用率,较少内存碎片
  • 页和段都是离散存储的,所以两者都是离散分配内存的方式。但是,每个页和段中的内存是连续的
    区别 :
  • 页的大小是固定的,由操作系统决定;而段的大小不固定,取决于我们当前运行的程序。
  • 分页仅仅是为了满足操作系统内存管理的需求,而段是逻辑信息的单位,在程序中可以体现为代码段,数据段,能够更好满足用户的需要。

内存分配机制之伙伴算法和Slab分配器

当在用户模式下运行进程请求额外内存时,从内核维护的空闲页帧列表上分配页面。这个列表通常使用页面置换算法来填充。如果用户进程请求单个字节内存,那么就会导致内部碎片,因为进程会得到整个帧。

内核需要为不同大小的数据结构请求内存,其中有的小于一页。因此,内核应保守地使用内存,并努力最小化碎片浪费
用户模式进程分配的页面不必位于连续物理内存。然而,有的硬件设备与物理内存直接交互,即无法享有虚拟内存接口带来的便利,因而可能要求内存常驻在连续物理内存中。

伙伴系统

Linux内核中引入了伙伴系统算法。把所有的空闲页框分组为11个块链表,每个块链表分别包含大小为1,2,4,8,16,32,64,128,256,512和1024个连续页框的页框块。最大可以申请1024个连续页框,对应4MB大小的连续内存。每个页框块的第一个页框的物理地址是该块大小的整数倍,

buddy

Demo: 假设要申请一个256个页框的块,先从256个页框的链表中查找空闲块,如果没有,就去512个页框的链表中找,找到了则将页框块分为2个256个页框的块,一个分配给应用,另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块,继续向1024个页框的链表查找,如果仍然没有,则返回错误。页框块在释放时,会主动将两个连续的页框块合并为一个较大的页框块

伙伴系统的一个优点是:通过称为合并的技术,可以将相邻伙伴快速组合以形成更大分段
伙伴系统的明显缺点是:由于是 2 的幂,很可能造成分配段内的碎片。例如,33KB 的内存请求只能使用 64KB 段来满足。

Slab分配器

伙伴系统是以页为单位管理和分配内存,但是当申请以字节为单位的内存时,就会造成内存浪费。slab分配器就专为小内存分配而生。slab分配器分配内存以Byte为单位。但是slab分配器并没有脱离伙伴系统,而是基于伙伴系统分配的大内存进一步细分成小内存分配。

每个 slab 由一个或多个物理连续的页面组成,每个 cache 由一个或多个 slab 组成,每个内核数据结构都有一个 cache。

slab 分配算法采用 cache 来存储内核对象。在创建 cache 时,若干起初标记为 free 的对象被分配到 cache。cache 内的对象数量取决于相关 slab 的大小。
最初,cache 内的所有对象都标记为空闲。当需要内核数据结构的新对象时,分配器可以从 cache 上分配任何空闲对象以便满足请求。从 cache 上分配的对象标记为 used(使用)。
slab

在 Linux 中,slab 可以处于三种可能状态之一:

  • 满的:slab 的所有对象标记为使用。
  • 空的:slab 上的所有对象标记为空闲。
  • 部分:slab 上的对象有的标记为使用,有的标记为空闲。

slab 分配器首先尝试在部分为空的 slab 中用空闲对象来满足请求。如果不存在,则从空的 slab 中分配空闲对象。如果没有空的 slab 可用,则从连续物理页面分配新的 slab,并将其分配给 cache;从这个 slab 上,再分配对象内存。

slab 分配器提供两个主要优点:

  • 没有因碎片而引起内存浪费。碎片不是问题,因为每个内核数据结构都有关联的 cache,每个 cache 都由一个或多个 slab 组成,而 slab 按所表示对象的大小来分块。因此,当内核请求对象内存时,slab 分配器可以返回刚好表示对象的所需内存。
  • 可以快速满足内存请求。因此,当对象频繁地被分配和释放时,如来自内核请求的情况,slab 分配方案在管理内存时特别有效。分配和释放内存的动作可能是一个耗时过程。然而,由于对象已预先创建,因此可以从 cache 中快速分配。再者,当内核用完对象并释放它时,它被标记为空闲并返回到 cache,从而立即可用于后续的内核请求

cache可以表示进程描述符、文件对象、信号量等的数据结构

虚拟内存

虚拟内存是指每一个程序都有自己的地址空间,这个空间被分割成很多块、每一块称为页 或者 页面,每一页都是连续的地址范围,通过映射表, 这些页被映射到物理内存,使得逻辑上的虚拟内存连续,但物理上的物理内存允许不连续
虚拟内存是通过分页将地址空间分割成固定大小的单元。物理内存被抽象成固定大小的单元,每个单元称为页帧(frame)。通过分页管理内存可以避免分段带来的内存外碎片问题。

虚拟地址由:虚拟页号+虚拟地址偏移量
物理地址由:物理页帧号+物理地址偏移量
虚拟页面号用于索引物理页帧号
PS 每个程序的内存空间可能会有共享的。比如进程间用共享内存来通信。

虚拟内存的出现是为了解决程序直接操作物理内存可能会导致一系列的问题,包括:

  1. 内存不足:如果是逻辑内存直接映射到物理内存,当逻辑内存超过物理内存的时候,计算机就会出现内存不足的情况,导致程序崩溃。
  2. 内存碎片化:如果程序频率启动或退出,会产生内存碎片,对于连续分配内存时,即使碎片内存数量比申请的内存大,但可能导致申请失败,因为没有足够的连续内存。
  3. 程序间互相修改内存:如果程序切换时,不同的程序指向相同的内存时,会导致修改数据错乱。

页表

页表是一种数据结构,它用于计算机操作系统中的虚拟内存系统,其存储了虚拟地址到物理地址间的映射。每个进程都有 自己的虚拟地址,所以每一个进程都有一个页表,所以页表所需要的空间是很大的,页表都存储在物理内存中,通过多级页表配合缺页异常的方式 来避免把全部的页表放在内存里面导致占用太大的内存空间。
多级页表就是把一级页表放在内存里面,需要使用的时候从硬盘里面加载二级页表,这样做可以降低内存的使用。多级页表查找过程:首先通过页表基址寄存器查找到一级页表,然后通过一级页表找到二级页表,再配置页表偏移量找到物理地址。 多级页表存在的问题就是耗费CPU的时间,需要进行额外的内存访问,所以通过块表/TLB 进行地址转换缓存TLB的作用是做页表转换的时候不再访问内存,而是访问缓存,因此降低时间的消耗。主要步骤是

  • 从虚拟地址中提取页号(VPN),检查TLB是否有该VPN的转换映射
  • 如果有,则表示TLB命中,意味着从TLB中找到VPN对应的物理页框号(PFN)。PFN与虚拟地址的偏移量组成成物理地址(PA)。
  • 如果没有,表示TLB未命中,则需要处理TBL miss,有两种处理方式:
    • 一种是硬件处理。硬件处理TLB miss会自动更新TLB。
    • 软件处理则是由硬件抛出一个TLB miss异常,软件进入异常处理程序,查找物理页表中转换映射,再由指令更新TLB,并从异常中返回。

一个页表的大小要花费4MB的内存空间,所以使用多级页表

页表的结构

  • PFN物理页帧号;
  • 有效位(valid),用于标记页面是否有效;
  • 存在位(present),指示该页是否存在于物理内存,用于页面换入换出(swap);
  • 特权标记,指示页面访问的特权等级;
  • Dirty位,写操作时设置该位,表示页面被写过,页面交换时使用;

分页机制如何完成进程地址空间切换
每个进程都拥有自己独立的地址空间,进程切换时地址空间也会切换。不同进程都拥有自己的一套页表,因而即使两个进程虚拟地址相同,映射的物理地址也是不同的。进程切换时,只需要设置页表基址寄存器即可完成页表的切换,也就完成了进程地址空间的切换。

局部性原理
基于局部性原理,在程序装入时,可以将程序的一部分装入内存,而将其他部分留在外存,就可以启动程序执行。由于外存往往比内存大很多,所以我们运行的软件的内存大小实际上是可以比计算机系统实际的内存大小大的。在程序执行过程中,当所访问的信息不在内存时,由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面,操作系统将内存中暂时不使用的内容换到外存上,从而腾出空间存放将要调入内存的信息。这样,计算机好像为用户提供了一个比实际内存大的多的存储器

缺页中断:如果需执行的指令或访问的数据尚未在内存,则由处理器通知操作系统将相应的页面或段调入到内存

内存置换

当发生缺页中断,或者内存不足时,操作系统会把根据置换算法把暂时不用的内存页置换到硬盘里(如果该页面有脏数据,需要先写入磁盘), 并更新映射关系到硬盘上,再更新 新申请的内存映射关系。如果虚拟内存映射的内存在硬盘上,操作系统就会把内存从硬盘加载到内存里,然后修改映射关系
常用的内存置换算法有

  • 最优置换算法(不可能实现的算法):每次将最不可能使用的内存置换到硬盘里面。
  • 最近未使用页面置换算法LRU:
  • 先进先出页面置换算法FIFO:操作系统维护一个链表,最新使用的页面放在末尾,最早使用的放在表头,每次都置换表头的页面。可能会置换掉使用很频繁的页面,会导致性能下降。
  • 第二次机会置换算法:在先进先出算法上面加了一个标志位,表示表头那个页面,是否是经常使用,如果是的话,置换的时候插入到链表末尾,然后继续选择页面置换;否则立刻置换掉。
  • 时钟页面置换算法:给每个页面设计一个标志位,0表示没有使用,1表示使用。把所有的页面保存在类似时钟的环形链表中,访问一个页面的时候设置标志位为1。当访问不存在的页,也就是发生缺页中断的时候,判断当前指向的标志位是否是0,是的话则替换当前页面,否则把当前页面标志位设置为0,然后指向下一个页面,并重新进行判断,依次类推,直到替换成功。
  • 最近最少使用页面置换算法LFU:

地址变换的流程

nei-cun-di-zhi-zhuan-huan-guo-cheng

块表TLB 和 多级页表

虚拟地址被分为虚拟页号(高位) 和 偏移量(低位)两部分,虚拟页号 作用页表的索引,以找到虚拟页面对应的页表项,由页表项找到页框号,然后把页框号替换高位的虚拟页号,变成实际内存的物理地址

在分页内存管理中,很重要的两点是:

  • 虚拟地址到物理地址的转换要快: 每条指令在进行虚拟地址到内存地址的映射时候,需要进行一次或者两次以上的页表访问。(TLB )
  • 解决虚拟地址空间大,页表也会很大的问题。(多级页表)

块表 TLB

为了解决虚拟地址到物理地址的转换速度,操作系统在 页表方案 基础之上引入了 快表TLB 来加速虚拟地址到物理地址的转换。我们可以把快表理解为一种特殊的高速缓冲存储器(Cache),其中的内容是页表的一部分或者全部内容。作为页表的 Cache,它的作用与页表相似,但是提高了访问速率。
由于采用多级页表做地址转换,读写内存数据时 CPU 要访问两次主存。有了快表,有时只要访问一次高速缓冲存储器,一次主存,这样可加速查找并提高指令执行速度。

使用快表之后的地址转换流程是这样的:

  • 根据虚拟地址中的页号查快表;
  • 如果该页在快表中,直接从快表中读取相应的物理地址;
  • 如果该页不在快表中,就访问内存中的页表,再从页表中得到物理地址,同时将页表中的该映射表项添加到快表中(如果内存中没有页表,则从外存中读取,页缺失);
  • 当快表填满后,又要登记新页时,就按照一定的淘汰策略淘汰掉快表中的一个页(页替换)。

多级页表

引入多级页表的主要目的是为了避免把全部页表一直放在内存中占用过多空间,特别是那些根本就不需要的页表就不需要保留在内存中。多级页表属于时间换空间的典型场景。

多级页表就是把一级页表放在内存里面,需要使用的时候从硬盘里面加载二级页表,这样做可以降低内存的使用多级页表查找过程:首先通过页表基址寄存器查找到一级页表,然后通过一级页表找到二级页表,再配置页表偏移量找到物理地址。 多级页表存在的问题就是耗费CPU的时间,需要进行额外的内存访问

磁盘调度算法

各个进程可能会不断提出不同的对磁盘进行读/写操作的请求,因为进程的发送请求的速度比磁盘响应的还要快,所以为每个磁盘设备建立一个等待队列,常见的调度算法有:

  • 先来先服务算法:根据进程请求访问磁盘的先后顺序进行调度
    • 优点:公平
    • 缺点:效率不高,相邻两次请求可能会造成最内到最外的柱面寻道,使磁头反复移动,增加了服务时间,对机械也不利。平均寻道距离大;
  • 最短寻道时间优先算法:选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道,以使每次的寻找时间最短。
    • 优点:减少了磁盘的服务时间,比先来先服务好
    • 缺点:有些请求,可能长期得不到处理,无法保证平均寻道时间最短
  • 扫描算法:在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象,由于磁头移动规律与电梯运行相似,故又称为电梯调度算法。
    • 优点:克服了最短寻道优先的缺点,既考虑了距离,同时又考虑了方向
    • 缺点:对最近扫描过的区域不公平,不利于远离磁头一端的访问请求
  • 循环扫描算法:在扫描算法的基础上规定磁头单向移动来提供服务,回返时直接快速移动至起始端而不服务任何请求。
    • 优点:消除了对两端磁道请求的不公平

Linux中rm(删除)正在被进程占用的文件会发生什么?

在 Linux 系统中,通过 rm 命令删除一个文件,实际上是在相应的目录结构中 unlink 这个文件。如果这个文件仍然被打开着,这个文件仍然可以被这个进程所使用,并将继续占用磁盘空间。等这个程序关闭该文件后,对应文件的空间才会被释放。

一个文件在文件系统中分为两个部分:数据部分指针部分;数据被删除后,指针部分就从文件系统中清除了,而数据部分就可以被覆盖并写入新的内容,但是此时因为有进程一直占用这个文件,会导致数据部分无法被清除


目录