操作系统

操作系统导论

　　操作系统是管理和控制计算机硬件和软件资源的计算机程序．计算机系统大致可以分为四个组成部分：计算机硬件、操作系统、系统程序与应用程序和用户．计算机系统的组成部分包括硬件、软件和数据．操作系统是一直运行在计算机上的程序（通常称为内核kernel）．

操作系统基本特征：

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

计算机系统组织

　　现在通用计算机系统有一个或多个cpu和若干设备控制器通过共同的总线相连而成，该总线提供了对共享内存的访问．每个设备控制器负责一种特定类型的设备（磁盘驱动器、音频设备、视频显示器），cpu与设备控制器可以并发工作，并竞争内存周期．

　　当启动计算机时，它需要一个初始化程序．该初始化程序通常位于ROM或EEPROM中，称为计算机硬件中的固件．他初始化系统中的cpu寄存器、设备控制器和内存内容．

　　计算机程序必须在内存（或随机访问内存RAM）中以便于运行．通过地特定内存地址执行一系列load或store指令来实现交互．指令load将内存中的子移到cpu的寄存器，指令store将寄存器的内容移到内存．存储设备层次：寄存器，高速缓存、驻村、电子磁盘、磁盘、光盘、磁带．

计算机系统体系结构

　　单处理系统（只要一个人同cpu）、多处理系统（增加吞吐量、规模经济、可靠性）、集群系统．

操作系统结构

　　操作系统具有多道程序处理能力，多道程序设计通过组织作业是cpu总有一个作业可执行，从而提高了cpu的利用率．分时系统是多道程序设计的延伸，分时操作系统允许许多用户同时共享计算机．

操作系统操作

　　双重模式操作：用户模式和监督程序模式．

进程管理

　　处于执行中的程序称为进程，进程需要一定的资源（cpu时间、内存、文件、I/O设备）以完成其任务．程序本身并不是进程，程序是被动的实体，如同储存在磁盘上的内容，进程是一个活动的实体．进程是系统工作的单元，操作系统负责下述与进程管理相关的活动：

创建和删除用户进程和系统进程

挂起和重启进程

提供进同步机制

提供进程通信机制

提供死锁处理机制　　

内存管理

　操作系统负责下列有关内存管理的活动：

记录内存的那部分在使用及被谁使用

当有内存空间时，决定奶写进程可以装入内存

根据需要分配和释放内存空间

存储管理

　文件系统管理，操作系统负责下列有关文件管理的活动：

创建和删除文件

创建和删除目录来组织文件

提供操作文件和目录的原语

将文件映射到二级存储上

在稳定存储介质上备份文件

　操作系统负责系列有关硬盘管理的活动：

空闲空间管理

存储空间分配

硬盘调度

高速缓存

　　信息通常保存在内存中，当他使用时，他会被临时复制到赶快的存储系统－高速缓存．当需要特定的信息时，首先检查他是否在高速缓存红，如果是，可直接使用高速缓存的信息，否则使用位于内存的信息，同事将其复制到高速缓存一片下次使用．索引寄存器为内存提供了高速缓存．

I/O系统

　　操作系统的目的之一在于对用户隐藏具体硬件设备的特性．I/O子系统摆阔如下几个部分：

一个包括缓存、高速缓存和假脱机的内存管理部分

通用设备驱动器接口

特定硬件设备的驱动程序

操作系统结构

• 用户界面：命令行界面、图形用户界面、
• 程序执行：系统必须将程序装入内存中并运行程序
• I/O操作：操作系统必须提供I/O操作的方法
• 文件系统操作：
• 通信：进程之间的信息交换
• 错误检测：
• 资源分配：
• 统计:
• 保护和安全

系统调用类型

　　系统调用大致分为五类：进程控制、文件管理、设备管理、信息维护和通信．

进程管理

