[操作系统] Review

于由咪啪发布

PPT

复习资料

QUIZ

作业

实验

复习题

Chapter 1 Introduction
Operating system goals:
  • Execute user programs and make solving user problems easier.
  • Make the computer system convenient to use.
  • Use the computer hardware in an efficient manner.
Computer System Structure

Hardware、OS 、APP、Users

操作系统是系统软件
操作系统提供的接口
  • 命令级接口：键盘鼠标
  • 程序级接口：System call
Linux is a multi-user time-sharing system
OS 是系统资源的管理者
  • OS is a resource allocator
  • OS is a control program
MULTICS is the oldest OS
OS 合理、有效、方便
bootstrap program is loaded at power-up or reboot

存储在 ROM、EEPROM

interrupt vector

contains the address of all the service routines.

Interrupt

An operating system is interrupt driven

  • Polling 轮询
  • vectored interrupt system 矢量化中断系统
Computer System 体系结构

单处理器系统、多处理器系统、集群系统 Cluster

Program is a passive entity, process is an active entity.

程序是静态的，进程是动态的

Multiprogramming（多道程序）

Several jobs are kept in main memory at the same time, and the CPU is multiplexed among them. 程序按顺序使用CPU 【会产生饥饿】

Time-Sharing Systems 分时系统

第一个分时系统 CTSS。UNIX、Linux、Windows

Privileged instruction 特权指令

can be issued only in monitor mode.

例如：I/O指令、设置时钟、设置控制寄存器等指令都是特权指令。

trap

A trap（陷入） is a software-generated interrupt caused either by an error or a user request

Real-time system 实时系统

Vary considerable, special purpose, limited purpose OS, real-time OS

Real-time OS has well-defined fixed time constraints

不强求系统资源的利用率

Symmetric multiprocessing （SMP对称多处理器）
Secondary storage 二级存储

Hard Disk Drives、Non-volatile memory (SSD)

DMA 直接内存访问
  • Used for high-speed I/O devices able to transmit information at close to memory speeds.
  • Device controller transfers blocks of data from buffer storage directly to main memory without CPU intervention.
  • Only on interrupt is generated per block, rather than the one interrupt per byte.
The main disadvantage of the batch system is lack of interaction
Chapter 2 OS Structures
System Calls

Programming interface to the services provided by the OS

programming interface between processes and the OS kernel.

fopen() 是程序调用

open() 是系统调用

Operating System Services
  • User interface
  • Program execution
  • I/O operations
  • File-system manipulation
Simple Structure 简单结构

MS-DOS  its interfaces and levels of functionality are not well separated 无良好分层

Layered Approach 层级化结构

缺点：不能越级访问

Monolithic Kernels Structure 单/宏内核结构
  • 优点:共享文件很方便，读写效率高
  • 缺点: 太大了，很容易出bug，很难扩展和修改，可能会导致源代码中出现复杂的嵌套
  • OS/360, VMS and Linux
Microkernel 微内核
  • 优点:易扩展，更容易将操作系统移植到新架构，更安全，更可靠
  • 缺点:效率低
  • Win8 Win10 MacOS
Modules 模块

Linux , Solaris, etc

  • 使用面向对象的方法
  • 每个核心组件都是独立的
  • 每个通过已知接口与其他人交谈
  • 每个内核都可以根据需要加载
Hybrid Systems

eg:Android、IOS、MacOS

Virtual Machines

A virtual machine takes the layered approach to its logical conclusion. It treats hardware and the operating system kernel as though they were all hardware.

Chapter 3 Processes
A process is a program in execution
process is a dynamic concept
Process includes
  • The program code, also called text section
  • Program counter (PC)
  • Registers
  • Data section (global data)
  • Stack (temporary data)
  • Heap
Process State

New、Running、Ready、Waiting、Terminated

124 #define TASK_RUNNING 0
125 #define TASK_INTERRUPTIBLE 1
126 #define TASK_UNINTERRUPTIBLE 2
127 #define TASK_STOPPED 4
128 #define TASK_TRACED 8
129 /* in tsk->exit_state */
130 #define EXIT_ZOMBIE 16
131 #define EXIT_DEAD 32
132 /* in tsk->state again */
133 #define TASK_NONINTERACTIVE 64

