个人整理的面试题汇总(三)——操作系统

文件描述符

0 ,1,2叫文件描述符;Linux中,每打开一个文件都有一个小的整数与之对应,就是文件描述符!
0 是标准输入的 (stdin)
1 是标准输出的 (stdout)
2 是标准报错输出的 (stderr)
'<'是输入重定向符
‘>’是输出重定向符

软链接和硬链接的区别

对于一个文件来说,有唯一的索引接点(inode)与之对应,而对于一个索引接点号,却可以有多个文件名与之对应。因此,在磁盘上的同一个文件可以通过不同的路径去访问该文件。Linux下是一切皆文件的,文件夹、新加的硬盘 …都可以看着文件来处理。

软链接实际上只是一段文字,里面包含着它所指向的文件的名字,系统看到软链接后自动跳到对应的文件位置处进行处理;相反,硬链接为文件开设一个新的目录项,硬链接与文件原有的名字是平权的,在Linux看来它们是等价的。由于这个原因,硬链接不能连接两个不同文件系统上的文件。

  • 硬链接: 与普通文件没什么不同,inode 都指向同一个文件在硬盘中的区块
  • 软链接: 保存了其代表的文件的绝对路径,是另外一种文件,在硬盘上有独立的区块,访问时替换自身路径。

Linux 中进程状态

(1)、不可中断状态:进程处于睡眠状态,但是此刻进程是不可中断的。不可中断, 指进程不响应异步信号。 (2)、暂停状态/跟踪状态:向进程发送一个 SIGSTOP 信号,它就会因响应该信号 而进入 TASK_STOPPED 状态;当进程正在被跟踪时,它处于 TASK_TRACED 这个特殊的状态。 “正在被跟踪”指的是进程暂停下来,等待跟踪它的进程对它进行操作。

(3)、就绪状态:在 run_queue 队列里的状态

(4)、运行状态:在 run_queue 队列里的状态 (5)、可中断睡眠状态:处于这个状态的进程因为等待某某事件的发生(比如等待 socket 连接、等待信号量),而被挂起 (6)、zombie 状态(僵尸):父亲没有通过 wait 系列的系统调用会顺便将子进程的尸体(task_struct)也释放掉 (7)、退出状态

协程

协程(Coroutines)是一种比线程更加轻量级的存在,正如一个进程可以拥有多个线程一样,一个线程可以拥有多个协程。

个人整理的面试题汇总(三)——操作系统

操作系统中的协程

协程不是被操作系统内核所管理的,而是完全由程序所控制,也就是在用户态执行。这样带来的好处是性能大幅度的提升,因为不会像线程切换那样消耗资源。

协程不是进程也不是线程,而是一个特殊的函数,这个函数可以在某个地方挂起,并且可以重新在挂起处外继续运行。所以说,协程与进程、线程相比并不是一个维度的概念。

一个进程可以包含多个线程,一个线程也可以包含多个协程。简单来说,一个线程内可以由多个这样的特殊函数在运行,但是有一点必须明确的是,一个线程的多个协程的运行是串行的。如果是多核CPU,多个进程或一个进程内的多个线程是可以并行运行的,但是一个线程内协程却绝对是串行的,无论CPU有多少个核。毕竟协程虽然是一个特殊的函数,但仍然是一个函数。一个线程内可以运行多个函数,但这些函数都是串行运行的。当一个协程运行时,其它协程必须挂起。

进程、线程、协程的对比

  • 协程既不是进程也不是线程,协程仅仅是一个特殊的函数,协程它进程和进程不是一个维度的。
  • 一个进程可以包含多个线程,一个线程可以包含多个协程。
  • 一个线程内的多个协程虽然可以切换,但是多个协程是串行执行的,只能在一个线程内运行,没法利用CPU多核能力。
  • 协程与进程一样,切换是存在上下文切换问题的。

