operating-system-note

操作系统保研笔记

进程调度算法

先来先服务调度算法(FCFS)是按照进程到达的先后顺序进行调度

最短作业优先调度算法(SJF)是按照进程执行时间长短进行调度，改为抢占式后诞生最短剩余时间优先（SRTF），存在饥饿问题

最高响应比优先（HRRF）是计算每个作业的响应比，选择响应比最高的先执行，响应比为1+已等待时间/要求运行时间

优先级调度算法是给每一个进程分配一个优先级，按照优先级高低进行调度

时间片轮转调度算法(RR)是每个进程轮流分配时间片，时间片到了或进程执行完成则切换下一个进程调度

多级反馈队列调度算法是将进程分配到不同的队列，每个队列时间片不同，根据优先级和队列进行调度(优先级不断下降，时间片不断增长)

windows使用多级反馈队列调度算法，linux使用时间片轮转调度算法

实时调度算法由最早截止时间优先和单调速率调度

页面置换策略

常见的分为最优置换，先入先出算法，LRU

最优置换是换掉未来最久不会被使用的页，需要先验知识，因此无法被实现，理论最优解

先入先出算法存在Belady现象，即分配页面增多，缺页率反而高

计算机是如何启动的

BIOS–>主引导程序–>硬盘启动–>操作系统启动

BIOS是什么

BIOS是Basic Input Output System，是固化到计算机主板上的一个ROM程序，主要保存自检程序和系统装载程序

自己OS课做了什么

我们用c语言编写了一个小型的操作系统，支持内存管理，进程管理，文件系统和磁盘读写等基本功能，我们在这个过程中模拟了操作系统启动的基本流程，如何建立内存管理机制，如何进行进程创建、时钟中断和异常处理和进程调度，如何创建系统调用并实现进程间通信，以及一些基本的文件系统，最后我们在lab6和它的challenge中实现了一个shell可以真正用我们的操作系统实现一些可视化的功能。

进程有哪些状态，它们之间如何切换

进程有新建、就绪、运行、阻塞和终止五个状态。

进程在运行过程中的状态切换由操作系统的调度器进行控制，当进程创建时为创建状态，当调度器分配CPU资源给该进程后，处于就绪状态;当该进程被调度执行时进入运行状态;当进程需要等待某个事件发生时，进入阻塞状态，当执行完毕或者异常终止进入终止状态，如果时间片到了进程没有执行完则返回就绪状态

进程同步的意义

进程同步的意义在于确保多个进程能够有序地访问和使用共享资源，从而避免数据竞争和死锁等问题的发生，常用的有信号量机制和互斥锁等方式来实现对共享资源的合理使用。

这里的共享资源包括共享内存、共享文件、共享设备等

临界区

一次仅允许一个进程访问的资源称为临界资源，进程访问临界资源的程序段叫临界区

进程间通信

在windows和linux系统中，进程间通信(IPC)是实现进程间数据共享和共享资源的重要手段，常用的有信号量、消息队列、管道（父子进程或兄弟进程）和共享内存等方式

死锁的条件、解决方法和预防办法

死锁是指两个或多个程序互相持有对方所需的资源而陷入的一种僵局，无法继续执行。

死锁需要满足四个条件——互斥条件、请求和保持条件、不剥夺条件、循环等待条件

为了避免死锁，可以采用预防死锁的方式即破坏死锁满足的四个条件之一来实现，还可以采用避免死锁的方式，入采用银行家算法判定当前是否会发生死锁，如果会发生则不分配资源。

银行家算法

银行家算法是通过安全检测来预防死锁的发生，核心思想是每当一个进程请求资源时，系统会检查此次请求是否安全来决定是否分配资源

线程与进程的联系和区别，为什么要引入线程

进程是程序的一次执行，具有动态性，并发性，独立性和异步性等特征（独立性指进程是独立执行的基本单位），正常由数据段，代码段和进程控制块PCB组成

线程和进程都是操作系统资源调度和分配的基本单位，拥有自己的程序计数器、寄存器、堆栈等运行时状态，可以与其他进程或线程进行通信

区别方面，进程是资源分配的最小单位，而线程是CPU调度的最小单位，一个进程可以有多个线程组成，每个线程只属于一个进程，同时进程拥有独立内存空间，切换开销较大，而线程共享进程的内存空间，切换开销较小

用户级线程和内核级线程，用户级线程切换与内核无关，容易优化，但会阻塞整个进程

虚拟存储管理

