操作系统 面试题整理 1

进程和线程以及它们的区别

进程是对运行时程序的封装,是系统进行资源调度和分配的的基本单位,实现了操作系统的并发;进程的生命周期由内核管理

线程是进程的子任务,是CPU调度和分派的基本单位,用于保证程序的 实时性,实现进程内部的并发;线程分内核线程和用户线程,
应用进程利用线程库,内核线程由内核管理

一个程序至少有一个进程,一个进程至少有一个线程,线程依赖于进程而存在;

进程在执行过程中拥有独立的内存单元,而多个线程共享进程的内存。
在这里插入图片描述

什么是死锁?死锁产生的条件?

1). 死锁的概念  在两个或者多个并发进程中,如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源,在未改变这种状态之前都不能向前推进,称这一组进程产生了死锁。通俗的讲,就是两个或多个进程无限期的阻塞、相互等待的一种状态。
2)
互斥:至少有一个资源必须属于非共享模式,即一次只能被一个进程使用;若其他申请使用该资源,那么申请进程必须等到该资源被释放为止;

占有并等待:一个进程必须占有至少一个资源,并等待另一个资源,而该资源为其他进程所占有;

非抢占:进程不能被抢占,即资源只能被进程在完成任务后自愿释放

循环等待:若干进程之间形成一种头尾相接的环形等待资源关系

死锁的处理基本策略和常用方法

解决死锁的基本方法主要有 预防死锁、避免死锁、检测死锁、解除死锁 、鸵鸟策略 等。

(1). 死锁预防
  
  死锁预防的基本思想是 只要确保死锁发生的四个必要条件中至少有一个不成立,就能预防死锁的发生,具体方法包括:

打破互斥条件:允许进程同时访问某些资源。但是,有些资源是不能被多个进程所共享的,这是由资源本身属性所决定的,因此,这种办法通常并无实用价值。

打破占有并等待条件:可以实行资源预先分配策略(进程在运行前一次性向系统申请它所需要的全部资源,若所需全部资源得不到满足,则不分配任何资源,此进程暂不运行;只有当系统能满足当前进程所需的全部资源时,才一次性将所申请资源全部分配给该线程)或者只允许进程在没有占用资源时才可以申请资源(一个进程可申请一些资源并使用它们,但是在当前进程申请更多资源之前,它必须全部释放当前所占有的资源)。但是这种策略也存在一些缺点:在很多情况下,无法预知一个进程执行前所需的全部资源,因为进程是动态执行的,不可预知的;同时,会降低资源利用率,导致降低了进程的并发性。

打破非抢占条件:允许进程强行从占有者哪里夺取某些资源。也就是说,但一个进程占有了一部分资源,在其申请新的资源且得不到满足时,它必须释放所有占有的资源以便让其它线程使用。这种预防死锁的方式实现起来困难,会降低系统性能。

打破循环等待条件:实行资源有序分配策略。对所有资源排序编号,所有进程对资源的请求必须严格按资源序号递增的顺序提出,即只有占用了小号资源才能申请大号资源,这样就不回产生环路,预防死锁的发生。

(2). 死锁避免的基本思想
  
  死锁避免的基本思想是动态地检测资源分配状态,以确保循环等待条件不成立,从而确保系统处于安全状态。所谓安全状态是指:如果系统能按某个顺序为每个进程分配资源(不超过其最大值),那么系统状态是安全的,换句话说就是,如果存在一个安全序列,那么系统处于安全状态。资源分配图算法和银行家算法是两种经典的死锁避免的算法,其可以确保系统始终处于安全状态。其中,资源分配图算法应用场景为每种资源类型只有一个实例(申请边,分配边,需求边,不形成环才允许分配),而银行家算法应用于每种资源类型可以有多个实例的场景。

(3). 死锁解除

死锁解除的常用两种方法为进程终止和资源抢占。所谓进程终止是指简单地终止一个或多个进程以打破循环等待,包括两种方式:终止所有死锁进程和一次只终止一个进程直到取消死锁循环为止;所谓资源抢占是指从一个或多个死锁进程那里抢占一个或多个资源,此时必须考虑三个问题:

