操作系统知识点复习总结(期末版)

阅读数: 84次 2020-09-21

这是我在本学期开学的操作系统理论考试复习笔记，针对的更多是个人不会的地方。

教材配套是操作系统设计与实现这本书，也是我们专业课使用的教材。

长上面这个样子。

对照着也有王道408考研书的，虽然表述不同，但大都大同小异，针对的都是操作系统的核心。

操作系统速记

操作系统控制和管理系统内的各种资源，源程序资源不是操作系统应该管理的
系统调用只能通过用户程序间接使用，是操作系统给编程人员的借口，系统调用的目的是请求系统服务。
操作系统与用户的通信接口不包括缓存管理指令
操作系统开机后，被最终加载到RAM。
提高单CPU利用率：多道程序设计，批处理OS的主要缺点是无交互能力。
OS的基本类型：批处理OS分时OS实时OS
多道程序系统的系统开销大
实时系统：抢占式的优先级调度
分时系统：优先级+非抢占
时间片一定，用户数越多，响应时间越长
甘特图CPU运行时间，进程周转时间
中断处理是OS必须提供的功能，
地址映射：重定位需要硬件的支持；时钟管理,中断系统也需要。
中断和异常
用户态执行命令解释程序
系统调用，是OS给用户的借口，用户态，进程切换只可能在和心态。
中断处理程序，PSWR/PC
中断是完成时的提醒，所以”缺页中断”是异常，但是广义来说，缺页中断作为中断，一条指令在执行期间，可能产生多次缺页中断。
执行系统调用的过程，传递系统调用参数，执行中断指令，执行相应的服务程序返回用户态
定时器产生时钟中断后，由时钟中断，所有与时间相关的都更新了。
显然，微内核没有大内核高效和稳定，但系统更可靠。

每一个进程必须有一个唯一的标示：PCB
进程状态的改变：
1. 就绪，除了CPU都有了
2. 阻塞，等待事件发生，等I/O的完成，等待中断的结束，等待其他资源
3. 当I/O完成时，由阻塞进入就绪态。
4. 时间片结束进入就绪态
5. 就绪态不可能直接到阻塞态
6. 进程的阻塞是进程自身的一种主动行为，因此也只有running才可以到wait态。
7. 进程间通信(IPC)需要进程同步和互斥手段的辅助
进程通信机制：共享存储消息传递管道PV原语
进程是拥有资源的基本单位，县城作为调度的基本单位
为啥要有线程？线程开销比进程开销小啊
有新进程进入就绪态不是引起操作系统选择新进程的直接原因
堆栈指针属于PCB但是全局变量不属于PCB
进程创建完成时会进入就绪序列
当就绪队列非空时，操作系统总是繁忙
对进程的管理和控制使用原语
设备分配由I/O系统完成，一种数据结构用来记录不会导致新进程的创建
属于同一个进程的线程也有属于自己的战指针
降低进程优先级的合理时机时进程时间片用完。
操作系统空闲，就绪队列为0，CPU处于空闲状态；当系统中所有进程处于阻塞状态时可能是死锁。
现代OS中，不能进行进程调度与切换的情况：
1. 处理中断
2. 进程在临界区
3. 完全屏蔽中断的原子操作过程
系统吞吐量时单位时间内CPU完成作业的数量，所以CPU完成的作业越多，CPU利用率高
FCFS不可剥夺算法，对长作业有利，长作业属于IO繁忙型，短作业属于CPU繁忙型(相对于SJF和高响应比)
SJF：导致饥饿，饥饿是由于策略调度产生的，死锁是循环等待，是由于系统资源互斥占有从而循环等待产生的。
优先级算法：剥夺式非剥夺式
优先级标准：IO >计算
高响应比优先调度：（等待+服务）/服务
时间片，适用于分时系统，为了多个用户可以及时干预系统，人机交互也应采用时间片轮转调度算法
时间片轮转调度算法是绝对可抢占的
进程处于临界区时可以进行处理机调度(28)
可以满足短作业优先且不会饥饿：高响应比优先
临界区是访问共享资源(临界资源)的那段代码！！！
可以用信号量机制来解决互斥与同步的问题,p/v操作
信号量实现同步：前V后P
信号量实现互斥：p(mutex)v(mutex)
一个进程只有通过管城内的过程才能进入管程访问共享数据
每次仅允许一个进程(任何时候)在管程内执行某个内部过程。管程可以实现进程的互斥和同步。管程是由编程语言支持的进程同步机制，管程中定义的变量只能被管程内的过程访问。
经典IPC问题：
1. 生产者消费者问题：
  
  信号量：标示资源，初始化为资源的数量
  
  p(资源)：要用什么p一下
  
  v(资源)：提供什么v一下
