导图社区 操作系统
- 54
- 5
- 2
- 举报
操作系统
包含最新考研408操作系统全部知识点，图片均为手绘可通过平板进行修改，包括:1.计算机系统概述、2.进程管理、3.内存管理.、4.文件管理、5. i/o设备等内容。
编辑于2023-01-14 14:27:59 云南- 相似推荐
- 大纲
操作系统
1. 计算机系统概述
1. 操作系统概念
计算机由下至上，硬件，操作系统，应用程序，用户 (计组是划分为软件系统和硬件系统)
操作系统是计算机系统最基本的软件，管理着各种资源，并组织，调度计算机工作
操作系统的特性
并发（交替）
多任务操作系统：多进程并发运行
区分并行（同一时刻）
共享
互斥访问和(宏观)同时访问
最基本
虚拟
空分复用（虚拟存储器）
时分复用（虚拟处理器）
异步
并发引起进程的走走停停
目标和功能
负责管理：2-4章标题
提供接口：命令接口(分/实时交互式和批处理) 程序接口(系统调用，如GUI图形接口)
2. 操作系统发展与分类
2.
手工操作阶段(无操作系统)
批处理阶段(单道)
多道批处理
除非，一道程序有I/O请求时，会挂起当前进程去执行其他进程。 否则，直到程序整个完成，才会去执行其他程序。
采用多道程序设计形成多道批处理OS，提高资源利用率
引入中断，设备与处理器之间并行，无人机交互性
分时操作系统
切时间片，实现人机交互
实时操作系统
及时性和可靠性，允许紧急情况
限制时间内完成
6.网络操作系统和分布式 7.个人计算机操作系统
3. 操作系统运行环境
运行机制
概念：内核程序/特权指令/内核态/核心态/管态、应用程序/非特权指令/用户态/目态
内核态→用户态：执行一条特权指令，修改PSW标志为用户态
用户态→内核态：由中断引起硬件自动完成
内核实现：时钟管理、中断机制、原语（实质是关闭中段）、系统数据结构管理
中断和异常/内中断
中断：来自CPU外部，和CPU执行指令无关，如时钟中断/分时操作系统
异常：源自CPU指令内部的事件
陷阱、陷入
陷入指令（请求内核服务，不是特权指令）引起，是应用程序故意引起
故障
可能被内核修复的错误，修复好又归还CPU到程序，如：缺页、算术溢出
终止
内核不可修复的错误，直接终止程序，不再归还，如非法特权指令
中断处理：详见计组
系统调用（广义指令）
用户可通过陷入(也叫访管/trap)来发起系统调用
设备管理、文件管理、进程控制、进程通信、内存管理
1、传递系统调用参数(系统调用需要的参数放到通用寄存器) 2、执行陷入指令(用户态，引发内中断，硬件修改标志位) 3、执行相应的内核请求和程序处理系统调用(核心态) 恢复现场和中断返回
4. 操作系统体系结构
大内核(大部分模块由OS管理)优点：高性能；缺点：内核代码庞大，结构混乱，难以维护 微内核(部分基本模块由OS管理)优点：内核功能少，结构清晰，方便维护；缺点：性能低
5. 操作系统的引导
6. 虚拟机
2. 进程管理
1. 进程与线程
相关概念
进程映像 进程实体
PCB
1.进程描述信息
PID进程标识符、UID用户标识符
2.进程控制和管理信息
CPU、磁盘、网络流量 当前状态：就绪、阻塞、运行
3.资源分配清单
使用那些文件、内存区域、I/O设备
4.处理机相关信息
如PSW、PC等各种寄存器的值（方便实现进程切换）
注意：进程被调入内存时，系统为之创建一个PCB
程序段
程序指令
相关数据段
运行过程中产生的各种数据
作业
用户给操作系统的任务，可能有一个或多个进程来完成
进程是资源分配的最小单位
进程的特征
动态性
动态性是最基本的特征，是程序的一次执行过程
并发性
内存中有多个进程实体，各进程了并发执行
独立性
独立接受资源，运行，接受调度的基本单位
异步性
以不可预知的速度向前推进(所以需要引入同步机制)
结构性
结构上看，进程由程序段、数据段、PCB组成
进程的状态
五状态
运行
就绪
阻塞
三种基本状态
创建
结束
七状态
添加了就绪挂起和阻塞挂起
注意：一个进程从运行态到阻塞态是主动的行为
进程控制
进程创建（创建原语）
申请PCB、分配资源、初始化PCB、插入就绪队列
进程终止（撤销原语）
终止PCB，剥夺CPU，终止子进程，归还资源，删除PCB
进程的阻塞和唤醒（阻塞和唤醒原语）
阻塞原语
找到PCB，保护运行现场，PCB状态信息设为阻塞态，将PCB插入相应等待队列
唤醒原语
等待进程中找到PCB，将PCB移除等待队列设为就绪态，PCB插入就绪队列，等待被调度
进程切换（切换原语）
将运行环境信息存入PCB，PCB移入相应队列，选择另一个进程执行并更新PCB，根据PCB恢复新进程所需的运行环境
进程通信IPC
共享存储
低级共享（基于数据结构的共享）
高级共享（基于存储区的共享）
操作系统只负责提供存储空间和同步互斥工具
消息传递
进程通过发送消息和接受消息两个原语进行数据交换，无共享空间
直接通信方式
进程之间直接进行通信，将消息放到缓冲队列上
间接通信方式（信箱通信方式），《计网》中电子邮件系统
管道通信
半双工通信：某一时刻只能单向传输
先进先出循环队列 管道写满写进程阻塞 管道读空读进程阻塞 一个管道允许多个写进程，一个读进程
线程
引入目的
为了更好的使多道程序并行开发，提高吞吐率和资源利用率
特点
是程序执行最小单元，是一个轻型实体，线程不拥有系统资源
同一进程的多个线程并发执行，共享进程拥有的全部资源
线程也有就绪、阻塞、运行三种基本状态
实现方式
用户级线程
用户通过线程库设计多线程程序
内核级线程
TCB线程控制块
线程标识符、程序计数器PC、其他寄存器、栈指针、运行状态、优先级
包含在PCB中
工作通通由内核完成
当一个进程中的一个线程被阻塞，内核可以调度该进程中的其他线程占用处理机
线程的切换，在核心态下完成
内核级线程才是CPU分配的最小单位
多线程模型
多对一模型
效率高但是容易阻塞
当一个进程中的一个线程被阻塞，不仅该线程被阻塞，而且进程内的所有线程都被阻塞
一对一模型
并发强但是开销大
多对多模型
集两者长处
一个用户级线程被阻塞使对应内核级线程被阻塞，但可以调用另一个内核级线程执行
2. 处理机调度
调度的层次
作业调度（高级调度）
作业调入内存，建立pcb
内存调度(中级调度)
将暂时不能运行的进程调入外存等待（挂起态）
进程调度（低级调度）
从就绪里选进程分配处理机
调度器/调度程序
不能调度的情况：处理中断/操作系统内核临界区/原子操作
临界资源：一个时间段内只允许一个进程使用的资源，各进程需要互斥的访问临界资源。 临界区：访问临界资源的那段代码。
通用调度的时机
创建新进程
进程退出
运行进程阻塞
I/O中断发生
非抢占式：只有运行进程阻塞或退出时 抢占式 ：每个时钟中断或每k个时钟中断
调度的方式
广义 进程调度+进程切换
狭义 就绪队列选出要运行的进程
非剥夺调度方式（非抢占式），批处理使用
只允许进程主动放弃处理机，在运行过程中即使有更紧急的任务到达，当前进程依然会使继续使用处理机，直到该进程中止或主动要求进入阻塞态。
无时间片
剥夺调度方式（抢占式）
当一个进程正在处理机上执行时，如果有一个更重要或更紧急的进程，需要使用处理机及立即暂停，正在执行的进程将处理机分配给更紧急的那个进程。
调度的准则
cpu利用率
忙碌时间/总时间
系统吞吐量
总共完成多少道作业/总共花了多少时间
周转时间
作业完成时间-作业提交时间
平均周转时间
各作业周转时间之和/作业数
带权周转时间
作业周转时间/作业实际运行时间
平均带权周转时间
各作业带权周转时间之和/作业数
等待时间
进程等待时间
进程建立到完成之间的的空闲等待时间
作业等待时间
进程等待时间+在外存后备队列排队时间
注意：衡量一个算法通常只需要考察等待时间
响应时间
提出请求到响应的时间
调度算法
先来先服务FCFS
公平，不会饥饿，非抢占，对长友好，对短不友好
短作业优先调度算法 (SJF,short job first)
饥饿，只对短友好,平均等待时间，平均周转时间最少
抢占式从就绪队列中选择剩余时间最短的上处理机运行
高响应比优先算法
响应比=(等待时间+要求服务时间)/要求服务时间 每次调度前先计算响应比，选择高的调度
不会饥饿
时间片轮转调度算法
抢占式，时间片到期，不会饥饿
人机交互
循环队列存储就绪队列
抢占式
非抢占式
优先级调度算法
1、系统进程优先级＞用户 2、前台＞后台 3、i/o进程更高
多级反馈队列调度算法（融合前几种优点）
抢占，会导致饥饿
3. 进程同步
基本概念
临界资源
只允许一个进程使用的资源
进入区
临界区(指访问临界资源的代码)
退出区
剩余区
同步
直接制约关系
先V后P
互斥
间接制约关系
先P后V
准则
空闲让进
空闲立即进入
忙则等待
已有进程进入则等待
有限等待
有限时间内进入
让权等待
不能进入就释放处理器
不是必要条件
互斥软件实现 均不能让权等待
单标志法
不能空闲让进
int turn=0;//true表示当前允许进入临界区的进程号“谦让”
P0进程： P1进程： while(turn !=0); while(turn !=1); //进入区 critical section; critical section; //临界区 turn=1; turn=0; //退出区 remainder section; remainder section; //剩余区
不遵循“空闲让进”原则
双标志先检查法
可能违背忙则等待原则(临界区有进程访问，但还是可能两个进程同时访问)
bool flag[2]; //表示进入临界区一元的数组 flag[0]=false; flag[1]=false;//刚开始设置为两个进程都不想进入临界区
P0进程： P1进程： while(flag[1]);① while(falg[0]);② //如果此时P0想进入临界区，P1就一直循环等待 flag[0]=true; ③ flag[1]=true; ④ //标志为P1进程想要进入临界区 critical section; critical section; //访问临界区 flag[0]=false; flag[1]=false; //访问完临界区，修改标志为P1不想使用临界区 remaindersection; remainder section;
不遵循“忙则等待”原则
双标志法后检查
两个进程可能都进不去，不遵循有限等待（饥饿）
bool falg[2]; //表示进入临界区意愿的数组 flag[0]=false; // flag[1]=false; //刚开始设置为两个进程都不想进入临界区
P0进程： P1进程： flag[0]=true;① falg[1]=true;② //表示P1进程想要进入临界区 while(flag[1]);③ while(falg[0]);④ //表示P0也想进入临界区，则P1循环等待 critical section; critical section; //访问临界区 flag[0]=false; flag[1]=false; //访问完临界区，修改标志为P1不想使用临界区 remaindersection; remainder section;
不遵循“空闲让进、有限等待”原则，可能导致“饥饿”
Peterson算法
相比较前三种最好，谁最后客气谁就后用，不遵循让权等待，会发生忙等
bool falg[2]; //表示进入临界区意愿的数组，初始化都为false‘表达意愿’ int turn=0; //turn表示优先让哪个进程进入临界区‘谦让’
P0进程： P1进程： flag[0]=true;① flag[1]=true;② //表示自己想要进入临界区 turn=1;③ turn=0;④ //可以优先让对方进入临界区 while(flag[1]&&turn==1);⑤ while(flag[0]&&turn==0);⑥ //对方想进，且最后一次是自己“让梨”，那么自己就循环等待 critical section; critical section; flag[0]=false; flag[1]=false; //访问完临界区，表示自己已经不想访问临界区 remainder section; remainder section;
不遵循“让权等待”原则，会出现“忙等”
互斥硬件实现方法
中断屏蔽方法
不适用多核处理器（多处理机）、只适用操作系统内核
关中断只对执行关中断的处理机有效
硬件指令方法(由硬件完成，代码只是逻辑表示)
TestAndSet指令(TS指令)，原子操作 (单标志检查法一气呵成)
//布尔型变量lock表示当前临界区是否被加锁 //true表示已加锁，false表示未加锁 bool TestAndSet(bool *lock){ bool old; old = *lock;//old用来存放lock原有的值 *lock =true;//无论之前是否加锁，都将lock设置为true，上锁 return old; //返回lock原来的值 }
硬件完成的，这个TSL逻辑 //以下是使用TSL指令实现互斥的算法逻辑 while(TesrAndSet(&lock)); //“上锁”并“检查” 临界区代码段... lock = false; //"解锁"
Swap指令
//Swap指令的作用是交换两个变量的值 Swap(bool a,bool *b){ bool temp; temp =*a; *a=*b; *b=temp; }
//一下是用Swap指令实现互斥的算法逻辑 //lock表示当前临界区是否被加锁 bool old=true; while(old==true) Swap(&lock,&old); 临界区代码段... lock =false; 剩余区代码段...
信号量解决同步互斥
Wait()(P减操作)和signal()(V加操作)
整型信号量
不遵循让权等待
int S=1;//初始化信号量S，表示当前系统中可用的资源数量
void wait(int S)｛//wait 原语，相当于“进入区” while(S＜＝0);//如果资源不够，就一直循环等待“忙等” S=S-1;//如果资源够，则占用一个资源 ｝
void signal(int S){//signal 原语，相当于“退出区” S=S+1;//使用完资源后，在退出区释放资源 }
记录型信号量(semaphore)
常用，资源数+进程链表
数据结构： typedef struct { int value;//剩余资源数 struct process *L;//等待队列 }semphore;
进程使用资源： void wait (semaphore S){ S.value--; if(S.vlue<0){ block(S.L);//资源用完，阻塞挂起 } }
进程释放资源： void signal(semaphore S){ S.value++; if(S.value<=0){ wakeup(S.L);//唤醒等待队列阻塞→就绪 } }
同步(先V后P)
semaphore S=0;//初始化同步信号量，初始为0 P1(){ P2(){ 代码1； P(S); 执行顺序：1、2~4~ 代码2； 代码4； V(S); 代码5； 代码3； 代码6； } ｝
互斥(先P后V)
semaphore mutex=1;//初始化同步信号量，初始为1 P1(){ P(mutex); //使用临界资源前需要加锁 临界区代码段...； V(mutex)； //使用临界资源后需解锁 }
管程
封装共享资源，自动实现互斥
管程组成：1.名称，2.数据结构说明，3.操作的过程(函数)，4.初始化语句
基本特征
各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据
每次仅允许一个进程在管程内执行某个内部过程
管程实现生产者消费者问题
monitor ProducerConsumer condition full, empty; //条件变量用来实现同步(排队) //full是生产者队列，empty是消费者队列 int count=0; //缓冲区中的产品数 void insert(Ttem item){//把产品item放入缓冲区 if (count = N) //当产品满了 full.wait (); //进程直接放入full队列 count++; insert_item (item); if (count ＝ 1) //说明有消费者被阻塞 empty.signal(); //从empty队列唤醒 } Item remove(){ //从缓冲区中取出一个产品 if (count = 0) //当没有产品 empty.wait(); //进程阻塞到empty队列 count--; if (count = N-1) //说明有生产者被阻塞 full.signal(); //从full队列唤醒 return remove_item(); } end monitor;
//生产者 Producer(){ while(1){ item=生产一个产品; ProducerConsumer.insert(item); } } //消费者 consumer()｛ while(1){ item=ProdecerConsumer.remove(); 消费一个产品item; } }
经典同步问题
生产者--消费者问题
特点:多对多，共享资源为n
semaphore mutex=1;//互斥信号量，实现对缓冲区的互斥访问 semaphore empty=n;//同步信号量，表示空闲缓冲区的数量 semaphore full=0;//同步信号量，表示产品数量，也即非空缓冲区的数量
producer(){ while(1){ 生产一个产品； P(empty);//消耗一个空闲缓冲区 P(mutex);//临界区互斥 把产品放入缓冲区； V(mutex); V(full);//增加一个产品 } }
consumer(){ while(1){ P(full);//消耗一个产品(非空缓冲区) P(mutex);//临界区互斥 从缓冲区取出一个产品； V(mutex); V(empty);//增加一个空闲缓冲区 使用产品； } }
多生产者--多消费者问题
semphore apple=0;//盘子中有几个苹果 semphore orange=0;//盘子中有几个橘子 semphore plate=1;//盘子中还可以放多少个水果 //semaphore mutex=1;//实现互斥访问盘子（缓冲区）
dad(){ while(1){ 准备一个苹果； P(plate);//检查盘子是否可以放水果 // P(mutex); 把苹果放入盘子; //V(mutex); V(apple);//向盘子中放入苹果 } }
mom(){ while(1){ 准备一个橘子； P(plate);//检查盘子是否可以放水果 // P(mutex); 把橘子放入盘子； // V(mutex); V(orange);//向盘子中放入橘子 } }
daughter(){ while(1){ P(apple);//检查是否有苹果 // P(mutex); 从盘子中取出苹果； // V(mutex); V(plate);//释放盘子位置，告诉父母盘子空了 吃掉苹果； } }
son(){ while(1){ P(orange);//检查是否有橘子 // P(mutex); 从盘子中取出橘子； // V(mutex); V(plate);//释放盘子位置，告诉父母盘子空了 吃掉橘子； } }
缓冲区大小只为1时，一般不用互斥
吸烟者问题
特点：一对多，轮流生产
同步：从事件角度分析 桌上有组合1→第1个抽烟者取走 桌上有组合2→第2个抽烟者取走 桌上有组合3→第3个抽烟者取走 发出完成信号→只有抽烟者抽完了，供应者才继续提供
semaphore offer1=0;//桌上组合一的数量 semaphore offer2=0;//桌上组合二的数量 semaphore offer3=0;//桌上组合三的数量 semaphore finish=0;//抽烟是否完成
provider(){ while(1){ if(i==0){ 将组合一放桌上； V(offer1);//通知吸烟者 }else if(i==1){ 将组合二放桌上； V(offer2); }else if(i==2){ 将组合三放桌上； V(offer3); } i=(i+1)%3; P(finish);//阻塞等待吸烟者发出吸烟完成信号 } }
smoker1(){ while(1){ P(offer1);//检查是否有组合一 从桌上拿走组合一；卷烟；抽掉 V(finish);//发出完成吸烟信号 } }
smoker1(){ while(1){ P(offer2);//检查是否有组合二 从桌上拿走组合二；卷烟；抽掉 V(finish);//发出完成吸烟信号 } }
smoker1(){ while(1){ P(offer3);//检查是否有组合三 从桌上拿走组合三；卷烟；抽掉 V(finish);//发出完成吸烟信号 } }
读者--写者问题
特点：一对多，读写互斥
①允许多个读者同时对文件进行读取操作 ②只允许一个写者进程往文件中写信息 ③任一写者在完成写操作之前不允许其他读者或写者工作 ④写者执行写操作前，应让已有的读者和写者全部退出 两类进程：写进程、读进程 互斥关系：写进程一写进程、写进程一读进程。读进程与读进程不存在互斥关系
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);//第一个读进程，读之前负责“加锁”，不让写 count++;//访问文件进程数+1 V(mutex); V(w); 读文件... P(mutex);//各读进程负责互斥访问count count--;//访问文件的读进程数-1 if(count==0) V(rw); //最后一个读进程负责，读完了“解锁” V(mutex); } }
哲学家就餐问题
特点：多对多，互相干扰
semaphore chopstick[5]={1,1,1,1,1}; Pi(){ //i号哲学家 while(1){ P(chopstick[i]); //拿左 P(chopstick[(i+1)%5]); //拿右 吃饭... V(choipstick[i]); //放左 V(chopstick[(i+1)%5]); //放右 思考... } }
死锁避免 解决办法
1. 最多有四个哲学家同时进餐
semaphore chopstick[5]={1,1,1,1,1}; semaphore max＝4；//最多进餐人数 Pi(){ //i号哲学家 while(1){ P（max); P(chopstick[i]); //拿左 P(chopstick[(i+1)%5]); //拿右 V(max); 吃饭... V(choipstick[i]); //放左 V(chopstick[(i+1)%5]); //放右 思考... } }
2. 奇、偶号哲学家分别首先只能拿他们左边、右边的筷子
3. 仅仅当一个哲学家左右两只筷子都可以使用才允许抓起筷子(破坏请求并保持)
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(choipstick[i]); //放左 V(chopstick[(i+1)%5]); //放右 思考... } }
根据前驱图可以知道PV操作的前后关系 V操作是在P之前,一般V操作在该进程末尾
4. 死锁
死锁产生的原因
系统资源的竞争
进程推进顺序非法
必要条件：1、互斥，2、不可剥夺，3、请求并保持，4、循环等待(一个资源存在循环等待链)
注意：发生死锁时一定有循环等待，但是发生循环等待时未必发生死锁
死锁处理策略
死锁预防
破坏四个必要条件其中一个： 破坏互斥：将临界资源改为可共享资源(spooling技术) 破坏不剥夺：1、申请资源得不到满足，立即释放2、申请资源被占用，操作系统协助剥夺 破坏请求并保持：预先静态资源分配(该进程在运行前一次申请完他所需要的全部资源) 破坏循环等待：为资源编号，只能递增或递减顺序请求资源，剪断了一个方向上的请求链
死锁避免
银行家算法(基于安全状态)
安全状态一定不会发生死锁，不安全状态可能发生死锁。
在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，从而决定是否答应资源分配请求
不安全状态：如果分配了资源后，系统中找不到任何一个安全系列(顺利执行结束的序列)，系统就进入了不安全状态
死锁检测和解除
死锁定理：当且仅当资源分配图不可完全简化时才可能死锁
死锁检测：运用死锁定理检测系统是否处于死锁状态
死锁解除：1、资源剥夺2、撤销进程(终止进程法)3、进程回退
资源分配图
分配边：表示已经分配的资源 请求编：表是正在请求的资源
依次消除与不阻塞进程相连的边，直到无边可消
3. 内存管理
1. 内存管理基本概念
程序变为程序步骤
编译
编译程序将用户源代码编译称若干目标模块
链接
将编译后的目标模块和库函数链接，形成装入模块
装入
将装入模块装入内存
程序链接方式
静态链接
运行之前将各模块和函数连接成一个可执行文件后完整装入内存
装入时动态链接
边装入边链接
运行时动态链接
执行时需要哪个模块装入哪个模块
装入的方式
绝对装入
编译时产生地址(逻辑地址=物理地址)；只适用单道程序
可重定位装入（静态重定位）
重定位：装入时对目标程序和（地址）数据的修改
装入时将逻辑地址转化为物理地址
用于早期的多道批处理操作系统
直接生成物理地址
运行时装入（动态重定位）
需要重定位寄存器支持，适用于虚拟地址
运行时将逻辑地址转化为物理地址，需要重定位寄存器
只有逻辑地址，配合基地址寄存器（重定位寄存器）
内存保护
cpu设置上下限寄存器
存放用户作业在内存的上下限地址
重定位寄存器（基址寄存器）+界地址寄存器（限长寄存器）
*覆盖与交换* *大纲已移除*
覆盖
固定区+若干覆盖区
固定期存放必须被调用的模块，覆盖区预留给可能被调用的模块
对用户不透明，增加编程负担，适合单道程序
交换(与磁盘)
PCB常驻内存
中级调度技术就是交换技术
磁盘分为
对换区（进程数据、连续分配）
文件区（离散分配、主要存放文件）
对比
注意：交换技术只在不同进程或者作业之间进行，而覆盖技术用于同一个程序或进程中
2. 连续分配管理方式 (分配连续内存)
单一连续分配 (独占)
系统区（系统区仅供操作系统使用，通常在低地址部分）
用户区
一整个用户区
注： 只能用于单用户，单任务，无外部碎片，有内部碎片，存储器利用率极低
固定分区分配
分区大小相等
缺乏灵活性，适用于控制各个相同对象
每个内存块大小相同
大小不等
配有分区说明表
不同大小的内存块都有
一个分区只能放一个程序
注：有内部碎片，无外部碎片，支持多道程序，每个分区只能装一个作业
内部碎片：分配给某个进程，它没有用上。
外部碎片：空闲分区太小，难以利用。
空闲分区表、空闲分区链：内存分区说明。
动态分区分配
注意：支持多道程序，在进程装入内存时，根据进程大小动态建立分区
无内部碎片，有外部碎片(可用紧凑技术解决)
内存分配的算法(从空闲分区表、空闲分区链中选择)
首次适应算法
性能最好，算法开销最小
最佳适应算法
容量递增排序
最坏适应算法（最大适应算法）
容量递减排序
分区链动态排序
临近适应算法（循环首次适应算法）
从上次分配的位置向后循环检索(循环链表)
3. 非连续分配管理方式
基本分页存储管理方式
术语
进程逻辑地址分块称为页/页面，编号称为页号。 内存物理地址分块称为页框/页帧/内存块/物理块，编号称为页框号/页帧号/内存块号/物理页号。 外存物理地址分块称为块。
内存块号大小由内存大小与块大小决定
逻辑地址结构
页号 | 页内偏移
页号是对虚拟地址分的页
页表
一个进程对应一张页表，进程的每个页面对应一个页表项，页表项＝页号＋内存块号，每个页表项长度相同，页号隐含
一个页表要能覆盖整个内存，则可能需要多级页表，层数取决于块大小和内存大小
顶级页表常驻内存，其他不用
i号页表项地址＝页表基地址＋内存块号大小×i
方式
基本地址变换机构
硬件完成，设置页表寄存器
页号=逻辑地址/页面长度（整数）
页内偏移量=逻辑地址%页面长度（余数）
具有快表的地址变换机构 快表：相联存储器(TLB)
注意：做题要看快表是同时查找还是先后查找
若出现缺页，调用顺序：快表、访问内存页表、中断处理、访问快表、合成物理地址访问主存
1、对于切换进程，TLB表要么是flash，要么是在页表项中加入进程的唯一标识符，防止不同进程调用相同内存 2、对于多级页表，TLB表中地址标记不进行拆分
TLB表项＝页号＋内存块号
由于页号每个进程都是独立的，当前进程的页号对下一个进程无效
多级页表
解决的问题：页表必须连续存放，当页表很大时，需要占用很多个连续的页框
将必须连续的列表再进行分页
一级页表(查到地址后，查快表，未命中再查内存);
二级页表是否与一级页表共享TLB表还未知
TLB存储的页号和内存块号只对当前调用的内存块管用，换了页表数据就失效。
第1个目录表称为：页目录表，外层页表，顶级页表
两级页表
一级页号 | 二级页号 | 页内偏移量
注意：n级页表需要n+1次访存，顶级页表不超过一个页面
一级页表和二级页表
基本分段存储管理方式
分段例如：主程序、堆栈、符号表、子程序、函数、变量等
地址结构
段号 | 段内偏移
段表
一个进程对应一张段表，每一个段对应一个段表项，段表项由段号、段长、基址组成，段号隐含
段长不同，多一次检查，方便用户编程、信息保护与共享，段内要求连续，段间不要求
段表
段页式管理方式
地址格式：段号+页号+页内偏移量（段内地址经硬件自动拆分为页号+页内偏移量）
一个进程段表只有一个，页表可能有多个
区别
页
对用户不可见，地址空间一维，页面不是按逻辑块分块，难以实现共享，不方便逻辑管理，有内部碎片(无外部)
段
对用户可见，地址空间2维，（纯代码或可重入代码可共享，可修改代码不能共享），容易实现信息共享，两次判断是否越界
段页式
地址2维
共享（纯代码或可重入代码）
页：不方便 段：方便，共享段表项
注意：做题时无论采用哪种方式，都需要检查页面/段是否越界
段页表
4. 虚拟内存
传统存储管理方式特征
一次性
一次性装入后才开始运行
驻留性
一直驻留在内存，直到运行结束
局部性原理
时间局部性
空间局部性
高速缓存技术
虚拟存储器的特征
多次性
允许作业分多次调入内存
对换性
作业无需常驻内存
虚拟性
逻辑上扩充内存
虚拟页号是对整个文件数据的页编号，实际页号通过页表项映射
虚拟地址空间
每一个进程看待内存都有一个统一的视角，内存的分布井然有序 为进程分配的一个概念上的空间
虚拟存储容量
最大容量
CPU寻址范围
决定虚拟地址寻址的大小，与内存大小无关
实际容量
min（内存和外存容量之和，CPU寻址范围）
为什么虚拟地址由CPU地址位数决定？
与实际的物理地址无关，只与地址位数有关
只需要有一级页表在内存中
虚拟内存实现的三种方式
请求分页存储管理
请求分段存储管理
请求段页式存储管理
请求分页管理方式
功能
请求换页功能
页面置换功能
机制
页表机制
页表项：虚拟页号 + 物理块号 + 状态位P + 访问字段A+修改位M +外存地址 (内存中位置)(是否已调入)(访问次数)(是否被修改)
虚拟页号/物理块号
虚拟页号：和基本分页存储管理中的页号，其本质是一样的
物理块号：和基本分页存储管理中的内存块号，其本质是一样的
访问次数：供置换算法选择换出页时参考
虚拟页号：类比分页存储的页号，但这里的页号并不是它的内存块号
与基本表区别
页表项比基本页表新增加四个字段 修改位写指令才修改，一般只修改快表数据，将快表项删除时才写回慢表
慢表：存储在内存中的页表
缺页中断机制(内中断)
找到页表项后检查页面是否在内存，若没在内存，产生缺页中断
缺页中断处理后，需要将目标页面调入内存，有必要时还需换出页面
缺页中断完成后，继续执行产生缺页中断的代码，此时还会重新查一次页表项(TLB表中已经装入)
缺页中断属于内中断，属于内中断的故障，即可能被系统修复的异常
一条指令在执行过程中可能产生多次缺页中断
地址变换机制
找到页表项时需要检查页面是否在内存中
若页面不在内存中，需要请求调页
若内存空间不够，还需要换出页面
页面调入内存后，需要修改相应的页表项
注意：为了实现请求分页，系统必须提供一定的硬件支持
页面置换算法
最佳置换算法OPT
理想化算法(无法实现)，缺页中断不一定会页面置换
最长时间内不再被访问页面的页面换出(向后找)
先进先出页面置换算法FIFO
算法性能差，会出现Belady异常，物理块增加，缺页故障不减反增
最近最久未使用算法LRU
向前找，性能最接近opt，硬件支持
时钟置换算法CLOCK
形成的循环队列和初始指针是根据调入时间顺序确定。
访问时：某页被访问时，访问位设为1 淘汰时：循环扫描各页面，访问位为1的设为0，淘汰访问位＝0的
最多两轮循环
改进型时钟置换算法
若用（访问位，修改位）的形式表述，则 第一轮：淘汰（0，0），不修改任何标志位 第二轮：淘汰（0，1），并将扫描过的所有页面访问位改为0 第三轮：淘汰（0，0），不修改任何标志位 第四轮：淘汰（0，1），不修改任何标志位
优先淘汰未被修改的页面，最多四轮扫描
页面分配策略
驻留集
内存中给一个进程分配的物理块的数目
页面分配、置换策略
固定分配全局置换
×
固定分配局部置换
驻留集大小不变，只能用自己的物理块置换
可变分配全局置换
只要缺页就分配，全部物理块（除锁定的页面）都可以用。
可变分配局部置换
根据缺页的频率动态增加或者减少进程物理块，如果频率低，就从自己的驻留集中换入换出
固定分配：操作系统为每个进行分配一组固定的物理块，在进程运行期间无再改变
可变分配：先为每个进程分配一定的物理块，在运行期间可根据情况做适当的增加或减少
全局置换：可以用不是自己的物理块。
局部置换：只能选择自己的物理块进行置换。
调入页面的时机
预调页策略
根据局部性原理，对下次调页进行预测，主要用于进程的首次调入，成功率为50％左右
请求调页策略
进程运行时，发现缺页再调入
从何处调入
对换区：采用连续存储方式，速度更快 文件区：采用离散存储方式，速度更慢
对换区足够大：运行前将数据从文件区复制到对换区，调入、调出都是在内存与对换区之间进行
对换区不够大：不会修改的数据每次从文件区调入，不用调出； 会修改的数据调出到对换区，以后需要时再从对换区调入
unix方式：第一次使用的文件都从文件区调入；调出的文件都写回对换区，再次使用时从对换区调入
抖动（颠簸）现象
页面频换换入换出的现象，驻留集太小
工作集
该时刻前某各窗口大小里，进程实际访问页面的集合，驻留集大小一般不能小于工作集大小
内存映射文件
操作系统将文件映射到该进程页表的虚拟地址空间中，访问文件时通过页表调页实现
方便实现文件数据的共享
4. 文件管理
1. 文件系统基础
1. 文件系统由： 1有关软件 2被管文件 3数据结构 组成
文件定义
硬盘为载体存储在计算机的信息集合，用户IO操作基本单位
文件属性
名称
标识符(供操作系统区分文件)
类型
位置
大小
保护
时间，日期和用户标识
文件的基本操作
创建文件create
分配外存空间，创建目录项
删除文件delete
回收外存空间，删除目录下
打开文件open
1、打开文件对应的目录项，检查该用户是否有指定操作权限
2、将目录项复制到内存中该用户进程的“打开文件表”，之后用户使用他的打开文件表的编号操作文件
同时系统中也有一份系统的打开文件表，有打开计数器
系统打开文件表
编号 | 文件名 | 外存地址 | 打开计数器
用户进程打开文件表
编号(文件描述符) | 文件名 | 读写指针 | 访问权限 | 系统索引号
读者指针记录该进程对文件读者操作进行到的位置
读read
指定进程打开文件表的编号
数据不在内存时会产生缺页中断，等数据调入内存，返回结果给read()后才继续向下执行代码
根据读指针指向的外存中，将用户指定大小的数据读取到指定内存区域
由操作系统将逻辑地址转换为物理地址
写write
根据写指针、写出数据量、内存位置将文件数据从内存写出外存
关闭close
删除进程的打开文件表相应表项
回收分配给该文件的内存空间等资源
系统打开文件表计数器减一，当为0时删除系统打开文件表项
文件逻辑结构 (研究文件逻辑结构)
无结构文件(流式文件)
有结构文件(记录式文件)
顺序文件
名词解释
顺序结构
按关键字顺序排列
串结构
与关键字无关，按存入时间先后顺序排列
顺序存储
可变长记录
无法实现随机存储，每次只能从第一个记录开始再往后查找
定长记录
可实现随机存取，记录长度为L，则第i个记录存放的相对位置是i*L
若采用串结构，无法快速找到某个关键字对应的记录
若采用顺序结构，可以快速找到某关键字对应的记录
链式存储
无论是定长、可变长记录都无法实现随机存取，每次只能从第1个记录开始，依次往后查找
索引文件
建立索引表(索引表是定长顺序文件)，一个索引项就是一条定长记录，支持随机存取
若索引表按关键字顺序排序，则可支持快速检索
索引顺序文件
前两种结合。分组，组内用顺序文件，每组对应一个索引项。组内可无序，组间必须有序
索引表 组内 A → AQ AE B → BU BI C → CR CJ
实现方法
将索引表数据和逻辑文件数据有结构的放在同一文件的特定位置
直接文件或散列(hash)文件
没有顺序的特性
目录结构
文件控制块(FCB)
实现“按名存储”系统创建一个新文件，就会分配一个FCB并存放到文件目录中，成为目录项，open操作调入目录项FCB。PS：FCB必须连续存放
文件目录：FCB（目录项）的有序集合
FCB：文件名 | 物理地址 | 类型 | 存取权限 ... 等 目录/txt
目录也是文件，目录的FCB中物理地址又指向下一级目录文件或文件
目录结构
单级目录结构
整个系统只建立一张目录表，文件不允许重名
两级目录结构
多用户，用户间文件可重名，不能对文件分类
多级目录结构
便于实现文件分类
绝对路径：从根目录出发进行查询 相对路径：当前目录的引入减少磁盘访问次数
不便于 文件共享
无环图目录结构（有向无环图）
实现文件共享
FCB中物理地址指向同一个索引节点，共享节点设置共享计数器，计数器为0时才真正删除节点
索引节点inode (FCB的改进)
定义：文件信息单独形成的一种数据结构（索引节点inode）中，FCB中只存储（文件名 | 索引节点指针） 目的：减小目录项大小，增加单位块存储目录项个数，进而在查目录时减少I/O次数 特点：打开文件时，磁盘索引结点信息将调入内存，变成内存索引节点，增加计数器表项等
索引节点inode存储他的其他文件信息，inode存放在系统区的i节点区，由操作系统统一管理。(文件系统全局结构中) 内存索引节点： 索引节点编号，用于标识内存索引节点。 状态，表示i节点是否上锁或被修改。 访问计数器，每当有一个进程访问此I节点时，计数器加1，访问结束减1。 逻辑设备号，文件所属文件系统的逻辑设备号。 链接指针，设置分别指向空闲列表和散列队列的指针。
不会常驻内存
文件共享
静态共享
硬链接(基于索引节点)
两个硬连接的文件指向的是同一个索引节点，删除其中一个只是删除了他在他的目录表中的目录项，同时索引节点的值减一，只有计数器减为0真正的文件才会删除。
索引节点设有计数count，记录链接到本索引节点上的用户目录项数目
软连接(基于符号链接)
由系统创建一个Link类型的新文件，存放文件路径（快捷方式）
注意：硬链接查找速度比软连接快
动态共享
两个进程同时对同一个文件进行操作
文件保护
口令保护
开销小，口令存在系统中不安全(口令存放在FCB或索引节点中)
加密保护
异或加密，需解密时间，比口令保护高
访问控制
特点：每个文件和目录增加一个访问控制列表ACL（可以使用复杂的访问方法） 规定每个用户名和及所允许的访问权限
复杂访问列表（用户为单位）
缺点：长度无法预计，且可能导致复杂的空间管理
精简访问者列表(分组)
系统管理员
拥有者
组
其他（其他用户）
访问控制项放在FCB中
注意：口令和密码都是防止文件被他人窃取，并没有控制用户对文件的访问类型
2. 文件系统实现 (文件管理系统)
文件系统层次结构
用户调用接口
创建删除等操作
文件基本操作
文件目录系统
管理文件目录
目录系统
存取控制验证模块
把用户的访问要求与FCB权限信息进行比较
文件保护
逻辑文件系统与文件信息缓冲区
将用户要求的逻辑记录转换成文件逻辑地址
逻辑结构
文件逻辑结构中的有结构文件
物理文件系统
逻辑地址转化为物理地址
物理地址映射
辅助分配模块
管理辅存空间(外存)
文件实现
设备管理程序模块
与设备直接交互
目录实现
线性列表
哈希表
文件实现 (研究文件物理结构)
分配方式 (管非空闲块)
连续分配 （一次访存）
为文件分配连续的磁盘块
FCB：文件名︱......︱起始块号︱长度
优点：速度快，支持随机访问 缺点：不好拓展文件大小，会产生碎片(可紧凑，时间代价)
链接分配 (n次访存)
隐式链接 （默认）
从文件目录项FCB中找到起始块，每一块中有指向下一个块的指针
FCB：文件名︱......︱起始块号︱结束块号
缺点：不支持随机访问，查找效率低
不需要结尾标识
显式链接
整个磁盘提取出来制成一张FAT(文件分配表[物理块号(隐含)︱下一块])，支持随机存储
一个块对应一项，启动后系统自动调入常驻内存
FCB：文件名︱......︱起始块号
索引分配 （m+1次访存）
一个文件对应一个索引块表，通过文件目录项找到索引块表，支持随机存储
FCB：文件名︱......︱索引块
索引表：逻辑块号(隐藏) | 物理块号
优点：可以随机访问，文件易于增删 缺点：索引表占用一定的空间，访问数据块前需要先读入索引块
大文件 解决方式
链接索引
1->1->1->1......
每个索引块中留一定空间指向下一个索引块
多层索引
1->n->n²......
分层管理索引块，直到最顶层只需要一个索引块
索引表：逻辑块号(隐藏) | 物理块号
混合索引
既采用直接地址，又采用单级或者两级分配方式
FCB：文件名︱索引节点指针
inode索引节点：文件信息 直接索引 ...... 间接索引
前几个索引项使用直接地址索引（直接指向数据块）， 后面的递增使用多层索引（指向一、二...级索引表）
索引块/节点最大不能超过一个块
存储空间管理 (管空闲块)
存储空间的划分 与初始化
存储空间的划分
文件卷/逻辑卷/逻辑盘(如C D E盘)
存储空间的初始化
目录区
FCB，空闲表，位示图，超级块等用于文件管理的数据
文件区
文件数据
1.空闲表法
空闲表记录：第一个空闲盘号︱空闲盘块数
适用于"连续分配方式"
分配时采用首次适应算法，最佳适应算法等策略
2.空闲链表法
空闲盘块链
以块为单位组成空闲链，分配时从头取下，回收放回链尾
每一个空闲盘块：下一个盘块号
空闲盘区链
以盘区(若干个空闲盘块组成)为单位
空闲盘区的第1个盘块：盘区的长度、下一个盘区的指针
3.位示图法
用二进制一位来表示磁盘一个块是否为空，1表示已分配，0表示空闲
计算：盘块号与字号、位号的转换
4.成组链接法 (UNIX) （适用于大型文件系统）
理解即可，空闲表法+空闲链表法，超级块充当链头,比较复杂，基本不考
文件系统的全局结构
格式化
物理格式化、低级格式化----划分扇区，检测坏扇区，并用备用扇区替换坏扇区
逻辑格式化后，磁盘分区完成各分区的文件系统初始化
虚拟文件系统
特点
向上层用户进程提供统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异
VFS要求下层的文件系统必须实现某些规定的函数功能，如：open/read/write。 一个新的文件系统想要在某操作系统上被使用，就必须满足该操作系统VFS的要求
每打开一个文件，VFS在组成中创建一个vnode，用统一的数据结构表示文件，无论该文件存储在哪个文件系统
vnode：文件名︱文件大小︱创建者︱文件格式︱......︱函数功能指针(open/read/write)
3. 磁盘组织和管理
磁盘
由磁道，磁头，磁块(扇区)组成
分类
固定头磁盘
活动头磁盘
固定盘磁盘
可换盘磁盘
扇区
磁盘读写的最小单位
簇/块
文件分配的最小单位，一般是扇区的整数倍
磁盘时间计算
寻找(道)时间
寻道(最大)
旋转延迟时间
旋转找到某一扇区所用的时间，默认取转半圈时间
传输时间
从磁盘读出或写入数据所经历时间,根据转速计算
磁盘调度算法
先来先服务算法
最短寻找时间优先算法(Shorest Seek Time First)
会产生饥饿
处理离当前磁头最近的磁道请求
扫描算法/电梯调度算法 （SCAN）
不会产生饥饿
只有磁头移动到最边缘，才改变磁头移动方向
look算法解决必须到头才能回来的问题，边移动边看，不一定要移动到头 注意：题目的scan算法默认为look算法
循环扫描算法（C-SCAN）
磁头移动到尾边缘，返回时不做任何操作，直接移动到头
c-look同样改进，不用移动到边缘，当移动的方向上没有请求，则直接转头去处理有请求的第一个磁道 注意：题目的c-scan算法默认为c-look算法
降低磁盘延迟
交替编号
磁盘相邻的扇区物理上不相邻，让扇区能连续读取
实际上磁盘不能连续读取，每读一个扇区就需要一段时间进行处理 原因：磁盘控制器(主板上)内的缓冲区需要读取时间
错位命名
让相邻盘面扇区编号错位，在切换盘面时也减少时间
因为磁盘读取完一块需要处理，不能连续取
磁盘地址结构的设计
物理地址顺序为： 柱面号+盘面号+扇区号
目的：减少磁头臂的移动，更多的是扇区移动，减少时间消耗
磁盘的管理
磁盘初始化步骤
1. 低级格式化/物理格式化：划分扇区
一个扇区格式化为：头、数据区域、尾
2. 磁盘分区（C盘D盘E盘）
柱面分区
3. 逻辑格式化：操作系统在磁盘上建立文件系统（根目录、存储空间管理数据结构）
引导块
存放自举程序，自举程序初始化CPU、寄存器等，然后启动操作系统
rom存放很小的自举装入程序，完整自举程序存放到启动块中 拥有启动分区的磁盘称为启动磁盘或系统磁盘
坏块
简单磁盘：逻辑格式化时在FAT将坏块标记出来
复杂磁盘：磁盘控制器维护一个坏块链，并管理备用扇区
扇区备用：将一些块保留备用，对操作系统透明
磁盘阵列
RAID0
无冗余无校验的磁盘阵列
RAID1
镜像磁盘阵列
RAID3
采用纠错的海明码的磁盘阵列
固态硬盘SSD
原理
基于闪存技术Flash Memory,属于电可擦除ROM,即EEPROM
组成
闪存翻译层
负责翻译逻辑块，找到对应页Page
存储介质：多个闪存芯片(Flash Chip)
每个芯片包含多个块(block)
每个块包含多个页(page)
读写性能特性
以页(page)为单位读/写
相当于磁盘的“扇区
以块(block)为单位"擦除”，擦干净的块，其中的每页都可以写一次，读无限次
支持随机访问，系统给定一个逻辑地址，闪存翻译层可通过电路迅速定位到对应的物理地址
读快、写慢。要写的页如果有数据，则不能写入，需要将块内其他页全部复制到一个新的（擦除过的）块中，再写入新的页
与机械硬盘相比的特点
SSD读写速度快，随机访问性能高，用电路控制访问位置；机械硬盘通过移动磁臂旋转磁盘控制访问位置，有寻道时间和旋转延迟
SSD安静无噪音、耐摔抗震、能耗低、造价更贵
SSD的一个"块"被擦除次数过多（重复写同一个块）可能会坏掉，而机械硬盘的扇区不会因为写的次数太多而坏掉
磨损均衡技术
思想：将“擦除”平均分布在各个块上，以提升使用寿命
动态磨损均衡
写入数据时，优先选择累计擦除次数少的新闪存块
静态磨损均衡
SSD监测并自动进行数据分配、迁移，让老|旧的闪存块承担以读为主的储存任务，让较新的闪存块承担更多的写任务
5. i/o设备
1. i/o设备管理
i/o设备分类
按使用特性
人机交互类外部设备；存储设备；网络通信设备
按传输速率分
低速设备；中速设备；高速设备
按信息交换单位分类
块设备
可寻址，传输速率高，有结构
字符设备
不可寻址，传输速率低，中断驱动方式，无结构
i/o控制方式 详见计组
程序直接控制方式
一次读入一个字，cpu和i/o只能串行工作，先从外存读入cpu，然后才能读入内存
中断驱动方式
中断信号驱动，需要保存CPU上下文，每个字的传输必须经过CPU
DMA方式
一次读入一个或多个块，多个块读入必须连续，不需读入cpu
通道控制方式
通道是小型cpu（只能识别通道指令），将通道程序存入内存(通道没有自己的内存)，需要硬件支持，cpu通过i/o通道发送i/o指令，给出通道程序在内存位置，通道cpu自动执行程序，传送结束向cpu发送中断请求，每次可读入一组数据，需硬件支持
i/o子系统层次结构
1. 用户层i/o软件
与i/o操作有关库，向用户提供库函数API，spooling技术（假脱机技术） eg：printf("hello world");
2. 设备独立性（设备无关性）软件
1、向用户层提供接口/系统调用接口 eg：write(fd,"hello world");
2、执行设备的共有操作，对设备进行回收和分配
3、将逻辑设备fd映射成物理设备：根据设备类型选择相应驱动程序 4、将系统调用的参数，传递到驱动程序入口地址相应标准接口中
设置一张LUT(逻辑设备表)来实现逻辑名到物理名的映射 LUT：逻辑设备名︱物理设备名︱驱动程序入口地址
方式：①整个设备只有一张LUT，不可重复，适用单用户 ②每个用户有一张LUT，可重复，适用多用户
3. 设备驱动程序
与硬件直接相关，用于驱动IO设备；对硬件的具体控制， 将上层发来的系统调用转化为设备能听懂的指令 eg：不同的驱动程序都会向上层提供一个组标准的程序接口，如read,write 通过接受的参数来控制设备工作。
4. 中断处理程序
保存被中断的CPU环境，转入相应中断处理程序
I/O核心子系统/操作系统内核部分
5. 硬件设备
电子部件：设备控制器（适配器）
机械部件：设备本身
设备控制器
设备控制器通过寄存器与CPU通信； 寄存器编制可独立编制(需要寄存器)或者内存映像IO(与内存同编制)
功能
接收识别cpu发出的命令（控制寄存器）
数据交换（数据寄存器，暂存输入输出数据）
向cpu报告设备状态（状态寄存器）
设备地址识别：通过CPU提供的地址判断要使用的寄存器
组成
与CPU的接口
数据寄存器，状态/控制寄存器
与设备的接口
一个通道对应多个控制器，一个控制器对应多个设备
i/o控制逻辑
识别cpu发出的命令，并向设备发出命令
输入/输出管理
输入/输出应用程序接口
字符设备接口
get/put
块设备接口
write/read
网络设备接口
socket
概念什么是阻塞/非阻塞I/O?
阻塞I/O
应用程序发出I/O，系统调用进程需转为阻塞态等待 eg：字符设备接口--从键盘读一个字符get
非阻塞I/O
应用程序发出I/O系统调用，系统调用可迅速返回进程，无需阻塞等待 eg：块设备接口--往磁盘写数据write
设备驱动程序接口
2. i/o核心子系统
高速磁盘缓冲和缓冲区区别
高速磁盘缓冲
逻辑上是磁盘，物理上是内存块（磁盘驻留），复制磁盘常用数据
缓冲区
单缓冲
方法论：初始化用户区有数据，缓冲区没数据
双缓冲
方法论：初始化工作区为空，缓冲区一个有数据另一个没有数据
循环缓冲
缓冲区呈环形，设置in和out指针
缓冲池
设置三个队列：空缓冲队列、输入队列、输出队列
设置初始状态，分析下一次到达相同 状态需要的时间即为平均所需时间 (甘特图分析)
设备分配与回收
设备分配方式
独占式使用设备
例：打印机，磁带机
分时式共享使用设备
例：磁盘
以spooling方式使用外部设备
以空间换时间，假脱机技术，虚拟设备（用户以为有好多设备）
设备分配数据结构
DCT设备控制表
每个设备有一张，记录设备属性
COCT控制器控制表
CHCT通道控制表
SDT系统设备表
整个系统只有一张，每个目录项包括设备类/标识符/DCT/驱动入口
设备分配步骤1,2,3,
设备分配策略
设备分配原则
考虑设备特性、用户要求和系统配置情况
设备分配安全性
安全分配方式
进程发出i/o启动命令就进入阻塞状态，i/o操作完成前，进程 处于阻塞态，缺点cpu和i/o串行工作，优点不会死锁
不安全分配方式
发出i/o请求后进程继续执行程序，可继续请求别的设备，直到请求设备被另一个进程占用才阻塞，缺点会死锁
设备分配算法
静态
进程运行前为其分配全部所需资源，结束后归还资源
动态
进程运行过程中动态申请设备资源
有可能造成进程死锁，多道程序
静态：死锁预防(破坏请求和保持) 动态：可采用死锁避免
SPOOLing技术
用户将需要输出的数据（经内存的缓冲区）先放到磁盘（输出井） 进行排队，待设备空闲，将数据依次调入缓冲区然后输出
打印机输出