磁盘空间分配方式

连续分配：在磁盘上为每个文件分配一组连续的块。这种方法简单且读写效率高，但容易产生磁盘碎片。
链接分配：文件的各个部分分散存储在磁盘上，每个部分的位置信息存储在前一个部分中。这种方法避免了碎片问题，但随机访问性能较差。
索引分配：所有文件块的索引信息存储在一个单独的索引块中。这种方法支持快速随机访问，同时减少了碎片问题，但需要额外的空间存储索引信息。

硬件保护的方式

二态模式：操作系统通过用户模式和内核模式的切换来保护关键系统资源。
特权指令：只有在内核模式下才能执行的指令，用于保护系统的关键操作。
存储器保护：（memory protection）使用内存管理单元MMU
CPU保护：使用定时器等硬件机制，确保一个程序不能占用CPU太长时间，从而保护系统的响应性。

竞争条件的解决方案和CPU调度状态转移

竞争条件的解决方案：为了确保多个进程或线程在访问共享资源时不会产生冲突，操作系统采用了包括互斥、前进性、有限等待和速度控制在内的策略。
CPU调度中的状态转移：操作系统通过调度算法管理进程的执行，进程在“就绪”、“运行”和“等待”等状态之间转移，以高效利用CPU资源。

1-2 章总览 Overview

1、操作系统的概念

充当 计算机用户 和 计算机硬件 之间的中介的程序

2、计算机系统结构

冯诺伊曼 体系结构

输入数据和程序的 输入设备
记忆程序和数据的 存储器 但是现代计算器已经转化为以存储器为中心
完成数据加工处理的 运算器 arithmetic logic unit ALU 逻辑上讲冯诺依曼计算机是以运算器为中心的
控制程序执行的 控制器 control unit CU
输出处理结果的 输出设备

连接五大子系统之间的方式以前多采用 分散连接 为增加效率和灵活性出现了总线

3、中断处理

作用、优势:中断处理的优势包括

提高系统的响应速度和效率
允许系统同时处理多个任务，
以及提供了一种有效的错误处理和系统管理机制。

中断向量（Interrupt Vector, IV）：是指向中断服务例程（ISR）的指针。当发生中断时，系统会使用这个指针来找到并执行相应的中断处理代码。
中断向量表（Interrupt Vector Table, IVT）：是存储中断向量的表格。它包含了系统中所有可能的中断和异常的处理入口点。当发生中断时，CPU 会根据中断类型到这个表中查找对应的中断向量。
中断服务例程（Interrupt Service Routine, ISR）：也称为中断处理程序，是响应特定中断的代码。当相应的中断发生时，CPU 会执行这段代码来处理中断。
中断请求（Interrupt Request , IRQ）：是从硬件设备到 CPU 的信号，表明设备需要 CPU 的注意。每个 IRQ 线路都被分配给了特定的设备，当设备需要 CPU 处理数据时，它会发送 IRQ。
软件生成的中断（Software Generated Interrupt, SGI）：也称为软中断，是由软件指令产生的中断，而不是由硬件事件直接触发。软件可以使用这种机制来触发中断处理程序的执行，以处理特定的软件事件或条件。

4、计算机系统的保护措施

4.1、二态模式

内核态系统程序执行时处理机所处的状态此时处理机可以执行所有指令，包括特权指令
用户态用户程序执行时处理机所处的状态只能执行非特权指令

这种模式的设计是为了防止用户程序直接执行可能会影响系统稳定性的操作。

4.2、CPU 保护

CPU 保护模式：物理内存地址不能直接被程序访问，程序内部的地址需要被转化为物理地址后再去访问；实模式 CPU 运行环境 16 位，保护模式 32 位
CPU 保护是通过设置保护模式来实现的，它确保物理内存地址不能直接被程序访问。程序中使用的地址需要通过操作系统转化为物理地址后才能访问，这样可以防止程序直接操作物理内存，从而保护系统的内存不被非法访问。

4.3、特权指令

具有特殊权限的指令。这类指令只用于操作系统或其他系统软件用于执行一些关键的系统操作，如内存管理、进程控制等

4.4、存储器保护

连续内存分配：Base+Limitation 连续内存分配使用基址（Base）和界限（Limitation）来限制程序访问的内存范围，防止程序访问非法内存区域
页式内存管理：Valid/Invalid Bit 页式内存管理通过设置有效/无效位（Valid/Invalid Bit）来控制对内存页的访问，只有标记为有效的页才能被访问，这样可以进一步提高内存的保护效果。

5.进程

进程。它是系统内的工作单元。程序是被动实体，进程是主动实体。

进程需要资源来完成其任务

CPU，memory，I/O ，files

Initialization data

