操作系统复习

一,引论

1.3 os的基本特征🍪

并发

并发是指操作系统能够同时处理多个任务或进程。这些任务可以在同一时间段内交替执行，或者在多个处理器上并行执行。并发的实现可以通过时间片轮转调度算法、多线程、多进程等技术。并发性可以提高系统的资源利用率和响应能力。

共享

共享是指操作系统能够让多个用户或多个程序同时访问和使用系统的资源。这些资源可以是处理器、内存、磁盘、网络等。共享的实现需要操作系统提供适当的机制，如进程间通信、文件系统等。共享可以提高系统的效率和资源利用率

虚拟

虚拟化是指操作系统能够为应用程序提供一个虚拟的执行环境，使其感觉自己拥有独占的资源。虚拟化可以分为多种类型，如硬件虚拟化、内存虚拟化、网络虚拟化等。通过虚拟化，操作系统可以提供更高的灵活性和可扩展性，同时实现资源的隔离和安全性。

异步

由于资源等因素的限制，进程的执行不能一气呵成，只能走走停停，虽然速度不可预知但是结果都是相同的

异步是指操作系统能够以非阻塞的方式处理多个任务或事件。在异步模式下，操作系统可以同时进行多个操作，而不需要等待每个操作的完成。这样可以提高系统的响应性能和效率。异步操作通常与事件驱动的编程模型结合使用，如回调函数、消息队列等。

之间的关系

这些特征之间存在着紧密的联系。并发性和共享性为操作系统提供了处理多个任务和资源共享的能力。虚拟化提供了资源的抽象和隔离机制，使应用程序能够在虚拟环境中运行。异步性使得操作系统能够同时处理多个任务或事件，提高系统的并行性和响应性能。

1.4 操作系统运行环境

硬件支持

引导程序在固件中

引导程序知道如何加载内核

操作系统内核

支撑功能

1. 中断处理
   (有限处理)
2. 时钟管理

​ 每次时间片用完都会由时钟管理产生一个中断信号,促使程序重新进行调度

3. 原语操作
   原语操作由若干条指令组成,是原子操作

资源管理功能

1. 进程管理
2. 存储器管理
3. 设备管理

中断与异常

1.5 操作系统的主要功能🌝

os的主要目的是为多道程序运行提供良好的运行环境

处理机管理

1. 进程控制

主要功能:为作业 创建进程,撤销(终止)已结束进程,控制进程在运行过程中状态的转换

2. 进程同步

两种协调方式:1.互斥,2.同步

互斥通过为临界资源加锁实现,进程同步通过信号量机制实现

3. 进程通信
4. 调度
   1. 作业调度
   2. 进程调度

存储器管理

1. 内存分配和回收
   1. 静态分配
   2. 动态分配
2. 内存保护
3. 地址映射
   程序和内存地址的映射
4. 内存扩充
   1. 请求调入
   2. 置换
      发生在内存空间不够用的情况下

设备管理

1. 缓存管理
   解决cpu和io设备速度不匹配的问题
2. 设备分配
   为进程分配设备(通过设备控制表,控制器控制表等数据结构记录设备和设备控制器的标识符和状态)
3. 设备处理
   设备驱动作用

文件管理

实现文件存储空间管理,目录管理,文件的读写管理和保护等功能

1. 文件存储空间管理
   为每个文件分配必要的存储空间,拥有数据结构,可以记录文件存储空间的使用情况
   对存储空间进行分配和回收
2. 目录管理
   为每个文件建立目录项,目录项,目录项包括文件名,文件属性,文件在磁盘上的物理位置等
3. 文件读写和保护

接口管理

用户接口

1. 联机用户接口

   shell

2. 脱机用户接口
   批处理命令,例如shell脚本

3. 图形接口

程序接口

调用函数的接口等

1.6 操作系统结构

简单结构

模块化结构

分层结构

微内核结构

外核结构

• 外核结构：外核结构允许应用程序直接访问和管理硬件资源，因此应用程序可以更灵活地控制资源的使用和优化。应用程序可以自定义外核库，实现自己的资源管理策略。
• 微内核：微内核将资源管理的责任交给用户空间的服务进程。内核只提供最基本的资源分配和保护机制，而具体的资源管理则由独立的用户空间进程实现。

二，进程的描述和控制

2.1进程描述

2.1.1进程的概念

为什么要有进程(来自chatgpt)

进程在计算机系统中扮演着重要的角色，主要有以下几个原因：

并发执行：进程允许多个程序同时运行，从而实现并发执行。通过多进程的方式，可以同时执行多个任务，提高系统的效率和资源利用率。

资源管理：进程提供了一种机制来管理系统资源，如内存、文件、设备等。每个进程都有自己的地址空间和资源表，操作系统可以通过进程控制块（PCB）来跟踪和管理进程的状态、资源分配等信息。

隔离性：每个进程都在独立的地址空间中运行，相互之间不会干扰。这种隔离性可以保证进程之间的数据和状态互不影响，提高了系统的稳定性和安全性。

独立性：每个进程都是一个独立的执行实体，具有自己的代码、数据和执行环境。进程之间可以独立地进行资源分配、调度和执行，从而实现灵活的应用程序设计和管理。

进程间通信：进程可以通过进程间通信（IPC）机制进行数据交换和协作。通过共享内存、消息传递、管道等方式，进程可以在需要时相互通信，实现数据共享和协同工作。

