操作系统复习
2021-01-29 19:42:28 0 举报AI智能生成
操作系统导论知识总结
作者其他创作
大纲/内容
CPU虚拟化
进程的概念
概念：运行的程序
进程状态：运行，就绪，阻塞
进程API
fork()：复制一个父进程，从fork返回处开始执行，父进程fork返回子进程pid,子进程返回0
wait()：父进程调用等待子进程执行完毕后返回
exec()：并没有创建新的进程，加载可执行程序覆写代码段，堆栈
受限直接执行
受限制的操作：进程要执行一些特权指令，需要通过系统调用的方式获得内核的服务，称为陷阱
进程之间的切换
协作方式：等待系统调用
非协作方式：操作系统通过CPU时钟中断方式获得控制权完成切换
保存和恢复上下文：将寄存器的值保存到内核栈，将内核栈保存的值恢复到寄存器
进程调度策略
指标：周转时间=完成时间-到达时间
FIFO策略
优化周转时间的策略
SJF策略：最短任务优先，非抢占式
STCF策略：最早完成时间优先，抢占式
指标：响应时间=首次运行-到达时间
优化响应时间
RR策略：轮转调度，每个工作执行一段时间就切换
多级反馈队列
规则1：如果A优先级>B的优先级，运行A
规则2：如果A的优先级=B的优先级，轮状调度A,B
规则3：工作刚到达系统时，优先级最高
规则4：如果一个工作用完它在该优先队列中的时间片，无论中间主动放弃多少次CPU都把他放到低一级队列中
规则5：隔一段时间S，把所有任务加到最高优先级队列
调度：比例份额
用彩票数表示一个任务占用资源的比例，通过随机数"抽奖"
步长调度：用一个很大的数除彩票数得到步长，每次选择行程值最小的先运行
陷阱和中断
陷阱：发生时间固定，系统初始化好陷阱表，为了通过系统调用获得内核服务
中断：不可预测
硬件中断
时钟中断
主要为了操作系统重新获得控制权完成进程切换
区别
CPU处理中断时屏蔽中断，处理陷阱时允许中断
内存虚拟化
物理内存的抽象--地址空间
为每个程序提供一个巨大的，稀疏的，私有地址空间的假象
栈-保存当前函数调用信息，分配空间给局部变量，传递参数和函数返回值、
堆-管理动态分配的，用户管理的内存
内存操作API
栈式内存：申请释放由编译器隐式管理，也称为自动内存
堆式内存：所有申请释放都由程序员显式完成
malloc：只需一个参数表示需要申请多少字节，返回一个指针指向内存块，内存不足返回null
free：接受一个malloc返回的指针作为参数
机制：地址转换
动态重定位：整个地址空间使用基址界限机制映射到物理内存
mmu：内存管理单元
缺点：效率低下，程序堆和栈空间之间的空闲空间使用不上
分段
给地址空间每个逻辑段一对基址界限寄存器
由虚拟地址某几位来表示引用哪个段，其他位表示段内偏移
栈是反向增长的
新的问题：物理内存充满空闲的小洞
空闲空间管理
底层机制
分割与合并
追踪已分配空间大小：分配空间时用一个8字节保存一些信息
嵌入空闲列表
堆可以增长
基本策略
最优匹配：遍历整个列表找到比申请块大且最小的内存
最差匹配：找最大的块
首次匹配：找到第一个合适的块
下次匹配：从上一次结束位置开始查找
其他方式
分离空闲列表
伙伴系统
问题：管理不同大小的内存块，总会导致内存碎片无法利用起来
分页
地址空间分为固定大小的单元——页，每个进程保存一个页表结构
页表作用：保存虚拟页到物理页的映射关系
问题：每次地址访问，增加了对页表的访问，地址访问相对较慢
问题：页表过大时，消耗内存大
分页：快速地址转换
TLB，利用缓存加速
TLB实际就是一个映射关系
TLB未命中跳转至陷阱处理程序
TLB内容：VPN | PFN | 其他位
分页：较小的表
多级页表！！！
超越物理内存：机制
地址空间比物理内存更大
交换空间：在磁盘开辟一部分空间用于物理页的移入和移出
超越物理内存：策略
最优替换策略：替换最远将来用到的页
FIFO：先入先出
随机
LRU：最少最近使用
近似LRU实现：使用一个使用位，如果是1表示最近被使用，每次使用都翻转
内存被超额请求：系统不停换页，发生内存抖动
并发
线程
概念：看起来像函数调用，但是开辟新的栈，一个程序有多个执行点，多个线程共享进程的地址空间
临界区：访问共享资源的一段代码
竞态条件：多个执行线程同时进入临界区
不确定性：程序由多个竞态条件组成，哪些线程先运行不确定，导致结果不确定各
线程API
线程创建pthread_create。四个参数
thread_t：指向thread_t的指针
attr：指定该线程可能具有的任何属性
第三个参数：入口函数的函数指针
函数参数
等待线程完成
pthread_t：用于指定线程
第二个参数是一个指针指定希望的返回值
锁
信号量
锁（实现互斥）
实际就是一个变量，一个线程获得锁时，其他线程无法获得，其他线程有锁，调用lock不会返回
控制中断：最早提供互斥方案——临界区关闭中断
实现一个锁
Test-And-Set：返回old_ptr指向的旧值，并更新为新值
Compare-And-Swap：如果旧值等于预期就更新值
链接的加载和条件式存储指令：上一次加载的地址中的值在期间没有被更新才行
获取并增加：ticket作为锁的顺序，turn作为全局顺序
条件变量（实现同步）
定义：实则是一个队列，把等待某个条件为真的线程放到一个队列
接口
wait调用，释放锁并休眠
signal调用，唤醒等待条件变量的线程
生产者/消费者问题
第一个方案，整体加锁，if判断，问题所在：两个消费者，另一个消费者抢先消费
第二个方案：if换while，两个消费者，消费者唤醒消费者
第三个方案：两个条件变量，对应唤醒消费者或者生产者
信号量
定义：有一个整数值对象，两个操作函数
sem_wait()：信号量>=1直接返回，否则等待下一次post，信号量-1
sem_post()：增加信号量的值，有线程等待则唤醒
信号量为负值表示等待的线程个数
二值信号量——锁
初始化为1
信号量作为条件变量
初值为0
生产者消费者问题
两个信号量：empty,full，empty初始为最大值，full为0
生产者等待信号量empty，生产值，唤醒full上等待的线程
消费者等待信号量full，消费，唤醒生产者
上述需要考虑get和pull是临界区
给一个锁，锁只负责put和get部分，否则会导致死锁
读者锁/写者锁问题
问题概述：允许多个读者线程，只允许一个写者线程
第一个读者获取写锁，最后一个退出的释放写锁
并发问题
非死锁缺陷：违反原子性，违反顺序
死锁缺陷，产生的条件
互斥：线程对于需要的资源进行互斥访问
持有并等待：线程持有资源并在等待其他资源
非抢占：线程获得锁不能被抢占
循环等待：线程之间存在一个环路，环路每个线程都持有一个资源，而这个资源是其他线程要申请的
持久化
磁盘驱动器
单磁道延迟：旋转时间
多磁道延迟：寻道时间
磁道偏斜：优化跨磁道边界连续读写
驱动器的缓存：实际本质是内存
write back后写缓存：写进缓存就通报完成，数据可能丢失，性能高
write through直写缓存：写到具体磁盘再通报，效率低
IO时间=T寻道+T旋转+T传输
磁盘调度算法
FIFO，先到先服务
SSTF：最短寻道时间优先
SCAN：电梯调度算法，磁头有方向，总是考虑该方向上最近的
CSACN：循环扫描，规定磁头只能单方向移动
RAID阵列
RAID-0
简单条带化
容量：N
可靠性：一个都不允许坏
读写性能
顺序读N*S
顺序写N*S
随机读N*R
随机写N*R
RAID-1
每个磁盘都有一个副本
容量N/2
可靠性：至少可以坏一个，至多N/2
读写性能
顺序读N/2*S
顺序写N/2*S
随机读N*R
随机写N/2*R
RAID-4
最后一块盘做奇偶校验
容量N-1
可靠性：至多坏一块
读写性能
顺序读(N-1)*S
顺序写(N-1)*S
随机读(N-1)*R
随机写1/2*R
RAID-5
旋转奇偶校验
容量N-1
可靠性：至多坏一块
读写性能
顺序读(N-1)*S
顺序写(N-1)*S
随机读N*R
随机写N/4*R
磁盘IO
打开一个文件
读inode，再读inode的数据块，递归找到具体文件的inode
子主题
职业：本科
0 条评论
下一页
