操作系统

Linux结构

进程调度子系统

功能：

• 决定CPU的归属
• 处理中断，将其发送给合适的子系统
• 发送信号给用户进程
• 管理定时器
• 支持模块动态装入

内存管理子系统

功能：

• 扩大地址空间
• 进程保护
• 内存映射
• 实现虚存

一、操作系统引论

单道批处理系统

特性：自动性、顺序性、单道性

优点：减少人工操作，解决了作业的自动接续。

缺点：

• 资源利用率不高：CPU，内存
• 平均周转时间长
• 没有交互能力

多道批处理系统

同时驻留多个作业

优点：

• 提高CPU利用率
• 提高内存和I/O设备的利用率
• 提高了系统吞吐量

缺点：

• 资源利用率高
• 系统吞吐量大
• 平均周转时间长
• 无交互能力

分时系统

指一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户共享主机中的资源，各个用户都可通过自己的终端以交互方式使用计算机

类型：

• 单道分时系统
• 具有前、后台的分时系统
• 多道分时系统

特征：

• 多路性
• 独立性
• 及时性
• 交互性

典型系统：MIT、UNIX、Linux

实时操作系统

及时处理

实时任务类型：

按程序运行是否呈现周期性：

• 周期性
• 非周期性

根据对截止时间的要求来划分：

• 硬实时任务
• 软实时任务

实时 vs 分时

• 多路性：相同
• 独立性：相同
• 及时性：实时系统要求更高
• 交互性：分时系统要求更高
• 可靠性：实时系统要求更高

微机操作系统

单用户单任务操作系统：CP/M，MS-DOS

单用户多任务操作系统：Windows（不会Server版）

多用户多任务操作系统：Unix、Solaris、Linux

操作系统

基本特征

• 并发性
• 共享性：互斥共享、同时访问
• 虚拟性：时分复用：虚拟处理机技术/虚拟设备技术、空分复用：虚拟存储
• 异步性

并发和共享是最基本的特征

并发：指两个或多个事件在同一时间间隔内发生

并行：指两个或多个事件在同一时刻发生

功能

1. 处理机管理
2. 存储器管理
3. 设备管理
4. 文件管理
5. 方便用户使用的用户接口

传统操作系统结构

1、整体式操作系统：Linux

2、模块化操作系统：

提升了易维护性、开发效率、适应性；没有提升运行效率

3、分层式操作系统

易于验证新开发功能的正确性

微内核操作系统结构

优点：

• 提高了可扩展性
• 增强了可靠性
• 可移植性强
• 提供了对分布式系统的支持
• 融入了面向对象技术

问题：

• 性能代价

做题

1、在OS中为实现多道程序设计需要有更大的内存

2、推动微机OS发展的主要动力是计算机硬件的不断更新换代

3、在多道批处理系统中，为了充分利用各种资源，系统总是优先选择计算型和I/O型均衡的的多个作业投入运行

4、在分时系统中，为使多个用户能够同时与系统交互，最关键的问题是能在一较短的时间内，使所有用户程序都得到运行

5、分时系统和实时系统都具有交互性，实时系统的交互性允许用户访问专用服务程序，分时系统的交互性运行用户请求系统提供多方面的服务

6、中断处理模块是必须包含在操作系统内核中的模块

二、进程描述与控制

1、前趋图

描述进程之间执行的前后关系

顺序执行：顺序性、封闭性、可再现性

并发执行：间断性、失去封闭性、不可再现性

2、进程

引入原因

为了使程序在多道程序环境下能并发执行，并对并发执行的程序加以控制和描述，在操作系统中引入了进程概念

结构

进程映像：程序段、数据段和PCB

PCB（Process Controll Block）:进程控制块，用与描述进程的基本情况和活动过程，进而控制和管理进程

创建进程就是创建进程实体中的PCB

撤销进程就是撤销进程实体中的PCB

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

特点

• 动态性：最基本特征
• 并发性
• 独立性
• 异步性

操作系统的并发性和异步性特征来自进程的特征

基本状态

就绪状态、执行状态、堵塞状态

在单CPU的主机上，有N个进程

最大就绪进程数为N-1

最大运行进程数为1

最大阻塞进程数为N

创建和终止状态

创建状态：未完成创建的进程不能被调度

终止状态：

• 1、等待进程终止的善后处理；2、撤销进程的PCB
• 避免再被调度

挂起状态

使执行的进程暂停执行，静止下来，使就绪状态的进程暂不接受调度

原因：

• 终端用户的请求
• 父进程的请求
• 负荷调节的需要。当实时系统中的工作负荷较重，把一些不重要的进程挂起，以保证系统能正常运行。
• 操作系统的需要。操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账。

数据结构

1、用于管理控制的数据结构

四大表：内存表、设备表、文件表、进程表

2、PCB作用

提供进程管理和调度所需的信息，实现与其他进程的同步和通信

PCB是进程存在的唯一标志

PCB中的信息

（1）进程标识符

• 内部标识符：唯一，系统使用
• 外部标识符：创建者提供，用户使用

（2）处理机状态

• 通用寄存器
• 指令计数器
• 程序状态字PSW
• 用户栈指针

中断和进程切换所需要保护的内容

（3）进程调度信息

• 进程状态
• 进程优先级
• 进程调度所需要的其他信息：如进程已等待CPU的时间总和
• 事件

（4）进程控制信息

• 程序和数据的地址
• 进程同步和通信机制
• 资源清单
• 链接指针

PCB的组织方式

• 线性
• 链接
• 索引

3、进程控制

操作系统内核

处理机的执行态

• 系统态/管态/内核态
• 用户态/目态

内核功能：

（1）支撑功能

• 中断处理
• 时钟管理
• 原语操作

（2）资源管理操作

• 进程管理
• 存储器管理
• 设备管理

原语：由若干条指令组成，用于完成一定功能的一个过程，并在执行中不可分割

操作系统内核的功能大都通过执行各种原语实现

原子操作：在一个操作中的所有动作，要么全做，要么全不做

在单机系统中采用屏蔽中断的方式来保证操作的原子性

进程的创建

进程的层次结构

• 创建形成的父子进程关系
• 子进程继承父进程的资源
• 父进程终止会导致子进程终止
• PCB中记录家族关系
• Windows中没有进程层次关系

进程图

创建进程的事件

1. 用户登录
2. 作业调度
3. 提供服务
4. 应用请求

fork()：复制父进程全部资源

clone()：有选择的复制父进程资源

Vfork()：创建线程。复制除task_struct和系统空间堆栈外的所有资源

fork()函数

失败返回负值

成功：

• 父进程返回创建子进程的ID
• 子进程返回0

进程终止

引起进程终止的三类事件

1. 正常结束

   return：结束函数的执行

   exit：先进行清除工作，再进入内核

   _exit：立刻进入内核

2. 异常结束

   调用abort函数

   收到某个信号使程序终止

3. 外界干预

进程阻塞和唤醒

引起阻塞和唤醒的事件

1. 请求系统服务而得不到满足
2. 启动某种操作而需同步时
3. 新数据尚未到达
4. 无新工作可做

唤醒原语流程：

首先把被阻塞的进程从该等待事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪

然后再将该PCB插入到就绪队列中

进程挂起与激活

挂起：

• 活动就绪->静止就绪
• 活动阻塞->静止阻塞

激活：

• 静止就绪->活动就绪
• 静止阻塞->活动阻塞

进程切换

进程调度：把处理机分配给不同的进程占用执行

调度程序：实现分配处理机的程序

进程的上下文：进程切换时要保护执行现场

4、进程同步

• 硬件同步机制
• 信号量机制
• 管程机制
• 经典同步问题

资源的共享和协作导致相关进程间形成制约

例一：银行储蓄问题

例二：生产者消费者问题

void producer() {
   while(1){
     产生数据到临时变量nextp；
      …….
      while (counter == n ) ;
      buffer[in] = nextp;
      in=(in+1)%n;
      counter++;
     }
};

void consumer() {
    while(1)  {
        while (counter ==  0);
        nextc = buffer[out];
         out = (out +1) %n;
         counter--;
          消费取出的数据；
      }；
}

问题 ：没有对counter进行并发访问控制

临界区

各个进程要保证互斥的进入自己的临界区，从而实现临界资源的访问

同步机制的准则（重要）

1. 空闲让进：如果临界区空闲，则只要有进程申请就立即让其进入，以有效利用资源
2. 忙则等待：每次仅允许一个进程处于临界区，保证对临界资源的“互斥”访问
3. 有限等待：进程只能在临界区内逗留有限时间，不得让其他进程在临界区外陷入“死等”
4. 让权等待：进程不能进入临界区时，应立即释放处理机，以免陷入“忙等状态

硬件同步机制

软件方法始终不能解决“忙等”现象，降低系统效率，同时很难控制多个进程的互斥

1、关中断

• 影响效率
• 不能保证互斥同步

2、Test-and-Set指令和Swap指令

本质：确保对锁的检测和关锁操作的原子性

Test-and-Set

boolean TS(boolean *lock){
    boolean old = *lock;
    lock = TRUE;
    return old;
}
do{
    ...
    while TS(&lock);
    临界区
    lock = FALSE;
    其他区域
}while(TRUE)

Swap

do{
    boolean key=TRUE;
    do{
        swap(&lock,&key);
    }while(key!=FALSE);
    临界区
    lock=FALSE;
    其他区域
}while(TRUE)

本质：lock是真死循环，lock是否跳出循环，最后都要置lock为否

缺点：

• 忙等
• 饥饿现象
• 死锁

信号量机制

整型信号量

P操作/Wait(s):while s<=0; s=s-1

V操作/Signal(s):s=s+1

未遵循让权等待原则

记录型信号量