　　处于执行中的程序称为进程，进程需要一定的资源（cpu时间、内存、文件、I/O设备）以完成其任务．程序本身并不是进程，程序是被动的实体，如同储存在磁盘上的内容，进程是一个活动的实体．进程是系统工作的单元．

　　进程状态：

• 新的：进程正在被创建

• 运行：指令正在被执行

• 等待：进程等待某个事件的发生

• 就绪：进程等待分配处理器

• 终止：进程完成执行

  进程控制块：（PCB）

• 进程状态：前述状态

• 程序计数器：表示进程要执行的下个指令的地址

• CPU寄存器：包括累加器、索引寄存器、堆栈指针、通用寄存器和其他条件码信息寄存器

• CPU调度信息：进程优先级、调度队列的指正和其他调度参数

• 内存管理信息：基址和界限寄存器的值顿号页表或段表

• 记账信息：CPU事件、实际使用时间、时间界限、记账数据、作业或进程数量

• I/O状态信息：分配给进程的I/O设备列表、打开的文件列表

进程操作

　　进程创建：创建进程称为父进程，新进程称为子进程，新进程可以再创建其他进程，形成进程树．

　　大多数操作系统根据唯一的进程标示符(pid)来识别进程，pid通常是一个整数值．在进程创建时，除了得到各种物理和罗技资源外，初始化数据由父进传递给子进程．

　　当进程创建新进程是，有两种执行可能：

• 父进程与子进程并发执行
• 父进程等待，直到某个或者去全部子进程执行完

　　新进程的地址空间也有两种可能：

• 子进程是父进程的复制品
• 子进程装入另外一个程序

进程终止

　　当进程完成执行最后的语句后用exit()请求操作系统删除自身时，进程终止．进程可以返回状态值到父进程，所有进程资源会被操作系统释放．

　　父进程终止子进程的原因：

• 子进程使用了超过他所分配到的一些资源
• 分配给子进程的任务已经不再需要
• 父进程退出

进程间通信

　　操作系统内并发执行的进程可以是独立进程或协作进程．协作进程需要进程间通信机制来允许进程相互交换数据与信息．进程间通信有两种基本模式：共享内存、消息传递．

线程

　　线程是CPU使用的基本单元，它有线程ID、陈旭计数器都闹寄存器集合和堆栈组成．它与属于同于进程的其他线程共享代码段、数据段和其他操作系统资源．单线程、多线程．

　　多线程编程优点：

• 响应度高：即使部分阻塞或者执行叫冗长的操作，陈旭仍然继续执行
• 资源共享：现成默认共享他们所属进程的内存和资源
• 经济：进程创建所需要的内存和资源的分配比较昂贵
• 多处理器体系结构的利用：充分使用多处理器体系结构，以便每个进程能并行运行在不同的处理器

多线程模型

多对一模型：将许多用户线程映射到一个内核线程．

一对一模型：将每个用户线程映射到一个内核线程．

多对多模型：多路复用许多用户线程到同样数量或更小数量的内核线程上．

现线程是进程内的控制流．多线程进程在同一地址被包括多个不同的控制流．

线程池

　　每当服务器收到请求，他就创建一个独立线程以处理请求．虽然创建一个独立线程显然要比传建一个独立进程好，但是多线程服务器存在一些潜在的问题：（１）处理请求之前用以创建线程的时间，以及线程在完成工作后就要被丢弃这一事实；（２）如果允许所有并发请求都通过新线程来处理，那么将无法限制在系统中并发执行的线程的数量．无限制的线程会耗尽系统资源，如CPU时间和内存．

　　线程池是解决这个问题的一种方法，主要思想是：在进程开始时创建一定数量的线程，并放入池中等待工作．当服务器收到请求时，他会唤醒池红的一个线程，并将要处理的请求传递给它．一旦线程完成任务，他会返回到池中再等待工作．如果池中没有可以使用的线程，那么服务器会一直等待到有空线程为止．线程池的优点如下：

