操作系统

1.1_1 操作系统的概念、功能和目标

• 提供的功能
• 命令接口（联机（交互式）命令接口|脱机（批处理）命令接口）
• 程序接口（通过系统调用来使用）
• GUI（图形用户界面win|ios|andriod）

• 目标
• 方便用户使用

1.1_2 操作系统的特征

• 互斥共享方式：一个时间段内只允许一个进程访问该资源

• 同时共享方式：允许一个时间段内由多个进程“同时”对它们进行访问

• 空分复用计数（例如虚拟内存）

• 时分复用计数（例如虚拟处理器）

1.1_3 操作系统的发展与分类

• 手工操作阶段
• 纸带机（用户独占全机、人机速度矛盾）

• 批处理阶段
• 单道批处理系统（外围机——磁带）CPU有大量时间是在空闲等待I/O完成
• 多道批处理系统（操作系统开始出现）没有人机交互

• 分时操作系统（解决了人机交互问题）
• 轮流处理作业
• 不能处理紧急任务

• 实时操作系统
• 优先处理紧急任务
• 硬实时系统：必须在严格的时间内完成处理
• 软实时系统：可以偶尔犯错

• 网络操作系统

• 分布式操作系统

• 个人计算机操作系统

1.1_4 操作系统的运行机制与体系结构

• 运行机制
• 两种指令
• 特权指令
• 非特权指令
• 两种处理器状态
• 内核态（root）
• 用户态
• 两种程序
• 内核程序(运行在内核态 )
• 应用程序

• 操作系统内核
• 时钟管理（实现计时功能）
• 中断处理
• 原语（程序运行具有原子性，不可中断）
• 对系统资源进行管理的功能
• 进程管理
• 存储器管理
• 设备管理

• 操作系统的体系结构
• 大内核（将操作系统的主要功能模块都作为系统内核，运行在核心态）
• 微内核（只把最基本的功能保留在内核）
有且仅有CPU调度和IPC必须在微内核内部



变态需要时间，频繁变态会影响系统性能

1.1_5 中断和异常

• 中断机制的诞生
• 操作系统介入，开展管理工作
• “用户态—>核心态”是通过中断实现的。并且中断是唯一途径

• 中断的概念和作用

• 中断的分类
• 内中断（异常） 陷入指令（用户态）可以引发内中断，切换为内核态执行系统调用
• 陷阱（trap）
• 故障（fault）
• 中止（abort）
• 外中断 （CPU外部）（例如时钟中断信号，I/O中断信号）

• 中断处理程序 中断向量表

1.1_6 系统调用

• 系统调用是操作系统向上层提供的接口

• 有的库函数是对系统调用的进一步封装

• 当今编写的应用程序大多是通过高级语言提供的库函数间接地进行系统调用

1.1_7 虚拟机

2.1_1 进程的定义、组成、组织方式、特征

• 进程状态：就绪、运行、等待、停止、新的

• 程序计数器PC

• CPU寄存器

• CPU调度信息：进程优先级、调度队列指针

• 内存管理信息：页表、段表

• 记账信息：CPU时间

• I/O状态信息：分配给进程的I/O设备列表

2.1_2 进程的状态与转换

2.1_3 进程控制

2.1_4 进程通信

2.1_5 线程概念和多线程模型

• 线程是处理机调度的基本单位

• 多CPU计算机中，各个线程可占用不同的CPU

• 每个线程都有一个线程ID、线程控制块（TCB）

• 线程也有就绪、阻塞、运行三种基本状态

• 线程几乎不拥有系统资源

• 同一进程的不同线程间共享进程的资源

• 由于共享内存地址空间，统一进程中的线程间通信甚至无需系统干预

• 同一进程中的线程切换，不会引起进程切换

• 不同进程中的线程切换，会引起进程切换

• 切换同进程内的线程，系统开销很小

• 切换进程，系统开销较大

2.1_6 线程切换、TCB

2.2_1 处理机调度的概念、层次

