open-courses
  • 公开课笔记
  • CMU 15-445/645 Database Systems
    • Relational Data Model
    • Advanced SQL
    • Database Storage
    • Buffer Pools
    • Hash Tables
    • Tree Indexes
    • Index Concurrency Control
    • Query Processing
    • Sorting&Aggregations
    • Join Algorithms
    • Query Optimization
    • Parallel Execution
    • Embedded Database Logic
    • Concurrency Control Theory
    • Two Phase Locking
    • Timestamp Ordering Concurrency Control
    • Multi-Version Concurrency Control
    • Logging Schemes
    • Database Recovery
    • Introduction to Distributed Databases
    • Distributed OLTP Databases
    • Distributed OLAP Databases
  • UCB - CS162
    • OS intro
    • Introduction to the Process
    • Processes, Fork, I/O, Files
    • I/O Continued, Sockets, Networking
    • Concurrency: Processes & Threads
    • Cooperating Threads, Synchronization
    • Semaphores, Condition Variables, Readers/Writers
    • Scheduling
    • Resource Contention & Deadlock
    • Address Translation, Caching
    • File System (18,19,20)
    • Distributed Systems, Networking, TCP/IP, RPC (21,22)
    • Distributed Storage, Key-Value Stores, Security (23)
    • Security & Cloud Computing (24)
    • Topic: Ensuring Data Reaches Disk
  • MIT - 6.006
    • Sequence and Set Interface
    • Data Structure for Dynamic Sequence Interface
    • Computation Complexity
    • Algorithms and Computation
    • Structure Of Computation
    • Graph & Search
    • Tree & Search
    • Weighted Shortest Paths
    • String Matching, Karp-Rabin
    • Priority Queue Interface & Implementation
    • Dictionary Problem & Implementation
    • Sorting
    • Dynamic Programming
    • Backtracking
    • Self-Balancing Tree
  • MIT - 6.824
    • 2PC & 3PC
    • Introduction and MapReduce
    • RPC and Threads
    • Primary/Backup Replication
    • Lab: Primary/Backup Key/Value Service
    • Google File System (GFS)
    • Raft
    • Lab: Raft - Leader Election
    • Lab: Raft - Log Replication
  • Stanford-CS107
    • 原始数据类型及相互转化
    • 指鹿为马
    • 泛型函数
    • 泛型栈
    • 运行时内存结构
    • 从 C 到汇编
    • 函数的活动记录
    • C 与 C++ 代码生成
    • 编译的预处理过程
    • 编译的链接过程
    • 函数的活动记录续、并发
    • 从顺序到并发和并行
    • 信号量与多线程 1
    • 信号量与多线程 2
    • 复杂多线程问题
    • 函数式编程 - Scheme 1
    • 函数式编程 - Scheme 2
    • 函数式编程 - Scheme 3
    • 函数式编程 - Scheme 4
    • 函数式编程 - Scheme 5
    • Python 基础
  • MIT - 6.001 - SICP
    • 什么是程序
    • 程序抽象
    • 替代模型
    • 时间/空间复杂度
    • 数据抽象
    • 高阶函数
    • Symbol
    • 数据驱动编程与防御式编程
    • 数据抽象中的效率与可读性
    • 数据修改
    • 环境模型
    • 面向对象-消息传递
    • 面向对象 - Scheme 实现
    • 构建 Scheme 解释器
    • Eval-Apply Loop
    • Normal Order (Lazy) Evaluation
    • 通用机
    • 寄存器机器
    • 子程序、栈与递归
    • 在寄存器机器中执行
    • 内存管理
  • MIT - 6.046
    • Randomized Algorithms
    • Skip Lists
  • System Design
    • Twitter
    • Cache Consistency & Coherence
  • DDIA 笔记
    • Replication
    • Transactions
    • The Trouble with Distributed Systems
    • Consistency & Consensus
  • Papers We Love
    • Consistent Hashing and Random Trees (1997)
    • Dynamic Hash Tables (1988)
    • LFU Implementation With O(1) Complexity (2010)
    • Time, Clocks, and the Ordering of Events in a Distributed System (1978)
    • Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
    • Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
  • Release It 笔记
    • Anti-patterns & Patterns in Microservice Architecture
  • Database Design
    • Log Structured Merge (LSM) Tree & Usages in KV Stores
    • Prometheus
