Skip to content

Latest commit

 

History

History
700 lines (328 loc) · 13.9 KB

操作系统.md

File metadata and controls

700 lines (328 loc) · 13.9 KB
Raw

操作系统笔记

第一章

os的目标：有效性，方便性，可扩展性，开放性

操作系统的作用：1.作为用户和计算机硬件系统的接口 2.作为计算机资源的管理者 3.实现了对计算机资源的抽象

分时系统的特征：多路性，独立性，及时性，交互性

设置schedule进程状态符：

  1. 根据终止进程标识符，找PCB
  2. 若该进程正在执行，终止，设调度标志为真
  3. 撤销其所有子孙
  4. 回收所有资源，归还父进程或者系统
  5. 将PCB移出所在队列

程序顺序执行的特征：顺序行，封闭性，可再现性

多道程序系统中执行环境：独立性，随机性，资源共享性

程序并发执行特征：间断性，失去封闭性，不可再现性

进程：进程是程序在一个数据集上的运行过程，是系统进行资源分配和调度的一个独立单位。

进程的六个特征：动态性，并发性，独立性，制约性，异步性，结构特征（进程=程序+数据+PCB）

进程和程序的6个区别：

  1. 进程是程序的执行，是动态的概念，有生命周期；程序是一组指令的有序集合，是静态的永久存在
  2. 进程组成：进程=程序+数据+PCB
  3. 进程可并发执行
  4. 进程可作为一个独立的单位运行，同时也是系统中独立获得资源和独立调度的基本单位；凡未建立进程的程序，都不能作为一个独立的单位运行
  5. 一个程序可对应多个进程
  6. 一个进程可包含多个程序。主程序进程执行时可调用其它程序，共同组成一次“活动”

创建进程的两个步骤：1. 创建PCB，并填写相应的管理信息 2.把该进程转入就绪状态并插入就绪队列

终止进程的步骤：1.回收资源 2.删除PCB

deposit(data):
		begin
			Ｐ（avail）
			Ｐ（mutex）
			送数据入缓冲区某单元
			Ｖ（full）
			Ｖ（mutex）
		end
remove(data):
		begin
			Ｐ（full）
			Ｐ（mutex）
			取缓冲区中某单元数据
			Ｖ（avail）
			Ｖ（mutex）
		end

进程的三种状态：

  1. 运行态（该时刻进程实际占用CPU）
  2. 就绪态（可运行，但因为其他进程正在运行而暂时停止）
  3. 阻塞态（除非某种外部事件发生，否则进程不能运行）

信号量！！

PV原语操作

P表示申请资源，资源数量-1，假如数量不够，则进入阻塞状态。

V表示使用完毕，释放资源，资源数量+1

引起阻塞事件：

  1. 请求系统服务
  2. 启动某种操作
  3. 新数据未到达
  4. 无新工作可以做

进程：

  1. 立即停止执行
  2. 把PCB中进程“执行”->“阻塞”
  3. PCB插入阻塞队列
  4. 转进程调度程序

临界区

为了避免竞争条件，有以下四个条件：

  1. 任何两个进程不能同时处于其临界区
  2. 不应对CPU的速度和数量做任何假设
  3. 临界区外进行的进程不得阻塞其他进程
  4. 不得使进程无限期等待进入临界区

忙等待的互斥

  1. 屏蔽中断（由于多核技术的发展，所以不可取）
  2. 锁变量（但是由于各种中断的原因，可能会出现两个进程同时进入临界区）
  3. 严格轮转法（使用自旋锁，但是可能由于在临界区外的进程阻塞其他进程，所以不可取）
  4. Peterson解法
# define FALSE 0
# define TRUE 1
# define N 2	//进程数量

int turn;	//现在轮到谁
int interested[N];	//所有值初始化为0

void enter_region(int process){	//进程为0/1
  int other;	//其他进程号
  
  other = 1 - process;	//另一方进程
  interested[process] = TRUE;	//表示感兴趣
  turn = process;	//设置标志
  while (turn == process && interested[other] == TRUE);	//死循环空等 
}

void leave_region(int process){	//进程：谁离开
  interested[process] = FALSE;	//表示离开临界区
}
  1. TSL指令（需要特殊的硬件设备）

使用信号量的生产者消费者问题

# define N 100	//缓冲区中的槽数目
typedef int semaphore;	//信号量是一种特殊的整型数据
semaphore mutex = 1;	//控制对临界区的访问
semaphore empty = N;	//计算缓冲区的空槽数量
semaphore full = 0;	//计算缓冲区的满槽数量