2.2_2 进程调度的时机、切换与过程调度方式

• 主动放弃（进程正常终止、运行过程中发生异常而终止、进程主动请求阻塞）

• 被动放弃（分给进程的时间片用完、有更紧急的事需要处理、有更高优先级的进程进入就绪队列）

• 在处理中断的过程中

• 在操作系统内核程序临界区中
• 临界资源：一个时段段内各进程互斥地访问临界资源
• 临界区：访问临界资源的那段代码
• 内核程序临界区会访问就绪队列，导致其上锁

• 在原子操作过程中（原语）

• 狭义：选择一个进程

• 广义：狭义+进程切换

• 对原来运行进程各种数据的保存

• 对新的进程各种数据的恢复

• 只允许进程主动放弃处理机

• 进程被动放弃，可以优先处理紧急任务，适合分时操作系统、实时操作系统

2.2_3 调度算法的评价指标

• 周转时间（提交作业到完成作业花费的时间）、平均周转时间（各作业周转时间之和/作业数）

• 带权周转时间（作业周转时间/作业实际运行的时间）、平均带权周转时间（各作业带权周转时间/作业数）

2.2_4 FCFS、SJF、HRRN调度算法

2.2_5 时间片轮转、优先级调度、多级反馈队列（适合交互式系统）

2.2_6 多级队列调度算法

2.3_1 进程同步、进程互斥

do{
    entry section;     //进入区     对访问的资源检查或进行上锁    
    critical section;  //临界区(段) 访问临界资源的那部分代码
    exit section;      //退出区     负责解锁    
    remainder section; //剩余区     其它处理
} while(true)

2.3_2 进程互斥的软件实现方法

int turn =0;//p0进程
while(turn!=0);
critical section;
turn = 1;
remainder section;//p1进程
while(turn!=1);
critical section;
turn = 0;
remainder section;

bool flag[2]={false,false};//p1进程
while(flag[1]);
flag[0]=true;
critical section;
flag[0]=false;
remainder section;//p2进程
while(flag[0]);
flag[0]=true;
critical section;
flag[1]=false;
remainder section;

bool flag[2]={false,false};//p1进程
flag[0]=true;
while(flag[1]);
critical section;
flag[0]=false;
remainder section;//p2进程
flag[0]=true;
while(flag[0]);
critical section;
flag[1]=false;
remainder section;

bool flag[2]={false,false};
int turn=0;//p1进程
flag[0]=true;turn=1;
while(flag[1]&&turn==1);
critical section;
flag[0]=false;
remainder section;//p2进程
flag[1]=true;
turn=0;
while(flag[0]&&turn==0);
critical section;
flag[1]=false;
remainder section;

2.3_3 进程互斥的硬件实现方法

//true表示已经上锁
bool TestAndSet(bool *lock){
    bool old;
    old=*lock;
    *lock=true;
    return old;
}

//以下是使用TSL指令实现互斥的算法逻辑
while(TestAndSet (&lock));//上锁并检查
//只有lock被其他进程变成false才能继续执行
临界区代码段
lock=false; //解锁

