进程的描述与控制
内核态与用户态
什么时候进入内核态：系统调用、异常、中断
为什么要有线程
在不引入线程概念的操作系统中，进程是资源分配和独立调度的单位。进程的创建、撤销和切换需要较大的时空开销，因此系统中进程的数量和进程切换的频率受到限制，影响系统并发性的提高。引入线程作为独立调度和分派的单位，不独立占有资源，而是与其他线程共享统一进程的资源，减小了系统的时空开销
进程和线程的区别
- 进程是资源分配的基本单位，线程是独立调度的基本单位
- 地址空间资源：不同进程的地址空间是相互独立的；同一进程的不同线程共享同一地址空间
- 通信：进程的通信需要使用操作系统提供的进程间通信机制；同一进程的不同线程可以通过读写全部变量通信
- 系统开销：创建和撤销进程时，需要系统为之分配和回收资源，操作系统付出的开销远大于创建和撤销线程时的开销。进程切换时，涉及到整个当前进程的CPU环境的保存的新的CPU环境的设置；切换线程时，只需保存和设置少量寄存器的内容，开销很小
孤儿进程
一个父进程退出后，它的一个或多个子进程还在运行，那么这些子进程将成为孤儿进程，孤儿进程将被init进程收养
进程中断的过程
- 保护现场，保护中断处理器的现场信息
- 修改中断进程的进程控制块信息，如进程状态等
- 把被中断的进程的进程控制块加入有关的队列
- 选择下一个占有处理器运行的进程
- 根据被选中进程设置操作系统用到的地址转换和存储保护信息
- 根据被选中进程恢复处理器现场
进程同步
进程间的通信方式
- 管道
- 信号量
- 消息缓冲队列
- 套接字socket
管道
操作系统在内核中开辟一块缓冲区用于通信。管道时一种两个进程间单向通信的机制。
进程调度
进程调度算法
- 先来先服务算法
- 短进程优先算法
- 优先权算法
- 时间片轮转算法
- 多级队列算法
- 多级反馈队列算法
时间片轮转算法
时间片过长或过短的影响
- 若时间片太长，则多数进程可以在一个时间片内处理完，能够缩短进程的周转时间，但是交互用户的响应时间会比较长
- 若时间片太短，则一个进程要经过多次调度运行才能执行完，进程切换和进程调度的开销会增加，系统的平均周转时间也会比较长
死锁
多个进程竞争共享资源而引起的进程不能向前推进的僵死状态叫做死锁
产生死锁的原因
- 竞争共享资源
- 进程推进顺序不当
产生死锁的条件
- 互斥条件
- 请求和保持条件
- 不剥夺条件
- 环路等待条件
处理死锁的基本方法
- 预防死锁
- 避免死锁
- 检测并解除死锁
- 忽略死锁，认为死锁不可能在系统内发生
死锁的预防
- 摒弃请求和保持条件：系统要求所有进程在执行前要一次性地申请整个运行过程中所需要的全部资源
- 摒弃不剥夺条件：一个已保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源
- 摒弃环路等待条件：规定进程必须按一定的顺序申请资源。对所有不同类型的资源排序，要求每个进程按递增顺序申请资源
死锁的避免
只要资源分配使系统资源分配处于安全状态，死锁就不会发生
安全状态：系统能找到一个进程执行序列，使系统只要按此序列为每个进程分配资源，就可以保证进程的资源分配和执行顺利完成，不会发生死锁时，称系统处于安全状态
银行家算法
死锁的检测和解除
资源分配图
死锁定理
S为死锁状态的充分条件是当且仅当S状态的资源分配图是不可能完全简化的
- 找到一个既不阻塞又非独立的进程节点pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量），消去它的请求边和分配边，使之成为孤立的节点
- 进程pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可以变为非阻塞进程。根据1中的方法进行一系列简化后，若能消去图中所有的边，则称该图是可完全简化的
死锁的解除
- 进程终止
- 资源抢占
- 回滚
饥饿：进程因长时间不能获得所需资源而处于无限等待的状态
内存管理
- 实现内存分配、内存回收等基本内存管理功能
- 提高空间的利用率和内存的访问速度
局部性原理：时间局部性、空间局部性
程序的装入和链接
绝大多数情况下，源程序需要经过编译、链接、装入几个阶段才能执行
程序的装入
- 绝对装入方式：事先已知程序在内存中的驻留位置
- 可重定位装入方式（静态重定位）
- 动态运行时装入方式（动态重定位）：地址映射必须延迟到进程执行时在进行
程序的链接
将编译后的目标模块装配成一个可执行的程序
静态链接
将目标模块链接成一个完整的装入模块
- 优点：静态链接程序运行的速度较快
- 缺点：
- 可执行目标比较大，占用的内、外存空间较大，使存储开销大
- 使程序开发不够灵活方便，修改某一个模块会导致整个程序的重新链接
动态链接
目标模块的链接推迟到执行时再进行
- 节省内存和外存空间
- 方便程序开发
- 程序运行时速度变慢
连续分配存储管理方式
连续分配是指操作系统分配内存时，为每个进程分配一块物理地址连续的内存空间
单一连续分配
适用于单用户单任务的OS
固定分区分配
将用户内存空间划分为若干个固定大小的区域，在每个用户分区中可以装入一道作业
数据结构：固定分区使用表
动态分区分配
根据进程的实际需要为进程分配大小合适的内存区域，系统中用户分区的数量和大小都是动态变化的
数据结构
空闲分区表、空闲分区链
动态分区分配的算法
- 首次适应算法FF
- 循环首次适应算法NF
- 最佳适应算法BF
- 最差适应算法WF
内存分配流程图
内存回收流程
- 释放一块连续的内存区域
- 如果被释放区域与其他空闲分区相邻，则合并空闲分区，否则为该回收区建立一个空闲分区链表的节点
- 修改空闲分区链表
紧凑
离散分配存储方式
分页式存储
LRU算法
最近最久未使用算法
实现方式：双向链表和hashmap
虚拟内存
操作系统为每一个进程分配一个独立的地址空间。虚拟内存与物理内存之间存在映射关系，通过页表寻址完成虚拟地址和物理地址的转换
使用虚拟内存的优点
- 扩大地址空间
- 内存保护：防止不同进程对物理内存的争夺和践踏，可以对特定内存地址提供写保护，防止恶意修改
- 可以实现内存共享，方便进程通信
- 可以避免内存碎片，虽然物理内存可能不连续，但映射到虚拟内存上连续
使用虚拟内存的缺点
- 需要额外构建数据结构，占用空间
- 虚拟地址到物理地址的转换，增加了执行时间
- 页面换入换出耗时
- 一页如果只有一部分数据，浪费内存
堆栈溢出
堆栈溢出就是不够堆栈中分配的局部数据块大小，向该数据块写入了过多的数据，导致数组越界。常指调用堆栈溢出，本质上一种数据结构的满溢情况
- 堆溢出: 不断地new一个对象，一直创建新的对象，而不进行释放，最终导致内存不足
- 栈溢出: 一次函数调用中，栈中将被依次压入：参数，返回地址等，而方法如果递归比较深或进去死循环，就会导致栈溢出
文件系统
软链接和硬链接的区别
- 定义不同
- 软链接又叫符号链接，这个文件包含了另一个文件的路径名。可以是任意文件或目录，可以链接不同文件系统的文件
- 硬链接就是一个文件的一个或多个文件名。把文件名和计算机文件系统使用的节点号链接起来。因此我们可以用多个文件名与同一个文件进行链接，这些文件名可以在同一个目录或不同目录
- 限制不同
- 硬链接只能对已存在的文件进行创建，不能交叉文件系统进行硬链接的创建
- 软链接可对不存在的文件或目录创建软链接；可交叉文件系统
- 创建方式不同
- 硬链接不能对目录进行创建，只可对文件创建
- 软链接可对文件或目录创建
- 影响不同
- 删除一个硬链接文件并不影响其他有相同inode号的文件
- 删除软连接并不影响被指向的文件，但若被指向的原文件被删除，则相关软链接被称为死链接（若被指向的文件被重新创建，死链接可恢复为正常的软链接）