typedef struct{
    int value;
    struct process_controll_block *list;
}semaphore;

wait(semaphore *S){
    S->vlaue--;
    if(S->value<0) block(S->list);
}
signal(semaphore *S){
    S->value ++;
    if(S->value <= 0) wakeup(S->list);
}

s.value初值：表示系统中某类资源的数目

s.value<0：表示信号量链表中已阻塞进程的数目

• 资源信号量：用于申请或归还资源，可以初始化为大于1的正整数，表示系统中某类资源的可用个数
• 互斥信号量：用于申请或释放资源的使用权，常初始化为1

资源信号量和互斥信号量使用相同的底层机制

AND型信号量

要么全分配，要么一个也不分配

Swait(s1,s2...sn)
{
    while(TRUE)
    {
        if(Si>=1 && .. && Sn>=1)
        {
            for(i=1;i<=n;i++) Si--;
            break;
        }
        else{
            ...
        }
    }
}
Ssignal(s1,s2,...sn)
{
    while(TRUE){
        for(i=1;i<=n;i++){
            Si++;
            ...
        }
    }
}

信号集量

为提高效率而对AND信号的补充（略）

信号量应用

• 实现进程互斥
• 实现前趋关系

管程机制

一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据

特点：

1. 局部数据变量只能被管程的过程访问，任何外部过程都不能访问
2. 一个进程通过调用管程的一个过程进入管程
3. 在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被挂起，以等待管程变成可用的。 从而实现进程互斥。

同步工具：条件变量

管程通过使用条件变量提供对同步的支持，这些条件变量包含在管程中，并且只有在管程中才能被访问 ，每个条件维护一个链表

①x.wait：调用进程的执行在条件x上挂起，插入x等待队列，并释放管程给另一个进程使用。

②x.signal：恢复在x条件挂起的进程的执行。如果有多个这样的进程，选择其中一个；如果没有这样的进程，什么也不做。

5、经典进程同步问题

生产者-消费者问题

（1）记录型信号量

int in=0,out=0;
item buffer[n];
semaphore mutex=1,empty=n,full=0;
void producer(){
    do{
        producer an item nextp;
        ...
        wait(empty); //empty缓冲区为空的数量
        wait(mutex);
        buffer[in] = nextp;
        in=(in+1)%n;
        signal(mutex);
        signal(full);
    }while(True);
}

void consumer(){
    do{
        wait(full);//full缓冲区为满的数量
        wait(mutex);
        nextc = buffer[out];
        out = (out+1)%n;
        signal(mutex);
        signal(empty);
        consumer the item in nextc;
        ...
    }while(True);
}

1. 进程应该先申请资源信号量，再申请互斥信号量
2. 对任何信号量的wait与signal操作必须配对。
3. 对同一个资源信号量的wait与signal可以不在同一个进程中

（2）AND信号量

int in=0,out=0;
item buffer[n];
semaphore mutex=1,empty=n,full=0;
void producer(){
    do{
        producer an item nextp;
        ...
        Swait(empty,mutex);
        buffer[in] = nextp;
        in=(in+1)%n;
        Ssignal(mutex,full);
    }while(True);
}

void consumer(){
    do{
        Swait(full,mutex);
        nextc = buffer[out];
        out = (out+1)%n;
        Ssignal(mutex,empty);
        consumer the item in nextc;
        ...
    }while(True);
}

（3）管程

Procedure entry put(item)
	begin
	  if count ≥n then notfull.wait;
	    buffer(in):=nextp;
	    in:=(in+1)mod n
	    count:=count+1;
	    if notempty.queue then notempty.signal;
	end
Procedure entry get(item)
	begin
	  if count ≤ 0 then notempty.wait;
	    nextc:=buffer(out);
	    out:=(out+1)mod n
	    count:=count-1;
	    if notfull.queue then notfull.signal;
	end
Begin in:=out:=0; count:=0 end

哲学家进餐问题

记录型信号量

do{
    wait(chopstick[i]);
    wait(chopstick[(i+1) %5]);
    …
   //eat
    …
   signal(chopstick[i]);
   signal(chopstick[(i+1) % 5]);
    …
   //think;
    …
} while (TRUE)

Q：死锁

A：仅当哲学家的左右两只筷子同时可以时才允许他拿起筷子

AND信号量

Var chopstick: array[0, …, 4] of semaphore:=(1,1,1,1,1);
processi
Repeat
   think;
   Sswait(chopstick[(i+1)mod 5],chopstick[i]);
    eat
    Ssignal(chopstick[(i+1)mod 5],chopstick[i]);
Until false

读写者问题

semphore rmutex = 1,wmutex = 1;
nt readcount = 0;
void reader(){
    do{
        wait(rmutex);
        if(readcount == 0) //如果有人在读则说明绝对不在写，因此只有没人在读时需要判断是否在写
            wait(wmutex); //保证第一个读进程来，写进程就不能进行
        readcount++;
        signal(rmutex);
        ...
        perform read operation
        ...
        wait(rmutex);
        if(readcount == 0)
        {
            signal(wmutex);
        }
        signal(rmutex);
    }while(TRUE);
}
void writer()
{
    do{
        wait(wmutex);
        perform write operation;
        signal(wmutex);
    }while(TRUE)
}

6、进程的通信

7、线程的基本概念

线程是资源调度和分派的基本单位

• 进程的终止或挂起会导致进程中的所有线程的终止或线程
• 进程比线程有更好的独立性
• 进程中的所有线程共享该进程的状态和资源
• 线程阻塞不一定引起进程阻塞（系统调用进入核心态时，若线程阻塞则其所在进程也会被阻塞）
• 同一进程中的线程切换不会引起进程切换，在不同进程中的线程切换会引起进程切换

线程状态变化的4种基本操作：

1. 派生
2. 阻塞
3. 解除阻塞
4. 结束

线程控制块：

线程标识符、一组寄存器、线程运行状态、优先级、专有存储区、用户栈、信号屏蔽

线程运行状态不是线程的上下文

8、做题

1、某进程所要求的一次打印输出结束，该进程被唤醒，其进程的状态将从阻塞到就绪

2、在批处理系统中，导致进程创建的典型事件是作业调度

3、由系统专门为运行中的应用进程创建新进程的事件是提供服务

4、wait,signal操作可以解决一切互斥问题

三、处理机调度和死锁

1、一些基本概念

层次	别名	对象	功能	频度	实现者	应用范围
高级	作业调度、长程调度、接纳调度	作业	决定外存作业上处于后备队列中的哪几个作业调入内存，创建进程，分配资源，插入就绪队列	最低，分钟级	作业管理程序	批处理系统
中级	内存调度	挂起的进程	把外存上那些已经具备运行条件的就绪进程重新载入内存（从静止就绪到活动就绪），将暂时不能运行的进程调至外存等待	中等	内存管理中的对换进程	具有对换功能的操作系统
低级	进程调度、短程调度	就绪进程/内核进程	决定就绪队列中的哪个进程应获得处理机，并将处理机分配给选中的进程	最频繁，毫秒级	分派程序	都有

CPU利用率 = CPU的有效工作时间/（CPU有效工作时间+ CPU空闲等待时间）

周转时间：接纳等待、执行等待、执行时间、I/O时间

面向用户的准则：平均周转时间

带权周转时间：作业的周转时间T与系统为它服务的时间（执行加IO）之比 （必定>1）

吞吐量：单位时间内系统完成的作业数

响应时间：输入时间、处理时间、显示时间

响应时间快：分时系统的重要准则

2、作业与作业调度

作业管理系统用于管理和控制作业运行的数据结构

先来先服务算法FCFS

first come fist serve

每次调度从就绪队列中选择一个最先进入该队列的进程

短作业优先算法SJF

shortest job first

从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。

优先级调度算法PSA

Priority-scheduling algorithm

外部赋予作业（进程）相应的优先级，例如以作业的紧迫程度作为优先级

高响应比优先调度算法HRRN

Highest Response Ratio Next

赋予作业动态优先级，优先级随作业等待时间延长而增加，从而使长作业的优先级在等待期间不断增加。

优先权=（等待时间+要求服务时间）/要求服务时间

在作业完成时以及新作业到达时计算响应比

不用于进程

3、进程调度

抢占式

非抢占式

轮转调度算法（抢占式）

• 每个进程仅运行一个时间片即被强占CPU
• 原理：FCFS策略+时钟中断+时间片原则
• 切换时机：时间片内进程结束，进程结束事件激活进程调度，新进程可运行一个时间片；时间片用完，时钟中断激活调度，旧进程到就绪队列尾，队头进程投入运行一个时间片

时间片大小默认为100ms

优先级调度算法

静态优先权

动态优先权：响应比Rp = （等待时间+服务时间）/服务时间

多队列调度算法

• 设置多个就绪队列，并为各个队列赋予不同的优先级。
• 优先级愈高的队列的进程的执行时间片就愈小。
• 新进程首先进入最高优先级的队列。每个队列采用FCFS算法。队列中的进程运行一个时间片后未结束则降级排到下一个队列的末尾。最低优先权队列中的进程则按RR方式运行。
• 按队列优先级调度。只有比队列的优先级高的队列均空时，才运行该队列中的进程。

未执行完时间片的进程被抢占后应不降级，到队列末尾

基于公平原则的调度算法

1. 保证调度算法：如N个进程平均分配时间
2. 公平分享调度算法：按照用户数量平均分配时间

4、实时系统与实时任务调度

最早截止时间优先算法（EDF）

Earliest Deadline First

具有最早截止时间的任务排在队列的最前面

最低松弛度优先算法（LLF）

Least Laxity First

松弛度=完成截止时间-剩余运行时间-当前时间

松弛度最小的任务排在队列最前面

优先级倒置

