Hugo's Cyber Heritage

Shine or Die

OS-15：Review

发表于 更新于 分类于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

总复习

Overview

1

Content

OS-02 Functions and Structures
OS-03 Process
OS-04 Threads & Concurrency
OS-05 CPU Scheduling
OS-06 Process Synchronization
OS-07 Deadlocks
OS-08：main memory
OS-09：Virtual Memory
OS-10：storage
OS-11：File System
OS-12：I/O Systems
OS-13：Virtual Machine
OS-14：Distributed System

Resources

Introduction
Functions and Structures
Process
Thread
CPU scheduling
Process synchronization
Deadlocks
Main Memory
Virtual Memory
Storage
File System
IO System
Virtual Machine
Distributed System
Review

Process Management

Process

  • 概念 （PCB， 内存， 进程状态）
  • 进程调度（长、短），上下文转换
  • 进程操作 fork() exec() wait() exit()
  • IPC： shared memory, message passing

    Threads & Concurrency

  • 概念（与进程对比）
  • Parallelism vs. Concurrency
  • 内核线程 vs. 用户线程(线程库) 映射
  • pthreads： tid attr init create join

CPU Scheduling

  • 调度标准： CPU利用率、吞吐量、周转时间、等待时间、响应时间
  • 调度算法： FCFS, SJF, RR, Priority, 多级(反馈)队列调度
  • thread scheduling：PCS vs. SCS

Process Synchronization

  • 临界区问题
  • Peterson’s algorithm； 指令重排失效
  • 原子操作
  • 信号量： wait() signal()
  • mutex lock： acquire() release()

Deadlocks

  • 互斥、占有且等待、不可抢占、循环等待
  • 预防：破坏条件
  • 避免：银行家算法，资源分配图
  • 检测：资源分配图

其他

进程的实体为程序、数据和PCB，线程的实体为TCB、程序计数器、栈空间和寄存器集合。进程是资源分配与CPU调度的基本单位。线程共享进程的地址空间，但有私有的寄存器集合和栈空间。

等待时间不算I/O时间，周转时间算I/O时间。

Memory Management

Main Memory

  • 低内存：OS 高内存：用户进程
  • MMU：转换 保护机制：基址、限长寄存器
  • Contiguous memory allocation: (1) first fit, (2) best fit, and (3) worst fit.
  • Internal fragmentation vs. External fragmentation
  • paging： 物理frames，逻辑pages 页号+页偏移
  • TLB：“缓存”
  • swapping

page table 的 entry大小与page number无关. page size 和 offset有关。

Virtual Memory

  • Demand paging： page fault
  • COW：写（修改）时复制
  • Page replacement algorithms:
    • FIFO, LRU,
    • Optimal （栈， second chance）
    • counting（LFU）

Storage Management

Storage

  • 磁盘结构： cylinder、track、sector
  • 磁盘调度算法： FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK （C为跳转，SCAN移到头）
  • 挂载， swap-space
  • RAID： 0（striping） 1（mirroring） 4（块交错奇偶校验） 5（4+分布）

File System

  • Access methods: sequential, direct
  • 磁盘分区+文件系统=卷
  • 目录：
    • single-level, two-level, tree-structured, acyclic graph
    • file descriptor: inode

I/O Systems

  • 中断，轮询， DMA

Advanced Topics

Virtual Machines

  • VCPU： Trap-and-emulate（特权指令）， Binary translation（翻译特殊指令）
  • Type：0-硬件 1-软件 2-应用

Distributed Systems

  • Network OS vs. Distributed OS 是否可感知
  • Distributed File System： client-server、 cluster-based

Algorithms

  • CPU Scheduling
    • FCFS, SJF, RR, Priority
    • MQS, MFQS (有无队列移动)
  • Banker’s Algorithm
  • Memory allocation(Fit algorithms)
  • Page replacement
    • FIFO, LRU, Optimal
    • Second chance, counting
  • Disk scheduling
    • FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK
  • File allocation: I-node

Quiz

Producer-Consumer Problem

Threads

1
Answer： 子进程5 父进程0

Banker’s Algorithm

2

Main Memory

3
Answer:

Second chance algorithm

4