操作系统-basic concept

This is my study note of operating system.

这段学习中使我印象最深的两句话：

一切皆文件，Linux系统下，一切皆文件，硬件设备也是文件
有问题找男人：可以使用man来查看命令帮助手册

Alt text

从图中我们可以看出操作系统是硬件和软件间的媒介，是最基本的软件。

/etc下主要配置文件名解释

file	explain
/etc/hosts	主机名到IP地址的映射关系的文件
/etc/resolv.conf	DNS服务的配置文件
/etc/gateways	建立动态路由需要用到的文件
/etc/services	定义了网络服务的端口

命令返回码

返回码	explain
0	操作执行成功
1	操作不允许
2	没有文件或目录
3	进程不存在
4	系统调用终端
5	I/O错误
6	无此设备或地址
7	参数列表过长
8	执行命令格式错误
9	错误的文件描述
10	不存在子进程
11	暂时性缺少资源
12	无法分配至内存空间
13	权限拒绝

linux文件系统

划分

操作系统：ext文件系统、ext2文件系统
日志文件系统：ext3文件系统、ext4文件系统、Reiser文件系统、JFS文件系统、XFS文件系统
写时复制文件系统：ZFS文件系统、Btrf文件系统

细节

链接文件以及顺序文件

1 2	链接文件就像数据结构中的链表，只能顺序访问顺序文件可以随机访问

进程

进程是程序运行的实例。执行前需要将程序放到内存中，才能被CPU所运行。

程序的运行

首先从文件中找到对应的运行文件（对应的存放位置）
其次将程序放到内存中
紧接交给CPU进行处理
最后将对应的设备分配给进程

并发和并行

并发是指两个或两个以上进程同时发生，这种“同时”在宏观上是同时的，但是在微观上是由于时间片的轮换。
并行是指多个进程同时发生，此时无论是宏观还是微观都同时。

进程通信

共享存储
消息传递

进程间的数据交换以格式化的消息为单位。

消息传递分为两种方式：

直接通信方式（消息直接挂到接收进程的消息缓冲队列上）
间接通信方式（消息接收和发送通过中间实体（信箱））
管道通信

Alt text

1、管道通信只能采用半双工，如果需要双向通信则需要设置两个管道。

2、各进程间要互斥地访问管道

3、数据以字节流的形式写入管道，管道写满后，写进程堵塞，读进程运行，等到管道内数据全部读完以后，读进程堵塞，写进程运行。

4、读进程最多只有一个

进程死锁

进程死锁的四个必要条件：

互斥
请求和保护条件
循环等待

非抢占

互斥
指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。

请求和保护条件
指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。

循环等待
指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

非抢占
指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

进程间使用临界资源

进程可以互斥的进入各自的同类资源临界区。

临界资源：只允许一个进程进行访问的资源，比如打印机。
临界区：访问临界资源的代码。

注意不同临界区访问同一个临界资源也需要互斥。

进程控制

创建进程

1	需要初始化PCB、分配系统资源。

创建态->就绪态

1	需要修改PCB内容和对应队列。

+就绪态->运行态

1	恢复进程运行环境，修改PCB内容和对应队列。

+运行态->终止态

1	回收资源，撤销PCB。

+运行态->就绪态

1	保存进程运行环境，修改PCB内容和对应队列（进程切换）。

+运行态->阻塞态

1	保存进程运行环境，修改PCB内容和对应队列。

+阻塞态->就绪态

1	修改PCB内容和对应队列，如果是申请资源的任务，还要为其分配资源。

进程调度

进程调度简单来说就执行了两件事：1保存当前进程的各数据 2.恢复新进程的各数据

当前运行进程主动放弃（正常终止，异常、主动请求阻塞）
当前运行进程被动放弃（时间片轮转、更紧急的作业、更高优先级的任务进入队列）

不能进行进程调度的情况：1.处理中断时 2.进程在操作系统内核临界区 3.原子操作中

中断的分类：

内中断（也称异常、意外、陷入），分为自愿中断（指令结束）和强迫中断（故障、软件中断）
外中断（外设请求、人工干预）

进程调度的方式：

剥夺式可被多种情况抢占。（可采用时间片等方式）
非剥夺式只有允许主动放弃处理机。（开销小，但不能及时处理紧急事件）

