构成上：进程内部含有线程和和逻辑内存；线程内部含有栈、包含程序计数器PC(保存下一条指令的地址)在内的CPU寄存器
功能上：进程是操作系统资源(全局变量、打开的文件等)分配的基本单位，同一进程内共享资源；线程是操作系统CPU任务执行的基本单位
- 即运行一个进程需要一核CPU，而这个CPU会在这个进程的线程之间来回切换执行不同的线程
开销上：每个进程有独立代码和数据空间(堆和静态变量)，切换开销大；每个线程只有运行栈、PC是独立的，切换开销小

2.程序、进程、线程、协程

程序和进程的概念
- 程序是一组指令的集合，是一个静态实体；
- 进程则是某个数据集上的程序执行，是一个动态实体；
- 运行的程序至少会有一个进程
协程比线程轻量级的原因
- 线程切换时会出现“CPU执行线程1变成CPU执行线程2”这个操作，而要对CPU进行调度，需要系统从用户态切换成内核态，而OS切换状态是非常耗费资源的，因为要去保存用户态的工作，后面切回来还得去恢复工作状态
- 而协程的切换只是让同一个线程来执行不同协程，不会去涉及CPU的调度，并且协程的切换可以由程序代码控制，而线程的切换是有系统的策略的

3.操作系统的储存:

容量从大到小：硬盘、内存、缓存、寄存器
速度从快到慢：寄存器、缓存、内存、硬盘

即容量越小速度越快

4.操作系统的寻址操作

首先根据指针访问进程中的逻辑地址(逻辑地址是虚拟的)
由逻辑地址解析得到物理内存中的地址(但这个地址也可能是系统虚拟处理的内存，以分页的形式存放在物理内存中)
将该地址拿给CPU的寄存器处理

5.进程间的通信方式

共享内存：两进程共享一块内存，该内存上数据可以共同修改和读取
管道通信：实现进程间通信的一种共享文件，用于连接一个读进程和一个写进程
消息队列：是消息的链表，有标识符标记并存在内核中
套接字(socket)：是网络编程的api，通过它可实现不同机器、不同进程之间的通信
信号：操作系统通过信号来通知进程系统中发生某种预先规定好的事件

6.线程同步的方式

互斥量：针对一个共享资源的单独访问设计，采用互斥对象机制，只有拥有互斥对象的线程才被允许访问公共资源，因为互斥对象只有一个所以保证了同一时间只有一个线程访问
信号量：针对一个使用用户数量有限制的资源设计，允许同一时刻多个线程访问同一资源，只要不达到最大数就行
事件(信号)：针对具有后继任务的事件设计，通过通知操作的方式来保持多线程同步，还可以方便实现多线程优先级的比较
临界区：针对公共资源或一段代码设计，通过对多线程的串行化来访问公共资源，速度快

7.进程的三种状态（调度方法有抢占式和非抢占式）

运行状态
就绪状态(等待被调度使用CPU的运行权)
阻塞状态

8.线程的六种状态

初始：还没有调用start()方法
运行
阻塞：线程阻塞于锁
等待：等待其他线程做出一些特定动作
超时等待：在超过时间后会自动返回
终止：表示该线程已执行完毕

9.CPU的调度算法

先来先服务：先来的先执行
短作业优先：运行完成当前作业会去找最短的作业执行(这个短的由用户定义，实际不一定短)
时间片轮转：设定一个时间片大小，把任务分割成n部分，选取等待时间最长的先执行

10.死锁：指两个或两个以上的进程在执行过程中，由于竞争资源或由于彼此通信而造成的阻塞，若无外力作用无法推进下去

产生条件

互斥条件：一段时间内某资源只能由一个进程占有
请求和保持：进程已经占有至少一个资源，但又对其他进程占有的资源提出要求，此时进程阻塞，但又对已经获得的资源保持不放
不可抢占：进程已获得的资源，在它使用完之前不能剥夺
环路条件：在一个环形链中，每个进程都在等待一个被占用的资源