存在高中低三个优先级的进程，高和低共享同一个临界资源，低优先级进程先进入临界区，阻止高优先级进程进入临界区，中优先级进程抢占低优先级进程的CPU，使得低优先级进程无法从临界区退出，从而间接阻止更高优先级进程运行。

解决办法：优先级继承

5、死锁

死锁：多个进程在运行过程中因争夺资源而造成的一种僵局

如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的

产生死锁的原因

1. 竞争资源
2. 进程间推进顺序非法

产生死锁的四个必要条件

1. 互斥条件：指进程对所分配到的资源进行排它性使用 。
2. 请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求 。
3. 不剥夺条件：进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
4. 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链 。（充要条件）

解决死锁

1. 预防死锁：预防2,3,4条件
2. 避免死锁
3. 检测死锁
4. 解除死锁

请求保持：资源的预分配

不剥夺条件：死锁时把保持的资源释放

循环等待：资源有序分配

6、避免死锁

安全状态：没有死锁的状态

非安全状态：可能有死锁的状态

银行家算法

当一个进程申请使用资源的时候，银行家算法通过先 试探 分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待。

避免死锁的限制条件：

• 预先必须声明每个进程需要的资源总量
• 进程之间相互独立，其执行顺序取决于系统安全，而非进程间的同步要求
• 系统必须提供固定数量的资源供进程使用

n个进程共享m个同种资源，若每个进程都需要该类资源，而且各进程对该类资源的最大需求量之和小于m+n，说明该系统不会因竞争该类资源而死锁

死锁检测算法

资源分配图：

若能消去资源分配图中所有结点的连接边，使全部结点都成为孤立结点，则称该图是可完全简化图；若不能使该图完全简化，则称该图是不可完全化简图。

死锁解除

（1）剥夺资源

（2）撤销进程（最简单常用）

7、做题

1、截止时间的保证是选择实时调度算法的重要准则，响应时间快是选择分时系统中进程调度算法的重要准则

2、FCFS只能采用非抢占式调度，时间片轮转只能采用抢占调度

3、为了实现人机交互采用时间片轮转法，为了兼顾短作业和长时间等待作业，采用高响应比优先，为了使作业的平均周转时间最短，应采用短作业优先算法

4、最容易引起进程长期等待的是抢占式静态优先权优先算法

5、有新进程进入就绪队列不是引起操作系统选择新进程的直接原因

6、产生死锁的基本原因是系统资源不足和进程推进顺序不当

7、在多道程序的环境中，不会因竞争可被抢占的资源而产生死锁

四、存储器管理

1、存储系统结构

• 寄存器、高速缓存、主存储器、磁盘缓存：属于操作系统存储管理的管辖范畴，掉电后存储信息不再存在
• 磁盘、可移动存储介质：设备管理和文件系统的管辖范畴，存储信息长期保存

高速缓存能有效提升指令访问内存的原因：程序执行的局部性原理

参与指令执行的存储器：寄存器、高速缓存、内存

基本概念

1. 逻辑地址（相对地址、虚地址）
2. 物理地址（绝对地址、实地址）
3. 名空间： 一个用高级语言编制的源程序，我们说它存在于由程序员建立的符号名字空间（简称名空间）
4. 地址空间：程序用来访问信息所用地址单元的集合，是逻辑（相对）地址的集合，由编译程序生成。
5. 存储空间：主存中物理单元的集合。这些单元的编号称物理地址或绝对地址。存储空间的大小是由主存的实际容量决定的。

• 一个编译好的目标程序存在于它自己的地址空间中，当要它在计算机上运行时，才把它装入存储空间。
• 一个作业在编译、装入前后存在于不同的空间。

编辑—编译—链接—装入—运行

2、程序的装入和链接

程序的装入

绝对装入方式

编译时即产生实际存储地址的目标代码，程序中的逻辑地址与实际内存地址完全相同

通常采用符号地址，编译或汇编时再将符号地址转换为绝对地址（转换在链接时候进行）

缺点：只能将目标模块装入到内存中实现指定的位置，这只适用于单道程序环境

可重定位装入方式

装入内存时，相对地址需要做出修改得到正确的物理地址

静态重定位：物理地址=相对地址+内存中的起始地址，地址变换在装入内存时一次完成，且以后不能移动

动态运行时的装入方式

动态重定位：装入程序将装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序执行时进行。即在硬件地址变换机构的支持下，随着对每条指令或数据的访问自动进行地址变换

利用重定位寄存器实现：值由进程调度根据作业分配到的存储空间起始地址来设定的，将有效地址与重定位寄存器中的内容相加后得到的值作为访问主存的地址

程序的链接

将经过编译后所得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块。

根据链接时间的不同，可把链接分成三种

静态链接

程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块（又称执行模块），以后不再拆开。

解决问题：

• 修改相对地址
• 变换外部调用符号

装入时动态链接

在装入内存时再链接需要的其他模块

优点：

• 便于对目标模块进行修改和更新
• 实现了对目标模块共享

运行时动态链接

在执行过程中，若发现一个被调用的模块尚未装入内存时，由操作系统去找到该模块，将它装入内存，并链接到调用模块上

优点：

凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。

当程序经过编译或者汇编后，形成了一种由机器指令组成的集合，被称为目标程序

若调用指令LOAD A Data，经动态重新定位后，其对应指令代码保持不变

3、连续分配存储管理方式

单一连续分配

内存分为系统区和用户区，系统区仅提供给OS使用，用户区仅装有一道用户程序，整个内存的用户空间由该程序独占

只适用于单用户、单任务

固定分区

有n个分区，则可同时装入n个作业/任务。

1、分区大小

• 相等：缺乏灵活性
• 不相等：利用率高

2、内存分配

将分区按大小排序，并将其地址、分配标识作记录

3、特点

简单，有碎片（内零头）

内零头：分配给进程没用到的空间

外零头：不能分配给任何一个进程的空间

动态分区分配

数据结构

1. 空闲分区表
2. 空闲分区链

顺序分配算法

1、首次适应算法（First Fit / FF）

• 要求：分区按地址递增排序

• 方法：每次链首开始，直到找到满足大小的空闲分区，分割该分区

• 特点：有外零头，低址内存使用频繁，查找慢。高地址区保留大分区

2、循环首次适应算法（next fit / NF）

• 方法：从上次找到的空闲分区的下一个开始查找，直到找到满足大小的空闲分区，分割该分区。
• 特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区

3、最佳适应算法（best fit / BF）

• 要求：分区按大小递增排序；分区释放时需插入到适当位置。
• 方法：从小分区开始，找大小满足要求，但空余最小的分区。
• 特点：单次分配看似最优，但存在许多难以利用的碎片。总体未必最优。

4、最坏适应算法 （worst fit / WF）

• 要求：分区按大小递减排序

• 方法：总是选择最大的分区来分割分配。

• 特点：缺乏大的空闲分区。对中小作业有利。查找效率高。

分区合并

（1）上邻空闲区：合并，改大小

（2）下邻空闲区：合并，改大小，首址。

（3）上、下邻空闲区：合并，改大小。

（4）不邻接，则建立一新表项。

基于索引搜索的动态分区分配算法

1、快速适应算法（分类搜索法）（quick fit）

对于每一类相同容量的空闲分区单独设立一个空闲分区链表；设置管理索引表，每个表项对应一种空闲分区类型，并记录该类空闲分区链表表头指针。

优点：

• 查找效率高
• 不会对任何分区产生分割，能保留大的分区，也不会产生碎片

缺点：

• 分区归还主存时算法复杂，系统开销较大
• 内零头

2、伙伴系统（buddy system）

在伙伴系统中，可用内存块的大小为2k(1≤k≤m)

对空闲区按照大小分类，相同大小的分区链接为一个双向空闲链表；最多可形成k（0 ≤k≤m）个链表。