2. p(mutex) do sth on critical section v(mutex)
3. 读者写者问题的三种类型和不同的思路
4. 哲学家就餐问题
某个信号量的处置是n，当信号量n<0,|n|阻塞队列的进程个数。n>=0表示可用资源的个数
临界区是指并发进程访问共享变量段的代码程序。
p操作可能导致进程阻塞
管程定义了共享数据结构和各种进程在该数据结构上的全部操作。
用v操作唤醒，被唤醒进程变为就绪态。

阻塞态->就绪态。
可以被多个进程在任意时刻共享的代码必须是不允许任何修改的代码
如果有进程在等待进入临界区的话，mu tex一定<0
临界区是代码，
互斥使用的资源一定是1.
x.wait()阻塞该进程，并将之插入x的阻塞队列中。
对共享变量的操作需要互斥执行。
死锁
1. 死锁预防
  
  破坏死锁的四个条件
  - 互斥：任意时刻只允许一个进程使用资源【对所有资源进行spooling】
  - 环路等待：顺序资源分配，资源编号，资源有序分配
  - 破坏不剥夺：已占用的不会被强制剥夺
  - 请求并保持(占有并请求)：进程在请求剩余资源，不主动释放所占用的资源，运行前一次性申请完所需要的资源
2. 死锁检测：资源分配图
3. 死锁避免：银行家算法，检查系统的安全状态，防止系统进入不安全的状态
产生死锁的可能原因是独占资源分配不当，系统资源分配不足只会产生饥饿而不是死锁。
解除死锁通常不采用从非死锁进程抢夺资源
两级调度
忙等算法
两阶段加锁

虚拟存储器(virtual memory)：使进程在只有一部分主存的情况下也能运行。

虚拟存储是把内存与外存有机结合起来使用

虚拟存储器：在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理内存大得多，可寻址的内存。虚拟存储区的容量与物理内存(主存)大小无关，而受限于计算机的地址结构(最大容量取决于虚拟地址空间，即虚拟存储器的最大容量由计算机的地址结构决定)和可用磁盘容量。

48位虚拟地址空间，针对于64位计算机而言。

虚拟存储只能基于非连续分配技术。
虚拟内存技术的实现：

虚拟内存实现：分页存储/分段存储/请求段页式存储

不管哪种方式，都需要一定的硬件支持。
地址重定位：(将用户空间中使用的逻辑地址转变为物理地址的过程)
- 静态重定位：固定分区
- 动态重定位：作业执行过程
重定位与地址保护：一个既针对重定位又针对保护问题的解决方法是设置基址和界限寄存器
地址映射

逻辑地址变为物理地址：

虚拟地址是用户空间的逻辑地址
固定分区
动态分区（FF/BF/NF/WF）
软件模拟LRU算法(NFU )
非连续分配管理方式：(虚拟存储管理)

分页存储管理，没有外碎片，1/2内碎片；地址变换由硬件自动完成。

逻辑地址结构与页表项结构

多级页表：不浪费空间存储无用页表项在内存中，【不盲目顺序式查找页表项】地址映射需要非常迅速

