跳至主要內容

操作系统

Zzz操作系统操作系统2024年11月3日约 4275 字大约 14 分钟

计算机系统概述

操作系统的基本概念

  • 控制和连接计算机各种软硬件资源的平台.

  • 操作系统的特征

    • 并发，两个或者多个事件在同一个时间间隔内发生，跟并行（两个或者多个事件在同一个时刻内发生）做区别.

    • 共享，资源共享，共享和并发是最基本的特性，互为存在条件.

    • 虚拟，物理上的实体变成逻辑上的若干实体，原本的互斥设备就可以被多个进程所访问.

    • 异步，程序是以走走停停的方式运行的.

操作系统的发展历程

  • 手工处理阶段，用纸袋来存储程序，不存在并发.

  • 批处理阶段，将程序成批执行，顺序执行，用户不能干预执行过程，没有人机交互.

    • 单道批处理，同一个时刻只存在一个程序执行.

    • 多道批处理，同一个时间间隔多程序执行，宏观上并行，微观上串行.

  • 分时操作系统

    • 将CPU\text{CPU}的使用时间分为多个时间片分给联机作业使用.

    • 具有特性，同时性，交互性，独立性，及时性.

  • 实时操作系统，对响应时间要求较高的操作系统.

  • 网络操作系统，为了数据共享.

  • 分布式操作系统，将任务发送到云端进行多节点处理，实现协同处理任务.

操作系统的运行环境

  • 特权指令和非特权指令

    • 特权指令，不允许用户直接使用.

    • 非特权指令，允许用户直接使用.

  • 内核态（管态）和用户态（目态）

    • 内核态执行特权指令.

    • 用户态执行非特权指令.

    • 在用户态执行特权指令的过程称为系统调用，发生在用户态，系统调用时用户态切换为核心态，用户态切换为核心态是由硬件自动实现的.

  • 原语，程序的执行要不然都成功要不然都失败.

  • 中断称为外中断，除CPU\text{CPU}之外的异常.

  • 异常称为内中断，由CPU\text{CPU}内部自己发生的.

    • 异常分为故障（除零），自陷（系统调用），终止（CPU\text{CPU}没有办法继续执行）.

    • 终止异常和外部中断属于硬件中断.

进程管理

进程和线程

  • 程序存在外存的，执行的时候由操作系统创建进程执行，执行结束，进程消亡，进程是程序的一次执行过程，进程是动态的，程序是静态的.

  • 进程在创建的时候需要给资源，进程是资源管理的基本单位，创建进程对应的就是创建PCB\text{PCB}，进程终止就是删除PCB\text{PCB}，PCB\text{PCB}是进程存在的唯一标识.

  • 进程包含PCB\text{PCB}，程序段，数据段，PCB\text{PCB}里面包含了各种状态信息和进程所需要的资源，进程标识符，用户标识符.

  • 线程就是轻量级进程，由进程创建线程，此时CPU\text{CPU}调度的基本单位是线程，线程共享当前进程的资源，自己几乎不含资源，只有部分运行需要的资源.

  • 线程的调度代价远小于进程，线程的切换不会伴随快表的失效，进程切换回导致快表失效.

  • 进程状态的转换

    • 就绪态，有资源，没有CPU\text{CPU}，存放在就绪队列中.

    • 阻塞态，缺资源，没有CPU\text{CPU}.

    • 运行态，有资源，有CPU\text{CPU}.

    • 就绪态→\rightarrow运行态，获取CPU\text{CPU}调度的过程，低级调度.

    • 运行态→\rightarrow阻塞态，需要等待某些资源.

    • 运行态→\rightarrow就绪态，时间片用完，被其他进程抢占了CPU\text{CPU}.

    • 阻塞态→\rightarrow就绪态，资源到来.

  • 进程的创建

    • 申请PCB\text{PCB};

    • 分配资源;

    • 初始化PCB\text{PCB};

    • 放入就绪队列.

  • 进程的删除

    • 检查进程状态;

    • 若为运行态则直接终止;

    • 结束子孙进程线程;

    • 删除PCB\text{PCB}.

  • 管道系统，用于连接读进程和写进程之间的共享文件.

  • 用户级线程就是用户层面感知的线程，内核级线程就是接受调度的线程.

  • 多对一模型，如果内核级线程阻塞则会导致整个系统阻塞，一对一模型，解决阻塞问题，但是内核级线程较多比较浪费，多对多模型，多个用户级线程对应多个内核级线程，内核级线程个数小于用户级线程，解决上述两个问题.