CPU：进程需要 CPU 时间来执行其指令。
内存：进程需要内存空间来存储其代码、数据以及运行时的临时信息。
I/O 设备：进程可能需要输入/输出设备来进行数据的输入输出操作。
文件：进程可能需要访问文件系统中的文件来读取数据或者存储结果。
初始化数据：进程启动时可能需要一些初始化数据，这些数据可以是配置信息、启动参数等。

OS Service & Structure

6、OS Structure

Simple structure （简单结构）– MS-DOS

没有明确分离内核与用户空间简单设计用于早期计算机系统

More complex（整体式结构） – UNIX（ Monolithic Structure ）

整体式所有系统和内核都紧密集成在一个大内核中

Layered（分层） – THE

将系统分为不同层次每层只用下一层提供的功能让操作系统更加模块化便于理解和维护可能引入额外开销

Microkernel （微内核）– Mach

将核心功能（进程管理内存管理）留在内核中而将其他服务（文件系统网络通信）移至用户空间提高灵活性安全性

loadable kernel modules (LKMs)（模块化）— Solaris

支持可加载内核模块允许不重启系统时动态增删功能提高可拓展性

Hybrid structure（混合结构）— Mac OS X ，iOS ，Android

结合 微内核 的优点和 单内核 的高性能

第三章 Process

1、进程概念：

进程是操作系统中的基本概念，它代表着操作系统中正在执行的程序。每个进程都是独立的执行单元，拥有自己的执行顺序和状态。进程的执行必须按照特定的顺序进行，这是由操作系统的调度策略决定的。

2、进程的组成部分：

进程由多个部分组成，包括：

Text：程序的代码部分。
Data：程序的全局变量和静态变量。
Stack：程序的运行时栈，用于存储局部变量、函数参数等。
Heap：动态分配的内存，如通过malloc或new分配的内存。
Register：寄存器，存储当前执行的指令和其他关键信息。
PC（Program Counter）：程序计数器，指向下一条要执行的指令。

3、进程的状态：

进程在其生命周期中会经历多种状态，包括：

New：进程刚被创建。
Running：进程正在 CPU 上执行。
Waiting：进程等待某些事件发生，如 I/O 操作完成。
Ready：进程准备好运行，等待被调度到 CPU 上。
Terminated 终止：进程执行完毕或被终止。

标准一些：

1、就绪态-》运行态

2、运行态-》就绪态

3、运行态-》等待态；

4、阻塞态-》就绪态

4、进程控制块（PCB）：

PCB 是操作系统中用于存储进程信息的数据结构，包括进程状态、程序计数器、CPU 寄存器、内存管理信息等。PCB 是操作系统管理进程的关键数据结构。

5、抢占性问题：

在多任务操作系统中，进程从一个状态转换到另一个状态可能涉及到抢占性问题，如从“等待”状态转换到“就绪”状态，或从“运行”状态转换到“就绪”状态。这涉及到操作系统的调度策略，如何公平、高效地分配 CPU 时间给多个进程。

6、进程调度：

进程调度是操作系统中的一个核心功能，负责管理进程的执行顺序。它涉及到几个关键组成部分：

就绪队列

I/O队列

挂起队列

就绪队列：存放已准备好执行但正在等待 CPU 资源的进程。
等待队列：存放因为等待某些事件（如 I/O 操作完成）而被挂起的进程。
上下文切换：当操作系统从一个进程切换到另一个进程时，需要保存当前进程的状态（上下文）并加载新进程的状态，这个过程称为上下文切换。上下文切换是一个开销较大的操作，因为它涉及到 CPU 状态的保存与恢复。

7、进程间通信（IPC）：

进程间通信是指在不同进程之间交换数据的机制。它是多任务操作系统中实现进程协作的重要手段。共享内存是 IPC 的一种形式，它允许两个或多个进程访问同一块内存区域，从而实现数据的共享和交换。

共享内存：在共享内存模型中，操作系统会提供一块可以被多个进程访问的内存区域。这种方式的优点是数据交换速度快，因为数据不需要在进程间复制，只需要通过内存就可以直接访问。然而，这也带来了同步和数据一致性的挑战。
生产者-消费者问题：这是一个经典的并发问题，用于描述两个或多个进程间的协作模式。生产者进程负责生成数据并放入缓冲区，消费者进程则从缓冲区中取出数据进行处理。这个问题的关键在于如何确保生产者不会在缓冲区满时向其写入数据，以及消费者不会在缓冲区空时尝试从中读取数据。
有界缓冲区与无界缓冲区：
- 有界缓冲区：缓冲区的大小是固定的，这意味着它能够存储的数据量是有限的。在这种情况下，必须有机制确保当缓冲区满时生产者停止生产，当缓冲区空时消费者停止消费。
- 无界缓冲区：理论上缓冲区的大小是无限的，生产者可以无限制地生产数据，而不用担心缓冲区会溢出。然而，在实际应用中，无界缓冲区可能会因为资源限制（如内存大小）而不能真正实现无限制。