死锁处理方法

鸵鸟策略(大部分采用)：直接忽略死锁
预防死锁
- 破坏互斥，让资源静态分配可以共享使用(一般无法破坏)
- 破坏请求与保持，规定所有进程在它们执行之前要请求所有它们需要的资源
- 破坏不可抢占，让高优先级可以剥夺低优先级的资源
- 破坏环路：给资源编号，按顺序申请资源
避免死锁：安全序列、银行家算法
检测和接触死锁
- 一次消除与不阻塞进程相连的边，最后剩下的就是出现死锁的进程(也叫资源分配图)
- 资源剥夺、终止进程、进程回退

11.什么是内存?

答：内存是一种高速存储设备，仅次于寄存器和缓存。因为CPU处理速度与外存读取程序速度存在差异，所以程序执行前要先放入内存后再被CPU处理，内存用于缓和CPU与外存的速度矛盾，提高CPU利用率

12.虚拟内存时为了防止不同进程同一时刻在物理内存中运行而产生对物理内存的争夺，每个进程看到自己独占了内存空间，但实际只是把目前自己需要的内存空间映射并存储到物理内存上

13.缺页中断：每当要访问的页面不在内存中，会产生一次缺页中断，然后系统再根据页表中的外存地址找到该页并调入内存

与一般中断步骤一样：保护CPU现场-分析中断原因-转入中断处理程序-回复现场
不同点在于：缺页中断返回后会继续执行该指令，其他中断返回后会执行下一条指令

14.并发：宏观上两程序同时运行，例如单核CPU的多任务，但微观上还是你一条指令、我一条指令交替运行的。并不能提高计算机性能，只能提高效率

并行：严格意义上的同时运行，例如多核CPU，两程序同时分别运行在两个核上，提高了计算机性能

15.单核机器上写多线程程序，为什么仍需要考虑加锁？

答：因为线程锁用于实现线程的同步和通信，在抢占式操作系统中，当某线程时间片耗尽被挂起时，为保证运行的下一个线程不会出错(两线程共享同一数据的情形)，要使用线程锁

16.线程切换

要保存当前线程id、线程状态、堆栈、寄存器状态
主要寄存器有：
- 堆栈指针sp，指向当前栈的栈顶地址
- 程序计数器PC，存储下一条将要执行的指令
- 累加寄存器EAX，用于加法乘法的缺省寄存器

17.内存溢出：程序申请内存时，没有足够的内存供申请者使用

内存泄漏：出于某种原因没有释放掉不再使用的内存的情况，失去了对该部分内存的控制，造成浪费

18.源码到可执行文件的过程：

预编译：主要处理源码中以#开头的预编译指令，生成xx.i或xx.ii文件
编译：进行语法分析和优化后，生成汇编代码文件
汇编：将汇编代码转变成机器可以执行的指令，按照对照表翻译即可，生成xx.o或xx.obj文件
链接：形成可以执行的程序
- 动态只在程序运行时才把个模块链接起来
- 静态是预先就全部链接起来

19.进程种类：

正常进程：父进程用wait()或waitpi()系统调用获知子进程是否终止
孤儿进程：一个父进程退出，它的还在运行的子进程就成为了孤儿进程，有init进程(进程号为1)收养，并有init进程负责他们完成状态的收集工作
僵尸进程：被fork()创建的子进程退出后，父进程没有使用wait()或waitpi()获知，该子进程的进程描述符仍保存在系统中(一直占据进程号)，成为僵尸进程

20.五种IO模型(前四种都是同步IO)：

