操作系统面试题

1、操作系统有哪些调度方法?

1、先来先服务调度算法
2、短作业(进程)优先调度算法
3、高优先权优先调度算法
4、高响应比优先调度算法
5、时间片轮转法
6、多级反馈队列调度算法

2、请你说一说进程和线程区别

1、一个线程只能属于一个进程,而一个进程可以有多个线程,但至少有一个线程。线程依赖于进程而存在。
2、进程在执行过程中拥有独立的内存单元,而多个线程共享进程的内存。(资源分配给进程,同一进程的所有线程共享该进程的所有资源。同一进程中的多个线程共享代码段(代码和常量),数据段(全局变量和静态变量),扩展段(堆存储)。但是每个线程拥有自己的栈段,栈段又叫运行时段,用来存放所有局部变量和临时变量。)
3、进程是资源分配的最小单位,线程是CPU调度的最小单位。
4、系统开销: 由于在创建或撤消进程时,系统都要为之分配或回收资源,如内存空间、I/o设备等。因此,操作系统所付出的开销将显著地大于在创建或撤消线程时的开销。类似地,在进行进程切换时,涉及到整个当前进程CPU环境的保存以及新被调度运行的进程的CPU环境的设置。而线程切换只须保存和设置少量寄存器的内容,并不涉及存储器管理方面的操作。可见,进程切换的开销也远大于线程切换的开销。
5、通信:由于同一进程中的多个线程具有相同的地址空间,致使它们之间的同步和通信的实现,也变得比较容易。进程间通信IPC,线程间可以直接读写进程数据段(如全局变量)来进行通信——需要进程同步和互斥手段的辅助,以保证数据的一致性。在有的系统中,线程的切换、同步和通信都无须操作系统内核的干预 。
6、进程编程调试简单可靠性高,但是创建销毁开销大;线程正相反,开销小,切换速度快,但是编程调试相对复杂。
7、进程间不会相互影响 ;线程一个线程挂掉将导致整个进程挂掉。
8、进程适应于多核、多机分布;线程适用于多核。

3、进程间通信

网络,共享内存,消息队列,管道,信号量
管道(pipe)及命名管道(named pipe):管道可用于具有亲缘关系的父子进程间的通信,有名管道除了具有管道所具有的功能外,它还允许无亲缘关系进程间的通信;

信号(signal):信号是一种比较复杂的通信方式,用于通知接收进程某个事件已经发生;

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

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

信号量:主要作为进程之间及同一种进程的不同线程之间得同步和互斥手段;

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

4、线程间同步

互斥锁,信号量,条件变量

    使用临界区对象。拥有临界区对象的线程可以访问被保护起来的资源或代码段,其他线程若想访问,则被挂起,直到拥有临界区对象的线程放弃临界区对象为止【只用于同一进程】

信号量

是用来解决进程/线程之间的同步和互斥问题的一种通信机制,是用来保证两个或多个关键代码不被并发调用。

信号量(Saphore)由一个值和一个指针组成,指针指向等待该信号量的进程。信号量的值表示相应资源的使用情况。信号量S>=0时,S表示可用资源的数量。执行一次P操作意味着请求分配一个资源,因此S的值减1;当S<0时,表示已经没有可用资源,S的绝对值表示当前等待该资源的进程数。请求者必须等待其他进程释放该类资源,才能继续运行。而执行一个V操作意味着释放一个资源,因此S的值加1;若S<0,表示有某些进程正在等待该资源,因此要唤醒一个等待状态的进程,使之运行下去。

信号量是选择睡眠的方式来对共享工作停止访问的。

也就是说信号量通过PV操作同步解决了进程/线程对临界资源利用的冲突问题;

互斥锁

互斥锁同样也是对线程间(不能对进程)同步和互斥的一种另一种机制。

互斥锁更多的是强调对共享资源的锁定作用,当一个线程占用了当前共享资源,使用互斥锁将其lock住之后,其他线程就无法访问,必须等到unlock之后,其他线程才能利用共享资源里面的内容;

互斥锁是选择睡眠的方式来对共享工作停止访问的。

也就是说互斥锁通过对共享资源的锁定和互斥解决利用资源冲突问题;

自旋锁

是为实现保护共享资源而提出一种锁机制。其实,自旋锁与互斥锁比较类似,它们都是为了解决对某项资源的互斥使用。无论是互斥锁,还是自旋锁,在任何时刻,最多只能有一个保持者,也就说,在任何时刻最多只能有一个执行单元获得锁。但是两者在调度机制上略有不同。对于互斥锁,如果资源已经被占用,资源申请者只能进入睡眠状态。但是自旋锁不会引起调用者睡眠,如果自旋锁已经被别的执行单元保持,调用者就一直循环在那里看是否该自旋锁的保持者已经释放了锁,"自旋"一词就是因此而得名。

5、死锁

所谓死锁,是指多个进程在运行过程中因争夺资源而造成的一种僵局,当进程处于这种僵持状态时,若无外力作用,它们都将无法再向前推进。

产生死锁的原因?
可归结为如下两点:

①竞争资源