• 通常用现有线程处理请求要比等待创建新的线程要快．
• 线程池限制了在任何时候可用线程的数量．

调度程序激活

　　一种解决用户线程库与内核间通信的方法被称为调度器激活．工作方式：内核提供一组虚拟处理器给应用程序，应用程序可调度用户线程到一个可用的虚拟处理器上．

进程和线程的区别

进程是系统分配资源的单位，每一个进程对应一个活动的程序，当进程激活时，操作系统将系统的资源（内存、I/O和CPU等分配给它，使它执行）．

线程是CPU分配时间的单位，每一个线程对应于它在进程中的一个函数，也就是内存中的代码段，多个线程执行是CPU会根据他们的优先级分配时间，使它们完成自己的功能．

• 线程是比进程更小的能独立运行的单位，通常一个进程都有若干个线程，至少也需要一个线程．

调度：线程是调度和分派的基本单位，进程是资源拥有的单位．

并发性：进程之间可以并发执行，在一个线程中的多个线程之间也可以并发执行．

拥有资源：进程是拥有资源的一个独立单元，线程自己不拥有系统单元可以访问其隶属进程资源

系统开销：创建和撤销进程时，系统需要为之分配或回收资源，OS所付出的开销显著大于在创建或撤销线程时的开销；进程切换的开销也远大于线程切换的开销．

• 进程是指在系统中正在运行的一个应用程序；
• 线程是系统分配处理器时间资源的基本单元，或者说进程之内独立执行的一个单元。

CPU调度

　　CPU调度是多道程序操作系统的基础，在进程之间切换CPU,操作系统可以提高计算机的吞吐率．

　　CPU调度决策发生情景：

• 当一个进程从运行状态切换到等待状态．
• 当一个进程从运行状态切换到就绪状态．
• 当一个进程从等待状态切换到就绪状态．
• 当一个进程终止时．

调度准则

• CPU使用率：需要使CPU尽可能忙．
• 吞吐量：测量工作量的方法称为吞吐量，它指一个单元内所完成进程的数量．
• 周转时间：进程提交到进程完成的时间段．
• 等待时间：就绪队列中等待所花费的时间之和．
• 响应时间：从提交请求到产生第一想要的时间．

调度算法

单处理器系统CPU调度

先到先服务调度：先请求CPU的进程先分配到CPU，平均等待时间较长．

最短作业优先调度算法：将每个进程与下一个CPU区间段相关联．当CPU为空闲时，他会付给具有最短CPU区间的进程．

优先级调度：每一个进程都有一个优先级与其关联，具有最好优先级的进程会分配到CPU.

轮转法调度：为分时系统设计，类似于先到先服务调度，但是增加了抢占以切换进程．

多级队列调度：将就绪队列分成多个独立队列．根据进程的属性，如内存大小、进程优先级、一个进程被永久的分配到一个队列，每个队列有自己的调度算法．

多级反馈队列调度：允许进程在队列之间移动，根据不同CPU区间的特点以区分进程，如果进程使用过多CPU时间，他会被转移到更低优先级队列．

多处理器调度方法

• 非对称多处理：让一个处理器处理所有的调度决定、I/O处理以及其他系统活动，其他处理器只执行用户代码．
• 对称多处理：每个处理器自我调度，调度通过每个处理器检查共同就绪队列并选择一个进程来执行．

　负载平衡设法将工作服在平均分配到对称多处理系统的所有处理器上．

线程调度

　　用户线程和内核线程的区别之一在于他们是如何被调度的．

进程同步

　　协作进程是可以与在系统内执行的其他进程互相影响的进程．互相协作的进程可以直接共享逻辑地址空间（代码和数据），或者只通过文件或消息来共享数据．

临界区问题

　　每个进程有一个代码段称为临界区，在该区中进程可能改变共同变量、更新一个表、写一个文件等．当一个进程进入临界区，没有其他进程可悲允许在临界区执行．