进程与程序的区别

  • 进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。
  • 进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。
  • 进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。
  • 进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。
PCB
  • Program code (text) PCB没有完整代码段
  • Data
    • global variables
    • heap (dynamically allocated memory)
  • Process stack
    • function parameters
    • return addresses
    • local variables and functions
  • OS Resources, environment
    • open files, sockets
    • Credential for security
  • Registers
    • program counter, stack pointer
调度类型

长程调度、作业调度 Long-term scheduler

selects which processes should be brought into the ready queue

短程调度、CPU调度 Short-term scheduler

selects which process should be executed next and allocates CPU

Context Switch

PCB切换

fork()计算

int pid1 = fork();

从系统调用 fork 中返回时，两个进程除了返回值 pid 1不同外，具有完全一样的用户级上下文。在子进程中，pid1 的值为0;父进程中， pid 1的值为子进程的进程号。fork从原程序的那一句开始执行。

exec()

system call used after a fork to replace the process’ memory space with a new
program.

Advantages of process cooperation
  • Information sharing
  • Computation speed-up
  • Modularity
  • Convenience

IPC

IPC provides a Mechanism for processes to communicate and to
synchronize their actions without sharing the same address space .

常用通信机制：
  • 信号(signal)
  • 共享存储区(shared memory)
  • 管道(pipe)
  • 消息(message)
  • 套接字(socket)
Pipe

操作系统中提供了一种进程间的通信机制，把一个进程的标准输出与另一个进程的标准输入连接起来，这种机制称为管道

Socket

用于C/S模型中

Message-Passing System

A kind of inter-process communication

communicate with each other without resorting to shared variables

  • Direct Communication
    • The link may be unidirectional, but is usually bi-directional
  • Indirect Communication
    • mailboxes
    • A link may be associated with many processes
  • Blocking（阻塞） is considered synchronous
  • Non-blocking （非阻塞） is considered asynchronous
Shared-Memory Systems

* 在死锁章节有详解

Chapter 4 Threads
The concept of a process as embodying two characteristics
  • Unit of Resource ownership资源分配单位
  • Unit of Dispatching 调度单位
线程定义为进程内一个执行单元或一个可调度实体。

线程只拥有一点在运行中必不可省的资源（程序计数器、一组寄存器和栈），但它可与同属一个进程的其它线程共享进程拥有的全部资源。

线程共享资源：
  • code section
  • data section
  • operating-system resources
Thread Benifits
  • 创建一个新线程花费时间少（结束亦如此）
  • 两个线程的切换花费时间少
  • 因为同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核
  • 适合多处理机系统
User Threads

不依赖于OS内核（内核不了解用户线程的存在），应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。

Kernel Threads

依赖于OS核心，由内核的内部需求进行创建和撤销，用来执行一个指定的函数。一个线程发起系统调用而阻塞，不会影响其他线程。时间片分配给线程，所以多线程的进程获得更多CPU时间。

Multithreading Models
  • Many-to-One Many user-level threads mapped to single kernel thread
    • Disadvantages ：Entire process blocks when one thread
      blocks
  • One-to-One  Each user-level thread maps to kernel thread
    • Advantages
      • Each kernel-level thread can run in parallel on a multiprocessor
      • When one thread blocks, other threads from process can be scheduled 不会阻塞
    • Disadvantages
      • Higher overhead for thread operations 高额管理费用
      • OS must scale well with increasing number of threads
  • Many-to-Many
Linux Thread

Thread creation is done through clone() system call

Linux refers to them as tasks rather than threads

TCB

TCB（线程控制块）存储：The machine state（寄存器、程序计数器）

Chapter 5 CPU Scheduling
周转时间Turnaround time

进程从提交到完成所经历的时间。包括：在CPU上执行，就绪队 列和阻塞队列中等待。

响应时间Response time 

从进程提出请求到首次被响应（而不是输出结果）的时间段（在分 时系统环境下）

First-Come, First-Served (FCFS) Scheduling 先来先服务调度

