第一章导论
操作系统概述
- 并发指的是多个程序可以同时运行的现象。并发的"同时"是经过上下文快速切换，使得看上去多个进程同时都在运行的现象，是一种OS欺骗用户的现象。
- 并行的"同时"是同一时刻可以多个进程在运行(处于running)
RAM随机存取存储器,也叫主存，它可以随时读写，速度很快，通常作为 操作系统 或者其他正在运行中的程序的临时数据存储介质 
BIOS基本输入输出系统，是个人电脑启动时加载的第一个软件，其实，它是一组固化到计算机内主板上一个ROM芯片上的程序，保存着计算机最重要的基本输入输出程序，开启后自己按程序和系统自启动程序。它可从CMOS中读写系统设置的具体信息。 其主要功能是为计算机提供最底层的、最直接的硬件设置和控制。
ROM只读存储的简称，是一种只能读出实现所存数据的固态半导体存储器。通常用在不需经常变更资料的电子或电脑系统中，并且资料不会因为电源关闭而消失。
EPROM是一种断电后仍能保留数据的计算机储存芯片——即非易失性的（非挥发性）
cpu的状态
- 特权指令：在内核态（管态）下运行的指令
- 不仅能访问用户空间，还能访问系统空间。
- 如启动外部设备、设置系统时钟、管中断、切换执 行状态、I/O指令
- 非特权指令：在用户态（目态）下运行的指令
- 应用程序所使用的都是非特权指令。
- 防止应用程序的运行异常对系统造成破坏。
- 仅能访问用户空间
处理器每执行完一条指令以后，硬件的中断扫描机构立即检查有无中断发生。若无，继续执行，若有，暂停当前进程，转由OS内核的中断处理程序接手。
操作系统作为用户和计算机硬件系统之间的接口，可以通过以下3种方式使用计算机：
- 命令行界面（CLI）
- 图形用户界面（GUI）
- 应用程序接口（API）
OS结构设计
- 模块化结构：将OS划分为若干个具有一定 独立性的模块。
- 分层式结构：划分层次，每一层仅使用下一层所提供的功能和服务。
- 微内核OS结构：内核仅保留极少的功能，提供服务之间的通信机制。在设计微内核OS时，采用了面向对象的技术，与传统的操作系统相比，其优点是提高了系统的灵活性、可扩充性，增强了系统的可靠性，提供了对分布式系统的支持，增强了系统的可靠性和可移植性。但是，微内核与文件管理、设备驱动、虚拟内存管理、进程管理等其他上层模块之间需要有较高的通信开销。
- 宏内核则将所有功能整合在一起，各个功能模块之间可以直接调用。这样的优势就是性能极高，但其缺点也很明显，就是其耦合度高，一旦其中一个模块出现问题，其他所有的模块都可能会受到影响。
系统调用
系统调用是操作系统内核提供给应用程序的基础接口，需要运行在操作系统的核心模式下，以确保有权限执行某些 CPU 特权指令。 系统调用本身并非内核函数，但它是由内核函数实现的。 用户程序可以利用这组接口来调用系统服务，例如磁盘I/O会用到的open，write，read等服务。
进程的描述与控制
进程与程序
- 程序是永久的，进程是暂时的。
- 同一程序可以对应多个进程。
- 程序是一个静态的概念。而进程是一个动态的概念。
- 进程是动态的、多个进程可以含有相同的程序、多个进程可以并发运行
- 动态性、并发性、独立性和异步性（不可预知的速度同时向前推进）
- 进程实体由三部分构成：程序段、数据集、进程控制块
- 进程的定义：进程是执行中的程序。
- 进程是程序的执行过程，是系统进行资源分配和调度的一个独立单位。
- 进程实体 = 程序段 + 数据段 + 进程控制块（PCB）
进程的状态
- 运行态
- 当一个进程已分配到CPU，它的程序正在被CPU执行时进程所处的状态称执行状态，也称为运行状态。对于单CPU系统而言，处于执行状态的进程只可能有一个，多处理机系统中则有多个
- 就绪态
- 若进程已具备了运行条件，只因CPU被别的进程占用而不能被CPU执行，则称此时进程处于就绪状态。一旦把CPU分配给它，该进程就可以运行。系统中处于就绪状态的进程可能有多个，通常将它们按某种策略（优先级）排成一个队列，称为就绪队列
- 阻塞态
- 正在执行的进程因等待某种事件的发生而暂时不能运行便放弃CPU的状态称阻塞状态(等待状态、封锁状态)，例如，等待输入/输出、等待进程间的同步/互斥等。一旦引起等待的原消失，进程便转为就绪状态。以便在适当的时候占用CPU。系中处于等待状态的进程可能有多个，通常也将它们排成一个列。有的系统按照进程不同的等待原因，把处于等待状态的进程排成多个阻塞队列
- 创建状态
- 一个进程刚刚建立，但还未将它插入就绪队列时的状态(fork,CreateProcess)，通常是PCB已经创建，但还没有加载到内存中
- 终止状态
- 一个进程已经正常结束(exit,TerminateProcess)或异常结束， OS已将它从就绪队列中移出，但尚未将它撤消时的状态
等待就是阻塞等待就是阻塞等待就是阻塞就绪和运行可以相互变化就绪和运行可以相互变化就绪和运行可以相互变化等待阻塞是一个特殊的中间过程，只能从运行到就绪等待阻塞是一个特殊的中间过程，只能从运行到就绪等待阻塞是一个特殊的中间过程，只能从运行到就绪
新建→就绪
- 许可（加载）：操作系统准备好接纳一个新进程
- 不许可：超过操作系统最大进程/虚存数量限制
就绪→运行
- 调度：调度进程选择一个新进程运行
运行→结束
- 释放：进程已经完成，或出错结束
运行→阻塞
- 等待事件：请求系统调用，如
- 等待I/O操作完成（printf、scanf）
- 等待新任务的到来（等待网络发数据包）
- 访问暂不能被使用的资源（其他进程正在使用打印机）
- 等待另一个进程提供输入（wait）
- 申请外设
阻塞→就绪
- 事件发生：如I/O完成
运行→就绪
- 时间片到：Linux-5~800ms；Windows-20ms
- 抢占（preempted）：更高优先级进程已就绪
- 自愿释放：如周期性维护进程
挂起状态
使正在执行的进程暂停执行；若此时进程正处于就绪状态而未执行，则该进程暂不接受调度，我们把这种静止状态称为挂起（suspend）状态。
引入挂起状态的原因有：
- 交换(Swapping) 操作系统需要释放内存空间，调节负荷
- 其他OS原因 OS挂起后台进程、工具进程，或怀疑有问题的进程
- 用户请求 用户希望调试进程或连接进程资源
- 父进程请求 挂起后代进程，以便考查修改，或协调子进程的活动
- 定时 周期性的记账或系统监视进程
进程控制块
进程控制块PCB(Process Control Block)记录了操作系统所需的，用于描述进程的当前情况以及管理进程的全部信息，是操作系统中最重要的记录型数据结构。
对系统而言，PCB是进程存在的惟一标志。
PCB常驻内存。操作系统将所有的PCB组织成若干个队列，存放在系统内核空间中专门开辟的区域内
- 进程标识符 用于唯一标识一个进程。
- 内部标识符 操作系统为每一个进程赋予一个惟一的
- 数字标识符（进程的序号，Process ID，PID ）
- 用户标识符（User ID，UID）
- 父进程标识符（Parent PID，PPID
- 处理机状态信息 又称上下文（Context）
- 通用寄存器（General Purpose Registers），又称用户可见寄存器，8~32个/CISC，100+个/RISC
- 程序计数器（Program Counter），指令计数器，存放下一条指令的地址
- 程序状态字（Program State Word），存放状态信息，如x86的EFLAGS
- 栈指针（Stack Pointer），指向栈顶
- 进程调度信息
- 进程状态：运行、就绪、等待、停止……
- 优先级
- 事件：在等待的具体事件，即阻塞原因
- 其它信息：已等待时间，已使用CPU时间
- 进程控制信息
- 内存相关：程序和数据的（首）地址、段表、页表
- 进程间通信：标记、信号量、消息队列……
- 资源清单：打开的文件、设备……
- 连接指针：指向其它PCB
进程(仅概念)
进程的创建
引起创建进程的事件
- 用户登录（由系统内核创建）
- 作业调度（由系统内核创建）
- 提供服务（由系统内核创建）
- 应用请求（由应用进程自已创建）
- 子进程与父进程的关系可以是并发或递归
创建进程的基本过程：创建原语Creat
（1）申请空白PCB；
（2）为新进程的程序和数据分配所需资源（内存、文件、I/O和CPU时间）
（3）初始化PCB。向该PCB中填写各种参数；
（4）New→Ready，将新进程插入到就绪队列。
进程的终止
- 正常结束 进程任务已完成，退出运行。
- 异常结束 如：越界错误、无可用内存、保护错、无效指令、特权指令错、超时、算术运算错、I/O故障等
- 外界干预 进程应外界的请求而终止运行。包括：操作员或操作系统干预、父进程请求、父进程终止。
进程的终止过程是： 终止原语Halt
（1）根据进程PID检索出该进程的PCB，读出进程状态
（2）若进程处于执行状态，立即终止(Run→Terminate)，并重新进行调度 （3）某些系统可能将其子孙进程终止
（4）把进程拥有的资源归还给父进程或者系统内核
（5）等待其他程序来搜集信息。
进程的阻塞
引起进程阻塞的事件
- 请求系统提供服务
- 启动某种操作
- 新数据尚未到达
- 无新工作可做
进程的阻塞(等待)过程 阻塞(等待)原语block
(1) 进程立即停止执行，把其PCB中的状态Run→Blocked；
(2) 将其PCB插入到相应的阻塞队列中去；
(3) 转调度程序进行重新调度，并进行切换
进程的唤醒
引起进程唤醒的事件——被阻塞进程所期待的事件出现
进程的唤醒过程:唤醒原语wakeup
(1) 把被阻塞进程从相应事件的阻塞队列中移出;
(2) 将其PCB中的状态由Blocked→Ready;
(3) 该PCB插入到就绪队列中。
进程通信
合作的进程通过进程间通信机制实现数据和信息的交换的锁、信号量、管程等同步机制，都可以交换进程的信息，也属于进程通信（但是传输的信息量很小，称为低级通信）
高级通信机制：
- 共享内存：进程通过共享某些数据结构或内存区域通信，程序员负责处理同步问题
- 消息传递：以格式化的消息(message)为单位，用户通过OS提供的一组通信原语(send, receive)进行通信。当前应用最广泛的IPC机制
- 直接通信
- send (P, message) – 发送信息到进程P
- receive(Q, message) – 从进程Q接受消息
- 间接通信（借助中介数据结构）
- send(A, message) – 发送消息（信件）到队列A
- receive(A, message) – 从队列A接受消息（信件）
- 信���通信：A=mailbox
- 管道通信：用一个共享文件连接一个读进程和一个写进程采用先进先出（FIFO）机制的循环队列/缓冲区管道通信机制必须提供互斥、同步和确定对方是否存在的协调能力
- 客户机-服务器系统：在网络环境的各种应用中已经成为主流 主要实现方法
- 套接字（Socket）
- 远程过程调用（Remote Procedure Call, RPC）
线程
进程 = 一个资源 + 多个指令执行序列（即多个线程）
只切换指令执行序列，而不切换资源保留了并发的优点，避免了进程切换代价
它是进程中的指令执行流的最小单元，是CPU调度的基本单位。
现代操作系统将进程并发调度的部分和占有资源的部分分离
- 进程作为资源分配的基本单位
- 线程作为系统调度的基本单位，是能独立运行的基本单元（线程可以并行在多核处理器上）
- 资源共享：默认共享地址空间、文件等
- 响应性：拆分应用中的多种活动
- 考虑字处理程序
- 轻量级：创建、撤销、切换线程的代价比进程小
- 可扩展：多个线程可在多CPU系统��并行
- 可以并发
- 线程仅拥有少量自己的资源（寄存器、PC指针、栈指针等上下文信息，不能共享），多是共享的
- 系统开销比进程小
- 独立性比进程小
- TCB（线程控制块） 缺点：任何一个线程出问题，可能导致整个进程崩溃
用户级线程
用户级线程是指不需要内核支持而在用户程序中实现的线程，它的内核的切换是由用户态程序自己控制内核的切换，不需要内核的干涉。但是它不能像内核级线程一样更好的运用多核CPU。
优点：
（1） 线程的调度不需要内核直接参与，控制简单。
（2） 可以在不支持线程的操作系统中实现。
（3） 同一进程中只能同时有一个线程在运行，如果有一个线程使用了系统调用而阻塞，那么整个进程都会被挂起，可以节约更多的系统资源。
缺点：
（1） 一个用户级线程的阻塞将会引起整个进程的阻塞。
（2） 用户级线程不能利用系统的多重处理，仅有一个用户级线程可以被执行。
内核级线程
切换由内核控制，当线程进行切换的时候，由用户态转化为内核态。切换完毕要从内核态返回用户态。可以很好的运用多核CPU，就像Windows电脑的四核八线程，双核四线程一样。
优点：
（1）当有多个处理机时，一个进程的多个线程可以同时执行。
（2） 由于内核级线程只有很小的数据结构和堆栈，切换速度快，当然它本身也可以用多线程技术实现，提高系统的运行速率。
缺点：
（1） 线程在用户态的运行，而线程的调度和管理在内核实现，在控制权从一个线程传送到另一个线程需要用户态到内核态再到用户态的模式切换，比较占用系统资源。（就是必须要受到内核的监控）
关联性
（1） 它们之间的差别在于性能。
（2） 内核支持线程是OS内核可感知的，而用户级线程是OS内核不可感知的。
（3） 用户级线程的创建、撤消和调度不需要OS内核的支持。
（4） 用户级线程执行系统调用指令时将导致其所属进程被中断，而内核支持线程执行系统调用指令时，只导致该线程被中断。
（5） 在只有用户级线程的系统内，CPU调度还是以进程为单位，处于运行状态的进程中的多个线程，由用户程序控制线程的轮换运行；在有内核支持线程的系统内，CPU调度则以线程为单位，由OS的线程调度程序负责线程的调度。
（6） 用户级线程的��序实体是运行在用户态下的程序，而内核支持线程的程序实体则是可以运行在任何状态下的程序。 
处理机调度与死锁
调度
调度是为同时需要资源的多方，分配所需资源的方法。 凡有稀缺资源(“排队”)之处，皆有调度。
调度的资源
- 处理机（CPU） 从就绪队列中挑选下一个占用CPU运行的进程
- 临界区 信号量V操作后，从等待队列挑选一个进程唤醒
- 内存 从外存的挂起队列挑选一个进程激活
- I/O设备 决定I/O设备处理等待队列中的哪个I/O请求
调度的时机
- 进程从运行态切换到等待态(非抢占调度) I/O操作、wait操作、sleep……
- 进程退出(非抢占调度) return、exit、出错……
- 进程时间片完(抢占调度) 高优先级进程抢夺 时钟中断
- 进程从等待到就绪、新建(抢占调度) I/O中断、fork