多级页表的缺点是我们需要多次访问内存以查找页表。

分段存储管理：没有内碎片

分段/段表/地址变换机构

段页式管理方式：一个进程中，段表只有一个，页表可能有多个。段式：编程时程序的逻辑结构。段没有内碎片但有外碎片
页式存储管理的设计问题：
1. 工作集模型：
  1. 抖动：分配给进程的物理页数太小，无法包含其工作集，频繁的在内存和外存间换页。
  2. 预先调页
2. 分配策略
3. 页面大小：内碎片在最后一页
4. 虚拟存储接口
LRU算法耗费高的原因是需要对所有的页进行排序。
虚拟存储管理系统的基础是基于程序的局部性
使用覆盖，交换可以实现虚拟存储

I/O的各种控制方式：

程序控制
中断控制
DMA控制
通道控制

设备驱动程序

设备无关软件的设计目标

设备无关性

Spooling

磁盘

磁盘调度算法

时钟

终端设备

文件系统
字符设备文件/块设备文件
I-node ：

inode包含了文件的元信息，inode也会消耗磁盘空间，所以在磁盘格式化的时候，磁盘中也有inode区。

unix/linux系统内部不使用文件名，而是使用inode号来识别文件。

unix中目录也是一种文件，所以，打开目录就是打开文件，每个目录的目录项由两部分组成，包含文件的文件名与该文件名的inode号。

硬连接：文件名和inode号码之间是一一对应的关系，每个inode对应一个文件名。但是unix系统允许多个文件名指向同一个inode号码。

所以，可以用不同的文件名访问同样的内容。对文件内容的修改，会影响到所有文件名，但是删除一个文件名不会影响另一个文件名的访问。

即inode信息项中有一项叫做链接数，记录指向该inode的文件名总数，这时会增加1.

删除一个文件名，会使得inode节点中的“链接数”减1，当这个值减到0，表示没有文件名指向这个inode.

符号链接是一个包含文件名的小文件。硬链接比符号链接更有效。

所以删除原文件的时候，符号链接就失效啦，符号链接类比于快捷方式，但是符号链接可以跨系统

磁盘块结构
FOT
文件系统安装
磁盘空间管理
块高速缓存
文件系统的性能

生产者-消费者问题

生产者消费者共享一个初始为空，大小为n的缓冲区
缓冲区没满，生产者才能生产
缓冲区没空，消费者才能消费
缓冲区是临界资源，必须互斥访问。

semaphore mutex=1;
semaphore full=0;
semaphore empty=n;
producer(){
  while(1){
    p(empty)//消耗一个空的slot
    p(mutex)//p操作会导致进程阻塞，所以实现互斥的p操作一定要放在实现同步的p操作之后。
    produce()
    v(mutex)
    v(full)//增加一个满的
  }
}
consumer(){
  while(1){
    p(full)
    p(mutex)
    consume()
    v(mutex)
    v(empty)
  }
}

读者-写者问题(三种变体，课后题)

变体1

允许多个读者可以同时对文件进行读操作
写写互斥
读写互斥
读者优先

semaphore db=1//共享文件的互斥访问(写写)
int count =0;//引入count变量记录有多少读进程
semaphore mutex=1;//count变量的互斥访问
reader(){
  while(1){
    p(mutex);//读进程互斥访问count
    counter=counter+1;
    if(counter==1)
      p(db);//因为读优先，所以对db加锁
    v(mutex);//living critical sectioncount
    read();
    p(mutex);//各读进程互斥访问count
    counter=counter-1;
    if(counter==1)
      v(db);
   	v(mutex)  
  }
}
writer(){
  while(1){
    p(db);//可omit
    p(mutex);//写之前加锁
    writer;
    v(mutex);//写之后解锁
    v(db);//可omit
  }
}

变体2：公平竞争

设有一个数据库，存在多个读者和写者，读写互斥，写写互斥，写操作只需要等待它到来时处于活跃状态的读者结束，而不需要等待所有读者结束。