$$
buddy_{k}(x)=\left{\begin{matrix}x+2^{k}(若xMOD~~~2^{k+1}=0)
\x-2^{k}(若xMOD~~~2^{k+1}=2^{k})
\end{matrix}\right.
$$

• 优点：分配和回收内存速度快，且不会产生很多小碎片
• 缺点：内存利用率不高，分配的内存大小为2的幂

3、哈希算法

按照分区链表的大小建立哈希数组，从而快速找到需要大小的空闲分区链表。

可重定位分区分配

引入原因：连续式分配中，总量大于作业大小的多个小分区不能容纳作业。

紧凑

• 通过作业移动将原来分散的小分区拼接成一个大分区
• 作业的移动需重定位。是动态（因作业已经装入）

引入重定位寄存器

当程序执行时，由相对地址与重定位寄存器中的起始地址相加得到物理地址访问内存

4、对换

• 以整个进程为单位：整体对换/进程对换
• 以“页”和“段”为单位：页面对换/分段对换/部分兑换

对换空间管理

外存：

• 文件区：为提高存储空间利用率，采用离散分配方式
• 对换区：为提高进程换入换出的速度，采用连续分配方式

分配算法、对换空间的分配与回收与内存动态分区雷同。

进程换出

进程选择：

• 先阻塞状态的，后选择就绪的挂起状态优先被换出，但不是一定被换出）
• 尽量选择优先级低的
• 考虑内存驻留时间长短

换出进程：

• 只能换出非共享的程序和数据段，共享段有其他进程使用时不能换出
• 先申请对换空间，然后启动磁盘将要换出的内容写出，最后才回收内存空间，并修改进程控制块和内存分配表等数据结构

进程换入

• 系统定时地查看所有进程的状态，从中找出就绪状态但已换出的进程；
• 将其中换出时间最久的进程作为换入进程；
• 有能满足进程需要的内存时可将之换入。

进程被换出时，非共享的程序段和数据段将被换出到外存

5、分页存储方式

离散分配：程序在内存中不一定连续存放

引入原因

• 连续分配会产生内外零头
• 为解决零头问题要进行紧凑等高开销活动

根据基本单位不同：

• 分页存储管理
• 分段存储管理
• 段页式存储管理

基本概念

• 页面/页 ： 将一个进程的逻辑地址空间分为若干大小相等的片
• （物理）块/页框 ： 将内存空间分成与页面相同大小的若干个存储块
• 为进程分配内存时，以块为单位将进程中的若干个页装入到多个可以不相邻接的物理块中
• 最后一页不满一块会产生“内零头”（页内碎片）

页面大小

• 页面小：页表长，页面换入换出效率低
• 页面大：页内碎片增大
• 应为2的幂，通常为512B~8KB

空间组织

若逻辑地址空间地址为A，页面大小为L，则页号P和页内地址d：
$$
P=INT[\frac{A}{L}]
\d=[A]MOD~L
$$

数据结构

• 页表：每个进程对应一个页表，描述该进程的各页面在内存中的物理块号（还可能有存取控制字段）
• 作业表：整个系统一张，记录作业的页表情况，包含进程号、页表长度、页表始址等信息
• 空闲块表：整个系统一张，记录主存当前空闲块

全部页表集中存放在主存的系统专用区中，只有系统有权访问页表，保证安全。

地址变换

硬件机制：实现逻辑地址到物理地址的转换

页表寄存器PTR：存放当前运行的进程的页表在内存中的起始地址，和此进程的页表长度

执行检索前比较页号与页表长度，若页号大于页表长度，则表示本次所访问的地址已超越进程的地址空间，即产生越界中断，未出现则将页表始址与页号和页表项长度的乘积相加，得到物理块号

快表

分页系统：处理机每次存取指令或数据至少需要访问两次物理内存：

第一次访问页表，第二次存取指令或数据

为了提高地址变换速度，为进程页表设置一个专用的高速缓冲存储器，称为快表、TLB(Translation Lookaside Buffer)或联想存储器(Associative Memory)

工作原理：专门保存当前进程最近访问过的一组页表项（类似于高速缓存），根据逻辑地址中的页号，查找快表中是否存在对应的页表项

• 若存在，称为命中(hit)，取出页框号，加上页内偏移量，计算出物理地址
• 若不存在，称为命中失败，则再查找页表，找到逻辑地址中指定页号对应的页框号。同时，更新快表，将该表项插入快表中，并计算物理地址。

内存有效访问时间EAT(Effective Access Time)：

• 无快表：EAT = 2t
• 有快表：EAT=a * λ + ( t + λ )(1-a) + t = 2t + λ – t x a

其中，t为一次内存访问需要时间，λ 为查找快表所需时间，a为命中率

两级和多级页表

大逻辑地址空间，页表非常大，需要占用相当大的内存空间

1. 采用离散分配方式来解决难以找到一块连续的大内存空间的问题（即引入两级页表）
2. 只将当前需要的部分页表项调入内存， 其余的页表项仍驻留在磁盘上，需要时再调入

对于4GB的进程，若采用二级页表，则对应的二级页表结构如图：

增设外层页表寄存器，用于存放外层页表的始址

利用逻辑地址中的外层页号，作为外层页表的索引，从中找到指定页表分页的始址，再利用指定页表分页的索引，找到指定的页表项，即该页在内存的物理块号

对于64位的机器就需采用多级页表

反置页表

现代计算机系统中通常允许一个进程的逻辑地址空间非常大

反置页表为每一个物理块设置一个页表项，并将它们按物理块的编号排序，其中的内容则是页号和其所属进程的标志符。

地址变换：根据进程标志符和页号检索反置页表，如果找到则页表项中的序号就是该页所在的物理块号。如果检索未找到则失败或者必须请求调页。

虽然反置页表占用内存空间可以更小，但是仍然需要为每个进程保存完整的页表，以便实现请求调页。这样无法真正节约内存。

反置页表不适用于大物理内存

评价

• 彻底消除了外零头，仅存在很少的内零头，提高了内存利用率
• 分页操作由系统自动进行，一个页面不能实现某种逻辑功能。用户看到的逻辑地址是一维的，无法调试执行其中的某个子程序或子函数。
• 采用分页技术不易于实现存储共享，也不便于程序的动态链接。

6、分段存储管理方式

引入原因

• 方便编程
• 信息共享
• 信息保护
• 动态增长
• 动态链接

基本原理

作业地址空间按逻辑信息的完整性被划分为若干个段，每段有段名/段号，从0开始编址，段内的地址空间是连续的

地址空间的访问：段名+段内地址

分段管理

实现分段管理的关键：保证分段（二维）地址空间中的一个作业在线性（一维）的存储空间中正常运行

建立段映射表（段表）—每个段在表中占有一个表项，记录了该段在内存中的起始地址（基址）和段的长度

作用：实现从逻辑段到物理内存区的映射

地址变换

1. 根据段表寄存器的内容找到该作业的段表地址
2. 利用有效地址中的段号作为检索段表的索引，得到该段在主存的起始地址
3. 将段的主存起始地址和位移量W相加，即得访问主存的物理地址

评价

优点：

• 没有内碎片，外碎片可以通过内存紧凑来消除
• 便于改变进程占用空间大小

缺点：

• 进程全部装入内存

信息共享

分页系统中：

对于数据页面，实现起来比较简单。因为这个数据页面可以安排在诸作业地址空间中的任何一页面上。

对于代码页面，它必须把共享的代码安排到所有共享它的作业地址空间中相同页号的页面中。即共享代码所在的地址空间必须重叠

之所以有这种要求，是因为一个作业在运行前必须链接好，而链接后，一个例程的所占页号就确定了。如果其它作业要共享该例程，则必须使它具有相同的页号，才能正确运行。

分段系统中：

分段的共享是通过两个作业段表的相应表目都指向COS过程的同一物理副本来实现的。

说明：段号是在动态链接过程中分配的，而且，系统不可能事先知道某个过程将为哪些作业所调用，因此，一个公共过程不一定也无需赋相同的段号

7、段页式存储管理方式

先将用户程序分段，每段内再划分成若干页，每段有段名（段号），每段内部的页有一连续的页号。

地址空间由段号S、段内页号P和页内相对地址（位移量）W构成

• 首先，从段表寄存器从获得进程段表的起始地址，根据该地址，查找进程的段表。
• 然后，根据逻辑地址指定的段号检索段表，找到对应段的页表起始地址。
• 再根据逻辑地址中指定的页号检索该页表，找到对应页所在的物理块号。
• 最后，用物理块号加上逻辑地址中指定的页内偏移量，形成物理地址。

每访问一次数据，需访问三次内存：

1. 访问内存中的段表
2. 访问内存中的页表
3. 访问相应数据

可以设置快表，表项包括段号，页号，物理块号

引入分段存储管理的原因不包括提升内存利用率

8、分页分段区别

（1）

页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。

段则是信息的逻辑单位，它含有一组意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。

（2）

页的大小固定且由系统决定，因而在系统中只能有一种大小的页面

段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。

（3）

分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；

分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

段页式的虚拟空间地址也是二维的

（4）

分页不利于实现程序的共享和保护，分段利于实现

9、连续分配vs离散分配

技术性能	连续分配	离散分配
大批量数据的存取速度	较快	较慢
机制的复杂性	较简单	较复杂
内存碎片	较大	较小
实现虚拟技术	较难	较易
实现动态链接	较难	较易

五、虚拟存储器

1、概述

引入

常规存储管理方式的特征：

• “一次性”：要求将一个作业全部装入内存中才能运行
• “驻留性”：作业装入后一直驻留内存直到作业完成

一次性和驻留性严重降低内存利用率，减少系统吞吐量。

解决方法：

• 物理扩充
• 逻辑扩充
  • 覆盖：应用程序手动把需要的指令和数据保存在内存中
  • 对换：操作系统自动把暂时不能执行的程序保存到外存中
  • 虚拟存储

局部性原理

程序执行的局部性原理：程序的执行总是呈现局部性。即，在一个较短的时间段内，程序的执行仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域。

因此，只要保证进程执行所需的部分程序和数据驻留在内存，一段时间内进程都能顺利执行。

• 时间局限性：存在大量循环操作
• 空间局限性：访问地址集中在一定的范围内

虚拟存储器定义与特征

指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

• 逻辑容量由内存容量和外存容量之和所决定
• 运行速度接近于内存速度，而每位的成本却又接近于外存

特征

1. 多次性
2. 对换性
3. 虚拟性

实现方法

（1）请求分页存储管理方式

1. 硬件支持
   • 请求分页的页表机制上增加若干项，作为请求分页的数据结构
   • 缺页中断机构：当要访问的页面尚未调入内存时，便产生缺页中断，请求调页
   • 地址变换机构：虚地址到物理地址转换
2. 软件
   • 实现请求调页的软件
   • 实现页面置换的软件

（2）请求分段系统

• 请求分段的段表机制，这是在纯分段的段表机制基础上增加若干项而形成的
• 缺段中断机构
• 地址变换机构
• 相应软件支持

（3）段页式虚拟存储系统

2、请求分页存储管理方式

页表机制

建立在基本分页基础上

主要数据结构是页表

页表项：

• 状态位：也称存在位，标志该页是否驻留内存。
• 访问位：记录一段时间内该页被访问的情况，如一段时间内该页被访问的次数或者多长时间未被访问。
• 修改位：标记该页是否被修改过。注：为减少置换开销，通常选择未被修改过的页面置换。
• 外存地址：用于记录该页在外存上的存储地址。

缺页中断机构

在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。

地址转换时，检查页面的页表项中的存在位，如果为0，则产生一个缺页中断。

由于缺页中断的独特性，系统中需要提供硬件寄存器或其它机构，在出现页面故障时，保存部分完成的指令的状态。此外，还需要使用一条特殊的返回指令，确保在出现缺页中断处恢复该指令的处理。

地址变换机构

内存分配策略和分配算法

1. 最小物理块数：保证进程正常运行所需的最小物理块数
2. 物理块的分配策略
   • 固定分配局部置换
   • 可变分配全局置换
   • 可变分配局部置换

（1）固定分配局部置换

为每个进程分配一定数目的物理块，在整个运行期间都不再改变

困难：应为每个进程分配多少物理块难以确定

（2）可变分配全局置换（常用）

在采用这种策略时，先为系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲物理块队列。

当某进程发现缺页时，由系统从空闲物理块队列中，取出一个物理块分配给该进程，并将欲调入的（缺）页装入其中

可能引起抖动问题

（3）可变分配局部置换

为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程运行

在进程运行过程中统计进程的缺页率，如果缺页率高，则为其增加一定的内存页，否则适当减少其内存的页面数

困难：对进程的缺页情况统计需要额外开销

物理块分配算法

（1）平均分配算法

（2）按比例分配

按进程的页面数占页面数总和的比例进行分配

（3）考虑优先权的分配算法

将内存中可供分配的所有物理块分为两部分，一部分按比例分配，另一部分根据各进程的优先权，适当增加其相应份额后，分配给各进程

页面调入策略

1、何时调入

• 预调页：当进程创建时，预先为进程装入多个页面。 缺页中断时，系统为进程装入指定的页面以及与之相临的多个页面。
• 请求调页：仅当进程执行过程中，通过检查页表发现相应页面不在内存时，才装入该页面。

预调页总比请求调页高效

2、何处调入

外存分为两部分：

• 用于存放文件的文件区
• 用于存放对换页面的对换区

三种情况

• 系统拥有足够的对换区空间：进程运行前需将全部有关文件从文件区拷贝到对换区。
• 系统缺少足够的对换区空间：这时凡是不会被修改的文件，都直接从文件区调入； 而当换出这些页面时，若未被修改则直接丢弃，以后再调入时，仍从文件区调入。 但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。
• UNIX方式：由于与进程有关的文件都放在文件区，应从文件区调入。 凡是未运行过的页面，都应从文件区调入。 而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。 允许页面共享

页面调入过程

整个页面的调入过程对用户是透明的

3、页面置换算法

最佳置换算法（Optimal）

所选择的被淘汰页面，将是以后永不使用的，或是在最长(未来)时间内不再被访问的页面

理想化的算法，具有最好的性能，但很难实现

先进先出算法（FIFO)

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰

最近最久未使用置换算法（LRU）

选择最近最久未使用的页面予以淘汰（Least Recently Used）

该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

要求有硬件支持：寄存器/栈

寄存器实现：

为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器可表示为：

R=Rn-1Rn-2Rn-3···R2R1RO

当进程访问某物理块时，要将相应寄存器的最高位Rn-1位置成1。

系统每隔一定时间（例如100 ms）将寄存器右移一位。

如果我们把n位寄存器的数看作是一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。

此时应置换第3个页面

栈实现：

利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。

栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。

最少使用算法（LFU)算法

选择自某时刻开始以来，访问次数最少的页面予以淘汰

Clock置换算法（NRU）

简单Clock置换算法

循环地检查各页面的使用情况，又称为最近未使用算法NRU（Not Recently Used）

为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。

当某页被访问时，其访问位被置1。

置换程序从上次停止位置开始检查页面的访问位。

• 如果是0，就选择该页换出；
• 若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会。

改进Clock置换算法

在置换范围内首选在最近没有被使用过、在驻留内存期间没有被修改过的页面作为被置换页面

由访问位A和修改位M可以组合成下面四种类型的页面：

• 1类（A=0，M=0：表示该页最近既未彼访问，又未被修改，是最佳淘汰页。
• 2类（A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。
• 3类（A=1，M=0）：最近已被访问，但未被修改：该页有可能再被访问。
• 4类（A=1，M=1）：最近已被访问且被修改，该页可能再被访问。

执行过程：

（1）从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。

（2）如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M＝1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。

（3）如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页

其他算法

最少使用（LFU： Least Frequently Used）算法

页面缓冲算法（PBA: Page Buffering Algorithm)

访问内存有效时间

三种情况：

（1）被访问页在内存中，且对应页表项在快表中

​ EAT = λ + t

λ 是查找快表时间，t为访问实际物理内存需要的时间

(2) 被访问页在内存，但对应的页表项不在快表中：

查找快表，查找页表，修改快表，修改页表

EAT = 2 * (λ + t)

(3) 被访问页不在内存中 ： EAT = ε + 2 * (λ + t)

ε 为缺页中断的处理时间

再考虑快表命中率a，访问缺页率f

EAT=查找快表时间+a * 根据物理地址访存时间+（1-a）* [查找页表时间+f * (处理缺页时间+查找快表时间+根据物理地址访存时间)+（1-f）* (修改快表时间+根据物理地址访存时间)]

EAT = λ + at + (1-a)[ t + f * (ε + λ + t) + (1-f) * (λ + t) ]

若没有快表，λ和a都为0

EAT = t + f * (ε +t) + (1 – f) * t

缺页率

如果成功访问的次数为S，访问页面发生缺页的次数为F，则缺页率为：f = F / （S + F）

影响因素：

• 页面大小，页面越大越小；
• 进程所分配的物理页数，越多越少；
• 页面置换算法；
• 程序的访问局部性。

4、抖动与工作集

抖动：如果运行进程的大部分时间都用于页面的换入/换出，而几乎不能完成任何有效的工作，则称此进程处于抖动状态。抖动又称为颠簸。

分为：

• 局部抖动
• 全局抖动

产生原因：

• 进程分配的物理块太少
• 置换算法选择不当
• 全局置换使抖动传播

工作集略·

5、请求分段存储管理方式

段表机制

在请求分段式管理中所需的主要数据结构是段表，段表项有新的扩展。

缺段中断机构

地址变换机构

共享段的分配与回收

简单来说就是分配的时候count+1，回收的时候count-1

分段保护

（1）越界检查

（2）存取控制检查

（3）环保护机构

低编号的环具有高优先权。OS核心处于0环内；某些重要的实用程序和操作系统服务，占居中间环；而一般的应用程序在外环上。

基本原则：

• 一个程序可以访问驻留在相同环或较低特权环中的数据；
• 一个程序可以调用驻留在相同环或较高特权环中的服务。

6、做题

1、由于有了虚拟存储器，于是允许用户使用比内存更大的地址空间

2、状态位->程序访问；修改位->换出页面；访问位->置换算法;外存始址->调入页面

3、Belady现象：当分配到的内存块数增加时，缺页中断的次数有可能反而增加；->FIFO

4、凡未装入过内存的页都应从文件区调入，已运行过的页主要从对换区调入，有时也从页面缓冲区调入

5、虚拟存储器的功能由软硬件结合完成。在虚拟存储器系统中，采用高速缓冲存储器提高动态地址翻译的速度

6、Linux采用请求分页的存储管理方式，采用伙伴系统算法进行页框的分配和回收

六、输入输出系统

1、I/O系统简介

• 设备管理的对象：主要是I/O设备。

• 设备管理的基本任务：完成用户提出的I/O请求，提高I/O速率以及改善I/O设备的利用率。

• 设备管理的主要功能有：缓冲区管理、设备分配、设备处理、虚拟设备及实现设备独立性等。

• I/O系统基本功能：

  • 设备管理
  • 设备映射
  • 设备驱动
  • I/O缓冲区的管理

• 通用设备管理分层模型

设备通常通过数据信号线、状态信号线、控制信号线与设备控制器连接

设备控制器

• 设备控制器是CPU与I/O设备之间的接口，它接收从CPU发来的命令，并去控制I/O设备工作，以使处理机从繁杂的设备控制事务中解脱出来。
• 设备控制器主要职责是控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换。
• 若控制器可连接多个设备时，则应含有多个设备地址，并使每一个设备地址对应一个设备。

I/O通道

I/O通道设备的引入目的是使一些原来由CPU处理的I/O任务转由通道来承担，从而把CPU从繁杂的I/O任务中解脱出来。

采用通道有以下特点：

1. DMA（直接存储器存取）方式显著地减少了CPU的干预。
2. 只需向I/O通道发送一条I/O指令，即可完成一组相关的读（或写）操作及有关控制。
3. 可实现CPU、通道和I/O设备三者的并行操作，从而更有效地提高整个系统的资源利用率。

2、中断处理程序

中断和陷入—CPU外部事件和内部事件导致

基本概念：

• 中断源
• 中断请求
• 中断响应
• 关中断/开中断
• 中断屏蔽

中断处理层主要工作：

• 进行进程上下文的切换
• 对处理中断信号源进行测试
• 读取设备状态和修改进程状态等

中断处理程序的过程

• 测定是否有未响应的中断信号
• 保护被中断进程的CPU环境
• 转入相应的设备处理程序
• 中断处理
• 恢复被中断进程的现场

3、设备驱动程序

对I/O设备的控制方式

使用轮询的可编程I/O方式

• 程序I/O（Programmed I/O）方式，或称为忙 – 等待方式。处理机向控制器发出一条I/O指令启动输入设备输入数据时，同时把busy置为1，再不断循环测试busy。
• Busy=0，完成输入，处理机读取数据，送入指定单元，完成一次I/O。
• 对状态寄存器中的忙/闲标志busy的检查实现控制。

CPU的绝大部分时间都处在等待I/O设备完成数据I/O的循环测试中，会造成对CPU的极大浪费

使用中断的可编程I/O方式

效率高

直接存储器访问方式

