操作系统

计算机系统

硬件：寄存器，中断，CPU ALU 存储器，输入输出，通道，网络接口

操作系统建在硬件接口上，提供操作系统接口

软件通过trap自陷或系统调用转到操作系统服务

资源管理：硬件资源CPU，主存，IO，外部设备

中断：内部（软件中断，异常，系统调用），外部（硬件，设备，时钟）

中断响应：中断向量转移到程序入口地址，多级中断

程序状态字PSW：保存程序的状态，中断码，中断屏蔽位，每个处理器具备一个PSW寄存器

操作系统

特点：并发（进程），共享（资源），虚拟（内存），异步（中断）

进程

组成：程序段，数据段，PCB

（PCB常驻内存，具备PID标识，状态，优先级，现场...

创建进程：新的PCB实例）

基本状态：就绪（队列），执行（CPU），阻塞（IO）

进程 proceed graph PG有向无环图

线程共享进程资源，对应TCB

进程同步：资源共享，进程互斥：访问临界资源

进程通信：低级-控制信号，高级-共享存储区，管程

进程调度：FCFS，SJF，RR，

信号量

s >= 0，P操作申请

s < 0，阻塞

生产者消费者：共享缓冲区，互斥访问缓冲区

生产P，消耗缓冲区容量

消费V，释放缓冲区容量

死锁

条件：互斥，保留并请求新资源，不可抢占，环路等待

银行家算法：计算安全序列

最大资源需求量Max，已分配资源量Allocation，需求资源量Need=Max-Allocation矩阵相减

资源当前可用量Available已知

计算安全序列：

在Need中查找满足Available的行，标记该进程为完成，更新Available向量

重复查找和更新，安全序列可能不唯一

避免死锁：任意时刻，至少有一个进程能够获取资源并释放。

假设n个进程，都申请k个资源，最坏的情况下所有进程都分配了k-1，申请最后1个资源，那么至少需要 (k-1) \times n + 1 个资源才能避免死锁

解除死锁：资源剥夺，撤销（代价最小）进程

内存

（汇编得到的）逻辑地址（虚拟地址，相对地址）

（程序装入内存，通过地址重定位得到）物理地址（绝对地址）

重定位分为：静态（连续，不能扩充空间），动态（程序可以在主存中移动，可以共享）

内存空间分配：提高利用率，动态内存分配（分区，分页，分段，段页式）

• 内存管理策略 分区：固定，动态（减少内部碎片） 分页：内存分为页帧frame，程序分为页page，页表记录frame中存放的page 分段：按段、堆、栈划分内存，段长可变，由段表记录起始地址和长度 段页式：段划分为页（访问段表获取页地址，访问页表获取物理地址，访问物理地址取指令）
• 快表（高速缓存）：缓存最近使用过的页到帧的映射，未命中则访问页表，然后访问绝对地址

二级页表：外层页号加偏移量得到内层页号，访问内层页得到物理地址

• 局部性原理

程序运行无需全部装入内存，而是装入必要的页或段

时间局部性：访问过的数据会再次被访问

空间局部性：程序访问某个内存单元后，附近的单元也可能会在将来被访问

• Swapping 将某些进程、数据换出内存（离散分配，局部装入），页表存储物理地址和外存地址 缺页中断：保存中断状态

页面置换：最佳（最常时间不被访问），FIFO（替换最旧的页面），LRU（最近最少使用）

设备

IO，通道，总线

块设备：高速，可寻址

字符设备：低速，不可寻址

控制器：接收CPU命令，控制设备，总线：数据、地址、控制

缓冲：减少CPU中断频率

假脱机SPOOLING：通过缓冲将独占设备虚拟为共享设备

磁盘：（寻道时间）磁头移动到相应磁道上，（旋转延迟时间）扇区旋转到磁头下方，（访问时间）读写

文件

UNIX中分为普通文件、目录文件、设备文件

文件系统类型：FAT，NTFS，Ext2，HPFS

• UNIX文件的物理结构 数据块固定4KB，小于这个长度直接读写 大文件存在多个不连续的数据块中，使用索引（间接块）来寻址，4M一次寻址，4G多次寻址
• 文件目录 文件控制块（文件名，物理地址，长度，块数，rwx权限）
• 存取方法 顺序，随机

UNIX操作系统

权限：ugoa

文件类型：dlsbcp-

输入输出重定向

管道命令

正则表达式