操作系统复习笔记

操作系统基本功能

文件管理
存储管理
设备管理
进程管理

单道批处理系统特点

一批：作业队列
自动：识别作业
单道：串行

联机批处理：主机控制输入输出

脱机批处理：卫星机控制输入输出

多道批处理系统特点

多道：内存同时存放多道程序
宏观上并行：同时进入系统的几道程序都处于运行过程中，即它们先后开始了各自的运行，但都未运行完毕。
微观上串行：从微观上看，内存中的多道程序轮流地或分时地占有CPU。

分时系统特点

多路调制性：多用户联机使用同一台计算机
独占性：用户感觉独占计算机
交互性：及时响应用户的请求

理解操作系统特性

并发
共享
虚拟
异步

程序执行方式

顺序执行

① 顺序性：指处理机严格地按照程序所规定的的顺序执行。

② 封闭性：指程序在封闭的环境下运行，即程序运行时独占全机资源（没有其它程序一起共享），资源的状态只有本机才能改变。

③ 可再现性只要程序执行时的环境和初始条件相同，当程序重复执行时，都可获得相同的结果。
并发执行

① 间断性：也就是一个程序的整个执行过程是“走走停停”的，由于共享资源，这些并发的程序相互制约，有时需要进行等待，造成了 “执行——暂停——执行” 的间断性活动规律。

② 失去封闭性：由于并发的程序之间共享系统资源，导致其中任一程序在运行时，其环境都必然会收到其它程序的影响，所以就失去了运行环境的封闭性。

③ 不可再现性：程序在并发执行时，由于失去了封闭性，从而也失去了不可再现性。换句话说，程序在多次执行后，虽然它们执行的环境和初始条件是相同的，但得到的结果却各不相同。

虚拟机 = 裸机 + 配置操作系统

用户界面：OS提供给用户控制计算机的机制，又称用户接口。（操作界面 + 系统调用）
屏蔽硬件细节
扩展硬件功能
系统更安全
系统更可靠
效率更高

操作系统的逻辑结构

单体式结构：操作系统四个功能放在一个模块里 UNIX/LINUX
模块化结构：windowsNT
可扩展化结构：微内核+核外服务器（以进程形式运行在用户态）MINIX/WINCE
层次式结构：把所有功能模块按照调用次序分别排成若干层，确保各层之间只能是单向依赖或单向调用 MSDOS

态：核态（目态），用户态（管态）

操作系统生成过程

根据硬件环境/用户要求配置功能模块和构造参数
构建（build）OS的映像

操作系统启动过程

初始引导：把OS内核装入内存并使之开始工作接管计算机系统

（FFFF0H单元的命令）加电自检 JUMP POST -》启动程序运行-》启动程序加载MBR中的引导程序-》引导程序加载硬盘上OS内核，并初始化基本参数-》OS内核边运行，边逐步加载OS的剩余部分。
核心初始化：OS内核初始化系统的核心数据（各种寄存器，存储系统的页表，核心进程）
系统初始化：为用户使用系统作准备，使系统处于待命状态（文件系统，网络系统，初始化控制台，初始化图形界面）

中断定义：指CPU对突发的外部事件的反应过程或机制

向量中断就是不同的中断有不同的入口地址，非向量中断就只有一个入口地址，进去了在判断中断标志来识别具体是哪个中断。向量中断实时性好，非向量中断简单

向量中断——由硬件提供中断服务程序入口地址；
非向量中断——由软件件提供中断服务程序入口地址；

中断类型

强迫中断和自愿中断
- 强迫中断：程序没有预期：例：I/O、外部中断
- 自愿中断：程序有预期。例：执行访管指令
外中断（中断）和内中断（俘获）
- 外中断：由CPU外部事件引起。例：I/O，外部事情。
- 内中断：由CPU内部事件引起。例：访管中断、程序中断
外中断：不可屏蔽中断和可屏蔽中断
- 不可屏蔽中断：中断的原因很紧要，CPU必须响应
- 可屏蔽中断：中断原因不很紧要，CPU可以不响应

