计算机架构

Konata Lv1
  2025-11-24 16:57:05 2025-11-24 16:57:05 创建   2025-11-24 16:59:47 2025-11-24 16:59:47 更新      

操作系统

操作系统是合理组织，调度计算机工作与资源的分配，进而提供接口与环境的程序合集

1. Process/进程

  1. Process Concepts
    1. 什么是Process? - 进程是一个正在被执行的程序。程序文件进入内存是程序就变得“executable” - 既变为process
    2. 进程是由 程序段，数据段和PCB 3部分合在一起定义的
    3. State of Processes
      1. New: 进程被创建
      2. Running: CPU正在执行进程对应的指令
      3. Waiting: 进程在等待事件的发送 (进程主动等待)
      4. Ready: 进程等待被CPU执行 （可能因为系统中断而回到ready, 被动过程）
      5. Terminated: 进程已经结束执行
    4. PCB - Process Control Block - Identifies the process
      1. PCB of each process resides in the main memory
      2. It is also called as context of the process
  2. Process Scheduling
    1. Queues
      1. Job Queue - All process in System
      2. Ready Queue - Process in memory, permitted by Long-term Scheduler
      3. Device Queue - Processes waiting for I/O device
    2. Process Schedulers
      1. Short-term Schedulers - 决定哪个进程被CPU执行
      2. Mid-term Schedulers - **决定哪些进程应从内存中“挂起（suspend）”或“恢复（resume）”。当系统内存不足，mid-term scheduler 可以将某个 ready 或 waiting 状态的进程换出到磁盘（挂起）**或在资源充足时再 换入内存（恢复）。这个过程被称为swapping。总结而言，他的作用是决定决定进程是否留在内存中。
      3. Long-term Schedulers - 决定哪个进程从job queue进入ready queue
    3. Context Switch
      1. 当CPU从一个进程切换(switch)到另一个进程时，我们需要保存他的状态(state)到PCB，然后再切换。这个过程被称为context switch
  3. Operations on a Process
    1. Create a Process
      1. 父进程创建子进程，子进程再创建子进程，由此形成一棵树
      2. 父进程和子进程之间的资源没有必然联系
      3. 同样进程状态也没有必然联系
    2. Terminate a Process
      1. 使用系统调用exit()来结束进程
      2. 进程占用的资源会被重新分配
      3. 父进程可能等待子进程terminate
  4. Inter-Process Communication
    1. Independent/Cooperate Process - 不会/会受其他进程影响的进程
    2. 存在逻辑：
      1. Information Sharing
      2. Computation Speedup
      3. Modularity
      4. Convenience
    3. 进程间通信方式
      1. Shared Memory/共享储存 - 两个进程通过读写一个共享的数据结构/共享存储区实现通信，但是只共享数据结构/存储区，两个进程不能直接访问对方进程内部的数据。这个共享区域可以是固定大小(bounded)，也可以是不固定大小(unbounded)
      2. Message Passing/消息传递 - 是由逻辑上的send()和recieve()函数实现的。这个实现是在操作系统级别的完成的。具体实现有以下几种方式：
        1. Direct / Indirect Sending - 注明了发送的对象(寻址方式)：Direct直接发送给对方进程；Indirect发送给Mailbox
        2. Synchronous / Asynchronous Sending - 注明了发送后的状态：同步表示发送后/接收前 进入Waiting(Block)状态，等待接受完后继续；异步表示发送后/接收前继续执行而不进行等待，也不改变状态
      3. Pipe Communication/管道通信 - 同步间接的字节流通信方式。这意味着传输的数据无边界，一次写入可以对应多次，多次写入也可能只定义一次读入。消息格式在应用层定义。
        1. Unnamed / Named Pipe(First In First Out, FIFO) - Unnamed管道只能被父子进程间使用，Named Pipe可以被任意有权限的进程访问。
      4. Signal - 通知某个事件发生的机制，参考编程中的Flag
        1. 发送方式
          1. 内核检测到特定事件时，向进程发送信号
          2. 进程通过kill函数向进程(可能是其他进程，也可能是自己)发送信号
        2. 处理方式
          1. 内核调用内核默认的信号处理程序
          2. 进程调用进程自定义的信号处理程序

