[OSTEP Chapter 13] The Abstraction : Address Spaces

For program:

stack keep track and pass parameters and return values to and from routines

heap is used for dynamically-allocated, user-managed memory

Goal of virtual memmory system:

  1. transparency 透明化 ,程序不需要意识到内存被虚拟化,让程序以为自己访问的是实际的物理内存
  2. efficiency 效率,OS需要力争在时间和空间上让程序运行更有效率
  3. protection 保护安全,OS需要保护各个进程之间的内存安全


[OSTEP Chapter 9] Scheduling : Proportional Share

proportional-sahre is a different type of scheduler

其中的一个例子是抽签策略 lottery scheduling

lottery scheduling 决定下一个运行的job , 长时间没有抽中的job 增加优先级

Tickets represent the share of a resource that a process (or user or whatever) should receive

Tickets has number

Ticket Mechanisms

  1. ticket currency Currency allows a user with a set of tickets to allocate tickets among their own jobs in whatever currency they would like; the system then automatically converts said currency into the correct global value.
  2. ticket transfer A process can temporarily hand off its tickets to another process
  3. ticket inflation A process can temporarily raise or lower the number of tickets it owns

[OSTEP Chapter 8] Scheduling: The Multi-Level Feedback Queue

MLFQ 基本规则:

  1. Rule 1: If priority(A) > Priority(B), A runs (B doesn’t)
  2. Rule 2: If Priority(A) = priority(B),A & B run in RR
  3. rule 3: when a job enters the system , it is placed at the highest priority (the topmost queue)
  4. rule 4a: if a job uses up an entire time slice while running , its priority is reduced (i.e.,it moves down one queue).
  5. rule 4b: if a job gives up the CPU before the time slice is up, it stays at the same priority level


  1. 如果有很多敏感jobs,需要长时间运行的jobs 可能会一直得不到CPU资源
  2. 有些程序会作弊得到更多资源,比如在slice time 结束之前触发一个I/O 操作
  3. 一个程序可能会随时改变行为模式

解决问题的方案 (problem 1,3):

Rule 5: After some time period S, move all the jobs in the system to the topmost queue

解决程序作弊的方案 ( problem 2 增强版的Rule 4):

Rule 4 : Once a job uses up its time allotment at a given level (re-gardless of how many times it has given up the CPU), its priority is reduced (i.e., it moves down one queue).

[OSTEP Chapter7] Scheduling: Introduction

By now low-level mechanisms of running processes should be clear. However, we have yet to understand the high-level policies that an OS scheduler employs.


workload accumptions

  1. Each job runs for the same amount of time
  2. All jobs arrive at the same time
  3. Once started, each job runs to completion.
  4. All jobs only use CPU
  5. The run-time of each job is known

策略计量单位 turnaround time

T[^turnaround] = T[^completion] – T[^arrival]


7.3 First In, First Out (FIFO)

FIFO 的优点:简单清晰,易于实现,工作良好

7.4 Shortest Job First (SJF)


7.5 Shortest Time-to-Completion First (STCF)


新计量单位 : Response Time 相应时间 —-任务到达系统和被体统调用的时间差

T[^response] = T[^firstturn] – T[^arrival]


7.7 Round Robin

instead of running jobs to completion, RR runs a job for a time slice (sometimes called a scheduling quantum) and then switches to the next job in the run queue

7.8 Incorporation I/O 纳入IO/考虑IO

relax assumption 4

Doing so allows for overlap, with the CPU being used by one process while waiting for the I/O of another process to complete

[OSTEP chapter 6] Mechanism: Limited Direct Execution

操作系统通过time sharing 的方式来虚拟化CPU 要做到以下两点:
基本解决方案:Limited Direct Execution  这个方案带来了两个问题
The first :
if we just run a program, how can the OS make sure the program doesn’t do anything that we don’t want it to do, while still running it efficiently?
The second:
when we are running a process, how does the operating system stop it from running and switch to another process, thus implementing the time sharing we require to virtualize the CPU
problem #1 : Restricted Operations 严格控制操作
user mode 限制进程能访问操作到的资源
kernel model 能像操作系统一样访问所有资源
通过操作系统的 user mode 和 kernel mode  以及两者之间的转换指令[特殊的 return-from-trap 指令]来控制进程的执行
但是允许程序在内核模式到处跳转是一个Very Bad Idea, 为了直接这一点内核在启动boot time 的时候用建立一个trap table.
系统在启动的时候就会配置好硬件,告诉硬件什么时候执行什么代码,而且会告诉硬件trap instruction 的句柄 handle
Problem #2 Switching Between Process 进程间的切换
A Cooperation Approach : Wait For System Calls
一个合作的方式: OS 信任application,application会自己调用system call 或者 自己产生了一个错误异常调用一个trap 把从职权交回OS
A Non-Cooperation Approach : The OS Take Control
如果碰到拒绝交出控制权的process ,  可以通过  time interrupt 【硬件级别支持】 来使 OS 重新获取控制权;每隔一段时间就产生一个中断  ,系统中预设好的interrupt handler 会运行,这个handler 拿回控制权然后会决定是不是接着运行之前的process ; timer 的硬件要保存中断时候的上下文环境。
Just run the program you want to run on the CPU ,but first make sure to set up the hardware so to limit what the process can do without OS assistance