//true表示已经上锁
void Swap(bool *a,bool *b){
    bool temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

//以下是使用Swap指令实现互斥的算法逻辑
bool old=true;
while(old=true)
    Swap(&lock,&old);
//临界区代码段
lock=false; //解锁
//剩余代码段

2.3_4 信号量机制

int S=1;
void wait(int S){ //wait原语，相当于：进入区
    while(S<=0);  //如果资源数不够，就意志循环等待
    S=S-1;        //如果资源数够，则占用一个资源
}

void signal(int S){//signal原语，相当于“退出区”
    S=S+1;         //使用完资源后，在退出区释放资源
}

//记录型信号量的定义
typedef struct{
    int value;
    struct process *L;
} semaphore;
//某进程需要使用资源时，通过wait原语申请
void wait (semaphore S){
    S.value--;
    if(S.value<0){
        block (S.L);//将该进程加入到消息队列中
    }
}
//进程使用完资源后，通过signal原语释放
void signal (semaphore S){
    S.value++;
    if(S.valie<=0){
        wakeup(S.L);
    }
}

2.3_5 用信号量机制实现进程互斥、同步、前驱关系

2.3_6 生产者-消费者问题

semaphore mutex=1;
semaphore emtpy=n;
semaphore full=0;

void Producer(){
  while(1){
    produce();
    P(emtpy);
    P(mutex);
    V(full);
    V(mutex);
  }
}

void Consumer(){
  while(1){
    P(full);
    P(mutex);
    V(empty);
    V(mutex);
    consume();
	}
}

2.3_7 多生产者-多消费者模型

2.3_8 吸烟者问题

2.3_9 读者-写者问题

semaphore rw=1;//用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count=0;//记录当前有几个读进程在访问文件
semaphore mutex=1;//用于保证对count变量的互斥访问
semaphore w=1; //用于实现“写优先”
    
writer(){
    while(1){
        P（w）;
        P(rw); //写之前“加锁”
        写文件。。。
        V（rw);//写之后“解锁”
    	V(w);
    }
}

reader(){
    while(1){
        P(w);
	    P(mutex);   //各读进程互斥访问count
        if(count==0) 
            P(rw);  //第一个读进程的读进程数+1
        count++;	//访问文件的读进程数+1
        V(mutex);	
        V(w);
        读文件...
        P(mutex);	//各读进程互斥访问count
        count--;	//访问文件的读进程数-1
        if(count==0)
            V(rw);	//最后一个读进程负责“解锁”
        V(mutex);
    }
}

2.3_10 哲学家进餐问题

semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex = 1;  //互斥地取筷子
Pi(){				 //i号哲学家的进程
    while(1){
        P(mutex);
        p(chopstick[i]);      //拿右
        p(chopstick[(i+1)%5]);//拿左
        V(mutex);
        吃饭...
        V(chopstick[i]);
        V(chopstick[(i+1)%5]);
        思考...
    }
}

2.3_11 管程

• 局部于管程的共享数据结构说明

• 对该数据结构进程操作的一组过程

• 对局部于管程的共享数据设置初始值的语句

• 管程有一个名字

• 局部于管程数据结构只能被局部于管程的过程所访问

• 一个进程只有通过调用管程内的过程才能进入管程访问共享数据

• 每次仅允许一个进程在管程内执行某个内部过程

monitor producerconsumer
    condition full,empty;
    int count = 0;
    void insert(Item item){
        if(count == N)
            wait(full);
        count++;
        insert_item (item);
        if(count == 1)
            signal(empty);		//count==1说明原来count=0，可能有消费者在等待，唤醒它
    }
    Item remove(){
        if(count == 0)
            wait(empty);
        count--;
        if(count == N-1)
            signal(full);		//count==N-1说明原来count=N，可能有生产者在等待，唤醒它
        return remove_item();
    }
    end monitor;

//使用
producer(){
    while(1){
        item = 生产一个产品;
        producerconsumer.insert(item);
    }
}

consumer(){
    while(1){
        item = producerconsumer.remove();
        消费产品 item;
    }
}

2.4_1 死锁的概念

• 互斥条件：多个进程争夺资源发生死锁

• 不剥夺条件：进程获得的资源不能由其它进程强行抢夺

• 请求和保持条件：某个进程有了资源，还在请求资源

• 循环等待条件：存在资源的循环等待链

• 对系统资源的竞争

• 进程推进顺序非法

• 信号量的使用不当也会造成死锁

• 预防死锁

• 避免死锁

• 死锁的检测和解除

2.4_2 死锁的处理策略——预防死锁