2. Threads

  1. What is a Thread? - 可以看作轻量级的进程，拥有独立的调用栈，独立的调度逻辑和控制块TCB；但是和所属进程共享数据段和代码段。如果一个进程拥有多个线程，那么意味着它可以同时执行多个任务
  2. 同一进程的线程和线程之间，也共享进程的代码段和数据段，但不共享线程的调用栈
  3. Concurrency Vs. Parallelism - 多线程既可以并行也可以并发
  4. Multi-threading Models
    1. 本身既可以直接被内核支持，也可以只被用户定义的库支持(用户定义+用户管理)
    2. 定义Thread的分类
      1. User Level Thread - 用户创建的进程，他们的创建和切换不会进入内核，没有TCB
        1. 优势：
          1. 因为不经过内核所以运行速度比Kernel Thread快很多
          2. 可以自由选择调度算法
          3. 可以在任何操作系统上运行
        2. 缺点：
          1. 同属于一个Process的User thread无法放在多个处理器上并行
          2. 如果所属的Kernel Process被Block, 那么多个用户线程都将被block
      2. Kernel Level Thread - 直接受操作系统内核管理，是系统执行的单位
        1. 优点：
          1. 可以在多个处理器上并行
          2. 受CPU独立调度，所以可以被单独Block，而非整个进程
        2. 缺点：
          1. 相对较慢
    3. Multi-Threading Model - 两个类别之间的对应关系
      1. Many to One - 创建/切换快，资源占用小 / 阻塞影响全部线程，不支持并发
      2. One to One - 真正并发，系统支持强，线程隔离好 / 内核开销大，线程数量有限，切换慢
      3. Many to Many - 理论上最优，实践中实现复杂，支持有限
  5. Thread Libraries
    1. Thread may be implemented in User Space or in Kernel Space via Thread API
    2. 在用户层面实现thread library, 即使调用不涉及kernel操作
    3. 在内核级别实现thread library, 调用API等同于调用system call
  6. Implicit Threading
    1. Explicit Threading - 编程者创建和管理线程
    2. Implicit Threading - 编译器和运行库调用和管理线程
  7. Threading issues / Designing multithreaded programs
    1. fork() 和 exec()
      1. Fork() - 创建子线程，复制父线程内容
      2. Exec() - 使用一个新的可执行文件替换当前的线程，PID不变，但是代码段，数据段，堆栈都替换为新的线程
      3. 如果fork()+exec()一起调用，那么fork()只需要复制当前线程
      4. 如果fork()单独调用，则需要复制父线程完整的子线程以及结构，否则容易造成线程出错或者“畸形”
    2. Thread Cancellation - 在其完成之前退出
      1. Asynchronous cancellaiton - 立即结束当前线程
      2. Deferred cancellation - 目标线程periodically check是否取消取消自己
    3. Race Conditions（从单线程走向多线程的问题）
      1. 当一个线程修改变量后被switch走，下一个线程修改了同一个变量，当回到最开始的线程时，变量的值已经更改。也就是多个线程同时访问并修改同一个共享变量

3. Process Sychronization