虚拟存储管理实现了虚拟内存到物理内存之间的映射，使得程序可以使用比物理内存更大的地址空间，提高系统利用率。但虚拟存储管理需要进行页面的映射和替换增加了时间和空间开销，且页面大小固定会无法适应不同程序的内存需求

页式和段式存储管理

页式存储可以很好解决外碎片的问题，因为每个页面大小固定便于释放。

分页会产生内碎片，因为程序使用的内存很可能不是页面大小整数倍

段式存储管理中一般用户按照逻辑关系对作业分段，通常一个作业由多个程序段和数据段组成，并能通过名字访问对应字段，易于实现对段的共享和保护，但由于段大小不固定，会存在外碎片，且处理花费时间更长

页式信息的物理单位，段是信息的逻辑单位，并诞生了段页式存储管理，即用分段方式管理虚拟存储器，用分页方式管理实存储器

进程上下文切换的具体过程

保存上下文、更改PCB和相关队列、调度新进程、新进程改为运行态、修改TLB和页表的信息，将PC指向进程代码段

介绍一下中断和异常

异常可以细分为异步异常和同步异常，其中异步异常就是中断，中断主要有I/O设备、处理器时钟或者定时器等硬件产生，除此之外异常还包括陷阱如常见的系统调用，故障如缺页异常，除0异常等以及终止如硬件本身的错误

内碎片和外碎片

内部碎片是指分配给作业的存储空间中未被利用的部分，内部碎片无法被整理，它已经随着作业被分配出去了，只是没被利用。

外部碎片是指系统中无法利用的小的空闲分区，是分区与分区之间的碎片，动态分区管理会产生外部碎片，外部碎片可以通过紧凑技术整理后清除。

存储分配的分区管理方式分为固定分区和可变式分区，固定分区没有外碎片，可变式分区没有内碎片

常用的内存分配算法

分为四种，分别是首次适应算法，下次适应算法，最佳适应算法和最坏适应算法

如何将一个源程序变成在内存中执行的程序

首先要通过编译程序将源程序变成若干目标模块，之后通过链接程序将目标模块和库函数链接成可装载模块，最后将可装载程序载入内存。

这里链接分为静态链接和动态链接，即是否在程序运行需要目标模块时才载入

程序，进程和作业

程序是静止的，是存放在磁盘上的可执行文件。

进程是动态的，进程包括程序和程序处理对象（数据集），是一个程序对某个数据集的执行过程，是分配资源的基本单位，有自己的生存周期。

作业是用户需要计算机完成的某项任务。

介绍一下MMU

MMU是存储管理单元，是为了提高地址转化效率设置的CPU内部的一个硬件单元，其主要包括TLB，TLB控制单元和页表查询单元，TLB可以理解为是页表的Cache用于快速访问虚拟地址和物理地址之间的映射，TLB控制单元控制TLB的行为，页表查询单元是在TLB没有命中时进行页表查询

多级页表，继续破除页表存储连续性假设

程序并发执行时的特征

间断性：并发程序具有“执行，暂停，执行”的间断性活动规律

非封闭性：多个程序共享系统资源，程序间可能相互影响

不可再现性：初始条件相同可能出现不同执行结果

访问临界区的原则

空闲让进，忙则等待，有限等待，让权等待（释放CPU,避免忙等）

CPU调度的高级调度、中级调度和低级调度

高级调度，又称作业调度，决定哪些作业从外存加载到内存，每个作业只调入一次。中级调度也称交换调度，用于将暂时不需要执行的进程从内存交换到外存，暂时挂载，以释放内存空间，当资源充足时，再将其换回内存。低级调度，负责决定在内存中的哪一个进程将获得CPU的使用权，它通过调度算法选择并分配CPU资源。

假脱机技术

利用假脱机技术可把独享设备转变成具有共享特征的虚拟设备，从而提高设备利用率。

操作系统定义

操作系统是计算机系统中的核心软件，它管理计算机硬件和软件资源，并为应用程序提供基础服务。操作系统的主要功能包括进程管理、内存管理、文件系统管理和设备管理。通过调度算法，操作系统确保各个进程能有效地共享CPU资源，优化系统的性能。内存管理负责分配和回收内存，确保各个进程能够安全地访问内存。文件系统管理提供文件的存储、检索和保护机制，使用户和程序能够方便地存取数据。此外，操作系统还提供用户接口，通常是命令行或图形用户界面，使用户能够与计算机进行交互。常见的操作系统包括Windows、Linux、macOS和Android等。操作系统是计算机运行的基础，决定了系统的效率和稳定性。

操作系统的特征

并发，共享，虚拟，异步