Powered by GitBook
On this page
  1. UCB - CS162

Introduction to the Process

PreviousOS introNextProcesses, Fork, I/O, Files

Last updated 6 years ago

本节主要涉及到四个基本 OS 概念:

  • 线程 (Thread):单个独立的执行上下文 (Single unique execution context),它其中包含如 Program Counter (PC)、Registers、Execution Flags、Stack 等信息。

  • 地址空间与地址转换 (Address Space & Translation):所有运行中的程序都认为自己拥有完整、连续的内存地址空间,而 OS 在背后完成虚拟地址空间到物理地址空间的转换。

  • 进程 (Process):程序运行起来就成为进程,每个进程都认为自己有一块完整、连续的内存地址空间,同时每个进程可能拥有一个或多个线程在控制其运行过程。

  • 双模操作及保护 (Dual Mode operation/Protection):

    • OS 为用户进程提供了虚拟的硬件服务,如网络、硬盘、输入输出等,但用户进程不能直接接触硬件本身,而只能通过 OS 获取。这就需要双模操作,即 user mode 和 kernel mode,来保护整个过程顺利、安全地进行。

    • 不同用户进程运行同样需要隔离保护,OS 可以通过控制地址转换的过程保证不同的进程只能在不同的物理地址空间中寻址。

程序的运行过程

工程师写完程序源代码后,交由编译器去将源代码编译成可执行机器码。运行程序时,OS 将可执行机器码被载入到内存中,并为其创建 Stack 和 Heap,然后将控制权转交给该进程,为该进程提供各种虚拟服务,同时保护 OS 以及其它用户进程与之互不干扰。

进程的运行过程如上图所示,简而言之就是一个 "获取指令 - 执行指令" 的循环:

  • 获取 PC 所指的指令

  • 解析指令

  • 执行指令

  • 将结果写出到寄存器或内存

  • 更新 PC,让它指向下一条指令

  • 回到第一步

基本 OS 概念

线程 (Thread)

线程是最小的执行单位,它仅包含执行所需上下文信息。当线程中的上下文信息映射在 CPU 中的寄存器上时,则线程处于运行状态。

  • 寄存器 PC (program counter) 保存线程下一条指令所在地址

  • 寄存器 SP (stack pointer) 保存线程栈顶的地址

  • ...