(I). 选择一个牺牲品
  (II). 回滚:回滚到安全状态
  (III). 饥饿(在代价因素中加上回滚次数,回滚的越多则越不可能继续被作为牺牲品,避免一个进程总是被回滚)

进程的几种状态

创建状态(new) :进程正在被创建,尚未到就绪状态。就绪状态(ready) :进程已处于准备运行状态,即进程获得了除了处理器之外的一切所需资源,一旦得到处理器资源(处理器分配的时间片)即可运行。运行状态(running) :进程正在处理器上上运行(单核 CPU 下任意时刻只有一个进程处于运行状态)。阻塞状态(waiting) :又称为等待状态,进程正在等待某一事件而暂停运行如等待某资源为可用或等待 IO 操作完成。即使处理器空闲,该进程也不能运行。结束状态(terminated) :进程正在从系统中消失。可能是进程正常结束或其他原因中断退出运行。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MWSkYwEV-1631073947376)(en-resource://database/2227:1)]

线程的几种状态

在这里插入图片描述

新建
就绪
运行
阻塞
死亡

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

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

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

段页式管理机制

主存先分成若干段,每个段又分成若干页

快表和多级页表 (分页式管理)

虚拟地址到物理地址的转换要快。
解决虚拟地址空间大,页表也会很大的问题。

快表

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

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

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

多级页表

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

总结为了提高内存的空间性能,提出了多级页表的概念;但是提到空间性能是以浪费时间性能为基础的,因此为了补充损失的时间性能,提出了快表(即 TLB)的概念。 不论是快表还是多级页表实际上都利用到了程序的局部性原理,

银行家算法

在这里插入图片描述

首先,进入算法第一步,初始化。
那么Work = Available = [3 3 2]首先看P0:
P0的Need为[7 4 3],Available不能满足,于是跳过去P1的Need为[1 2 2]可以满足,我们令Work = Allocation[P1] + Work
此时Work = [5 3 2]再看P2,P2的Need为[6 0 0],那么现有资源不满足。跳过去。看P3,那么看P3,Work可以满足。那么令Work = Allocation[P3] + Work,此时Work = [7 4 3]再看P4,Work可以满足。令Work = Allocation[P4] + Work ,此时Work = [7 4 5]到此第一轮循环完毕,由于找到了可用进程,那么进入第二轮循环。看P0,Work此时可以满足。令Work = Allocation[P0] + Work ,此时Work = [7 5 5]再看P2,此时Work可以满足P2。令Work = Allocation[P2] + Work , 此时Work = [10 5 7]至此,算法运行完毕。找到安全序列<P1,P3,P4,P0,P2>,证明此时没有死锁危险。(安全序列未必唯一)

进程同步 互斥 异步

互斥:指某一个资源同时只允许一个访问者对其进行访问,具有唯一性和排它性。
同步:是指在互斥的基础上,通过算法机制实现访问者对资源的有序访问。

同步:体现的是一种协作性。互斥:体现的是排它性。
异步 一个程序调用需要花费很长时间,并不希望程序等待,就需需要异步。

并发:同一时刻多个线程在访问同一个资源,多个线程对一个点
例子:春运抢票 电商秒杀…
并行:多项工作一起执行,之后再汇总
例子:泡方便面,电水壶烧水,一边撕调料倒入桶中

什么是虚拟内存?

在这里插入图片描述

1).内存的发展历程

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

2).虚拟内存

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

注意,请求分页系统、请求分段系统和请求段页式系统都是针对虚拟内存的,通过请求实现内存与外存的信息置换。

CPU 寻址了解吗?为什么需要虚拟地址空间?

不理解

进程同步有哪几种机制:

1.信号量机制
一个信号量只能置一次初值,以后只能对之进行p操作或v操作。 由此也可以看到,信号量机制必须有公共内存,不能用于分布式操作系统,这是它最大的弱点。

2.自旋锁