上下文切换

  • 进程的切换者是操作系统,切换时机是根据操作系统自己的切换策略,用户是无感知的。进程的切换内容包括页全局目录、内核栈、硬件上下文,切换内容保存在内存中。进程切换过程是由“用户态到内核态到用户态”的方式,切换效率低。
  • 线程的切换者是操作系统,切换时机是根据操作系统自己的切换策略,用户无感知。线程的切换内容包括内核栈和硬件上下文。线程切换内容保存在内核栈中。线程切换过程是由“用户态到内核态到用户态”, 切换效率中等。
  • 协程的切换者是用户(编程者或应用程序),切换时机是用户自己的程序所决定的。协程的切换内容是硬件上下文,切换内存保存在用户自己的变量(用户栈或堆)中。协程的切换过程只有用户态,即没有陷入内核态,因此切换效率高。
  • 上面说的全局目录就是页表,内核栈就是函数的执行栈,或者说代码,硬件上下文就是指寄存器中的数据,硬件上下文切换就是指保存当前寄存器中要切换出的进程的数据,将要切换进来的进程的数据存入寄存器。

线程/进程

进程:在操作系统中能够独立运行,并且作为资源分配的基本单位。它表示运行中的程序。

线程:是进程中的一个实例,作为系统调度和分派的基本单位。是进程中的一段序列,能够完成进程中的一个功能。

1.同一个进程可以包含多个线程,一个进程中至少包含一个线程,一个线程只能存在于一个进程中。

2.同一个进程下的所有线程能够共享该进程下的资源。(系统运行时会为每个进程分配不同的内存区域,但不会为线程分配内存。线程只能共享它所属进程的资源。)

3.进程结束后,该进程下的所有线程将销毁,而一个线程的结束不会影响同一进程下的其他线程。

4.线程是轻量级的进程,它的创建和销毁所需要的时间比进程小得多,所有操作系统的执行功能都是通过创建线程去完成的。

5.线程在执行时是同步和互斥的,因为他们共享同一个进程下的资源。

6.在操作系统中,进程是拥有系统资源的独立单元,它可以拥有自己的资源。一般而言,线程不能拥有自己的资源,但是它能够访问其隶属进程的资源。

进程状态转换

个人整理的面试题汇总(三)——操作系统

就绪状态 -> 运行状态:处于就绪状态的进程被调度后,获得处理机资源(分派处理机时间片),于是进程由就绪状态转换为运行状态。

运行状态 -> 就绪状态:处于运行状态的进程在时间片用完后,不得不让出处理机,从而进程由运行状态转换为就绪状态。此外,在可剥夺的操作系统中,当有更高优先级的进程就 、 绪时,调度程度将正执行的进程转换为就绪状态,让更高优先级的进程执行。

运行状态 -> 阻塞状态:当进程请求某一资源(如外设)的使用和分配或等待某一事件的发生(如I/O操作的完成)时,它就从运行状态转换为阻塞状态。进程以系统调用的形式请求操作系统提供服务,这是一种特殊的、由运行用户态程序调用操作系统内核过程的形式。

阻塞状态 -> 就绪状态:当进程等待的事件到来时,如I/O操作结束或中断结束时,中断处理程序必须把相应进程的状态由阻塞状态转换为就绪状态。

进程间的通信方式:

1.管道(pipe)及有名管道(named pipe):

管道可用于具有亲缘关系的父子进程间的通信,有名管道除了具有管道所具有的功能外,它还允许无亲缘关系进程间的通信。

2.信号(signal):

信号是在软件层次上对中断机制的一种模拟,它是比较复杂的通信方式,用于通知进程有某事件发生,一个进程收到一个信号与处理器收到一个中断请求效果上可以说是一致的。

3.消息队列(message queue):

消息队列是消息的链接表,它克服了上两种通信方式中信号量有限的缺点,具有写权限得进程可以按照一定得规则向消息队列中添加新信息;对消息队列有读权限得进程则可以从消息队列中读取信息。

4.共享内存(shared memory):

可以说这是最有用的进程间通信方式。它使得多个进程可以访问同一块内存空间,不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作,如互斥锁和信号量等。

共享内存是System V版本的最后一个进程间通信方式。共享内存,顾名思义就是允许两个不相关的进程访问同一个逻辑内存,共享内存是两个正在运行的进程之间共享和传递数据的一种非常有效的方式。不同进程之间共享的内存通常为同一段物理内存。进程可以将同一段物理内存连接到他们自己的地址空间中,所有的进程都可以访问共享内存中的地址。如果某个进程向共享内存写入数据,所做的改动将立即影响到可以访问同一段共享内存的任何其他进程。