8、消息传递

直接通信（Direct IPC）：在这种模式下，每对进程都需要显式地发送消息给对方。发送方需要指定接收方的标识符，而接收方需要从指定的发送方接收消息。这种方式的通信是直接的，没有中间实体或存储介质参与消息的传递。
间接通信（Indirect IPC）：间接通信通过使用共享的数据结构（如消息队列）来实现，进程通过这些共享结构来交换消息。在这种模式下，发送方和接收方不需要直接知道对方的标识符，它们通过操作共享的消息队列来进行通信。
管道（Pipes）：
- 普通管道（Unnamed Pipes）：这是最简单的管道形式，通常用于有亲缘关系的进程间通信（如父子进程）。普通管道是单向的，数据只能从一端流向另一端。
- 命名管道（Named Pipes）：与普通管道不同，命名管道可以在没有亲缘关系的进程间进行通信。它们在文件系统中有一个名字，任何知道这个名字的进程都可以通过它来发送或接收数据。命名管道可以是单向的或双向的。
套接字（Sockets）：套接字是一种更为复杂和强大的通信机制，它不仅可以用于同一台机器上的进程间通信，还可以用于不同机器上的进程间通信。套接字支持多种通信协议（如 TCP 和 UDP），提供了丰富的接口来实现复杂的网络通信。

9、同步：

在多进程或多线程环境中，同步是确保数据一致性和避免竞态条件的机制。它可以分为两种：

阻塞同步：进程在等待某个条件满足时被挂起，直到条件满足后才继续执行。
非阻塞同步（异步）：进程在等待某个条件时不会被挂起，而是继续执行其他任务，条件满足后通过回调或事件来通知进程。

第四章 Thread&Concurrency

好处：线程和并发编程带来了多方面的好处，包括：

响应性：在多线程应用中，即使某个线程因为执行长时间操作而阻塞，其他线程仍然可以继续执行，从而提高了应用的响应性。
资源共享：线程间可以共享进程资源，如内存和文件，这使得数据交换和通信更加方便。
经济：相比于进程，线程的创建、销毁和切换的开销更小。
可扩展性：多线程可以更好地利用多核处理器的计算能力，提高应用的性能。

并行类型：并行编程可以分为两种类型：

数据并行性：将数据分割成多个部分，由多个线程并行处理，每个线程处理数据的一个子集。
任务并行性：程序被分成多个可以并行执行的任务，每个任务由一个线程执行。

多线程模型：描述了用户线程和内核线程的关系，主要有三种模型：

多对一：多个用户线程映射到一个内核线程。这种模型的缺点是一个用户线程阻塞会导致所有用户线程阻塞。
一对一：每个用户线程对应一个内核线程。这提高了并发性，但创建大量线程时会增加开销。
多对多：多个用户线程可以映射到多个内核线程。这种模型既提供了良好的并发性，又避免了一对一模型中的开销问题。

两级模型（M:M+1:1）：

这是一种特殊的多对多模型，它允许系统动态调整用户线程和内核线程之间的映射关系，以达到最优的性能。这种模型结合了多对一和一对一模型的优点，提供了更高的灵活性和效率。

第五章 CPU Scheduling

调度评价指标：在评估 CPU 调度算法的效果时，通常会考虑以下几个关键指标：
- CPU 利用率：衡量 CPU 活跃时间与总时间的比例，高 CPU 利用率意味着系统能高效利用 CPU 资源。
- 吞吐量：单位时间内完成的作业数量，反映了系统的处理能力。
- 周转时间：从作业提交到作业完成的总时间，包括等待、执行和 I/O 操作的时间。
- 等待时间：作业在就绪队列中等待被调度的时间总和。
- 回答：这可能是指对作业完成情况的反馈或评价。
调度算法：介绍了几种常见的 CPU 调度算法，包括：
- FCFS（先来先服务）：按照作业到达的顺序进行调度。
- Shortest-Job-First（最短作业优先）：优先调度预计执行时间最短的作业。
- Round Robin（时间片轮转）：每个作业轮流使用 CPU 一定时间片，适用于时间共享系统。
- Priority Scheduling（优先级调度）：根据作业的优先级进行调度。
- Priority+Round-Robin：结合了优先级调度和时间片轮转的特点。
- Multilevel Queue（多级队列）：根据作业的类型将其分配到不同的队列，每个队列有自己的调度算法

计算给定案例的等待时间

产生优先级反转：SJF、多级队列

Multi-Processor Scheduling

Abstract

2 levels of scheduling

第六章 Synchronization Tools