同步 - 进程之间的进行需要满足特定顺序
互斥 - 只有一个进程可以运行特定区间

  1. Background - 防止数据不稳定(Data inconsistency / Race conditions), 并发的进程需要被同步
  2. The Critical Section Problem - 代码段中，处理被共同访问的数据的部分，称为Critical Section
    1. 解决方案需要满足以下3个条件
      1. Mutual Exclusion - 同时只能有一方运行CS是
      2. Progress - 若当前没有程序在运行CS，且有多个程序准备进入CS，那么需要允许这些程序协商谁先谁后进入CS
      3. Bounded Waiting - 进入CS的等待事件应该是有界的
  3. 软件解决方案 - 核心在于如何定义进入CS之前的entry section 和 退出CS之后的exit section
    1. 基本假设：
      1. 每个进程都在以非零的速度运行，但关于运行状况不能做除此以外的假设
      2. 无法假设进程之间交替运行的状态
    2. Peterson‘s Solution
      1. 设置一个变量turn 和一个flag数组，turn负责记录当前谁进入CS, flag负责记录谁需要进入CS。在CS前设置一个while循环，使得不进入CS的一方等待，当另一方退出CS，更新flag布尔数组以后可以进入CS
      2. 当只有两个进程P0, P1时 - turn设置为对方的值，则当两程序并发进行时，不论系统先执行到哪一个程序，总可以保证后执行的程序先进入CS
      3. 两个进程的代码结构完全对称，没有偏向哪一个进程，这是算法的公平性来源之一，且Peterson算法只适用于两个进程。
      4. 证明Mutual Exclusion:
        1. For both P0 and P1 to be in their CS:
          1. Both flag[0] and flag[1] must be true and
          2. Turn=0 and turn=1 (at same time): impossible
      5. 证明Progress：若只有一个进程想进入 CS（另一个 flag=false），它不会阻塞在 while 循环中
      6. 证明Bounded Waiting - 一方退出以后会将flag设置为false, 并且不会再设置为true, 此时另一方可以进入CS，所以不会无限等待
    3. 软件解决方案的缺点
      1. 浪费CPU资源
      2. 编程复杂
      3. 不如操作系统层面直接Block进程
  4. 硬件解决方案 - Locks
    1. 在CS前初始化全局Lock = 0, 当有进程进入CS时使用atomic hardware instructions (比如Test-and-Set、Compare-and-Swap) 将Lock设置为1，结束后重新设置为0。Atomic(原子性) 保证了指令不会被别的进程打断
    2. 优点
      1. 在仍和处理器情况下都适用
      2. 简单且容易证实
      3. 简单支持多个CS的情况
    3. 缺点
      1. 等待的程序依然占用处理器资源
      2. 在一个进程退出CS之后，可能同时有多个进程等待进入(starvation)
      3. 死锁
  5. 操作系统&编程语言解决方案 - Mutex Lock, Semaphores
    1. Mutex Lock 互斥锁 - (抽象概念)
      1. 在内核级别实现 = 在可能的最小代码范围内禁用系统中断
      2. 在软件级别实现 = 使一个进程循环检查lock是否存在(Busy-wait机制)。这种实施方式也被称为spinlock(自旋锁)
      3. 在进入CS前设置Lock，在退出CS时解锁Lock，对Lock的操作必须是原子的(atomic)
    2. Counting Semaphore 计数信号量
      1. 定义一个资源量S，表示可以同时进入CS的最大进程数。如果只允许一个进程进入CS则S=1
      2. 定义一个函数wait(S) / P(S), 当进程请求进入CS时调用。
        1. 调用时若S > 0, 则表示仍有空余资源，进程可以直接进入CS。之后可用资源数S = S - 1。
        2. 调用时若S <= 0, 则说明没有空余资源，进程被wait()函数调用的系统调用阻塞，进入waiting状态。之后可用资源数S = S - 1。S<0 时 abs(S) 表示有多少进程在等待进入CS
      3. 定义一个函数Signal(S) / V(S)，当进程退出CS时调用
        1. 调用后S = S+1。如果有等待队列，则从等待队列中取一个进程进入CS
    3. Binary Semaphore
      1. S 限定为0和1
      2. 只有当S = 1时，wait()可以被成功调用；只有当S = 0时，signal()可以被成功调用
  6. Classic Problems of Synchronization
    1. Bounded Buffer / Producer-Consumer Problem / 生产者-消费者模型
    2. The Readers–Writers Problem / 读者-写者问题
    3. Dining-Philosophers Problem / 哲学家进餐问题

