概论

操作系统分类

  • 手工操作
  • 单道批处理:串行执行作业
  • 多道批处理:宏观并行运行,微观串行运行。 内存管理、内存保护、CPU调度、进程通信
  • 分时系统:CTSS、MULTICS、UNIX 通道技术:用于控制IO设备和内存间数据传输,有专用IO处理器,启动后独立于CPU 中断:CPU收到外部中断信号后,停下来处理中断事件,完成后回到断点继续工作
  • 实时系统 实时性:对请求严格时间范围内做出反应 可靠性:高度可靠 实时过程控制:工业、军事控制。 实时通信处理:电信、银行、飞机订票
  • 嵌入式操作系统 VxWork、嵌入式Linux、uC/OS-II、Windows CE、PalmOS
  • PC DOS系列、Windows系列、Unix系列
  • 分布式操作系统 计算机连接在一起,以获得极高运算能力(云计算)和广泛的数据共享(云储存)。实现处理上的分布,功能和任务的分布。

OS需要的硬件特性

受保护的指令

  • 访问硬件资源、访问IO设备、对内存管理状态操作(页表、段表、TLB)、某些特殊状态位的设置、停机指令
  • 管态:特权态、系统态、内核态
  • 目态:普通态、用户态
  • PSW,包括CPU的状态码、条件码和中断屏蔽码,判断是系统程序or用户程序
  • 管态->目态:设置PSW实现
  • 目态->管态:系统调用。

系统调用

  • CPU执行访管指令,引起访管中断
  • 处理器保存断点程序上下文环境(PSW、PC和其他寄存器),CPU切换到管态
  • 中断处理程序调用相应的系统服务
  • 中断处理结束后,恢复中断程序的上下文环境,CPU恢复目态继续执行

内存保护

  • 基址寄存器+边界寄存器

中断机制

  • 由于某事件发生改变了CPU上指令执行顺序
  • CPU暂停,保留现场,转去执行相应程序。执行完毕后返回断点继续
  • 同步中断:CPU执行指令时由CPU控制单元发出的中断,也叫“异常”
    • CPU检测到的异常 Fault、Trap、Abort。如算术溢出、除0、用户态使用特权指令
    • 程序设定的异常 即程序员通过int、int3指令发出的请求中断(软中断),实现系统调用
  • 异步中断:其他硬件设备在任意时刻发出的中断,每个中断有一个0-255整数(中断向量)表示
    • 可屏蔽中断:即IO中断,当外部设备或通道操作正常结束或发生错误产生的,如打印机完成或缺纸、读磁盘时驱动器无磁盘等
    • 不可屏蔽中断 由掉电、存储器校验错误等硬件故障引起的硬件中断

IO系统

时钟

  • 分时系统中时间片轮转
  • 实时系统中输出正确时间信号给实时控制设备
  • 记录用户和系统所需的绝对时间

死锁问题

条件

  • 互斥
  • 请求和保持条件
  • 不可抢占条件
  • 环路等待条件

对策

  • 无为而治
  • 死锁检测和解除

    • 检测算法
      • 单资源:检测封闭环路
      • 多资源:不断找既不阻塞又非独立的进程节点,消去请求和分配。若所有孤立则无死锁
    • 解除算法
      • 剥夺资源(危害取决于资源性质)
      • 进程回退(定期备份不同时刻进程状态,死锁后回退,不野蛮但存储和计算代价高)
      • 撤销进程(一直撤销进程直到解除)
  • 动态避免
    • 安全检查:银行家算法:如果安全就分配。但无用:不知道请求矩阵,进程个数不确定,资源个数不确定
  • 死锁预防
    • 破坏互斥条件:允许多个进程使用同个资源(假脱机打印),不普适
    • 破坏请求和保持条件:只允许一次请求所有资源:不知道需要多少、效率低。若申请时先释放所有可能饿死
    • 破坏环路等待条件:资源编号,按序申请。可避免死锁,但存在无法获取到全部资源的风险

存储管理