CPU调度

  • 高级调度（作业调度），将任务实体转化为进程并创建的过程.

  • 中级调度（内存调度），虚拟化内存.

  • 低级调度（进程调度），将就绪队列中的进程进行调度，使其获得CPU\text{CPU}进入执行状态，高级调度是为了低级调度做准备的.

  • 什么时候发生调度

    • 进程正常执行结束或者终止.

    • 进程进入阻塞态.

    • 进程从阻塞态变为就绪态.

  • 不能进行调度的情况

    • 原语

    • 处理中断的过程

  • 典型的调度算法

    • FCFS\text{FCFS}，有利于CPU\text{CPU}繁忙型作业，不利于IO\text{IO}繁忙性，对长作业有利，对短作业不利.

    • SJF\text{SJF}，短作业优先，平均周转时间最短，饥饿，进程长时间得不到响应.

    • 高响应比的优先级调度算法

      • 响应比 ==（等待时间++服务时间）//服务时间.

    • 优先级调度算法

      • 静态优先级，事先确定优先级.
      • 动态优先级，事先确定优先级.

    • 时间片轮转FF\text{FF}

      • 将CPU\text{CPU}时间分为多个时间片，轮流给进程使用.
      • 时间片过大，会退化为FCFS\text{FCFS}.
      • 时间片过小，则会导致进程的频繁切换，影响系统效率.
      • 多级反馈队列调度算法
      • 多个队列，最下层队列使用时间片轮转算法，其余队列使用FCFS\text{FCFS}，上层队列时间片较小，下层较大.
      • 按照队列优先级进行调度.

同步和互斥

  • 同步，进程之间存在先后执行的关系，互斥指同一个时刻只能有一个进程访问资源（互斥资源）.

  • 临界资源，互斥资源，临界区指访问临界资源的一段代码.

  • 互斥的准则，一让进，三等待.

    • 空闲让进，临界区空闲时，可以让一个进程进入访问临界资源.

    • 忙则等待，临界区内有其他进程，当前进程应该等待.

    • 有限等待，等待进程的等待时间是有限的，不是无限.

    • 让权等待，如果当前进程不能进入临界区，则释放处理器.

  • 软件方法实现互斥.

    • 单标志法，turn == 1表示可以让P1P_1进入，等于00表示可以让P0P_0进入，违背了空闲让进，turn == 1表示P0P_0不能进入临界区，如果此时P1P_1也不想进入临界区，违背了空闲让进.

    • 双标志法，flag[] = {true,true}，flag[0] == true P0P_0可以进入，当数组的值都为false的时候，导致两个进程都能进入临界区，违背了忙则等待.

    • 双标志后检查法，先进行标志设置，后进行检查， 两个进程都在while循环处死循环，违背了空闲让进和有限等待.

    • Peterson\text{Peterson}算法，在双标志后检查法的第二行添加turn标志，同一个时刻只能有一种状态，实现互斥.

  • 互斥锁能实现互斥访问变量.

  • 信号量中PV\text{PV}，P\text{P}表示获取许可证，获取不到许可证的进程会被阻塞，V\text{V}表示释放许可证.

    • Semaphore mutex = 1，先P\text{P}再V\text{V}，互斥操作，则中间的代码就是临界区.

    • Semaphore sign = 0，先V\text{V}再P\text{P}，同步操作.

  • 消费者生产者，缓冲区互斥，空间和商品数量同步.

Semaphore mutex = 1;
Semaphore full = 0;
Semaphore empty = n;