特别提醒:共享内存并未提供同步机制,也就是说,在第一个进程结束对共享内存的写操作之前,并无自动机制可以阻止第二个进程开始对它进行读取,所以我们通常需要用其他的机制来同步对共享内存的访问,例如信号量。

共享内存的通信原理
在Linux中,每个进程都有属于自己的进程控制块(PCB)和地址空间(Addr Space),并且都有一个与之对应的页表,负责将进程的虚拟地址与物理地址进行映射,通过内存管理单元(MMU)进行管理。两个不同的虚拟地址通过页表映射到物理空间的同一区域,它们所指向的这块区域即共享内存。

当两个进程通过页表将虚拟地址映射到物理地址时,在物理地址中有一块共同的内存区,即共享内存,这块内存可以被两个进程同时看到。这样当一个进程进行写操作,另一个进程读操作就可以实现进程间通信。但是,我们要确保一个进程在写的时候不能被读,因此我们使用信号量来实现同步与互斥。

对于一个共享内存,实现采用的是引用计数的原理,当进程脱离共享存储区后,计数器减一,挂架成功时,计数器加一,只有当计数器变为零时,才能被删除。当进程终止时,它所附加的共享存储区都会自动脱离。

5.信号量(semaphore):

主要作为进程之间及同一种进程的不同线程之间得同步和互斥手段。

6.套接字(socket);

这是一种更为一般得进程间通信机制,它可用于网络中不同机器之间的进程间通信,应用非常广泛。

线程之间的同步通信:

1、通过共享对象通信

2、忙等待(Busy Wait)

3、wait(),notify()和notifyAll()

虚拟内存,页表

虚拟内存是操作系统为每个进程提供的一种抽象,每个进程都有属于自己的、私有的、地址连续的虚拟内存,当然我们知道最终进程的数据及代码必然要放到物理内存上,那么必须有某种机制能记住虚拟地址空间中的某个数据被放到了哪个物理内存地址上,这就是所谓的地址空间映射,也就是虚拟内存地址与物理内存地址的映射关系,那么操作系统是如何记住这种映射关系的呢,答案就是页表,页表中记录了虚拟内存地址到物理内存地址的映射关系。有了页表就可以将虚拟地址转换为物理内存地址了,这种机制就是虚拟内存。

个人整理的面试题汇总(三)——操作系统

每个进程都有自己的虚拟地址空间,进程内的所有线程共享进程的虚拟地址空间。在进程进行切换时,会发生页表的切换,CPU有一个TLB cache来保存页表,进程切换导致TLB失效,需要重新从内存中读取页表,因此非常耗时。

IO多路复用,select,poll,epoll

先说BIO,NIO和IO多路复用

Blocking IO:阻塞直到准备好数据

NIO:不阻塞,返回error,依赖轮询

IO多路复用:一个进程专门负责监听多个socket,任何一个准备好,就会返回,使用select,poll,epoll函数

select: 返回的活跃连接 ==select(全部待监控的连接)。 序言遍历所有连接,只能支持1024个,高并发下效率不高

poll:与select没有本质区别,只取消了最大1024个fd的区别

epoll:epoll精巧的使用了3个方法来实现select方法要做的事:

  1. 新建epoll描述符==epoll_create()

  2. epoll_ctrl(epoll描述符,添加或者删除所有待监控的连接)

  3. 返回的活跃连接 ==epoll_wait( epoll描述符 )

    与select相比,epoll分清了频繁调用和不频繁调用的操作。例如,epoll_ctrl是不太频繁调用的,而epoll_wait是非常频繁调用的。这时,epoll_wait却几乎没有入参,这比select的效率高出一大截,而且,它也不会随着并发连接的增加使得入参越发多起来,导致内核执行效率下降。

epoll三个关键要素:mmap,红黑树,链表,与前两个的O(N)相比,能实现O(1),数据结构叫做eventpoll,包含 lock、mtx、wq(等待队列)、rdlist等成员。rdlist和rbr是我们所关心的