　　临界区满足三项要求：互斥、前进、有限等待．

　　处理操作系统内的临界区问题：抢占内核和非抢占内核．抢占内核更适合实时编程，因为它允许实时进程抢占处于内核模式运行的其他进程．抢占内核的相应更快，因为处于内核模式的进程在释放CPU之前不会运行过久．

硬件同步

　　临界区的问题都需要一个简单的工具：锁．通过要求临界区用锁来防护，就可以避免竞争条件，即一个进程在进入临界区之前必须得到锁，而在其退出临界区时释放锁．

经典同步问题

• 有限缓存问题
• 读者－写者问题
• 哲学家进餐问题

死锁

　　在多道程序环境下，多个进程可能竞争一定数量的资源．某个进程申请资源，如果这时资源不可用，那么该进程进入等待状态．若谷神奇的资源被其他等待进程占用，那么该等待进程有可能再也无法改变其状态．这种情况称为死锁(deadclock).

死锁特征

　　必要条件

• 互斥：至少一个资源必须处于非共享模式，即一次只有一个进程使用．如果了一个进程申请该资源，那么申请进程必须等到该资源被释放为止．
• 占有并等待：一个进程必须占有至少一个资源，并等待另一资源，二该资源为其他进程所占有．
• 非抢占：资源不能被抢占，即资源只能在进程完成任务后自动释放．
• 循环等待：有一组等待进程{p0,p1,…,pn}，p0等待的资源为p1占有，p1等待的资源为p2占有，．．．，pn等待的资源为p0占有．

　上述四个条件必须全部满足才会出现死锁．循环等待条件意味着占有并等待条件，这样4个条件并不

完全独立．

死锁处理方法

• 使用协议以预防或避免死锁，确保系统不会进入死锁状态．
• 可允许系统进入死锁状态，然后检测它，并加以恢复．
• 可忽视这个问题，认为死锁不可能在系统内发生．

为了确保思索不会发生，系统可采用死锁预防或死锁避免方案．

死锁预防

互斥

对于非共享资源，必须要有互斥条件．例如：一台打印机不能同事为多个进程所共享．共享资源不要求互斥访问，一次不会死锁．

占有并等待

当一个进程申请一个资源时，它不能占有其他资源．一种可以使用的协议时每个进程在执行前申请并获得所以资源．另一种协议允许进程在没有资源时才可以申请资源．这两种协议的主要缺点：第一，资源利用率可能比较低，因为许多资源可能已分配，但是长时间没有被使用．第二，可能发生饥饿，一个进程如需要多个常用资源，可能会永久等待，因为其所需要的资源中至少有一个已分配给其他进程．

非抢占

如果一个进程占有资源并申请了一个不能立即分配的资源，那么其现已分配的资源都可能被强占．换句话说，这些资源都被隐式地释放了．如果一个进程申请一些资源，那么首先检查它们是否可用．如果可用，那么就分配它们；如果不可用，那么检查这些资源是否已分配给其他等待额外资源的进程．

循环等待

对所有资源类型进行完全排序，且要求每个进程按递增顺序来申请资源．

死锁避免

获得以后如何申请资源的附加信息，每次申请要求系统考虑现有可用资源、现已分配给每个进程的资源和每个进程将来申请与释放的资源，以决定当前申请是否满足或必须等待，从而避免死锁发生的可能性

安全状态

如果系统能按某个顺序诶每个进程分配资源（不超过其最大值）并能避免死锁，那么系统状态就是安全的．准确的说，如果存在一个安全写，那么系统处于安全状态．

• 资源分配图算法 　每种资源类型只有一个实例
• 银行家算法　每种资源类型有多个实例

检测死锁

允许系统运行过程中产生死锁，在死锁发生之后，采用一定的算法进行检测，并确定与死锁相关的资源和进程，采取相关方法清除检测到的死锁。实现难度大 ．