按照进程或作业提交顺序形成就绪状态的先后次序，分派CPU

  • 比较有利于长进程，而不利于短进程。
  • 有利于CPU Bound的进程，而不利于I/O Bound的进程。
  • 平均等待时间通常较长
Shortest-Job-First (SJF) Scheduling 短作业优先调度
  • 对预计执行时间短的作业（进程）优先分派处理机。
  • 最小平均等待时间
  • 缺点：饥饿（starvation）
  • CPU调度算法SJF没有在LINUX的2.6以后的版中使用。
Priority Scheduling 优先权调度
  • 数字越小，优先级越高
Round Robin (RR) 时间片轮转调度
  • 进程可以未使用完一个时间片，就出让CPU（如阻塞）。
Multilevel Queue Scheduling 多级队列调度
  • 根据进程的性质或类型的不同，将就绪队列再分为若干个子队列。
Multilevel Feedback Queue Scheduling多级反馈队列调度

多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。优点：

  • 为提高系统吞吐量和缩短平均周转时间而照顾短进程
  • 为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程
  • 不必估计进程的执行时间，动态调节
  • 为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级。
高响应比优先调度算法 Highest Response Ratio Next(HRRN)
  • 响应比R = (等待时间 + 要求执行时间) / 要求执行时间
  • 是FCFS和SJF的折衷
Chapter 6 Process Synchronization
Atomic operation
  • means an operation that completes in its entirety without interruption.
Race condition 竞争条件
  • The situation where several processes access and manipulate shared data concurrently. The final value of the shared data depends upon which process finishes last. Outcome of execution depends on the particular order in which the access takes place.
竞争控制问题：
  • 互斥（mutual exclusion ）、死锁（deadlock )、饥饿（starvation )

进程两个最基本特性

  • 并发行
  • 独立性
Critical-Section 临界区
  • Each process has a code segment, called critical section（临界区）, in which the
    shared data is accessed. 临界区修改共享数据，临界区是访问临界资源的那段代码。
临界资源
  • 一次只允许一个进程使用(访问)的资源。
解决方案必须满足

1.Mutual Exclusion（互斥）
2.Progress（空闲让进）
3.Bounded Waiting（有限等待）

Various software solutions –Peterson’s algorithm
  • 软件使用 Peterson’s 算法实现
Hardware solutions 硬件解决
  • atomic operations, like test-and-set
  • 优点
    • 适用于任意数目的进程，在单处理器或多处理器上
    • 简单，容易验证其正确性
    • 可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量
  • 缺点
    • 等待要耗费CPU时间，不能实现”让权等待”
    • 可能“饥饿”：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上
    • 可能死锁：单CPU情况下,P1执行特殊指令(swap)进入临界区，这时拥有更高优先级P2执行 并中断P1,如果P2又要使用P1占用的资源，按照资源分配规则拒绝P2对资源的要求，陷入忙等循环。然后P1也得不到CPU，因为P1比P2优先级低。硬件解决会导致 busy-waiting
Binary semaphore（二值信号量）
  • integer value can range only between 0 and 1;can be simpler to implement
  • Also known as mutex locks
Counting semaphore （计数信号量）

integer value can range over an unrestricted domain

信号量的物理含义

  • S.value >0 表示有S.value个资源可用；
  • S.value=0 表示无资源可用或表示不允许进程再进入临界区；
  • S.value<0 则|S.value|表示在等待队列中进程的个数或表示等待进入临界区的进程
    个数。

wait(S)≡P(S) ≡ down(S) ： 表示申请一个资源 applying是错的
signal(S)≡V(S) ≡ up(S) ： 表示释放一个资源

Classical problems of synchronization
  • Bounded-buffer 生产者消费者问题
    • full = 0, empty=n, mutex=1
    • wait(empty) wait(mutex) signal(mutex) signal(empty)
    • 只要存在空就可以写入，只要存在满就可以读出
    • In the producer-consumer problem, the order of wait operations cannot be reversed, while the order of signal operations can be reversed. wait顺序不能变 但sign顺序可以变
  • Readers-writers 读者-写者问题
    • 读读不互斥，读写互斥，写写互斥
    • mutex=1, wrt=1, readcount=0
    • 读者：
  • Dining-philosophers 哲学家就餐问题
    • chopsticks[5]=1
    • 解决饥饿的方式：存在一个哲学家按倒序等待筷子
