一、操作系统基础知识
操作系统的作用：用户接口、存储管理、文件管理、设备管理、处理机管理。
1. 存储管理：
2. 处理机管理：
3. 设备管理：
4. 文件管理：
5. 用户接口：
6. http://blog.csdn.net/nd200642/article/details/3867867
7. http://blog.sina.com.cn/s/blog_7d8771ed01010tie.html
操作系统定义：是管理和控制计算机系统中各种硬件和软件资源、合理地组织计算机工作流程的系统软件，是用户与计算机之间的接口。
多道批处理系统
1. 在内存中同时存放多道程序，在管理程序的控制下交替执行，这些作业共享CPU和系统其他资源。
2.
3.
分时系统：把处理机运行时间分成时间片，按时间片轮转的方式，把处理机分配给各联机作业使用。
实时系统：系统能及时(或即时)响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。提供即时响应和高可靠性，响应时间快，可以在毫秒级甚至微秒级立即处理。
二、操作系统用户界面
作业的基本概念
1. 定义：是要求计算机系统按指定步骤对应用程序进行处理并得到计算结果的加工工作。
2. 作业步：对应用程序进行处理的步骤。作业由不同的顺序相连的作业步组成。
3. 组成：
4. 作业的建立：当一个作业的全部程序和数据输入到外存并且在系统中建立了相应的作业控制块之后，一个作业就建立了。
用户接口基本概念
1. 定义：
2. 系统提供的用户接口：
3. 处理机执行状态：
大多数处理器至少支持两种执行模式，某些指令只能在特权模式下运行，包括读取或改变诸如程序状态字之类控制寄存器的指令、原始I/O 指令和与内存管理相关的指令。另外，有部分内存区域仅在特权模式下可以被访问到。非特权模式通常称为用户模式，这是因为用户程序通常在该模式下运行;特权模式可称为系统模式、控制模式或内核模。态的切换不一定会导致进程的切换，进程的切换一点伴随态的切换。
4.
三、进程管理
程序基本概念
1. 程序执行的两种方式：顺序执行、并发执行（现代操作系统多为并发执行，引入并发执行的目的是为了提高资源利用率）。
2. 顺序执行：一个计算的若干操作必须按照严格的先后次序顺序地执行，这类计算过程就是程序的顺序执行过程。
3. 并发执行：指一组在逻辑上相互独立的程序或程序段在执行过程中，其执行时间在客观上相互重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始的这种执行方式。
进程基本概念
1. 定义：进程是指一个具有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基本单位。
2. 进程和程序的区别：
3. 进程的组成：进程通常由程序、数据集合和进程控制块PCB三部分组成。程序和它操作的数据是进程存在的静态实体，而专门的数据结构PCB用来描述进程当前的状态、本身的特性等。
进程的状态
1. 就绪状态：处于就绪状态的进程已经得到除CPU之外的其他资源，只要由调度得到处理机，便可立即投入执行。
2. 运行状态：进程调度程序从就绪队列中选择一个进程分配给它CPU控制权，该进程所处的状态为运行状态。
3. 等待状态：进程因等待某个事件的发生（如等待I/O的完成），而暂停执行，则该进程处于等待状态（这时，即使给它CPU，它也无法执行）。
进程的相互作用：多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源。这些资源有些是可共享使用的，如磁盘，有些是以独占方式使用的，如打印机。由此将会引起一系列的矛盾，产生错综复杂的相互制约的关系。
进程互斥
1. 临界资源：一次仅允许一个进程使用的资源成为临界资源。
2. 临界区：每个进程中访问临界资源的那段程序段称为临界区。
3. 互斥的定义：在操作系统中，当某一进程正在访问某临界区时，就不允许其它进程进入，进程之间的这种相互制约的关系成为互斥。
进程同步
1. 异步环境下的一组并发进程互相发送消息而进行互相合作、互相等待，使得各进程在执行速度上相互协调，这样的相互制约关系称为进程同步。
2.
同步与互斥的关系：
死锁
1. 定义：指各并发进程彼此相互等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想得到资源而又都得不到资源，各并发进程不能继续向前推进的状态。
2. 死锁的必要条件：互斥条件（资源是不可共享的临界资源，进程要求对所分配的资源进行排他性控制）；部分分配（进程每次申请它所需要的一部分资源，在等待新资源的同时，继续占有已经分配到的资源）；不剥夺条件（进程已经获得资源，在没有使用完之前不能被剥夺）;环路条件（在发生死锁时，必然存在一种进程-资源的循环链，链中每一个进程已获得的资源同时被下一个进程所请求）。
3. 安全状态：现有进程资源占有的情况下，各进程按照某种推进顺序仍然可以使每个进程得到其对资源的最大需求，从而都可以顺利地完成。
4. 死锁的排除方法：
5. 预防死锁的方法：
银行家算法的实质就是要设法保证系统动态分配资源后仍然保持安全状态，从而避免死锁的发生。要求进程预先告知自己的最大资源需求，并且假设系统拥有固定的资源总量。
1.
2.
3.
4.
进程间通信IPC：http://www.cnblogs.com/applebunny/archive/2012/07/11/2586483.html
1. 通信类型：低级通信（只传送控制信息）和高级通信（传送大批量的数据，目的是为了交换信息）；直接通信（发送和接收时都要致命进程的名字。信息直接传递给接收方，如：管道）和间接通信（发送进程发消息时不指定接收进程的名字，而是借助于收发双方进程之外的共享数据结构作为通信中转，如消息队列。）。
2. 通信方式——消息/邮箱机制：
3. 通信方式——共享存储区：两个需要互相交换信息的进程通过对同一共享数据区(shared memory)的操作来达到互相通信的目的。这个共享数据区是每个互相通信进程的一个组成部分。
4. 通信方式——消息缓冲机制：发送进程先申请一个消息缓冲区，写入消息后把该消息缓冲区送入接收进程的消息队列中，通知接收进程。接收进程从消息队列中摘下一消息缓冲区，取出所需要的信息。
线程的基本概念
1. 引入线程目的：为了提高系统的执行效率，减少处理机的空转时间(使得单个进程可以利用CPU和I/O之间的并行性)，减少调度切换（保护现场信息）的时间，以及便于系统管理，引入了“线程”。
2. 定义：线程是进程的一个实体，是CPU调度的最基本单位。（资源分配的基本单位还是进程）
3.
四、处理机调度
分级调度
1. 调度层次：作业调度（按一定原则选择外存后备队列中的作业，为其分配内存等资源，并建立进程，使其获得竞争处理机的资格，进入就绪队列。此外，在作业执行完毕时，回收系统资源。)；交换调度（按给定策略，将外存中处于就绪状态或等待状态的进程调入内存，或将内存中暂时不能运行的进程调至外存，以提高内存利用率和系统吞吐量。）；进程调度（决定就绪队列中的哪个进程应获得处理机，为其进行进程上下文切换以建立相应的执行环境）；线程调度（进程中相关堆栈和控制表等的调度）。
2. 作业状态
3. 作业是用户向计算机提交任务的任务实体，进程是计算机为了完成用户任务实体而设置的执行实体。计算机要完成一个任务实体，必须要有一个以上的执行实体，即一个作业是由一个以上的进程组成的。
作业调度
1. 周转时间：作业从提交到执行完成所经历的时间。包括：在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待等。
2. 平均周转时间：
3. 平均带权周转时间：
进程调度
1. 进程调度的任务是控制协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选择一个进程，并把CPU的使用权交给被选中的进程。
2. 进程调度的功能：记录所有进程的执行状况；按一定策略，选择一个就绪进程；完成进程上下文切换。
3. 作业调度对除了CPU之外的所有系统资源进行分配；进程调度专门负责对CPU进行分配，使进程活动起来。
调度算法
1. 先来先服务调度算法（FCFS——First Come First Server）：按照作业提交/进程变为就绪状态的先后次序，调入系统或分派CPU。
2. 时间片轮转法（RR——Round Robin）：
3. 短作业优先法（SJF——Shortest Job First）：对预计执行时间短的作业（进程）优先处理。通常后来的短作业不抢先正在执行的作业。其目标是减少平均周转时间。
4. 最高响应比优先法（HRN——Highest Response_Ratio Next）：最高响应比优先法是介于FCFS和SJF之间的一种拆衷的算法，同时考虑每个作业的等待时间和估计需要的运行时间，从中选出响应比最高的作业投入运行。
5. 多级队列算法（Multiple-level Queue）：根据作业或进程的性质或类型的不同，将后备或就绪队列在分为若干个子队列，各队列有不同的调度算法。多级队列：该算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。
多级队列调度算法由于设置多个就绪队列，因此对每个就绪队列就可以实施不同的调度算法，因此，系统针对不同用户进程的需求，很容易提供多种调度策略。
6. 优先级算法（Priority Scheduling）：对优先级高的作业/进程优先处理，可分为抢先式和非抢先式。
7. 多级反馈轮转法（Round Robin with Multiple Feedback）：时间片轮转法和优先级法的综合和发展。
五、存储管理
存储管理的功能
存储分配的方式
重定位（地址映射）：在可执行文件装入时需要解决可执行文件中地址（包含指令和数据的地址）和内存地址的对应。
1.
2.
3.
内存信息的共享和保护
1.
2. 界限保护：
3. 访问方式保护：
虚拟存储器：为用户提供一种不受物理存储器结构和容量限制的存储技术。
1. 使得用户编程时不需要考虑物理内存的结构和容量；每个进程都拥有自己的虚存，且虚存大小不受实际物理存储器的限制。
2. 虚拟存储器的物质基础：两级存储结构（内存和外存）；地址变换机构（实现逻辑地址到物理地址的转换）。
3. 虚拟存储器的原理：
4. 根据地址空间结构的不同将虚拟存储技术分为三类：页式管理；段式管理；段页式管理。
内外存数据传输的控制
1. 覆盖：
2. 交换：
3. 虚拟存储：
分区存储管理
1. 原理：把内存分为一些大小相等或不等的分区，除操作系统占用一个分区外，其余分区用来存放进程的程序和数据。
2. 分区管理——固定分区法：作业执行前把内存固定地划分区域。缺点：存在大量碎片，主存利用率低。
3. 分区管理——动态分区法：在作业的处理过程中划分区域。
4. 固定分区的分配与回收：存储管理程序根据请求表查询分 区说明表，从中找出一个满足要求的空闲分 区，并将其分配给申请者。
5. 动态分区的分配与回收：最先匹配法（按分区起始地址的递增次 序，从头查找，找到符合要求的第一个分区）；最佳匹配法（按分区大小的递增次序， 查找，找到符合要求的第一个分区）；最坏匹配法（按分区大小的递减次 序，从头查找，找到符合要求的第一个分区）。
6. 分区存储管理的主要优缺点
页式存储管理
1. 基本原理
2. 逻辑地址的表示
3. 页表：页式存储管理的数据结构，它包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息。
4. 页式地址映射
请求页式存储管理——纯页式（静态）存储管理提高了内存的利用效 率，但并不为用户提供虚存。为此，提出了请求分页（动态）存储管理技术。
1. 实现思想：
2. 请求分页要解决的问题：如何发现执行的程序或访问的数据不在内存；调入策略，程序或数据什么时候调入内存；淘汰策略，当一些页调入内存时，内存没有空闲内存，将淘汰哪些页。
3. 调入策略：
4. 淘汰策略的评价指标：缺页次数和缺页率（缺页率为缺页次数与总访问次数之比）。
5. 置换算法
当要完全实现LRU算法需花费巨大的系统开销（必须对每一个页面都设置有关的访问记录 项，而且每一次访问都必须更新这些记录）。实际系统中往往使用LRU的近似算法
6. 存储保护
7.
段式存储管理——基本概念
1. 段式管理的由来
2. 分段
3. 段式管理的程序地址结构
4. 段式管理的内存分配思想
5. 段表和段表地址寄存器
6. 分页和分段的异同之处
段式存储管理——实现原理
1. 段式管理的内存分配与释放
2. 段式管理程序进行地址变换的步骤
3. 段的共享
段式存储管理——优缺点
1. 优点
2. 缺点
段页式存储管理——基本概念
1. 段页式管理的基本思想
2. 等分内存：把整个内存分成大小相等的内存块（内存被划分成 若干个页），内存块从0开始依次编号。
3. 地址空间分段：把用户程序分成若干段，每段有段名。
4. 段内分页：段内页面的大小与内存块相同，每段都分别从0开始 依次编号。虚空间的最小单位是页而不是段，分段大小不再受内 存可用区的限制（每段所拥有的程序和数据在内存中 可以按页分开存放）。
5. 逻辑地址的构成
6.
各种存储方法比较
六、文件管理
文件系统的概念：文件系统时OS与用户关系最紧密的一部分，对用户来说，它是OS中最直观的部分，能否方便使用OS，以及OS的可信赖程度往往取决于文件系统的功能和性能。
1. 文件和文件系统
2. 文件系统的功能
3. 文件的类型：分类的目的是对不同文件进行管理，提高系统效率
文件系统的组织结构：从用户观点出发，所看到的文件组织形式称为文件的逻辑结构；从实现观点出发，文件在外存上的存放组织形式成为文件的物理结构。
文件的逻辑结构和存取方法
1. 文件的逻辑结构由两种形式：
2. 选取文件的逻辑结构遵循下述原则：尽量减少对已存储好的文件信息的变动；能在尽可能短的时间内查找到需要的记录或基本信息单位；占据最小的存储空间；便于用户进行操作。
3. 文件逻辑结构的选择
4. 常用的记录式结构文件
5. 文件的存取方法：指用户读写文件的方法。用户通过对文件的存取来完成对文件的修改、追加和搜索等操作。通常有三种存取方法，无论是采用哪种存取方法，都是首先查找出操作对象的逻辑地址，然后由逻辑地址映射到对应的物理地址，再对物理地址的有关信息进行操作。
文件的物理结构和存储设备
1. 文件的物理结构指文件在外存上的存储结构。它依赖于外存的物理存储介质。
2. 常见的文件物理结构：顺序结构（连续文件），链接结构（串联文件），索引结构（索引文件）。
磁盘调度算法：磁盘是可被多个进程共享的设备。当有多个进程都请求访问磁盘时，应采用一种适当的调度算法，对这些请求的服务顺序调整安排，旨在降低平均磁盘服务时间，达到公平、高效。
1. 先来先服务——FCFS
2. 最短寻道时间优先——SSTF：优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先。
3. 扫描算法——SCAN：
4. 调度算法的选择
文件存储空间的管理：文件存储空间通常是分成若干个大小相等的物理块，并以块为单位来交换信息的。因此，文件存储空间的管理实质上是一空闲块的组织、分配和回收等问题。
1. 外存空闲块管理：
2. 空闲文件目录：把一个连续的未分配的区域称“空闲块”。将所有空闲块记录在一个表中，即空闲块表，其中空闲文件目录的每个表项对应一个由多个连续的空闲块构成的空闲区，主要包括： 空闲块数和第一个空闲块号。
分配空闲块
回收空闲块
3. 空闲块链
4. 成组链接法
成组链接法的分配过程
成组链接法的回收过程
5. 位示图
6.
文件目录管理：文件目录是文件系统实现按名存取的一个有效方法。系统为每个文件编制一个目录表，内容包括，文件名、物理地址、存取控制信息。
1. 文件的组成
2. 文件目录：把文件说明按一定的逻辑结构存放到物理存储块的一个表目中，该表目称为文件目录。文件目录可分为单级目录、二级目录和多级目录。
3. 目录管理
文件存取控制：与文件的共享、保护和保密问题紧密相关。
七、设备管理
概述
1. 设备类型：计算机系统中，除了CPU及存储器之外，还有一类比较重要的硬件资源——I/O设备。I/O设备是计算机与外界进行信息交换的装置。
2. 设备管理的任务
3. 设备管理的功能
数据传送控制方式
1. 程序直接控制方式
2. 中断方式
3. DMA方式——直接存取方式
4. 通道控制方式
设备分配技术
1. 多道环境下的设备分配，不只是对设备进行分配，而且还要实现与设备相关联的通道及设备控制器的分配。设备的分配和管理中，常采用的数据结构主要有四张表：系统设备表SDT、设备控制表DCT、控制器控制表COCT、通道控制表CHCT。通道控制设备控制器、设备控制器控制设备。
根据用户请求的I/O设备的逻辑名，查找逻辑设备和物理设备的映射表；以物理设备为索引，查找SDT，找到该设备所连接的DCT；继续查找与该设备连接COCT和CHCT。 一个进程只有获得了通道、控制器和所需设备三者之后，才具备了进行I/O操作的物理条件。
2. 设备分配的方式有两种：静态分配和动态分配
3. 设备独立性：指应用程序独立于具体使用的物理设备，即用户编制程序使用的设备与实际使用的设备无关。
4. 设备分配策略：先来先服务；优先级高者优先。
5. 设备分配步骤：按照顺序——分配设备；分配控制器；分配通道。
I/O进程控制
1. I/O控制：指从用户进程的I/O请求开始，给用户进程分配设备、启动有关设备进行I/O操作，以及在I/O操作完成之后响应中断，进行善后处理为止的整个系统控制过程。
2. I/O控制的功能
3. I/O控制的实现方式
缓冲技术：可提高外设利用率
1. 缓冲引入的主要目的：
2. 缓冲种类：单缓冲；双缓冲；多缓冲；缓冲池。
虚拟设备与假脱机技术
1. 虚拟设备：
2. SPOOLING系统（同时联机的外围操作或者假脱机操作）：利用一台高速共享设备（磁盘或磁鼓）将一台独占设备模拟成多台可并行操作的虚拟设备。这样一来，使每个用户都感到得到了系统中的一台独享设备。
3. 假脱机系统的特点