epoll分离了创建监视集合和等待socket准备好数据,监视集合使用红黑树来实现,原因是增加删除都比较频繁,O(logN)。维护了一个就绪链表,因此当监视进程被唤醒后,直接去读取就绪链表的记录,就得到了所有的就绪socket,这是O(1)的。而后者是频繁进行的操作,因此整体的时间复杂度为O(1)。

操作系统保证线程安全

一般说来,确保线程安全的方法有这几个:竞争与原子操作、同步与锁、可重入、防过度优化

竞争与原子操作
多个线程同时访问和修改一个数据,可能造成很严重的后果。出现严重后果的原因是很多操作被操作系统编译为汇编代码之后不止一条指令,因此在执行的时候可能执行了一半就被调度系统打断了而去执行别的代码了。一般将单指令的操作称为原子的(Atomic),因为不管怎样,单条指令的执行是不会被打断的。

因此,为了避免出现多线程操作数据的出现异常,Linux系统提供了一些常用操作的原子指令,确保了线程的安全。但是,它们只适用于比较简单的场合,在复杂的情况下就要选用其他的方法了。

同步与锁
为了避免多个线程同时读写一个数据而产生不可预料的后果,开发人员要将各个线程对同一个数据的访问同步,也就是说,在一个线程访问数据未结束的时候,其他线程不得对同一个数据进行访问。

同步的最常用的方法是使用锁(Lock),它是一种非强制机制,每个线程在访问数据或资源之前首先试图获取锁,并在访问结束之后释放锁;在锁已经被占用的时候试图获取锁时,线程会等待,直到锁重新可用。

二元信号量是最简单的一种锁,它只有两种状态:占用与非占用,它适合只能被唯一一个线程独占访问的资源。对于允许多个线程并发访问的资源,要使用多元信号量(简称信号量)。

可重入
一个函数被重入,表示这个函数没有执行完成,但由于外部因素或内部因素,又一次进入该函数执行。一个函数称为可重入的,表明该函数被重入之后不会产生任何不良后果。可重入是并发安全的强力保障,一个可重入的函数可以在多线程环境下放心使用。

防过度优化
在很多情况下,即使我们合理地使用了锁,也不一定能够保证线程安全,因此,我们可能对代码进行过度的优化以确保线程安全。

我们可以使用volatile关键字试图阻止过度优化,它可以做两件事:第一,阻止编译器为了提高速度将一个变量缓存到寄存器而不写回;第二,阻止编译器调整操作volatile变量的指令顺序。

在另一种情况下,CPU的乱序执行让多线程安全保障的努力变得很困难,通常的解决办法是调用CPU提供的一条常被称作barrier的指令,它会阻止CPU将该指令之前的指令交换到barrier之后,反之亦然。

调度方式

一、先来先服务和短作业(进程)优先调度算法

1.先来先服务调度算法

先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。当在作业调度中采用该算法时,每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业,将它们调入内存,为它们分配资源、创建进程,然后放入就绪队列。在进程调度中采用FCFS算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

2.短作业(进程)优先调度算法

短作业(进程)优先调度算法SJ§F,是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程,将处理机分配给它,使它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时再重新调度。

二、高优先权优先调度算法

1.优先权调度算法的类型

为了照顾紧迫型作业,使之在进入系统后便获得优先处理,引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中,作为作业调度算法,也作为多种操作系统中的进程调度算法,还可用于实时系统中。当把该算法用于作业调度时,系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时,该算法是把处理机分配给就绪队列中优先权最高的进程,这时,又可进一步把该算法分成如下两种。

  1. 非抢占式优先权算法

在这种方式下,系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成;或因发生某事件使该进程放弃处理机时,系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中;也可用于某些对实时性要求不严的实时系统中。

  1. 抢占式优先权调度算法

