笔记整理——计算机操作系统（笔记整理三之三）
操作系统的五大功能：处理机管理、存储器管理、设备管理、文件管理、向用户提供方便的用户接口。
操作系统共有的特征：并发、共享、虚拟、异步。（并发与共享是最基本的特征）。操作系统分为单道批处理、多道批处理；分时、实时系统。
进程：系统中能独立运行并作为资源分配的基本单位，由一组机器指令、数据、堆栈等组成。线程：作为独立运行的调度的基本单位。进程控制块：PCB，进程存在的唯一标志，系统利用PCB进而控制和管理进程（常驻内存）。进程和程序的最根本的区别是，进程是动态的，而程序是静态的。
进程的特征：并发性（重要特征）、动态性（最基本的特征）、独立性、异步性。进程由独立的地址空间；线程由自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉（每个进程最少有一个线程）。进程之间的地址空间独立。
挂起状态 —> 活动就绪、静止就绪、活动阻塞、静止阻塞。终止状态后，除PCB之外其他都被释放。
临界资源：在一段时间内只允许一个进程访问的资源。每个进程中访问临界资源的那段代码称为临界区。
关中断：屏蔽中断，系统不响应中断，从而不会引发调度，也就不会发生进程或线程切换。
调度算法：
- FCFS：先来先服务（不利于短作业）
- SJF：短作业优先（平均周转时间最短的算法）
- PSA：优先级调度算法（优先级数越大，优先度越高）
- HRRN：高响应比优先调度算法。响应比 Rp = 响应时间 / 要求服务时间 = （等待时间 + 要求服务时间） / 要求服务时间
- RR：轮转调度算法（主要用于分时系统）
- 抢占式调度算法：1、基于时钟中断的抢占式优先级调度算法；2、立即抢占。
- EDF：最早截止时间优先算法
- LLF：最低松弛度优先算法。 松弛度 = 完成截止时间 - 剩余运行时间 - 当前时间
死锁的必要条件：1、互斥条件；2、请求和保持条件；3、不可抢占条件；4、循环等待条件。处理死锁的方法：1、预防死锁；2、避免死锁（银行家算法，在资源分配过程中，防止系统进入不安全状态）；3、检测死锁；4、解除死锁。产生死锁的原因主要有：1、系统资源不足；2、进程运行推进的顺序不合适；3、资源分配不当等。
死锁的预防措施：1、静态资源分配法；2、资源顺序分配法；3、剥夺控制法。
程序装入：1、编译；2、链接（逻辑地址变物理地址）；3、装入。（绝对装入方式、可重定位装入方式、动态运行时的装入方式）。
基于顺序搜索的动态分区分配算法：
- 首次适应算法（FF）
- 循环首次适应算法（NF）
- 最佳适应算法（WF）：总是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用。
基于索引搜索的动态分区分配算法：
- 快速适应算法
- 伙伴系统
动态可重定位分区分配。紧凑：解决了碎片问题。
分页 / 分段 / 段页式。页是信息的物理单位，以消减内外零头（系统行为）；段时信息的逻辑单位，满足用户的需要。
内存分配策略：
- 固定分配局部置换（只能从分配给改进程n个页面中选出一页换出）（固定分配全局置换不能组合）
- 可变全局置换
- 可变分配局部置换（只交换该进程的页面，分配若干物理块）
物理块分配算法：
- 平均分配算法
- 按比例分配算法
- 考虑优先权的分配算法
页面调入：预调页策略，请求调页策略。
请求分页系统中的外存分为：1、用于存放文件的文件区；2、用于存放对换页面的对换区。
页面置换算法：
- 最佳置换算法（无法实现）
- FIFO算法，有Belady现象
- LRU，最近最久未使用。需要较多硬件支持；管理虚拟内存的分配，物理内存的释放。
- LFU，最少使用置换算法
- Clock置换算法
- 页面缓冲算法PBA
抖动：同时在系统中运动的进程太多，从而分配每一个进程物理块太少，导致频繁缺页。
- 工作集指某个时间间隔∆里，进程实际所要访问页面的集合。
- 块设备接口是块设备管理程序与高层之间的接口。
- 设备控制器，控制一个或多个I/O设备，以实现I/O设备和CPU之间的数据交换。
- I/O通道，通道与CPU共享内存
磁盘调度算法：1、先来先服务（FCFS）；2、最短寻道时间优先（SSTF）；3、扫描算法（SCAN），电梯调度算法；4、循环扫描算法（CSCAN）
文件组织方式：顺序文件、索引文件、索引顺序文件。文件的逻辑结构：连续结构、多重结构、转置结构、顺序结构；（流式文件属于逻辑结构的文件）。文件的物理存储：顺序结构、链接结构、索引结构。文件的目录结构：一级目录结构、二级目录结构、树形结构、无环图。
文件存储空间的管理：1、空闲法和空闲链表法；2、位示图法；3、成组链接法。
数据传输率 = 记录密度 X 线速度。系统对每一块数据的处理时间：1、单缓冲区 Max（C，T）+ M；2、多缓冲区 Max（C，T）。（CPU处理时间C、缓冲区时间T、传送到用户时间M）
作业调度JCB：后备队列，优先级调度可能产生饥饿。
内存管理中常用区间和区间中的数据：
- 静态区：存放（初始化的）全局变量、静态变量，和（未初始化）全局变量和静态变量。
- 栈区：存放局部变量和函数的形参。栈中的内存空间由编译器自动申请和释放。
- 堆区：存放动态分配内存函数申请的变量。堆中的内存空间需要程序员手动释放，否则会发生内存泄露。（易产生内存碎片）
虚拟设备（Spooling技术），将独占设备变为共享设备，实现设备的虚拟分配，提高独占设备的利用率。（只能用软件实现）
线程共享的内容包括：1、进程代码段；2、进程数据段；3、进程打开的文件描述符；4、信号的处理器；5、进程的当前目录；6、进程用户ID与进程组ID。
线程独有的内容包括：1、线程ID；2、寄存器组的值；3、线程的堆栈；4、错误返回码；5、线程的信号屏蔽码。
用于进程间通信（IPC）的四种不同技术：
- 消息传递（管道、FIFO、Posix和System v消息队列）
- 同步（互斥锁、条件变量、读写锁、文件和积累锁，Posix和System v信号灯）
- 共享内存区（匿名共享内存区，有名Posix共享内存区，有名System v共享内存区）
- 过程调用（Solaris门、SunRPC）
实现线程同步：事件、临界区、互斥量、信号量。
外部中断处理过程，PC值由中断隐指令自动保存，而通用寄存器内容由操作系统保存。
虚拟存储的实现是基于程序局部性原理，其实质是借助外存将内存较小的物理地址空间转化为较大的逻辑地址空间。
用户级线程的管理由用户应用程序来完成，内核是不知道用户线程的。
删除文件，文件的关联目录项和文件控制块需要随着文件一同删除，同时释放文件的关联缓冲区。
管道是指用于连接一个读进程和一个写进程以实现进程之间通信的一种共享文件。数据格式是字符流。
虚拟存储器最大实际容量 = min（计算机地址，内存 + 辅存）
在分段存储管理中，地址转换公式：物理地址 = 界限寄存器值 + 逻辑地址。
fork子进程，但父子进程二者的地址空间是各自独立的，子进程无法读取父进程的数据。
文件目录：把所有FCB组织在一起，就构成了文件目录，即文件控制块的有序集合。目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保持在外存，这个文件就是目录文件。
进程上下文实际是进程执行活动全过程的静态描述。进程被抢占需要保存内容：1、所有CPU寄存器的内容，2、页表，3、程序计数器。
在请求分页管理中，一个首次装入内存的页面可能来自：1、磁盘文件区；2、后备作业区；3、I/O缓冲池。
逻辑地址到物理地址的映射，是由处理机中设置的专门硬件完成，即地址管理部件。页式的地址是一维的，段式的地址是二维的。
用户程序引发磁盘I/O请求后，系统处理流程：用户程序 -> 系统调用处理流程 -> 中断处理程序 -> 设备驱动程序。
减少缺页中断（缺页错误、换页错误）：
- 内存页框数，增加作业分得得内存块数
- 页面大小。页面划分越大，中断率越低。
- 替换算法的优劣影响缺页中断次数。
- 程序局部性。程序局部性好可减少中断。
总线是用于连接CPU、内存、外存和各种I/O设备并在它们之间传输信息的一组共享的传输线及控制电路。
总线按功能和规范可分为五大类型：
- 数据总线：在CPU与RAM之间来回传送需要处理或是需要储存的数据
- 地址总线：用来指定在RAM之中储存的数据地址
- 控制总线：将微处理器控制单元的信号，传送到周边设备，一般常见为USB Bus和1394 Bus
- 扩展总线：可连接扩展槽和电脑
- 局部总线：取代更高速数据传输的扩展总线
各种虚拟存储都是时间换空间，缓冲是用空间换时间。
利用通道实现了内存与外设之间数据的快速传输。
sleep方法会给其它线程运行的集合，而不管其优先级。yield只会给优先级相同的或者比自己高的线程运行的机会。sleep会使线程进入阻塞状态，yield进入就绪。
进程挂起的原因：1、终端用户的请求；2、父进程的请求；3、符合调节的需要；4、操作系统的需要。
一般来说，磁盘I/O进程的优先权要高于计算进程。
上下文切换需要完成：1、内存管理上下文；2、页表切换；3、切换内核态堆栈上下文数据；4、硬件上下文，主要部分为进程和CPU的任务状态寄存器。
硬件的存取访问时间分为三个部分：寻道时间Ts，旋转延迟时间Tr，传送时间Tt。
多关键字文件的特点是，在文件进行检索操作时，不仅仅对主关键词进行简单询问，还经常需要对次关键字进行其它类型的询问检索。（常见的有多重文件、倒排文件）
管态，又叫特权态，系统态或核心态。当CPU处理系统程序的时间，CPU会转为管态，CPU在管态下可以执行指令系统全集（特权指令、非特权指令）。
主存地址寄存器MAR和程序计数器PC的位数都取决于主存储器的容量，二者位数相等。
文件操作是唯一依据是文件句柄。