Producer{
	while(true){
		P(empty);
		P(mutex);
		放入商品
		V(full);
		V(mutex);
	}
}
Consumer{
	while(true){
		P(full);
		P(mutex);
		拿商品
		V(empty);
		V(mutex)
	}
}
  • 读者优先，对readCount\text{readCount}的互斥，书的互斥.
Semaphore book = 1;
Semaphore mutex = 1;
int readCount = 0;

reader i{
	P(mutex);
	if(readCount == 0){
		P(book);
	}
	V(mutex);
	读书
	P(mutex);
	readCount--;
	if(readCount == 0){
		V(book);
	}
	V(mutex);
}
writer{
	P(book);
	写书
	V(book);
}
  • 写者优先
Semaphore book = 1;
Semaphore mutex = 1;
SemaPhore readAble = 1;

int readCount = 0;

reader i{
	P(readAble);
	P(mutex);
	if(readCount == 0){
		P(book);
	}
    readCount++;
	V(mutex);
	V(readAble);
	读书
	P(mutex);
	readCount--;
	if(readCount == 0){
		V(book);
	}
	V(mutex);
}

writer{
	P(readAble);
	P(book);
	写书
	V(book);
	V(readAble);
}

  • 哲学家进餐问题，当所有哲学家都先拿左手的筷子则会产生死锁，解决办法，让奇数的哲学家先拿左手的筷子，偶数的哲学家先拿右手的筷子.

  • 同步工具管程，保证进程互斥，将访问临界资源的操作进行集中管理，提供条件变量实现进程同步.

  • 每次仅允许一个进程进入管程，局部于管程内的临界资源只能通过管程进行访问.

死锁

  • 两个或者两个以上的进程因为不正当的推进关系导致阻塞，若无外力作用都无法向前推进.

  • 死锁的四个必要条件

    • 互斥，资源是互斥的；

    • 不剥夺，资源不能从其他进程中抢夺；

    • 请求并保持，当前进程获得了部分资源不释放，并请求其他资源；

    • 环路等待，存在环路等待的关系.

  • 预防死锁，破坏死锁发生的四个必要条件

    • 破坏，请求和保持，静态资源分配，如果进程需要的资源不能一次性分配完成则不分配.

    • 破坏，环路等待，资源有序分配，对不同类资源进行编号，只能按照编号递增的顺序进行请求，同类资源一次性申请完，例如两个进程分别需要A\text{A}和B\text{B}资源，系统中只包含一个A\text{A}和一个B\text{B}，则必须先获得A\text{A}才能申请B\text{B}.

  • 避免死锁

    • 安全状态，系统中存在一种状态，进程能按照某种顺序执行，最后所有的进程都能执行完并且不发生死锁，这种状态称为安全状态，如果不存在这种顺序则为不安全状态.

    • 不安全状态不是死锁状态，正常 执行下去一定发生死锁.

    • 银行家算法，计算当前的分配请求是否会导致系统进入不安全状态，如果会则不分配.

  • 死锁检测和解除

    • 死锁定理：当资源分配图是不可以完全简化的时候，系统状态为死锁状态。

    • 死锁解除：

      • 资源剥夺法，将其他进程的资源进行剥夺.
      • 撤销进程，进程直接撤销，则释放资源给其他进程.
      • 进程回退，将进程回退到足以避免死锁的状态.

内存管理

装入

  • 程序的执行包含编译-链接-装入.

  • 装入包含三种

    • 绝对装入，从编译阶段就能知道装入内存的物理地址.

    • 可重定位装入，根据内存的情况，将装入模块放入适当位置，后续不会改变，又叫做静态重定位.

    • 动态重定位，根据内存的情况，将装入模块放入一个相对位置，等到使用的时候再进行调整，需要重定位寄存器支持，只需要装入部分代码就能投入运行.

  • 链接有三种

    • 静态链接，编译完成之后链接成一个整体.

    • 装入时动态链接，在装入的时候采取边装入边链接的方式.

    • 运行时动态链接，当需要使用的时候再进行链接装入到内存中.

  • 内存保护

    • 设置上下限寄存器.

    • 设置基地址寄存器和界地址寄存器.