中断相应过程：

识别中断源
保护断点和现场
装入中断服务程序 CS:IP
进入中断服务程序
恢复现场和断点
中断返回：IRET

系统调用

特点：

一般涉及核心资源或硬件的操作
运行于核态。
每个系统调用具有唯一的编号：ID
调用过程会产生中断：自愿中断

DOS： INT 21H（AH存放系统调用的编号）
LINUX：INT 80H（EAX存放系统调用的编号）

进程 = 程序 + 数据 + PCB

进程是资源分配的最小单位，线程是cpu调度的最小单位

进程的特征

动态性进程是程序的一次执行过程，动态产生/消亡
并发性进程可以同其他进程一起向前推进；
异步性进程按各自速度向前推进
独立性进程是系统分配资源和调度CPU的单位；

进程的状态：

就绪：当一个进程获得了除处理机以外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态。就绪进程可以按多个优先级来划分队列。例如，当一个进程由于时间片用完而进入就绪状态时，排入低优先级队列；当进程由I／O操作完成而进入就绪状态时，排入高优先级队列。
运行：当一个进程在处理机上运行时，则称该进程处于运行状态。处于此状态的进程的数目小于等于处理器的数目，对于单处理机系统，处于运行状态的进程只有一个。在没有其他进程可以执行时（如所有进程都在阻塞状态），通常会自动执行系统的空闲进程。
阻塞：也称为等待或睡眠状态，一个进程正在等待某一事件发生（例如请求I/O而等待I/O完成等）而暂时停止运行，这时即使把处理机分配给进程也无法运行，故称该进程处于阻塞状态。

状态变迁：

就绪-》运行：进程调度
运行-》就绪：时间片到；被抢占
运行-》阻塞：等待某事件如I/O请求
阻塞-》就绪：I/O结束或等待的事情发生

五态：

活跃就绪：是指进程在主存并且可被调度的状态。
静止就绪（挂起就绪）：是指进程被对换到辅存时的就绪状态，是不能被直接调度的状态，只有当主存中没有活跃就绪态进程，或者是挂起就绪态进程具有更高的优先级，系统将把挂起就绪态进程调回主存并转换为活跃就绪。
活跃阻塞：是指进程已在主存，一旦等待的事件产生便进入活跃就绪状态。
静止阻塞：是指进程对换到辅存时的阻塞状态，一旦等待的事件产生便进入静止就绪状态。

进程控制块(Process Control Block，PCB) ：包含pid，进程当前的状态，next指针（指向当前队列的下一个进程），进程优先级，cpu现场保护区，和别的进程的通信信息，家族关系，占有资源清单等等。

进程控制的概念：在进程生存全期间，对其全部行为的控制

四个典型的控制行为

创建进程
撤消进程
阻塞进程
唤醒进程

原语：由若干指令构成的具有特定功能的函数，具有原子性，其操作不可分割

临界资源：一次只允许一个进程独占访问使用的资源

临界区：进程中访问临界资源的程序段

设计临界区访问机制的四个原则

忙则等待
空闲让进
有限等待
让权等待

同步：合作进程中某些操作之间需要满足某种先后关系或某个操作能否进行需要某个前提条件满足，否则只能等待

同步编程应用：

临界区（锁）CRITICAL_SECTION 在进程内使用，保证仅一个线程可以申请到该对象。
互斥量(Mutex) （锁）HANDLE 保证只有一个线程或进程可以申请到该对象。
信号量（Semaphore）HANDLE 允许指定数目的多个线程/进程访问临界区
事件（Event）HANDLE 用于通知一个或多个线程某事件出现或标识某操作已经完成。
等待操作

//WINDOWS同步机制

DWORD WaitForMultipleObjects (
	DWORD nCount,//等待对象的数量
	CONST HANDLE *lpHandles,//对象句柄的数组
	BOOL bWaitAll,//等待方式（true全部等待）
	DWORD dwMilliseconds//等待时间，单位MS
);