自旋锁 spinlock
  • Windows、Linux内核用来达到多处理器互斥的机制“自旋锁”

Busy-waiting & No busy-waiting

  • 信号量是 no busy-waiting
  • 硬件解决是 busy-waiting 

Critical section & Excusion section

  • Critical section 初始化为 1
  • Exclusion section 初始化为 n（缓冲区大小）
Chapter 7 DeadLocks
DeadLock
  • A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.

 

死锁产生的四个必要条件

  • 互斥（Mutual exclusion）
  • 占有并等待、请求和保持（Hold and wait）对已经获得的其它资源保持不放
  • 不可抢占（No preemption）
  •  循环等待（Circular wait）

 

死锁定理
  • Cycle and if only one instance per resource type, then deadlock.
  • S为死锁状态的充分条件是：尚且仅当S状态的资源分配图是不可完全简化的。（有环）

 

Prevention 死锁预防

分配资源之前，使4个必要条件一个不符合即可。

  • Mutual Exclusion 互斥
    • 虚拟化 Restrain the ways request can be made
  • Hold and Wait 请求保持
    • 资源静态预分配方式
    • 保证分配时该资源不含其他资源
  • No Preemption 非抢占
    • 回退
    • 如果一个拥有某些资源的进程请求另一个不能立即分配给它的资源，那么当前持有的所有资源将被释放
  • Circular Wait 循环等待
    • 资源的有序申请

 

Avoidance 死锁避免
  • 如果产生死锁，则不分配资源。
  • 实质是保证系统不进入非安全状态。

 

Safe State 安全状态
  • 系统能按照一个安全序列顺序执行完全部进程。
  • 若系统此状态不存在一个安全序列，则称系统处于不安全状态。

 

Resource-Allocation Graph Algorithm 资源分配图算法
  • 假设进程Pi申请资源Rj。只有在需求边Pi ->Rj 变成分配边 Rj-> Pi 而不会导致资源分配图形成环时，才允许申请。
  • 用算法循环检测，如果没有环存在，那么资源分配会使系统处于安全状态。如果存在环，资源分配会使系统不安全。进程Pi必须等待。

 

Banker’s Algorithm 银行家算法
  • Dijkstra
  • 没有系统在使用银行家算法
  • 是 Avoidance 的一种算法
  • Available Rj类资源有k个可用
  • Max 行表示某一个进程对所有资源的请求，M[i,j]表示Pi进程对Rj资源最大的需求是k个
  • Allocation Rj资源对Pi已分配了k个
  • Need Pi还需k个Rj资源

 

  • Initialize: Work = Available Finish [i] = false for i = 1,2,3, …, n.
  • Find an index i such that both:(a). Finish[i] = false(b). Need[i] <= Work
  • Work = Work + AllocationFinish[i] = truego to step 2.
  • If Finish[i] == true for all i, then the system is in a safe state.所有进程完成

 

Detection Algorithm 死锁检测算法

Deadlock Detection 的一种算法

  • Work = Available
  • For i = 1,2, …, n, if Allocationi != 0, then Finish[i] = false;otherwise, Finish[i] = true.
  • Find an index i such that both:
    (a) Finish[i] == false
    (b) Requesti <= Work
  • Work = Work + Allocationi Finish[i] = true go to step 2.
  • If Finish[i] == false, for some i, 1 <= i <= n, then the system is in deadlock state. Moreover, if Finish[i] == false, then Pi is deadlocked. 存在一个Finish[i] = false 则产生死锁
  • 相当于无法完成银行家算法？

 

Recovery 死锁解除
  • 打破死锁的两种方式：
    • 进程终止
    • 抢占资源
  • 回退
Chapter 8 Main Memory

Logical address 逻辑地址

  • generated by the CPU; also referred to as virtual address
  • 其首地址为0，其余指令中的地址都相对于首地址来编址