在这种方式下,系统同样是把处理机分配给优先权最高的进程,使之执行。但在其执行期间,只要又出现了另一个其优先权更高的进程,进程调度程序就立即停止当前进程(原优先权最高的进程)的执行,重新将处理机分配给新到的优先权最高的进程。因此,在采用这种调度算法时,是每当系统中出现一个新的就绪进程i 时,就将其优先权Pi与正在执行的进程j 的优先权Pj进行比较。如果Pi≤Pj,原进程Pj便继续执行;但如果是Pi>Pj,则立即停止Pj的执行,做进程切换,使i 进程投入执行。显然,这种抢占式的优先权调度算法能更好地满足紧迫作业的要求,故而常用于要求比较严格的实时系统中,以及对性能要求较高的批处理和分时系统中。

2.高响应比优先调度算法

在批处理系统中,短作业优先算法是一种比较好的算法,其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权,并使作业的优先级随着等待时间的增加而以速率a 提高,则长作业在等待一定的时间后,必然有机会分配到处理机。该优先权的变化规律可描述为:

个人整理的面试题汇总(三)——操作系统

由于等待时间与服务时间之和就是系统对该作业的响应时间,故该优先权又相当于响应比RP。据此,又可表示为:

个人整理的面试题汇总(三)——操作系统

由上式可以看出:

(1) 如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而该算法有利于短作业。

(2) 当要求服务的时间相同时,作业的优先权决定于其等待时间,等待时间愈长,其优先权愈高,因而它实现的是先来先服务。

(3) 对于长作业,作业的优先级可以随等待时间的增加而提高,当其等待时间足够长时,其优先级便可升到很高,从而也可获得处理机。简言之,该算法既照顾了短作业,又考虑了作业到达的先后次序,不会使长作业长期得不到服务。因此,该算法实现了一种较好的折衷。当然,在利用该算法时,每要进行调度之前,都须先做响应比的计算,这会增加系统开销。

三、基于时间片的轮转调度算法

1.时间片轮转法

  1. 基本原理

在早期的时间片轮转法中,系统将所有的就绪进程按先来先服务的原则排成一个队列,每次调度时,把CPU 分配给队首进程,并令其执行一个时间片。时间片的大小从几ms 到几百ms。当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并将它送往就绪队列的末尾;然后,再把处理机分配给就绪队列中新的队首进程,同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之,系统能在给定的时间内响应所有用户的请求。

2.多级反馈队列调度算法

前面介绍的各种用作进程调度的算法都有一定的局限性。如短进程优先的调度算法,仅照顾了短进程而忽略了长进程,而且如果并未指明进程的长度,则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而多级反馈队列调度算法则不必事先知道各种进程所需的执行时间,而且还可以满足各种类型进程的需要,因而它是目前被公认的一种较好的进程调度算法。在采用多级反馈队列调度算法的系统中,调度算法的实施过程如下所述。

(1) 应设置多个就绪队列,并为各个队列赋予不同的优先级。第一个队列的优先级最高,第二个队列次之,其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同,在优先权愈高的队列中,为每个进程所规定的执行时间片就愈小。例如,第二个队列的时间片要比第一个队列的时间片长一倍,……,第i+1个队列的时间片要比第i个队列的时间片长一倍。

(2) 当一个新进程进入内存后,首先将它放入第一队列的末尾,按FCFS原则排队等待调度。当轮到该进程执行时,如它能在该时间片内完成,便可准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按FCFS原则等待调度执行;如果它在第二队列中运行一个时间片后仍未完成,再依次将它放入第三队列,……,如此下去,当一个长作业(进程)从第一队列依次降到第n队列后,在第n 队列便采取按时间片轮转的方式运行。

(3) 仅当第一队列空闲时,调度程序才调度第二队列中的进程运行;仅当第1~(i-1)队列均空时,才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时,又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列),则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在运行的进程放回到第i队列的末尾,把处理机分配给新到的高优先权进程。

Fork操作

fork()用于创建子进程,新的子进程将拷贝父进程的一切资源(包括文件描述符,变量等)。
fork()函数最重要的特性是:执行一次,返回两次,有三种返回情况。
若返回为负,则创建子进程失败;
返回为0,即返回的是子进程;
返回为正值,即返回的是父进程。
fork()返回的结果为创建子进程的pid,子进程的pid自然为0,他还没有子进程。

内存管理(块式、页式、段式、段页式).

内存管理有块式管理,页式管理,段式和段页式管理。现在常用段页式管理。

