计算机编程基础_操作系统
[TOC]
操作系统概览
操作系统是管理计算机硬件和软件资源的计算机程序
操作系统是管理硬件、提供用户交互的软件系统
多道程序设计：是指在计算机内存中同时存放几道相互独立的程序，使它们在管理程序控制之下，相互穿插的运行。 两个或两个以上程序在计算机系统中同处于开始到结束之间的状态。这就称为多道程序设计。多道程序技术运行的特征：多道、宏观上并行、微观上串行。
操作系统基本功能
操作系统统一管理着计算机资源，处理器资源、存储器资源、IO设备资源以及文件资源。
操作系统实现了对计算机资源的抽象
操作系统提供了用户与计算机之间的接口
操作系统相关概念
并发性、共享性、虚拟性、异步性
并发性
并行是指两个或多个事件可以在同一个时刻（时间点）发生。需要作用在多核处理器上。
并发是指两个或多个事件可以在同一个时间间隔发生。
共享性
共享性表现为操作系统中的资源可供多个并发的程序共同使用。
互斥共享形式：当资源被程序A占用时，其他程序想使用的话只能等待。比如：打印机每次只能打印一份资料。
同时访问形式：某种资源在一段时间（一个时间间隔）内并发地被多个程序访问。比如：在一个时间间隔内有多个程序需要写数据到硬盘上（并发）。注意每个时刻只能有一个程序在执行写硬盘操作
虚拟性
虚拟性表现为把一个物理实体转变为若干个逻辑实体
物理实体是真实存在的，逻辑实体是虚拟的
虚拟性的技术主要有时分复用技术和空分复用技术
时分复用技术：资源在时间上进行复用，不同程序并发使用。多道程序分时使用计算机的硬件资源。可以提高资源的利用率。时分复用技术又分为虚拟处理器技术和虚拟设备技术。
虚拟处理器技术借助多道程序设计技术，为每个程序建立进程，多个程序分时复用处理器。
虚拟设备技术将物理设备虚拟为多个逻辑设备，每个程序占用一个逻辑设备，多个程序通过逻辑设备并发访问。
空分复用技术：资源在空间上进行复用。用来实现虚拟磁盘，虚拟内存等，提高资源的利用率，提升编程效率。
虚拟磁盘：将物理磁盘虚拟为逻辑磁盘。比如电脑的C、D、E盘。逻辑磁盘之间相互隔离让我们使用起来更加安全、方便。
虚拟内存：在逻辑上扩大程序的存储容量。程序可以使用比时间内存更大的容量。可以提高编程效率。
异步性
在多道程序环境下，运行多个进程并发执行。
进程在使用资源时可能需要等待或放弃。
进程的执行并不是一气呵成的，而是以走走停停的形式推进。
进程以不可预知的速率向前推进，不知道程序何时执行，也不知道程序何时暂停，也不知道程序何时完成。
进程管理之进程实体
为什么需要进程？
进程是系统进行资源分配和调度的基本单位。进程作为程序独立运行的载体保障程序正常执行（资源隔离）。进程的存在使得操作系统资源的利用率大幅提升。
进程的实体
主存中的进程形态：
标识符，唯一标记一个进程，用于区别其他进程
状态，标记进程的进程状态，如：运行态
程序计数器，进程即将被执行的下一条指令的地址
内存指针，程序代码、进程数据相关指针
上下文数据，进程执行时处理器存储的数据
IO状态信息，被进程IO操作所占用的文件列表
记账信息， 使用处理器时间、时钟数总和等
进程控制块（PCB）：用于描述和控制进程运行的通用数据结构。记录进程当前状态和进程控制运行的全部信息。PCB使得进程是能够独立运行的基本单位。
PCB是操作系统进行调度经常会被读取的信息。
PCB是常驻内存的，存放在系统专门开辟的PCB区域内。
进程与线程
进程（Process）
进程是系统进行资源分配和调度的基本单位，一个进程可以有多个线程。
线程（Thread）
线程是操作系统进行运行调度的最小单位，线程包含于进程中，是进程中实际运行工作的单位。线程共享进程的资源
进程管理之五状态模型
五状态指的是：创建、就绪、终止、阻塞、执行这五个状态
就绪状态：其他资源都准备好，只差CPU资源的状态为就绪状态。当进程分配到CPU资源就可以立即运行。
执行状态：进程获得CPU资源，其程序正在执行称为执行状态。在单处理器机器中，某个时刻只能有一个进程处理执行状态。
阻塞状态：进程因某种原因（比如其他设备未就绪而无法继续执行）从而放弃CPU的状态称为阻塞状态
创建状态：创建进程时拥有PCB（进程控制块）但其他资源尚未就绪的状态。操作系统提供了fork函数接口创建进程。
终止状态：进程结束由系统清理或者归还PCB的状态称为终止状态。
进程管理之进程同步（通信）
为什么需要进程间同步
进程间的同步目的是对竞争资源在多进程间进行使用次序的协调，使得并发执行的多个进程之间可以有效使用资源和相互合作。（如果不进行同步，那么程序计算结果可能不符合预期，程序甚至死锁）
生成者消费者模型
由于每个任务的操作并非原子操作，那么需要对每个任务进行加锁，否则计算结果将是未知的。
哲学家进餐问题
有五个哲学家，他们的生活方式是交替地进行思考和进餐，哲学家们共同使用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五支筷子。平时哲学家们只进行思考，饥饿时则试图取靠近他们的左、右两支筷子，只有两支筷子都被他拿到的时候就能进餐，进餐完毕之后，放下左右筷子继续思考
一个极端的例子是：五个哲学家同时拿起了左边筷子，发现右边的筷子被拿了然后都等待右边筷子释放，五个哲学家饿死
进程间同步的原则
临界资源
临界资源指的是一些虽作为共享资源却又无法同时被多个线程共同访问的共享资源。当有进程在使用临界资源时，其他进程必须依据操作系统的同步机制等待占用进程释放该共享资源才可重新竞争使用共享资源。
同步原则
空闲让进：资源无占用，允许使用
忙则等待：资源有占用，请求进程等待
有限等待：保证有限等待时间能够使用资源
让权等待：等待时，进程需要让出CPU
进程间同步的方法
消息队列
共享存储
信号量
线程同步
进程内多线程也需要同步
线程间同步的方法
互斥量
读写锁
自旋锁
条件变量
Linux的进程管理
Linux进程的相关概念
进程的类型
前台进程：具有终端，可以和用户交互的进程
后台进程：不占用终端的进程，基本上不和用户交互，优先级比前台低
守护进程：是特殊的后台进程。很多守护进程在系统引导的时候启动，一直运行直到系统关闭。（守护进程的名字一般以"d"结尾，比如：crond、sshd、httpd、mysqld）
fg命令将一个后台命令调换至前台终端继续执行
bg命令将一个后台暂停的命令编程继续执行
ctrl+z将前台工作暂停
进程的标记
进程ID（PID）是进程的唯一标记，每个进程拥有不同的ID
进程ID是一个非负整数，最大值由操作系统限定。
操作系统提供fork函数接口创建进程
父子进程关系可以通过pstree命令查看
PID为0的进程为idle进程，是系统创建的第一个进程····
PID为1的进程为init进程，是0号进程的子进程，完成系统初始化。是所有用户进程的祖先进程。
Linux相关命令
ps命令
查看进程ps -aux，如果增加参数--sort=pcpu那么将按照CPU排序，增加参数--sort=pmem那么将按照MEM排序。
ps命令常用语显示当前进程的状态
ps命令常配合aux参数或ef参数和grep命令检索特定进程
top命令
top命令可以查看系统资源使用情况
kill命令
kill命令发送指定信号给进程
kill -l可以查看操作系统支持的信号。
kill 9只有信号9可以无条件终止进程。对于其他信号进程有权忽略。
作业管理之进程调度
进程调度概述
进程调度是指计算机通过决策决定哪个就绪进程可以获得CPU使用权。
保留旧进程的运行信息，请求旧进程（收拾包袱）
选择新进程，准备运行环境并分配CPU（新进驻）
就绪队列排队机制：将就绪进程按照一定的方式排成队列，以便调度程序可以最快找到就绪进程。
选择运行进程的委派机制：调度程序以一定的策略选择就绪进程，将CPU资源分配给它。
新老进程的上下文切换机制：保持当前进程的上下文信息，装入被委派执行进程的运行上下文。
非抢占式调度：处理器一旦分配给某个进程，就让该进程一直使用下去。调度程序不以任何原因抢占正在被使用的处理器。直到进程完成工作或进程主动让出CPU（比如：IO阻塞）才会让出CPU。
抢占式调度：允许调度程序以一定策略暂停当前运行的进程。保存好旧进程的上下文信息，分配CPU给新进程。
进程调度算法
先来先服务调度算法
从就绪队列中依次取出任务
短进程优先调度算法
调度程序优先选择就绪队列中估计运行时间最短的进程。短进程优先调度算法不利于长作业进程的执行。
高优先权优先调度算法
进程附带优先级，调度程序优先选择权重高的进程。（前台进程与用户交互较多，因此相对后台进程来说权重较高）
时间片轮转调度算法
按先来先服务的原则排列就绪进程，每次从队首取出待执行进程，分配一个时间片执行，是相对公平的调度算法，但不能保证及时响应用户。
作业管理之死锁
死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者彼此通信而造成的一种阻塞现象，若无外力作用，他们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在相互等待的进程称为死锁进程。
死锁产生
资源竞争
共享资源数量不满足各个进程的需求，各个进程之间发生资源进程导致死锁。
假设现在有两个进程，他们都需要打印机、传真机资源。 进程1现在获取到了传真机资源，进程2现在获取到了打印机资源。进程1等待打印机资源被释放，进程2等待传真机资源被释放。相互等待而自身占用的资源不释放。
进程调度顺序不当
假设现在有两个进程，他们都需要打印机、传真机资源。按调度顺序A→B→C→D，将会死锁。如果按调度顺序A→D→B→C。
死锁的四个必要条件
互斥条件、请求保持条件、不可剥夺条件、环路等待条件。
互斥条件
进程对资源的使用是排他性（非共享）的作用
某资源只能由一个进程使用，其他进程需要使用只能等待
请求保持条件
进程至少保持一个资源，又提出新的资源请求
（请求的）新资源被占用，请求被阻塞
被阻塞的进程不释放自己保持的资源（我们所请求的资源无法得到）
不可剥夺条件（非抢占式）
进程获得的资源在未完成使用前不能被剥夺，获得的资源只能由进程自身释放
环路等待条件
发生死锁时，必然存在进程资源环形链
预防死锁的方法
通过避免一个或多个产生死锁必要条件来预防
摒弃不可剥夺条件：当一个进程请求新的资源得不到满足时，必须释放占用的资源。进程运行时占有的资源可以被释放，意味着可以被剥夺。
摒弃环路等待条件：可用资源线性排序，申请必须按照需要递增申请。线性申请不再形成环路。
银行家算法
是一个可操作的著名的死锁避免算法。以银行借贷系统分配策略为基础的算法。
客户申请的贷款是有限的，每次申请需声明最大资金量
银行家在能够满足贷款时，都应该给用户贷款
客户在使用贷款后，能够及时归还贷款
将每个进程执行所需的资源信息扣除已分配的资源信息得出进程完成还需分配的资源信息，根据当前可分配资源信息计算出有限执行P2，将资源分配给P2后A：1，B：0，C：1，D：0，待P2进程执行完毕后归还资源，可分配资源则变为A：2，B：9，C：5，D：2。此时资源足够P1、P2、P3等进程使用。
存储管理之内存分配和回收
早期计算机编程并不需要过多的存储管理。随着计算机和程序越来越复杂，存储管理成为必要。
确保计算机有足够的内存处理数据
确保程序可以从可用内存中获取一部分内存使用
确保程序可以归还使用后的内存以供其他程序使用
内存分配的过程
单一连续分配
单一连续分配是最简单的内存分配方式。只能在单用户、单进程的操作系统中使用。
固定分区分配
固定分区分配是支持多道程序的最简单存储分配方式。内存空间被划分为若干固定大小的区域。每个分区只提供给一个程序使用，互不干扰。
动态分区分配
根据进程实际需要，动态分配内存空间。有多种分配算法及相关数据结构。
动态分区空闲表数据结构：使用一个列表存储空间区是否被使用，0代表未被使用，1代表已被使用。
动态分区空闲链数据结构：使用双向链表存储未被使用的空闲区地址（一个优化是将相邻的空闲区合并，记录当前合并的空间区的总容量）
动态分区分配相关算法
首次适应算法（FF算法）
分配内存时从开始顺序查找适合内存区。
若没有合适的空闲区，则该次分配失败。
每次从头部开始，使得头部地址空间不断被划分。
最佳适应算法（BF算法）
空闲区链表按照容量大小排序。
遍历空闲区链表找到最佳合适空闲区。
快速适应算法（QF算法）
快速适应算法要求多个空闲区链表
每个空闲区链表存储一种容量的空闲区
内存回收的过程
对于第一种：不需要新建空闲链表节点，只需要把空闲区1的容量增大为原空闲区加回收区容量。
对于第二种：将回收区与空闲区1合并，合并后的空闲区使用原回收区的地址。
对于第三种：将空闲区1、空闲区2和回收区合并，新的空闲区使用空闲区1的地址。
对于第四种：为回收区创建新的空闲节点，插入到相应的空闲区链表中去。
存储管理之段页式存储管理
页式存储管理
将进程逻辑空间分成若干大小的页面
相应的把物理内存空间分成与页面大小的物理块
以页面为单位把进程空间装进物理内存中分散的物理块
注意：如果有一段连续的逻辑分布在多个页面中，将大大降低执行效率。
页面
字块是相对于物理设备的定义；页面则是相对逻辑空间的定义。
页面大小应该适中（大小一般在512B～8K），过大难以分配，过小内存碎片过多。
页表
页表记录进程逻辑空间与物理空间的映射。
多级页表
现代计算机系统中，可以支持非常大的逻辑地址空间（(1<<32)~(1<<64)），这样，页表就变得非常大，要占用非常大的内存空间。如：具有32位逻辑地址空间的分页系统，规定页面大小为4KB，则每个进程页面中的页表可达（1<<20=1<<(32-12)）个，如果每个页表项占用1Byte，那么每个进程仅仅页表就要占用1MB的内存空间。
段式存储管理
将进程逻辑空间划分成若干段（非等分）
段的长度由连续逻辑的长度决定
段表
由于段式存储是按逻辑空间划分的，并非等分划分，还需要额外为维护段长的信息。
页式存储和段式存储对比
相同点：段式存储和页式存储都离散地管理了进程的逻辑空间
不同点：
页是物理单位，段式逻辑单位
分页是为了合理利用空间，分段是满足用户要求
页大小由硬件固定，段长度可动态变化
段页式存储管理
分页可以有效提高内存利用率（虽然说存在内存碎片），分段可以更好满足用户需求。
两者结合，形成分段式存储管理。
先将逻辑空间按段式管理分成若干段
再把段内空间按页式管理等分成若干页
存储管理之虚拟内存
虚拟内存概述
有些进程实际需要的内存很大，超过物理内存的容量（比如一个游戏10G+，但是我们的电脑只有8G却可以运行该游戏）。多道程序设计，使得每个进程可用物理内存更加稀缺。不可能无限增加物理内存，物理内存总有不够的时候。
虚拟内存是操作系统内存管理的关键技术。使得多道程序运行和大程序运行成为现实。把程序使用内存划分，将部分暂时不使用的内存放置在辅存
程序的局部性原理
局部性原理是指CPU访问存储器时，无论是存取指令，还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。
程序运行时，无需全部装入内存，装载部分即可。如果访问页不在内存，则发出缺页中断，发起页面置换。从用户层面看，程序拥有很大的空间，即是虚拟内存。
虚拟内存实际是对物理内存的补充，速度接近于内存，成本接近于辅存。
虚拟内存的置换算法
替换策略发生在Cache-主存层次、主存-辅存层次。
Cache-主存层次的替换策略主要是为了解决速度问题。
主存-辅存层次的替换策略主要是为了解决容量问题。
高速缓存的替换时机
主存页面的替换时机
先进先出算法（FIFO）
最不经常使用算法（LRU）
最近最少使用算法（LFU）
Linux的存储管理
页内碎片和页外碎片
页内碎片
指的是已经被分配出去（能明确指出属于哪个进程）的内存空间大于请求所需的内存空间，不能被利用的内存空间就是页内碎片。
外部碎片
指的是还没有分配出去（不属于任何进程），但是因为大小而无法分配给申请内存空间的新进程的内存空间就是页外碎片。
buddy内存管理算法
buddy算法是经典的内存管理算法，是基于计算机处理二进制的优势具有极高的效率，主要是为了解决内存外碎片的问题。
buddy算法努力让内存分配与相邻内存合并能快速进行。
buddy算法内存分配原则
buddy算法分配空间向上取整为2的幂大小。比如：70k -> 128k，127k -> 256k，888k -> 1024k。
伙伴系统
“伙伴”指的是内存的“伙伴”
一片连续内存的“伙伴”是相邻的另一片大小一样的连续内存
buddy算法创建一系列空闲块链表，每一种都是2的幂。
分配与回收100k内存
分配100k内存
100k向上取2的幂=128k
查询是否有128k空闲内存块？
没有！查询是否有256k空闲内存块？
没有！查询是否有512k空闲内存块？
没有！查询是否有1M空闲内存块？
有，摘下1M空闲内存块，分配出去
拆下512k放在512k的空闲链表，其余的分配出去
拆下256k放在256k的空闲链表，其余的分配出去
拆下128k放在128k的空闲链表，其余的分配出去
分配完毕
最终我们给它分配了128k，但是实际上只需要100k，因此会产生页内碎片问题。
回收100k内存
判断刚才分配的内存伙伴在空闲链表上吗？
在！移除伙伴，合并为256k空闲内存，判断
在！移除伙伴，合并为512k空闲内存，判断
在！移除伙伴，合并为1M空闲内存
插入1M空闲链表，回收完成
Linux交换空间
交换空间（swap）是磁盘的一个分区
Linux物理内存满时，会把一些内存交换至swap空间
swap空间时初始化系统时配置的
冷启动内存依赖
系统睡眠依赖
大进程空间依赖
swap空间与虚拟内存的对比
相同点：都存在于磁盘上，与主存发生置换。
不同点：swap空间时操作系统概念，虚拟内存时进程概念；swap空间解决系统物理内存不足问题，虚拟内存解决进程物理内存不足问题。
注意：一般不建议使用交换空间，因为交换空间是在磁盘上的，这样会拖慢操作系统。比如腾讯云服务器的Linux就不设置交换空间。
操作系统的文件管理
文件的逻辑结构
逻辑结构文件类型
有结构文件
文件内容由定长记录和可变长记录组成
定长记录存储文件格式、文件描述等结构化数据项
可变长记录存储文件具体内容
无结构文件
也称为流式文件，文件内容长度以字节为单位。比如：exe文件、dll文件、so文件等。
顺序文件
顺序文件指的是按顺序存放在存储介质中的文件。顺序文件是所有逻辑文件当中存储效率最高的。
磁带的存储特性使得磁带文件只能存储顺序文件。
索引文件
可变长文件不适合使用顺序文件格式存储
索引文件是为了解决可变长文件存储而发明的一种文件格式，索引文件需要配合索引表完成存储操作。
辅存的存储空间分配
辅存的分配方式
连续分配：顺序读取文件内容非常容易，速度更快。对存储要求高，要求满足容量的连续存储空间。
链接分配：可以将文件存储在离散的盘块中，需要额外的存储空间存储文件的盘块链接顺序。
隐式分配的下一个链接指向存储在当前盘块内，适合顺序访问，随机访问效率很低。可靠性差，任何一个链接出问题都影响整个文件。
FAT不支持高效的直接存储（FAT记录项多）
检索时FAT表占用较大的存储空间（需要将整个FAT加载到内存）
索引分配（主流操作系统文件管理都采用该分配方式）：把文件的所有盘块集中存储（索引），读取某个文件时，将索引读取进内存即可。
每个文件拥有一个索引块（索引块会占用一个额外的盘块），记录所有盘块信息。索引分配方式支持直接访问盘块。文件较大时，索引分配方式具有明显优势。
存储空间管理
空闲表：空闲盘区的分配与内存分配类似。相关算法有首次适应算法、循环适应算法、快速适应算法等。回收过程也与内存回收类似。
空闲链表：把所有空闲盘区组成一个空闲链表，每个链表节点存储空闲盘块和空闲的数目。
位示图：维护成本很低，可以非常容易找到空闲盘块，使用0/1比特位，占用空间很小。
目录管理
目录树
任何文件或目录都只有唯一路径。
文件描述信息
文件标识符
文件类型
文件权限
文件物理地址
文件长度
文件连接计数
文件存取时间
索引节点编号
文件状态
访问计数
链接指针
Linux文件基本操作
Linux目录
Linux一切皆文件
相对路径
绝对路径
Linux文件常用操作
创建、删除、读取、写入
Linux文件类型
套接字（s）
普通文件（-）
目录文件（d）
符号链接（l）
设备文件（b、c）
FIFO（p）
Linux的文件系统
文件系统概览
FAT（file allocation table）
FAT16、FAT32等，微软Dos/Windows使用的文件系统，使用一张表保存盘块信息。
NTFS（new technology file system）
WindowsNT环境的文件系统，对FAT进行了改进，取代了旧的文件系统
EXT（extended file system）
扩展文件系统，Linux的文件系统，EXT2/3/4数字代表第几代。
Ext文件系统
Boot Sector：启动扇区，安装开机管理程序。
Block Group：块组，存储数据的实际位置。
Inode Table
Inode Table存放文件Inode的地方
每一个文件（目录）都有一个Inode
是每一个文件（目录）的索引节点。
文件名不是存放在Inode节点上的，而是存放在目录的Inode节点。
列出目录文件的时候无需加载文件Inode
Inode bitmap
记录已分配的Inode和未分配的Inode
Data block
data block是存放文件内容的地方。每个block都有唯一的编号。文件的block记录在文件Inode上
Block bitmap
记录data block的使用情况。
Superblock
记录整个文件系统相关信息的地方。
记录Block和Inode的使用情况（时间信息、控制信息等）
操作系统的设备管理
广义的IO设备
对CPU而言，凡是对CPU进行数据输入的都是输入设备。
对CPU而言，凡是对CPU进行数据输出的都是输出设备。
按使用特性分类
按信息交换的单位分类
按设备的共享属性分类
按传输速率分类
IO设备的缓冲区
减少CPU处理IO请求的频率
提高CPU与IO设备之间的并行性
专用缓冲区只适用于特定的IO进程。当这样的IO进程比较多时，对内存的消耗也很大。操作系统划出可供多个进程使用的公共缓冲区，称之为缓冲池。
SPOOLing技术
SPOOLing技术时一种虚拟设备技术。
是关于慢速字符设备如何与计算机主机交换信息的一种技术。利用高速共享设备将低速的独享设备模拟为高速的共享设备。逻辑上，系统为每一个用户都分配了一台独立的高速独享设备。
SPOOLing技术把同步调用低速设备改用异步调用
在输入、输出之间增加了排队转储环节（输入井、输出井）
SPOOLing负责输入（出）井与低速设备之间的调度
逻辑上，进程直接与高速设备交互，减少了进程的等待时间
最后更新于
这有帮助吗？