4. CPU Scheduling 1

  1. Basic Concepts
    1. CPU-I/O Burst Cycle - 进程的处理实际上是由 CPU Burst 和 I/O Burst 共同构成的，每个进程所组成的CPU Burst 和 I/O Burst的比重不一样。 I/O Burst占比大的被称为I/O Bound。CPU Burst占比大的被称为CPU Bound。这些比重是CPU scheduler进行调度的重要指标
    2. CPU Scheduler - 用于使process进入不同的state
      1. Short / Mid / Long term Scheduler
    3. Preemptive Scheduling - 系统在分配处理器后可以打断进程并执行Context Switch
    4. Non-Preemptive Scheduling - 系统分配完处理器之后就不能打断进程
    5. 4种情况的CPU scheduling
      1. 进程状态从running变为ready - 比如因为系统调度，系统中断(mid-term scheduler)
      2. 进程状态从waiting变为ready - 比如因为I/O请求完成
      3. 以上这两个状态是Preemptive Scheduling， 因为是系统基于调度策略主动介入切换进程，而不是进程自行释放了CPU资源
      4. 进程状态从running变为waiting - 比如因为I/O请求
      5. 进程结束
      6. 这两个情况是Non-Preemptive Scheduling，因为是进程主动释放了CPU占用，系统必须加入新进程，而不能打断这两个过程
    6. Dispatcher - 具体执行将CPU资源分发给进程的程序。Dispatcher参与所有的进程交换。他具体做以下几件事：
      1. Context Switch
      2. 从内核模式切换到用户模式
      3. 跳转到program counter指向的指令
  2. Scheduling Criteria
    1. Max CPU utilization
    2. Max Throughput - 在单位时间内完成尽可能多的进程
    3. Fairness - 给每个进程平等的分配CPU资源
    4. Min Waiting time - 进程在ready队列中的等待时间尽可能少。这包括进程进入waiting状态后再回到ready队列的等待时间
    5. Min Response time - 进程从进入ready队列到第一次开始执行的时间尽可能短
  3. Scheduling Algorithms
    1. Turnaround time = 进程第一次进入ready队列到执行完成所用的时间 = Terminate time(End Time/Completion Time) - Arrival Time
    2. Burst Time = 进程占用CPU的时间
    3. First Come First Serve(FCFS) - 正如其名，先到达先执行。等待时间很长，效率低
    4. Shortest-Job-First (SJF) No preemption - 选择Burst Time最短的先执行
      1. 优点：平均等待时间和平均response time最短
      2. 缺点：
        1. 不现实，CPU Burst time难以预测
        2. 可能使Burst Time长的进程进入长时间等待和共同等待/Starvation - 饿虎扑食
      3. CPU Burst time 的预测方法 (参考TCP中计算EstimatedRTT的方法)
        1. 下一个CPU Burst Time的预测值 = (1-α) * 当前CPU Burst Time的预测值 + α * 当前真实的CPU Burst Time
        2. 开销很小，因为每个进程都只需要保存两个量
        3. 由此产生了比较实际的SJF
    5. Shortest-Remaining-Time-First SRTF (SJF with preemption) - 当一个CPU burst time比当前处理器中所有进程都短的进程进入队列时，将他替换当前的进程
    6. Priority Scheduling - 给每个进程设置一个优先级(数字)，数字越小优先级越高，优先级越高越早被调度
      1. Priority可能的给出理由有：1.系统判定(内部来源)，比如进程的内存消耗量 2. 用户指定(外部来源)，比如系统管理员的设置
      2. 可能面临的问题：优先级比较低的进程一直没有被执行(Starvation)
        1. 解决方法：按时间提高进程的优先级(数字减小)，比如每15分钟priority - 1
    7. Round Robin Scheduling - 每个进程都分配到固定的CPU时间，在时间结束后进程排到ready队列的最尾端。
      1. 当单位时间量q很大时，算法等价于FCFS
      2. 当单位时间量q很小时，算法无意义，因为要考虑context switch的开销
    8. MultiLevel Queue Scheduling
      1. 把进程分割成多个队列，进程自被分配队列之后不能再移动队列
      2. 比如分割成Foreground queue, Background queue
      3. Scheduling既发生在单个队列中的每个process之间，也发生在队列和队列之间
      4. Fixed priority scheduling (Possible Starvation) / Time slice
    9. Multilevel Feedback Queue Scheduling
      1. 设计多个队列从优先级最高到最低
      2. 进程一开始在优先级最高的队列
      3. 进程的I/O需求越高，就会停留在优先级更高的队列，CPU需求越高，就会被降低到优先级越低的队列
      4. 如果一个进程未能完成自己的quantum(主动进入waiting)，那么他将被留在当前队列
      5. 可以晋升来防止Starvation