块式管理:把主存分为一大块、一大块的,当所需的程序片断不在主存时就分配一块主存空间,把程序片断load入主存,就算所需的程序片度只有几个字节也只能把这一块分配给它。这样会造成很大的浪费,平均浪费了50%的内存空间,但是易于管理。

页式管理:把主存分为一页一页的,每一页的空间要比一块一块的空间小很多,显然这种方法的空间利用率要比块式管理高很多。

段式管理:把主存分为一段一段的,每一段的空间又要比一页一页的空间小很多,这种方法在空间利用率上又比页式管理高很多,但是也有另外一个缺点。一个程序片断可能会被分为几十段,这样很多时间就会被浪费在计算每一段的物理地址上。

段页式管理:结合了段式管理和页式管理的优点。将程序分成若干段,每个段分成若干页。段页式管理每取一数据,要访问3次内存。

分页和分段有什么区别(内存管理)?

段式存储管理是一种符合用户视角的内存分配管理方案。在段式存储管理中,将程序的地址空间划分为若干段(segment),如代码段,数据段,堆栈段;这样每个进程有一个二维地址空间,相互独立,互不干扰。段式管理的优点是:没有内碎片(因为段大小可变,改变段大小来消除内碎片)。但段换入换出时,会产生外碎片(比如4k的段换5k的段,会产生1k的外碎片)

页式存储管理方案是一种用户视角内存与物理内存相分离的内存分配管理方案。在页式存储管理中,将程序的逻辑地址划分为固定大小的页(page),而物理内存划分为同样大小的帧,程序加载时,可以将任意一页放入内存中任意一个帧,这些帧不必连续,从而实现了离散分配。页式存储管理的优点是:没有外碎片(因为页的大小固定),但会产生内碎片(一个页可能填充不满)。

两者的不同点:

目的不同:分页是由于系统管理的需要而不是用户的需要,它是信息的物理单位;分段的目的是为了能更好地满足用户的需要,它是信息的逻辑单位,它含有一组其意义相对完整的信息;

大小不同:页的大小固定且由系统决定,而段的长度却不固定,由其所完成的功能决定;

地址空间不同: 段向用户提供二维地址空间;页向用户提供的是一维地址空间;

信息共享:段是信息的逻辑单位,便于存储保护和信息的共享,页的保护和共享受到限制;

内存碎片:页式存储管理的优点是没有外碎片(因为页的大小固定),但会产生内碎片(一个页可能填充不满);而段式管理的优点是没有内碎片(因为段大小可变,改变段大小来消除内碎片)。但段换入换出时,会产生外碎片(比如4k的段换5k的段,会产生1k的外碎片)。

页面置换算法

最佳置换算法OPT:只具有理论意义的算法,用来评价其他页面置换算法。置换策略是将当前页面中在未来最长时间内不会被访问的页置换出去。

先进先出置换算法FIFO:简单粗暴的一种置换算法,没有考虑页面访问频率信息。每次淘汰最早调入的页面。

最近最久未使用算法LRU:算法赋予每个页面一个访问字段,用来记录上次页面被访问到现在所经历的时间t,每次置换的时候把t值最大的页面置换出去(实现方面可以采用寄存器或者栈的方式实现)。

时钟算法clock(也被称为是最近未使用算法NRU):页面设置一个访问位,并将页面链接为一个环形队列,页面被访问的时候访问位设置为1。页面置换的时候,如果当前指针所指页面访问为为0,那么置换,否则将其置为0,循环直到遇到一个访问为位0的页面。

改进型Clock算法:在Clock算法的基础上添加一个修改位,替换时根究访问位和修改位综合判断。优先替换访问位和修改位都是0的页面,其次是访问位为0修改位为1的页面。

LFU最少使用算法LFU:设置寄存器记录页面被访问次数,每次置换的时候置换当前访问次数最少的。

操作系统中进程调度策略

先来先服务调度算法FCFS:队列实现,非抢占,先请求CPU的进程先分配到CPU,可以作为作业调度算法也可以作为进程调度算法;按作业或者进程到达的先后顺序依次调度,对于长作业比较有利;