进程的组织

链接方式：

按照进程状态将PCB分为多个队列
操作系统持有指向各个队列的指针

索引方式：

根据进程状态不同，建立几张索引表
操作系统持有指向各个索引表的指针

进程同步和进程互斥

对临界资源的访问可以总结为四个部分：

进入区负责检查是否可进入临界区（设置标志位）
临界区负责访问临界区代码
退出区负责接触进入区设置的标志位
剩余区做其他处理

四大原则：

1．空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区

2．忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待

3．有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）

4．让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

进程互斥的软件实现方法：

单标志法

1	每个进程进入临界区的权限只由另一个进程赋予

此时面对一个问题，只有访问了前一个进程，后一个进程才能被访问，这很容易违背空闲让进原则。

双标志检查法
1
使用布尔型数组表示每个进程进入临界区的意愿。
此时也面临一个问题，若是按照1526的顺序运行，此时两个进程会同时访问临界区，造成错误。
Peterson法
1
引入让权思想。
但是未遵守让权等待。

进程互斥的硬件实现方法：

中断屏蔽方法

1	利用“开\关中断指令”，跟原语的思想一样，某进程开始访问到结束访问都不可被抢断，因此不会发生进程切换。

不适用于多处理机（其余处理机的中断仍在运作），适合用于操作系统内核进程。

TestAndSet（TS指令）
TS（或称TSL）指令是由硬件实现的。

Alt text

缺点在于不满足让权等待，其余线程会因为无法进入临界区而占用CPU并不断循环。

Swap（或称XCHG）

同样不满足让权等待。

线程

引入线程后，程序流执行流的最小单位就变为了线程。引入线程后，进程只是资源分配的基本单位，任务的调度由线程执行。

线程锁

常见的线程同步锁有：

信号量
读写锁
互斥量
事件
临界区

上述锁中，互斥量和临界区为递归锁，其余为非递归锁。同一个线程可以多次获取同一个递归锁，不会产生死锁。而如果一个线程多次获取同一个非递归锁，则会产生死锁。

线程分类

用户级线程

1	用户级线程由应用程序通过线程库来实现。此时，线程切换在用户态就能完成，不需要转为核心态。

内核级线程

1	线程的管理由操作系统内核来完成，此时需要在核心态进行操作。

指令

系统指令

系统指令一般指指令系统，包括特权指令、用户指令。

特权指令（只能由操作系统使用）
用户指令（用户使用）

此时，用程序状态字寄存器（PSW）中的某标志位来标识当前处理器处于什么状态，0为用户态，1为核心态。

Alt text

系统调用

“系统调用”是操作系统提供给应用程序（程序员/编程人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以发出系统调用请求来获得操作系统的服务。

注意系统调用可以使处理器从用户态到核心态，暂时知道的系统调用只有中断

系统调用的分类：

设备管理
文件管理
进程控制
进程通信
内存管理

凡是和内存或是其他进程有关的操作，一般都会引起系统调用。

调度算法

先来先服务（FCFS）

1	按照进程到达就绪队列的先后顺序进行任务调度，为非抢占式，不会产生饥饿问题，但是对高优先级的任务无法快速响应。

短作业优先（SJF）

要求最短的平均等待时间，非抢占式，能够减少等待时间。也有抢占式的短作业优先算法，称为“最短剩余时间优先算法(SRTN)”,如果所有任务几乎同时到达，则此时短作业优先算法平均等待时间、平均周转时间最小，可能产生饥饿。

高相应比优先（HRRN）

1	相应比 = （等待时间+要求服务时间）/ 要求服务时间，也是非抢占式算法，不会导致饥饿。

时间片轮转（RR）

1	让每个进程在一定的时间间隔内得到响应，如果时间片过大则会退化为先来先服务算法，太小时进程切换过于频繁，符合分时系统。

优先级调度算法

1	根据优先级进行抢占（分抢占和非抢占）。抢占时，同优先级根据先后顺序抢占，可将优先级分为动态优先级和静态优先级，可能导致低优先级饥饿。

多级反馈调度算法

1
2

设置多级就绪队列，各级队列优先级从高到低，时间片从小到大新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经在最下级的队列，则重新放回最下级队列队尾只有第k级队列为空时，才会为k+1级队头的进程分配时间片

资源

资源共享方式

互斥共享方式（一段时间内只允许一个进程访问该资源）
同时共享方式（一段时间内允许多个进程访问该资源）

注意此时“同时”也可能指宏观上的同时，微观上为时间片的轮换

系统调度

高级调度（面向作业）

1	从外存中挑选一个或多个作业，给他们分配内存等资源，并建立相应的进程（PCB），使他们获得竞争处理的机会。

中级调度（面向进程）

1	虚拟存储技术将暂时无法执行的进程移到外存中，PCB不移出外存，而是保存在内存的挂起队列中。中级调度就是决定哪个等待的进程重新进入内存。

如上图，进程的七状态模型。

低级调度（内存、CPU）

1	按照某种方法，从挂起队列中选择进程并分配资源，是最基本的调度。

信号量机制

用户进程可根据操作系统的一对原语（wait(s)和signal(s)也称P(s)和V(s)）进行信号量的操作，信号量其实就是一个变量。我们知道软件同步最大的不足是各区的操作无法一气呵成，一口气执行完毕，对此我们改用原语进行处理。

整型信号量
——用于表示某种资源的数量，存在”忙等”
记录型信号量
——由于整型信号量存在”忙等”，因此做出改进。block是进程堵塞，wakeup使线程唤醒。

信号量实现进程互斥：

划定临界区域
设置互斥量
临界区前执行P(mutex)
临界区后执行V(mutex)

信号量实现进程同步：

分析区域实现“同步关系”
设置同步信号量“S”，初始为0
前一个操作进行”V(s)”
后一个操作进行”P(s)”

Alt text

信号量实现前驱：

为每一对前驱设置一个同步变量
前操作对相应同步变量执行”V”
后操作对相应同步变量执行”P”

管程

管程的组成：

局部于管程的共享数据结构说明
对该数据结构进行操作的函数
对局部于管程的共享数据设置初始值的语句
管程有一个名字

特征：

局部于管程的数据只能被局部于管程的过程所访问
一个进程只有通过调用管程内的函数才能进入管程访问共享数据
每次仅允许一个进程在管程内执行某个内部过程

常见问题

系统抖动

在请求分页存储管理中，从主存（DRAM）中刚刚换出（Swap Out）某一页面后（换出到Disk），根据请求马上又换入（Swap In）该页，这种反复换出换入的现象，称为系统颠簸，也叫系统抖动。产生该现象的主要原因是置换算法选择不当。

1
2

1、如果提供的存储块数量小于进程需要的存储块数量，则会发生缺页中断
2、在请求分页存储管理中，可能出现这种情况，即对刚被替换出去的页，立即又要被访问

死锁

定义：各进程间互相等待对方手里的资源，导致各进程堵塞无法推进。

必要的四个条件：

互斥条件
不可剥夺
请求和保持
循环等待条件(死锁一定循环等待，循环等待不一定死锁)

死锁的处理：

死锁预防

避免死锁

安全序列：
    就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。
    系统进入安全状态一定不会发生死锁，而进入不安全状态则有可能发生死锁。
银行家算法：
    在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。

死锁的解除：

资源剥夺法，挂起某些死锁进程，并剥夺他资源。
撤销进程法，强制撤销死锁进程，并剥夺这些进程的资源。
进程回退法，让一个进程回退到足以避开死锁的地步。
以下为系统资源分配图，如果系统资源分配图是不可以完全简化的，则系统就是发生死锁。

概念

CPU利用率 = CPU忙碌时间/总时间
系统吞吐量 = 总共完成多少道作业/总时间
周转时间 = 作业完成时间-作业提交时间
平均周转时间 = 所有周转时间和/作业数
带权周转时间 = 周转时间/作业实际运行时间
等待时间 = 等待处理机的时间
大内核：将操作系统的主要功能都做为系统内核，运行在核心态
微内核：只保留最基本的功能给系统内核

内存

内存时用来存放数据的硬件。

逻辑地址和物理地址

逻辑地址相对于进程在内存中的起始地址而言的地址
物理地址具体的内存地址

Alt text

编译：由编译程序将用户代码编译成若干个目标模块（将高级语言翻译为机器语言）
链接：由链接程序将编译后形成的一组目标模块，以及所需要库函数链接在一起，形成一个完整的装入模块
装入：由装入程序将装入模块装入内存运行

装入的三种方式

1
2
3

1.绝对装入，在编译时就知道程序放在内存中哪个位置，编译程序将产生绝对地址的目标代码。
2.静态重定位，由装入模块将逻辑地址转换为物理地址，一旦作业进入内存中，运行期间不可再移动。
3.动态重定位，在程序执行时再将逻辑地址转换为物理地址。

链接的三种方式

1
2
3

1.静态链接，运行前链接
2.装入时动态链接，边装入边链接
3.运行时动态链接，边运行边链接

内存保护

采取上、下限寄存器

存放进程的上下限地址，cpu检查是否越界。

重定位寄存器和界地址寄存器

重定位寄存器存放的是进程的起始物理地址，界地址存放的是最大的逻辑地址。

覆盖技术

将程序分为多个段，常用的段常驻内存，不常用的段需要时再调用，通常分为“固定区”和若干个“覆盖区”。

Alt text

如图，将A区当作固定区，B、C共用一个覆盖区，当B被调用时则覆盖区域，C被调用时同样覆盖区域。

交换技术

当内存空间紧张时，可选择一部分进程换出外存，等空间不那么紧张时再取回。具有对换技术的操作系统一般由文件区和对换区组成，被换出的内存就存在对换区，对换区讲究读写速度，采用连续存储，文件区主要用于存放文件，主要在意磁盘空间利用率，采用离散分配方式。

连续分配管理

1
2
3

1.单一连续分配，只支持单道程序，内存分为系统区和用户区，用户程序放在用户区，无外部碎片，有内部碎片
2.固定分区分配，支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装一个作业，无外部碎片，有内部碎片，
3.动态分区分配，支持多道程序，根据进程的大小动态的建立分区，无内部碎片，有外部碎片，外部碎片可采用“紧凑技术进行实现”

动态分区分配算法:

首次适应算法(First Fit)

从小到大开始，找到第一个满足条件的分区。

最佳适应算法(Best Fit)

将空闲分区链从小到大排列，这样就能从小开始，找到最适合的一个分区。容易留下越来越多小外部碎片。

最坏适应算法(Worst Fit)

将空闲分区链从大到小排列，这样就能从大开始，找到最适合的一个分区。容易导致大分区不断减少，最后无大分区可用。

邻近适应算法(Next Fit)
每次都从上一次查找结束的位置继续往下查找。

分页管理

将内存空间分为一个个大小相等的分区，每个分区就是一个”页框”，每个”页框”都有一个编号，称为”页框号”，从0开始（页框不宜过大，容易产生碎片）。

如何计算实际物理地址

1.要算出逻辑地址对应的页号
2.要知道该页号对应页面对应在内存中起始地址
3.算出逻辑地址在页面中的偏移量
页号 = 逻辑地址/页面长度(整数部分)
页内偏移量 = 逻辑地址%页面长度(余数部分)

PCB存放着页表寄存器。

快表(又称联想寄存器TLB)
存放经常被访问的页号和内存块号。
两级页表(各级页表大小不能超过一个页面)
单级页表的缺点：
1.所有的页表项都连续存放的基础上才能用这种方法。
2.进程在一段时间内只需要访问某几个页面就可以了，不需要整个页表都常驻内存。

两级页表缺点：

缓存次数不断增加，耗时长

分段管理（按逻辑结构划分）

每段对应一个段表项，记录了内存中的起始位置和段长。
每个段的长度时是相同的。
段时信息的逻辑单位，对用户可见。
分段比分页更容易实现信息的共享和保护，只需要将不同程序的段表项指向同一个段，不能被修改的代码称为纯代码，可共享。可被修改的代码不能共享。

虚拟内存

在操作系统的管理下，用户似乎有一个比实际内存大得多的内存，虚拟内存的最大容量是由计算机的地址结构确定的。

传统存储管理方式的特征、缺点：

作业必须一次性装入内存后运行
作业很大时，不能全部装入内存
大量作业要求运行时，内存无法容纳所有作业，并发度下降
驻留性，作业一旦装入内存就会常驻在内存中，浪费大量资源

特点：

多次性，多次调入内存
对换性，无需一直常驻内存，需要时换入换出
虚拟性，扩充了内存的容量

请求分页管理方式：