异步操作：进程可以以异步的方式执行任务，即一个进程可以执行自己的任务，而不需要等待其他进程的完成。这种异步操作使得系统能够同时进行多个独立的任务，提高了系统的响应性和并发能力。

综上所述，进程在操作系统中扮演着重要的角色，通过并发执行、资源管理、隔离性、独立性、进程间通信和异步操作等特性，实现了多任务处理和资源利用的优化。

为什么进程可以允许程序同时运行

进程允许多个程序同时运行的主要原因是操作系统的调度和资源管理机制。

在操作系统中，有一个称为进程调度器的组件负责决定哪些进程应该在给定的时间片内获得 CPU 的执行时间。通过使用调度算法，操作系统可以公平地分配CPU时间片给不同的进程，从而实现多个程序的同时运行。

此外，操作系统还提供了资源管理的机制，如内存管理、文件系统、设备驱动程序等，用于分配和管理系统资源。每个进程都有自己的地址空间和资源表，操作系统可以根据进程的需求来分配和管理资源。

通过进程调度和资源管理，操作系统能够将 CPU 时间和其他系统资源按照一定的策略分配给多个程序，使它们可以同时运行。这种并发执行的机制提高了系统的效率和资源利用率，使多个程序能够在同一个系统中独立地执行，从而满足用户的多任务处理需求。

我的理解:普通程序在设计的时候我们不会考虑执行到哪个状态拥有资源,还有地址空间等信息,所以我们需要引入进程这个结构包装一下

进程作为程序的执行实体，包含了程序的代码、数据、执行环境和资源管理信息等。进程提供了一个隔离的执行环境，每个进程拥有独立的地址空间和资源表，使得不同的程序能够在同一个系统中并发执行，而互不干扰。

通过进程的包装，操作系统可以对进程进行调度、分配资源和管理状态，从而实现多任务处理和资源利用的优化。进程提供了一个执行上下文，使得程序能够被加载到内存中执行，并能够访问所需的资源。同时，进程间通信和同步机制也通过进程的概念来实现。

因此，引入进程这个结构是为了将普通程序与计算机系统的执行环境、资源管理和并发执行机制进行适配，从而使得程序能够在系统中正确运行，并能够同时执行多个程序

定义:(不同角度)

1. 进程是程序的一次执行

2. 进程是一个程序及数据在处理机上顺序执行的时所发生的的活动

3. 进程是有独立功能的的程序在一个数据集合上运行的过程,是系统进行资源分配和调度的一个独立单位

组成:

进程由程序控块pcb,程序段,数据段组成

• PCB: PCB中应该包含操作系统对其进行管理所需的各种信息，如进程描述信息、进程控制和管理信息、资源分配清单和处理机相关信息。
  (我的理解是各种原信息,起到识别和控制的作用)
• 程序段:程序代码存放的位置。
• 数据段:程序运行时使用、产生的运算数据。如全局变量、局部变量、宏定义的常量就
  存放在数据段内。

PCB

• pcb的作用

  • 作为独立运行基本单位的标志
  • 能实现间断性运行方式
  • 能提供进程管理 所需要的信息
  • 能提供进程调度所需要的信息
  • 能实现和其他进程的同步和通信

• pcb所包含的信息

  • 进程标识符
  • 处理机状态
  • 进程调度信息
  • 进程控制信息

• pcb 的组织方式

  • 线性方式
  • 链接方式
  • 索引方式

进程的特征

• 动态性:动态的产生变化和消亡

• 并发性:内存中有多个进程实体,各进程可并发操作(毕竟一开始进程的出现就是为了解决原本程序并发会出现失去了可再现性)

• 独立性:独立的运行,获取资源,独立接收调度的基本单位(不怎么理解)

• 异步性:各个进程按各自独立的、不可预知的速度向前推进，操作系统要提供进程向步机制来解决异步问题。

• 结构性:结构上来看,进程由程序段,数据段和PCB组成