• 静态策略：预防死锁
• 破坏互斥条件（有些不能破坏） 把互斥的资源改造为共享资源
• 破坏不剥夺条件（复杂，造成之前工作失效，降低系统开销，会全部放弃、导致饥饿） 方案1：当请求得不到满足的时候，立即释放手里的资源 方案2：由系统介入，强行帮助剥夺
• 破坏请求和保持条件（资源利用率极低，可能会导致某些进程饥饿） 采用静态分配方法，一次性全部申请，如果申请不到，不要允许
• 破坏循环等待条件（不方便增加新的设备，实际使用与递增顺序不一致，会导致资源的浪费，必须按规定次序申请资源） 顺序资源分配法：对资源编号，进程按编号递增顺序请求资源

• 动态检测：避免死锁

• 死锁的检测和解除

2.4_3 死锁的处理策略——避免死锁

• 什么是安全序列
进行后面的某些情况，不会使系统发生死锁

• 什么是系统的不安全状态，与死锁有何联系 如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定时在不安全状态）

• 如何避免系统进入不安全状态——银行家算法
初始分配完成后，优先全部分配给最少的，并且拿回资源

2.4_4 死锁的处理策略——检测和解除

• 静态链接（在程序运行前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件）

• 装入时动态链接（将各目标模块装入内存时，边装入边链接的链接方式）

• 运行时动态链接（在程序执行中需要该模块时，才对它进行链接，其优点时便于修改和更新。）

• 绝对装入在编译的时候就知道程序放在内存的哪个位置，编译、链接后得到的装入模块的指令直接就使用了绝对地址（装入之前）。只适用于单道程序环境

• 静态重定位装入时将逻辑地址转表为物理地址。在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业

• 动态重定位把地址转化推迟到程序真正要执行时才进行。装入内存时依然是逻辑地址，需要一个重定位寄存器来存放装入模块的起始位置，CPU执行时会将逻辑地址与重定位寄存器的指相加。允许程序在内存中发生移动

3.1_1 内存的基础知识

• 静态链接（在程序运行前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件）

• 装入时动态链接（将各目标模块装入内存时，边装入边链接的链接方式）

• 运行时动态链接（在程序执行中需要该模块时，才对它进行链接，其优点时便于修改和更新。）

• 绝对装入在编译的时候就知道程序放在内存的哪个位置，编译、链接后得到的装入模块的指令直接就使用了绝对地址（装入之前）。只适用于单道程序环境

• 静态重定位装入时将逻辑地址转表为物理地址。在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业

• 动态重定位把地址转化推迟到程序真正要执行时才进行。装入内存时依然是逻辑地址，需要一个重定位寄存器来存放装入模块的起始位置，CPU执行时会将逻辑地址与重定位寄存器的指相加。允许程序在内存中发生移动

3.1_2 内存管理的概念

• 设置上下限寄存器

• 采用重定位寄存器（基址寄存器，存放起始物理地址）和界地址寄存器（限长寄存器，存放最大逻辑地址）

3.1_3 覆盖与交换

3.1_4 连续分配管理方式

3.1_5 动态分区分配算法

3.1_6 基本分页存储管理的基本概念

3.1_7 基本地址变换机构

3.1_8 具有快表的地址变换机构

3.1_9 两级页表

3.1_10 基本分段存储管理方式

3.1_11 段页式的管理方式

3.2_1 虚拟内存的基本概念

• 时间局部性

• 空间局部性

• 高速缓存技术

3.2_2 请求分页管理方式

• 只有“写指令“修改“修改位“，一般来说只需要修改快表中的数据，只有快表快被删除时才会写回内存中的慢表

• 换入/换出都需要启动慢速的IO操作，太频繁会有很大开销

• 页面调入内存后需要修改慢表，同时将表项复制到快表中，系统会查快表然后访问目标内存单元

3.2_3 页面置换算法

3.2_4 页面分配策略

• 固定分配局部替换：驻留集大小不可改变

• 可变分配全局替换：可以将操作系统保留的空闲物理块分配给缺页进程，如果没有空闲物理块，选一个未锁定的页面调出，被选中的进程拥有的物理块会减少，缺页率上升。只要缺页就给分配新物理块

• 可变分配局部替换：只能选进程自己的物理块置换，操作系统根据缺页的频率来动态地增加或减少进程的物理块

