大家好,我是阿秀。
C++ 的八股文终于搞完了,前四篇文章字数分别是:32156、37814、31114、24098 个字,加起来一共 125,182个字,12W 字的八股文….如果还有没看过的,可以点击下面的链接去看看了。
《逆袭进大厂》
本期是操作系统开胃菜,既然是开胃菜那字数少一点好了哈哈,就先来21 道题,16213 个字好了。
还有本来想等到《逆袭进大厂》系列出完之后再放出 PDF 的,可很多人让我先出个第一版先看着…..
一开始我是拒绝的,可真的太多人跟我说了,考虑到最近金三银四以及春招找工作期间很多人都需要这份资料,emm…
没办法,先出第一期好了,文末有前四篇文章的汇总 PDF 下载方式。
现已将该八股文总结开源到个人 github 仓库上:
https://github.com/forthespada/InterviewGuide
你也可以点击文末左侧的『阅读原文』直达仓库地址,欢迎各位 star、fork,后期也会收录Java、Python、Golang等方面的面试常见八股文,同学们可以分享给你身边有需要的小伙伴,嘿嘿。
以下是本期目录,看看你会多少。
闲话少叙,开车开车!
1、进程是资源调度的基本单位,运行一个可执行程序会创建一个或多个进程,进程就是运行起来的可执行程序
2、线程是程序执行的基本单位,是轻量级的进程。每个进程中都有唯一的主线程,且只能有一个,主线程和进程是相互依存的关系,主线程结束进程也会结束。多提一句:协程是用户态的轻量级线程,线程内部调度的基本单位
1、线程启动速度快,轻量级
2、线程的系统开销小
3、线程使用有一定难度,需要处理数据一致性问题
4、同一线程共享的有堆、全局变量、静态变量、指针,引用、文件等,而独自占有栈
理论上,一个进程可用虚拟空间是2G,默认情况下,线程的栈的大小是1MB,所以理论上最多只能创建2048个线程。如果要创建多于2048的话,必须修改编译器的设置。
因此,一个进程可以创建的线程数由可用虚拟空间和线程的栈的大小共同决定,只要虚拟空间足够,那么新线程的建立就会成功。如果需要创建超过2K以上的线程,减小你线程栈的大小就可以实现了,虽然在一般情况下,你不需要那么多的线程。过多的线程将会导致大量的时间浪费在线程切换上,给程序运行效率带来负面影响。
《一个进程到底能创建多少线程》:https://www.cnblogs.com/Leo_wl/p/5969621.html
外中断是指由 CPU 执行指令以外的事件引起,如 I/O 完成中断,表示设备输入/输出处理已经完成,处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。
而异常时由 CPU 执行指令的内部事件引起,如非法操作码、地址越界、算术溢出等。
对于进程和线程的理解和把握可以说基本奠定了对系统的认知和把控能力。其核心意义绝不仅仅是“线程是调度的基本单位,进程是资源分配的基本单位”这么简单。
我们这里讨论的是用户态的多线程模型,同一个进程内部有多个线程,所有的线程共享同一个进程的内存空间,进程中定义的全局变量会被所有的线程共享,比如有全局变量int i = 10,这一进程中所有并发运行的线程都可以读取和修改这个i的值,而多个线程被CPU调度的顺序又是不可控的,所以对临界资源的访问尤其需要注意安全。
我们必须知道,做一次简单的i = i + 1在计算机中并不是原子操作,涉及内存取数,计算和写入内存几个环节,而线程的切换有可能发生在上述任何一个环节中间,所以不同的操作顺序很有可能带来意想不到的结果。
但是,虽然线程在安全性方面会引入许多新挑战,但是线程带来的好处也是有目共睹的。首先,原先顺序执行的程序(暂时不考虑多进程)可以被拆分成几个独立的逻辑流,这些逻辑流可以独立完成一些任务(最好这些任务是不相关的)。
比如 QQ 可以一个线程处理聊天一个线程处理上传文件,两个线程互不干涉,在用户看来是同步在执行两个任务,试想如果线性完成这个任务的话,在数据传输完成之前用户聊天被一直阻塞会是多么尴尬的情况。
对于线程,我认为弄清以下两点非常重要:
另外,我们通常只会去说同一进程的多个线程共享进程的资源,但是每个线程特有的部分却很少提及,除了标识线程的tid,每个线程还有自己独立的栈空间,线程彼此之间是无法访问其他线程栈上内容的。
而作为处理机调度的最小单位,线程调度只需要保存线程栈、寄存器数据和PC即可,相比进程切换开销要小很多。
线程相关接口不少,主要需要了解各个参数意义和返回值意义。
每一个进程是资源分配的基本单位。
进程结构由以下几个部分组成:代码段、堆栈段、数据段。代码段是静态的二进制代码,多个程序可以共享。
实际上在父进程创建子进程之后,父、子进程除了pid外,几乎所有的部分几乎一样。
父、子进程共享全部数据,但并不是说他们就是对同一块数据进行操作,子进程在读写数据时会通过写时复制机制将公共的数据重新拷贝一份,之后在拷贝出的数据上进行操作。
如果子进程想要运行自己的代码段,还可以通过调用execv()函数重新加载新的代码段,之后就和父进程独立开了。
我们在shell中执行程序就是通过shell进程先fork()一个子进程再通过execv()重新加载新的代码段的过程。
1、 先来先服务 first-come first-serverd(FCFS)
非抢占式的调度算法,按照请求的顺序进行调度。
有利于长作业,但不利于短作业,因为短作业必须一直等待前面的长作业执行完毕才能执行,而长作业又需要执行很长时间,造成了短作业等待时间过长。
2、 短作业优先 shortest job first(SJF)
非抢占式的调度算法,按估计运行时间最短的顺序进行调度。
长作业有可能会饿死,处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来,那么长作业永远得不到调度。
3、最短剩余时间优先 shortest remaining time next(SRTN)
最短作业优先的抢占式版本,按剩余运行时间的顺序进行调度。当一个新的作业到达时,其整个运行时间与当前进程的剩余时间作比较。
如果新的进程需要的时间更少,则挂起当前进程,运行新的进程。否则新的进程等待。
4、时间片轮转
将所有就绪进程按 FCFS 的原则排成一个队列,每次调度时,把 CPU 时间分配给队首进程,该进程可以执行一个时间片。
当时间片用完时,由计时器发出时钟中断,调度程序便停止该进程的执行,并将它送往就绪队列的末尾,同时继续把 CPU 时间分配给队首的进程。
时间片轮转算法的效率和时间片的大小有很大关系:
5、优先级调度
为每个进程分配一个优先级,按优先级进行调度。
为了防止低优先级的进程永远等不到调度,可以随着时间的推移增加等待进程的优先级。
6、多级反馈队列
一个进程需要执行 100 个时间片,如果采用时间片轮转调度算法,那么需要交换 100 次。
多级队列是为这种需要连续执行多个时间片的进程考虑,它设置了多个队列,每个队列时间片大小都不同,例如 1,2,4,8,..。进程在第一个队列没执行完,就会被移到下一个队列。
这种方式下,之前的进程只需要交换 7 次。每个队列优先权也不同,最上面的优先权最高。因此只有上一个队列没有进程在排队,才能调度当前队列上的进程。
可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。
①CPU给出逻辑地址,由某个硬件算得页号、页内偏移量,将页号与快表中的所有页号进行比较。②如果找到匹配的页号,说明要访问的页表项在快表中有副本,则直接从中取出该页对应的内存块号,再将内存块号与页内偏移量拼接形成物理地址,最后,访问该物理地址对应的内存单元。因此,若快表命中,则访问某个逻辑地址仅需一次访存即可。 ③如果没有找到匹配的页号,则需要访问内存中的页表,找到对应页表项,得到页面存放的内存块号,再将内存块号与页内偏移量拼接形成物理地址,最后,访问该物理地址对应的内存单元。因此,若快表未命中,则访问某个逻辑地址需要两次访存(注意:在找到页表项后,应同时将其存入快表,以便后面可能的再次访问。但若快表已满,则必须按照-定的算法对旧的页表项进行替换)
由于查询快表的速度比查询页表的速度快很多,因此只要快表命中,就可以节省很多时间。 因为局部性原理,–般来说快表的命中率可以达到90%以上。
例:某系统使用基本分页存储管理,并采用了具有快表的地址变换机构。访问- -次快表耗时1us, 访问一次内存耗时100us。若快表的命中率为90%,那么访问一个逻辑地址的平均耗时是多少? (1+100) * 0.9 + (1+100+100) * 0.1 = 111 us 有的系统支持快表和慢表同时查找,如果是这样,平均耗时应该是(1+100) * 0.9+ (100+100) *0.1=110.9 us 若未采用快表机制,则访问一个逻辑地址需要100+100 = 200us 显然,引入快表机制后,访问一个逻辑地址的速度快多了。
交换技术主要是在不同进程(或作业)之间进行,而覆盖则用于同一程序或进程中。
算法思想:每次都从低地址开始查找,找到第–个能满足大小的空闲分区。
如何实现:空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链( 或空闲分[表),找到大小能满足要求的第-一个空闲分区。
算法思想:由于动态分区分配是一种连续分配方式,为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间,可以尽可能多地留下大片的空闲区,即,优先使用更小的空闲区。
如何实现:空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第-一个空闲分区。
又称最大适应算法(Largest Fit)
算法思想:为了解决最佳适应算法的问题—即留下太多难以利用的小碎片,可以在每次分配时优先使用最大的连续空闲区,这样分配后剩余的空闲区就不会太小,更方便使用。
如何实现:空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第-一个空闲分区。
算法思想:首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区,而每次分配查找时,都要经过这些分区,因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索,就能解决上述问题。
如何实现:空闲分区以地址递增的顺序排列(可排成-一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
首次适应不仅最简单,通常也是最好最快,不过首次适应算法会使得内存低地址部分出现很多小的空闲分区,而每次查找都要经过这些分区,因此也增加了查找的开销。邻近算法试图解决这个问题,但实际上,它常常会导致在内存的末尾分配空间分裂成小的碎片,它通常比首次适应算法结果要差。
最佳导致大量碎片,最坏导致没有大的空间。
进过实验,首次适应比最佳适应要好,他们都比最坏好。
虚拟技术把一个物理实体转换为多个逻辑实体。
主要有两种虚拟技术:时(时间)分复用技术和空(空间)分复用技术。
多进程与多线程:多个进程能在同一个处理器上并发执行使用了时分复用技术,让每个进程轮流占用处理器,每次只执行一小个时间片并快速切换。
虚拟内存使用了空分复用技术,它将物理内存抽象为地址空间,每个进程都有各自的地址空间。地址空间的页被映射到物理内存,地址空间的页并不需要全部在物理内存中,当使用到一个没有在物理内存的页时,执行页面置换算法,将该页置换到内存中。
应该注意以下内容:
四个过程:
(1)预编译 主要处理源代码文件中的以“#”开头的预编译指令。处理规则见下 1、删除所有的#define,展开所有的宏定义。 2、处理所有的条件预编译指令,如“#if”、“#endif”、“#ifdef”、“#elif”和“#else”。 3、处理“#include”预编译指令,将文件内容替换到它的位置,这个过程是递归进行的,文件中包含其他 文件。 4、删除所有的注释,“//”和“/**/”。 5、保留所有的#pragma 编译器指令,编译器需要用到他们,如:#pragma once 是为了防止有文件被重 复引用。 6、添加行号和文件标识,便于编译时编译器产生调试用的行号信息,和编译时产生编译错误或警告是 能够显示行号。
(2)编译 把预编译之后生成的xxx.i或xxx.ii文件,进行一系列词法分析、语法分析、语义分析及优化后,生成相应 的汇编代码文件。 1、词法分析:利用类似于“有限状态机”的算法,将源代码程序输入到扫描机中,将其中的字符序列分 割成一系列的记号。 2、语法分析:语法分析器对由扫描器产生的记号,进行语法分析,产生语法树。由语法分析器输出的 语法树是一种以表达式为节点的树。 3、语义分析:语法分析器只是完成了对表达式语法层面的分析,语义分析器则对表达式是否有意义进 行判断,其分析的语义是静态语义——在编译期能分期的语义,相对应的动态语义是在运行期才能确定 的语义。 4、优化:源代码级别的一个优化过程。 5、目标代码生成:由代码生成器将中间代码转换成目标机器代码,生成一系列的代码序列——汇编语言 表示。 6、目标代码优化:目标代码优化器对上述的目标机器代码进行优化:寻找合适的寻址方式、使用位移 来替代乘法运算、删除多余的指令等。 (3)汇编 将汇编代码转变成机器可以执行的指令(机器码文件)。汇编器的汇编过程相对于编译器来说更简单,没 有复杂的语法,也没有语义,更不需要做指令优化,只是根据汇编指令和机器指令的对照表一一翻译过 来,汇编过程有汇编器as完成。经汇编之后,产生目标文件(与可执行文件格式几乎一样)xxx.o(Linux 下)、xxx.obj(Windows下)。 (4)链接 将不同的源文件产生的目标文件进行链接,从而形成一个可以执行的程序。链接分为静态链接和动态链 接: 1、静态链接: 函数和数据被编译进一个二进制文件。在使用静态库的情况下,在编译链接可执行文件时,链接器从库 中复制这些函数和数据并把它们和应用程序的其它模块组合起来创建最终的可执行文件。 空间浪费:因为每个可执行程序中对所有需要的目标文件都要有一份副本,所以如果多个程序对同一个 目标文件都有依赖,会出现同一个目标文件都在内存存在多个副本; 更新困难:每当库函数的代码修改了,这个时候就需要重新进行编译链接形成可执行程序。 运行速度快:但是静态链接的优点就是,在可执行程序中已经具备了所有执行程序所需要的任何东西, 在执行的时候运行速度快。 2、动态链接: 动态链接的基本思想是把程序按照模块拆分成各个相对独立部分,在程序运行时才将它们链接在一起形 成一个完整的程序,而不是像静态链接一样把所有程序模块都链接成一个单独的可执行文件。 共享库:就是即使需要每个程序都依赖同一个库,但是该库不会像静态链接那样在内存中存在多份副 本,而是这多个程序在执行时共享同一份副本; 更新方便:更新时只需要替换原来的目标文件,而无需将所有的程序再重新链接一遍。当程序下一次运 行时,新版本的目标文件会被自动加载到内存并且链接起来,程序就完成了升级的目标。 性能损耗:因为把链接推迟到了程序运行时,所以每次执行程序都需要进行链接,所以性能会有一定损 失。
《操作系统(三)》:https://www.nowcoder.com/tutorial/93/675fd4af3ab34b2db0ae650855aa52d5
可以借助进程的页表将逻辑地址转换为物理地址。
通常会在系统中设置一个页表寄存器(PTR),存放页表在内存中的起始地址F和页表长度M。进程未执行时,页表的始址和页表长度放在进程控制块(PCB) 中,当进程被调度时,操作系统内核会把它们放到页表寄存器中。
注意:页面大小是2的整数幂 设页面大小为L,逻辑地址A到物理地址E的变换过程如下:
例:若页面大小L为1K字节,页号2对应的内存块号b=8,将逻辑地址A=2500转换为物理地址E。 等价描述:某系统按字节寻址,逻辑地址结构中,页内偏移量占10位(说明一个页面的大小为2^10B = 1KB),页号2对应的内存块号 b=8,将逻辑地址A=2500转换为物理地址E。
①计算页号、页内偏移量 页号P=A/L = 2500/1024 = 2; 页内偏移量W= A%L = 2500%1024 = 452 ②根据题中条件可知,页号2没有越界,其存放的内存块号b=8 ③物理地址E=b*L+W=8 * 1024+ 425 = 8644 在分页存储管理(页式管理)的系统中,只要确定了每个页面的大小,逻辑地址结构就确定了。因此,页式管理中地址是-维的。即,只要给出一个逻辑地址,系统就可以自动地算出页号、页内偏移量两个部分,并不需要显式地告诉系统这个逻辑地址中,页内偏移量占多少位。
对临界资源进行访问的那段代码称为临界区。
为了互斥访问临界资源,每个进程在进入临界区之前,需要先进行检查。
// entry section
// critical section;
// exit section
信号量(Semaphore)是一个整型变量,可以对其执行 down 和 up 操作,也就是常见的 P 和 V 操作。
down和up操作需要被设计成原语,不可分割,通常的做法是在执行这些操作的时候屏蔽中断。
如果信号量的取值只能为0或者1,那么就成为了互斥量(Mutex),0 表示临界区已经加锁,1 表示临界区解锁。
typedef int semaphore;
semaphore mutex = 1;
void P1() {
down(&mutex);
// 临界区
up(&mutex);
}
void P2() {
down(&mutex);
// 临界区
up(&mutex);
}
使用信号量实现生产者-消费者问题
问题描述:使用一个缓冲区来保存物品,只有缓冲区没有满,生产者才可以放入物品;只有缓冲区不为空,消费者才可以拿走物品。
因为缓冲区属于临界资源,因此需要使用一个互斥量 mutex 来控制对缓冲区的互斥访问。
为了同步生产者和消费者的行为,需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计,这里需要使用两个信号量:empty 记录空缓冲区的数量,full 记录满缓冲区的数量。
其中,empty 信号量是在生产者进程中使用,当 empty 不为 0 时,生产者才可以放入物品;full 信号量是在消费者进程中使用,当 full 信号量不为 0 时,消费者才可以取走物品。
注意,不能先对缓冲区进行加锁,再测试信号量。也就是说,不能先执行 down(mutex) 再执行 down(empty)。如果这么做了,那么可能会出现这种情况:生产者对缓冲区加锁后,执行 down(empty) 操作,发现 empty = 0,此时生产者睡眠。
消费者不能进入临界区,因为生产者对缓冲区加锁了,消费者就无法执行 up(empty) 操作,empty 永远都为 0,导致生产者永远等待下,不会释放锁,消费者因此也会永远等待下去。
#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
void producer() {
while(TRUE) {
int item = produce_item();
down(&empty);
down(&mutex);
insert_item(item);
up(&mutex);
up(&full);
}
}
void consumer() {
while(TRUE) {
down(&full);
down(&mutex);
int item = remove_item();
consume_item(item);
up(&mutex);
up(&empty);
}
}
使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制,而管程把控制的代码独立出来,不仅不容易出错,也使得客户端代码调用更容易。
c 语言不支持管程,下面的示例代码使用了类 Pascal 语言来描述管程。示例代码的管程提供了 insert() 和 remove() 方法,客户端代码通过调用这两个方法来解决生产者-消费者问题。
monitor ProducerConsumer
integer i;
condition c;
procedure insert();
begin
// ...
end;
procedure remove();
begin
// ...
end;
end monitor;
管程有一个重要特性:在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程,否则其它进程永远不能使用管程。
管程引入了条件变量以及相关的操作:wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞,把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。
使用管程实现生产者-消费者问题
// 管程
monitor ProducerConsumer
condition full, empty;
integer count := 0;
condition c;
procedure insert(item: integer);
begin
if count = N then wait(full);
insert_item(item);
count := count + 1;
if count = 1 then signal(empty);
end;
function remove: integer;
begin
if count = 0 then wait(empty);
remove = remove_item;
count := count - 1;
if count = N -1 then signal(full);
end;
end monitor;
// 生产者客户端
procedure producer
begin
while true do
begin
item = produce_item;
ProducerConsumer.insert(item);
end
end;
// 消费者客户端
procedure consumer
begin
while true do
begin
item = ProducerConsumer.remove;
consume_item(item);
end
end;
进程通信方法
线程通信方法
Linux几乎支持全部UNIX进程间通信方法,包括管道(有名管道和无名管道)、消息队列、共享内存、信号量和套接字。其中前四个属于同一台机器下进程间的通信,套接字则是用于网络通信。
管道
消息队列
相比于 FIFO,消息队列具有以下优点:
共享内存
进程可以将同一段共享内存连接到它们自己的地址空间,所有进程都可以访问共享内存中的地址,如果某个进程向共享内存内写入数据,所做的改动将立即影响到可以访问该共享内存的其他所有进程。
信号量
在提到共享内存方式时也提到,进程共享内存和多线程共享全局变量非常相似。所以在使用内存共享的方式是也需要通过信号量来完成进程间同步。多线程同步的信号量是POSIX信号量,而在进程里使用SYSTEM V信号量。
辅助命令
ipcs命令用于报告共享内存、信号量和消息队列信息。
套接字
与其它通信机制不同的是,它可用于不同机器间的进程通信。
虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存,从而让程序获得更多的可用内存。
为了更好的管理内存,操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间,这个地址空间被分割成多个块,每一块称为一页。
这些页被映射到物理内存,但不需要映射到连续的物理内存,也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时,由硬件执行必要的映射,将缺失的部分装入物理内存并重新执行失败的指令。
从上面的描述中可以看出,虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存,也就是说一个程序不需要全部调入内存就可以运行,这使得有限的内存运行大程序成为可能。
例如有一台计算机可以产生 16 位地址,那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存,虚拟内存技术允许该计算机运行一个 64K 大小的程序。
完了,白了个白!
哦,等下,差点忘了,《逆袭进大厂》第一版 PDF 的下载方式就是公众号后台回复关键字【逆袭进大厂】即可,也可点击文末左侧的『阅读原文』去 github 仓库看一看呐。
—END—
小伙伴你好,我是阿秀,一个菜逼程序员
。公众号后台回复「宝贝」,送你一个宝贝!真的是宝贝!