Physical address 物理地址

  • 绝对地址
  • 内存中存储单元的地址。物理地址可直接寻址

Logical address space  逻辑地址空间

  • A pair of base and limit registers（基址寄存器和限长寄存器）define the logical
    address space 基址寄存器和限长寄存器决定。
Memory-Management Unit (MMU)
  • Hardware device that maps virtual to physical address
  • MMU中每次将 relocation register 的值加在每个逻辑地址上去寻址。

Dynamic Loading 动态加载

  • Libraries loaded into memory only when needed
  • Libraries are stored on disk in relocatable form

Dynamic Linking 动态链接

  • external libraries can be preloaded into (shared) memory
  • System also known as shared libraries
Swapping 交换
  • Linux、UNIX—交换区
  • Windows—交换文件(pagefile.sys)
碎片产生
  • 固定大小分区：内碎片
    • is wasted memory within a single process memory space
  • 动态可变分区：外碎片
    • can reduce the number of runnable processes

Contiguous Allocation 分区方式

  • Fixed partitioning（固定分区）
  • Dynamic Partitions（动态分区）
    • 动态划分内存，在程序装入内存时把可用内存“切出”一个连续的区域分配给该进程，且分区大小正好适合进程的需要。
减少外部碎片的方式
  • Compaction or Defragmentation （紧缩，拼接）
三种装入方式
  • 绝对装入：编译时产生相对地址。（单道程序阶段）
  • 可重定位装入：装入时将逻辑地址转换为物理地址。（用于早期多道批处理操作系统）
  • 动态运行时装入：运行时将逻辑地址转换为物理地址，需设置重定位寄存器。
    • execution time

Variable-size partition 动态分区

  • 首次适应 first-fit：分配第一个足够大的孔。
  • 最佳适应 best-fit：分配最小的最够大的孔。
  • 最差适应 worst-fit：分配最大的孔。
  • 比较：
    • 执行时间和空间利用 ：首次适应和最佳适应 > 最差适应
    • 执行时间：首次适应>最佳适应
    • 空间利用：首次适应～最佳适应
Pages
  • Divide logical memory into blocks of same size called pages
Frame
  • Divide physical memory into fixed-sized blocks called frames
Page table
  • 列出了进程的逻辑页与其在主存中的物理帧间的对应关系
Page Table Address Translation Scheme
  • 逻辑地址空间为2m，页大小为2n（字或字节），逻辑地址表达为p|d
  • 页号 p 位数= m-n，页偏移 d 位数= n
Memory access
  • In this scheme every data/instruction access requires two memory accesses. One for the page table and one for the data/instruction. 一般情况需要访问两次内存，一次访问内存上的页表，一次访问页表指向的数据地址。
  • 使用 TLB 可以减少内存访问、
TLB 快表
  • Hardware cache
Effective Access Time 有效访问时间
  • T = 内存访问时间
  • A = 命中率
  • B = 快表访问时间
  • EAT = (T+B) A + ( T + T + B) (1 – A)
Valid-invalid bit 有效位
  • Memory protection implemented by associating protection bit with each frame
Shared Pages
  • Shared code
    • One copy of read-only (reentrant) code
    • 一个复制，所有进程使用同一逻辑地址
  • Private code and data
    • Each process keeps a separate copy of the code and data
    • 不同进程使用不同的逻辑地址
页表类型
  • 多级页表
    • 偏移位的长度不变。
    • 根据层数划分page number。
    • Linux： four-level page table
      Windows：two-level page table
  • 哈希页表
    • page number 的哈希值存入 page table。
    • 通过 hash fuction 查找对应的 page。
    • SPARC Solaris (64位)
  • 反向页表 Inverted Page
    • 只保存 real page of memory（物理地址）
    • 整个系统只有一个页表，所有进程都使用同一个
    • 可以与哈希页表一起使用
    • 共享页表困难
    • pid|p|d 查找 pid|p 在页表的第 i 个，则物理地址为 i|d
    • UltraSPARC(64位) ，PowerPC (64位)
段表 Segment table
  • Hardward
  • base Segment-table base register (STBR) （段表基址寄存器）
  • limit Segment-table length register (STLR) （段表限长寄存器）
    • segment number s is legal if s < STLR

 