5. CPU Scheduling 2

  1. Thread Scheduling
    1. Contention Scope - the scope in which threads compete for the use of physical CPUs
      1. Process/Local Contention Scope - 进程内部的线程竞争CPU资源 (Many to One)
      2. System/Global Contention Scope - 所有的线程竞争CPU资源(One to One)
      3. Many to Many模型中既有1又有2
  2. Multi-processor scheduling
    1. Separate Kernel Configuration - 每个处理器运行自己独立的操作系统，文件系统。
      1. 优点：处理器和处理器之间相互独立
      2. 缺点：一个进程没有办法在多个处理器上并行
    2. Master–Slave Configuration (Asymmetric Configuration) - 存在一个运行操作系统的主处理器Master负责进程的scheduling
      1. 优点：Master可以将任务拆散成多个子任务然后再Slave处理器上并行
      2. 缺点：性能受限于Master节点的性能，也可能造成Master负载过重
    3. Symmetric Configuration SMP - 多个处理器共享OS，每个处理都可以接收I/O设备和系统中断。需要不断给各个处理器加锁才能保证并行。为了避免并发访问导致冲突，操作系统将调度器、文件系统调用等模块设计为尽可能互相独立的结构或线程安全的组件，这样可以安全高效地并发执行多个进程。
    4. Processor affinity - 尽可能的将一个进程放在同一个处理器上运行，以减少在不同处理器之间移动的内存消耗和Context switch成本
      1. Soft processor affinity - 尽可能的将一个进程放在同一个处理器，但不能保证进程一定停留在这个处理器
      2. Hard processor affinity - 将进程限制在他自己选择的一个或者几个处理器之间
    5. Load Balancing- 尽可能的平均分配进程，以保证多处理器系统的性能被充分利用
      1. Push migration = Process goes from higher load processer to lower load processer. This is done by a system process periodically check all queues
      2. Pull migration = Process raid by lower load processer from higher load processor
    6. 多处理器调度方案
      1. 共享就绪队列 - 所有处理器共享一个ready queue, 每次有cpu空闲就从队列中取一个进程，这个方法虽然保证处理器不会空闲，但是处理器亲和性差
      2. 私有就绪队列 - 每个处理器有自己的ready queue, 保证了Processor Affinity，但是需要load balancing来保证处理器效率
  3. Real Time CPU scheduling (Skipped)
  4. Algorithm Evaluation
    1. Deterministic evaluation - 计算一个具体的指标，比如进程的平均等待时间
    2. Queueing Models - 在进程进出队列的速率一致时，队列中的平均进程 = 入队速率 * 等待时间
    3. Simulations - 通过过去数据模拟算法效率

6. DeadLock

  1. Condition & Definition of Deadlock
    1. MUTUAL EXCLUSION: 一次只有一个进程占用某个资源
    2. HOLD AND WAIT: 进程需要等待某个资源才能继续
    3. NO PREEMPTION: 进程不能被切换
    4. CIRCULAR WAIT: 出现了进程资源需求的闭环，一个正在等待的进程持有其他一个或者多个进程需要的资源
  2. Deadlock prevention
    1. Mutal Exclusion - 难以避免
    2. Hold and Wait - 保证当一个进程请求资源时，不持有任何资源
    3. No preemption - 如果进程请求了一个别的进程占用的资源，那么系统可能切换后者
    4. Circular wait - 设计一套资源使得，如果一个进程获得了R, 则他只能后续只能获取R以后的资源
  3. Deadlock Avoidance
    1. 方式
      1. 不启动可能导致死锁的程序
      2. 拒绝可能导致死锁的请求
    2. Safe state - 系统至少存在一种资源分配方式，使系统不进入死锁
    3. A resource request is feasible, only if the total number of allocated resources of a resource type does not exceed the total number of that resource type in the system
    4. 简单来说，把每个资源想象成一个栈，如果使用中 + 需求的资源总和超过了栈的容量，那么就会进入unsafe state(可能导致死锁)
    5. Deadlock Avoidance in Single Instance of Resources - 使用图示
    6. Deadlock Avoidance in Multiple Instances of Resources - Banker’s Algorithm
      1. Safety test algorithm - 检测当前系统是否处在Safe State
      2. Resource request algorithm - 检测对资源的请求是否会导致系统进入unsafe state
      3. 定义4个矩阵Available, Max, Allocation, Need。后三个分别表示进程 i 对资源 j 的 max, allocation, need。Available 表示 j 资源总共有 k 个
      4. 定义一个函数is_Safe(), 用于Safety test algorithm。其定义为：
        1. 定义Work = Available；Finish[i] = 进程 i 是否正确结束，是为True, 否则为False
        2. 每次找到一个还未结束的进程 i，判断是否Need[i] <= Work，如果是，则假设他结束 Finish[i] = True，并将其占有的资源释放 Work += Allocation[i]
        3. 如果无法再满足任何进程， 则系统处于unsafe state，否则若全部进程都可以被完成，系统处于safe state
      5. 定义一个函数Request_i(j)，用于判断进程 i 请求资源 j 是否能被接收，其定义如下：
        1. 检测request_i <= Need_i，如果不是则报错
        2. 检测request_i <= Available_i 则该分配会进入unsafe state
        3. 否则假设资源已经被分配，然后运行is_Safe()
  4. Deadlock detection
    1. single instance of resource - 画图，只有当Pi 在等待Pj时，使箭头从i指向j，当图中出现圈/循环指向时，就存在死锁
    2. Multiple instance of resource - 跟avoidance一样，设置3个数组，Available 表示每种资源当前剩余多少个实例，Allocation 表示 进程i 当前被分配了多少 资源j ，Request 表示 i 进程当前对 j 资源有多少需求。
    3. 剩下的步骤和is_Safe()相同，除了在初始化Allocation时，只初始化当前有分配资源的进程。以及结束时，若存在Finish[i] == false, 则Finish[i] 既为死锁的进程
  5. Deadlock Recovery
    1. Process Termination / Abort Process
      1. 使所有死锁的进程强制退出
      2. 使死锁的进程一个一个退出，直到不再死锁
        1. 退出的顺序取决于进程的优先级 / 进程已经停留的时间 / 进程还需多少时间 / 具体哪个资源被占用 等等
    2. Resource Preemption - 遵循以下几个步骤
      1. 选择被死锁的进程中一个需要被拿走资源的进程
      2. 将他会被回滚到系统处在safe state的状态，从那一刻开始重新执行 / 或者通过Context Switch等待队列
      3. 可能造成的结果 - Starvation - 每次都是相同的进程被选择
        1. 可做出的对应：1.限制一个进程可以被选择的次数 2.提高进程在牺牲者选择策略中的优先级