（1）DMA控制方式

减少了CPU对I/O的干预

特点：

1. 数据传输的基本单位是数据块，即在CPU与I/O设备之间，每次传送至少一个数据块；
2. 所传送的数据是从设备直接送入内存的，或者相反；
3. 仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在控制器的控制下完成的。

提高了CPU与I/O设备的并行操作程度

I/O通道控制方式

• I/O通道方式是DMA方式的发展，它可进一步减少CPU的干预，即把对一个数据块的读（或写）为单位的干预，减少为对一组数据块的读（或写）及有关的控制和管理为单位的干预。
• 可实现CPU、通道和I/O设备三者的并行操作，从而更有效地提高整个系统的资源利用率。

中断vsDMA

1、中断方式是在数据缓冲寄存区满后，发中断请求，CPU进行中断处理；

DMA方式则是以数据块为单位传输的，在所要求传送的数据块全部传送开始或结束时需要CPU的干预，这样大大减少CPU进行中断处理的次数。

DMA方式不需CPU干预传送操作，不占用CPU任何资源，中断方式是程序切换，每次操作需要保护和恢复现场，中断次数多，CPU需要花较多的时间处理中断，中断次数多也会导致数据丢失。

2、中断方式的数据传送方向是由设备到CPU再到内存，或者相反。

DMA方式的数据传送则是将所传输的数据由设备直接送入内存，或是由内存直接送到设备。

4、与设备无关的I/O软件

为了实现设备独立性而引入了逻辑设备和物理设备这两个概念。

在应用程序中，使用逻辑设备名称来请求使用某类设备；

而系统在实际执行时，还必须使用物理设备名称。

设备独立性好处：

1. 设备分配时的灵活性
2. 易于实现I/O重定向

由于驱动程序与硬件紧密相关，为了实现设备独立性，必须在驱动程序之上设置一层软件，称为设备独立性软件

主要功能：

1. 公有操作
   • 对独立设备的分配与回收
   • 将逻辑设备名映射为物理设备名，进一步可以找到相应物理设备的驱动程序；
   • 对设备进行保护，禁止用户直接访问设备；
   • 缓冲管理
   • 差错控制
   • 提供独立于设备的逻辑块
2. 向用户层（或文件层）软件提供统一接口

5、虚拟设备域SPOOLing技术

虚拟设备技术是指把每次仅允许一个进程使用的物理设备，改造为能同时供多个进程共享的虚拟设备的技术，或者说将一个物理设备变为多个对应的逻辑设备。

SPOOLing技术也称假脱机操作，是指在多道程序的环境下，利用多道程序中的一道或两道程序来模拟外围控制机。从而在联机的条件下实现脱机I/O的功能。

SPOOLing系统的组成

1. 输入井和输出井。这是在磁盘上开辟的两个大存储空间。输入井是模拟脱机输入时的磁盘设备，用于暂存I/O设备输入的数据；输出井是模拟脱机输出时的磁盘，用于暂存用户程序的输出数据。
2. 输入缓冲区和输出缓冲区。为了缓和和CPU和磁盘之间速度不匹配的矛盾，在内存中要开辟两个缓冲区；输入缓冲区和输出缓冲区。输入缓冲区用于暂存由输入设备送来的数据，以后再传送到输入井。输出缓冲区用与暂存从输出井送来的数据，以后在传送给输出设备。
3. 输入进程SPi和输出进程SP0。这里利用两个进程来模拟脱机I/O时的外围控制机。其中，进程SPi模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区再送到输入井，当CPU需要输入数据时，直接从输入井读入内存；进程SP0模拟脱机输出时的外围控制机，把用户要求输出的数据从先内存送到输出井，待输出设备空闲时，在将输出井中的数据经过输出缓冲区送到输出设备上。
4. 井管理程序。用于控制作业与磁盘井之间信息的交换

SPOOLing系统的特点

1. 提高了I/O的速度
2. 将独占设备改造为共享设备
3. 实现了虚拟设备功能

假脱机打印机系统

1. 磁盘缓冲区
2. 打印缓冲区
3. 假脱机管理进程和假脱机打印进程

两件事：

• 在输出井中为之申请一个空闲的磁盘块区，并将要打印的数据送入其中
• 为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，然后将表挂到假脱机文件队列上

6、缓冲区管理

引入

1. 缓和CPU与I/O设备速度不匹配的矛盾
2. 减少对CPU的中断频率
3. 提高CPU和I/O设备之间的并行性

缓冲区

• 缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。
• 使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合（如存储器管理中所用的联想寄存器，由于对页表的访问频率极高，因此使用速度很快的联想寄存器来存放页表项的副本）
• 一般情况下，更多的是利用内存作为缓冲区，“设备独立性软件”的缓冲区管理就是要组织管理好这些缓冲区。

单缓冲

• 假设某用户进程请求某种块设备读入若干块的数据。若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）。
• 注意：当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出。
• 处理一块数据平均耗时Max(C,T)+M

从磁盘把一块数据输入到缓冲区的时间为T

OS将该缓冲区的数据传送到用户区的时间为M

CPU对这一块数据的处理时间为C

缺点：

1. 生产者与消费者在使用缓冲区时必须互斥。如果消费者尚未取出缓冲区的数据，即使生产者又生产出了新的数据，也无法将它送到缓冲区
2. 若两台机器之间只有单缓冲，则它们之间在任一时刻只能实现单方向的数据传输

双缓冲

• 假设某用户进程请求某种块设备读入若干块的数据。若采用双缓冲的策略，操作系统会在主存中为其分配两个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）
• 对一块数据的处理时间max(T,M+C)

环形缓存

• 将多个大小相等的缓冲区链接成一个循环队列。

使用：

1. Getbuf过程
2. Releasebuf过程

两种特殊情况：

1. Nexti指针追上Nextg指针，无缓冲区使用，输入进程应阻塞
2. Nextg指针追上Nexti指针，无装有数据的缓冲区供计算进程使用，计算进程阻塞

缓冲池

系统较大时，循环缓冲要消耗大量内存空间，利用率不高，为了提高缓冲区的利用率，引入了缓冲池

公有缓冲池即可用于输入又可用于输出，在池中设置了多个可供若干个进程共享的缓冲区

与缓冲区区别：

• 缓冲区仅仅是一组内存块的链表
• 缓冲池是包含了一个管理的数据结构及一组操作函数的管理机制，用于管理多个缓冲区

组成：

1. 空白缓冲队列emq
2. 输入队列inq
3. 输出队列outq
4. 四种工作缓冲区
   • 用于收容输入数据的工作缓冲区
   • 用于提取输入数据的工作缓冲区
   • 用于收容输出数据的工作缓冲区
   • 用于提取输出数据的工作缓冲区

#MS(type) :互斥信号量
#RS(type) :资源信号量
void Getbuf(unsigned type)
{
    Wait(RS(type));
    Wait(MS(type));
    B(number) = Takebuf(type);
    Signal(MS(type));
}
void Putbuf(type, number)
{
    Wait(MS(type));
    Addbuf(type, number);
    Signal(MS(type));
    Signal(RS(type));
}

1. 收容输入。输入进程可调用Getbuf(emg)过程，从空缓冲队列emq 的队首摘下一空缓冲区，把它作为收容输入工作缓冲区 hin。然后，把数据输入其中，装满后再调用 Putbuf(inq,hin)过程，将它挂在输入队列 inq 队列上。
2. 提取输入。计算进程可调用 Getbuf(inq)过程，从输入队列 inq 的队首取得一缓冲区，作为提取输入工作缓冲区(sin)，计算进程从中提取数据。计算进程用完该数据后，再调用 Putbuf(emq,sin)过程，将它挂到空缓冲队列emq 上。
3. 收容输出。计算进程可调用 Getbuf(emq)，从空缓冲队列 emq 的队首取得一空缓冲，作为收容输出工作缓冲区hout。当其中装满输出数据后，又调用 Putbuf(outq,hout)过程，将它挂在outq末尾。 **
4. 提取输出。输出进程可调用 Getbuf(outq)过程，从输出队列的队首取得一装满输出数据的缓冲区，作为提取输出工作缓冲区sout。在数据提取完后，再调用 Putbuf(emq,sout) 过程，将它挂在空缓冲队列末尾。

7、磁盘系统与磁盘调度

磁盘系统

提高磁盘I/O速度的主要途径：

（1）选择性能好的磁盘

（2）采用好的磁盘调度算法

（3）设置磁盘高速缓存（Disk Cache）

（4）其它方法

（5）采用高度可靠、快速的容量磁盘系统–磁盘冗余阵列

数据的组织与格式

• 存储面
• 磁道
• 柱面
• 扇区

磁道访问时间：

（1）寻道时间Ts：

指把磁臂（磁头）移动到指定磁道上所经历的时间
$$
T_{s} = m * n+s
$$
s：启动磁臂时间

n：磁头移动n条磁道

m：移动每一条磁道所花费时间

（2）旋转延迟时间Tτ：

指定扇区移动到磁头下面所经历的时间

（3）传输时间Tt

指把数据从磁盘读出或向磁盘写入数据所经历的时间

Tt 的大小与每次所读/写的字节数b 和旋转速度有关：
$$
T_{t}=\frac{b}{rN}
$$
r为磁盘每秒钟转数；N为一条磁道上的字节数

磁盘调度

先来先服务FCFS

根据进程请求访问磁盘的先后次序进行调度

最短寻道优先SSTF

选择这样的进程，其要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短

可能会导致某个进程发生“饥饿”现象

扫描（SCAN）算法

优先考虑的是磁头当前的移动方向。

例如，磁头自里向外移动, 并同时自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向自外向里移动。（又常称之为电梯调度算法）