3.2_5 内存映射文件

• 以访问内存的方式访问文件数据

• 文件数据的读入、写出由操作系统自动完成

• 进程关闭文件时操作系统自动将文件被修改的数据写回磁盘

4.1_1 初识文件管理

4.1_2 文件的逻辑结构

• 可变长：无法随机存取

• 定长：可以随机存取，采用串结构，无法快速找到关键字；采用顺序结构，可以快速查找关键字，不好添加或删除记录

4.1_3 文件目录

• 单级目录结构
整个系统一张表，所以不允许文件重名

• 两级目录结构
允许不同用户的文件重名，不允许用户对文件分类
主文件目录（MFD）+用户文件目录（UFD）

• 多级目录结构（树形目录结构）
不同目录下可以重名
当代操作系统采用方法、不便于文件共享
使用相对路径可以减少磁盘I/O的次数

• 无环图目录结构
可以共享
目录成为有向无环图
需要设置共享计数器，当一个用户删除结点，结点的计数器减一，当计数器归零时才删除结点
文件数据变化对所有用户可见

4.1_4 文件的物理结构（文件分配方式）

• 隐式分配：采用链接分配方式的文件，只支持顺序访问，不支持随机访问，因为读完上一个块才知道下一个块的地址；方便拓展，没有碎片
目录记录起始块号和结束块号

• 显示分配：文件分配表FAT显式记录下一块物理块的位置，方便拓展，无外部碎片，支持随机访问（可以直接查表，只要不用访问之前的文件块就算支持随机访问！😆），文件表会占内存空间
目录记录起始块号

• 链接方案 文件很大时，索引表很长，如果要找第i号索引块必须把之前的索引块都读入，导致磁盘I/O过多，效率低下

• 多层索引（类似多级页表） 即使是小文件也需要查多级，多次

• 混合索引

4.1_5 文件存储空间管理

• 文件卷（逻辑卷）的概念

• 目录区与文件区

• 空闲表法：首位置+长度，分配算法和分配内存块相似，回收和动态分区分配很类似，因此回收时也要注意表项合并

• 空闲链表法（空闲盘块链、空闲盘区链）



空闲盘块链：系统保存链头链尾指针，回收的盘块放链尾
空闲盘区链：和动态分区分配很类似，回收注意合并

• 位示图法 分配时顺序扫描位示图，分配掉的块设为1，回收时设回0 连续，离散分配都适用

• 成组链接法：文件卷的目录区中专门用一个磁盘块作为超级块，当系统启动时需要将超级内存块读入内存。并且保证内存与外存中的超级块数据一致。



分配：
例如要100个块，就先分配超级块的201-299出去，然后把300号的内容复制到超级块，再分配300号出去，没爆就正常分配
回收：
例如回收100个块，先回收99个，然后创建一个新的超级块，空闲盘数设为1，空闲块号指向回收了99个块已经收满了的那个块

4.1_6 文件的基本操作

4.1_7 文件共享

4.1_8 文件保护

4.1_9 文件系统的层次结构

4.1_10虚拟文件系统

5.1_1 I-O设备的概念和分类

5.1_2 I-O控制器

5.1_3 I-O控制方式

5.1_4 I-O软件层次结构

5.1_5 I-O核心子系统

5.1_6 假脱机技术

• 输入井和输出井

• 输入进程和输出进程

• 输入缓冲区和输出缓冲区

5.1_7 设备的分配与回收

5.1_8 缓冲区管理

5.2_1 磁盘的结构

5.2_2 磁盘调度算法

• 寻找时间Ts=s+m*n

• 延迟时间Tr=1/(2r)

• 传输时间Tt=b/(rN)

• 先来先服务（FCFS）

• 最短寻找时间优先（SSTF）

• 扫描算法（SCAN）

• 循环扫描算法（C-SCAN）

5.2_3 减小磁盘延迟时间的方法

5.2_4 磁盘的管理

本笔记是基于littlexi0的笔记的完善&修正