mindmap
进程的特征[动态性](并发性)((独立性))))异步性(()结构性(

2.1.2进程的状态

一般来说进程有五个状态:就绪状态,运行状态,阻塞状态创建状态,终止状态组成,前三个是基本状态

就绪态:

进程状态的切换

阻塞 -> 就绪 ->运行

阻塞->运行 and 就绪->阻塞不可能发生

2.2 进程通信

低级通信:pv操作

高级通信:

高级通信

1. 共享存储系统

   1. 共享数据结构
   2. 共享存储区

2. 管道通信

   • 连接一个读进程和一个写进程以实现通信的文件,pipe文件

3. 消息传递

   利用原语进行通信

   1. 直接通信
   2. 间接通信

三,处理机调度和死锁

3.1 处理机调度概述

作业通常是指用户在一次计算过程中或者一次事物处理过程中要求计算机系统所做工作的集合,包括用户程序、所需的数据及命令等。进程是具有独立功能的可并发执行的程序在一个数据集合上的运行过程,是系统进行资源分配和调度的独立单位。作业和进程之间的区别和联系如下:

1.作业是用户向计算机提交的任务实体,而进程则是完成用户任务的执行实体,是向操作系统申请分配资源的基本单位。

2.一个作业可以由多个进程组成,且一个作业至少由一个进程组成。

调度层次

高级调度

调度作业

中级调度

调度内存

低级调度

调度进程

3.2 调度算法 🎃

先来先服务(FCFS)

选择队头的进程为之分配处理机

缺点:很多很多,比如第一个进程很长的话后面会有很多进程一直在等待,而且也没有考虑进程的重要性啥的

短作业优先调度(SJF)

作业所要求的的运行时间越短,越优先执行

缺点:

1. 很难估计作业所需运行时间
2. 忽视了作业等待时间,可能会使作业的等待时间过长
3. 无法实现人机交互(我的理解是程序的运行次序都定死了)
4. 不能使紧迫的作业得到及时处理和FCFS同样的缺点

优先级调度算法

貌似前面的俩家伙都算是优先级调度算法

但是这里的优先级是基于进程的紧迫程度

优先级调度算法类型

（1）非抢占式优先权调度算法

系统一旦把处理机分配给优先权最高的进程后，便一直执行下去，至完成。

（2）抢占式优先权调度算法

只要系统中出现一个新的就绪进程，就进行优先权比较 。若出现优先权更高的进程，则立即停止当前执行，并将处理机分配给新到的优先权最高的进程。

(你强,但是我比你更强😼,直接interrupt you)

优先级类型

1. 静态优先级

   进程创建时候确定

   依据:

   • 进程类型(系统>用户)
   • 进程对资源的要求(少的优先)
   • 用户要去

2. 动态优先级

   • 随着时间的推迟,进程的优先级会发生变化

3. 高响应比优先调度(HRRN)

$$优先级=\frac{等待时间+要求服务时间}{要求服务时间}$$

轮转调度算法(RR)😫

没看懂书上的

多级队列调度算法

不同

四,进程同步🧐

4.1 进程同步和互斥

基本概念

1. 临界资源

   临界资源是一次只允许一个进程访问的资源,各个进程以互斥的方式实现共享

2. 临界区
   每个资源访问临界区的那段代码就是临界区,每次都只有一个进程进入临界区,就比如打印机,每次正在使用的人只有一个

   临界资源的访问过程分为4个部分:
   a.进入区。负责检查是否可以进入临界区,设置正在访问临界资源的标志。(相当于上了把锁)

   b.临界区。访问临界资源的那段代码。

   c.退出区。负责解除正在访问临界资源的标志。

   d.剩余区。做其他处理。

同步机制应该遵循的准则

这些准则的目的是为了实现进程互斥的进入自己的临界区

1. 空闲让进
2. 忙则等待
3. 有限等待 (我只等有限的时间,超过这个时间就不等了)
4. 让权等待 (这个不是必须的) 我不能进入自己的临界区了,就释放掉处理器那些资源,以防进入忙等

信号量机制😥

这是为了解决同步和互斥问题的

信号量机制是一种功能较强的机制，可用来解决互斥和同步问题，它只能被两个标准的原语wait(S)和signal(S)访问，也可记为“P操作”和“V操作”。

1. 整型信号量

整型信号量被定义为一个用于表示资源数目的整型量S。P和V操作可描述为:
wait(S){
while(S<=0); 这里是如果S资源<=0的情况下是一直在等待资源的到来
S=S-1;}

signal(S){
S=S+1}
该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。

2. 记录型信号量

记录型信号量是不存在“忙等”现象的进程同步机制。除需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L,用于链接所有等待该资源的进程。

typedef struct{int value;struct process *L}
semaphore;
void wait(semaphore S){s. value - - ;
if(S. value<0){add this process to S.L; //如果资源<0就挂到阻塞队列里面去block(S. L);}}
void signal (semaphore *S){S. value++;if(S.value<=0){  //释放资源的时候如果value<=0那说明队列中有进程还在被阻塞,然后就释放队列中的第一个进程 	remove a process to S.L;wakeup(P);
}}

信号量的应用

1.互斥

相当于一把锁的作用,拿资源的时候上锁,使用完资源释放锁

2.同步

如果进程是先执行v操作的话,s+1变为1,然后可以进行p2执行C2,如果是先执行p操作的话s=-1,会把自己阻塞,只有p1执行v操作后才会释放阻塞

这样保证了c1一定是在c2之前执行的.

总结:

（1）同步信号量，值为资源可以使用的个数，信号量小于0，则线程进行等待，信号量大于0，表示可用资源个数。初始值一般为0.
（2）互斥信号量只有两个值0或1，0表示资源正在被占用，线程等待。1表示，资源没有被使用，线程可以进入。初始值为1

4.2 使用信号量解决同步问题

基本解题步骤

PV操作题目分析的步骤:
①关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
②整理思路。根据各进程的操作流程确定操作的大致顺序。
③设置信号量。设置需要的信号量，并根据题目条件确定信号量的初值。

如何实现
互斥的实现是在同一个进程中进行一对PV 操作。
同步的实现是在两个进程中进行，在一个进程中执行P操作，在另一个进程中执行v操作。

生产者消费者问题

需要注意的是互斥操作在一个个进程内成对出现,同步操作在不同进程之间同步出现

为什么这样安排？可能是因为互斥操作必须紧邻“临界区”的缘故。互斥操作要紧邻临界区，才能充分地发挥作用。这里也就是把产品放入缓冲区或者拿出缓冲区的操作

读者-写者问题

两个并发进程共享一个文件，当两个或两个以上的读进程共同访问数据时不会产生副作用。但多个写进程同时访问数据可能会导致数据不一样。因此要求：允许多个读者可以同时对文件进行读操作。只允许一个写者往文件里写信息，在任一写者完成操作前不允许其他读者或写者工作，写者执行操作前应该给让所以其余的读者或写者退出。

算法：在上锁前进行判断，第一个读进程负责加锁，最后一个读进程负责解锁，其中还有个互斥信号量保证对读者数量的互斥操作,在这两个过程中要设置互斥变量来保证检查与赋值一气呵成。在写进程的前后设置PV，在读进程前设置PV，保证读写进程有序进行，不会出现饥饿。

哲学家就餐问题

圆桌上两个哲学家中间有一根筷子，每个哲学家只能用他两边的筷子吃饭，一旦缺少一根进程就会被阻塞。

算法：设置信号量数组chopstick[5] = {1,1,1,1,1},每个哲学家i左边的筷子编号为i，右边的筷子编号为（i+1）%5.每个哲学家先对左右两边的筷子进行P操作，在完成进程后再对两边进行V操作。

如果不加条件，如果所有哲学家并发用餐就会出现死锁现象。

可以添加的条件：1.限制最大进餐人生；2，对于奇数号哲学家先拿左边的筷子，对于偶数号的哲学家先拿右边的筷子。（用争抢防止阻塞）；3.仅当哲学家左右两只筷子都可用时才允许他抓起筷子

4.3 管程

管程（Monitor）是一种用于实现并发控制的编程机制。它提供了一种结构化的方式来管理共享资源的访问，并确保线程之间的同步和互斥。管程机制最初由荷兰计算机科学家Edsger Dijkstra在1965年提出，并在之后的几十年中得到了广泛应用和研究。

管程的基本思想是将共享资源和对该资源的操作封装在一个单元内部。这个单元包含了用于操作共享资源的一组过程或方法，以及用于同步和互斥的机制。通过使用管程，可以确保只有一个线程能够同时访问共享资源，从而避免了竞态条件和数据不一致性的问题。

管程机制通常包括以下几个关键要素：

1. 数据结构：管程内部包含一个或多个共享资源，可以是变量、队列、缓冲区等。这些数据结构被管程的过程所使用和操作。
2. 过程（Procedure）：管程内部定义了一组过程或方法，用于对共享资源进行操作。每个过程都是原子性的，一次只能由一个线程执行。通过调用这些过程，线程可以安全地访问和修改共享资源。
3. 条件变量（Condition Variable）：管程中的条件变量用于实现线程之间的等待和通知机制。线程可以通过等待一个条件变量来释放对共享资源的占用，并暂时阻塞。当某个条件满足时，其他线程可以通过通知条件变量来唤醒等待的线程。
4. 互斥锁（Mutex）：管程通常使用互斥锁来实现对共享资源的互斥访问。只有获取了互斥锁的线程才能执行管程内部的过程。其他线程必须等待互斥锁的释放才能执行管程中的操作。

管程机制的优点在于提供了一种高级抽象的并发控制方式，使得程序员能够更方便地编写并发代码。通过将共享资源和操作封装在管程内部，可以减少竞争条件和死锁等并发问题的出现。此外，管程的条件变量和互斥锁提供了线程之间的同步和互斥机制，可以确保线程按照预期的顺序访问共享资源。

需要注意的是，管程并不是一种语言提供的原生机制，而是一种抽象的概念。不同的编程语言和环境提供了不同的实现方式，如Java中的synchronized关键字和wait/notify机

在Java中，可以使用synchronized关键字和wait()/notify()方法来实现管程的功能。下面是一个使用管程的简单示例：

class Monitor {private int sharedData;public synchronized void processData() {// 管程过程：对共享资源进行操作// 在管程过程中可以使用synchronized关键字确保互斥访问// 例如，这里可以修改sharedData的值sharedData = 10;// 唤醒等待的线程notify();}public synchronized void waitForData() throws InterruptedException {// 管程过程：线程等待共享资源的条件// 在管程过程中可以使用synchronized关键字确保互斥访问// 例如，这里可以检查sharedData的值是否满足特定条件while (sharedData != 10) {// 等待共享资源满足条件wait();}// 共享资源满足条件，执行后续操作}
}

在上述示例中，Monitor类代表了一个简单的管程，其中包含了两个管程过程：processData()和waitForData()。这两个过程都使用了synchronized关键字，以确保在同一时间只有一个线程可以进入管程执行过程。

在processData()过程中，共享资源sharedData被修改，并通过notify()方法唤醒等待的线程。

在waitForData()过程中，线程会等待共享资源满足特定条件。如果共享资源的值不满足条件，线程会调用wait()方法进入等待状态，释放锁并让其他线程执行。一旦共享资源满足条件，其他线程通过notify()方法唤醒等待的线程。

请注意，以上示例仅为演示如何使用synchronized、wait()和notify()来实现管程的基本功能。在实际开发中，可能需要更复杂的管程实现，例如使用ReentrantLock和Condition等类来实现更灵活的管程机制。

语言基本上本身不提供管程的实现

在其他编程语言中，有些语言提供了原生的管程机制，而有些语言则需要使用特定的库或框架来实现管程功能。以下是一些常见编程语言的管程实现方式：

1. C/C++：C/C++本身没有原生的管程机制。但是可以使用线程库（如pthread）提供的互斥锁（mutex）和条件变量（condition variable）来实现管程。通过使用互斥锁和条件变量，可以实现对共享资源的互斥访问和线程之间的同步。

2. Python：Python提供了threading模块和Lock、Condition等类来支持管程的实现。可以使用Lock类来实现互斥访问，使用Condition类来实现等待和通知机制。

3. C#：C#提供了Monitor类来实现管程。可以使用Monitor类的方法如Enter()、Exit()、Wait()和Pulse()来实现互斥访问和线程等待和通知。

4. Rust：Rust通过标准库提供了std::sync::Mutex和std::sync::Condvar等类型，用于实现管程。Mutex用于实现互斥访问，Condvar用于实现线程等待和通知。

5. Go：Go语言的并发模型本身就提供了原生的管程机制。通过使用关键字go和chan，可以实现对共享资源的互斥访问和线程之间的同步。

需要注意的是，具体实现方式可能因编程语言和使用的库或框架而有所不同。某些编程语言可能提供了更高级的管程实现，例如活跃对象（Active Object）模型或消息传递机制。在选择编程语言和实现管程时，可以根据具体需求和语言特性来进行选择。

管程相对于普通方式实现同步和互斥具有以下优点：

1. 结构化：管程提供了一种结构化的编程方式，将共享资源、操作和同步机制封装在一个单元内部。这样可以更清晰地组织代码，使得并发控制的逻辑更易于理解和维护。
2. 简化同步：使用管程可以简化同步的实现。管程内部的互斥锁和条件变量可以由编程语言或框架提供，减少了手动实现同步的复杂性。开发者可以专注于共享资源的操作，而无需显式处理底层的同步机制。
3. 避免竞态条件：管程通过互斥访问共享资源，确保同一时间只有一个线程可以访问。这样可以避免竞态条件的出现，即多个线程同时对共享资源进行修改导致不确定的结果。
4. 避免死锁：管程内部的同步机制可以帮助避免死锁的发生。通过使用条件变量来等待和通知线程，可以确保线程之间按照预期的顺序进行同步，避免了死锁的可能性。
5. 提高可扩展性：管程提供了一种高级抽象，可以更容易地实现并发控制。通过将共享资源和相关操作封装在管程内部，不同的线程可以独立地调用管程过程，从而提高了代码的可扩展性和重用性。

总而言之，管程提供了一种结构化、简化和安全的方式来实现并发控制。它可以帮助开发者避免常见的并发问题，提高代码的可读性和可维护性，同时提供了更高层次的抽象，使并发编程更加容易和安全。

五,存储器管理

高速缓存和磁盘缓存的区别是高速缓存是为了减少处理机对内存的访问次数,以提高程序的执行速度,并且它是一个实际存在的存储器,而磁盘缓存本身并不存在,而是利用内存中的部分存储空间.

5.1 程序的装入与链接

1. 编译
2. 链接
3. 装入
   • 由装入程序将装入模块装入内存

1.地址绑定与内存保护

需要完成逻辑地址到物理地址的变换

内存保护

在地址变换过程中我们需要保证os不被用户访问和其他进程不受干扰.

这需要确定一个进程的合法地址范围,通过基地值寄存器和界限寄存器来实现保护

基地址<=物理地址<(基地址+界限地址)

2.程序的装入🍤

1. 绝对装入方式
2. 0可重定位方式
3. 动态运行时装入方式
   • 在把装入模块装入内存后,并不会立即将装入模块的相对地址变换为绝对地址,而是推迟到执行时才进行

5.2 覆盖与交换

1.覆盖

思想:将程序分为多个段(多个模块).常用的段常驻在内存,不常用的段在需要时调入内存

把内存划分为一个固定区和若干个覆盖区，固定区存放用户程序经常活跃的部分，调入后就
不再调出(除非运行结束)，其余部分按调用大尔力权w1B田前系依将L调入覆盖区，替换原有调入内存，用不到时调出内存。其他放在外存，在需要调用前，系统将其调入覆盖区，替换原有
的段。必须由程序员声明覆盖结构，操作系统完成自动覆盖。

2.交换

把处于等待状态的进程或者被CPU剥夺运行权限的进程从内存移出到外存，这一过程称为换出;把准备好竞争CPU的进程从外存移到内存，这一过程称为换入。
暂时换出外存等待的进程状态为挂起状态(挂起态)。
挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。

5.3 连续分配存储管理方式

连续分配方式可分为三类:单一连续分配、固定分区分配、动态分区分配。

1.单一连续分配

内存分为系统区和用户区

特点:
内存中只能有一道用户程序，用户程序独占整个用户区空间。优点:实现简单;
无外部碎片;
可以采用覆盖技术扩充内存;

2.固定分区分配

分区大小的预分配可能会导致内存浪费或分配不足的问题。

• 分区大小相同的方式
• 分区大小不等的方式

优点:实现简单,无外部碎片。缺点:

1. 当用户程序太大时,可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但又会降低性能;

2. 会产生内部碎片,内存利用率低。

题1.分区分配内存管理方式的主要保护措施是().

A．界地址保护
B.程序代码保护
C．数据保护
D.栈保护
解析:分区分配存储管理方式的保护措施是设置界地址寄存器。每个进程都有自己独立的进程空间，,如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。当程序要访问某个内存单元时，由硬件检查是否允许,如果允许则执行，否则产生地址越界中新,
由OS进行相应处理。

3.动态分区分配

动态分区分配又称可变分区分配，是一种动态划分内存的分区方法。
这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区。系统分区的大小和数目是可变的。
两种常用的数据结构:空闲分区表和空闲分区链

首次适应(First Fit)算法。

空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。

最佳适应(Best Fit)算法。

空闲分区按容量递增的方式形成分区链,找到第一个能满足要求的空闲分区。
缺点:会产生很多的外部碎片。

最坏适应(Worst Fit)算法。

又称最大适应(Largest Fit)算法，全内刀区以合里足减人链接，找到第一个能满足要求的空闲分区，即挑选出最大的分区。
缺点:不利于后续大进程使用，会造成后续大进程到达时无内存分区可用。

找到能够容纳该进程大小的最大空闲分区后这个分区没用完的部分怎么处理

当最坏适应算法找到能够容纳进程大小的最大空闲分区后，该分区可能会有一部分空闲空间未被使用。这个未使用的部分可以成为一个新的空闲分区，可以进一步被分配给其他进程。
在处理这个未使用的部分时，通常会更新该分区的大小和位置信息。如果未使用的部分足够大，可以将其标记为一个新的空闲分区，并将其添加到空闲分区列表中，以备后续的内存分配请求使用。
更新空闲分区的大小和位置信息时，需要确保分区之间的内存空间不会出现碎片化问题。这可能涉及到对相邻的空闲分区进行合并，以形成更大的连续空闲区域。通过合并相邻的空闲分区，可以减少碎片化，并提供更大的可用空间来满足较大的内存请求。
总结起来，当最坏适应算法找到最大空闲分区后，未使用的部分可以被标记为新的空闲分区，并添加到空闲分区列表中。在更新空闲分区信息时，可能需要对相邻的空闲分区进行合并，以减少碎片化并提供更大的连续空闲空间。这样可以更有效地利用内存资源。

邻近适应(Next Fit) 算法。

又称循环首次适应算法，由首次适应算法演变而成。不同之处是，
分配内存时从上次查找结束的位置开始继续查找。

(首次适应算法每次都从低地址查找所以会留下很多小的空闲分区)

这种算法可能会导致产生很多小的空闲分区的原因是，当一个进程释放了一块内存后，该算法会从低地址开始搜索空闲分区。如果内存中存在多个相邻的小空闲分区，而当前进程需要的内存大小与其中一个小空闲分区的大小相等或略大，那么该算法就会选择这个小空闲分区来满足请求。这样一来，如果有多个进程反复分配和释放内存，而它们的内存需求大小比较接近，就会导致产生很多小的空闲分区。这些小的空闲分区可能无法满足大内存请求，从而导致内存碎片化的问题。内存碎片化指的是内存空间被分割成许多不连续的小块，虽然总的剩余空间足够，但是无法满足大内存请求，从而浪费了一些可用的内存空间。为了解决这个问题，可以使用其他的内存分配算法，如最佳适应算法（Best Fit Algorithm）或最坏适应算法（Worst Fit Algorithm），它们可以更好地利用内存空间，减少碎片化问题的发生。

5.4 非连续分配存储管理方式

非连续分配管理方式根据分区的大小是否固定，分为分页存储管理方式、
分段存储管理方式和段页式存储管理方式。

1. 分页存储管理方式

算法思想:把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分，分页
存储管理不会产生外部碎片。

把进程的地址空间分为若干页,把内存空间分为若干块

页面

进程最后一页经常装不了一块,所以会形成不可用的碎片—页内碎片

页面大小应是2的幂

地址结构

题1.假设某系统物理内存大小为4GB，页面大小为4KB,则每个页表项至少应该为多少字节?
解析: 4GB=232B, 4KB=2l2 B
因此4GB的内存总共会被分为232/212 = 20个内存块，因此内存块号的范围应该是0~20-1，因
此至少要20个二进制位才能表示这么多的内存块号，因此至少要3个字节才够(每个字节8个二进
制位，3个字节共24个二进制位)。

刚开始进程未执行的时候页表起始地址和页表放在PCB中,执行之后放在页表寄存器中

变换过程计算:
设页面大小为L,逻辑地址A到物理地址E的变换过程如下(逻辑地址、页号、每页
的长度都是十进制数) :

1. 计算页号P(P= A/L)和页内偏移量W(W = A%L)。

2. 比较页号P和页表长度M,若P> M，则产生越界中断，否则继续执行。

3. 页表中页号P对应的页表项地址=页表始址F +页号P X页表项长度，取出该页表项内
   容b,即为物理块号。

   要注意区分页表长度和页表项长度。页表长度的值是指一共有多少页，页表项长度是指页
   地址占多大的存储空间。

4. 计算E=b * L+ W,用得到的物理地址E去访问内存。

具有块表的页面变换结构

快表，又称联想奇存器(TLB)，是一种访问速度比内存快很多的高速缓冲存储器，用来存
放当前访问的若干页表项，以加速地址变换的过程。快表命中，只需一次访存， 快表未命中，
需要两次访存。

2.分段存储管理方式

引入原因

1. 方便编程
2. 信息共享
3. 信息保护
4. 动态增长
5. 动态链接

基本原理

段表:每个段表项对应进程的一段，段表项记录该段在内存中的始址和长度。

注意:

段号的位数说明可以分为多少段

地址变换结构

在系统中设置了段表寄存器，用于存放段表始址F和段表长度M。从逻辑地址A到物
理地址E之间的地址变换过程如下:

3.段页式存储管理方式

六,虚拟存储器

6.1 概述

1. 常规存储器特征和局部性原理

特征

1. 一次性:作业必须一次性全部装入内存才可以执行
2. 驻留性:作业被装入内存后,整个作业都会一直驻留在内存中,其中任何部分都不会换出,直至运行结束

程序的局部性表现

1. 时间局限性 原因:程序中存在大量循环操作
2. 空间局限性 原因:程序的顺序执行

正是因为常规存储器这两个特征和程序的局部性表现所以我们需要引入虚拟存储器

2.虚拟存储器三大特征

1. 多次性(最重要的特征)
   多次性是指无需在作业运行时一次性地装入内存,而允许被分成多次调入内存运行
2. 对换性
   无需在作业运行时一直常驻内存,而允许在作业运行的过程中,进行换进和换出
3. 虚拟性
   指从逻辑上扩充内存的容量,使用户看到内容远大于实际的内存容量

虚拟性是以多次性和对换性为基础的,

6.2 虚拟内存技术的实现

三种方式

1. 请求分页存储管理
2. 请求分段存储管理
3. 请求段页式存储管理

不管哪种方式都需要硬件的支持

请求分页存储管理

请求分页系统建立在基本分页管理方式之上的,为了支持虚拟存储器功能而增加了请求调页和页面置换功能.请求分页是目前最常用的一种实现虚拟存储器的方法.

页表机制

1.状态位P

用于指示该页是否已调入内存，供程序访问时参考。

2.访问字段A

用于记录本页在一段时间内的访问次数,或记录本页最近有多长时间未被访问,供置换算法换出页面时参考.

3.修改位M

又称为"脏位" 标识该页在调入内存后是否被修改过.

4.外存地址

用于指出该页在外存上的地址,通常是物理块号,供调入该页时参考

请求分页的地址变换过程

6.3 页面置换算法🐻

1.最佳(OPT)页面置换算法

算法思想:

选择以后永不使用的页面淘汰或者在最长时间内不在被访问的页面,以保证最低的缺页率

但是因为无法预知哪个页面不会被访问,所以这个算法是实现不了的,但是可以用来评价其他算法

2.先进先出(FIFO)页面置换算法

优先淘汰最早进入内存的页面,即在内存中驻留最久的页面

3.最近最久未使用页面置换算法(LRU)

算法思想:选择最近最久时间未访问的页面予以淘汰

为每个页面赋予一个访问字段,记录自上次访问以来的时间t

思想:以过去预告将来,之前很久未使用的以后使用的几率也很小

4.时钟(clock)置换算法

算法要扫描缓冲区,像时钟的指针一样转动,称为clock算法,又称最近未用(NRU)算法

被访问过置为1

当需要淘汰时,循环队列轮转检查访问位,如果是1则变为0给他一次机会,如果是0就选择该页进行换出

0 0 最近既未被访问,又未被修改是最佳淘汰位

0 1 表示最近未被访问但是已经被修改,并不是很好的淘汰页面

1 0 最近被访问但是未被修改 该页有可能再被访问

1 1 最近已被访问, 也被修改 ,该页有可能再被访问

置换算法对比

6.4 抖动

在页面置换过程中，一种最糟糕的情形是，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存，这种频繁的页面调度行为称为抖动或颠簸。
频繁发生缺页中断(抖动)的主要原因是:

某个进程频繁访问的页面数目高于可用的物理页帧数目。

七,输入/输出系统

7.1、硬件层面

1 I/O设备
IO设备大致分为两类：块设备和字符设备；

    功能：完成具体的操作；（对磁盘的读写操作）

1.2 I/O控制器
接受CPU发来的命令，去控制I/O设备，为了将处理机能够从繁杂的设备控制事务中解脱出来；

设备控制器的基本功能：

接受和识别命令
数据交换
标识和报告设备的状态
地址识别
数据缓冲区
差错控制
操作系统不与设备打交道，只通过设备控制器来操作设备；

i/o设备的控制方式

1. 轮询的方式
2. 中断的方式
3. DMA方式
4. I/o通道方式

7.2中断

中断和陷入

1.中断

cpu对io设备发来的中断信号的一种响应.cpu暂停正在执行的程序,保护cpu现场 ,然后自动去执行该io设备的中断处理程序

2.陷入

cpu内部事件引起的中断,比如程序出错

中断向量表和中断优先级

1.中断向量表

通常会为每种设备配以相应的中断处理程序

表结构

中断号	中断处理程序的入口地址

2.中断优先级

中断请求的紧急程度是不同的,所以要为他们设置不同的优先级

处理多中断源的方式

这是为了应对当处理机正在处理一个中断的时候又来了另一个中断.的处理

1.屏蔽中断

处理一个中断的时候屏蔽其他中断

2.嵌套中断

1.多个中断一同请求,优先响应高优先级的中断,2.高优先级中断请求可以抢占正在运行的低优先级中断的处理机

中断处理程序

1.测试是否有未响应的中断信号

2.保护被中断进程的cpu现场

3.转入相应设备的中断处理程序

4.处理中断

5.恢复cpu现场环境后退出中断

7.3 设备驱动程序

驱动程序操控的设备里面需要有嵌入式程序

是的，驱动程序操控的设备通常内置有嵌入式程序（也称为固件），用于控制和管理设备的功能和行为。
嵌入式程序是一种运行在设备内部的软件，通常存储在设备的非易失性存储器中，例如闪存或EEPROM。这些程序由设备制造商开发，并在生产过程中烧录到设备中。嵌入式程序包含了设备的驱动程序、操作系统、引导加载程序和其他必要的软件组件。
驱动程序与嵌入式程序进行交互，向设备发送指令和参数，以控制设备的工作模式、配置设备的功能、读取和写入设备的数据等。嵌入式程序接收驱动程序发送的指令和参数，并执行相应的操作，控制设备的硬件部分。
嵌入式程序还负责设备的初始化、启动、状态监测、错误处理等任务。它们可能实现设备间的通信协议，处理输入和输出数据，执行特定的算法，以及提供设备的各种功能。
因此，驱动程序和嵌入式程序是紧密关联的，共同确保设备能够按照预期进行操作。驱动程序在计算机系统上运行，与操作系统和应用程序交互，控制和管理设备。而嵌入式程序在设备内部运行，控制和管理设备的硬件和底层功能。

设备驱动程序的功能

1. 接收由与设备无关的软件发来的命令和参数,并将命令中的抽象io请求转换为与设备相关的低层操作序列(比如read命令转换为具体的该怎么读)
2. 检查用户io的合法性
3. 发出io命令 忙则等待
4. 及时响应由设备控制器发来的中断请求,调用相应的中断处理程序进行处理

设备处理方式

1. 为没类设备设置一个进程
2. 整个系统设置一个io进程
3. 不设置专门的设备处理进程

设备驱动执行过程

1.将抽象要求转换成具体要求

2.校验服务请求

3.检查设备的请求

设备处于就绪状态才能启动这个设备

4.传送必要的参数

5.启动io设备

7.4 与设备无关的io软件

需要实现物理设备名到逻辑设备名的映射

使用逻辑设备表

7.5用户层io软件

系统调用和库函数

系统调用是应用程序取得os所有服务的唯一途径

早期的系统调用是以汇编的形式提供的,现在C语言提供了与系统调用相对应的库函数

比如java打印出helloworld就调用了C语言中关于控制台输出的库函数

假脱机技术

SPOOLing 技术

特点:

提高了io速度

将独占设备改造为共享设备

实现了虚拟设备的功能

守护进程

守护进程是允许使用该独占设备的唯一进程,所有其他进程都不能直接使用该设备,而只能将对该设备的使用要求写入一份文件中,并将文件放入假脱机目录找那个,由守护进程按照目录中的文件,依次完成各进程对该设备的请求

7.6 缓冲

1. 缓和cpu和i/o设备间速度不匹配的矛盾
2. 减少对cpu中断的哦频率,
3. 解决数据粒度不匹配的问题
4. 提高cpu和io设备之间的并行性

双缓冲区和单缓冲区

经常用来解决互斥访问缓冲区和双向通信问题的

环形缓冲区

八,文件系统

文件逻辑结构

流式文件以字节为单位

记录式文件(有结构文件)

顺序文件

索引文件

索引顺序文件

2.文件目录

与文件管理系统和文件集合相关联的是文件目录。

1）文件控制块

与进程管理一样，为实现目录管理，操作系统中引入了文件控制块的数据结构。
文件控制块(FCB)是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。为了创建一个新文件，系统将分配一个FCB关存放在文件目录中，成为目录项。

fcb包含的信息
(1）基本信息，如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。

(2) 存取控制信息,如文件存取权限等

索引结点

除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引结点。目录项中只包含文件、索引结点指针，因此每个目录项的长度大幅减少。

目录结构

(1）单级目录结构:
在整个文件系统中建立一张目录表，每个文件占一个目录项。

(2）两级目录结构:
将文件目录分成文件目录和用户文件目录两级。

3. 共享

1）文件共享
(1）基于索引结点的共享方式(硬链接)
索引结点中设置一个链接计数变量count，用于表示链接到本索引结点上的用户目录项数。若count =

2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。
若某个用户“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点count的值减1。

若count>0，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。

(2）基于符号链的共享方式(软链接)
为使用户B能共享用户A的一个文件F，可以由系统创建一个LINK 类型的新文件，也
取名为F，并将文件F写入用户B的目录中，以实现用户B的目录与文件F的链接。

结构、文件的物理结构等。

(2) 存取控制信息,如文件存取权限等

索引结点

除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引结点。目录项中只包含文件、索引结点指针，因此每个目录项的长度大幅减少。

目录结构

(1）单级目录结构:
在整个文件系统中建立一张目录表，每个文件占一个目录项。

(2）两级目录结构:
将文件目录分成文件目录和用户文件目录两级。

3. 共享

1）文件共享
(1）基于索引结点的共享方式(硬链接)
索引结点中设置一个链接计数变量count，用于表示链接到本索引结点上的用户目录项数。若count =

2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。
若某个用户“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点count的值减1。

若count>0，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。

(2）基于符号链的共享方式(软链接)
为使用户B能共享用户A的一个文件F，可以由系统创建一个LINK 类型的新文件，也
取名为F，并将文件F写入用户B的目录中，以实现用户B的目录与文件F的链接。