操作系统复习笔记

lzhgod2024-12-222024-12-22

大题40分

(1)同步互斥(工作流程，服务人员，设备，道路)

1.概述思路 2.信号量作用和初值 3.伪代码

4.关键步骤注释

概述思路
同步互斥是处理多线程或多进程环境中资源共享问题的技术。在现实场景中，如工作流程、服务人员、设备和道路，同步互斥确保了资源在多个并发执行单元中的正确使用，防止了竞态条件和数据不一致的问题。

工作流程：确保各个任务按照预定的顺序执行，例如，任务B不能在任务A完成之前开始。
服务人员：在服务行业中，确保同一时间只有一个服务人员可以处理某个特定的任务或资源。
设备：在多个进程或线程需要使用同一设备时，确保设备一次只被一个进程或线程使用。
道路：在交通管理中，确保交叉路口的车流按照交通规则同步通过，避免交通事故。

信号量作用和初值
信号量是一个整数变量，可以用来控制对共享资源的访问。信号量主要有两种操作：P（等待）和V（信号）。

作用：
- 同步：用于控制多个线程的执行顺序。
- 互斥：用于保证同一时刻只有一个线程可以访问共享资源。
初值：
- 二进制信号量（用于互斥）：初始值通常设为1。
- 计数信号量（用于同步，如资源计数）：初始值设为资源的总数。

伪代码

// 初始化信号量
semaphore mutex = 1; // 互斥信号量，用于保护临界区
semaphore sync = 0; // 同步信号量，用于任务同步
// 工作流程伪代码
procedure TaskA()
begin
    // 执行任务A
    P(mutex); // 进入临界区
    // 临界区代码
    V(mutex); // 离开临界区
    V(sync); // 通知任务B可以开始了
end
procedure TaskB()
begin
    P(sync); // 等待任务A完成
    P(mutex); // 进入临界区
    // 临界区代码
    V(mutex); // 离开临界区
end
// 服务人员伪代码
procedure ServeCustomer()
begin
    P(mutex); // 确保一次只有一个服务人员服务
    // 服务客户
    V(mutex); // 完成服务，释放资源
end
// 设备伪代码
procedure UseDevice()
begin
    P(mutex); // 确保设备一次只被一个进程使用
    // 使用设备
    V(mutex); // 完成使用，释放设备
end
// 道路伪代码
procedure CrossRoad()
begin
    P(mutex); // 确保交叉路口的互斥通行
    // 通过道路
    V(mutex); // 离开道路，允许其他车辆通过
end

关键步骤注释

// 初始化信号量
semaphore mutex = 1; // 互斥信号量，用于保护临界区
semaphore sync = 0; // 同步信号量，用于任务同步
// 工作流程伪代码
procedure TaskA()
begin
    // 执行任务A
    P(mutex); // 进入临界区前请求互斥信号量，确保独占访问
    // 临界区代码 // 任务A的关键部分，需要互斥访问
    V(mutex); // 离开临界区后释放互斥信号量，允许其他任务访问
    V(sync); // 释放同步信号量，通知任务B可以开始执行
end
procedure TaskB()
begin
    P(sync); // 等待任务A通过V(sync)释放同步信号量
    P(mutex); // 进入临界区前请求互斥信号量
    // 临界区代码 // 任务B的关键部分，需要互斥访问
    V(mutex); // 离开临界区后释放互斥信号量
end
// 服务人员伪代码
procedure ServeCustomer()
begin
    P(mutex); // 确保一次只有一个服务人员可以进入服务状态
    // 服务客户 // 服务客户的关键步骤，需要互斥进行
    V(mutex); // 完成服务后释放互斥信号量，允许其他服务人员服务
end
// 设备伪代码
procedure UseDevice()
begin
    P(mutex); // 确保设备不会被多个进程同时使用
    // 使用设备 // 使用设备的关键步骤，需要互斥进行
    V(mutex); // 完成设备使用后释放互斥信号量，允许其他进程使用
end
// 道路伪代码
procedure CrossRoad()
begin
    P(mutex); // 在交叉路口前请求互斥信号量，确保交通规则得到遵守
    // 通过道路 // 车辆通过交叉路口的关键步骤，需要互斥进行
    V(mutex); // 离开

(2)银行家算法

1.当前是否安全，给出安全序列