DWORD WaitForSingleObject (
	HANDLE hHandle,//对象句柄
	DWORD dwMilliseconds//等待时间，单位MS
);
/****************************************************************/
EnterCriticalSection( );//上锁操作/进入临界区
LeaveCriticalSection( );//开锁操作/离开临界区
InitializeCriticalSection( );//初始化临界区/初始化锁
DeleteCriticalSection( );//删除临界区/删除锁
/****************************************************************/
HANDLE CreateMutex( //创建互斥量 :全局用1次
	LPSECURITY_ATTRIBUTES lpMutexAttributes,
	BOOL bInitialOwner, // 初始化互斥量的状态：真或假
	LPCTSTR lpName // 名字，可为NULL但不能跨进程用
);

HANDLE OpenMutex(//打开互斥量: 每个进程用1次
	DWORD dwDesiredAccess,
	BOOL bInheritHandle,
	LPCTSTR lpName // 名字
);

BOOL CloseHandle(//关闭互斥量: 每个进程用1次
	HANDLE hObject // 句柄
);

BOOL ReleaseMutex(// 释放：开锁
	HANDLE hMutex // 句柄
);
/****************************************************************/
HANDLE CreateSemaphore( //创建信号量：全局用1次
	LPSECURITY_ATTRIBUTES lpSemaphoreAttributes,// 安全属性
	LONG lInitialCount, // 初始值
	LONG lMaximumCount, // 最大值
	LPCTSTR lpName // 名字
);

HANDLE OpenSemaphore(//打开信号量：每个进程用1次
	DWORD dwDesiredAccess, // 存取方式
	BOOL bInheritHandle, // 是否能被继承
	LPCTSTR lpName // 名字
);

BOOL CloseHandle(//关闭信号量：每个进程用1次
	HANDLE hObject // 句柄
);

BOOL ReleaseSemaphore(//释放信号量
	HANDLE hSemaphore, // 句柄
	LONG lReleaseCount, // 释放数，让信号量的值增加的数量
	LPLONG lpPreviousCount // 得到释放前信号量的值，可为NULL
);
/****************************************************************/
HANDLE CreateEvent ( //创建事件对象
	LPSECURITY_ATTRIBUTES lpEventAttributes,// 安全属性
	BOOL bManualReset, // 是否为人工重置
	BOOL bInitialState, // 初始状态是否为有信号状态
	LPCTSTR lpName // 名字
);
HANDLE OpenEvent (//打开事件对象
	DWORD dwDesiredAccess, // 存取方式
	BOOL bInheritHandle, // 是否能够被继承
	LPCTSTR lpName // 名字
);
BOOL ResetEvent (//设置事件为无信号状态
	HANDLE hEvent // 句柄
);
BOOL SetEvent (//设置事件有信号状态
	HANDLE hEvent // 句柄
);
BOOL CloseHandle (//关闭事件对象
	HANDLE hObject // 句柄
);

进程通信

管道通信仅能用于父子或兄弟进程间通信
双向通信必须建立2个管道

软件中断：由写在程序中的语句引起的中断程序的执行，称为软件中断。

Linux软中断通信机制

kill(pid, sig)：传递软中断信号
signal(sig, func)：注册软中断信号
wait( )：用于父子进程间的同步
sleep( n )：使当前进程睡眠n秒后自动唤醒自己

死锁：两个或多个进程无限期地等待永远不会发生的条件的一种系统状态。

死锁的原因：

系统资源有限
并发进程推进顺序不当

死锁的必要条件：

资源独占性
不可剥夺
部分分配
环路条件

预防死锁：

破坏互斥条件
破坏不剥夺条件
破坏部分分配条件预先静态分配法
破坏环路条件有序资源分配法

避免死锁：银行家算法

检测死锁

恢复死锁

进程调度概念：在合适的时候以一定策略选择一个就绪进程运行

进程调度的目标