旋锁是为了保护共享资源提出的一种锁机制。 调用者申请的资源如果被占用,即自旋锁被已经被别的执行单元保持,则调用者一直循环在那里看是否该自旋锁的保持着已经释放了锁,自旋锁是一种比较低级的保护数据结构和代码片段的原始方式,可能会引起以下两个问题;
(1)死锁
(2)过多地占用CPU资源

3.管程
信号量机制功能强大,但使用时对信号量的操作分散,而且难以控制,读写和维护都很困难。因此后来又提出了一种集中式同步进程——管程。其基本思想是将共享变量和对它们的操作集中在一个模块中,操作系统或并发程序就由这样的模块构成。这样模块之间联系清晰,便于维护和修改,易于保证正确性。

4.会合

进程直接进行相互作用

5.分布式系统

由于在分布式操作系统中没有公共内存,因此参数全为值参,而且不可为指针。

操作系统中进程调度策略有哪几种?

FCFS(先来先服务,队列实现,非抢占的):先请求CPU的进程先分配到CPU

SJF(最短作业优先调度算法):平均等待时间最短,但难以知道下一个CPU区间长度

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

时间片轮转调度算法(可抢占的):队列中没有进程被分配超过一个时间片的CPU时间,除非它是唯一可运行的进程。如果进程的CPU区间超过了一个时间片,那么该进程就被抢占并放回就绪队列。

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

多级反馈队列调度算法:与多级队列调度算法相比,其允许进程在队列之间移动:若进程使用过多CPU时间,那么它会被转移到更低的优先级队列;在较低优先级队列等待时间过长的进程会被转移到更高优先级队列,以防止饥饿发生。

进程间的通信的几种方式

管道/匿名管道(Pipes) :用于具有亲缘关系的父子进程间或者兄弟进程之间的通信。有名管道(Names Pipes) : 匿名管道由于没有名字,只能用于亲缘关系的进程间通信。为了克服这个缺点,提出了有名管道。有名管道严格遵循先进先出(first in first out)。有名管道以磁盘文件的方式存在,可以实现本机任意两个进程通信。信号(Signal) :信号是一种比较复杂的通信方式,用于通知接收进程某个事件已经发生;消息队列(Message Queuing) :消息队列是消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识。管道和消息队列的通信数据都是先进先出的原则。与管道(无名管道:只存在于内存中的文件;命名管道:存在于实际的磁盘介质或者文件系统)不同的是消息队列存放在内核中,只有在内核重启(即,操作系统重启)或者显示地删除一个消息队列时,该消息队列才会被真正的删除。消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取.比 FIFO 更有优势。消息队列克服了信号承载信息量少,管道只能承载无格式字 节流以及缓冲区大小受限等缺。信号量(Semaphores) :信号量是一个计数器,用于多进程对共享数据的访问,信号量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。共享内存(Shared memory) :使得多个进程可以访问同一块内存空间,不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作,如互斥锁和信号量等。可以说这是最有用的进程间通信方式。套接字(Sockets) : 此方法主要用于在客户端和服务器之间通过网络进行通信。套接字是支持 TCP/IP 的网络通信的基本操作单元,可以看做是不同主机之间的进程进行双向通信的端点,简单的说就是通信的两方的一种约定,用套接字中的相关函数来完成通信过程。

3、线程同步的方式

互斥量 Synchronized/Lock:采用互斥对象机制,只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个,所以可以保证公共资源不会被多个线程同时访问

信号量 Semphare:它允许同一时刻多个线程访问同一资源,但是需要控制同一时刻访问此资源的最大线程数量

事件(信号),Wait/Notify:通过通知操作的方式来保持多线程同步,还可以方便的实现多线程优先级的比较操作

进程调度几种算法

先到先服务(FCFS)调度算法 : 从就绪队列中选择一个最先进入该队列的进程为之分配资源,使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。

短作业优先(SJF)的调度算法 : 从就绪队列中选出一个估计运行时间最短的进程为之分配资源,使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。时间片轮转调度算法 :