当磁头刚从里向外（或刚从外向里）移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，那它必须等待磁头到达磁盘的另一端，反向回来后，才能得到处理。

循环扫描算法（CSCAN)

磁头单向移动，例如，只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。

磁道由外向里编号

8、做题

1、通道控制控制器，设备在控制器控制下工作

2、共享设备必须是可寻址的和可随机访问的设备

3、通道是一种特殊的处理机，具有执行I/O指令集的能力。主机的CPU和通道可以并行工作，并通过I/O指令和I/O中断实现彼此的通信和同步

4、在I/O控制方式的发展过程中，最重要的推动因素是减少主机对I/O控制的干预。提高I/O速度和设备利用率，在OS中主要依靠缓冲管理功能

5、打印机的I/O控制主要采取程序中断的方式

6、在程序I/O方式中，对于输出设备，准备就绪是指输出缓冲区已空

7、在单用户系统中可为整个系统设置一张逻辑设备表，在多用户系统中应为每个用户设置一张逻辑设备表

8、为实现设备分配，应为每个设备设置一张设备控制表，在系统中设置一张系统设备表，为实现设备独立性，系统中应设置一张逻辑设备表

9、SPOOLing系统实现了对I/O设备的虚拟，只要输入设备空闲，SPOOLing可预先将输入数据从设备传送到输入井中供用户程序随时读取

在SPOOLing系统中，用户程序可随时将输出数据送到输出井中，待输出设备空闲时再执行数据输出操作

10、同一用户所使用的I/O设备也可以并行操作

七、文件管理

1、概念

文件是存储和管理数据的容器

文件时指由创建者所定义的，具有文件名的一组相关元素的集合

• 有结构的文件：文件由若干个相关记录组成
• 无结构文件：看成一个字符流

文件在文件系统是一个基本的管理单元，这个管理单元必然有一组属性

属性：

• 文件类型
• 文件长度
• 文件的物理位置
• 文件的建立时间

文件类型

按用途：

1. 系统文件：可调用，不可读，不允许修改
2. 用户文件
3. 库文件

按文件中的数据形式：

1. 源文件
2. 目标文件
3. 可执行文件

按存取控制属性：

1. 只执行文件
2. 只读文件
3. 读写文件

按组织形式和处理方式：

1. 普通文件
2. 目录文件
3. 特殊文件：特指系统中的各类I/O设备

文件系统：

操作系统中的各类文件、管理文件的软件，以及管理文件所涉及到的数据结构等信息的集合

功能：

• 有效地管理文件的存储空间；
• 管理文件目录；
• 完成文件的读/写操作；
• 实现文件共享与保护；
• 为用户提供交互式命令接口和程序调用接口

文件系统模型

不完整，一般为下图

（1）对象及其属性

• 文件
• 目录
• 磁盘（磁带）存储空间

对目录的组织和管理是方便用户和提高对文件存取速度的关键

（2）对对象操纵和管理的软件集合

核心部分

• 对文件存储空间的管理
• 对文件目录的管理
• 用于将文件的逻辑地址转换为物理地址的机制
• 对文件读和写的管理
• 以及对文件的共享与保护等功能。

（3）文件系统接口

• 命令接口：用户与文件系统交互
• 程序接口：用户程序与文件系统交互

2、文件基本操作

1. 最基本：创建文件、删除文件。读文件、写文件、截断文件和设置文件的读／写位置
2. 文件的“打开”和“关闭”操作
3. 其他文件操作：对文件属性的操作，改变文件名、改变文件的拥有者，查询文件的状态等

3、文件系统目录管理

管理要求：

1. 实现“按名存取”
2. 提高对目录的检索速度
3. 文件共享
4. 允许文件重名

文件控制块（FCB）：用于描述和控制文件的数据结构

文件目录：文件控制块的有序集合

通常，一个文件目录也被看做是一个文件，称为目录文件。

FCB内容：

• 基本信息：文件名、文件类型等；
• 地址信息：卷（存储文件的设备）、起始地址（起始物理地址）、文件长度（以字节、字或块为单位）等。
• 访问控制信息：文件所有者、访问信息（用户名和口令等）、合法操作等；
• 使用信息：创建时间、创建者身份、当前状态、最近修改时间、最近访问时间等。

目录项的两种组织方式：

1. FCB存储全部目录内容
2. 存储部分目录信息，如文件名、索引节点指针等，其余部分保存在索引节点（i节点）。打开文件时将索引节点从磁盘读到内存中。

索引节点：文件描述信息单独形成一个数据结构。文件名与索引节点分开。

文件目录保存：文件名和对应的文件索引节点

每个文件都在磁盘上保存一个磁盘索引节点，当文件被打开时，文件的索引节点从磁盘读入内存，称为内存索引节点。

目录结构

单级目录结构

所有用户的全部文件目录保存在一张目录表中，每个文件的目录项占用一个表项

实现目录管理的基本功能—按名存取

缺点：

• 查找速度慢
• 不允许重名
• 不便于实现文件共享

两级目录结构

• 一定程度解决了重名问题
• 提高了文件目录检索效率
• 简单的文件共享

在文件系统中，用户以虚拟地址方式使用外存

树形结构目录

多级目录结构

主目录在这里被称为根目录，把数据文件称为树叶，其它的目录均作为树的结点。

用户的主目录就是用户注册进入系统时的初始基本目录

UNIX的文件目录系统采用可装卸式多级树型目录

目录操作

1. 创建目录
2. 删除目录：不删除非空目录、可删除非空目录
3. 改变目录
4. 移动目录
5. 查找

目录查询技术

线性检索法

顺序检索法

• 在单级目录中，利用用户提供的文件名，用顺序查找法直接从文件目录中找到指名文件的目录项。
• 在树型目录中，用户提供的文件名是由多个文件分量名组成的路径名，此时须对多级目录进行查找。

在操作系统中，将文件名转换为文件存储地址，对文件实施控制管理都是通过文件目录来实现的

Hash法

略

4、文件系统外存管理

磁盘管理的主要任务和目标是；

• 有效地利用外存空间
• 提高对文件的访问速度
• 提高磁盘系统的可靠性

目前，常见的文件磁盘块的组织方法有:

• 连续组织
• 链接组织
• 索引组织

连续组织

连续分配(Continuous Allocation)要求为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址。

把逻辑文件中的数据顺序地存储到物理上邻接的各个数据块中，这样形成的物理文件可以进行顺序存取。

文件目录中为每个文件建立一个表项，其中记载文件的第一个数据块地址及文件长度。

对于顺序文件，连续读/写多个数据块内容时，性能较好。

优点：

1. 顺序访问容易
2. 顺序访问速度快

缺点：

1. 要求有连续的存储空间
2. 必须事先知道文件的长度

链接组织方式

链接文件：采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的物理文件称为链接文件。

优点：

• 消除磁盘外部碎片，提高了利用率
• 对插入、删除和修改记录都非常容易；
• 能适应文件的动态增长，无需事先知道文件的大小。

隐式链接

在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。

缺点：只适合于顺序访问，它对随机访问是极其低效的。

为了提高检索速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇(cluster)

比如，一个簇可包含4 个盘块，在进行盘块分配时，是以簇为单位进行的。在链接文件中的每个元素也是以簇为单位的。

减少查找时间和指针所占空间，但增大了内部碎片

显示链接

指把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。

整个磁盘仅设置一张文件分配表（FAT File Allocation Table）

缺点：FAT需要占用较大的内存空间

索引组织

单级索引

为每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块号的数组

优点：

• 支持直接访问
• 基于数据块的分区能消除外部碎片

缺点：

• 大文件索引项较多
• 索引块可能要花费较多的外存空间

两级索引

当文件太大，其一级索引块太多时，这种方法是低效的。此时，应为这些索引块再建立一级索引，形成两级索引分配方式。

增量式索引

全面照顾小、中、大及特大文件的组织需求。

同时采用：

• 直接寻址：10个块号
• 一级索引，一次间址：一个索引块
• 二级索引，二次间址
• 三级索引，三次间址

5、磁盘空闲空间管理

存储空间的基本分配单位是磁盘块。

系统应为分配存储空间而设置相应的数据结构；其次，系统应提供对存储空间进行分配和回收的手段。

空闲分区表

空闲表法属于连续分配方式，它为每个文件分配一块连续的存储空间，即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息

适合于可变大小分区的连续分配方式

为文件分配存储空间时，首先顺序查找空闲分区表中的各个表项，直至找到第一个大小适合的空闲分区。

可以采用首次适应分配算法、最佳适应分配算法等。然后，将该分区分配给文件，同时修改空闲分区表，删除相应表项。

当删除文件释放出空间时，系统回收其存储空间，合并相邻空闲分区.

• 优点：实现简单
• 缺点：当存储空间中的空闲分区分布较分散且数量较多时，空闲分区表将会很大。需要很大的内存空间，会降低空闲分区表的检索速度。

空闲链表法

空闲链表法是将所有空闲盘区拉成一条空闲链。

根据构成链所用基本元素的不同，可把链表分成两种形式：

• 空闲盘块链
• 空闲盘区链

空闲盘块链

将磁盘上的所有空闲空间，以盘块为单位拉成一条链。

• 当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。
• 当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。

优点：用于分配和回收一个盘块的过程非常简单.

空闲盘区链

将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。

在每个盘区上含有用于指示下一个空闲盘区的指针和能**指明本盘区大小(盘块数)**的信息。

通常采用首次适应算法

回收盘区时，同样也要将回收区与相邻接的空闲盘区相合并

问题：

• 一段时间以后，可能会使空闲分区链表中包含太多小分区，使文件分配到的存储空间过分离散。
• 删除一个由许多离散小分区组成的文件时，将回收的小分区链接到空闲分区链表中需要很长时间。
• 若一个文件申请连续存储空间，则需要花费较长的时间查找相邻的空闲分区。

