操作系统知识点散记

计算机系统概述

导论

• 

进程与线程

进程与线程

进程

状态

• 
• 
• ​进程=进程上下文+code, data, and \space stack、

进程图

• 几个函数：fork、wait、waitpid、execve、sleep、exit

异常控制流

• 
• 

通信

• 共享内存
• 消息传递
• 管道

线程

• ​进程=线程+code, data, and \space kernel\space context
• 

线程VS进程

• 
• 

多线程模型

• 1对1
• 多对1
• 多对多
• 双层

并发与同步

信号量（semaphore）

生产者-消费者

• empty、full、S1、S2......

读者-写者

• 引入计数器

哲学家进餐

• 信号量数组+防止死锁的互斥信号量

信号（signal）

• 信号不会排队
• 
• 
• 其中SIGSTOP和SIGKILL信号除外：这两个信号的默认操作不可被修改
• 常用的安全函数：_exit, fork, accept, kill, execve, signal, waitpid, writ
  • 异步信号安全（简称安全）：可重入的（例如只访问局部变量，之后会介绍）或者不能被信号处理程序中断。

CPU调度

• 几个参数
  1. CPU利用率
  2. 周转时间
     作业完成时间-作业提交时间
  3. 平均周转时间
  4. 等待时间
  5. 响应时间

先到先服务调度FCFS

最短作业优先调度SJF

优先级调度

轮询法调度RR

多级反馈调度MLRQ

彩票算法

死锁

四个条件

1. 互斥使用
2. 不可抢占
3. 请求和保持
4. 循环等待

避免死锁

银行家算法

内存管理

• 几个概念
  1. 虚拟地址
  2. 逻辑地址
  3. 物理地址
  4. 比较
  5. 逻辑地址空间
  6. 线性地址空间（虚拟地址空间）
  7. 物理地址空间
• 几个流程

  • 

  • 

    故，命中2次访存，不命中3次访存

  • 

  • 

内存管理

连续内存分配

1. 固定分配
   1. 内部碎片
2. 动态分配
   1. 外部碎片

分段式分配

分页式分配

• 不产生外部碎片

段页结合

请求式分页

虚拟内存

分配算法

• OPT ，最好
• FIFO , 有Belady异常
• LRU
• Clock
• 工作集分配
  • 固定分配
  • 可变分配

结合缓存

IO与存储

IO

IO控制

• CPU与DMA[[DMA]]

缓冲技术

• 单、双、环形、缓冲池
• Linux缓冲
  • buffer
  • sync
• 假脱机SPOOLing技术
  • SPOOL是操作系统中采用的一项将独占设备改造成共享设备的技术
  • 

磁盘

• 磁盘结构

  • 

• 磁盘IO

  • 磁盘访问延迟 = 队列时间 + 控制器时间 + 寻道时间 + 旋转时间 + 传输时间
  • 

• 磁盘调度

  • 先来先服务磁盘调度 First Come First Severed (FCFS)
  • 最短寻道时间优先磁盘调度 Shortest-Seek-Time First (SSTF)
  • 扫描/电梯算法磁盘调度 SCAN
  • 循环扫描/电梯算法磁盘调度 C-SCAN
  • C-LOOK磁盘调度

算法	磁头臂粘着	公平性	平均寻道时间
FCFS	不会	最好	较长
SSTF	会（严重）	差	最短
SCAN	会（较轻）	较好	较短
C-SCAN	不会	好	适中

• 
• 编号
  • 
• 页面交换
  • 

文件管理

文件系统

• FCB
• 权限

簇

• 几个盘块组成一个簇
• 按簇分配，而不按照块分配
• 创建文件数量=索引节点数量

1.连续分配

2.EXT2（UNIX）

• 索引方式（inode）
  • 地址项
  • 直接、一级、二级
  • 随机、可变

3.WIndows FAT

• 显示链接分配
  • FAT表

严禁转载！！！