单道程序存储管理

  • 内存分为系统区用户区。应用程序装入用户区,和OS共享内存。结束后被新程序覆盖。
  • 简单开销小易于管理,适合单用户单任务。但只能运行一个程序,内存效率不高,程序bug会破坏OS,地址空间有限。

分区存储管理

又把用户区划分若干分区,每个进程一个分区

固定分区存储管理

分区大小、位置、个数不变。多小分区适量中等少量大。输入队列处理多个进程 内存分配表:分区号+地址+长度+状态+进程名字 内存分配:先放入输入队列,然后最先匹配、最佳匹配等。回收简单 内存利用率不高,内碎片多。总数固定不灵活。地址大小有限。

可变分区存储管理

  • 从空闲区划分内存给他,结束后释放
  • 避免内碎片,提高内存利用率。但有外碎片,且回收、分配、管理更复杂
  • 分区链表:占05-空53-占86-...
  • 分配方法
    • 最先匹配法:碰到第一个足够的,一分为二
    • 下次匹配法:记录当前位置(头指针移动)
    • 最佳匹配法:大小最接近的,外碎片难以利用
    • 最坏匹配法:找最大的
    • 内存回收:trivial

页式存储管理

  • 划分为物理页框,逻辑页面,不必连续
  • 页表:系统为每个进程建立一个页表,给出逻辑页面号和物理页面号的对应
  • 物理页面表:系统内设立。位示图描述物理页框分配情况。256个物理页面可用8个32位的字
    • 分配:检查是否还有N个空闲。若有则申请一个长度为N的页表,并把地址填入PCB。分配N个物理页框,编号填入页表,修改位示图,加N
    • 回收:根据编号计算位示图位置,写0,减N
  • 页号=地址/大小,偏移=地址%大小
  • 页表保存在内核中,有PTBR指示基址,PTLR指示大小
  • 每次访问内存需要两次访问 用TLB缓存常用页表项
  • 没有外碎片,内碎片大小平均半页。程序不必连续存放,便于管理。但程序必须全部装入内存,每个进程都需维护页表

段式存储管理

  • 单个地址空间不利于存储保护和存储共享
  • 以段为单位进行分配
  • 段表:系统为每个进程建立段表,存储的段号对应的起始地址和长度
  • 划分模块,可以分别编写、编译、保护、共享,无内碎片。但有外碎片,程序需全装如内存

段页式存储管理

  • 先分段,然后分页。内存划分按段式,以页面为单位分配
  • 段表:记录了每个段的页表起始地址和段长(而非段的起始地址)
  • 页表:每个段有一个,一个进程可能有多个。

虚拟存储技术(TLB,Cache)

  • 局部性原理:顺序执行、循环结构、数组操作
  • 虚拟页式:只装程序部分页面。可发出缺页中断请求换页。使用后备存储和后备页面
  • 页表表项:逻辑页号、物理页号、驻留位、保护位、修改位、访问位
  • 缺页中断:若有空闲物理页面则分配,否则替换一个,然后继续运行。若修改过则写回
  • 置换算法
    • 最优页面置换(OPT)(不现实)
    • (最近)最久未使用(LRU)(开销大,缺乏硬件支持)
    • 最不常用(LFU) 设置访问计数器,淘汰最小
    • 先进先出(FIFO) 选择驻留时间最长的,性能较差
    • 时钟页面置换(Clock) 若被访问后置1,缺页后指针旋转,0则淘汰1则置0
  • 举例:不同输入下系统策略的比较
    • LRU=FIFO 123412341234
    • LRU>FIFO 123124252
    • FIFO>LRU 123142314
    • LRU>Clock 123213414

工作集和驻留集

  • 工作集:进程当前使用的逻辑页面集合,W(t,delta),t为时刻,delta为容量(从t往前找delta个)
  • 驻留集:实际驻留在内存的逻辑页面集合
  • 固定分配:驻留集大小固定,各进程平均分配or按比例分配。采用局部页面置换,但分配难以确定。少则抖动大则浪费
  • 可变分配:全局页面置换,各并发进程竞争使用物理页面。性能好但开销大。
  • 缺页率算法:根据缺页次数/内存访问次数(或缺页平均时间间隔倒数)调整 这和置换算法、分配物理页面数、页面大小和程序编制方法(比如循环ij和ji)有关。
  • 页表结构
    • 多级页表:32位,4K,则20位逻辑页面号,12位页内偏移地址。前10位以及页表,接下来二级页表
    • 反置页表:根据物理页面号组织页表,作为索引。常用Hash
  • 缺段中断:内存够则装入,不够则紧缩或者淘汰一些段(虚拟段式存储)
  • 32bitwindows:内核中每个段有一个VAD,描述逻辑地址范围、是否共享、是否继承、保护属性