解除死锁

与死锁检测配合，将系统从死锁中解脱出来（撤销进程或者剥夺资源）。对检测到的和死锁相关的进程以及资源，通过撤销或者挂起的方式，释放一些资源并将其分配给处于阻塞状态的进程，使其转变为就绪态。实现难度大．

内存管理方式-段式页式和段页式

　　由于连续内存分配方式(单一连续分配，固定分区分配，动态分区分配，动态重定位分区分配)导致的内存利用率偏低以及内存碎片的问题，进而引出离散的内存分配方式。离散内存分配可以从OS的内存管理角度引出页式(离散分配的基本单位是页)管理，也可以从程序编制角度引出段式(离散分配的基本单位是段)管理。

基本分页存储管理

　 基本分页存储管理中不具备页面置换功能(即没有实现虚拟内存的功能)，因此需要整个程序的所有页面都装入内存之后才可以运行。因为程序数据存储在不同的页面中，而页面又离散的分布在内存中，因此需要一个页表来记录逻辑地址和实际存储地址之间的映射关系，以实现从页号到物理块号的映射。由于页表也是存储在内存中的，因此和不适用分页管理的存储方式相比，访问分页系统中内存数据需要两次的内存访问(一次是从内存中访问页表，从中找到指定的物理块号，加上页内偏移得到实际物理地址；第二次就是根据第一次得到的物理地址访问内存取出数据)。
　　为了减少两次访问内存导致的效率影响，分页管理中引入了快表(或者联想寄存器)机制，包含快表机制的内存管理中，当要访问内存数据的时候，首先将页号在快表中查询，如果查找到说明要访问的页表项在快表中，那么直接从快表中读取相应的物理块号；如果没有找到，那么访问内存中的页表，从页表中得到物理地址，同时将页表中的该映射表项添加到快表中(可能存在快表换出算法)。
　　在某些计算机中如果内存的逻辑地址很大，将会导致程序的页表项会很多，而页表在内存中是连续存放的，所以相应的就需要较大的连续内存空间。为了解决这个问题，可以采用两级页表或者多级页表的方法，其中外层页表一次性调入内存且连续存放，内层页表离散存放。相应的访问内存页表的时候需要一次地址变换，访问逻辑地址对应的物理地址的时候也需要一次地址变换，而且一共需要访问内存3次才可以读取一次数据。

基本分段存储管理方式

　　分页是为了提高内存利用率，而分段是为了满足程序员在编写代码的时候的一些逻辑需求(比如数据共享，数据保护，动态链接等)。
　　分段内存管理当中，地址是二维的，一维是段号，一维是段内地址；其中每个段的长度是不一样的，而且每个段内部都是从0开始编址的。由于分段管理中，每个段内部是连续内存分配，但是段和段之间是离散分配的，因此也存在一个逻辑地址到物理地址的映射关系，相应的就是段表机制。段表中的每一个表项记录了该段在内存中的起始地址和该段的长度。段表可以放在内存中也可以放在寄存器中。
　　访问内存的时候根据段号和段表项的长度计算当前访问段在段表中的位置，然后访问段表，得到该段的物理地址，根据该物理地址以及段内偏移量就可以得到需要访问的内存。由于也是两次内存访问，所以分段管理中同样引入了联想寄存器。

分页和分段对比

• 页是信息的物理单位，是出于系统内存利用率的角度提出的离散分配机制；
• 段是信息的逻辑单位，每个段含有一组意义完整的信息，是出于用户角度提出的内存管理机制
• 页的大小是固定的，由系统决定；
• 段的大小是不确定的，由用户决定
• 页地址空间是一维的；
• 段地址空间是二维的

段页式存储管理