并发共享资源访问的问题：在多线程程序中，当多个线程同时访问同一资源时，如果没有适当的同步控制，就会导致数据的不一致性问题。
临界区（Critical Section, CS）：是指那些访问共享资源的代码区域。为了防止不一致性问题，需要对临界区进行访问控制。

解决临界区问题的三个条件：
- 互斥（Mutual Exclusion）：任何时刻只允许一个线程进入临界区。
- 前进性（Progress）：如果没有线程在临界区内，那么在外部等待的线程必须能够进入临界区。
- 有限等待（Bounded Waiting）：确保等待进入临界区的线程最终能够进入。
Peterson’s Solution 和 Turn+Flag 方法是解决临界区问题的经典算法，主要用于两个线程的同步。
硬件同步机制：包括内存屏障（Memory barriers）、硬件指令（如 Test-and-Set, Compare-and-Swap）和原子变量，这些机制可以直接由硬件支持，提高同步操作的效率。
互斥锁（Mutex Locks）：通过acquire()和release()操作来获取和释放锁，保证了临界区的互斥访问。
信号量（Semaphore）：是一种更为通用的同步机制，通过wait()和signal()操作来实现线程间的同步和通信。

这里很有意思例如

 struct semaphore{
     int value；
     struct PCB* queue;
 
 }
 
 void wait(semphore s)
 {
     s.value-=1;
     if(s.value<0)//ez to realize 
         {
             block(s.queue);
         }
 }
 
 void signal (semaphore s)
 {
     s.value+=1;
     //！！
     if(s.value<=0)
     {
         wakeup(s.queue);
     }
     
 }

生产者-消费者（Producer-Consumer） 和 读者-写者（Reader-Writer） 问题是并发编程中的经典问题，通过使用信号量或互斥锁可以有效地解决这些问题。

生产者-消费者问题是一个经典的同步问题，用于描述两个或多个进程（或线程）使用共享资源的情况，其中生产者负责生成数据并放入缓冲区，消费者从缓冲区取出数据进行消费。为了解决这个问题，通常会使用三个信号量：mutex、empty、full。

信号量的意义和用途

mutex（互斥量）：
- 意义：用于保证对缓冲区的互斥访问。
- 用途：确保任何时刻只有一个生产者或消费者可以操作缓冲区，防止数据竞争和条件竞争。
empty：
- 意义：表示缓冲区中空闲位置的数量。
- 用途：生产者在向缓冲区放入数据之前检查empty，如果empty大于0，表示缓冲区有空间，生产者可以生产；生产者每次生产后，empty减1。
full：
- 意义：表示缓冲区中已填充数据的位置数量。
- 用途：消费者在从缓冲区取出数据之前检查full，如果full大于0，表示缓冲区有数据，消费者可以消费；消费者每次消费后，full减1。

解决方案

先看有无空间 P 再是mutex互斥然后V互斥 V空间务必对称

生产者和消费者通过上述三个信号量协同工作，以确保缓冲区的同步访问，避免生产者在缓冲区满时继续生产（导致溢出），以及消费者在缓冲区空时尝试消费（导致下溢）。

生产者操作：
1. 等待empty（确保有空间生产）。
2. 等待mutex（确保互斥访问缓冲区）。
3. 生产数据并放入缓冲区。
4. 释放mutex。
5. 释放full（增加一个已填充位置的计数）。
消费者操作：
1. 等待full（确保有数据可消费）。
2. 等待mutex（确保互斥访问缓冲区）。
3. 从缓冲区取出数据进行消费。
4. 释放mutex。
5. 释放empty（增加一个空闲位置的计数）。

考点强调

互斥访问：理解mutex如何保证缓冲区的互斥访问是关键。
如何保证：mutex（互斥量）信号量用于保证在任何时刻，只有一个进程（生产者或消费者）可以访问缓冲区。当一个进程需要访问缓冲区时，它会首先执行P操作（等待）在mutex上。如果mutex的值为1，表示缓冲区未被占用，该进程可以进入，同时将mutex设置为0，阻止其他进程进入。当进程离开缓冲区时，它会执行V操作（信号）在mutex上，将mutex设置回1，允许其他进程访问缓冲区。
资源计数：理解empty和full如何作为计数器管理缓冲区的空闲和已占用空间。
如何作为计数器管理：empty和full信号量分别跟踪缓冲区中的空闲位置数量和已占用位置数量。empty初始值为缓冲区大小，表示所有位置都是空的；full初始值为0，表示没有位置被占用。生产者在生产前检查empty（P操作），确保有空间放置新生产的项，每生产一个项，empty减1。消费者在消费前检查full（P操作），确保有项可消费，每消费一个项，full减1。这样，empty和full确保生产者和消费者只在缓冲区状态允许时才进行操作。
避免死锁和饥饿：死锁可能发生当多个进程相互等待对方持有的资源。在生产者-消费者问题中，确保进程按照固定顺序获取信号量可以避免死锁。例如，进程总是先尝试获取mutex，然后是empty或full。饥饿发生于当一个或多个进程无法得到足够的资源执行。通过确保信号量的公平使用（例如，操作系统层面的队列管理），可以减少饥饿的可能性。