Chapter 9 Virtual Memory

页表项

  • 状态位P（存在位）：用于指示该页是否已调入内存，供程序访问时参考。
  • 访问字段A：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页时参考。
  • 修改位R/W：表示该页在调入内存后是否被修改过。
  • 外存地址：用于指出该页在外存上的地址，供调入该页时使用。
虚拟内存管理的基础：局部性原理

缺页 Page fault

  • first reference to that page will trap to operating system
  • 系统会检测是非法访问还是缺页
  • 找到空白帧换入，置v
  • 重启产生缺页的指令 
Effective memory-access time EAT
  • P = 缺页率
  • EAT = （1-P） * 访存时间 + P * 缺页服务时间
Copy-on-Write
  • allows both parent and child processes to initially share the same pages in memory
  • If either process modifies a shared page, only then is the page copied
  • 在写时拷贝一个，而不会修改原本的内容。
First-In-First-Out Algorithm (FIFO，先进先出算法)
  • 会产生 Belady’s Anomaly
Optimal Algorithm （OPT 最佳页面置换算法）
  • 最优解，但不可能实现。
  • 选择“未来不再使用的”或“在离当前最远位置上出现的”页被置换。
Least Recently Used (LRU) Algorithm (最近最少使用算法)

但由于需要记录页面使用时间，硬件开销太大。

LRU Approximation Algorithms （近似LRU算法） ：
  • Additional-Reference-Bits Algorithm 附加引用位算法
    • 被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小
      的是最久未使用页面。
  • Second-Chance（clock） Algorithm
    • 又称NRU算法  Not Recently Used
    • 也会产生 Belady’s Anomaly
  • Enhanced Second-Chance Algorithm