阻塞IO：调用socket后，会一直卡在这里直到socket有数据为止
非阻塞IO：自旋轮询去问每一个socket是否有数据，有就接受，没有就问下一个
信号驱动IO：进程继续运行不阻塞，当IO事件就绪时，进程收到SIGIO信号，然后处理IO事件，即该水龙头有水了就通知
IO复用(转接IO)：系统select或epoll去监听各个socket，每当确定有数据可读或可写时才去进行IO操作，select只告诉有事件发生，去操作的时候还要遍历一遍确认一下是哪里的事件；而epoll直接把发生的事件列表发过来，可以直接去操作
- 即同一个操作里同时监听多个输入输出源，在其中一个源可用时返回，并开始对其进行读写操作
异步IO：linux中，调用aio_read告知内核描述字缓冲区指针和缓冲区大小、文件偏移等，当内核将数据拷贝到缓冲区后，再通知程序，即该水龙头下的杯子接满水了再通知

21.多线程、线程池、IO复用可以使server接受多个client的请求

22.怎么实现线程池

设置一个生产者消费者队列作为临界资源
初始化n个线程并让其运行
当任务队列为空时，所有线程阻塞
当生产者队列生产出一个任务后，先对生产者队列加锁，然后把任务挂到任务队列上，最后再用条件变量区通知阻塞中的一个线程

23.立即寻址不用访问内存

24.用来实现线程间的通知和唤醒的两种方法

Object.wait/notify/notifyALL
Condition.await/signal/signalALL

25.微机一般是16位或32位机，“微”指的是机器的字长

26.建立符号链接时，引用计数值直接复制，删除两个文件的任一个不影响值，而是直接删除链接

建立硬链接时，双方的引用值+1，删除文件时将与之硬链接的文件引用值减1，若某文件引用值为0则会删除该文件

27.若系统有m个进程，则就绪队列的进程数就为0 ~ m-1个

28.文件属性有：系统、只读、隐藏、存档

29.进程在运行中不能自行修改PCB(进程管理块)

30.挂起就绪状态(也叫静止就绪)的进程只能转换为就绪状态(活动就绪)

31.处于同一进程的多个线程，CPU寄存器对每个线程来说都是私有的

32.用户态和内核态

每个进程都有一个4G大小的虚拟地址空间，前3G为用户空间，每个进程的用户空间之间是相互独立的，互不相干。而3G～4G为内核空间，因为每个进程都可以从用户态切换到内核态。内核空间对于所有进程来说可以说是共享的
系统从用户态切换到内核态，需要中断操作
- 发生系统调用时：用户态的进程通过系统调用申请使用操作系统提供的系统调用服务例程来处理任务，而系统调用的机制使用了操作系统特别开发的一个中断机制来实现的，即软中断
- 产生异常时
- 外设产生中断时
切换到内核态开销大来源于：中断的工作以及处理恢复工作非常耗时

33.用户使用计算机的方式

命令接口：联机命令接口和脱机命令接口
程序接口：系统调用
GUI接口：图形接口

34.DOS是磁盘操作系统

35.文件管理系统管理的对象(最小磁盘空间单位是扇区)

文件
目录
磁盘存储空间

36.物理地址的计算