7. Main Memory

  1. MMU - Memory Management Unit
    1. 储存管理有几个要求：
      1. Protection - 用户进程 和 操作系统 需要被隔离。用户进程之间也需要被隔离
      2. Relocation - 可以在进程执行的过程中移动其使用的储存而不影响其执行
      3. Sharing - 允许多个进程访问同一段储存
      4. Logical Organization & Physical Organization - 需要组织好内存和磁盘的关系
  2. 程序从编译器开始进入内存的完整流程
    1. 编译 - 编译器将程序划分成数个 目标模块
    2. 链接 - 将 目标模块 链接上库函数 形成装入模块
    3. 装入 - 将程序装入 装入模块 然后进入内存
    4. 将一个装入模块 装入内存有几种方式
      1. 绝对装入 - 使用程序和编译器写死的绝对地址
      2. 可重定位装入 - 使用 相对地址 转换成物理地址时只作偏移
      3. 动态运行时装入 - 保持不变的逻辑地址，在程序执行时CPU动态转换为物理地址
    5. 同时链接也有三种模式
      1. 静态链接 - 形成装入模块时链接
      2. 装入时动态链接 - 在装入时动态链接
      3. 运行时动态链接 - 在运行需要时链接
  3. Memory Protection - Base register + Limit Register (基地址寄存器 + 限长寄存器)
    1. 不论使用哪种地址和这两个register相比较，最终可用的物理地址是 Base - Base + limit
  4. Memory Relocation - 通过relocation register (也就是Base register) 改变程序逻辑地址对应的物理地址。除非进程执行在内核态，进程执行过程中relocation register也不会改变
  5. Memory Allocation - Contiguous / Non-Contiguous
    1. Contiguous Memory Allocation
      1. Fixed Partitioning - 固定长度的内存分割
      1. 问题：Internal fragementation - 被分配的进程未能全部占用当前的分割
      2. Dynamic Partitioning - 动态长度的内存分割
      1. 进程放置方法
      1. First Fit - 第一个合适大小的内存块
      2. Best Fit - 最小合适大小的内存块
      3. Worst Fit - 分配最大的内存块
      2. 问题：External Partitioning - 已经推出的进程空出的内存块大小单个不够新来的内存块使用
      3. 解决方案：1. Compaction - 把当前被占用的内存移动到内存空间一侧 2.使用Non-Contiguous Allocation
    2. Non-Contiguous Allocation - Segmentation & Paging
      1. Segmentation - 把进程分为数块，每块的逻辑地址为<segmentation number, offset>
        1. 同样有Segement table 把这个逻辑地址对应到物理地址
        2. 但是内容不同 - Segement table 包含的是Base + limit（参考Base Register）
      2. Paging
          1. 将内存分割成相同大小的小块，并编号
        2. 将一个进程分割成与单个内存块大小相同的多个小块 (逻辑分割，一个小块对用多个逻辑地址，所以具体查找时需要使用offset进行精确定位)
        3. 把分割好的进程根据页表放入内存块
        4. 需要取时，只需要使用进程块对应的内存块的编号*内存块大小+偏移量，就可以取到对应的进程块
      3. Implementation of Page Table
        1. Page table is kept in PCB
        2. When A process is accessed, its page table is loaded into Page-table base register (PTBR). It’s length is loaded into Page Table Length Register (PTLR)
        3. 当进程切换发生时，page table也会随Context Switch一并切换
        4. 传统的Page Table实施会产生Two Memory Access problem, 既每次访问一个逻辑地址时都需要访问两次物理地址，第一次为查Page Table页表，第二次为访问对应的物理地址。
        5. 这个问题可以使用一种特殊的Fast-lookup hardware cach解决，其名称为Translation Look-aside Buffers (TLBs)
        6. 可以理解为一个快查表，在查询PTBR之前先查询TLB, 如果没有查到，再去查询PTBR，并把查到的结果存入TLB。
        7. Effective memory-access time (EAT) = A (E + M) + (1 - A) (E + 2 x M)，其中A为TLB的命中率 (Hit Ratio), E 为查询TLB需要的时间，M为查询Main Memory需要的时间
        8. Valid (v) or Invalid (i) Bit In A Page Table (Memory Protection) - 在页表中注明当前Frame是否valid，如果访问invalid frame, 则可能导致Page fault 或者 系统中断
        9. Shared Pages - 为了进程之间的通信和存储效率，有时可能出现多个进程共享一段代码的情况，这时page table会指向相同的frame，内存中也只有这一份这段代码。
        10. Page Table的一些结构
          1. Hierarchical Paging - 将逻辑地址分割为处在多个不同层级的多个Page Table
          2. Hashed Page Tables - 使用哈希函数对页号（Page number）进行哈希，从而快速定位页表项的数据结构。
          3. Inverted Page Tables - 反过来使用Frame对应进程，整个系统使用一张表。因为表庞大，一般使用TLB作为加速
        11. Hierarchical Paging - Two Level Page Table 二级页表
          1. 将page table分成两级, p1 和 p2, 查询时先从第1级别定位到p1，然后再从p1所指向的第2级别的表中找到对应的p2，之后和正常paging一样使用offset定位