进程管理

进程

  • 进程=代码+数据+寄存器+堆栈+系统资源
  • 进程的特性:动态性、独立性、并发性
  • 运行->阻塞:等待输入 运行->就绪:切换了进程 就绪->运行 被选择 阻塞->就绪 等待发生
  • 系统为每个进程维护一个PCB。操作系统维护运行、就绪、阻塞队列

线程

  • 线程:并发执行,可以共享地址。进程=线程+资源平台。
  • 代码、数据、文件共享,栈、程序计数器和寄存器私有(线程优先级)。
  • 进程是资源分配的单位,线程是CPU调度单位。

进程间通信

  • 低级:只传送状态和整数。高级:任意数量 信号量、信号、共享内存、消息传递 分为直接(套接字)和间接通信、管道

进程互斥

  • 临界区:完成访问共享内存、文件的程序
  • 临界资源:需要互斥访问的共享资源
  • 互斥访问
    • 任何两个进程不能同时进入临界区
    • 不能事先假定CPU个数和运行速度
    • 进程运行在临界区外不能妨碍其他进程进入
    • 任何一个进程进入的要求在有限时间得到满足

基于关闭中断

  • 进入临界区后关闭所有中断(用来更新内部变量、链表)
  • 有可能临界区大量计算;不适用用户进程(忘记开启中断);不适用于多CPU

基于繁忙等待:

  • 方法1:while(lock);lock=1;do;lock=0类似图书馆借书,但可能出现lock的竞争
  • 方法2:强制轮转while(turn!=0);do;turn=1另一个对偶。保证只有一个进程,但违反第三个条件。
  • 方法3:Peterson方法调用enter和leave判断是否安全。
1
2
3
void enter(int process)
{other=1-process;interested[process]=1;turn=other;while(turn==other && interested[other]==true);}
void leave(int process){interested[process]=0;}
  • 繁忙等待浪费CPU,且低优先级在临界区,高优先级也想进入会死锁
  • 解决:无法进入后应该sleep,退出后应该wakeup别人。
  • 信号量:操作系统维护。用户进程只能初始化和PV原语。A先VPB后

进程调度

  • 何时调度:1.新进程2.进程结束3.进程阻塞4.IO完成5.时间中断。不可抢占调度1-3发生。可抢占1-5发生
  • 批处理:不可抢占 交互式:必须抢占 实时系统:可抢占
  • 周转时间T=E-S。平均周转时间。平均带权周转时间:W=Sigma(T/r) / N, r是实际
  • 等待时间:位于就绪队列时间 响应时间 :请求到相应的时间
  • 吞吐量:单位时间完成作业数。CPU利用率、设备均衡利用(搭配)
  • 调度算法
    • FIFO/FCFS按作业到达次序
    • SJF预计执行时间,先完成短的
    • RR就绪进程按FCFS排成队列。轮流执行时间片。公平有保证。Q小花销大,q大退化成FCFS。通常20-50ms
    • 优先级算法:SJF把需要用时作为优先级。
    • 静态优先级:低优先级可能饥饿
    • 动态优先级:可根据运行时间和等待时间调整优先级防止饥饿。
    • 可以不同优先级别分组,然后级别间优先级算法,同级别内时间片轮转。
    • 有锁的话可能出现优先级反转
    • 多级反馈队列算法:引入多个就绪队列,根据进程性质、类型分为若干子队列有不同优先级。前台交互式进程RR,后台批处理FCFS等。根据进程的运行反馈信息调整队列。
    • 新进程优先级高。若时间片未用完升级,否则降级。高优先级低时间片。IO繁忙的高优先级,CPU繁忙的低优先级减少调度次数。