时间片轮转调度是一种最古老,最简单,最公平且使用最广的算法,又称 RR(Round robin)调度。每个进程被分配一个时间段,称作它的时间片,即该进程允许运行的时间。多级反馈队列调度算法 :前面介绍的几种进程调度的算法都有一定的局限性。如短进程优先的调度算法,仅照顾了短进程而忽略了长进程 。

多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业(进程)迅速完成。,因而它是目前被公认的一种较好的进程调度算法,UNIX 操作系统采取的便是这种调度算法。

优先级调度 : 为每个流程分配优先级,首先执行具有最高优先级的进程,依此类推。具有相同优先级的进程以 FCFS 方式执行。可以根据内存要求,时间要求或任何其他资源要求来确定优先级。

文件系统

文件怎么写入磁盘

热门文章

暂无图片
编程学习 ·

C语言二分查找详解

二分查找是一种知名度很高的查找算法&#xff0c;在对有序数列进行查找时效率远高于传统的顺序查找。 下面这张动图对比了二者的效率差距。 二分查找的基本思想就是通过把目标数和当前数列的中间数进行比较&#xff0c;从而确定目标数是在中间数的左边还是右边&#xff0c;将查…
暂无图片
编程学习 ·

GMX 命令分类列表

建模和计算操作命令&#xff1a; 1.1 . 创建拓扑与坐标文件 gmx editconf - 编辑模拟盒子以及写入子组(subgroups) gmx protonate - 结构质子化 gmx x2top - 根据坐标生成原始拓扑文件 gmx solvate - 体系溶剂化 gmx insert-molecules - 将分子插入已有空位 gmx genconf - 增加…
暂无图片
编程学习 ·

一文高效回顾研究生课程《数值分析》重点

数值分析这门课的本质就是用离散的已知点去估计整体&#xff0c;就是由黑盒子产生的结果去估计这个黑盒子。在数学里这个黑盒子就是一个函数嘛&#xff0c;这门课会介绍许多方法去利用离散点最大化地逼近这个函数&#xff0c;甚至它的导数、积分&#xff0c;甚至微分方程的解。…
暂无图片
编程学习 ·

在职阿里5年,一个28岁女软测工程师的心声

简单的先说一下&#xff0c;坐标杭州&#xff0c;14届本科毕业&#xff0c;算上年前在阿里巴巴的面试&#xff0c;一共有面试了有6家公司&#xff08;因为不想请假&#xff0c;因此只是每个晚上去其他公司面试&#xff0c;所以面试的公司比较少&#xff09; ​ 编辑切换为居中…
暂无图片
编程学习 ·

字符串左旋c语言

目录 题目&#xff1a; 解题思路&#xff1a; 第一步&#xff1a; 第二步&#xff1a; 第三步&#xff1a; 总代码&#xff1a; 题目&#xff1a; 实现一个函数&#xff0c;可以左旋字符串中的k个字符。 例如&#xff1a; ABCD左旋一个字符得到BCDA ABCD左旋两个字符…
暂无图片
编程学习 ·

设计模式--观察者模式笔记

模式的定义与特点 观察者&#xff08;Observer&#xff09;模式的定义&#xff1a;指多个对象间存在一对多的依赖关系&#xff0c;当一个对象的状态发生改变时&#xff0c;所有依赖于它的对象都得到通知并被自动更新。这种模式有时又称作发布-订阅模式、模型-视图模式&#xf…
暂无图片
编程学习 ·

睡觉突然身体动不了,什么是睡眠痽痪症

很多朋友可能有这样的体验&#xff0c;睡觉过程中突然意识清醒&#xff0c;身体却动弹不了。这时候感觉非常恐怖&#xff0c;希望旁边有一个人推自己一下。阳光以前也经常会碰到这样的情况&#xff0c;一年有一百多次&#xff0c;那时候很害怕晚上到来&#xff0c;睡觉了就会出…
暂无图片
编程学习 ·

深入理解C++智能指针——浅析MSVC源码