程序的地址空间 (Program's Address Space)

如上图所示,每个程序在运行时都拥有自己的内存地址空间,这个空间被划分为 4 个主要区域:

  • 代码段 (Code Segment):代码段保存着控制程序执行的可执行机器码,寄存器 PC 就指向这个区域中的某个地址。

  • 静态数据 (Static Data):静态数据保留程序所需的全局的静态数据

  • 堆 (Heap):堆用于内存空间的动态分配,它由低地址向高地址方向增长

  • 栈 (Stack):栈用于存储局部、临时的数据,它由高地址向低地址方向增长

当 OS 中同时存在多个正在运行的程序时,内存中就会存有多个内存寻址空间,如下图所示:

每个工程师在构建程序时,无需考虑程序运行时环境中存在的其它程序,每个程序都认为自己:

  • 拥有独立的 CPU

  • 拥有独立的内存空间

那么 OS 如何为每个运行的程序创造这种假象?以多处理器的假象为例:

假设系统实际上只有一个处理器,OS 如何用一个处理器抽象出多处理器的假象?最简单直观的方法就是分时,为每个正在运行的程序轮流分配处理器的使用时间,当一个程序的使用时间到期时,就把它的执行上下文信息储存起来,然后载入队伍中下一个正在运行的程序的执行上下文信息,继续执行,如下图所示:

这就是所谓的并发。但有收获必有牺牲,并发引入了系统复杂度。所有硬件都为所有程序共享,那么 OS 就需要为所有硬件创造假象,如 CPU、DRAM、I/O 设备等等。提供了假象还远远不够,如果所有运行中的程序都分享所有硬件,这意味着每个运行的程序都有机会获取、修改共享的硬件中的信息,如 DRAM,因此 OS 除了提供每个运行的程序都独占硬件的假像,还需要提供保护机制,让不同的运行程序在不破坏其它运行程序的同时独占硬件。

进程 (Process)

前面反复提到的运行中的程序实际上就是进程。进程是一个权限受限的执行环境,OS 在尽量减少效率损失的前提下,在进程之间 (包括用户进程与用户进程、用户进程与 OS 进程)加上一层严格的保护,使得进程互相隔离,互不干扰。而每个进程内部,可以运行一个或多个线程,这些线程共享进程提供的执行环境。OS 的保护机制主要依靠内存地址转换,所有进程只被允许访问属于自己的物理内存空间,其它保护机制之后会介绍。进程的示意图如下所示:

双模操作 (Dual Mode Operation)

以 UNIX 系统结构为例,如下图所示:

进程在执行中分为两种模式,User Mode 和 Kernel Mode,处于 Kernel Mode 的进程可以直接操作硬件,而处于 User Mode 的进程无法直接访问硬件。处于 User Mode 的进程要使用硬件服务,需要通过进入 Kernel Mode 才能完成相应的操作,通过对模式切换的控制,OS 得以保证它对用户进程的抽象不泄露。

进程在两种模式之间切换存在以下几种情况:

User -> Kernel

  1. 系统调用 (system call):进程像函数调用一样请求系统服务,只不过这个服务的程序在进程之外

  2. 中断 (interrupt):如 CPU 时间片到了、I/O 事件。中断通常与当前进程无关,来自于运行时的外部环境

  3. 异常 (exception):一些程序异常,如除于0

  4. 结束运行 (exit)

Kernel -> User

  1. 开始运行 (exec)

  2. 从系统调用返回

  3. 从中断处理返回

进程内存空间的保护策略

Simple Protection: Base and Bound (B&B)

在启动程序时,为其分配整块的内存空间,记录下该快空间的 Base 和 Bound,如放在特定的寄存器中,每次访问内存空间时检查地址是否在 Base 和 Bound 之间。该策略确实能够将不同的进程隔离开,但缺点是:

  • 每个进程认为自己拥有独立完整的内存空间的假象消失,因为 Base 和 Bound 每次的位置不一样,程序中的寻址操作也需要相应地变化,在一个系统上编译的代码也无法在其它系统中使用。

  • 多个运行同一段程序时,需要重新分配一段完整的内存空间。

Address Space Translation

程序仍然认为自己拥有从 0 开始的所有内存空间,但程序的地址只是虚拟内存地址,在运行时,程序中的地址会经过 translator 被转换成实际的物理内存地址,如下图所示:

Address translation with Base and Bound

将 Base and Bound 策略与 translation 策略相结合,可以得到如下策略:

这样就避免了 Base and Bound 策略的第一个缺点,OS 为进程提供的假象成立。但 Address Translation with Base and Bound 的缺点就在于,在程序运行之初,OS 就要决定为 heap 和 stack 分配多大的空间,而 heap 和 stack 之间的空白区域无法精细地控制,甚至在大部分时间内这片区域没有被合理利用。

Paging

为了更精细化地控制 heap 与 stack 之间的空间,OS 可以把空间以更小的单位划分 --- page,然后在进程的虚拟内存地址与物理内存地址之间同样增加一层转换,这时 Code、Data、Stack 和 Heap 将可能占用多个 page,而这多个 page 之间并不一定要位于连续的物理内存地址上,示意图如下所示:

同时,我们可以将不同进程的部分区域,如 Code 区域,中的部分 page 设为共享,这在多个进程之间的保护和共享之间找到了更好的平衡。在未来的课程中会深入介绍 paging 的具体做法。

举例:web server

参考

Lecture Note
Lecture Video