void produce(void){
  int item;
  
  while(TRUE){	//TRUE是常量1
    item = produce_item();	//产生在缓冲区中的一些数据
    down(&empty);	//将空槽数目减1
    down(&mutex);	//进入临界区
    insert_item(item);	//将新数据放到缓冲区
    up(&mutex);	//离开临界区
    up(&full);	//将满槽的数目加1 
  }
}


void consumer(void){
  int item;
  
  while(TRUE){	//无限循环
    down(&full);	//将满槽数目减1
    down(&mutex);	//进入临界区
    item = remove_item();	//从缓冲区取出数据项
    up(&mutex);	//离开临界区
    up(&empty);	//将空槽数目加1
    consume_item(item);	//处理数据项
  }
}

使用信号量时，应先对私有信号量操作，再对共有信号量操作

如果不需要信号量的计数能力，可以使用简化版——互斥量

消息传递

  1. 共享存储器信息
  2. 管道通信
  3. 消息传递通信（目标信箱容纳那些已被发送但尚未被目标进程接受的消息）

第二章

作业状态：提交、收容、执行和完成

调度程序

按照实时任务性质的不同来划分：

1. 硬实时调度算法
2. 软实时调度算法

作业与进程的关系：作业可被看作是用户向计算机提交任务的任务实体，例如一次计算、一个控制过程等；进程则是计算机为了完成用户任务实体而设置的执行实体，是系统分配资源的基本单位

调度程序调度时间：

  1. 静态调度算法
  2. 动态调度算法

多处理机环境：

  1. 集中式调度算法
  2. 分布式调度算法

调度：

作业调度（宏观/高级调度）频率最低

交换调度（中级调度）：为了提高内存的利用率和系统的吞吐量

进程调度（微观/低级调度）：分为抢占式和非抢占式；频率最高

线程调度

调度目标：

对所有作业公平合理，应使设备有高的利用率，每天执行尽可能多的作业，有快的响应时间。

JCB：作业名，作业类型，资源要求，资源使用情况，优先级，当前状态，其他

吞吐量是系统每小时完成的作业数量。

周转时间是指从一个批处理作业提交时刻开始直到作业完成时刻为止的统计平均时间。

批处理系统中的调度：

  1. 先来先服务（来一个就开始服务，直到结束）非抢占式

  2. 最短作业优先（适用于运行时间可以预知的作业）非抢占式

  3. 最短剩余时间优先

  4. 高响应比优先调度算法

    优先权＝(等待时间+要求服务时间)/要求服务时间

    响应比＝(等待时间+要求服务时间)/要求服务时间

    每次要进行作业调度时，系统首先计算后备队列中各作业的响应比，然后选择一个或若干个响应比最高的作业调入内存执行。

交互式系统中的调度：

  1. 轮转调度
  2. 优先级调度
  3. 多级队列
  4. 最短进程优先
  5. 保证调度
  6. 彩票调度
  7. 公平分享调度

产生死锁的必要条件

  1. 互斥条件：每个资源要么已经分配给了一个进程，要么就是可用的
  2. 占有和等待条件：已经得到了某个资源的进程可以再请求新的资源
  3. 不可抢占条件：已经分配给一个进程的资源不能强制性地再被抢占，他只能被占有他的进程显式地释放
  4. 环路等待条件：死锁发生时，系统中一定有两个或两个以上的进程组成的一条环路，该环路中的每个进程都在等待着下一个进程所占有的资源

解决死锁的四种策略

  1. 忽略该问题
  2. 检测死锁并恢复
  3. 仔细对资源进行分配，动态地避免死锁
  4. 通过破坏引起死锁的四个必要条件之一，防止死锁的产生

哲学家就餐问题

  1. 奇数先左后右，偶数先右后左
  2. 使用信号量数组
# define N 5	//哲学家数目
# define LEFT	(i+N-1)%N	//i的左邻居的编号
# define RIGHT 	(i+1)%N	//i的右邻居的编号
# define	THINKING	0	//哲学家在思考
# define	HUNGRY	1	//哲学家试图拿起叉子
# define	EATING	2	//哲学家进餐
typedef int semaphore;	//信号量
int state[N];	//跟踪记录哲学家的状态
semaphore mutex = 1;	//临界区的互斥
semaphore s[N];	//每个哲学家的状态

void philosopher(int i){	//哲学家编号，从0到N-1
  while(TRUE){	//无限循环
  }
}

void take_forks(int i){	
  down(&mutex);	//进入临界区
  state[i] = HUNGRY;	//记录i哲学家为饥饿状态
  test(i);	//尝试获得两把叉子
  up(&mutex);	//离开临界区
  down(&s[i]);	//得不到就阻塞
}

void put_forks(int i){
  down(&mutex);	//进入临界区
  state[i] = THINKING;	//就餐完毕
  test(LEFT);	//检查左邻居是不是可以吃
  test(RIGHT);	//检查右邻居是不是可以吃
  up(&mutex);	//离开临界区
}