内存分配

  • 连续分配管理方式

    • 单一连续分配方式，内存分成系统区和用户区，用户区中只能存在一个程序，用户区是给这一个程序所使用的，产生内部碎片（剩余空间部分是处于已经分配内存的内部），适用于单道操作系统.

    • 固定分区分配，将内存进行分区，每次将程序放入能放得下的内存区域，如果内存分区大小相等，则会导致大程序放不进，如果大小不等，能解决问题，产生内部碎片.

    • 动态分区分配，事先不将内存分区，当程序需要多大空间就创造一个多大的分区进行分配，产生外部碎片.

      • 首次适应，空闲分区按照地址递增进行排序，选择第一个符合的空闲分区进行分配，低地址部分会产生小碎片.
      • 邻近适应，上一次分配地址继续向后寻找.
      • 最佳适应，将空闲分区按照大小递增排序.
      • 最坏适应，将空闲分区按照大小递减排序.

  • 基本分页存储管理方式，离散的分配管理方式，将内存分成多个大小相同的页，内部碎片.

    • 页=物理块，分配的基本单位，物理块的大小=页的大小.

    • 页表，包含页表项，页表项表示了逻辑页号到物理页号的映射，页内偏移的位数等于log⁡页大小\log^{页大小},页表项的位数就等于log⁡块数目\log^{块数目}，页表的大小=页表项的大小∗*项数，页表中不存储虚页号.

    • 逻辑地址转物理地址的过程

      • 逻辑地址中包含虚页号，页内位移.
      • 虚页号（P\text{P}）通过PTR\text{PTR}中的页表长度进行越界判断.
      • PTR\text{PTR}中的页表起始地址++页表项大小∗*虚页号P=\text{P}=页表项的地址.
      • 通过页表项地址拿到对应的实页号b\text{b}，就是物理块号.
      • 物理块号b\text{b}和偏移量W\text{W}进行拼接得到物理地址（b\text{b}）.

    • 不太适合共享，地址是一维的.

  • 基本分段存储管理方式

    • 适合共享，将程序分为多个段，每个段的大小不相等，产生外部碎片.

    • 段表包含 段号，段长，段起始地址.

    • 逻辑地址转物理地址的过程

      • 段号从段表寄存器进行越界判断.
      • 通过段号查表，段表项地址==起始地址+段表项大小∗*段号，得到段长，段长和偏移地址进行第二次越界判断.
      • 拿到段的起始地址++偏移量得到对应物理地址.
      • 地址是二维的.

文件系统

文件系统布局

  • MBR\text{MBR}主引导记录用来引导计算机启动.

  • 引导块负责启动操作系统.

  • 超级块包含文件系统的所有信息.

  • 整个系统的文件打开表包含每个打开文件的FCB\text{FCB}副本，打开计数和其他信息.

  • 进程的文件打开表包含文件的描述符信息（不是文件）和指向整个系统文件打开表的指针.

  • 管理空闲空间的方式

    • 空闲表法，用表概括空闲分区所包含的盘块数.

    • 空闲链表法，用链表将空闲分区链接.

  • 成组链表法

输入输出系统

IO管理描述

  • IO\text{IO}的编址方式

    • 统一编址，用一块主存地址空间进行统一编址，不需要设置专门的IO\text{IO}指令，占用了部分主存空间.

    • 独立编址，为每一个端口分配一个IO\text{IO}端口号，寻址速度快，灵活性较差.

  • 设备驱动，每一类设备有一个驱动.

SPOOLing技术

  • 缓冲区是内存中的缓冲区，输入输出井在磁盘中.

  • 因为缓冲区提高了IO\text{IO}速度，将独占设备改造为共享设备，为进程分配的不是设备本身，对每个进程而言都认为自己获得了设备.

  • 改善磁盘IO\text{IO}性能的方式

    • 采用高速缓存.

    • 调整访问顺序.

    • 提前读.

    • 延时写.

终将美好，我们的春夏秋冬。
Copyright © 2023-present Liang