　　先将用户程序分为若干个段，然后再把每个段分成若干个页，并且为每一个段赋予一个段名称。这样在段页式管理中，一个内存地址就由段号，段内页号以及页内地址三个部分组成。
　　段页式内存访问：系统中设置了一个段表寄存器，存放段表的起始地址和段表的长度。地址变换时，根据给定的段号（还需要将段号和寄存器中的段表长度进行比较防止越界）以及寄存器中的段表起始地址，就可以得到该段对应的段表项，从段表项中得到该段对应的页表的起始地址，然后利用逻辑地址中的段内页号从页表中找到页表项，从该页表项中的物理块地址以及逻辑地址中的页内地址拼接出物理地址，最后用这个物理地址访问得到所需数据。由于访问一个数据需要三次内存访问，所以段页式管理中也引入了高速缓冲寄存器。

虚拟内存及页面置换算法

　　如果存在一个程序，所需内存空间超过了计算机可以提供的实际内存，那么由于该程序无法装入内存所以也就无法运行。单纯的增加物理内存只能解决一部分问题，但是仍然会出现无法装入单个或者无法同时装入多个程序的问题。但是可以从逻辑的角度扩充内存容量，即可解决上述两种问题。

　　虚拟存储器就是具有请求调入功能和置换功能，可以从逻辑上对内存容量加以扩充的一种存储器系统。虚拟存储器都是建立在离散内存管理的基础上．

虚拟存储器的特征：

• 多次性：一个作业可以分多次被调入内存。多次性是虚拟存储特有的属性 ．
• 对换性：作业运行过程中存在换进换出的过程(换出暂时不用的数据换入需要的数据) ．
• 虚拟性：虚拟性体现在其从逻辑上扩充了内存的容量(可以运行实际内存需求比物理内存大的应用程序)。虚拟性是虚拟存储器的最重要特征也是其最终目标。虚拟性建立在多次性和对换性的基础上行，多次性和对换性又建立在离散分配的基础上．

页面置换算法

• 最佳置换算法：只具有理论意义的算法，用来评价其他页面置换算法。置换策略是将当前页面中在未来最长时间内不会被访问的页置换出去。
• 先进先出置换算法：简单粗暴的一种置换算法，没有考虑页面访问频率信息。每次淘汰最早调入的页面.
• 最近最久未使用算法LRU：算法赋予每个页面一个访问字段，用来记录上次页面被访问到现在所经历的时间t，每次置换的时候把t值最大的页面置换出去(实现方面可以采用寄存器或者栈的方式实现).
• 时钟算法clock(也被称为是最近未使用算法NRU)：页面设置一个访问为，并将页面链接为一个环形队列，页面被访问的时候访问位设置为1。页面置换的时候，如果当前指针所指页面访问为为0，那么置换，否则将其置为0，循环直到遇到一个访问为位0的页面.
• 改进型Clock算法：在Clock算法的基础上添加一个修改位，替换时根究访问位和修改位综合判断。优先替换访问为何修改位都是0的页面，其次是访问位为0修改位为1的页面。
• 最少使用算法LFU：设置寄存器记录页面被访问次数，每次置换的时候置换当前访问次数最少的。存在问题是该访问寄存器并不能真正反映当前页面访问次数，因为访问速度比较快，所以在更新寄存器的时间间隔内访问1次和访问100次都是一样的。另外，LFU和LRU是很类似的，支持硬件也是一样的，但是区分两者的关键在于一个以时间为标准，一个以次数为标准(例如对于寄存器 pa 001111 和pb 111000，两个页面，如果采用LRU，那么被淘汰的是pa，如果采用LFU那么被淘汰的是pb)。
• 页面缓冲算法PBA：置换的时候，页面无论是否被修改过，都不被置换到磁盘，而是先暂留在内存中的页面链表(已修改页面链表和未修改页面链表，也可以不区分)里面，当其再次被访问的时候可以直接从这些链表中取出而不必进行磁盘IO，当链表中已修改也难数目达到一定数量之后，进行依次写磁盘操作(相当于将多次IO合并为一次).