8. Virtual Memory

  1. Background - 如果一个程序过大无法加载到内存中，但是其中又有很多不常访问/未被访问的代码，应该如何操作？ - 使用虚拟内存系统（既需要软件支持，又需要硬件支持）
    1. 在磁盘上开一块空间，称为Swap Space / Swap Partition，将程序段储存在Swap Space中，需要时再放入内存。
    2. 程序在内存中的部分称为resident
  2. Demand Paging - 只有当page被调用时才将他们swap (page-in) 进内存，也就是当一个进程产生了一个逻辑地址，指向一个不在内存中的page的时候 (Page Fault)
    1. 当页表中 Page对应的frame 被设置为 invalid 时，他可能：
      1. 不在进程的逻辑地址空间中
      2. 在进程的逻辑地址空间中，但是不在内存中
      3. 访问这个page 会产生Page Fault，引发同步中断 (causes a trap to the OS)，将控制权转交给内核态。
      4. 如果此时内核中没有空的 Frame了，那么必须要有frame被page-out 也就是换出内存/
      5. 选择哪个frame/page被换成，取决于page-replacement algorithms
    2. The Effective Access Time (EAT) = (1 - p) * Memory Access Time + p * Page Fault Time，其中 p 为 page fault 的概率
  3. Copy-on-Write in Operating System - 也就是多个进程共享相同的page，直到其中有进程需要修改任意page时，触发Page fault，然后操作系统再为其复制一份该进程当前需要使用的page的副本。能显著提高fork()的性能。
  4. Page Replacement -
    1. 两个基本原则
      1. 尽可能减少Page Fault的发生率 - 也就是说经常被调用的page不应该被换出
      2. 尽可能提高Page Fault的处理速度 - 提高处理的代码效率，尽可能换出已经未被修改的page (比如使用dirty bit注明page是否被修改)
    2. Basic Page Replacement
      1. 寻找Free Frame - 如果有Free Frame直接使用Free Frame
      2. 如果没有，使用Page Replacement alogrithm找到一个victim
      3. 检查modify bit，判断是否需要先将page内容写入磁盘
      4. 将需要的page换入(page-in)到需求的位置，更新page table
    3. Page-replacement algorithms
      1. First In First Out Algorithm - 最早被分配的page成为victim
      2. Optimal Algorithm - 未来最长时间不会被使用的page成为victim (不现实)
      3. Least Recently Used Algorithm - 最长时间未被使用的page成为victim (两种实施方法)
        1. 使用Counter实现 - 给page table中每一项都安排一个counter。当这一项对应的page被调用时，将系统时钟更新给这一项的counter。在需要选择时，选择进程的page table中最小的counter
        2. 使用Stack实现 - 使用一种类似栈的结构维护page的访问，最早被访问的处在栈底。当“栈”中的任意一个page被调用了，他就被提到栈的顶部，同理新出现的page也加入栈顶部。使用LRU时直接从栈底选择。
      4. Second-Chance Alogorithm - 一个循环的数组包含所有的Frame, 每个Frame 包含一个 Reference bit , 表明他自上一次 Page replacement以来有没有被访问过 (包括读和写) 如果有则RB = 1, 否则 = 0. 当需要Page Replacement的时候，循环检测一遍整个数组，如果有1，则置为0，并到下一个；如果当前=0， 则该page为victim
      5. Counting Alogrithms - 设置一个Counter统计每个page被访问的次数，LRU = MIN (Counter)
  5. Frame Allocation
    1. Equal Allocation - 每个进程分配等量的Frame
    2. Proportional Allocation - 根据进程的Page Number大小来分配 (等比例分配)
  6. Thrashing - a process is busy swapping pages in and out ➢ a process spends more time paging then executing。这会导致CPU认为当前负载很低，进而提高并发 -> 增加线程 (恶行循环)

