概述
- 相对路径--相对于进程的工作目录。
- windows中不存在父子进程层次，创建\被创者身份平等。
- 被并发的进程共享的资源可以是互斥\同时共享，互斥共享的资源称为临界资源。
- 并发--一段时间内多个任务被轮流处理，切换很快，单核处理器，并行--某一时刻多个任务，多核或多个处理器支持。
- 虚拟技术：时分\空分复用
- 异步IO：系统调用后，调用者不阻塞进程，而是立马返回，系统调用完成后，通过状态、通知、回调来通知调用者。并发时的异步：走走停停，以不可知的速度向前推进。
- 操作系统功能：1.自上为用户程序提供抽象接口，自下管理物理硬件2.管理计算机资源(对用户程序透明)3.可以说运行在内核态的程序就叫操作系统。
体现在进程(通信、控制)\内存地址空间分配\文件\设备管理
- 进程在用户态需要内核态的功能，就进行系统调用陷入内核，由操作系统代为完成。
系统调用和库函数调用
系统中的共享资源都由OS内核统一管理，保证系统的稳定性和安全性，防止用户随意修改系统重要数据。系统调用就是操作系统所提供的在用户程序中可以调用的接口，运行在内核态，在用户程序中，凡是与资源有关的操作（按照功能可分为：内存分配、进行I/O设备传输、管理文件、进程控制、进程通信）都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代替它完成。通常，一个操作系统提供的系统调用有几十个乃至上百个之多。
库函数是将常用的代码块编写放入文件中，形成可重用的模块，编写应用程序时调用，由第三方提供，运行在用户态/用户地址空间。
在移植性方面，不同操作系统的系统调用一般是不同的，移植性差；库函数移植性相对好一点。比如说在所有的ANSI C编译器版本中，C库函数是相同的。调用开销方面，系统调用需要在用户态和内核态切换CPU上下文环境，开销较大，库函数调用开销较小。
另一种OS提供的含有系统调用的库函数一般是对多个系统调用的封装，方便了用户程序的调用，可以实现更多的功能。用户程序一般是调用它间接使用系统调用，用C定义接口，如与对应系统调用重名的read()读磁盘上文件。
调用的过程是将库函数参数压到栈上，然后执行到函数内的系统调用，OS将它的唯一编号放入寄存器，然后执行指令trap(执行int $0x80)产生中断进入内核，OS查询中断向量表，调用对应中断的服务程序，服务程序将系统调用编号拿出来，对照操作系统一直维护的系统调用表，找到该系统调用程序体的内存地址，访问该地址，执行系统调用。执行完毕后返回库函数，库函数负责检查系统调用的执行情况，根据检查的结果返回相应的值。
这里trap指令产生一个陷入中断并且是软中断(软件发出，不会直接中断CPU)，系统调用可当做一个中断处理函数，靠中断机制切换到内核模式来进行调用。
库函数一般可以概括的分为两类，一类是随着操作系统提供的，另一类是由第三方提供的。系统提供的库函数把系统调用进行封装或者组合，可以实现更多的功能，也就是上面写的内嵌系统调用的库函数，这样的库函数能够实现一些对内核来说比较复杂的操作。比如，read()函数根据参数，直接就能读文件，而背后隐藏的比如文件在硬盘的哪个磁道，哪个扇区，加载到内存的哪个位置等等这些包含了系统调用的操作，程序员是不必关心的。而对于第三方的库，它其实和系统库一样，只是它直接利用系统调用的可能性要小一些，而是利用系统库函数来实现功能。
- 大内核(单体系统)：系统全部功能如文件系统、设备驱动都放进内核，整个操作系统以功能模块的方式编写，链接成一个大型可执行二进制程序，在内核态以单一程序的方式运行，各模块共享信息，性能高，但拓展性差，拓展功能代码需要与内核代码重新编译。
微内核：在微内核结构下，将一部分操作系统功能模块移出内核，只有最核心的功能在内核中，如IPC、地址空间分配，其余模块(即服务，如文件系统、设备驱动)运行在用户态。需要频繁切换性能低，但扩展性好，且不容易因一个功能错误导致系统崩溃(所以只在高可靠性要求场景如军事、工业、航空中流行)。
中断分为外中断(一般就是我们说的中断，由cpu执行指令以外的事件引起，如 I/O 完成中断)、异常(内中断，由 CPU 执行指令的内部事件引起，如操作地址越界。)、陷入trap(软中断，在用户程序中使用系统调用引起)。
中断由外因引起，异常由CPU本身原因引起。
中断发生后处理步骤一般是：1.保存CPU环境。2.查询中断向量表。3.调用中断处理服务函数。4.恢复CPU环境。
10. 通常计算机采用的是分时系统，就是系统把CPU时间分成很短的时间片分配给多个进程，让它们轮流共享CPU，各进程占用cpu的时间并非严格限定，如果一个进程需要，可以给它分配更多的时间片，优点是有较强的交互性、多作业并发提高资源利用率。而实时操作系统，计算机及时响应外部事件请求（低优先级任务会被高优先级直接挂起），事件处理必须遵从严格的时间限制与执行顺序，超过时限的进程可能直接被终止，优点是可靠性安全性相对更高，但交互性略差。
进程管理
- 进程是资源分配和拥有的基本单位，一个进程就是一个正在执行程序的实例，进程有自己的程序(即指令)、虚拟地址空间、PCB表项、IO设备、输入、输出、运行状态。
比如说用户运行自己的程序，系统就创建一个进程，并为它分配虚拟内存空间(虚拟地址空间,包括堆栈指针的指向)、一个控制线程(主线程)、IO设备。PCB描述基本信息和运行状态。该进程放人进程的就绪队列。进程调度程序选中它，为它分配CPU该进程才真正运行。
进程切换时先要从用户态切换到内核态，保存当前进程的状态(三态)，cpu上下文环境(拥有自己的虚拟cpu，切换进程时老的存入内存，新的装入cpu,一般装的都是PCB里的东西)，程序的内存映像，程序计数器（保存下一条指令的地址），设置新进程的cpu环境和内存映像，然后切换到用户态，进程切换次数太多降低cpu效率，调度算法需要注意。
进程有cpu密集型\IO密集型，要尽快让IO密集型获取cpu，来保持磁盘的忙碌。
- OS维护着一张进程表(进程控制块PCB)，描述进程基本信息(其中有各态转换需要保存的信息，从而保证运行时IO中断导致的阻塞结束后能再次就绪)和运行状态，创建、撤销进程都需要对PCB操作。
- 进程从开始到结束的完整过程(四个)①创建进程、申请空PCB填信息、分配资源、进入就绪态②调度程序的时间片到来，跳转到运行态，用完了继续就绪③请求资源如IO则进入阻塞态等待资源，得到资源时转为就绪态④运行完毕后回收资源、PCB。
- 守护进程是一个在后台运行并且不受任何终端控制的特殊进程，用于执行特定的系统任务(如处理打印、web页面、电子邮件)，很多守护进程在系统引导的时候启动，并且一直运行直到系统关闭。
- 进程可能在启动系统、运行的程序(父进程)用系统调用创建、用户请求时被创建，但本质上都是存在的进程创建新进程(如unix中所有进程都属于出现在启动映像中的特殊进程init为根的一颗树)。fork()创建的子进程一开始内存映像和父一样，随后一般执行一个execve()修改并运行新程序，但win中开始就不一样。
- 进程可能正常退出、出错退出、被其他进程杀死。
7. 线程是CPU调度和分配的基本单位，也是操作系统独立调度的最小单位，是指进程内的一个执行单元，进程中可以有多个线程，共享进程资源(地址空间与全局变量(即内存空间)、打开文件(即IO设备))。比如浏览器有HTTP 请求线程、事件响应线程、渲染线程等等，使得浏览器可以响应用户事件的同时处理http连接。各个线程共享堆区，而进程中的线程各自维持自己的栈。主线程用于创建和销毁其他线程。
进程与线程的不同：
1.拥有资源(进程是资源分配的基本单位，而进程不拥有资源，访问属于进程的资源)
2.调度(同一进程中线程切换，不会引起进程切换，不同就会引起)
3.系统开销(切换与创建销毁分配回收资源主要是IO设备、内存，开销远大于创建或销毁线程，切换时进程需要保存和设置CPU环境、内存映像，线程仅需保存和设置少量寄存器开销很小)
4.通信手段(线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。)。相同：均可并发执行，实现程序的并发运行。
线程分类：
1.用户级线程有关线程管理的所有工作都由应用程序调用线程库完成，内核意识不到线程的存在，不用陷入，高效，但一个线程阻塞其他都阻塞，并发效率低。
2.内核级线程线程管理的所有工作由内核完成，程序只能用系统调用让内核代为管理，并发性高，但需要陷入内核。
优劣比较：线程的切换开销小于进程，使得多线程程序的并发性高。
多个线程共享内存，从而极大地提高了程序的运行效率和CPU利用率。
- 进程状态：运行态\就绪态(等待调度)\阻塞态(等待资源)，其中1->2与2->1由进程调度程序(算法)引起，许多适用于进程的调度算法也适用于线程。
- 为什么需要线程？应用程序进程可分解为多个可以并发运行实现的任务，每个线程完成应用程序中的一个任务，提高并发性。并发实体可以有共同的地址空间和可用数据(进程无法办到)，极大提高程序运行效率。轻量级，开销少，创建销毁速度快。每个线程也有三态，进程内有些执行部分进行IO时可以用三态在多线程间切换(切换时间短易于调度)，增加cpu利用率，加快程序运行。
例如：服务器通常接收大量且不确定数量用户的并发请求，为每一个请求创建一个线程而不是进程。
8. 进程可以创建2048个线程，因为用户空间2G，线程栈1MB。
- 如果一个子进程运行结束了(此时多数资源已被回收，进程描述符和pcb中有返回信息所以需要父进程来回收)，它的父进程没有调用wait来获取它的返回信息，回收它在内核中pcb信息，导致内核空间和进程描述符的浪费，这个子进程就变成了僵尸进程,将因为没有可用的进程号而导致系统不能产生新的进程,要消灭系统中大量的僵尸进程，只需要将其父进程杀死，此时僵尸进程就会变成孤儿进程，从而被init进程所收养释放。如果子进程还在运行，而他的父进程已经退出了，没有父进程去获取它的退出状态了，这个子进程就变了孤儿进程，但会被init进程收养，退出的时候就有init进程来为其完成状态收集工作。
- 不同环境的调度算法目标不同，因此需要针对不同系统来讨论调度算法，但所有都需要公平、平衡(让系统所有部分保持忙碌)。进程调度算法分为1.批处理系统(保证吞吐量、周转时间、cpu利用率(减少进程切换))2.交互式系统(响应时间、均衡性(满足用户期望))3.实时系统(保证在一定时间限制内完成特定功能的操作系统，要满足截止时间避免数据丢失)。
- 进程调度算法①批处理系统：1.先来先服务(非抢占，利于计算密集型，不利于IO密集型进程)2.短作业优先(非抢占，计算密集型容易饥饿)3.最短剩余时间优先(前一个的抢占版本，新的短作业得到良好的服务) ②交互式系统：1.时间片轮转调度(就绪进程按 FCFS 的原则排成一个队列，依次分配时间片，时间片太小，进程切太频繁，时间片太大，实时性无法保证，IO密集小时间片即可，计算密集需要大时间片)2.优先级调度(为进程分配优先级(IO密集需要高优先)，按优先级调度，随着时间推移增加等待进程的优先级)3.多级反馈队列(时间片轮转调度算法和优先级调度算法的结合，用完第一队列的时间片就转到第二队列末尾，让IO密集型获得了高优先和小时间片，计算密集从高优先小时间片到适合计算密集的低优先大时间片，兼顾两种进程) ③实时系统：分为硬实时(必须满足截止时间)和软实时(容忍一定的超时)。
- 同步：多个进程按一定次序执行一项任务，避免共享资源冲突或进程间信息不一致。比如生产消费者问题，同时操作共享资源，导致wakeup丢失，最后都睡眠产生死锁，同步实现一般是睡眠(等待)与唤醒。互斥：只有一个进程进入临界区。
进程同步
①临界区是对临界资源进行访问的那段代码，为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查，如有占用就不能访问。
②共享锁变量如，互斥量(一种信号量，信号量特点是其他进程休眠等待被唤醒)、自旋锁(进程会忙等待，占用CPU，所以适用于锁使用者保持锁时间比较短的情况))。
③信号量是一个整型变量，可以对其执行down(如果信号量大于 0 ，执行 -1 操作，并获取资源；如果信号量等于 0，进程睡眠，等待信号量大于 0)和up(对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作)操作，也就是常见的P和V。down 和 up 操作需要被设计成原子操作，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。如果信号量的取值只能为0或者1，那么就成为了互斥量（互斥锁mutex），设置为1，进入临界区前down，退出时up，0表示临界区已经加锁，1表示临界区解锁。
③用信号量解决生产消费者中wakeup丢失问题,设置三个信号量full、empty、mutex(这退化为了互斥量)，生产者这边down(&empty);down(&mutex);insert_item(item);up(&mutex); up(&full);消费者这边down(&full);down(&mutex); int item = remove_item(); consume_item(item); up(&mutex); up(&empty); 用full与empty为了让两者能休眠
④管程，用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把表示共享资源的数据结构还有相关的同步操作都集中封装到一起，使得客户端代码调用更方便。进程只能通过管程间接访问临界资源，在一个时刻只能有一个进程使用管程，能有效地完成互斥。管程引入了条件变量以及相关的操作：wait()和signal()来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有，signal() 操作用于唤醒被阻塞于条件变量的进程。
⑤经典同步(因为同步要通过进程间通信(传输信息)实现，所以也叫进程间通信IPC)问题
1.生产消费者已说，是一个有界缓冲区模型场景。
2.读者写者问题：允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生，为数据库访问建立了一个模型。一个整型变量 count记录在对数据进行读操作的进程数量，一个互斥量count_mutex用于对count加锁，一个互斥量data_mutex 用于第一个读者对读写的数据加锁，具体去cyc或书。
3.哲学家进餐问题：五个哲学家，当一个哲学家吃饭时，一次只能拿起一根筷子，为互斥访问有限资源的竞争问题(如IO设备)一类问题建模，如果不进行同步则可能一个人拿一只筷子造成死锁。
15. 进程间通信，同步是某一种目的，通信是手段，勿混淆。
线程间通信：互斥锁、信号量、事件(事件为0则阻塞，一个线程如果将一个 event 对象的信号标志设置为真，它将唤醒所有等待这个 event 对象的线程)
①管道实质是一个内核缓冲区，进程以先进先出的方式从缓冲区存取数据，通过调用 pipe 函数创建，管道fd[0]端用于读，fd[1]端用于写，只支持半双工通信(单向交替传输);只能在父子进程中使用。
②FIFO也称为命名管道，以FIFO文件的形式存在于文件系统中，去除了管道只能在父子进程中使用的限制，常用于客户-服务器应用程序中，FIFO 用作多个客户写数据的汇聚点，服务器则读取请求。可以选择以读或写的方式打开，但如果只有一种方式打开则会阻塞(如只有读)，如果两个进程想做读操作也会阻塞其中一个。
③消息队列是消息的链表，允许进程独立于其他进程向队列写入或者读取数据块(消息)，每个消息都有一个类型，所以可利用它将一个数据块发到另一个进程。相比于FIFO具有以下优点：可以独立于读写进程存在，进程终止时不会被删除，从而避免了在同步命名管道的打开和关闭时可能产生的困难(如如果只有写进程则此进程write()会被阻塞，不能直接写，直到有读进程)；通过发送消息，避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法；读进程可以根据消息类型有选择地随机查询并接收消息，而不像 FIFO 只能先进先出。
缺点：和管道、FIFO一样，每个数据块有一个最大长度的限制，队列所包含的全部数据块的总长度也有一个上限。
④信号量是一个整型变量，用于同步多个进程对共享资源的访问。
⑤共享存储允许多个进程共享一个物理内存，通过(linux是mmap函数)将处在物理内存的同一个文件映射到它们的虚拟地址空间。需要使用信号量用来同步对共享存储的访问。因为数据不需要在进程之间复制，不再通过执行任何进入内核的系统调用来传递彼此的数据,所以这是最快的一种IPC。
⑥套接字与其它通信机制不同的是，它可用于不同主机间的进程通信。
16. 协程
协程是一种单线程工作的机制(保证不会线程切换)，一个线程可以有多个协程，用户创建协程，然后每个协程都是循环按照指定的任务清单顺序完成任务，当任务被阻塞(如IO)的时候执行到另一个协程的任务(如果是此线程执行任务则会阻塞，这样一来调度与切换线程又会费时)，当恢复的时候再回来执行这个任务，只需要在用户态进行任务之间的切换，这样就完全没有反复调用进、线程切换系统调用的开销，切换非常快。
协程的调度完全由用户控制，操作系统内核对协程一无所知，通过插入相关的代码使得代码段能够实现分段式的执行，由特定语言的编译器如python实现它的机制。
可以看到，协程适合用在IO密集型项目，比如Web后台，每个用户来了都要读数据库，我们为每个用户提供一个服务线程，但IO数据库时需要阻塞线程然后进行线程切换，这时候为每个请求分配一个协程就非常快了。因其是单线程模式，故采用多进程+协程的方式，充分利用CPU多核的计算处理能力。
死锁
- 死锁定义：如果一个进程集合中的每个进程都在挂起等待只能由该进程集合中的其他进程才能引发的事件(如释放占有的资源,这叫资源死锁)，那么就发生了死锁，这个进程集合就是死锁集合。
- 死锁的条件：①互斥：每个资源要么已经分配给了一个进程，要么就是可用的。②占有和等待：已经得到了某个资源的进程可以再请求新的资源。③不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。④环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。
- 处理方法：
①鸵鸟策略：把头埋在沙子里，假装根本没发生问题。
解决死锁问题的性能代价很高，不采取任何措施的方案会使系统获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。大多数操作系统，包括Unix，Linux和Windows，处理死锁问题的办法仅仅是忽略它。
②死锁检测与死锁恢复
此后都假设最坏的情况，即每个进程只有在结束时才释放所有资源。每种类型一个资源的死锁检测用资源分配图实现，资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。从一个节点出发进行深度优先搜索(会回溯的那种)，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。
每种类型多个资源的死锁检测用资源向量E，可用资源向量A，当前分配矩阵C(每个进程占一行)，请求矩阵R实现。结束时，任何没有被标记的进程是死锁进程。1.寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。2.如果找到了这样一个进程，那么将C矩阵的第i行向量加到A中，标记该进程，并转回1。3.如果没有这样一个进程，算法终止。
死锁恢复：利用抢占恢复(强行挂起)。利用回滚恢复(将某进程用检查点文件回滚到还没有请求死锁资源，将资源分配给死锁进程)。通过杀死死锁进程恢复(并非总是安全的)。
③死锁预防：实际中操作系统一般用死锁预防来防止死锁
1.破坏互斥条件：例如假脱机打印技术允许若干个进程同时访问资源，唯一真正请求物理打印机的进程是打印机守护进程，该进程不会请求任何其他资源，所以不会死锁。
2.破坏占有和等待条件：一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。
3.破坏不可抢占条件
4.破坏环路等待条件：给资源统一编号，进程只能按照编号顺序请求资源，但几乎找不出令人满意的编号次序
④死锁避免：程序运行时避免发生死锁。死锁避免本质上一般不可能，因为需要获取未来请求，这些请求一般不可知。
1.安全状态与不安全状态：即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的，相反则不安全。
2.单种资源的银行家算法：通过维护一个表，每行是一个进程的已有资源和最大需求，先全部分配给最小的最大需求，等待它结束释放，如果从安全状态开始的话，所有进程都能通过此方法顺利运行。判断每请求之后是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。
3.多种资源的银行家算法：已经分配的资源矩阵，左边的图表示还将需要分配的资源矩阵。最右边的 E、P 以及 A向量 分别表示：总资源、已分配资源以及可用资源。
检测一个状态是否安全：查找需要分配的资源矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。重复以上两步，直到所有进程都标记为终止，则状态是安全的。一个状态不是安全的，则拒绝进入这个状态。
死锁检测和银行家算法的步骤一模一样，只不过死锁检测是根据当前请求分配资源来检测此刻是否有死锁进程，而银行家根据未来请求来检测下一个状态是否安全(不安全也不一定死锁，只不过安全状态完全杜绝了死锁将发生的可能性)。
内存管理
- 虚拟内存是操作系统将物理内存抽象成的虚拟地址空间，每个进程都有自己独立的虚拟地址集合①(使用部分加载技术，让进程的某些页面加载进内存，需要另一些页面时从磁盘替换进内存，这样能加载的进程的内存可以大于物理内存，于是好像内存变大了，这部分内存其实包含了磁盘)让物理内存扩充成更大的逻辑内存，程序可以使用更多的可用内存②防止物理地址暴露给进程(将会产生安全性问题)③进程间独立的地址空间防止争抢物理内存的问题。
- 每个进程自己的虚拟地址空间被分割成多个块，每一块称为页面，一般为4K，存储在磁盘上，这些页被唯一映射到物理内存的页框，(内存管理单元MMU发送物理地址给内存)，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中，这个映射存储在每个进程独有的页表中（一个虚拟地址可以看成两个部分，一部分存储页面号，一部分存储偏移量。而页表中每项第一部分存储页面号(顺序存储)作为索引，一部分存储对应的页框号，一个比特表示页面是否在内存中），映射由MMU完成。进程执行时会将页面调入页框中，并在页表中设置页面页框的唯一映射，产生缺页中断也会发生这个过程，OS负责维护页表。
页表存放在内存中。巨大虚拟内存可以用多级页表，让使用内存少的进程不用在内存中保存巨大的页表(其中很多表项虽然有页面号，但是页框号和存在位都是0，没用到)。正是因为页框比特位可以比页面比特位少，才能实现小内存映射到大虚拟内存。
MMU中有一个快表作为缓存区，放有少量的表项，MMU查看需要的页号是否在TLB中，不在则去内存页表中寻找它，并用它替换掉一个TLB表项。
- 当程序引用到不在物理内存中的页时，产生一个缺页中断，如果物理内存已被占满，则OS将在内存中选择一个页面进行页面置换,如有修改则回写入磁盘，没修改则用新页面覆盖，将缺失的页面从磁盘装入物理内存并更新页表项，重新执行中断前的指令。
- 页面置换时需要用到页面置换算法，主要目的是使页面置换频率最低（也可以说缺页率最低）。
①最佳页面置换
所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。是一种理论上的算法，因为无法知道一个页面多长时间不再被访问，但可以通过此算法对其他可实现算法的性能进行比较和度量。
②最近最少使用(LRU)
维护一个内存中页面的链表,当一个页面被访问时，将这个页面移到链表表头,这样就能保证链表表尾的页面是最近最久未访问的,因为每次访问都需要更新链表，因此这种方式实现的LRU代价很高。
③最近未使用(NRU)
每个页面都有两个状态位：R与M，当页面被访问时设置页面的R=1，当页面被修改时设置M=1。其中R位会定时被清零。可以将页面分成以下四类：R=0\1 & M=0\1。
NRU算法随机地从最优先的(即状态接近00的)非空类中挑选一个页面将它换出。NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。
④先进先出(FIFO)
OS维护一个内存中页面的链表，最新进入内存的页面放在表尾，换出表头的页面。该算法会将那些经常被访问的页面也被换出，从而使缺页率升高。
⑤第二次机会算法
FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：当页面被访问 (读或写) 时设置该页面的R位为1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是1，就将R位清0，并把该页面放到链表的尾端，然后继续从链表的头部开始搜索。
⑥时钟算法
第二次机会算法需要在链表首位移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面，当它的R为1时只需向后移动一次指针。
- 分段与分页
虚拟内存采用的是分页技术，也就是将进程的地址空间划分成大小相同的页，每一页再与内存进行映射，为了获得更大的地址空间。
分段的做法是把进程的内存块分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且预留了方便动态增长的空间，预留空间用完了就会移到足够大的空闲区。
程序的地址空间划分成多个拥有逻辑上独立地址空间的段，每个段划分成大小相同的页。这样既有分段系统的共享和保护，又有分页系统的虚拟内存功能。
比较：
①对(操作系统之上的)程序员的透明性：分页透明，但是分段需要程序员(即编译器)显式划分每个段。
②地址空间的维度：分页是一维地址空间，分段是二维的。
③大小是否可以改变：页的大小不可变，段的大小可以动态改变。
④出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。
文件系统
- 文件是OS对磁盘的抽象，进程虚拟地址空间是OS对内存的抽象。OS中处理文件(创建、命名、访问、保护、实现、管理)的部分称为文件系统。文件为进程提供非易失性的数据存储方法，进程创建文件时就为文件命名，进程终止时其他进程可以通过文件名访问。
- 扩展名是供程序选择处理哪种文件，或在系统中注册扩展名并规定哪个程序打开该扩展名的文件。OS只看到了一堆字节，文件内容的含义只在用户程序中解释。
- 普通文件分为字符文件和二进制文件，目录是管理文件系统的系统文件。
- 文件系统包括了文件与文件目录，文件系统具有树状结构，数的每一个叶子结点表示文件或空目录。文件系统具体有：
inode table：一个文件占用一个 inode，记录文件的属性，同时记录此文件的内容所在的 block地址；
block：记录文件的内容。
superblock：记录文件系统的整体信息，包括 inode 和 block 的总量、使用量、剩余量，以及文件系统的格式与相关信息等；
block bitmap：记录 block 是否被使用的位图。
- 每个文件独有一个表结构的i节点，包含了文件的属性、文件内容磁盘块(block)的地址,给定了文件inode才能找到文件的所有块，OS用每个inode都有的一个号码识别不同的文件。只有在文件被打开时，inode才在内存中。linux一个inode中除了文件属性部分还有12个块指针和1个间接块指针，1个二级间接块指针，1个三级间接块指针，所以块大小限制了单个文件大小。建立一个目录时，会分配一个inode与地址在inode中的block，block记录目录下所有文件的inode编号以及文件名。文件的inode本身不记录文件名，文件名记录在目录中，因此新增文件、删除文件、更改文件名这些操作与目录的写权限有关。
- 文件读取：对于Ext2文件系统，当要读取一个文件的内容时，先在inode中查找文件内容所在的所有 block，然后把所有 block 的内容读出来。
而对于 FAT 文件系统，它没有 inode，每个block中存储着下一个block的地址。
8. 磁盘碎片：一个文件内容所在的 block 过于分散，导致磁盘磁头移动距离过大，从而降低磁盘读写性能。
9. 链接技术允许在多个目录中出现同一个文件，link建立一个文件与另一个目录的链接，在目录下创建一个条目，记录着文件名与 inode 编号，会增加文件的i-node中的连接计数器的计数，称为硬链接，限制是不能对目录建立硬链接。Unlink解除文件与目录连接，删除目录中此文件的条目，文件连接计数减一，如果文件被引用数为0则删除它(删inode和inode指定的block)。符号链接文件保存着源文件所在的绝对路径，在读取时找到绝对路径对应目录的i节点中的block地址(block存放文件名-inode对)再通过inode定位到源文件各块上，可以理解为 Windows 的快捷方式，当源文件被删除了，链接文件就打不开了。可以为目录建立符号链接。
IO设备
- I/O设备分为块设备(以固定大小块为单位发送数据，块可寻址)和字符设备，一般由机械部件(设备本身)和电子部件(设备控制器\适配器)。
- OS为每一类设备定义一组接口，驱动程序必须包括它们的实现，如此做到了设备驱动程序对OS接口的统一。
- 设备IO是异步方式的，设备驱动程序通过设备控制器启动设备，让设备在操作完成时发出一个中断。
- 设备I/O缓冲很重要(内核缓冲区、用户缓冲区)，可提高读写效率，网络数据包也需要放在缓冲区检查，OS才知道要将其放置在哪。
- 盘面(柱面)、磁道、扇区（一个块，最小的物理储存单位，4k），磁头(盘面磁场转为电信号或电信号转为盘面磁场)、磁盘臂、主轴
- 读写一个磁盘块的时间的影响因素有：旋转时间(主轴转动盘面，使磁头移到适当扇区)、寻道时间(磁盘臂移动到适当的磁道)、实际数据传输时间，寻道时间最长，因此磁盘调度的主要目的是使磁盘平均寻道时间最短。
- 磁盘调度算法①先来先服务，按照磁盘请求的顺序进行调度，优点是公平简单，缺点未对寻道优化，平均寻道时间较长。②最短寻道时间优先，优先调度与当前磁头所在磁道距离最近的磁道，优点寻道时间短，缺点不够公平，两端磁道容易出现饥饿现象。③电梯算法，保持一个方向寻道，直到没有请求，然后改变运行方向，既公平又高效。
编译链接
- 预处理阶段处理以 # 开头的预处理命令，如包含头文件、宏定义、条件编译，生成修改过的源文件文本；编译阶段检查语法，并翻译成汇编语言；汇编阶段将汇编文件翻译成可重定位的目标二进制文件；链接阶段将目标文件(包括静态库文件和项目中所有源文件产生的目标文件)进行合并，得到最终的可执行目标文件。
- 编译时，编译器只检测程序语法和函数、变量是否被声明。如果函数未被定义，编译器会给出一个警告，但可以生成Object File。而在链接程序时，链接器会在所有的Object File中找寻函数的实现，如果找不到，那到就会报链接错误码。
- 链接器主要完成以下两个任务：①符号解析：每个符号对应于一个函数、一个全局变量或一个静态变量，符号解析的目的是将每个符号引用与一个符号定义关联起来。②重定位：链接器通过把每个符号定义与可执行文件中的一个虚拟内存位置关联起来(一般只需在原目标文件地址基础上加一个在可执行文件中存放这个目标文件开头的偏移地址)，然后修改所有对这些符号的引用(引用地址)，使得它们指向这个内存位置。
- 静态\动态库都是闭源的可重定位二进制目标文件。
静态库链接的时候会复制到每个最终的可执行文件中，在n个可执行文件中总共有n份(所以在内存和文件系统中都可能分别有n份)。
动态库运行需要时加载1份到内存，内存中的多个可执行文件(进程)共享，在n个可执行文件中总共只有1份(所以在内存和文件系统中都可能分别只有1份)。
- 动态链接库(共享库，.so(linux)，.DLL(windows))中的指令一般是用的相对地址，因为要实现内存中(被某个进程链接重定位并装载到内存后)被多进程共享，但用到它的软件需要带着库进行发布。
- 静态库缺点①如果改变则要对所有目标文件进行重新链接生成可执行文件，不方便②每个可执行文件中都有一份，使文件膨胀，但发布时不用带着库发布。