系统中的资源可以分为两类:
可剥夺资源,是指某进程在获得这类资源后,该资源可以再被其他进程或系统剥夺,CPU和主存均属于可剥夺性资源;
另一类资源是不可剥夺资源,当系统把这类资源分配给某进程后,再不能强行收回,只能在进程用完后自行释放,如磁带机、打印机等。
产生死锁中的竞争资源之一指的是竞争不可剥夺资源(例如:系统中只有一台打印机,可供进程P1使用,假定P1已占用了打印机,若P2继续要求打印机打印将阻塞)
产生死锁中的竞争资源另外一种资源指的是竞争临时资源(临时资源包括硬件中断、信号、消息、缓冲区内的消息等),通常消息通信顺序进行不当,则会产生死锁
② 进程间推进顺序非法

若P1保持了资源R1,P2保持了资源R2,系统处于不安全状态,因为这两个进程再向前推进,便可能发生死锁
例如,当P1运行到P1:Request(R2)时,将因R2已被P2占用而阻塞;当P2运行到P2:Request(R1)时,也将因R1已被P1占用而阻塞,于是发生进程死锁
死锁产生的4个必要条件?

①互斥条件:进程要求对所分配的资源进行排它性控制,即在一段时间内某资源仅为一进程所占用。

②请求和保持条件:当进程因请求资源而阻塞时,对已获得的资源保持不放。

③不剥夺条件:进程已获得的资源在未使用完之前,不能剥夺,只能在使用完时由自己释放。

④环路等待条件:在发生死锁时,必然存在一个进程--资源的环形链。

解决死锁的基本方法

①预防死锁

②避免死锁
银行家算法【在动态分配资源的过程中,银行家算法防止系统进入不安全状态,从而避免死锁】
银行家算法:

    当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。

    当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源。若没超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若满足则按当前的申请量分配资源,否则也要推迟分配。

安全序列:是指系统能按某种进程推进顺序(P1, P2, P3, …, Pn),为每个进程 Pi 分配其所需要的资源,直至满足每个进程对资源的最大需求,使每个进程都可以顺序地完成。这种推进顺序就叫安全序列【银行家算法的核心就是找到一个安全序列】。
系统安全状态 :如果系统能找到一个安全序列,就称系统处于安全状态,否则,就称系统处于不安全状态
③检测死锁
根据死锁定理:S 为死锁的条件是当且仅当 S 状态的资源分配图是不可完全简化的,该条件称为死锁定理。
④解除死锁
1、资源剥夺:挂起某些死锁进程,并抢占它的资源,将这些资源分配给其他死锁进程。(但应该防止被挂起的进程长时间得不到资源);

2、撤销进程:强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。(撤销的原则可以按进程优先级和撤销进程代价的高低进行);

3、进程回退:让一个或多个进程回退到足以避免死锁的地步。【进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息,设置还原点。】

6、进程有哪几种状态?

①新建:进程开始创建状态
②运行:该进程的指令代码正在执行
③等待:进程正在等待某个时间,比如I/O完成或收到信号
④就绪:进程等待分配处理器,万事俱备,只欠CPU
⑤终止:进程已经执行完成

7、分页和分段有什么区别(内存管理)?[/scode

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

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

两者的不同点:

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

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

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

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

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

1).内存的发展历程

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

2).虚拟内存

  虚拟内存允许执行进程不必完全在内存中。虚拟内存的基本思想是:每个进程拥有独立的地址空间,这个空间被分为大小相等的多个块,称为页(Page),每个页都是一段连续的地址。这些页被映射到物理内存,但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时,由硬件立刻进行必要的映射;当程序引用到一部分不在物理内存中的地址空间时,由操作系统负责将缺失的部分装入物理内存并重新执行失败的命令。这样,对于进程而言,逻辑上似乎有很大的内存空间,实际上其中一部分对应物理内存上的一块(称为帧,通常页和帧大小相等),还有一些没加载在内存中的对应在硬盘上,如图5所示。
注意,请求分页系统、请求分段系统和请求段页式系统都是针对虚拟内存的,通过请求实现内存与外存的信息置换。
虚拟内存实际上可以比物理内存大。当访问虚拟内存时,会访问MMU(内存管理单元)去匹配对应的物理地址。如果虚拟内存的页并不存在于物理内存中,会产生缺页中断,从磁盘中取得缺的页放入内存,如果内存已满,还会根据某种算法将磁盘中的页换出。
3). 页面置换算法

FIFO先进先出算法:在操作系统中经常被用到,比如作业调度(主要实现简单,很容易想到);

LRU(Least recently use)最近最少使用算法:根据使用时间到现在的长短来判断;

LFU(Least frequently use)最少使用次数算法:根据使用次数来判断;

OPT(Optimal replacement)最优置换算法:理论的最优,理论;就是要保证置换出去的是不再被使用的页,或者是在实际内存中最晚使用的算法。

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

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

在内存中可以保留多个进程,系统并发度提高
虚拟内存技术:允许将一个作业分多次调入内存。可以用分页式、分段式、段页式存储管理来实现。

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

9、局部性原理

(1). 时间上的局部性:最近被访问的页在不久的将来还会被访问;

(2). 空间上的局部性:内存中被访问的页周围的页也很可能被访问。

生产者消费者模型、哲学家就餐问题

Last modification:February 9th, 2020 at 12:55 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment