操作系统基础知识复习

总述

操作系统四大功能

处理机管理：进程管理。处理机如何调度的问题： FCFS、优先级、时间片轮转？
存储器管理：主存管理。存储分配、存储保护、主存扩充。
设备管理：涉及对系统中各种输入、输出设备的管理和控制。分配设备，控制设备传输数据
文件管理将程序、数据、操作系统软件等组织成文件，存放在磁盘或磁带上，方便用户访问

操作系统的特性

(1)并发性：并发是指系统中存在着若干个逻辑上相互独立的程序，它们都已被启动执行，
都还没有执行完，并竞争各种资源。
(2)共享性：是指系统中的资源可供内存中多个并发执行的进程共同使用。如打印机、磁带
机、磁盘等。支持系统并发性的物质基础是资源共享
(3)虚拟性：把共享资源的一个物理实体变为若干个逻辑上的对应物。如， CPU 的分时共享；
虚拟存储器技术。
(4)异步性（随机性）：有限的共享资源使并发进程之间产生相互制约关系。各个进程何时
执行、何时暂停、以怎样的速度向前推进、什么时候完成等都是不可预知的

操作系统的接口

命令接口
- 联机控制(即使响应的意思)：cmd
- 脱机控制：日常编程
程序接口（通过某程序进行交流）
- GUI

核心态和用户态

在核心态下，允许执行处理机的全部指令集，访问所有的寄存器和存储区；
在用户态下，只允许执行处理机的非特权指令，访问指定的寄存器和存储区。
管态到目态的转换由操作系统程序执行后*软件自动完成

三类中断（目态->管态）

由计算机硬件异常或故障引起的中断，称为内部异常。
由外部设备请求引起的中断，称为外部中断。
系统调用：软中断。

进程管理

进程

是程序的一次运行
包括：
- 程序段(text region)
- 数据段(data,stack)
- PCB

进程的特征

动态性
并发性：共存主存
独立性：独立接收资源、独立接收调度（线程也是独立调度，但不是独立分配资源）
异步性：进程之间相互制约，导致间断运行
结构性：由数据段、程序段、pcb构成

进程状态

主要：运行，就绪，阻塞。
创建，挂起，终止。

进程控制：对进程状态的改变进行控制

创建、杀死、切换、阻塞&唤醒。

进程的通信

图片说明
https://www.bilibili.com/video/BV1dt4y1m7F5?p=7

进程运行步骤

编译：源代码 -> obj
链接：obj + 库函数 => 一个完整的装入模块（if静态链接）
- 动态链接：在装入时，或运行时，再链接
装入：用装入程序将装入模块装入内存

线程

线程与进程的比较

（1）拥有的资源
进程拥有一个独立的地址空间，若干代码段和数据段，若干打开文件、主存以及至少一个线程。
一个进程内的多线程共享该进程的所有资源，线程自己拥有很少资源。
（2）调度
同一进程内的线程切换，仅把线程拥有的一小部分资源变换了即可，效率高。同一进程内的线程切换比进程切换快得多。
（3）并发性
引入线程后，使得系统的并发执行程度更高。进程之间、进程内的多线程之间可并发执行。线程很容易的实现相互之间的通讯。
（4）（不）安全性
同一进程的多线程共享进程的所有资源，一个线程可以改变另一个线程的数据，安全性低，而多进程实现则不会产生此问题。

锁

锁要解决的是线程之间争取资源的问题，这个问题大概有下面几个角度：
资源是否是独占（独占锁 - 共享锁）
抢占不到资源怎么办（互斥锁 - 自旋锁）
自己能不能重复抢（重入锁 - 不可重入锁）
竞争读的情况比较多，读可不可以不加锁（读写锁）

进程（线程）调度

作业从提交开始直到完成，往往要经历下述三级调度：

高级调度：(High-Level Scheduling）
- 作业调度
- 它决定把后备作业从外存调入内存运行；
中级调度：(Intermediate-Level Scheduling)
- 内存调度
- 在内、外存对换区进行进程对换
低级调度：(Low-Level Scheduling)
- 进程调度
- 决定把就绪队列的某进程获得CPU；

进程调度算法

非剥夺方式

某一进程占用 CPU,直到运行完或不能运行为止，其间不被剥夺。用在批处理系统。主要优点：简单、系统开销小。
- 先来先服务(FCFS)：效率低，容易被大作业垄断，
- 最短作业优先(SJF)：平均等待时间短，但长作业可能饥饿。
- 响应比高者优先(HRN) ：Rp =(作业等待时间+作业估计运行时间)/作业估计运行时间
- 非剥夺优先级调度法：一般优先级原则（系统进程,交互式进程，IO型进程）
  剥夺方式
  允许调度程序基于某种策略剥夺现行进程的CPU给其它进程。用在分时系统、实时系统
- 剥夺式优先级调度法
- 时间片轮转法：使用一个固定的时间片长度，因此时间片长度的确定很重要
- 多级反馈队列轮转法
  - 设有N个队列（Q1,Q2....QN），位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高
  - 各个队列的时间片是随着优先级的增加而减少
  - 除了优先级最低的队列，遵循的是先来先服务算法，若时间片运行完时进程未结束，则进入下一优先级队列的末尾。
  - 对于优先级最低的队列来说，里面是遵循时间片轮转法。

进程调度指标

CPU利用率
吞吐量
周转时间
响应比

进程同步和并发问题

https://hit-alibaba.github.io/interview/basic/arch/Concurrency.html

临界区的制约

临界资源：就是一次仅允许一个进程使用的资源。
临界区(critical section)：就是并发进程访问临界资源的那段必须互斥执行的程序。
进入临界区的四个准则
不能同时有两个进程在临界区内执行 —— 互斥使用
等待进入临界区的进程，应释放处理机后阻塞等待 —— 让权等待
在临界区外运行的进程不可阻止其他进程进入临界区 —— 有空让进
不应使要进入临界区的进程无限期等待在临界区之外 —— 有限等待

死锁

定义：多个进程因竞争资源
产生死锁的根本原因：是对独占资源的共享，并发执行进程的同步关系不当。

发生的必要条件

1）互斥条件。独占性的资源。
2）保持和等待条件。进程因请求资源而阻塞时，对已经获得的资源保持不放。
3）不剥夺条件。已分配给进程的资源不能被剥夺，只能由进程自己释放。
4）循环等待条件。存在一个进程循环链，链中每个进程都在等待链中的下一个进程
所占用的资源。

死锁解决办法

鸵鸟算法。忽略死锁。
死锁的预防。通过破坏产生死锁的四个必要条件中的一个或几个，来防止发生死锁
死锁的避免。用某种方法（如银行家算法）防止系统进入不安全状态
死锁的检测和恢复：定期检查+剥夺资源

银行家算法

思想: 判断此次请求是否造成死锁，若会造成死锁，则拒绝该请求。
对于一个资源请求，假设分配进行试探。对于已经分配的进程，用现有的资源尝试分配满&回收，如果都能成功回收，则安全。

规则

(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;
(2) 顾客可以分期贷款,但贷款的总数不能超过最大需求量;
(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;
(4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金.
原文链接：https://blog.csdn.net/yaopeng_2005/article/details/6935235