2.一个进程能否申请资源

银行家算法是一种避免死锁的算法，它通过确保系统处于安全状态来允许进程动态地申请资源。

1. 当前是否安全，给出安全序列

银行家算法通过以下步骤来检查系统是否处于安全状态，并给出一个安全序列：

步骤1： 检查当前状态是否为安全状态。
Need = Max - Allocation
进程 work need allocation work+allocation

P0 1,6,2,2 0,0,1,2 0,0,3,2 1,6,5,4

P3 1,6,5,4 0,6,5,2 0,3,3,2 1,9,8,6
步骤2： 如果是安全状态，输出一个安全序列。
p0,p3

进程	work	need	allocation	work+allocation
P0	1,6,2,2	0,0,1,2	0,0,3,2	1,6,5,4
P3	1,6,5,4	0,6,5,2	0,3,3,2	1,9,8,6

2. 一个进程能否申请资源

银行家算法检查一个进程是否可以申请资源，通过以下步骤：

步骤1： 检查请求是否超过了进程的最大需求量。
步骤2： 检查系统是否有足够的资源来满足请求。
步骤3： 假设分配资源给请求的进程，并执行安全性检查。
步骤4： 如果系统仍然安全，则分配资源；否则，拒绝请求。

(3)逻辑地址转物理地址

需要的页面在外存，需要缺页中断，页号越界

处理逻辑地址转换并处理缺页中断和页号越界情况的步骤：

逻辑地址结构：首先，逻辑地址通常由两部分组成：页号（Page Number）和页内偏移（Offset）。例如，如果逻辑地址是32位，并且页面大小是4KB（即212字节），那么逻辑地址的低12位将用于页内偏移，其余的高20位将用于页号。
查找页表：使用逻辑地址中的页号在页表中查找对应的页表项（PTE，Page Table Entry）。
检查页表项：
- 页号越界：如果页号超出了页表的范围，则发生页号越界错误。操作系统通常会终止访问该地址的进程，并可能触发一个异常或错误处理程序。
- 有效位检查：如果页号在页表范围内，操作系统会检查页表项中的有效位（或存在位）以确定该页是否存在于内存中。
处理缺页中断：
- 如果有效位表明页面不在内存中（即发生缺页中断），操作系统将执行以下步骤：
  - 选择牺牲页：如果内存已满，操作系统必须选择一个页面将其移出内存，这通常是通过某种页面替换算法（如LRU、FIFO等）来完成的。
  - 如果牺牲页被修改过，则需要将其写回外存。
  - 加载请求的页面：将外存中需要的页面加载到内存中刚刚释放的帧。
  - 更新页表项以反映新页面的物理位置，并将有效位设置为表示页面现在在内存中。
计算物理地址：一旦确定了页面的物理帧号，就可以通过以下公式计算物理地址：
物理地址 = (页表项中的帧号 << 页内偏移的位数) + 页内偏移
例如，如果帧号是5，页内偏移是0x100（即256），并且页内偏移的位数是12，那么物理地址将是：
物理地址 = (5 << 12) + 256 = 0x5000 + 0x100 = 0x5100
访问物理地址：最后，处理器使用计算出的物理地址访问内存中的数据。
在整个过程中，操作系统负责透明地管理这些细节，使得应用程序不需要知道数据实际存储在物理内存的哪个位置。如果发生错误，如页号越界，操作系统将介入，通常会通知应用程序错误，并可能终止程序的执行。

(4)LRU等淘汰算法，页面访问次序，缺页次数，缺页率，课件上都有

(5)混合索引，文件占磁盘空间有多大，在几级索引上

(6)内存动态分区，给你主存多少大，让你用分配算法算

论述题30分 6个题

单道，多道批处理的特点，实时操作系统，分时操作系统

单道和多道批处理系统：单道系统一次只能处理一个作业，多道可以同时处理多个作业，提高资源利用率。
实时操作系统：保证对事件的及时响应。响应时间短，可靠性高
分时操作系统：多个用户可以同时使用计算机。允许多个用户同时与系统交互，每个用户都感觉自己在独占系统资源。时间片轮转：CPU时间被分成多个时间片，操作系统通过时间片轮转的方式为每个用户或任务分配CPU时间。多任务：系统可以同时运行多个任务

操作系统四大特征，会描述，他们直接的关系