IO

IO管理

机械部分(设备本身)+电子部分(设备控制器(芯片)or适配器(印刷电路卡),完成设备和主机通讯)

IO通信

  • IO独立编址 控制器每一个寄存器分配唯一port
  • 内存映像编址 把寄存器映射为内存地址 编程方便,但无cache,需要判断IOor内存
  • 混合编址 寄存器-独立,缓冲区-内存

IO控制

  • 程序循环检测方式(轮询、繁忙等待) 程序(驱动)不断检测IO状态(就绪or完成),CPU控制IO 浪费太多CPU
  • 中断驱动方式 IO完成后,控制器通过bus向中断控制器发出信号,如果接受,就将设备编号放在地址线并令CPU中断。CPU根据编号访问中断向量表,取出中断程序地址然后执行,最后向中断控制器发出确认信号
    1. CPU向设备控制器发出命令,启动读操作
    2. 设备控制器控制IO设备完成读操作,把数据保存在寄存器或缓冲区,中断CPU
    3. CPU把数据读入内存
  • 直接内存访问方式 DMA访问系统总线,代替CPU指挥IO和内存间数据传送 有寄存器如内存地址寄存器、字节计数器、多个控制寄存器(指出端口地址、数据传送方向、传送单位、字节数)
    1. CPU对DMA控制器编程,告诉他把什么数据传送到内存什么地方,并向磁盘控制器发出命令,让它去磁盘驱 动器读入所需的数据块,保存到内部缓冲区,并验证数据正确性。
    2. DMA控制器通过总线向磁盘控制器发出读操作,并把写入的内存地址打在Bus上
    3. 磁盘控制器取出一个字节,按地址写入内存
    4. 磁盘控制器向DMA发送确认信号,DMA吧内存+1,计数器-1
    5. DMA向CPU发送中断,告诉数据已完成

IO接口

  • 设备独立性 用户无需制定特定的设备类型
  • 统一命名 所有文件和设备采用相同的命名规则:路径名
  • 阻塞和非阻塞IO 进程启动系统调用后,是立即返回还是阻塞起来

设备驱动和中断处理

  • 方案1 用户—系统调用—设备驱动—IO(驱动阻塞)—中断信号—中断例程接管CPU唤醒驱动 只适用于互斥访问设备
  • 方案2 请求队列 IO请求的提交和实现分离。上层函数管理请求队列,底层函数负责硬件完成IO 用户—内核—上层函数—提交请求,阻塞—底层取出请求—完成请求 可以优化IO请求(如数据块重组)

设备独立的IO软件

  • 给上层应用统一接口
  • 给驱动程序统一接口
  • 提供设备无关的数据块大小
  • 缓冲技术

用户空间的IO软件

  • 库函数 write、read,把参数传给系统调用,后者完成实际IO
  • Spooling技术 多道系统中处理独占设备的方法。Virtual IO

磁盘

  • 扇区为最小寻址和存取单位,先移动磁头定位柱面,选中磁头等待扇区到达
  • 低级格式化:标出磁道和扇区,扇区=相位编码+数据+纠错码
  • 分区:划分为若干逻辑分区,每个分区可视为独立磁盘。第0扇区存放boot和分区表(起始扇区和大小)
  • 高级格式化:对每个逻辑扇区,生成引导块、空闲存储管理结构、根目录和空白文件系统

磁盘调度

柱面定位时间+旋转延迟时间+数据传送时间

  • 10000rpm,300扇区,512字节,读150kb,柱面平均6.9ms,旋转平均旋转时间一半(3ms),数据传输17微秒
  • 300个连续扇区:6.9+3+6=15.9
  • 随机300个:(6.9+3+0.017)*300
  • 一般柱面定位时间最久

调度算法

  • FCFS先来先服务,简单公平但效率不高
  • SSTF最短定位时间优先:性能好但两侧柱面有可能饥饿
  • 电梯算法:上界是柱面总数两倍

文件系统