文章目录unique_ptrshared_ptr 与 weak_ptrstd::bad_weak_ptr 异常std::enable_shared_from_thisunique_ptr unique_ptr 是一个只移型别&#xff08;move-only type&#xff0c;只移型别还有std::mutex等&#xff09;。 结合一下工厂模式&#xff0c;看看其基本用法&#xff…
暂无图片
编程学习 ·

@TableField(exist = false)

TableField(exist false) //申明此字段不在数据库存在&#xff0c;但代码中需要用到它&#xff0c;通知Mybatis-plus在做写库操作是忽略它。,.
暂无图片
编程学习 ·

Java Web day15

第十二章文件上传和下载 一、如何实现文件上传 要实现Web开发中的文件上传功能&#xff0c;通常需要完成两步操作&#xff1a;一.是在Web页面中添加上传输入项&#xff1b;二是在Servlet中读取上传文件的数据&#xff0c;并保存到本地硬盘中。 需要使用一个Apache组织提供一个…
暂无图片
编程学习 ·

【51nod 2478】【单调栈】【前缀和】小b接水

小b接水题目解题思路Code51nod 2478 小b接水 题目 输入样例 12 0 1 0 2 1 0 1 3 2 1 2 1输出样例 6解题思路 可以发现最后能拦住水的都是向两边递减高度&#xff08;&#xff1f;&#xff09; 不管两个高积木之间的的积木是怎样乱七八糟的高度&#xff0c;最后能用来装水的…
暂无图片
编程学习 ·

花了大半天写了一个UVC扩展单元调试工具

基于DIRECTSHOW 实现的&#xff0c;用的是MFC VS2019. 详见&#xff1a;http://www.usbzh.com/article/detail-761.html 获取方法 加QQ群:952873936&#xff0c;然后在群文件\USB调试工具&测试软件\UVCXU-V1.0(UVC扩展单元调试工具-USB中文网官方版).exe USB中文网 USB中文…
暂无图片
编程学习 ·

贪心(一):区间问题、Huffman树

区间问题 例题一&#xff1a;区间选点 给定 N 个闭区间 [ai,bi]请你在数轴上选择尽量少的点&#xff0c;使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。 位于区间端点上的点也算作区间内。 输入格式 第一行包含整数 N&#xff0c;表示区间数。 接下来 …
暂无图片
编程学习 ·

C语言练习实例——费氏数列

目录 题目 解法 输出结果 题目 Fibonacci为1200年代的欧洲数学家&#xff0c;在他的着作中曾经提到&#xff1a;「若有一只免子每个月生一只小免子&#xff0c;一个月后小免子也开始生产。起初只有一只免子&#xff0c;一个月后就有两只免子&#xff0c;二个月后有三只免子…
暂无图片
编程学习 ·

Android开发(2): Android 资源

个人笔记整理 Android 资源 Android中的资源&#xff0c;一般分为两类&#xff1a; 系统内置资源&#xff1a;Android SDK中所提供的已经定义好的资源&#xff0c;用户可以直接拿来使用。 用户自定义资源&#xff1a;用户自己定义或引入的&#xff0c;只适用于当前应用的资源…
暂无图片
编程学习 ·

零基础如何在短时间内拿到算法offer

​算法工程师是利用算法处理事物的职业 算法&#xff08;Algorithm&#xff09;是一系列解决问题的清晰指令&#xff0c;也就是说&#xff0c;能够对一定规范的输入&#xff0c;在有限时间内获得所要求的输出。 如果一个算法有缺陷&#xff0c;或不适合于某个问题&#xff0c;执…
暂无图片
编程学习 ·

人工智能:知识图谱实战总结

人工智能python&#xff0c;NLP&#xff0c;知识图谱&#xff0c;机器学习&#xff0c;深度学习人工智能&#xff1a;知识图谱实战前言一、实体建模工具Protegepython&#xff0c;NLP&#xff0c;知识图谱&#xff0c;机器学习&#xff0c;深度学习 人工智能&#xff1a;知识图…
暂无图片
编程学习 ·

【无标题】

这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注…