9. Mass Storage System

  1. Secondary Storage
    1. Sequential Secondary Storage - Stores records sequentially
    2. Direct Secondary Storage - stores records in discrete and seperate location
    3. Moving-head Disk Mechanism - 一个硬盘是由:
      1. Platter - 物理上的磁性盘片，通常一个磁盘最多16片
      2. Track - 磁性盘片上的轨道
      3. Sector - 轨道中的具体扇区，磁盘访问的最小单位
      4. Cylinder - 多个盘片上相同编号track的集合
      5. Head - 磁头，每个磁头对应一个盘片
      6. 一个磁盘地址可以被 Cylinder/轨道集合 + Head/盘片编号 + Sector/具体的扇区 (CHS) 定义
    4. Disk Speed
      1. Seek time = Move to the corresponding cylinder
      2. Rotational latency = Rotate to the corresponding sector
      3. Positioning time / Random Access Time = Seek time + Rotational lantency
      4. Transfer time = Time took to transfer data from sector to application
      5. Disk access time = seek time + rotational latency + transfer time
      6. Disk access time是一个顺序流程：先移动磁头 ➜ 再等待旋转 ➜ 最后传输数据。
  2. Disk Structure
    1. 逻辑上被视为一个一维数组
    2. Disk Controller 负责将一维数组的下标映射到CHS
  3. Disk Attachment
    1. Via I/O ports - 比如通过 IDE / ATA / USB / SATA / M.2
    2. Via a remote host - 在分布式系统上通过 TCP/IP 协议访问
  4. Disk Scheduling - minimize positioning time (Seek Time + Rotational Latency)
    1. Scheduling is performed by both O.S. and disk itself - 因为OS只负责控制workload的顺序，而disk本身知道具体的positioning time
    2. Minimize arm movement / Minimize mean response time
    3. First Come First Serve
    4. Shortest Seek Time First (贪心)
    5. SCAN - 从一个点移动向disk的一个边界(假设为左)，触及边界后继续移动像反向的边界(右)，在过程中访问需求的cylinder
    6. Circular-Scan - 从一个点移动向disk的一个边界(假设为左)，触及边界后 从另一个边界(右)开始继续移动向边界(左)，在过程中访问需求的cylinder。在第一次触及边界到移动到相反的边界之间不访问cylinder
    7. Look - 优化版的Scan，不移动到边界只移动到需求的最靠近边界的cylinder
    8. C-Look - 优化版的Scan，不移动到边界只移动到需求的最靠近边界的cylinder
  5. Disk Management
    1. Low Level formating / Physical Formatting - 低级格式化，把一个磁盘分为多个扇区，每个由header， data，ID
  6. Swap space Management
  7. RAID (Skipped)

10. File System

  • 标题: 计算机架构
  • 作者: Konata
  • 创建于 : 2025-11-24 16:57:05
  • 更新于 : 2025-11-24 16:59:47
  • 链接: http://blog.suzumiyaharuhi.net/2025/11/24/计算机架构/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
计算机架构
  1. 操作系统
    1. 1. Process/进程
    2. 2. Threads
    3. 3. Process Sychronization
    4. 4. CPU Scheduling 1
    5. 5. CPU Scheduling 2
    6. 6. DeadLock
    7. 7. Main Memory
    8. 8. Virtual Memory
    9. 9. Mass Storage System
    10. 10. File System