同步机制

如何支持并发执行而不违反数据一致性：通过使用mutex保证互斥访问，以及使用empty和full信号量管理资源状态，生产者和消费者可以并发执行而不会相互干扰。mutex确保了数据一致性，防止了同时读写缓冲区的情况。empty和full确保生产者不会在缓冲区满时写入数据，消费者不会在缓冲区空时尝试读取数据，从而保持了系统的稳定性和效率。

死锁和饥饿

死锁和饥饿：考虑如何避免死锁（例如，生产者和消费者都在等待对方释放资源）和饥饿（某个进程永远得不到执行的机会）。
同步机制：理解生产者和消费者如何通过信号量同步，以及这种同步机制如何支持并发执行而不违反数据一致性。

首先，展示了两个基础的同步原语：test_and_set 和 compare_and_swap。这两个函数是实现低级同步机制的基础，通常由硬件直接支持。

 boolean test_and_set (boolean *target)
         {
           boolean rv = *target;
           *target = true;
           return rv:
          }
 test_and_set函数通过检查目标变量的值，然后将其设置为true，并返回原始值。这个操作是原子的，意味着在执行过程中不会被其他线程中断，常用于实现锁机制。
 int compare_and_swap(int *value, int expected, int new_value) {
          int temp = *value;
           if (*value == expected)
             *value = new_value;
             return temp;      }
 compare_and_swap函数则是比较目标变量的当前值与预期值，如果相同，则将其更新为新值。这个操作也是原子的，广泛用于实现更复杂的同步机制，如无锁数据结构。

接下来，介绍了信号量的概念，它是一种更高级的同步机制。信号量通过两个原子操作 wait()和 signal()来控制对共享资源的访问。wait()操作会递减信号量的值，如果信号量的值小于 0，则线程会阻塞直到信号量的值被其他线程通过 signal()操作增加。这个机制可以用来实现线程间的同步和互斥。

信号量 S-整数变量，仅通过两个原子操作访问

wait():递减，阻塞直到信号量打开(down())

signal():增量，允许另一个线程进入(up())

Consider P1 and P2 that requires S1 to happen before S2