适用于非连续存储文件

位示图

利用二进制位0、1表示存储空间中存储块的使用状态。空闲分区:0，已分配分区:1（或者相反）

通常可用m × n 个位数来构成位示图，并使m × n等于磁盘的总块数。

盘块分配：

(1) 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。

(2) 将所找到的一个或一组二进制位转换成与之相应的盘块号。

假定找到的其值为“0”的二进制位位于位示图的第i 行、第j列，则其相应的盘块号应按下式计算：
$$
b=n(i-1)+j
$$
(3)修改位示图，令map[i,j]=1

盘块回收

（1）将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：
$$
i=(b-1)DIVn+1
\j=(b-1)MODn+1
\DIV ~~~~取整
$$
（2）修改位示图。令map[i,j] =0

优点：可以很容易的找到一个或一组连续的空闲分区

一个位示图需要占用的存储空间：磁盘容量（字节数）/ （8 * 数据块大小）

缺点：很难一次性将该位示图全部装入内存。即使内存足够大，可以存放全部或绝大部分位示图数据，搜索一个很大的位示图将会降低文件系统的性能。

尤其当磁盘空间快用完，剩下的空闲磁盘块很少时，文件系统的性能将严重降低。

成组链接法

• 将磁盘空闲块分成若干组，如将100个盘块作为一组，用索引表表示；
• 该组空闲块总数和各空闲块块号存入下一组的第一个空闲块中（从后往前分组），各组通过链接指针连在一起形成链表；
• 最后不满100块的那组空闲块总数和各空闲块块号计入磁盘区专用管理块（超级块）的空闲盘块号栈的s_nfree和s_free[100]中

分配：

• 未到栈底：出栈，将栈顶盘块分配给用户
• 已到栈底盘块：调用磁盘读过程将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去（其中的有用数据已读入栈中）。然后，再分配一相应的缓冲区作为该盘块的缓冲区。最后，把栈中的空闲盘块数-1并返回

回收：

• 栈未满：进栈，依次将回收盘块号压入栈中
• 栈已满：将现有栈中的100个盘块号记入新回收的盘块中，再将其盘块号作为新栈底

仅适用于离散分配形式，无法用于连续分配

优点：

• 无需占用额外的磁盘空间
• 分配回收速度快
• 大小磁盘均可采用

缺点：

• 不适用于连续分配

6、文件共享与保护

文件共享

1. 同时存取
2. 存取权限

同时存取

• 允许多个用户同时读文件内容，但不允许同时修改，或同时读且修改文件内容。
• 共享用户之一修改文件内容时，可以将整个文件作为临界资源，锁定整个文件，不允许其他共享用户同时读或写文件。
• 也可以仅仅锁定指定的一条记录，允许其他共享用户读/写该文件的其它记录。后者的并发性能更好。
• 涉及进程的同步与互斥

存取权限

• 无（None） — 用户不知道文件的存在。用户无法获知该文件的目录信息，当然更不会知道文件的内容。
• 探知（Knowledge） — 用户可以检测文件的存在和文件的文件主，还可以向文件主申请增加对该文件的存取权限。
• 执行（Execution） — 用户可以装载并执行程序，但不允许拷贝程序内容。
• 读（Reading）— 允许用户读文件内容，包括拷贝和执行文件。某些系统严格地将浏览文件内容和拷贝权限分开，可以控制文件只能被浏览（显示），不能被拷贝。
• 追加（Appending）— 允许用户向文件添加数据，通常只能将数据添加到文件尾。但是，不能修改或删除文件内容。例如，超市收银员只能将新结帐的数据添加到文件中，不允许其修改或删除已有的数据。
• 更新（Updating）— 允许用户修改、删除、增加文件内容。包括创建文件、重写文件的全部或部分内容、移动文件的全部或部分数据等操作。
• 更改权限 (Changing protection) — 一般只有文件主才能更改共享该文件的其他用户对该文件的存取权限。有的系统允许文件主将更改文件存取权限赋予其他某个用户，但必须限制授权用户更改的权限范围。
• 删除 (Deletion) — 允许用户删除文件

后一种权限包含前一种及前面各种存取权限

实现文件共享的实质就是可以从不同地方打开同一个文件

打开文件的首要步骤就是找到文件的目录项，读取文件在外存的起始地址

链接目录项实现法

文件目录项中设置一个链接指针，用于指向共享文件的目录项。

访问文件时，根据链接指针内容找到共享文件的目录项，读取该目录项中文件起始位置等信息，操作该文件。

每当有用户（进程）共享文件时，共享文件目录项中的“共享计数”加1；当用户不再共享该文件，撤消链接指针时，“共享计数”减1。

只有当共享文件用户数为1时，才能删除共享文件。

索引节点实现法

文件的物理地址及其它的文件属性等信息，不再是放在目录项中，而是放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。

由任何用户对文件进行Append 操作或修改，所引起的相应结点内容的改变(例如，增加了新的盘块号和文件长度等)，都是其他用户可见的，从而也就能提供给其他用户来共享。

可以通过共享文件索引节点来共享文件，即当用户需要共享文件时，在自己的文件目录中新建一个目录项，为共享文件命名(也可用原名)，并将索引节点指针指向共享文件的索引节点。

在索引结点中还应有一个链接计数count，用于表示链接到本索引结点(亦即文件)上的用户目录项的数目。

• 当用户C创建一个新文件时，他便是该文件的所有者，此时将count 置1。
• 当有用户B要共享此文件时，在用户B 的目录中增加一目录项，并设置一指针指向该文件的索引结点，此时，文件主仍然是C，count=2。

符号链实现法

为使B能共享C的一个文件F，可以由系统创建一个LINK类型的新文件，也取名为F并将F写入B的目录中，以实现B的目录与文件F的链接；在新文件中只包含被创文件F的路径名。这样的链接方法被称为符号链接.

新文件中的路径名，则只被看作是符号链。当B要访问被链接的文件F且正要读LINK类新文件时，将被OS截获， OS根据新文件中的路径名去读该文件，于是就实现了用户B对文件F的共享。

（快捷方式？？？！！！）

在利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的指针,而共享该文件的其它用户，则只有该文件的路径名，并不拥有指向其索引结点的指针。

优点：能连接任何机器上的文件

缺点：

• 访问共享文件时要多次读盘，开销大
• 建立符号链时仍需要配置索引节点，耗费一定的磁盘空间

利用URL

统一资源定位器URL (Uniform Resource Locator)是Internet上用来链接超文本文件的一种方法。

（在线文档呗）

7、做题

1、文件系统最基本的目标是按名存取，它主要是通过文件共享功能实现的，文件系统所追求的最重要的目标就是文件安全性管理

2、FC通常存放在该文件的上级目录的数据盘块中

3、Windows FAT32的目录项中不会包含文件控制块的物理位置，而Unix的磁盘索引节点中不会包含文件名信息

4、在执行close的过程时，若系统打开文件表项引用技术f.count=0不成立，应置用户文件描述符表项为空；若f.count=0但内存索引节点引用计数i.count=0不成立，应使用户文件描述符和文件表项皆为空，若i.count=0，则关闭文件

八、操作系统接口

1、操作系统与用户接口

1. 命令接口：用户在终端输入命令与系统交互或者是用户通过提交作业控制说明书来控制系统运行。这种方式要求用户记忆所提交的命令。分为：联机用户接口（交互式方式运行的命令）与脱机用户接口（批处理用户接口）；
   • 联机命令
   • 终端处理程序
   • 命令解释程序
2. 程序接口：通过系统调用实现，这种接口主要提供给程序员使用，在OS的外层软件或用户程序中，凡是与资源有关的操作都必须通过该接口向操作系统提出服务请求，并由OS完成
3. 图形接口：采用了图形化的操作界面，直观，方便，易学，更适合于普通用户使用

2、系统调用

系统调用在用户空间进程和硬件设备之间添加了一个中间层，该层的主要作用有两个:

为用户空间提供了一种硬件的抽象界面，例如，当需要读文件时，应用程序可以不管磁盘类型和介质，甚至不用去管文件所在的文件系统到底是哪种类型；

系统调用保证了系统的稳定和安全。

各种版本的UNIX系统都提供了定义明确、数量有限、可直接进入内核的入口点，这些入口点被称为系统调用

系统调用和普通调用的区别：

系统调用本质上是一种过程调用，但它是一种特殊的过程调用，与一般用户程序中的过程调用有明显区别

	系统调用	一般过程调用
运行状态	主调程序：用户态 被调程序：系统态	主调程序和被调程序 同在用户态或系统态
状态切换	通过软中断进行状态切换	不切换
返回问题	可能引起调度 （与调度算法有关）	不调度
嵌套调用	有深度限制	不限制调度

1. 运行在不同的系统状态。一般的过程调用，其调用程序和被调用程序都运行在相同的状态——系统态或用户态；而系统调用与一般调用的最大区别就在于：调用程序是运行在用户态，而被调用程序是运行在系统态
2. 通过软中断进入。由于一般过程调用不涉及到系统状态的转换，故可直接由调用过程转向被调用过程。但在运行系统调用时，由于调用和被调用过程是工作在不同的系统状态，因而不允许由调用过程直接转向被调用过程，通常都是通过软中断机制，先由用户态转换为系统态，经核心分析后，才能转向相应的系统调用处理子程序
3. 返回问题。一般的过程调用在被调用过程执行完后，将直接返回到调用过程继续执行。但对系统调用，如果系统采用抢占调度方式，则在被调用过程执行完后，必须对系统中所有要求运行的进程做优先权分析。只有当调用进程仍具有最高优先权时，才返回到调用进程继续执行；否则，将引起重新调度