响应速度尽可能快
进程处理的时间尽可能短
系统吞吐量尽可能大
资源利用率尽可能高
对所有进程要公平
避免饥饿
避免死锁

进程调度两个量化的衡量指标

周转时间/平均周转时间进程提交给计算机到完成所花费的时间
带权周转时间/平均带权周转时间进程的周转时间/进程的运行时间

进程调度算法

先来先服务调度（First Come First Serve）
短作业优先调度算法（Short Job First）
响应比高者优先调度算法响应比 =（等待时间+运行时间）/运行时间
优先数调度算法进程优先数=静态优先数+动态优先数
循环轮转调度法（ROUND-ROBIN）进程以时间片q为单位轮流使用CPU
可变时间片轮转调度法时间片的大小可变
多重时间片循环调度法组织多个轮转队列

linux进程调度

基于优先级调度，选择优先级最高的进程运行
既支持普通的分时进程，也支持实时进程
让实时进程优先于普通进程
保证普通进程公平使用CPU时间

普通进程

采用动态优先级来调度

调度程序周期性地修改优先级（避免饥饿）
实时进程

采用静态优先级来调度

由用户预先指定，以后不会改变

实时进程的优先级总是比普通进程的优先级高

存储管理的功能

地址映射
虚拟存储
1. 页式虚拟存储
2. 段式虚拟存储
内存分配
存储保护

物理内存管理

单一区存储管理（不分区存储管理）
分区存储管理

分区的分配在所有空闲区中寻找一个空闲区，分配给用户使用。
1. 首次适应法尽可能地先利用低地址空间
2. 最佳适应法选中分区是满足要求的最小的空闲区
3. 最坏适应法空闲区表按大小递减排序
内存覆盖技术常驻区覆盖区
内存交换技术

内存不够时把进程写到磁盘（换出/Swap Out）

当进程要运行时重新写回内存（换入/Swap In）

虚拟内存管理

改善物理内存管理的相关技术

内存拼接
对换技术【Swapping】
覆盖技术【Overlay】

典型虚拟内存管理方式

页式虚拟存储管理
- 虚拟地址VA 分成页号P和页内偏移W
- 页表扩充
  - 中断位I ——标识该页是否在内存
    
    I =１，不在内存
    
    I =０，在内存
  - 辅存地址——该页在辅存上的位置
  - 访问位——标识该页最近是否被访问？
    
    ０最近没有被访问
    
    １最近已被访问
  - 修改位——标识该页的数据是否已被修改？
    
    ０该页未被修改
    
    １该页已被修改
- 缺页中断
- 淘汰策略
  - 最佳算法（OPT算法）
    
    淘汰以后不再需要或最远的将来才会用到的页面
  - 先进先出淘汰算法（FIFO算法）
    
    淘汰在内存中停留时间最长的页面
  - 最久未使用淘汰算法（LRU算法）
    
    淘汰最长时间未被使用的页面，页面设置一个定时器（移位寄存器R）。页面被访问则重置1。周期性地(周期很短)将所有页面的R左移1位（右边补0）
  - 最不经常使用（LFU算法）
    
    选择到当前时间为止被访问次数最少的页面
段式虚拟存储管理
段页式虚拟存储管理

设备按信息组织特征分为字符设备(如打印机), 块设备(如磁盘),网络设备

设备独立性

设备独立性：用户在程序中仅使用仅与实际设备无关的逻辑设备名。
逻辑设备名：用户自己指定的暂时的、可更改的设备名 (或设备号)。
物理设备名：系统提供的永久的、不可更改的设备标准名称。

程序独立于分配给它的某种类型的具体设备
1. 系统可动态分配给程序某类设备中任一台物理设备，程序都
  能正确地执行。
程序应尽可能与它所使用的I/O设备类型无关
1. 在输入/输出信息时，信息可以来自不同类型的具体设备
2. 若要改变输入 /输出设备的类型，程序只需进行最少的改动。
设备独立性的优点
1. 方便用户
2. 改善设备利用率
3. 提高系统的可扩展性和可适应性修改。