与基本分页管理相比，请求分页管理中，为了实现“请求掉页”，需要知道每个页面是否已经调入内存，如果还没有调入，则需要知道该页面在外存中存放的位置。当空间不够时，还需要置换页面，记录页面修改过的信息。
增加了几个字段：状态位、访问字段、修改位、外存地址

页面置换算法：

最佳置换算法(OPT)，每次淘汰都是永不使用或者最长时间内不会再被使用的页面
先进先出置换算法(FIFO)，每次淘汰最早进入内存的页面
最近最久未使用置换算法(LRU),每次淘汰最久未使用的页面
时钟置换算法(CLOCK),检查访问位，为0淘汰，为1置0
改进型时钟置换算法，在时钟置换算法的基础上增加修改位，优先淘汰没有被修改过的页面，第一优先级：最近没访问、没修改；第二优先级：最近没访问，有修改；第三优先级，最近有访问，没修改；第四优先级：最近无访问，无修改。

驻留集：
值请求分页存储管理中给进程分配的物理块的集合

若驻留集太小，容易导致缺页频繁。
若驻留集太大，又会导致多道程序并发度下降，资源利用率降低。

驻留集置换：

固定分配，为每个进程分配一定数目的物理块，运行期间不变
可变分配，为每个进程分配一定数目的物理块，运行期间可变
局部置换，发生缺页时，只能选进程主机的物理块进行置换
全局置换，将操作系统保留的空闲物理块分配给缺页进程

文件管理

同一目录不允许有重名文件。

结构

无结构文件
文件内部由一系列二进制流或字符流组成，称为流式文件。

有结构文件
由若干个数据项组成，可定长和可变长。

1
2
3

1.顺序文件，一个一个顺序排列，可定长和可变长。又分为串结构(顺序和关键字无关)和顺序结构（按关键字顺序排列）。
2.索引文件，会建立一个索引表，进行文件查找，可将关键字做为索引号。
3.索引顺序文件，将记录分组，每个组对应一个索引表项。

物理结构

文件的逻辑地址空间也被分为了一个一个的文件块，使用逻辑块号和块内地址的形式。

连续分配方式
要求每个文件在磁盘上占有一组连续的块。会产生内部碎片。
隐式链接
除了最后一个磁盘块，每一个磁盘块中都会存放下一个磁盘块的指针。只支持顺序访问，不支持随机访问。
显示链接
把各物理块的指针放在一张表（FAT）里，目录中只记录起始块号，剩余块根据表进行查找。支持顺序访问和随机访问。
索引分配
会为每个文件建立一张索引表，目录中记录索引块的位置，具体文件数据根据索引表查找。如果索引块太大，则可以通过链接的方式将多个索引块链接起来存放。但是通过链接存放，当查找时会进行多次磁盘读取操作，考虑到这个问题我们也可以使用多级索引的方式。
混合索引
即包含直接索引，又包含间接索引（索引表）。

文件存储空间管理

空闲表法，空闲表中存储第一个空闲盘块号，空闲盘块数
空闲链表法，以盘块为单位组成一条空闲链，或以盘区为单位组成一条空闲盘区链，每一个盘块内部都包含下一个盘块或盘区的地址。回收资源时，若没有相邻空闲区相邻，则单独挂在队尾。
成组链接法，超级快中记录了每个组中有多少个盘块。

文件共享

软链接基于符号链的共享方式，Link类型的文件存放着文件的存放路径，类似快捷方式
硬链接基于索引节点的共享方式，检索文件时只需要文件名，硬扯可以把文件名之外的信息放到索引节点中，目录项只包含文件名、索引节点指针。

文件保护

口令保护，用户请求访问时需要提供口令，花销小，验证的时间小，但是不安全
加密保护，通过密码进行保护，安全性高，但是费时
访问控制，记录哪些用户可以执行哪些操作

文件的层次结构

Alt text

单级目录结构，实现按名存取，但不允许文件重名
两级目录结构，分为主文件目录和用户目录，允许不同用户文件重名
多级目录结构，要访问某个文件时，要用文件路径名标识文件，各级目录用”/“隔开。
无环图目录结构，不同文件名指向同一个文件，需要为共享文件设置一个共享计数器，当计数器减为0时，才删除结点。
索引节点，根据文件名找到索引节点，就可以找到文件