进程的状态：运行、阻塞、就绪三种状态。
运行和就绪之间的转换由调度程序引导；
当进程等待一个外部事件发生时，则由执行→阻塞；
当等待的一个外部事件发生时，则阻塞→就绪；
当没有其他进程运行，则立刻由就绪→执行；否则处于就绪态，等待CPU空闲并轮到它运行。
为什么要引入线程？
进程是资源拥有者。在创建、切换和撤销的操作需要较大的时空开销，限制了并发程度的进一步提高。引入线程将进程作为资源分配单位和资源调度单位这两个属性分开处理。进程任作为资源分配的基本单位；把调度执行和切换的任务交给线程。
令牌：一种高级的线程同步的方法。它既提供锁的安全访问临界资源的功能，又利用了条件变量使得线程争夺临界资源时是有序的。
生产者消费者问题
问题描述：
一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入到缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或者一个消费者从中取出消息。
semaphore mutex=1; //临界区互斥信号量
semaphore empty=n; //空闲缓冲区
semaphore full=0; //缓冲区初始化为空
producer () { //生产者进程
while(1){
produce an item in nextp; //生产数据
P(empty); //获取空缓冲区单元 先对empty信号量操作，再对mutex信号量进行操作！
P(mutex); //进入临界区.
add nextp to buffer; //将数据放入缓冲区
V(mutex); //离开临界区,释放互斥信号量
V(full); //满缓冲区数加1
}
}
consumer () { //消费者进程
while(1){
P(full); //获取满缓冲区单元
P(mutex); // 进入临界区
remove an item from buffer; //从缓冲区中取出数据
V (mutex); //离开临界区，释放互斥信号量
V (empty) ; //空缓冲区数加1
consume the item; //消费数据
}
}一、用户态 内核态的概念
内核态与用户态是操作系统的两种运行级别，intel cpu提供Ring0-Ring3三种级别的运行模式。Ring0级别最高，Ring3最低。其中特权级0（Ring0）是留给操作系统代码，设备驱动程序代码使用的，它们工作于系统核心态；而特权极3（Ring3）则给普通的用户程序使用，它们工作在用户态。
二、为什么要划分用户态与内核态
由于需要限制不同的程序之间的访问能力, 防止他们获取别的程序的内存数据, 或者获取外围设备的数据, 并发送到网络, CPU划分出两个权限等级 – 用户态 和内核态。
用户态: 只能受限的访问内存, 且不允许访问外围设备. 占用CPU的能力被剥夺, CPU资源可以被其他程序获取
内核态: CPU可以访问内存所有数据, 包括外围设备, 例如硬盘, 网卡. CPU也可以将自己从一个程序切换到另一个程序
三、用户态与核心态的区别
处于用户态执行中的进程，其所能访问的内存空间和对象受到限制，其所处于占有的处理机是可被抢占的；
处于核心态执行中的进程，其能访问所有的内存空间和对象，且所占有的处理机是不允许被抢占的。
四、用户态向核心态的转换方式
一、用户栈和内核栈的概念
内核在创建进程的时候，在创建task_struct的同时，会为进程创建相应的堆栈。每个进程会有两个栈，一个用户栈，存在于用户空间；一个内核栈，存在于内核空间。
当进程在用户空间运行时，cpu堆栈指针寄存器里面的内容是用户堆栈地址，使用用户栈；
当进程在内核空间运行时，cpu堆栈指针寄存器里面的内容是内核栈空间地址，使用内核栈。
二、用户栈和内核栈的区别
三、设置用户栈和内核栈的原因
一、池的概念
由于服务器的硬件资源“充裕”，那么提高服务器性能的一个很直接的方法就是以空间换时间，即“浪费”服务器的硬件资源，以换取其运行效率。这就是池的概念。池是一组资源的集合，这组资源在服务器启动之初就完全被创建并初始化，这称为静态资源分配。当服务器进入正是运行阶段，即开始处理客户请求的时候，如果它需要相关的资源，就可以直接从池中获取，无需动态分配。很显然，直接从池中取得所需资源比动态分配资源的速度要快得多，因为分配系统资源的系统调用都是很耗时的。当服务器处理完一个客户连接后，可以把相关的资源放回池中，无需执行系统调用来释放资源。从最终效果来看，池相当于服务器管理系统资源的应用设施，它避免了服务器对内核的频繁访问。
池可以分为多种，常见的有内存池、进程池、线程池和连接池。
二、内存池
c++内存分配优先使用内存池，而不是new，delete。
new和delete首先会转调用到malloc和free，这个大家应该很熟识了。很多人认为malloc是一个很简单的操作，其实巨复杂，它会执行一个系统调用(当然不是每一次，windows上是按页算)，该系统调用会锁住内存硬件，然后通过链表的方式查找空闲内存，如果找到大小合适的，就把用户的进程地址映射到内存硬件地址中，然后释放锁，返回给进程。如果在多线程环境下，进程内的分配也会上锁，跟上面类似，不过不是以页，而是以分配的内存为单位。
内存池就是预先分配好，放到进程空间的内存块，用户申请与释放内存其实都是在进程内进行，SGI-STL的alloc遇到小对象时就是基于内存池的。只有当内存池空间不够时，才会再从系统找一块很大的内存。 所以使用内存池提升了内存分配与回收的效率。
三、进程池与线程池
进程池和线程池相似，所以这里我们以进程池为例进行介绍。如没有特殊声明，下面对进程池的讨论完全是用于线程池。
进程池是由服务器预先创建的一组子进程，这些子进程的数目在3~10个之间（当然这只是典型情况）。线程池中的线程数量应该和CPU数量差不多。进程池中的所有子进程都运行着相同的代码，并具有相同的属性，比如优先级、PGID等。当有新的任务来到时，主进程将通过某种方式选择进程池中的某一个子进程来为之服务（如使用随机算法或轮转法来挑选一个子进程）。当选择好子进程后，主进程还需要使用某种通知机制来告诉目标子进程有新任务需要处理，并传递必要的数据。最简单的方式是，在父进程和子进程之间预先建立好一条管道，然后通过管道来实现所有的进程间通信。在父线程和子线程之间传递数据就要简单得多，因为我们可以把这些数据定义为全局，那么它们本身就是被所有线程共享的。
综上所述，进程池的一般模型如下所示：
死锁指的是多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。
导致死锁的原因：
一、预防死锁
死锁的预防是通过破坏产生条件来阻止死锁的产生，但这种方法破坏了系统的并行性和并发性。
死锁产生的前三个条件是死锁产生的必要条件，也就是说要产生死锁必须具备的条件，而不是存在这3个条件就一定产生死锁，那么只要在逻辑上回避了第四个条件就可以避免死锁。
二、避免死锁
避免死锁采用的是允许前三个条件存在，但通过合理的资源分配算法来确保永远不会形成环形等待的封闭进程链，从而避免死锁。该方法支持多个进程的并行执行，为了避免死锁，系统动态的确定是否分配一个资源给请求的进程。
常用的避免死锁的方法：
有序资源分配法：
这种算法资源按某种规则系统中的所有资源统一编号（例如打印机为1、磁带机为2、磁盘为3、等等），申请时必须以上升的次序。
系统要求申请进程：
（1）对它所必须使用的而且属于同一类的所有资源，必须一次申请完；
（2）在申请不同类资源时，必须按各类设备的编号依次申请。
例如：
进程PA，使用资源的顺序是R1，R2； 进程PB，使用资源的顺序是R2，R1；
若采用动态分配有可能形成环路条件，造成死锁。
采用有序资源分配法：R1的编号为1，R2的编号为2；
PA：申请次序应是：R1，R2 ； PB：申请次序应是：R1，R2
这样就破坏了环路条件，避免了死锁的发生。
银行家算法
基本思想：分配资源之前，判断系统是否是安全的；若是，才分配。每分配一次资源就测试一次是否安全。
我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全，银行家规定：
（1）当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客(试探性分配)。
（2）顾客可以分期贷款，但贷款的总数不能超过最大需求量(可能一次并不能满足所需要的全部资源)。
（3）当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款(不存在死锁)。
（4）当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金(运行后释放)。
本算法在理论上是出色的，能非常有效地避免死锁，但从某种意义上说，它缺乏实用价值，因为很少有进程能够在运行前就知道其所需资源的最大值，且进程数也不是固定的，往往在不断地变化（如新用户登录或退出），况且原来可用的资源也可能突然间变成不可用（如打印机、磁带机可能被损坏）。
内存管理方式：块式、页式、段式、段页式
物理内存：即实际内存，实存储器。
虚拟内存：用硬盘空间做内存来弥补计算机RAM空间的缺乏。
虚拟内存好处：内存中可以保留多个进程，进程可以比内存的全部空间还大
连续分配方式，是指为一个用户程序分配一个连续的内存空间。它主要包括单一连续分配、固定分区分配和动态分区分配。
一、分别编译与链接（Linking）
大多数高级语言都支持分别编译，程序员可以显式地把程序划分为独立的模块或文件，然后每个独立部分分别编译。在编译之后，由链接器把这些独立的片段（称为编译单元）“粘接到一起”。好处是降低了各部分模块的耦合度。
在C/C++中，这些独立的编译单元包括obj文件（一般的源程序编译而成）、lib文件（静态链接的函数库）、dll文件（动态链接的函数库）等。
静态链接方式：在程序执行之前完成所有的组装工作，生成一个可执行的目标文件（EXE文件）。
动态链接方式：在程序已经为了执行被装入内存之后完成链接工作，并且在内存中一般只保留该编译单元的一份拷贝。
二、静态链接库(LIB)与动态链接库(DLL)
先来阐述一下DLL(Dynamic Linkable Library)的概念，你可以简单的把DLL看成一种仓库，它提供给你一些可以直接拿来用的变量、函数或类。
静态链接库与动态链接库都是共享代码的方式，如果采用静态链接库，则无论你愿不愿意，lib中的指令都被直接包含在最终生成的EXE文件中了。但是若使用DLL，该DLL不必被包含在最终的EXE文件中，EXE文件执行时可以“动态”地引用和卸载这个与EXE独立的DLL文件。
静态链接库的优点：
（1）代码装载速度快；
（2）只需保证在开发者的计算机中有正确的.LIB文件，在以二进制形式发布程序时不需考虑在用户的计算机上.LIB文件是否存在及版本问题，可避免DLL地狱等问题。
动态链接库的优点：
（1）更加节省内存；
（2）DLL文件与EXE文件独立，只要输出接口不变，更换DLL文件不会对EXE文件造成任何影响，因而极大地提高了可维护性和可扩展性。
静态和动态链接
三、认识动态链接库
动态链接是相对于静态链接而言的。所谓静态链接是指把要调用的函数或者过程链接到可执行文件中，成为可执行文件的一部分。换句话说，函数和过程的代码就在程序的exe文件中，该文件包含了运行时所需的全部代码。当多个程序都调用相同函数时，内存中就会存在这个函数的多个拷贝，这样就浪费了宝贵的内存资源。而动态链接所调用的函数代码并没有被拷贝到应用程序的可执行文件中去，而是仅仅在其中加入了所调用函数的描述信息（往往是一些重定位信息）。仅当应用程序被装入内存开始运行时，在Windows的管理下，才在应用程序与相应的DLL之间建立链接关系。当要执行所调用DLL中的函数时，根据链接产生的重定位信息，Windows才转去执行DLL中相应的函数代码。一般情况下，如果一个应用程序使用了动态链接库，Win32系统保证内存中只有DLL的一份复制品
动态链接库的两种链接方法：
(1) 装载时动态链接(Load-time Dynamic Linking)：这种用法的前提是在编译之前已经明确知道要调用DLL中的哪几个函数，编译时在目标文件中只保留必要的链接信息，而不含DLL函数的代码；当程序执行时，调用函数的时候利用链接信息加载DLL函数代码并在内存中将其链接入调用程序的执行空间中(全部函数加载进内存），其主要目的是便于代码共享。（动态加载程序，处在加载阶段，主要为了共享代码，共享代码内存）
(2) 运行时动态链接(Run-time Dynamic Linking)：这种方式是指在编译之前并不知道将会调用哪些DLL函数，完全是在运行过程中根据需要决定应调用哪个函数，将其加载到内存中（只加载调用的函数进内存），并标识内存地址，其他程序也可以使用该程序，并用LoadLibrary和GetProcAddress动态获得DLL函数的入口地址。（dll在内存中只存在一份，处在运行阶段）
上述的区别主要在于阶段不同，编译器是否知道进程要调用的dll函数。动态加载在编译时知道所调用的函数，而在运行态时则必须不知道。
基本分页的特征：
(1)一次性：将作业全部装入内存后方能运行，浪费空间。
(2)驻留性：作业装入内存后，便一直驻留在内存中，直至作业运行结束。
请求分页原理：
(1)在进程开始运行之前，仅装入当前要执行的部分页面即可运行；
(2)在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的页面；
(3)当内存空间已满，而又需要装入新的页面时，者根据置换功能适当调出某个页面，以便腾出空间而装入新的页面。
(4)为实现请求分页，需要一定的硬件支持，包括：页表机制、缺页中断机构、地址变换机构。
基本分段的特征：一次性、驻留性;
按照用户进程中的自然段划分逻辑空间，段内要求连续，段间不要求连续，整个作业的地址空间是二维的。逻辑地址由段号S与段内偏移量W两部分组成。
分页和分段的主要区别
段是信息的逻辑单位，用户可见，长度可变
页是信息的物理单位，用户透明，长度固定
段式：若干独立的逻辑空间构成进程的非连续逻辑空间，二维地址空间
页式：一维地址空间
段式：物理空间不连续，但段内连续
页式：物理空间不连续
1.最佳置换算法(OPT)
最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。
2.先进先出(FIFO)页面置换算法
优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。
3.最近最久未使用(LRU)置换算法
选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。
4.时钟(CLOCK)置换算法
LRU算法的性能接近于OPT,但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体。
简单的CLOCK算法是给每一帧关联一个附加位，称为使用位。当某一页首次装入主存时，该帧的使用位设置为1;当该页随后再被访问到时，它的使用位也被置为1。对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为最近未用(Not Recently Used, NRU)算法。
CLOCK算法的性能比较接近LRU，而通过增加使用的位数目，可以使得CLOCK算法更加高效。在使用位的基础上再增加一个修改位，则得到改进型的CLOCK置换算法。这样，每一帧都处于以下四种情况之一：
最近未被访问，也未被修改(u=0, m=0)。
最近被访问，但未被修改(u=1, m=0)。
最近未被访问，但被修改(u=0, m=1)。
最近被访问，被修改(u=1, m=1)。
算法执行如下操作步骤：
1)从指针的当前位置开始，扫描帧缓冲区。在这次扫描过程中，对使用位不做任何修改。选择遇到的第一个帧(u=0, m=0)用于替换。
2)如果第1)步失败，则重新扫描，查找(u=0, m=1)的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中，对每个跳过的帧，把它的使用位设置成0。
3)如果第2)步失败，指针将回到它的最初位置，并且集合中所有帧的使用位均为0。重复第1步，并且如果有必要，重复第2步。这样将可以找到供替换的帧。
改进型的CLOCK算法优于简单CLOCK算法之处在于替换时首选没有变化的页。由于修改过的页在被替换之前必须写回，因而这样做会节省时间。
基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。
之所以将其称为虚拟存储器，是因为这种存储器实际上并不存在，只是由于系统提供了部分装入、请求调入和置换功能后（对用户完全透明），给用户的感觉是好像存在一个比实际物理内存大得多的存储器。虚拟存储器的大小由计算机的地址结构决定，并非是内存和外存的简单相加。虚拟存储器有以下三个主要特征：
1. 多次性，是指无需在作业运行时一次性地全部装入内存，而是允许被分成多次调入内存运行。
2. 对换性，是指无需在作业运行时一直常驻内存，而是允许在作业的运行过程中，进行换进和换出。
3. 虚拟性，是指从逻辑上扩充内存的容量，使用户所看到的内存容量，远大于实际的内存容量。
实现方式：
1. 请求分页存储管理。
2. 请求分段存储管理。
3. 请求段页式存储管理。
操作系统的4个特征是并发性、共享性、虚拟性和不确定性。
并发性（concurrency）：指在计算机系统中存在着许多并发执行的活动。对计算机系统而言，并发是指宏观上看系统内有多道程序同时运行，微观上看是串行运行。因为在大多数计算机系统中一般只有一个CPU，在任意时刻只能有一道程序占用CPU。
共享性（sharing）：系统中各个并发活动要共享计算机系统中的各种软、硬件资源，因此操作系统必须解决在多道程序间合理地分配和使用资源问题。
虚拟性（virtual）：虚拟是操作系统中的重要特征，所谓虚拟是指把物理上的一台设备变成逻辑上的多台设备。例如，在操作系统中采用了spooling技术，可以利用快速、大容量可共享的磁盘作为中介，模拟多个非共享的低速的输入输出设备，这样的设备称为虚拟设备。
异步性（Asynchronism)：多道程序环境下程序的执行，是以异步方式进行的；是操作系统的一个重要特征。换言之，每个程序在何时执行，多个程序间的执行顺序以及完成每道程序所需的时间都是不确定的，因而也是不可预知的。
操作系统的五大管理功能是进程管理、文件管理、存储管理、设备管理和作业管理。
Direct Memory Access（存储器直接访问）：这是指一种高速的数据传输操作，允许在外部设备和存储器之间直接读写数据，既不通过CPU，也不需要CPU干预。整个数据传输操作在一个称为”DMA控制器”的控制下进行的。CPU除了在数据传输开始和结束时做一点处理外，在传输过程中CPU可以进行其他的工作。这样，在大部分时间里，CPU和输入输出都处于并行操作。因此，使整个计算机系统的效率大大提高。
目的：让设备可以绕过CPU，直接读写系统内存
原理：在一段时间内，由DMA控制器取代CPU，获得总线控制权，从而实现内存与外设或者内存不同区域间的大量数据快速传递
特点：允许不同速度的硬件装置来沟通，不需要依于 CPU 的大量中断负载
外设向DMA控制器请求→DMA控制器向CPU请求→DMA控制器获得总线→传输数据→字节计数器为0时DMA结束→返还总线给CPU
为了缓和CPU的高速性与I/O设备低速性之间的矛盾而引入了脱机输入/输出技术。该 技术是利用专门的外围控制机，将低速I/O设备上的数据传送到高速磁盘上；或者相反。 Spooling的意思是外部设备同时联机操作，又称为假脱机输入/输出操作，是操作系统中釆用的一项将独占设备改造成共享设备的技术。
目的：为了缓和CPU的高速性与I/O设备低速性之间的矛盾
原理：利用专门的外围控制机，将低速I/O设备上的数据传送到高速磁盘上；或者相反。
特点：提高了 I/O的速度；将独占设备改造为共享设备；实现了虚拟设备功能。
输入设备→输入缓冲区→输入井→内存→输出井→输出缓冲区→输出设备
外存分配方式主要有这几种：连续分配，链式分配，索引分配。
一. 连续分配
原理：创建文件时，分配一组连续的块；FAT（文档分配表）中每个文件只要一项，说明起始块和文件长度。对于顺序文件有利。
优点：1.简便。适用于一次性写入操作。2.支持顺序存取和随机存取，顺序存取速度快。3.所需的磁盘寻道次数和寻道时间最少。（因为空间的连续性，当访问下一个磁盘块时，一般无需移动磁头，当需要移动磁头时，只需要移动一个磁道。）
缺点：1.文件不能动态增长。（可能文件末尾处的空块已经分配给了别的文件。）2.不利于文件的插入和删除。3.外部碎片问题。（反复增删文件后，很难找到空间大小足够的连续块，需要进行紧缩。）4.在创建文件时需生命文件大小。
如图：
二. 链式分配
原理：一个文件的信息存放在若干个不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。fat中每个文件同样只需要一项，包括文件名、起始块号和最后块号。任何一个自由块都可以加入到链中。
优点：1.提高磁盘的空间利用率，不存在外部碎片问题。2.有利于文件的插入和删除。3.有利于文件的动态扩充。
缺点：1.存取速度慢，一般只适用于信息的顺序存取，不适于随机存取。2.查找某一块必须从头到尾沿着指针进行。3.可靠性问题，如指针出错。4.更多的寻道次数和寻道时间。5.链接指针占一定的空间，将多个块组成簇，按簇进行分配而不是按块进行分配。（增加了磁盘碎片）
如图：
使用FAT文件分配表法，链接分配的变种，如MS-DOS 和 OS/2.
三. 索引分配
原理：每个文件在FAT中有一个一级索引，索引包含分配给文件的每个分区的入口。文件的索引保存在单独的一个块中，FAT中该文件的入口指向这一块。
优点：1.保持了链接结构的优点，又解决了其缺点：按快分配可以消除外部碎片。按大小可改变的分区分配可以提高局部性。索引分配支持顺序访问文件和直接访问文件，是普遍采用的一种方式。2.满足了文件动态增长，插入删除的要求。（只要有空闲块）3.能充分利用外存空间。
缺点：1.较多的寻道次数和寻道空间。2.索引表本身带来了系统开销，如：内外存空间、存取时间。
