操作系统知识点

进程

进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和资源调度的一个独立单位，由程序代码和相关数据还有进程控制块组成。

进程控制块：标识符、状态、优先级、程序计数器、内存指针、上下文数据、I/O状态信息、记账信息。

五态：新建态、就绪态、运行态、等待态、退出态。

进程创建：

1. 分配唯一进程标识符
2. 分配空间
3. 初始化进程控制块
4. 设置正确的连接
5. 创建或扩充其他数据结构

用户态->内核态依靠中断机制：

1. 中断
   1.时钟中断
   2.I/O中断
   3.内存失效

2. 陷阱(异常或错误)

3. 系统调用(显式请求)

进程间通信

同一台机器的进程间通信：管道、消息队列、共享内存、信号量
不同机器的进程间通信：套接字

1. 管道
   无名管道 在内核中，只能用于父子进程或者兄弟进程间通信。
   有名管道，以FIFO的文件形式在文件系统中，可以用于任意两个进程。

2. 消息队列
   一个在系统内核中用来保存消息的队列，在系统内核中是以消息链表的形式出现。
   与管道相比，优点：1. 消息队列可以独立发送和接收进程而存在，消除了管道打开和关闭可能产生的困难；2. 可以同时通过发送消息以避免命名管道的同步和堵塞问题；3. 接收程序可以通过消息类型有选择地接收数据，而不是像管道只能默认地接收。
   事实上，消息队列正在被淘汰，可以流管道和套接口来取代。

3. 共享内存
   是允许两个不相关的进程访问同一个逻辑内存。
   常安排在同一段物理内存中，效率最快。
   但是共享内存并未提供同步机制，需要用其他的机制来同步对共享内存的访问。

4. 信号量
   可以解决共享内存的同步问题。
   守护进程P347
   进程间通信P352

ipcs
报告系统的消息队列、信号量、共享内存等
-a 列出本用户所有相关的ipcs参数
-q 列出进程中的消息队列
-s 列出所有的信号量
-m 列出所有的共享内存信息
-l 列出系统的限额
-t 列出最后的访问时间
-u 列出当前的使用情况

进程状态

• 孤儿进程，是指一个父进程退出后，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程收养，并由init进程对它们完成状态收集工作。

• 僵尸进程，是指一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。
  区别：孤儿进程是父进程已退出，而子进程未退出；僵尸进程是父进程未退出，而子进程已退出。

• 守护进程是脱离于终端并且在后台运行的进程

创建一个简单的守护进程的步骤：

1. 创建子进程，父进程退出
2. 在子进程中创建新会话
3. 改变当前目录为根目录
4. 重设文件权限掩码
5. 关闭文件描述符

线程

线程是进程的一个实体，是CPU调度和分配的基本单位。

线程有：

1. 线程执行状态
2. 线程上下文
3. 执行栈
4. 局部变量的静态存储空间
5. 与进程内的其他线程共享的对进程的内存和资源的访问。

优点：

1. 易于调度
2. 提高并发性。通过线程可以方便有效地实现并发。
3. 开销小。创建线程比创建进程要快。所需要的开销也更小。
4. 有利于发挥多处理器的功能。通过创建多线程，每个线程都在一个处理器上运行，从而实现应用程序的并行，使每个处理器都得到充分运行。

与进程区别：

1. 一个线程必定属于也只能属于一个进程；而一个进程可以拥有多个线程并且至少拥有一个线程。
2. 属于一个进程的所有进程共享该线程的所有资源。包括打开的文件、创建的Socket等。不同的进程互相独立。
3. 线程又被称为轻量级进程。进程有进程控制块，线程也有线程控制块。但线程控制块比进程控制块小得多。线程间切换代价小，进程间切换代价大。
4. 进程是程序的一次执行，线程可以理解为程序中一段程序片段的执行。
5. 每个进程都有独立的内存空间，而线程共享其所属进程的内存空间。

线程状态：
就绪态、运行态、阻塞态

内核线程和用户线程

用户线程优点：