文件

  • 命名:文件名.扩展名
  • 结构:无结构的字节流序列,以块为单位,包含若干个扇区
  • 分类:普通文件(ASCII、二进制文件)、目录文件
  • 属性:保护信息、创建者、只读、隐藏、系统、时间(创建、访问、修改)、长度

文件系统的布局

低格为若干个分区,主磁盘的0扇区为MBR,MBR结尾是一个分区表,记录每个分区的起始扇区和大小。

文件的物理结构

FCB是OS管理文件的结构,存放文件所有管理信息,文件存在的标志 FCB包含文件的类型、长度、所有者、访问权限、创建、访问、修改时间、物理块信息

  • 连续结构 容易实现、访问速度快、有外碎片、难以动态增长 用于早期、DVD
  • 链表结构 指针存在块内,顺序访问而不适合随机访问,速度慢,文件内容不对齐
  • 带FAT的链表 分离指针和文件数据,只需一次外存访问 表项的宽度=XX(物理块编号的位数) FAT表项个数=物理块个数 FAT大小=个数*宽度 FAT容量=个数*块
  • 索引结构 每个文件都有I结点存在FCB,逻辑快与物理块映射,只装载正在用的节点进内存

目录

  • 目录项:直接法=文件名+FCB,间接法=文件名+FCB地址。给定名字返回FCB 每个目录项32字节,文件名(8+3),属性1字节,创建时间日期各2字节,起始物理块编号2字节,长度4字节
  • 外存:目录结构、FCB
  • 内存:系统文件表(计数+FCB)、进程文件表(打开方式+读写指针+系统表指针)
    • 文件组织成索引文件,磁盘块512byte,文件10+1+1+1,每个地址2字节
    • 一个文件最多 10+28+216+2^24 个文件页

空闲空间管理

  • 位图法 16G硬盘 物理块1KB。则有16M bit=2M byte=2048物理块
  • 链表法 空闲物理块上有指针
  • 索引法 拿物理块存放空闲物理块编号,自身不分配

操作系统与安全

计算机安全的三个目标

  • 数据的私密性
  • 数据的完整性
  • 系统的可用性

数据加密

  • 私钥加密:加密解密都是秘密,两者简单对应。简单安全,但密钥传送有问题
  • 公钥加密:加密密钥无法推算解密密钥。二者互反。无需传密钥
  • 数字签名:MD5,SHA

用户认证

  • 基于用户名密码的认证:易于理解实现,输入保护 攻击:穷举法猜测用户名和密码。多线程回避次数限制
  • 基于用户所拥有的东西(塑料卡片、磁条卡、芯片卡)
  • 基于用户自身生物特征(指纹、声纹、视网膜、笔记)

系统内部攻击:

  • 特洛伊木马(Trojan Horse):无害程序内嵌破坏代码,用户“自愿”运行
  • 登陆欺骗(Login Spoofing):运行自己的login程序,盗窃用户名和密码,钓鱼网站
  • 逻辑炸弹(Logic Bomb):员工植入代码。若在岗则定期输入密码,辞退则引爆,破坏文件
  • 后门(Trap Door):系统中嵌入代码能绕开正常检查
  • 缓冲区移除(Buffer Overflow):攻击C语言缺少数组边界检查

外部攻击

病毒

  • 一段代码附着在宿主程序复制传播,可感染可执行程序、内存、引导扇区、驱动、宏。
  • 可执行程序病毒:动静太大容易察觉,重复感染,文件修改时间和大小,变覆盖为寄生
  • 常驻内存病毒:躲在两段,修改中断,运行在内核态,感染系统调用。需内存冷启动,bios放电清理,然后用光驱、软驱启动,杀毒。
  • 宏病毒:文档嵌入,文档操作(打开、关闭、激活)时可能激活

蠕虫:躲在内存,传播但不更改系统,通过网络传播

(1)程序是静态的,而进程是动态的;(2)程序是永久的,进程是短暂的;(3)程序的组成是代码,进程由程序、数据和进程控制块组成;(4)一个程序可以对应多个进程,通过调用关系,一个进程也可以包括多个程序;(5)进程可以生成其他进程,而程序不能生成新的程序。(5分)