最短作业优先调度算法SJF:作业调度算法,算法从就绪队列中选择估计时间最短的作业进行处理,直到得出结果或者无法继续执行,平均等待时间最短,但难以知道下一个CPU区间长度;缺点:不利于长作业;未考虑作业的重要性;运行时间是预估的,并不靠谱 ;

优先级调度算法(可以是抢占的,也可以是非抢占的):优先级越高越先分配到CPU,相同优先级先到先服务,存在的主要问题是:低优先级进程无穷等待CPU,会导致无穷阻塞或饥饿;

时间片轮转调度算法(可抢占的):按到达的先后对进程放入队列中,然后给队首进程分配CPU时间片,时间片用完之后计时器发出中断,暂停当前进程并将其放到队列尾部,循环 ;队列中没有进程被分配超过一个时间片的CPU时间,除非它是唯一可运行的进程。如果进程的CPU区间超过了一个时间片,那么该进程就被抢占并放回就绪队列。

高相应比算法HRN:响应比=(等待时间+要求服务时间)/要求服务时间;

多级队列调度算法:将就绪队列分成多个独立的队列,每个队列都有自己的调度算法,队列之间采用固定优先级抢占调度。其中,一个进程根据自身属性被永久地分配到一个队列中。

多级反馈队列调度算法:目前公认较好的调度算法;设置多个就绪队列并为每个队列设置不同的优先级,第一个队列优先级最高,其余依次递减。优先级越高的队列分配的时间片越短,进程到达之后按FCFS放入第一个队列,如果调度执行后没有完成,那么放到第二个队列尾部等待调度,如果第二次调度仍然没有完成,放入第三队列尾部…。只有当前一个队列为空的时候才会去调度下一个队列的进程。与多级队列调度算法相比,其允许进程在队列之间移动:若进程使用过多CPU时间,那么它会被转移到更低的优先级队列;在较低优先级队列等待时间过长的进程会被转移到更高优先级队列,以防止饥饿发生。

说一说进程同步有哪几种机制

原子操作、信号量机制、自旋锁管程、会合、分布式系统

虚拟内存

1).内存的发展历程

没有内存抽象(单进程,除去操作系统所用的内存之外,全部给用户程序使用) —> 有内存抽象(多进程,进程独立的地址空间,交换技术(内存大小不可能容纳下所有并发执行的进程)
)—> 连续内存分配(固定大小分区(多道程序的程度受限),可变分区(首次适应,最佳适应,最差适应),碎片) —> 不连续内存分配(分段,分页,段页式,虚拟内存)

2).虚拟内存

虚拟内存允许执行进程不必完全在内存中。虚拟内存的基本思想是:每个进程拥有独立的地址空间,这个空间被分为大小相等的多个块,称为页(Page),每个页都是一段连续的地址。这些页被映射到物理内存,但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时,由硬件立刻进行必要的映射;当程序引用到一部分不在物理内存中的地址空间时,由操作系统负责将缺失的部分装入物理内存并重新执行失败的命令。这样,对于进程而言,逻辑上似乎有很大的内存空间,实际上其中一部分对应物理内存上的一块(称为帧,通常页和帧大小相等),还有一些没加载在内存中的对应在硬盘上,如图所示。
注意,请求分页系统、请求分段系统和请求段页式系统都是针对虚拟内存的,通过请求实现内存与外存的信息置换。

由图可以看出,虚拟内存实际上可以比物理内存大。当访问虚拟内存时,会访问MMU(内存管理单元)去匹配对应的物理地址(比如图5的0,1,2)。如果虚拟内存的页并不存在于物理内存中(如图5的3,4),会产生缺页中断,从磁盘中取得缺的页放入内存,如果内存已满,还会根据某种算法将磁盘中的页换出。

3). 虚拟内存的应用与优点

虚拟内存很适合在多道程序设计系统中使用,许多程序的片段同时保存在内存中。当一个程序等待它的一部分读入内存时,可以把CPU交给另一个进程使用。虚拟内存的使用可以带来以下好处:

在内存中可以保留多个进程,系统并发度提高

解除了用户与内存之间的紧密约束,进程可以比内存的全部空间还大