1. 可以在不支持线程的操作系统中实现。
2. 创建和销毁线程、线程切换等线程管理的代价比内核线程少得多。
3. 允许每个进程定制自己的调度算法，线程管理比较灵活。
4. 线程能够利用的表空间和堆栈空间比内核级线程多。

缺点：

1. 同一进程中只能同时有一个线程在运行，如果有一个线程使用了系统调用而阻塞，那么整个进程都会被挂起。
2. 页面失效也会产生类似的问题。

多线程

多线程同步

1. 互斥锁
   互斥锁是一个特殊的变量，它有锁上和打开两个状态。互斥锁一般被设置成全局变量。打开的互斥锁可以由某个线程获得，获得后只有该线程有权打开这个互斥锁。

2. 条件变量
   条件变量通过允许线程堵塞和等待另一个线程发送信号的方法弥补互斥锁的不足，常与互斥锁一起使用。使用时，条件变量被用来堵塞一个线程，当条件不满足时，线程往往解开相应的互斥锁并等待条件发生变化。一旦其他的某个线程改变了条件变量，它将通知相应的条件变量唤醒一个或多个正被此条件变量阻塞的线程，这些线程将重新锁定互斥锁并重新测试条件是否满足。

3. 读写锁
   存在两种操作，一种是独占性的，写操作；一种是共享性，读操作。
   读写锁最适用于对数据结构的读操作次数多于写操作次数的场合。
   一般有两种策略：
   (1. 强读者同步：总是给读者更高的优先权，只要写者当前没有写操作，读者就可以获得访问权限。
   (2. 强写者同步：总是给写者更高的优先权，读者只能等到所有正在等待的或者正在执行的写者结束以后才能执行。
   航班订票系统一般用强读者策略，图书馆系统一般用强写者策略。
   读写锁机制是由POSIX提供的。

4. 信号量
   区别：互斥锁只允许一个线程进入临界区 信号量允许多个线程同时进去临界区

多线程重入

同步方式是为了解决“函数不可重入”的问题。“可重入函数”，是指可以由多于一个任务并发使用，而不必担心数据错误的函数。

内存管理的方式

1. 块式管理

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

1. 页式管理

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

1. 段式管理

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

1. 段页式管理

结合了段式管理和页式管理的优点。把主存先分成若干段，每个段又分成若干页。段页式管理每取一数据，要访问3次内存。

分段和分页的区别

页是信息的物理单位，分页是为了实现离散分配方式，以削减内存的外零头，提高内存的利用率；或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。
段是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。页的大小固定且有系统确定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统只能有一种大小的页面。段的长度却不固定，决定于用户所编写的程序，通常由编辑程序在对源程序进行编辑时，根据信息的性质来划分。
分页的作业地址空间是一维的，即单一的线性空间，程序员只需利用一个记忆符，即可表示一地址。分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

虚拟内存

虚拟内存简称虚存，是计算机系统内存管理的一种技术。它是相对于物理内存而言，可以理解为“假的”内存。它使得应用程序认为它拥有连续可用的内存（一个连续完整的地址空间），允许程序员编写并运行比实际系统拥有的内存大得多的程序，这使得许多大型软件项目能够在具有有限内存资源的系统上实现。而实际上，它通常被分割成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。虚存比实存有以下好处：

1. 扩大地址空间。无论段式虚存，还是页式虚存，或是段页式虚存，寻址空间都比实存大。
2. 内存保护。每个进程运行在各自的虚拟内存地址空间，互相不能干扰对方。另外，虚存还对特定的内存地址提高写保护，可以防止代码或数据被恶意篡改。
3. 公平分配内存。采用了虚存之后，每个进程都相当于有同样大小的虚存空间。
4. 当进程需要通信时，可采用虚存共享的方式实现。

不过，使用虚存也是有代价的，主要表现在以下几个方面：

1. 虚存的管理需要建立很多数据结构，这些数据结构要占用额外的内存。
2. 虚拟地址到物理地址的转换，增加了指令的执行时间。
3. 页面的换入换出需要磁盘I/O，这是很耗时间的。
4. 如果一页中只有一部分数据，会浪费内存。

内存碎片、内碎片和外碎片

• 内存碎片是由于多次进行内存分配造成的，当进行内存分配时，内存格式一般为：（用户使用段）（空白段）（用户使用段），当空白段很小的时候可能不能提供给用户足够需要的空间，可能夹在中间的空白段的大小为5，而用户需要的内存大小6，这样会产生很多的间隙造成使用效率的下降，这些很小的空隙叫碎片。
• 内碎片：分配给程序的存储空间没有用完，有一部分是程序不使用，但其他程序也没法用的空间。内碎片是处于区域内部或页面内部的存储块，占有这些区域或页面的进程并不使用这个存储块，而在进程占有这块存储块时，系统无法利用它，直到进程释放它，或进程结束时，系统才有可能利用这个存储块。
• 由于空间太小，小到无法给任何程序分配（不属于任何进程）的存储空间是外碎片。外部碎片是出于任何已分配区域或页面外部的空闲存储块，这些存储块的总和可以满足当前申请的长度要求，但是由于它们的地址不连续或其他原因，使得系统无法满足当前申请。
• 内碎片和外碎片是一对矛盾体，一种特定的内存分配算法，很难同时解决好内碎片和外碎片的问题，只能根据应用特点进行取舍。

虚拟地址、逻辑地址、线性地址、物理地址的区别

• 虚拟地址是指由程序产生的由段选择符和段内偏移地址组成的地址。这两部分组成的地址并没有直接访问物理内存，而是要通过分段地址的变换处理后才会对应到相应的物理内存地址。
• 逻辑地址指由程序产生的段内偏移地址。有时直接把逻辑地址当成虚拟地址，两者并没有明确的界限。
• 线性地址是指虚拟地址到物理地址变换之间的中间层，是处理器可寻址的内存空间（线性地址空间）中的地址。程序代码会产生逻辑地址，或者说是段中的偏移地址，加上相应段基址就生成了一个线性地址。如果启用了分页机制，那么线性地址可以再经过变换产生物理地址。若是没有采用分页机制，那么线性地址就是物理地址。
• 物理地址是指现在CPU外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果。
• 虚拟地址到物理地址的转化方法是与体系结构相关的，一般有分段与分页两种方式。内存管理单元负责从虚拟地址到物理地址的转化。逻辑地址是段标识+段内偏移量的形式，MMU通过查询段表，可以把逻辑地址转化为线性地址。如果CPU没有开启分页功能，那么线性地址就是物理地址：；如果CPU开启了分页功能，MMU还需要查询页表来将线性地址转化为物理地址：逻辑地址（段表）->线性地址（页表）->物理地址。
• 映射是一种多对一的关系，即不同的逻辑地址可以映射到同一个线性地址上；不同的线性地址也可以映射到同一个物理地址上。而且，同一个线性地址在发生换页以后，也可能被重新装载到另外一个物理地址上，所以这种多对一的映射关系也会随时间发生变化。

进程调度算法

1. 先来先服务(FCFS, First Come First Serve)
2. 短作业优先(SJF, Shortest Job First)
3. 最高优先权调度(Priority Scheduling)
4. 时间片轮转(RR, Round Robin)
5. 多级反馈队列调度(multilevel feedback queue scheduling)

常见的调度算法总结:http://www.jianshu.com/p/6edf8174c1eb

实时调度算法:

1. 最早截至时间优先 EDF
2. 最低松弛度优先 LLF

Cache替换算法

1. 随机算法（RAND）。随机算法就是用随机数发生器产生一个要替换的块号，将该块替换出去，此算法简单，易于实现，但命中率较低。
2. 先进先出（FIFO）算法。是将最先进入Cache的信息块替换出去。比较容易实现，系统开销小，其缺点是可能会把一些需要经常使用的程序块（如循环程序）也作为最早进入Cache的块替换掉，而且没有根据访存的局部性原理，故不能提高Cache的命中率。
3. 近期最少使用（LRU）算法。是将近期最少使用的Cache中的信息块替换出去。虽然比较好地反映了程序局部性规律，但是这种替换方法需要随时记录Cache中各块的使用情况。实现起来比较复杂，系统开销较大。实现有：计数器法、寄存器栈法及硬件逻辑比较对法。
4. 最优替换算法（OPT算法）。理想，实现不现实，用来评价。
5. 近期最少使用算法（LFU算法）。选择近期最少访问的页面作为被替换的页面。既充分利用了主存中页面调度情况的历史信息，又正确反映了程序的局部性。但是，实现非常困难，要为每个页面设置一个很长的计数器。

死锁

原因:

1. 竞争资源
2. 程序推进顺序不当

必要条件:

1. 互斥条件
2. 请求和保持条件
3. 不剥夺条件
4. 环路等待条件

处理死锁基本方法:

1. 预防死锁(摒弃除1以外的条件)
2. 避免死锁(银行家算法)
3. 检测死锁(资源分配图)
4. 解除死锁
   1.剥夺资源
   2.撤销进程

死锁概念处理策略详细介绍:https://wizardforcel.gitbooks.io/wangdaokaoyan-os/content/10.html

边沿触发和水平触发

边缘触发是指每当状态变化时发生一个 io 事件，条件触发是只要满足条件就发生一个 io 事件

并发与并行

并发和并行从宏观上来讲都是同时处理多路请求的概念。但并发和并行又有区别，并行是指两个或者多个事件在同一时刻发生；而并发是指两个或多个事件在同一时间间隔内发生。
在操作系统中，并发是指一个时间段中有几个程序都处于已启动运行到运行完毕之间，且这几个程序都是在同一个处理机上运行，但任一个时刻点上只有一个程序在处理机上运行。

程序编译与链接

推荐: http://www.ruanyifeng.com/blog/2014/11/compiler.html

Bulid过程可以分解为4个步骤:预处理(Prepressing), 编译(Compilation)、汇编(Assembly)、链接(Linking)

以c语言为例:

1 预处理

预编译过程主要处理那些源文件中的以“#”开始的预编译指令，主要处理规则有：

1. 将所有的“#define”删除，并展开所用的宏定义
2. 处理所有条件预编译指令，比如“#if”、“#ifdef”、 “#elif”、“#endif”
3. 处理“#include”预编译指令，将被包含的文件插入到该编译指令的位置，注：此过程是递归进行的
4. 删除所有注释
5. 添加行号和文件名标识，以便于编译时编译器产生调试用的行号信息以及用于编译时产生编译错误或警告时可显示行号
6. 保留所有的#pragma编译器指令。

2 编译

编译过程就是把预处理完的文件进行一系列的词法分析、语法分析、语义分析及优化后生成相应的汇编代码文件。这个过程是整个程序构建的核心部分。

3 汇编

汇编器是将汇编代码转化成机器可以执行的指令，每一条汇编语句几乎都是一条机器指令。经过编译、链接、汇编输出的文件成为目标文件(Object File)

4 链接

链接的主要内容就是把各个模块之间相互引用的部分处理好，使各个模块可以正确的拼接。 链接的主要过程包块 地址和空间的分配（Address and Storage Allocation）、符号决议(Symbol Resolution)和重定位(Relocation)等步骤。

库函数与系统调用的区别

库函数调用是语言或应用程序的一部分，它是高层的，完全运行在用户空间，为程序员提供调用真正的在幕后完成实际事务的系统调用接口。而系统函数是内核提供给应用程序的接口，属于系统的一部分。函数库调用是语言或应用程序的一部分，而系统调用是操作系统的一部分。

库函数调用通常比行内展开的代码慢，因为它需要付出函数调用的开销。但系统调用比库函数调用还要慢很多，因为它需要把上下文环境切换到内核模式。

静态链接和动态链接的区别

• 静态链接是指把要调用的函数或者过程直接链接到可执行文件中，成为可执行文件的一部分。换句话说，函数和过程的代码就在程序的exe文件中，该文件包含了运行时所需的全部代码。静态链接的缺点是当多个程序都调用相同函数时，内存中就会存在这个函数的多个拷贝，这样就浪费了内存资源。
• 动态链接是相对于静态链接而言的，动态链接所调用的函数代码并没有被拷贝到应用程序的可执行文件中去，而是仅仅在其中加入了所调用函数的描述信息（往往是一些重定位信息）。仅当应用程序被装入内存开始运行时，在操作系统的管理下，才在应用程序与相应的动态链接库（dynamic link library，dll）之间建立链接关系。当要执行所调用dll中的函数时，根据链接产生的重定位信息，操作系统才转去执行dll中相应的函数代码。
• 静态链接的执行程序能够在其它同类操作系统的机器上直接运行，而动态链接的执行程序则不可以。

静态链接库与动态链接库有什么区别

• 静态链接库就是使用的.lib文件，库中的代码最后需要链接到可执行文件中去，所以静态链接的可执行文件一般比较大一些。
• 动态链接库是一个包含可有多个程序同时使用的代码和数据的库，它包含函数和数据的模块的集合。程序文件（如.exe文件或.dll文件）在运行时加载这些模块（也即所需的模块映射到调用进程的地址空间）。
• 静态链接库和动态链接库的相同点是它们都实现了代码的共享。不同点是静态链接库.lib中的代码被包含在调用的.exe文件中，该.lib中不能再包含其他动态链接库或者静态链接库了。而动态链接库.dll可以被调用的.exe动态地“引用”和“卸载”，该.dll中可以包含其他动态链接库或者静态链接库。

用户态和核心态的区别

核心态与用户态是操作系统的两种运行级别，它用于区分不同程序的不同权利。核心态就是用户资源多的状态，或者说访问资源多的状态，也称之为特权态。相对来说，用户态就是非特权态，在此种状态下访问的资源将受到限制。如果一个程序运行在特权态，则该程序就可以访问计算机的任何资源，即它的资源访问权限不受限制。如果一个程序运行在用户态，则其资源需求将受到各种限制。
核心态下CPU可执行任何指令，在用户态下CPU只能执行非特权指令。当CPU处于核心态时，可以随意进入用户态；而当CPU处于用户态时，用户从用户态切换到核心只有在系统调用和中断两种情况下发生。一般程序一开始都是运行于用户态，当程序需要使用系统资源时，就必须通过调用软中断进入核心态。
和心态和用户态各有优势：运行在核心态的程序可以访问的资源多，但可靠性、安全性要求高，维护管理都较复杂；用户态程序访问的资源受限，但可靠性、安全性要求低，自然编写维护起来都较简单。一个程序到底应该运行在核心态还是用户态其对资源和效率的需求。

用户栈与内核栈的区别

内核在创建进程的时候，在创建task_struct的同时，会为进程创建相应的堆栈。每个进程会有两个栈，一个用户栈；一个内核栈，存在于内核空间。当进程在用户空间运行时，CPU堆栈指针寄存器里面的内容是用户堆栈地址，使用用户栈；当进程在内核空间时，CPU堆栈指针寄存器里面的内容是内核栈空间地址，使用内核栈。
当进程因为中断或者系统调用而陷入内核态时，进程所使用的堆栈也要从用户栈转到内核栈。进程陷入内核态后，先把用户态堆栈的地址保存在内核栈之中，然后设置堆栈指针寄存器的内容为内核栈的地址，这样就完成了用户栈向内核栈的转换；当进程从内核态恢复到用户态之后时，在内核态之后的最后将保存在内核栈里面的用户栈的地址恢复到堆栈指针寄存器即可。这样就实现了内核栈和用户栈的互转。
那么，知道从内核转到用户态时用户栈的地址是在陷入内核的时候保存在内核栈里面的，但是在陷入内核的时候，如何知道内核栈的地址？关键在进程从用户态转到内核态的时候，进程的内核栈总是空的。这是因为当进程在用户态运行时，使用的是用户栈，当进程陷入到内核态时，内核栈保存进程在内核态运行的相关信息，但是一旦进程返回到用户态后，内核栈中保存的信息无效，会全部恢复，因此每次进程从用户态陷入内核的时候得到的内核栈都是空的，所以在进程陷入内核的时候，直接把内核栈的栈顶地址给堆栈指针寄存器就可以了。