先已知逻辑地址(16进制换成逻辑地址(10进制) / 每页大小(1k就是1024) = 商 + 余数
商就是页号，根据页号和物理块号的关系得到物理块号，余数就是页内偏移
物理地址(10进制) = 物理块号 - 每页大小 + 页内偏移

37.线程共享堆和静态变量，不共享寄存器、栈、PCB、状态

38.页的计算

页面大小就是每一页的容量
页表项大小是每一页对应目录的一个项，页表项之和就是目录大小
逻辑空间大小就是整本书的页数

39.实模式下的算法就是CS往左移1位十进制 + ip

例如：地址位2330H：5041H，实际地址为23300+5041=28341H

40.几核CPU就表示可同时运行几个进程，但因为CPU运转速度极快我们会感觉所有进程都是同时运行的

41.几个名词的解释

物理层面：磁盘组合->单个磁盘->某一盘面->某一磁道->某一扇区，簇就是包含几个相邻扇区的集合(方便调用)，Linux下叫做块
虚拟层面：页
BIOS：用于在电脑启动初期检测基本的硬件的程序，随后加载grub，grub之后会把操作系统内核加载进来，并运行内核，最后就是内核启动，并将最终界面展示在你面前了
引导文件：是一个具有隐藏和只读属性的系统文件，它的主要职责是解析INI的文件，在预引导阶段里计算机所做的工作，运行POST程序，POST将检测系统的总内存以及其他硬件设备的状况，将磁盘第一个物理扇区加载到内存，加载硬盘主引导记录并运行，主引导记录会查找活动分区的起始位置，接着活动分区的引导扇区被加载并执行，最后从引导扇区加载并初始化NTLDR文件

42.操作系统的地址映射使用段页式实现

43.操作系统的内存管理

虚拟内存，来实现内存抽象，每个进程都以为自己拥有全部内存，操作虚拟地址的操作都会被转换为操作物理地址
页面替换算法：当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存

44.一个进程占用什么资源

（1）地址空间
（2）全局变量
（3）打开的文件
（4）子进程
（5）信号量
（6）账户信息

进阶部分

1.操作系统的四个特性

并发：同一段时间内多个程序执行(并行指的是同一时刻)
共享：系统中资源可以被内存中多个并发执行的进程共同使用
虚拟：通过时分复用(分时系统)以及空分复用(虚拟内存)实现把一个物理实体虚拟成多个虚拟实体
异步：系统中的进程以走走停停方式执行，且以一种不可预知的速度推进

2.操作系统主要功能

处理机管理
存储器管理(又叫内存管理)
设备管理
文件管理
提供用户接口

3.采用段页式存储，将进程按逻辑模块分段，再将各段分页，将内存空间分为大小相同的页框，将程序按页装入页框，分页分段都是为虚拟内存服务的。

分页：指将内存空间分为一个个大小相等的分区，每个分区叫页框(一般为1kb)，将用户进程的地址空间分为与页框相等的一个个称为页的区域。
- 进程的每一个页都要放入一个页框里
- 程序使用的仍是逻辑地址，通过页表地址加页内偏移才能得到物理地址
分段：指程序按自身逻辑关系划分为若干段，例如代码段、数据段、堆栈段
分页和分段区别
- 分页是系统为利用内存空间，将程序按页装入内存，是系统行为；分段是按程序逻辑意义划分，要用户来划分每个段
- 页的大小是固定的，段的大小则取决于用户编写的程序
- 分页是一维地址空间，分段是二维地址空间(即第0页最后一个地址与第1页第一个地址是连续的，而段号0最后一个地址与段号1第一个地址不是连续的)
缺页中断：当前指令想要访问的页面没有调入内存，而发生的中断

4.页面置换算法

最佳置换算法(OPT)：每次淘汰的页面都是最长时间内不再被访问的页面，保证最低缺页率(但因为一般无法预知页面访问序列，因此无法实现)
先进先出算法(FIFO)：每次淘汰的页面都是最早进入内存的页面(较简单，性能较差)
最近最久未使用置换算法(LRU)：每次淘汰的页面都是最近最久未使用的页面
- 数组实现：用一个数组来存数据，每个数据有一个时间戳t，插入时将新数据t设为0，旧数据t加1，访问时将被访问数据t设为0，满内存时删除t最大的数据
- 链表实现：插入时放在首部，访问时放在首部，满内存时删除最末尾的数据
时钟置换算法(CLOCK)：为每个页面加一个访问位(0为最近未访问，1为最近访问)，淘汰时先淘汰访问位为0的，遇到1就把它改为0，下一次循环遍历到再淘汰(淘汰一个页面最多两次扫描)
- 改进型：再多加一个修改位，即每个页面有(访问位，修改位)，淘汰顺序(0,0)>(0,1)>(1,0)>(1,1),没有一个(0,0)时才淘汰一个(0,1)以此类推(淘汰一个页面最多四次扫描)

5.磁盘寻址

根据“柱面号”移动磁壁，让磁头指向指定柱面
激活指定盘面对应的磁头
磁盘旋转过程中，指定的扇区会从磁头下面划过，完成对其的读写

磁盘调度算法

先来先服务：按磁盘请求顺序进行调度
最短寻找时间优先：优先处理与当前磁头最近的磁道，易出现饥饿现象(最后两个磁道相距极远)
电梯算法：优先处理与当前磁头最近的磁道，但磁头移动方向固定，只能一直往外侧磁道移，移到最外后只能一直往内侧磁道移，降低饥饿现象

6.Linux进程的内存结构分为：用户空间和内核空间，内核空间在系统调用时才可访问，内核映射是固定的，分用户态和内核态是为了安全，因为内核一旦出错就会使整个系统崩溃

用户空间分为

只读段：把含程序代码(.init和.text)和只读数据(.rodata)
数据段：存放全局变量和静态变量，可读可写数据段(.data)存放已初始化的，BSS数据段存放未初始化的
栈：由系统自动分配释放。存放函数的参数值、局部变量、返回地址
堆：存放动态分配的数据，一般由程序员分配释放
共享库的内存映射区域：Linux动态连接器和其他共享库代码的映射区域

7.fork()和vfork()都是拷贝进程，vfork()较快因为不用复制页表

fork()子进程拷贝父进程的数据段和代码段，子进程执行顺序不确定
vfork()子进程与父进程共享，保证子进程先运行

8.Linux的四种锁机制（获取锁失败后，线程会睡眠，等待锁释放的时候再被唤醒）

互斥锁mutex：任何时刻，只要一个线程访问该对象
读写锁rwlock：分读锁和写锁，写优先于读，一旦有写者，则后续读者都得等待
- 读操作时，允许多个线程同时获得
- 写操作时，只允许一个线程获得
自旋锁spinlock：与互斥锁一样，但线程获取自旋锁失败后会进入自旋（保持唤醒，消耗CPU），直到锁被释放
RCU：即read-copy-update，在改数据时先读，然后生成一个副本，对副本修改后再将老数据更新为新数据

9.判断大端和小端用联合体变量，因为联合体变量总是从低地址(小端)到高地址存储的

大端：低字节存在高地址
小端：低字节存在低地址(主流intelCPU采用的方式)
例如0x12345678中，0x12是最高字节，0x78是最低字节，而在操作系统中地址从左往右从小往大
- 大端0x12、0x34、0x56、0x78
- 小端0x78、0x56、0x34、0x12

10.常用线程模型

Future模型：把结果放在将来获取，当前主线程并不急于获取处理结果，允许子线程先进行处理一段时间，处理结束后把结果保存，当主线程需要时再向子线程索取
fork与join模型：把一个大任务分成多个子任务，然后分别再子线程中执行，每个子线程执行结束之后逐级回溯，返回结果进行合并计算
actor模型：基于消息传递机制并行任务处理，以消息的形式来进行线程间数据传输，避免了全局变量的使用，每个actor接受消息后可以自己处理也可以传递给其它actor处理
生产消费者模型：分为生产者线程和消费者线程，其核心时使用一个缓存来保存任务。生产者不处理任务，只负责生成任务然后保存到缓存中，消费者只负责从缓存中取出任务并处理
master-worker模型：有一个master线程负责接受和分发任务，worker子线程负责处理任务并在需要时返回处理结果给master

11.协程的暂停完全由程序控制，开销远小于线程，一个线程可拥有多个协程

12.宏内核：内核执行大部分操作，包括调度、内存管理、文件系统、驱动、网络协议，例如linux内核，效率高但稳定性差

微内核：内核只执行调度、内存管理，其他功能用用户态的守护进程去实现，出错也只会导致对应进程死掉，效率低但稳定性好

13.异步编程的事件循环：在单个的线程中，如果某事件绑定了两个处理器，那它也会先去第一个处理器处理再去第二个处理器处理，在这个事件的所有处理器执行完毕前，事件循环不会去检查是否有新事件触发

14.Unix的文件系统按物理结构划分，采用索引文件；Unix时分时系统

15.银行家算法中：需求矩阵 = 最大需求矩阵 - 分配矩阵

16.内存屏障用于使CPU有序，在高级语言的体现就是锁

17.二层交换机(层指的是OSI模型前几层)：不同VLAN(广播域)之间的通信必须通过三层设备；交换机仅根据MAC地址进行帧的转发

18.若进程P一旦被唤醒就能投入运行，则系统是抢占调度式，P的优先级高于正在运行的进程

19.实时系统中的进程调度采用抢占式的优先级高者优先执行的算法

20.原语有不可中断性，它是通过在执行过程中关闭中断实现的，且一般由系统进程调用

21.最佳适应算法时按空闲区大小递增顺序形成空闲分区链

22.逻辑设备表(LUT)作用：在物理设备和逻辑设备之间建立对应关系

23.信号量初值为2，表示为有两个可用资源；当前值为-1，表示两个可用资源都在忙且还有一个等待进程

24.一次I/O请求对应一个I/O请求包；每次I/O操作都会有对应的I/O请求包

25.进程

阻塞->就绪：靠“合作”进程的唤醒
就绪->执行：靠下一个时间片的到来

26.守护进程最重要的特性是后台运行，并且守护进程必须与其运行前的环境隔离开来。创建方法：

在父进程使用fork()创建子进程，然后关闭父进程
在子进程中用系统函数setsid创建新会话
改变当前工作目录
重设文件创建掩码为0，umask(0)
关闭从父进程继承而来的文件描述符(隔离性)

27.指令流水线

例如一条指令要执行要经过3个阶段：取指令、译码、执行，每个阶段都要花费一个机器周期，如果没有采用流水线技术，那么这条指令执行需要3个机器周期；如果采用了指令流水线技术，那么当这条指令完成“取指”后进入“译码”的同时，下一条指令就可以进行“取指”了
常见的六级流水线将指令流的处理过程划分为取指(FI)、译码(DI)、计算操作数地址(CO)、取操作数(FO)、执行指令(EI)、写操作数(WO)等几个并行处理的过程段。这就是指令6级流水时序。在这个流水线中，处理器有六个操作部件，同时对这六条指令进行加工，加快了程序的执行速度。几乎所有的高性能计算机都采用了指令流水线

28.内核同步

避免由于对共享数据的不安全访问导致的数据崩溃
原子操作
自旋锁
读写锁
信号量（计数信号量、二值信号量）
屏障
- 优化屏障，原语保证编译程序不会混淆放在原语操作之前的汇编语言指令和放在原语操作之后的汇编语言指令，这些汇编语言指令在C中都由对应的语句。在Linux中，优化屏障就是barrier()宏
- 内存屏障，原语确保，在原语之后的操作开始执行之前，原语之前的操作已经完成。因此，内存屏障类似于防火墙，让任何汇编语言指令都不能通过

29.如果把一个较大的数据放入内存该怎么做

用到虚拟内存，匀出一部分硬盘空间来充当内存使用，但计算机从RAM读取数据的速率要比从硬盘读取数据的速率快，因此一般扩增RAM容量(加内存条)
- 1.中央处理器访问主存的逻辑地址分解成组号a和组内地址b，并对组号a进行地址变换，即将逻辑组号a作为索引，查地址变换表，以确定该组信息是否存放在主存内
- 2.如该组号已在主存内，则转而执行4；如果该组号不在主存内，则检查主存中是否有空闲区，如果没有，便将某个暂时不用的组调出送往辅存，以便将这组信息调入主存
- 3.从辅存读出所要的组，并送到主存空闲区，然后将那个空闲的物理组号a和逻辑组号a登录在地址变换表中
- 4.从地址变换表读出与逻辑组号a对应的物理组号a
- 5.从物理组号a和组内字节地址b得到物理地址
- 6.根据物理地址从主存中存取必要的信息
用到分块

Kenway's Blog

【笔记】操作系统笔记

目录

基础部分

进阶部分