操作系统四大特征：
并发性：多个独立的活动同时进行
共享性：系统中的多个并发进程可以共享系统资源
虚拟性：通过技术手段将一个物理实体转换为多个逻辑实体
异步性：在多道程序环境下，由于资源有限，进程的执行不会一直连续进行，而是可能会出现执行、停止、再执行的情况。这种不连续的执行方式使得进程以不可预知的速度向前推进。

微内核的基础功能

微内核：提供基本的进程通信、内存管理、设备驱动等核心功能。

进程线程的概念，两个基本，七状态图要会描述

三种调度方式(作业调度。。。)

作业调度
它负责在作业进入系统后，选择哪些作业可以进入内存并准备运行。
先来先服务（FCFS）

短作业优先（SJF）

优先级调度
进程调度
它负责在作业调度选择的作业进入内存后，决定哪个进程可以获得CPU进行执行。
先来先服务（FCFS）
短作业优先（SJF）
优先级调度
时间片轮转（RR）
高响应比优先（HRRN）
内存调度

死锁的概念2443

死锁是指在操作系统中，两个或多个进程在执行过程中因争夺资源而互相等待的现象，从而导致这些进程无法继续执行。
产生死锁的必要条件：互斥、请求和保持、不可抢占、循环等待

PV操作的动作如何定义

虚拟存储器理解

虚拟地址转换流程P177，图画出来

外部碎片和内部碎片的区别，哪些算法会产生他们

外部碎片
外部碎片是指内存中未被使用的小块空间，这些空间分散在已分配的内存块之间，虽然总体上有足够的空闲内存，但由于这些空闲块不连续，无法满足新的内存分配请求。

产生原因：

动态分区分配：在动态分区分配中，当进程结束并释放内存时，内存区域会出现不连续的空闲块，形成外部碎片。

示例：假设内存分为多个动态分区，进程A、B、C分别占用内存块。进程B释放内存后，留下一个空闲块，但这个块可能不足以容纳新的进程D，从而形成外部碎片。

内部碎片
内部碎片是指已分配的内存块内未被使用的空间。即使有进程占用了该内存块，由于分配的内存块大于实际需要的内存，未使用的部分即为内部碎片。

产生原因：

固定分区分配：在固定分区分配中，每个分区的大小是固定的，如果分配给进程的分区大于进程实际需要的内存量，剩余部分就成为内部碎片。

分页管理：在分页管理中，如果最后一页的实际数据量小于页框大小，未使用的部分也形成内部碎片。

示例：假设内存按照固定大小的块进行分配，一个进程需要110KB内存，而一个块的大小为128KB，多余的18KB就是内部碎片。

产生碎片的算法
动态分区分配：容易产生外部碎片，因为内存分区大小和位置是动态变化的。

固定分区分配：容易产生内部碎片，因为分区大小固定，可能会出现浪费的内存空间。

分页管理：容易产生内部碎片，因为最后一页可能没有被完全使用。

操作系统复习笔记

操作系统复习笔记

大题40分

(1)同步互斥(工作流程，服务人员，设备，道路)

(2)银行家算法

1. 当前是否安全，给出安全序列

2. 一个进程能否申请资源

(3)逻辑地址转物理地址

(4)LRU等淘汰算法，页面访问次序，缺页次数，缺页率，课件上都有

(5)混合索引，文件占磁盘空间有多大，在几级索引上

(6)内存动态分区，给你主存多少大，让你用分配算法算

论述题30分 6个题

单道，多道批处理的特点，实时操作系统，分时操作系统

操作系统四大特征，会描述，他们直接的关系

微内核的基础功能

进程线程的概念，两个基本，七状态图要会描述

三种调度方式(作业调度。。。)

死锁的概念2443

PV操作的动作如何定义

虚拟存储器理解

虚拟地址转换流程P177，图画出来

外部碎片和内部碎片的区别，哪些算法会产生他们

文件：对FAT表的了解，计算FAT表的大小

磁盘空闲管理：位示图大小求法，王道里面有题，成组链接法的组成过程

单选题30分 15题

实时系统什么时候快

批处理提交作业时提交控制信息

缓存，编程用的是系统调用，什么是重定位，什么是动态重定位，程序和进程的本质区别，

文件系统要实现的重要目标：按名存取

lzhgod