void test(int i){
  if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING){
    state[i] = EATING;
    up(&s[i]);
  } 
}

第三章

逻辑地址:目标地址使用的地址单元

物理地址:实际地址

地址空间是一个进程可用于寻址内存的一套地址集合。

跟踪内存使用的两种方式：位图，空闲链表

空闲链表：

  1. 首次适配算法
  2. 下次适配算法（从上次地方开始）
  3. 最佳适配算法
  4. 最坏适配算法：分配最大的可用空闲区

重定位：为了保证程序的正确执行，必须把程序和数据的逻辑地址转换为物理地址，这一工作叫做地址转换或重定位（分为动态和静态）

静态重定位的特点：

  1. 程序重定位之后就不能在内存中搬动了
  2. 要求程序的存储空间是连续的，不能把程序放在若干个不连续的区域内

动态重定位：需要特殊硬件的支持——重定位寄存器

页面置换算法：

  1. 先进先出算法
  2. 最久未使用（LRU）算法
  3. 最近未使用算法（NRU）
  4. 最少使用算法（LFU）
  5. clock算法
  6. 页面缓冲算法

合并空闲区

可变分区分配方式下，当收回主存时，应检查是否有与归还区相邻的空闲区，若有，则应合并成一个空闲区。相邻可能有上邻空闲区、下邻空闲区、既上邻又下邻空闲区、既无上邻又无下邻空闲区。若有上邻空闲区，只修改上邻空闲区长度（为收回的空闲区长度与原上邻区长度之和）即可；若有下邻空闲区，改记录这个下邻空闲区记录的地址为收回空闲区的地址，长度为下邻空闲区的长度和收回空闲区的长度即可；若既有上邻又有下邻空闲区，改记录上邻区记录的长度（为上邻区长度、下邻区长度和收回区长度之和），再把下邻区记录的标志位改为空即可；若既无上邻区又无下邻区，那么找一个标志位为空的记录，记下该回收区的起始地址和长度，且改写相应的标志位为未分配，表明该登记栏中指示了一个空闲区。

第四章

外存分配方式

  1. 连续分配

  2. 链接分配（分为显式和隐式）

    隐式链接：末尾为下一个盘块地址

    显式链接：磁盘对应的所有指针全部储存在外存的一张链接表FAT中，使用的时候调入内存

  3. 索引分配：每个文件分配一个索引块，放置该文件的物理块

文件目录：树形

设置当前目录和绝对目录

目录查询技术：线性检测法和hash法

第五章

DMA的引入（Direct Memory Access）

一个设备接口试图通过总线直接向另一个设备发送数据(一般是大批量的数据)，它会先向CPU发送DMA请求信号。外设通过DMA的一种专门接口电路――DMA控制器（DMAC），向CPU提出接管总线控制权的总线请求，CPU收到该信号后，在当前的总线周期结束后，会按DMA信号的优先级和提出DMA请求的先后顺序响应DMA信号。CPU对某个设备接口响应DMA请求时，会让出总线控制权。于是在DMA控制器的管理下，外设和存储器直接进行数据交换，而不需CPU干预。数据传送完毕后，设备接口会向CPU发送DMA结束信号，交还总线控制权。

单缓冲，双缓冲，循环缓冲

设备驱动程序：设备驱动程序主要是指在请求I/O的进程与设备控制器之间的一个通信和转换程序。

设备独立性：为了提高OS的可适应性和可扩展性，现代操作系统都毫无例外地实现了设备独立性(Device Independence)，也称为设备无关性。其基本含义：应用程序独立于具体使用的物理设备。

设备独立性软件：基本功能是执行对所有设备公共的I/O功能，并且向用户层软件提供一个统一的接口

SPOOLING：联机情况下实现的同时外围操作称为SPOOLing，或称假脱机操作

组成：

  1. 输入井和输出井
  2. 输入缓冲区和输出缓冲区
  3. n输入进程SPi和输出进程SPo（预输入程序和缓输出程序）

磁盘访问时间

  1. 寻道时间$T_s$ ：是指把磁臂（磁头）移动到指定磁道上所经历的时间
  2. 旋转延迟时间$T_τ$：是指定扇区移动到磁头下面所经历的时间
  3. 传输时间$T_t$：是指把数据从磁盘上读出或向磁盘写入数据所经历的时间

磁盘调度算法

  1. 先来先服务
  2. 最短寻道时间优先
  3. 电梯算法
  4. 循环扫描算法（单方向的电梯算法）
  5. NStepScan算法
  6. FScan算法

提高磁盘IO速度算法

磁盘高速缓存提前读、延迟写、优化物理块的分布、虚拟盘等