读完才能写；写完才能读；

读读不需要互斥。

semaphore rw=1;//读写对共享资源的互斥访问
int count=0;//有多少读进程
semaphore mutex=1;//对count共享变量互斥访问
semaphore w=1;//写资源优先，
writer(){
  while(1){
    p(w);//拿到写令牌，阻塞读
    p(rw);//拿到访问数据库令牌
    write;
    v(rw);
    v(w); 
  }
}
reader(){
  p(w);//拿到写令牌
  p(mutex);
  counter=counter+1;//都reader了，肯定counter计数要+1;
  if(counter==1)//如果是第一个读
    p(rw);//访问数据库的锁
  v(mutex);//counter咱不需要占着了嘛
  read();
  //读完以后呢
  p(mutex);
  counter=counter-1;
  if(counter==0)
    v(rw);//释放访问数据库的锁
  v(mutex);
}

变体3 写者优先

当有写者到来时阻塞读者线程的队列

读写互斥，写完后才能读。

没有写的时候，所有读都能读。

增加计数这是第几个写？

哲学家就餐问题

#define N 5
#define LEFT (i+N-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
semaphore mutex=1;//临界区互斥
semaphore s[N];//每个哲学家一个信号量
int state[N]//记录哲学家的状态

void philosopher(int i){
  while(1){
    think();
    take_forks(i);
    eat();
    put_forks(i);
  }
}
void take_forks(int i){
  p(mutex);
  state[i]=HUNGRY;
  test(i);//试图得到两把叉子
  v(mutex);
  p(s[i]);//得不到叉子就阻塞该哲学家
}
void put_forks(int i){
  p(mutex);
  state[i]=THINKING:
  test(LEFT);//看左能否进餐
  test(RIGHT);//看右能否进餐
  v(mutex)
}
void test(i){
  if(state[i]==HUNGRY &&state[LEFT]!=EATING &&state[RIGHT]!=EATING){
    state[i]=EATING;
    v(s[i]);//得到叉子后就唤醒
  }
}

操作系统名词解释

陷入

管程：管程是由过程、变量及数据结构组成的集合，组成一个特殊的模块或软件包，进程可在任何需要的时候调用管程中的过程

把共享变量，和对共享变量的操作都集中在一个模块中。

设备驱动程序：接受上方设备无关软件的请求，负责执行请求。

设备无关性：用软件屏蔽硬件上的差异

两阶段加锁法：【死锁预防的方案过于严格，死锁避免的方法需要无法得到信息】，【在很多数据库系统中，常常需要将若干记录上锁然后更新】

在第一阶段，进程时图将其所需的全部记录加锁，一次锁一个记录。若成功，则开始第二阶段。完成更新然后释放锁。如果有一些记录已经被上锁，则它将已上锁的记录解锁并重新开始第一阶段。

交换：把各个进程完整地掉入内存，运行一段时间，然后再放回磁盘

虚拟存储器: virtual memory，进程即使只有一部分内容在内存中也能运行。程序代码\，数据和栈的总大小可以超过实际可用的物理内存的大小。OS把当前需要的留在内存中，不需要的保留在磁盘上。

工作集模型：一个进程当前正在使用的页面的集合称为它的工作集。

字符设备文件：与输入/输出有关，用于处理各种串行I/O设备；

快设备，用于磁盘

文件系统的布局：

大多数磁盘可以分为若干个分区，每个分区上的FS是相互独立的，MBR(主引导技术)：

整个磁盘：

MBR(磁盘扇区0，用来启动计算机BIOS 读入执行MBR中的代码)+分区表

单独分区：

Boot block;Super block;空闲空间管理；I-nodes(索引节点)；根目录；文件和目录

Difference between file discriptor and i-nodes.

超级块用来管理文件系统

Inode-与打开文件表

magic number:

rwx（所有者)//同组(rwx)//其他
CPU核心态OS使用，执行机器所有指令
用户态用户，I/O操作和其他操作都不能执行
先将参数放入预先确定的寄存器或堆栈，然后执行一条特殊的陷入指令
虚拟机：全虚拟化技术(虚拟成多个大型机，并且和硬件接口完全一致)，半虚拟化技术
部分虚拟化：在硬件支持不完全的情况下，仍然能够提供虚拟化
基于容器的虚拟化技术：计算机系统上运行着唯一的操作系统实例，通过在这个系统上加装虚拟化平台，可以将系统划分成多个独立隔离的容器，每个容器是一个虚拟的操作系统，不虚拟任何硬件设备。
PCB 进程控制块：资源占用信息：虚拟地址空间现状,打开文件列表。
中断处理的步骤：
用户线程：不依赖于OS核心；所以也没有用户态与核心态的切换
内核线程：依赖于OS核心
可能的方法：
1. 关中断；
2. 锁变量(如果锁变量是普通类型，不是原子类型，仍会发生竞争条件)
3. 严格交替法：即使代码在非临界区中，也会阻塞其他进程
4. 忙等待形式互斥：Peterson互斥，TSL解法
许多系统调用是原语，但并非所有系统调用都是原语
条件变量：在管程内部，存在某种等待机制，管程内部可以说明和使用的一种特殊类型的变量（条件变量）,每个表示一种等待原因，相当于每个原因对应一个队列。
利用消息传递进行进程间通信，使用SEND/RECEIVE两条原语
分时系统：多个用户分享使用同一台计算机，多个程序分时共享硬件和软件资源(按时间片分配)
OS的有些部分也需要定时器，即所谓的看门狗时钟。每次向硬盘控制器发命令时，都要安排唤醒调用，以便当命令执行完全失败时的试图恢复。
程序控制I/O：I/O操作由程序发起，CPU等待操作完成,数据的读写通过CPU，每个控制器都有一些用来与CPU通信的寄存器与缓冲区。

设备数据缓冲区按内存地址空间进行统一编址。
中断驱动：I/O操作由程序发起，在读/写字符数据完成时，向CPU发出中断，通知CPU，读写通过CPU
DMA：程序DMA硬件中的完成I/O操作，CPU只需要干预I/P操作的开始和结束。
通道，通道比CPU完成更为复杂的I/O控制，一个通道对应多个外设，一次完成几批I/O操作。
spooling ：假脱机，创建一个特殊的守护进程与特殊的目录，称为spooling 目录，进程将文件方在spooling 目录下，打印机是独占设备。
RAM 盘：在内存中保留一部分存储区域，使其像普通磁盘一样使用。
寻道时间是找道找柱面(磁道)！旋转延迟则是由于扇区的定位带来的！
终端是用户与计算机交互的工具，包括键盘和显示器
TLB：页表的缓存，lookaside buffer,快表
反置页表：一个物理页框对应一个页表项
一台虚拟机由48位虚拟地址和32位物理地址，页面大小为8KB，请问在页表中需要多少个页表项，页表项只取决于虚拟地址空间，所以为35位
TLB的大小只有工程上的折衷。
旋转时间8msec,一道的容量为1MB，所以transfer其实也相当于是知道了。
磁盘计算：20题。

一个磁盘有4000个柱面，每个柱面有8个磁道，每个磁道有512个块，在寻道时每移过一个柱面需要1ms。

逻辑上相邻两个块的平均寻道时间为5ms，

逻辑上相邻两个块的平均寻道为100 $\mu s$

旋转延迟为10ms，传输时间时每块20 $\mu s$ .

读100个块：

旋转延迟10ms，所以平均旋转延迟是5ms。

（5+5+0.02）✖️100

（0.1+5+0.02）✖️100

4000柱面 10ms，块与块rotation0.005

OS关心磁盘存储，有效工作，管理安全一致性的问题