Counting-Base Page Replacement：
  • Least Frequently Used Algorithm (LFU最不经常使用算法）
  • Most Frequently Used Algorithm (MFU引用最多算法)
页面缓冲算法
  • Windows、Linux页面置换算法是基于页面缓冲算法。
  • VAX/VMS系统使用
帧分配方式
  • Equal allocation（平均分配算法）
  • Proportional allocation （按比例分配算法）
  • Priority Allocation（优先级分配）
 帧分配策略、置换策略
  • 置换策略：全局置换、局部置换
  • 分配策略：固定分配、可变分配
  • 搭配组合：
    • 固定分配局部置换策略
    • 可变分配全局置换策略
    • 可变分配局部置换
    • 没有固定分配全局置换
Thrashing 颠簸
  • a process is busy swapping pages in and out
  • 解决方式：增加内存大小 
Chapter 10 File System Interface
Open()
  • search the directory structure on disk for entry Fi, and move the content of
    entry to memory 读取的是 file control information
  • 在打开文件之前执行。
  •  reading file control information from outer storage into memory
    • File pointer: pointer to last read/write location, per process that has the file open
    • File-open count: counter of number of times a file is open – to allow removal of data from open-file table when last processes closes it
    • Disk location of the file: cache of data access information
    • Access rights: per-process access mode information
Close()
  • move the content of entry Fi in memory to directory structure on disk
  • 在关闭文件之前执行。
文件结构
  • 无结构文件（文本文件）又称流式文件 sequence of words, bytes
  • 有结构文件（数据库表）Simple record structure
文件属性 Attributes
  • 文件名：主要为了方便用户找到文件，同一目录下不允许有重名文件 
  • 标识符：一个系统内各文件标识符唯一，对用户来说无可读性。
  • 类型：文件的类型。设置默认打开程序。
  • 位置：文件存放的路径（用户）、在外存中存放的路径（大小）。
  • 大小、创建时间、上次修改时间、文件所有者信息、保护信息……
Access Methods
  • Sequential Access （顺序存取）
  • Direct Access （直接存取）
  • Indexed sequential-acess（索引顺序）
Directory Structure
  • Single-Level Directory
    • 不允许文件重名
  • Two-Level Directory（二级目录）
    • Separate directory for each user
    • No grouping capability 不能对文件进行分类
  • Tree-Structured Directories（树型目录）
    • Absolute or relative path name 绝对路径、相对路径
    • mkdir 创建新目录 rm 移出文件
    • 每次读入目录表需要一次IO操作
    • 缺点：不便于实现文件的共享
  • Acyclic-Graph Directories无环图结构目录
    • Have shared subdirectories and files
    • Entry-hold-count solution （表项保留计数）unix、linux:hard links
Entity containing file system known as a volume
Mount 挂载
  • A file system must be mounted before it can be accessed
  • A unmounted file system is mounted at a mount point
File Sharing
  • Network File System (NFS)is a common distributed file-sharing method UNIX
  • Consistency semantics specify how multiple users are to access a shared file simultaneously
  • CIFS is standard Windows protocol
权限与安全
  • File owner/creator should be able to control:
    • what can be done
    • by whom
  • Mode of access: read, write, execute
  • Three classes of users: owner access、group access、public access
Chapter 11 File System Implementation
硬链接 & 软链接
  • 硬链接 inode 共享
  • 指向各自的用户打开文件表中的一项。
Free-Space Management 空闲空间管理方式
  • 位图法 Bit vector
    • 0表示空，1表示占用，每一块占用1位表示
    • Easy to get contiguous files
    • 需要额外空间
    • Must be kept on disk
    • Copy in memory and disk may differ
      • 解决方法：先改磁盘再改memory
  • Linked list (free list，空闲链表)
    • Cannot get contiguous space easily
    • No waste of space
  • Grouping （分组）—Unix 成组连接法(next page)
  • Counting（空闲表）
File control block FCB
  • storage structure consisting of information(Attributes) about a file
  • File control block is created on disk when open system call
  • Commonly, In memory the file control block of a file does not contain the file name
VFS （Linux）虚拟文件系统
  • VFS是物理文件系统与服务之间的一个接口，它屏蔽各类文件系统的差异，给用户和程序提供一个统一的接口。provide an object-oriented way of implementing file systems.
LTFS(Liner Tape File System，线性磁带文件系统)
  • LTFS为磁带提供了一种通用、 开放的文件系统。

In-Memory File System Structures

  • An in-memory partition table(分区表)
  • An in-memory directory structure（目录结构）
  • The system-wide open-file table （系统打开文件表）
  • The per-process open-file table （进程打开文件表）
On-Disk file system structures
  • Boot control block contains info needed by system to boot OS from that volume
  • Volume（卷） control block contains volume details
  • Directory structure organizes the files
  • Per-file File Control Block (FCB，文件控制块) contains many details about the file

目录实现

  • Linear list（线性检索法）of file names with pointer to the data blocks
  • Hash Table（哈希表） – linear list with hash data structure.
    • 可能产生重名
  • 索引
Contiguous allocation（连续分配）
  • 优点：
    • 连续分配支持顺序访问和直接访问（随机访问）。Random access
    • 连续分配的文件在顺序读写时速度最快。
  • 缺点：
    • 物理上采用连续分配不方便拓展文件。Files cannot grow
    • 存储空间利用率低，会产生难以利用的磁盘碎片。可以用紧凑来处理碎片，但会花费大量时间。Wasteful of space (dynamic storage-allocation problem)
Linked allocation （链接分配）

记录起始块号和结束块号。磁盘块中会保存指向下一块的指针。

  • 优点：
    • 方便文件拓展，且利用率很高。
  • 缺点：
    • 只支持顺序访问，不支持随机访问。需要存放指针增加空间。
File-allocation table (FAT)

显式存放链表，一个磁盘仅设置一张FAT，开机时将FAT读入内存，并常驻内存。

  • 优点：逻辑块号转换为物理块号的过程不需要读磁盘操作。转换过程不访问磁盘，访问速度快。支持顺序访问，支持随机访问。
  • 缺点：文件分配表需要占用一定的存储空间。
  • 计算机系统启动时，首先执行的是BIOS引导程序，完成自检，并加载主引导记录和分区表，然后执行主引导记录，由它引导激活分区引导记录，再执行分区引导记录，加载操作系统，最后执行操作系统，配置系统。

File System (NTFS)

  • MFT由一个个MFT项（也称为文件记录）组成，每个MFT项占用1024字节的 空间。
  • MFT前16个记录用来存放元数据文件的信息，它们占有固定的位置。
  • 每个MFT项的前部几十个字节有着固定的头结构，用来描述本MFT项的相关信 息。后面的字节存放着文件属性等。
  • 每个文件或目录的信息都包含在MFT中，每个文件或目录至少有一个MFT项。
  • Win10使用了 NTFS 
Extent-Based Systems （基于长度系统）
  • An extent is a contiguous block of disks
  • A file consists of one or more extents 文件可以有多个区构成
Indexed allocation（索引分配）

系统为每个文件建立一张索引表，索引表中记录文件各个逻辑块对应的物理块。索引表存放的磁盘块称为索引块 index block，文件数据存放的磁盘块称为数据块。

  • 优点：支持随机访问和文件拓展。
  • 缺点：索引表需要占用一定的存储空间。
  • 连接方案：如果索引表太大，则用多个索引块链接起来存放。在最后一个中链接下一个索引表的块号。
Chapter 12 Mass-Storage Systems
FCFS 先来先服务

SSTF 最短寻道时间优先

  • 当前位置最短时间
  • 缺点：每次都需要排序

may cause starvation of some requests

SCAN 算法
  • SCAN 电梯算法，一个方向后转到另一个方向。
  • C-SCAN 电梯算法，只在从头到尾时访问，访问到尾后迅速回到头部继续从头到尾访问。
  • S-LOOK 电梯算法，在SCAN的基础上不会到头尾才转换方向。
  • C-LOOK 电梯算法，在C-SCAN的基础上不会到头尾才转换方向。
寻道时间
  • Transfer rate is rate at which data flow between drive and computer
    Positioning time (random-access time) is time to move disk arm to desired cylinder (seek time) and time for desired sector to rotate under the disk head (rotational latency)
    Head crash results from disk head making contact with the disk surface
  • Host controller in computer uses bus to talk to disk controller built into drive or
    storage array
Disk
  • The size of the logical block is usually 512 bytes
  • Sector 0 is the first sector of the first track on the outermost cylinder
  • Host-attached storage accessed through I/O ports talking to I/O busses
    I/O bus like IDE
RAID 冗余廉价磁盘阵列

RAID是一种把多块独立的硬盘（物理硬盘）按不同的方式组合起来形成一个硬盘组（逻辑硬盘），从而提供比单个硬盘更高的存储性能和提供数据备份技术。

磁盘是随机半顺序存取，磁带是顺序存取。

Chapter 13 I/O System
SPOOLING
  • 用来保存设备输出的缓冲，这些设备如打印机不能接收交叉的数据流。
  • Printing：打印机虽然是独享设备，通过SPOOLing技术，可以将它改造为一台可供多个用户共享的设备。
缓冲 Buffering
  • 解决 IO 设备与 CPU 速度不匹配的问题。
  • IO 速度过慢
Direct Memory Access （DMA）
  • Used to avoid programmed I/O for large data movement 避免大量数据移动
  • Requires DMA controller
  • Bypasses CPU to transfer data directly between I/O device and memory
  • 利用总线，而不是CPU控制。
设备驱动程序
  • 完成设备的打开、关闭、读写等操作
  • 为I/O子系统提供了统一接口。
I/O 方式
  • Polling 轮询
    • Busy-wait cycle to wait for I/O from device
  • Interrupts中断

采用虚拟设备号访问 I/O 设备

10分填空 60分选择 30分综合 同步算法

Linux 内核题目少

可以带3张A4纸！！！

分类： Like A programmerOperating System

0 条评论

发表评论

Avatar placeholder

相关文章

Like A programmer

[ BASH ] 帮同事姐姐批量修改文件名后缀

同事有个需求要给100多个文件的后缀名前面加一个后缀（这算中缀么），手 阅读更多…

Like A programmer

Sublime 全局跳转失灵之后

最近work地很不顺手，我的sublime3不知道从哪一天开始只在打开 阅读更多…

Like A programmer

[Web] 试试Parcel

https://parceljs.org/getting-starte 阅读更多…