Create a semaphore “synch” initialized to 0

 P1:
    S1;
    signal(synch);
 P2:
    wait(synch);
    S2;`

文本中还提供了一个使用信号量同步两个线程的示例，其中 P1 线程执行操作 S1 后通过 signal()操作释放信号量，P2 线程则在执行操作 S2 之前通过 wait()操作等待信号量。这确保了 S1 操作在 S2 之前执行。

Reader -writer

Producer -Consumer

For reading 文本中还提供了一个使用信号量同步两个线程的示例，其中 P1 线程执行操作 S1 后通过 signal()操作释放信号量，P2 线程则在执行操作 S2 之前通过 wait()操作等待信号量。这确保了 S1 操作在 S2 之前执行。

最后，文本通过读者-写者和生产者-消费者问题展示了信号量在实际应用中的使用。读者-写者问题中，使用信号量来确保当有写者时，读者不能读取数据，反之亦然。生产者-消费者问题则是通过信号量来同步生产者和消费者之间的生产和消费操作，确保生产者不会在缓冲区满时写入数据，消费者也不会在缓冲区空时尝试读取数据。

这些机制和示例展示了在并发编程中同步和互斥的重要性，以及如何使用不同的同步工具来解决这些问题。

 while(1)
 {
     P(&mutex);
     readcount++  ;
     if( readcount==1 ) P(&wrt);//第一个读者 那么write暂停
     V(&mutex);
 
     Reading is performed;
 
     P(&mutex);
     Readcount-- ;
     if(readcount==0 )  V(&wrt);//最后一个读者结束 可以write
     V(&mutex);
 }

这段代码是解决读者-写者问题的一个经典示例，特别是在处理多个读者和写者访问共享资源时确保同步和互斥。读者-写者问题是一个常见的并发控制问题，其中读者可以同时读取共享数据，但写者必须独占访问。

代码中使用了两种信号量：mutex 和 wrt。mutex 用于保护 readcount 变量，这个变量跟踪当前正在读取共享资源的读者数量。wrt 信号量用于控制写者的访问，确保当有写者时，阻止新的读者开始读取。

开始读取：每个读者首先通过 P(&mutex)操作获取 mutex 信号量，以安全地增加 readcount。如果 readcount 为 1，意味着这是第一个读者，需要通过 P(&wrt)操作获取 wrt 信号量，以阻止写者进入。之后，释放 mutex 信号量，允许其他读者或写者尝试访问共享资源。

读取操作：在 mutex 信号量保护下进行，确保 readcount 的修改是互斥的。

结束读取：读取完成后，读者再次通过 P(&mutex)操作获取 mutex 信号量，以安全地减少 readcount。如果 readcount 为 0，意味着没有其他读者正在读取，通过 V(&wrt)操作释放 wrt 信号量，允许写者进入。最后，释放 mutex 信号量。

这种方法确保了多个读者可以同时读取数据，但在任何写者写入数据时，必须独占访问。这样既提高了读操作的并发性，又保证了写操作的正确性和数据的一致性。

代码中的 while(1)循环表示读者尝试读取操作是持续进行的，这在实际应用中可能会根据具体需求进行调整。需要注意的是，代码片段中的 Reading is performed;是一个占位符，表示实际的读取操作应该在这里执行。

第七章 Deadlocks

死锁的必要条件

文本首先列出了发生死锁的四个必要条件：

互斥（Mutual Exclusion）：至少有一个资源必须处于非共享模式，即一次只有一个进程可以使用资源。
持有并等待（Hold and Wait）：一个进程至少持有一个资源，并且正在等待获取其他进程持有的资源。
无抢占（No Preemption）：资源只能由持有它的进程释放，不能被抢占。
循环等待（Circular Wait）：存在一种进程资源的循环等待链，每个进程持有下一个进程所需要的至少一个资源。

处理死锁的方法

接着，文本介绍了处理死锁的几种方法：

死锁预防：通过破坏死锁的四个必要条件中的至少一个来预防死锁的发生。
避免死锁：在资源分配时避免系统进入不安全状态。这里提到了两种策略：对于单个资源实例，可以使用资源分配图来避免死锁；对于多个资源实例，可以使用银行家算法来确保系统始终处于安全状态。
死锁检测：这涉及到系统的运行时检测。对于单个资源实例，可以使用等待图来检测死锁；对于多个资源实例，需要使用特定的检测算法。
从死锁中恢复：一旦检测到死锁，系统需要采取措施从死锁状态中恢复，这可能包括资源的进程的回滚或终止等策略。

这段文本为理解和处理操作系统中的死锁问题提供了一个高层次的概述，涵盖了从预防和避免死锁到检测和从死锁中恢复的全过程。死锁是并发编程中一个复杂且重要的问题，理解这些概念对于设计能够有效管理资源和避免潜在死锁的系统至关重要。

第八章 Main Memory

这段文本是关于操作系统中主存储器（Main Memory）的管理和相关概念的概述，特别强调了内存分配、地址转换和内存保护的机制。

逻辑地址空间与物理地址空间

逻辑地址空间是指程序生成的所有逻辑地址的集合，这些地址在程序运行时由 CPU 生成，但并不直接对应物理内存的实际位置。
物理地址空间则是指程序生成的所有物理地址的集合，这些地址对应内存中的实际物理位置。

操作系统的任务之一是在逻辑地址和物理地址之间进行映射，确保程序的正确执行。

保护

操作系统通过使用一对基寄存器和极限寄存器来定义进程的逻辑地址空间，从而实现内存保护。这确保了进程只能访问分配给它的内存区域，防止了进程间的非法访问。

连续内存分配

文本提到了三种连续内存分配策略：

First-fit（首次分配）：在内存中顺序查找，分配第一个足够大的空闲区域。
Best-fit（最佳分配）：查找能够最紧凑地容纳进程的最小空闲区域。
Worst-fit（最差分配）：选择足够大的最大空闲区域进行分配。

这些策略各有优缺点，影响内存的利用率和系统的性能。

内存碎片

External Fragmentation（外部碎片）：由于连续内存分配导致的空闲内存碎片。
Internal Fragmentation（内部碎片）：分配给进程的内存块比实际需要的大，未使用的部分造成的碎片。

分页

分页是一种内存管理机制，通过将逻辑地址空间和物理地址空间分割成固定大小的页（page）和帧（frame），减少内存碎片，简化地址转换。页表用于将逻辑地址转换为物理地址。

页表的结构和优化

Hierarchical Paging（分层分页）：通过使用多级页表减少页表所需的内存。
Hashed Page Tables（哈希页表）：使用哈希表来加快页表的查找速度。
Inverted Page Tables（倒排页表）：每个帧一个条目，减少了页表的大小。

TLB 和 EAT 计算

TLB（Translation Lookaside Buffer）是一个小型硬件缓存，用于加速页表的查找过程。
EAT（Effective Access Time）计算考虑了 TLB 命中和未命中的情况下的平均访问时间。

这段文本为理解操作系统中主存储器的管理提供了一个全面的视角，涵盖了从内存分配到地址转换，再到内存保护的各个方面。

第九章 Virtual Memory

这段文本介绍了虚拟内存的概念、优点以及实现方式，特别强调了需求分页和页面替换算法等关键技术。

虚拟内存的优点

虚拟内存是一种内存管理技术，它将用户逻辑内存与物理内存分离，提供了以下几个主要优点：

部分程序执行：只有部分程序需要在内存中执行，可以有效地使用有限的物理内存资源。
逻辑地址空间大于物理地址空间：这允许程序的逻辑地址空间比实际的物理内存大，从而支持更大的应用程序。
地址空间共享：允许多个进程共享地址空间，便于资源共享和通信。
高效的进程创建：由于不需要一次性将所有数据加载到物理内存，进程创建更加高效。
支持更多程序同时运行：通过有效管理内存，可以在同一时间运行更多的程序。
减少 I/O 需求：加载或交换进程所需的 I/O 操作更少，提高了系统的整体效率。

虚拟内存的实现

虚拟内存主要通过以下方式实现：

需求分页：这是一种常见的虚拟内存实现方式，只有当程序需要某个页面时，才将其从磁盘加载到内存中。
页面替换：当内存中没有足够的空间加载新页面时，操作系统会选择一个页面进行替换。
页面故障：当访问的页面不在内存中时，会发生页面故障，触发需求分页机制。
页面和帧替换算法：为了决定哪个页面应该被替换，操作系统使用各种算法，如 FIFO（先进先出）、LRU（最近最少使用）和它们的变种。

抖动问题

抖动是虚拟内存系统中的一个问题，当进程频繁地换入换出页面时，页面故障率高，导致 CPU 利用率低。为了防止抖动，系统需要为进程提供足够数量的帧，确保进程能够高效运行。

总的来说，虚拟内存通过提供更大的逻辑地址空间、减少物理内存的需求、允许更多程序同时运行等优点，极大地提高了计算机系统的效率和灵活性。然而，需求分页、页面替换算法的选择以及抖动问题的处理都是虚拟内存管理中需要仔细考虑的关键因素。

第十、十一章 File System

这段文本概述了文件系统（File System）的基本概念、结构和实现机制，涵盖了从文件和目录的组织，到文件共享和保护，再到文件系统的体系结构和磁盘空间分配的各个方面。

文件和目录结构

逻辑存储单元：文件系统中的基本单位是文件，它是存储在磁盘或其他存储设备上的数据的集合。
目录结构：文件系统通常使用树状结构来组织文件和目录，以便用户能够方便地管理和访问。这种结构可以是单级或多级的，其中每个级别代表一个目录层次。更复杂的结构可能采用不带循环的图，允许更灵活的数据组织方式。

文件共享和保护

权限：文件系统通过定义不同的访问权限（如读、写、执行）来实现文件的共享和保护。权限可以是本地的，也可以是针对网络共享的。
访问控制：通过访问控制列表（ACLs）或其他机制，文件系统确保只有授权用户或程序才能访问特定的文件或目录。

文件系统的分层体系结构

逻辑文件系统（Logical FS）：处理与用户交互的部分，如文件操作的接口。
文件组织模块：负责文件如何在存储设备上组织，包括文件的物理布局。
基本文件系统（Basic FS）：与设备驱动程序交互，处理数据的实际读写操作。

文件系统的元数据

引导记录、分区控制块和文件控制块（FCB）是文件系统中用于存储文件属性和磁盘分区信息的重要元数据结构。

目录实现和磁盘空间分配

目录实现：文件系统可以通过线性列表或哈希表来实现目录，以支持文件的快速查找和访问。
磁盘空间分配：文件系统采用不同的策略来分配磁盘空间，包括连续分配、链接分配和索引分配。每种方法都有其优缺点，影响着文件的存取效率和磁盘空间的利用率。

总的来说，文件系统是操作系统中非常关键的组成部分，它不仅提供了数据存储和访问的机制，还包括了数据的组织、共享、保护和管理等多方面的功能。理解文件系统的基本概念和结构对于有效地管理和使用计算机资源至关重要。

分析：银行家算法很难吗？

1、判断安不安全很容易就看MAXNEED Allocation Available

最大需求已分配可用

从任意一个任务开始可用+已分配大于等于最大需求即可然后把已分配的释放出来，成为可用，

再比较后续可用+某个已分配是否大于等于最大需求

跑出一条通路即可证明安全分配方式是多样的

2、资源请求算法某个任务请求资源可不可以给？

满足几点理解了很容易

第一你请求的资源不能超过我可用的，假如我只有两个可用你请求三个，肯定不行

第二你请求的资源加上你已经分配的不能超过你的上限超过了就不满足银行家算法的定义了

第三，把数据表更新，然后判断安不安全，如果安全那就没问题，如果因为你的请求，导致别人无法跑通了，那肯定不行

硬件支持

testandset

 // 全局变量
 lock = 0 // 锁变量，0表示未锁定，1表示锁定
 
 // 尝试获取锁的函数
 function TestAndSet(lockVariable):
     oldValue = lockVariable
     lockVariable = 1
     return oldValue
 
 // 使用TestAndSet实现的互斥锁
 while (TestAndSet(lock) == 1) {
     // 等待锁释放
 }
 // 临界区
 ...
 lock = 0 // 释放锁

Swap

 // 全局变量
 lock = 0 // 锁变量，0表示未锁定，1表示锁定
 key = 1 // 当前线程的钥匙
 
 // Swap操作
 function Swap(a, b):
     temp = a
     a = b
     b = temp
     return temp
 
 // 使用Swap实现的互斥锁
 key = 1
 while (key == 1) {
     Swap(lock, key)
 }
 // 临界区
 ...
 lock = 0 // 释放锁

皮特森

 // 全局变量
 flag[2] = {false, false} // 表示每个线程是否准备进入临界区
 turn // 表示哪个线程的轮次
 
 // 线程0的代码
 flag[0] = true // 线程0准备进入临界区
 turn = 1 // 让出优先权给线程1
 while (flag[1] && turn == 1) {
     // 等待
 }
 // 临界区
 ...
 flag[0] = false // 线程0离开临界区
 
 // 线程1的代码
 flag[1] = true // 线程1准备进入临界区
 turn = 0 // 让出优先权给线程0
 while (flag[0] && turn == 0) {
     // 等待
 }
 // 临界区
 ...
 flag[1] = false // 线程1离开临界区

生产消费者

 void* producer(void* arg) {
     int item;
     while (1) {
         item = produce_item(); // 生产一个产品
         sem_wait(&empty); // 等待空闲槽  -1
         pthread_mutex_lock(&mutex); // 进入临界区
         insert_item(item); // 将产品放入缓冲区
         pthread_mutex_unlock(&mutex); // 离开临界区
         sem_post(&full); // 增加产品数量 +1
     }
 }
 
 void* consumer(void* arg) {
     int item;
     while (1) {
         sem_wait(&full); // 等待产品
         pthread_mutex_lock(&mutex); // 进入临界区
         item = remove_item(); // 从缓冲区取出产品
         pthread_mutex_unlock(&mutex); // 离开临界区
         sem_post(&empty); // 增加空闲槽数量
         consume_item(item); // 消费产品
     }
 }

读写者

// 假设有变量readCount来记录当前的读者数量，以及互斥锁resourceAccess, readCountAccess

// 读者代码
reader() {
    down(readCountAccess) // 保护readCount
    readCount++
    if (readCount == 1) down(resourceAccess) // 第一个读者获取资源访问权
    up(readCountAccess)

    // 读取资源
    ...

    down(readCountAccess)
    readCount--
    if (readCount == 0) up(resourceAccess) // 最后一个读者释放资源访问权
    up(readCountAccess)
}

// 写者代码
writer() {
    down(resourceAccess) // 获取资源访问权
    // 写入资源
    ...
    up(resourceAccess)
}

磁盘空间分配方式

硬件保护的方式

竞争条件的解决方案和CPU调度状态转移

1-2 章总览 Overview

1、操作系统的概念

2、计算机系统结构

3、中断处理

4、计算机系统的保护措施

4.1、二态模式

4.2、CPU 保护

4.3、特权指令

4.4、存储器保护

5.进程

6、OS Structure

第三章 Process

1、进程概念：

2、进程的组成部分：

3、进程的状态：

4、进程控制块（PCB）：

5、抢占性问题：

6、进程调度：

7、进程间通信（IPC）：

8、消息传递

9、同步：

第四章 Thread&Concurrency

好处：线程和并发编程带来了多方面的好处，包括：

并行类型：并行编程可以分为两种类型：

多线程模型：描述了用户线程和内核线程的关系，主要有三种模型：

两级模型（M:M+1:1）：

第五章 CPU Scheduling

第六章 Synchronization Tools

信号量的意义和用途

解决方案

考点强调

同步机制

同步机制

死锁和饥饿

第七章 Deadlocks

死锁的必要条件

处理死锁的方法

第八章 Main Memory

保护

连续内存分配

内存碎片

分页

页表的结构和优化

TLB 和 EAT 计算

第九章 Virtual Memory

虚拟内存的优点

虚拟内存的实现

抖动问题

第十、十一章 File System

文件和目录结构

文件共享和保护

文件系统的分层体系结构

文件系统的元数据

目录实现和磁盘空间分配

推荐文章