#include <stdio.h> void main() { int n = 0; printf(“0x%x\n”,&v); }

讯享网//file:fs/exec.c static int do_execve_common(const char filename, …) { bprm_mm_init(bprm); … }

//file:fs/exec.c static int bprm_mm_init(struct linux_binprm bprm) { //申请个全新的地址空间 mm_struct 对象  bprm->mm = mm = mm_alloc(); bprm_mm_init(bprm); }

讯享网//file:fs/exec.c static int bprm_mm_init(struct linux_binprm *bprm) { bprm->vma = vma = kmem_cache_zalloc(vm_area_cachep, GFP_KERNEL); vma->vm_end = STACK_TOP_MAX; vma->vm_start = vma->vm_end - PAGE_SIZE; … bprm->p = vma->vm_end - sizeof(void ); }

//file:include/linux/mm_types.h struct vm_area_struct { unsigned long vm_start; unsigned long vm_end; … }

讯享网//file:fs/binfmt_elf.c static int load_elf_binary(struct linux_binprm bprm) { //ELF 文件头解析  //Program Header 读取  //清空父进程继承来的资源  retval = flush_old_exec(bprm); … current->mm->start_stack = bprm->p; }

//file:arch/x86/mm/fault.c static void kprobes __do_page_fault(struct pt_regs *regs, unsigned long error_code) { … //根据新的 address 查找对应的 vma  vma = find_vma(mm, address); //如果找到的 vma 的开始地址比 address 小  //那么就不调用expand_stack了，直接调用  if (likely(vma->vm_start <= address)) goto good_area; … if (unlikely(expand_stack(vma, address))) { bad_area(regs, error_code, address); return; } good_area: //调用handle_mm_fault来完成真正的内存申请  fault = handle_mm_fault(mm, vma, address, flags); }

讯享网//file:mm/memory.c int handle_mm_fault(struct mm_struct mm, struct vm_area_struct vma, unsigned long address, unsigned int flags) { … //依次查看每一级页表项  pgd = pgd_offset(mm, address); pud = pud_alloc(mm, pgd, address); pmd = pmd_alloc(mm, pud, address); pte = pte_offset_map(pmd, address); return handle_pte_fault(mm, vma, address, pte, pmd, flags); }

//file:mm/memory.c int handle_pte_fault(struct mm_struct *mm, 
讯享网<span class="k">struct</span> <span class="n">vm_area_struct</span> <span class="o">*</span><span class="n">vma</span><span class="p">,</span> <span class="kt">unsigned</span> <span class="kt">long</span> <span class="n">address</span><span class="p">,</span> <span class="n">pte_t</span> <span class="o">*</span><span class="n">pte</span><span class="p">,</span> <span class="n">pmd_t</span> <span class="o">*</span><span class="n">pmd</span><span class="p">,</span> <span class="kt">unsigned</span> <span class="kt">int</span> <span class="n">flags</span><span class="p">)</span> 
 { … //匿名映射页处理  return do_anonymous_page(mm, vma, address, 
 <span class="n">pte</span><span class="p">,</span> <span class="n">pmd</span><span class="p">,</span> <span class="n">flags</span><span class="p">);</span> 
 }

讯享网//file:mm/memory.c static int do_anonymous_page(struct mm_struct mm, struct vm_area_struct vma, unsigned long address, pte_t page_table, pmd_t pmd, unsigned int flags) { // 分配可移动的匿名页面，底层通过 alloc_page  page = alloc_zeroed_user_highpage_movable(vma, address); … }

//file:arch/x86/mm/fault.c static void kprobes __do_page_fault(struct pt_regs *regs, unsigned long error_code) { … if (likely(vma->vm_start <= address)) goto good_area; //如果栈 vma 的开始地址比 address 大，需要扩大栈  if (unlikely(expand_stack(vma, address))) { bad_area(regs, error_code, address); return; } good_area: … }

讯享网//file:mm/mmap.c int expand_stack(struct vm_area_struct *vma, unsigned long address) { … return expand_downwards(vma, address); } int expand_downwards(struct vm_area_struct *vma, unsigned long address) { … //计算栈扩大后的最后大小  size = vma->vm_end - address; //计算需要扩充几个页面  grow = (vma->vm_start - address) >> PAGE_SHIFT; //判断是否允许扩充  acct_stack_growth(vma, size, grow); //如果允许则开始扩充  vma->vm_start = address; return … }

//file:mm/mmap.c static int acct_stack_growth(struct vm_area_struct *vma, unsigned long size, unsigned long grow) { … //检查地址空间是否超出限制  if (!may_expand_vm(mm, grow)) return -ENOMEM; //检查是否超出栈的大小限制  if (size > ACCESS_ONCE(rlim[RLIMIT_STACK].rlim_cur)) return -ENOMEM; … return 0; }

讯享网# ulimit -a …… max memory size (kbytes, -m) unlimited stack size (kbytes, -s) 8192 virtual memory (kbytes, -v) unlimited

# ulimit -s 10240 # ulimit -a stack size (kbytes, -s) 10240

讯享网‘Segmentation fault (core dumped)

function * gen(){ 
讯享网<span class="nx">data11</span> <span class="o">=</span> <span class="k">yield</span> <span class="nx">readfile</span><span class="p">(</span><span class="s2">&#34;11.txt&#34;</span><span class="p">)</span> <span class="nx">data12</span> <span class="o">=</span> <span class="k">yield</span> <span class="nx">readfile</span><span class="p">(</span><span class="s2">&#34;12.txt&#34;</span><span class="p">,</span> <span class="nx">data11</span><span class="p">)</span> <span class="nx">data</span> <span class="o">=</span> <span class="k">yield</span> <span class="nx">readfile</span><span class="p">(</span><span class="s2">&#34;13.txt&#34;</span><span class="p">,</span> <span class="nx">data12</span><span class="p">)</span> <span class="nx">console</span><span class="p">.</span><span class="nx">log</span><span class="p">(</span><span class="nx">data</span><span class="p">)</span> 
 } let p = gen() p.next() 

“What I cannot create, I do not understand” 
讯享网 ——Richard P. Feynman</code></pre></div><p data-pid="jGakW1Xk">参考资料</p><p data-pid="olLs98iy">[1]https://www.bilibili.com/video/BV1BEzp=2&amp;vd_source=35b20cf24ef5a1961e9723c932</p><hr/><p data-pid="nmiOntSA"><b>本文来自微信公众号：阿管学习录</b></p><p data-pid="9tWRgHMv"><b>持续更新学习的新知识......欢迎关注~</b></p> 
 os系统设计学习的关键：指针与寄存器不仅仅是高级语言中的变量和结构地址或者是表达思想的工具，而是cpu控制硬件的方式：寄存器＝IO，指针＝内存
 
    
      
    
 
      
    

 
    
      
    
 
      
    

初学者，需要言简意赅，《导论》吧。原书作者亲自授课：cs537—网上可以查到视频相关的讲义：https://canvas.wisc.edu/courses//files/folder/Slides 
    
      
    
时钟中断，cpu分时，流水线，缓存，虚拟内存，控制硬件。指令集—OS—汇编-ABI虚拟化，并发，持久性相关的调度策略和资源共享机制。 
    
      
    
对应的课程国外的是：MIT6.004（计算机专业必听课程）或者南京大学袁春风老师的计算机系统基础（南大袁老师课程缺少了数字逻辑的设计的讲解） 
    
      
    
cs537—网上可以查到视频听过课①很多书里不容易理解的地方都得到了解决②书的作者讲解的思路可以得到很多重新的认识：计算机发展的逻辑与历史的结合。问题—思路／方法—新问题：这个循环直到现在计算机 
    
      
    
 
      
    

 
    
      
    
 
      
    

学完这本书，可以直接再去做MIT的os或者哈工大李治军老师的都好进入实操了。 
    
      
    
 
      
    

 
    
      
    
计算进专业学习是难的！ 
    
      
    
 
      
    
学习是什么？就是不断问问题-解问题，而且问的问题不断的变化的过程！https://dzone.com/articles/word-count-hello-word-program-in-mapreducegithub都进化成这个模样了么？这个是一个例子
 
    
      
    
 
      
    
https://github.com/XiaochenCui/mit6.824/blob/battle/src/mapreduce/schedule.goHIT OS: Operating System 
三个重要的东西 
    
      
    
 
     
虚拟化——cpu的虚拟化（多个程序并发运行），内存的虚拟化（进程自己有自己的内存空间）
 
     
并行化——互斥
 
     
持久性——数据储存到系统-通过系统调用
 
    

进程的组成 
    
      
    
 
     
指令和数据
 
     
寄存器
 
     
持久存储设备如文件列表
 
    

进程加载的过程通过将代码和静态数据加载到内存中，通过创建和初始化栈和堆以及执行与I/O设置相关的其他工作，OS现在（终于）为程序执行搭好了舞台。然后它有最后一项任务：启动程序，在入口处运行，即main()。通过跳转到main()例程（第5章讨论的专门机制），OS将CPU的控制权转移到新创建的进程中，从而程序开始执行。
进程状态
进程的数据结构pcb和context（寄存器）
Fork函数新创建的子进程不会从main()函数开始执行，而是直接从fork()系统调用返回，就好像是它自己调用了fork()。但是它从fork()返回的值是不同的。父进程获得的返回值是新创建子进程的PID，而子进程获得的返回值是0。
Exec()函数给定可执行程序的名称（如wc）及需要的参数（如p3.c）后，exec()会从可执行程序中加载代码和静态数据，并用它覆写自己的代码段（以及静态数据），堆、栈及其他内存空间也会被重新初始化。然后操作系统就执行该程序，将参数通过argv传递给该进程。它并没有创建新进程，而是直接将当前运行的程序（以前的p3）替换为不同的运行程序（wc）。子进程执行exec()之后，几乎就像p3.c从未运行过一样。对exec()的成功调用永远不会返回。
如此设计的原因可以实现一些有趣的功能，shell在fork之后exec之前运行代码的机会，这些代码可以在运行新程序前改变环境，从而让一系列有趣的功能很容易实现： 
    
      
    
 
     
实现重定向，当完成子进程的创建后，shell调用exec()之前先关闭了标准输出（standard output），打开了文件newfile.txt。
 
     
在shell中执行程序。shell可以在文件系统中找到这个可执行程序，调用fork()创建新进程，并调用exec()的某个变体来执行这个可执行程序，调用wait()等待该命令完成。子进程执行结束后，shell从wait()返回并再次输出一个提示符，等待用户输入下一条命令。
 
    

虚拟化CPU的基本思想很简单：运行一个进程一段时间，然后运行另一个进程，如此轮换，以这种方式时分共享（time sharing）CPU，就实现了虚拟化。因此就有两个问题：第一个是性能：如何在不增加系统开销的情况下实现虚拟化？第二个是控制权：如何有效地运行进程，同时保留对CPU的控制？控制权对于操作系统尤为重要，因为操作系统负责资源管理。
为了使程序尽可能快地运行，操作系统开发人员想出了一种技术——我们称之为受限的直接执行（limited direct execution）。 
    
      
    
 
      
    

这个概念的“直接执行”部分很简单：只需直接在CPU上运行程序即可。因此，当OS希望启动程序运行时，它会在进程列表中为其创建一个进程条目，为其分配一些内存，将程序代码从磁盘加载到内存中，找到程序入口，跳转到那里，并开始运行用户的代码。，使用正常的调用并返回跳转到程序的main()，并在稍后回到内核。
但是出现了以下问题：第一个问题：如果我们只运行一个程序，操作系统怎么能确保程序不做任何我们不希望它做的事，同时仍然高效地运行它？第二个问题：当我们运行一个进程时，操作系统如何让它停下来并切换到另一个进程，从而实现虚拟化CPU所需的时分共享？
因此就是题目说的，受限制的操作，要加上一些限制。第一个问题的解决方法是：引入一种新的处理器模式，称为用户模式，在用户模式下运行的代码会受到限制。在用户模式下运行时，进程不能发出I/O请求，而操作系统（或内核）运行在内核模式下，代码可以做它喜欢的事，包括特权操作，如发出I/O请求和执行所有类型的受限指令当用户希望执行某种特权操作，可以通过系统调用，执行特殊的陷阱（trap）指令实现。该指令同时跳入内核并将特权级别提升到内核模式。一旦进入内核，系统就可以执行任何需要的特权操作（如果允许），从而为调用进程执行所需的工作。完成后，操作系统调用一个特殊的从陷阱返回指令，该指令返回到发起调用的用户程序中，同时将特权级别降低，回到用户模式。执行陷阱时，硬件必须确保存储足够的调用者寄存器，以便在操作系统发出从陷阱返回指令时能够正确返回。例如，在x86上，处理器会将程序计数器、标志和其他一些寄存器推送到每个进程的内核栈（kernel stack）上。从返回陷阱将从栈弹出这些值，并恢复执行用户模式程序。
陷阱如何知道在OS内运行哪些代码？内核通过在启动时设置陷阱表（trap table）来实现。当机器启动时，它在特权（内核）模式下执行，操作系统利用特权操作告诉硬件在发生某些异常事件时要运行哪些代码。一旦硬件被通知，它就会记住这些处理程序的位置，直到下一次重新启动机器，并且硬件知道在发生系统调用和其他异常事件时要做什么（即跳转到哪段代码）。 
    
      
    
 
      
    

第二个问题是进程的切换操作系统利用时间中断获得CPU的控制权（regain control），并通过调度程序决定是切换进程还是继续执行进程产生时间中断时，当前正在运行的进程停止，操作系统中预先配置的中断处理程序会运行。此时，操作系统重新获得CPU的控制权，因此可以停止当前进程，并启动另一个进程。首先操作系统必须通知硬件哪些代码在发生时钟中断时运行，然后是启动时钟中断，一项特权操作。硬件在发生中断时要为正在运行的程序保存足够的状态（上下文），以便随后从陷阱返回指令能够正确恢复正在运行的程序（与硬件在显式系统调用陷入内核时的行为非常相似），这样一来，操作系统就可以确保最后执行从陷阱返回指令时，不是返回到之前运行的进程，而是继续执行另一个进程。
上下文切换：为当前正在执行的进程保存一些寄存器的值（例如，到它的内核栈），并为即将执行的进程恢复一些寄存器的值（从它的内核栈）。为了保存当前正在运行的进程的上下文，操作系统会执行一些底层汇编代码，来保存通用寄存器、程序计数器，以及当前正在运行的进程的内核栈指针，然后恢复寄存器、程序计数器，并切换内核栈，供即将运行的进程使用。通过切换栈，内核在进入切换代码调用时，是一个进程（被中断的进程）的上下文，在返回时，是另一进程（即将执行的进程）的上下文。当操作系统最终执行从陷阱返回指令时，即将执行的进程变成了当前运行的进程。至此上下文切换完成。 
    
      
    
 
      
    
在上面的例子中，进程A正在运行，然后被中断时钟中断。硬件保存它的寄存器（在内核栈中），并进入内核（切换到内核模式）。在时钟中断处理程序中，操作系统决定从正在运行的进程A切换到进程B。此时，它调用switch()例程，该例程仔细保存当前寄存器的值（保存到A的进程结构），恢复寄存器进程B（从它的进程结构），然后切换上下文（switch context），具体来说是通过改变栈指针来使用B的内核栈（而不是A的）。最后，操作系统从陷阱返回，恢复B的寄存器并开始运行它。
注意在此协议中，有两种类型的寄存器保存/恢复： 
    
      
    
 
     
第一种是发生时钟中断的时候。在这种情况下，运行进程的用户寄存器由硬件隐式保存，使用该进程的内核栈。
 
     
第二种是当操作系统决定从A切换到B。在这种情况下，内核寄存器被软件（即OS）明确地保存，但这次被存储在该进程的进程结构的内存中。后一个操作让系统从好像刚刚由A陷入内核，变成好像刚刚由B陷入内核。
 
    

调度指标周转时间，指的是完成任务的时间响应时间，响应时间= T首次运行−T到达时
调度算法先进先出（FIFO），缺点就是效率低。最短任务优先（SJF），先运行最短的任务，然后是次短的任务，和下一个进行对比。缺点是长任务容易引饥饿最短完成时间优先（STCF），向SJF添加抢占，每当新工作进入系统时，它就会确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作。轮转（Round-Robin，RR）调度，在一个时间片（time slice，有时称为调度量子，scheduling quantum）内运行一个工作，然后切换到运行队列中的下一个任务，可以通过增大时间片来摊销切换上下文的成本（上下文切换时间为1ms，可以把时间片增加到100ms。在这种情况下，不到1%的时间用于上下文切换）结合IO来设计调度举个例子有两项工作A和B，每项工作需要50ms的CPU时间。A运行10ms，然后发出I/O请求（假设I/O每个都需要10ms），而B只是使用CPU 50ms，不执行I/O。调度程序先运行A，然后运行B（见图7.8）。一种常见的方法是将A的每个10ms的子工作视为一项独立的工作。因此，当系统启动时，它的选择是调度10ms的A，还是50ms的B。对于STCF，选择是明确的：选择较短的一个，在这种情况下是A。然后，A的工作已完成，只剩下B，并开始运行。然后提交A的一个新子工作，它抢占B并运行10ms。这样做可以实现重叠（overlap），一个进程在等待另一个进程的I/O完成时使用CPU，系统因此得到更好的利用）。 
    
      
    
 
      
    

总结任何公平的政策（如RR），在周转时间这类指标上表现不佳，因为周转时间只关心作业何时完成，RR几乎是最差的，在很多情况下甚至比简单的FIFO更差。因此问题就是要么注重周转时间，要么注重响应时间。一般操作系统通常对每个作业的长度知之甚少因此，我们如何建立一个没有这种先验知识的SJF/STCF？更进一步，我们如何能够将已经看到的一些想法与RR调度程序结合起来，以便响应时间也变得相当不没？稍后，我们将看到如何通过构建一个调度程序，利用最近的历史预测未来，从而解决这个问题。
注意：上下文切换的成本不仅仅来自保存和恢复少量寄存器的操作系统操作。程序运行时，它们在CPU高要缓存、TLB、分支预测器和其他片上硬件中建立了大量的状态。切换到另一个工作会导致此状态被刷新，且与当前运行的作业相关的新状态被引入。

本章介绍了一种调度方式，名为多级反馈队列（MLFQ）。你应该已经知道它为什么叫这个名字——它有多级队列，并通过观察工作的运行来给出对应的优先级。通过这种方式，MLFQ可以同时满足各种工作的需求：对于短时间运行的交互型工作，获得类似于SJF/STCF的很好的全局性能，同时对长时间运行的CPU密集型负载也可以公平地、不断地稳步向前。
多级反馈队列需要解决的是，如何优化响应时间和周转时间。首先，它要优化周转时间，通过先执行短工作来实现，但是操作系统通常不知道工作要运行多久。其次，优化响应时间，但是像轮转这样的算法虽然降低了响应时间，周转时间却很差。
MLFQMLFQ中有许多独立的队列（queue），每个队列有不同的优先级（priority level）。任何时刻，一个工作只能存在于一个队列中。MLFQ总是优先执行较高优先级的工作（即在较高级队列中的工作），具有同样的优先级的工作采用轮转调度。
至此，我们得到了MLFQ的两条基本规则。规则1：如果A的优先级 &gt; B的优先级，运行A（不运行B）。规则2：如果A的优先级 = B的优先级，轮转运行A和B
只有这两条容易出问题：低优先级的没有机会运行，如下。 
    
      
    
 
      
    

因此加入了新的规则规则3：工作进入系统时，放在最高优先级（最上层队列）。规则4a：工作用完整个时间片后，降低其优先级（移入下一个队列）。规则4b：如果工作在其时间片以内主动释放CPU，则优先级不变。举例子： 
    
      
    
 
      
    
例子1：从上面图可以看出，该工作首先进入最高优先级（Q2）。执行一个10ms的时间片后，调度程序将工作的优先级减1，因此进入Q1。在Q1执行一个时间片后，最终降低优先级进入系统的最低优先级（Q0），然后一直留在那里。 
    
      
    
 
      
    
例子2：上图中，A是一个长时间运行的CPU密集型工作，B是一个运行时间很短的交互型工作。假设A执行一段时间后B到达。A（用黑色表示）在最低优先级队列执行（长时间运行的CPU密集型工作都这样）。B（用灰色表示）在时间T=100时到达，并被加入最高优先级队列。由于它的运行时间很短（只有20ms），经过两个时间片，在被移入最低优先级队列之前，B执行完毕。然后A继续运行（在低优先级）。 
    
      
    
 
      
    
例子3：看一个有I/O的例子。根据上述规则4b，如果进程在时间片用完之前主动放弃CPU，则保持它的优先级不变。交互型工作B（用灰色表示）每执行1ms便需要进行I/O操作，它与长时间运行的工作A（用黑色表示）竞争CPU。MLFQ算法保持B在最高优先级，因为B总是让出CPU。如果B是交互型工作，MLFQ就进一步实现了它的目标，让交互型工作快速运行。这条规则的意图很简单：假设交互型工作中有大量的I/O操作（比如等待用户的键盘或鼠标输入），它会在时间片用完之前放弃CPU。在这种情况下，我们不想处罚它，只是保持它的优先级不变。
可以看出这个算法的一个主要目标：如果不知道工作是短工作还是长工作，那么就在开始的时候假设其是短工作，并赋予最高优先级。如果确实是短工作，则很快会执行完毕，否则将被慢慢移入低优先级队列，而这时该工作也被认为是长工作了。通过这种方式，MLFQ近似于SJF。
但是这样会有问题： 
    
      
    
 
     
如果系统有“太多”交互型工作，就会不断占用CPU，导致长工作永远无法得到CPU（它们饿死了）。
 
     
如果一个进程在时间片用完之前，调用一个I/O操作（比如访问一个无关的文件），从而主动释放CPU。如此便可以保持在高优先级，占用更多的CPU时间。做得好时（比如，每运行99%的时间片时间就主动放弃一次CPU），工作可以几乎独占CPU。
 
     
一个程序可能在不同时间表现不同。一个计算密集的进程可能在某段时间表现为一个交互型的进程。用我们目前的方法，它不会享受系统中其他交互型工作的待遇。
 
    

因此要对上面的规则进行添加和修改规则4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）。规则5：经过一段时间S，就将系统中所有工作重新加入最高优先级队列。
新规则解决了上面的问题： 
    
      
    
 
     
进程不会饿死——在最高优先级队列中，它会以轮转的方式，与其他高优先级工作分享CPU，从而最终获得执行。如果一个CPU密集型工作变成了交互型，当它优先级提升时，调度程序会正确对待它。
 
     
S的值应该如何设置？如果S设置得太高，长工作会饥饿；如果设置得太低，交互型工作又得不到合适的CPU时间比例。
 
     
只要进程用完了自己的配额，进程也无法长时间独占CPU。
 
    

当然这里也有很多问题： 
    
      
    
 
     
规则5中的时间段S应该怎么设置？
 
     
如何配置一个调度程序，例如，配置多少队列？每一层队列的时间片配置多大？为了避免饥饿问题以及进程行为改变，应该多久提升一次进程的优先级？
 
    
这些问题都没有显而易见的答案，因此只有利用对工作负载的经验，以及后续对调度程序的调优，才会导致令人满意的平衡。至于别的系统的实现可以去文献中的论文看看。
本章介绍了比例份额调度的概念，并简单讨论了两种实现：彩票调度和步长调度。首先介绍一个不同类型的调度程序——比例份额（proportional-share）调度程序，有时也称为公平份额（fair-share）调度程序。
具体的做法：彩票数（ticket）代表了进程（或用户或其他）占有某个资源的份额，每隔一段时间，都会举行一次彩票抽奖，以确定接下来应该运行哪个进程。
举个例子，假设进程A拥有0到74共75张彩票，进程B拥有75到99的25张，中奖的彩票就决定了运行A或B。调度程序然后加载中奖进程的状态，并运行它。 
    
      
    
 
      
    
当工作执行时间很短时，平均不公平度非常糟糕。只有当工作执行非常多的时间片时，彩票调度算法才能得到期望的结果。 
    
      
    
 
      
    
彩票调度的其他机制：彩票货币（ticket currency）：这种方式允许拥有一组彩票的用户以他们喜欢的某种货币，将彩票分给自己的不同工作。之后操作系统再自动将这种货币兑换为正确的全局彩票。比如，假设用户A和用户B每人拥有100张彩票。用户A有两个工作A1和A2，他以自己的货币，给每个工作500张彩票（共1000张）。用户B只运行一个工作，给它10张彩票（总共10张）。操作系统将进行兑换，将A1和A2拥有的A的货币500张，兑换成全局货币50张。类似地，兑换给B1的10张彩票兑换成100张。然后会对全局彩票货币（共200张）举行抽奖，决定哪个工作运行。 
    
      
    
 
      
    

如何为工作分配彩票？这是一个非常棘手的问题，很难量化。
彩票转让（ticket transfer）：通过转让，一个进程可以临时将自己的彩票交给另一个进程。这种机制在客户端/服务端交互的场景中尤其有用，在这种场景中，客户端进程向服务端发送消息，请求其按自己的需求执行工作，为了加速服务端的执行，客户端可以将自己的彩票转让给服务端，从而尽可能加速服务端执行自己请求的速度。服务端执行结束后会将这部分彩票归还给客户端。
彩票通胀（ticket inflation）：利用通胀，一个进程可以临时提升或降低自己拥有的彩票数量。如果一个进程知道它需要更多CPU时间，就可以增加自己的彩票，从而将自己的需求告知操作系统，这一切不需要与任何其他进程通信。
虽然随机方式可以使得调度程序的实现简单（且大致正确），但偶尔并不能产生正确的比例，尤其在工作运行时间很短的情况下，由于这个原因，Waldspurger提出了步长调度
步长调度:系统中的每个工作都有自己的步长，这个值与票数值成反比。举个例子，A、B、C这3个工作的票数分别是100、50和250，我们通过用一个大数分别除以他们的票数来获得每个进程的步长。比如用10000除以这些票数值，得到了3个进程的步长分别为100、200和40。我们称这个值为每个进程的步长（stride）。每次进程运行后，我们会让它的计数器增加它的步长，记录它的总体进展。当需要进行调度时，选择目前拥有最小行程值的进程，并且在运行之后将该进程的行程值增加一个步长。
优缺点 
    
      
    
 
     
步长调度可以在概率上实现比例。
 
     
彩票调度不需要全局状态。假如一个新的进程在上面的步长调度执行过程中加入系统，应该怎么设置它的行程值呢？设置成0吗？这样的话，它就独占CPU了。而彩票调度算法不需要对每个进程记录全局状态，只需要用新进程的票数更新全局的总票数就可以了。因此彩票调度算法能够更合理地处理新加入的进程。
 
    

总结彩票调度通过随机值，聪明地做到了按比例分配。步长调度算法能够确定的获得需要的比例。但以下原因，并没有作为CPU调度程序被广泛使用。 
    
      
    
 
     
这两种方式都不能很好地适合I/O
 
     
票数分配问题并没有确定的解决方式，例如，如何知道浏览器进程应该拥有多少票数？通用调度程序（像前面讨论的MLFQ及其他类似的Linux调度程序）做得更好，因此得到了广泛的应用。
 
    

先放着
 
    
      
    
 
     
为了解操作系统如何虚拟化CPU，必须了解一些重要的机制（mechanism）：陷阱和陷阱处理程序，时钟中断以及操作系统和硬件在进程间切换时如何谨慎地保存和恢复状态。
 
     
做课堂项目，它会对你有所帮助。
 
     
操作系统的哲学：它希望确保控制机器。虽然它希望程序能够尽可能高效地运行 [受限直接执行]，但操作系统也希望能够控制好程序和机器。也许这就是我们将操作系统视为资源管理器的原因。
 
    
 计算机基础 的操作系统系列文章基于这本书： 
    
      
    
 
     
《Operating Systems: Three Easy Pieces》
 
     
《操作系统导论》（中文版）
 
    
 
    
      
    
 
      
    

就是不断地重复执行指令的操作，即： 
    
      
    
 
     
fetch：处理器从内存中获取一条指令。
 
     
decode：解码，弄清这是哪条指令。
 
     
execute：执行。
 
    
这就是冯·诺依曼计算模型的基本概念。

Operating System是一类软件，负责让程序运行变得更容易，允许程序共享内存，让程序能够与设备交互等等，总体的目标是确保设备既易于使用又高效地运行，一个OS包含三个核心的概念： 
    
      
    
 
     
虚拟化（virtualization）
 
     
并发（concurrency）
 
     
持久性（persistence）
 
    

从功能上看，一个操作系统的基本组成： 
    
      
    
 
     
进程管理
 
     
内存管理
 
     
文件系统
 
     
网络通信
 
     
安全机制
 
     
用户界面
 
    

从主要设计目标看，一个操作系统至少满足： 
    
      
    
 
     
abstraction：建立抽象，让系统方便和易于使用。
 
     
performance：高性能，最小化操作系统的开销。
 
     
protection：在OS和应用程序之间提供保护。
 
     
reliability：持续不断地稳定运行。
 
    


进程（process）是为正在运行的程序提供的抽象，一个正常的系统能够在少量的物理CPU上运行上百个进程，靠的就是虚拟出很多个CPU的假象，也就是时分共享（time sharing）CPU 技术：通过允许资源由一个进程使用一小段时间，然后由另一个进程使用一小段时间，如此下去，CPU就可以被许多进程共享。
要实现CPU的虚拟化，需要：低级机制（mechanism）：低级方法或协议。例如，上下文切换（context switch），它让操作系统能够停止运行 一个程序，并开始在给定的 CPU 上运行另一个程序。高级策略（policy）：在操作系统内做出某种决定的算法。例如，操作系统中的调度策略（scheduling policy）会利用历史信息、工作负载知识以及性能指标来做出运行哪个程序的决定。

现代操作系统都会提供以下的进程API： 
    
      
    
 
     
创建（create）
 
     
销毁（destroy）
 
     
等待（wait）
 
     
其他控制（miscellaneous control）
 
     
状态（statu）
 
    

一个调用进程API的例子：UNIX 系统提供了许多与进程交互的API：fork()：创建子进程exec()：让子进程与父进程执行不同的任务。wait()：延迟当前进程的执行，直到被调用的进程执行完毕。kill()：向进程发送信号，包括要求进程睡眠、终止或其他有用的指令。
下面的代码展示了使用fork()创建子进程： 
    
      
    
 
     
use nix::unistd::*;  fn main() {  println!(“hello world (pid:{})”, getpid());  match fork() {  Ok(ForkResult::Parent { child }) =&gt; {  // 在父进程中  println!(“hello, I am parent of {} (pid:{})”, child, getpid());  }  Ok(ForkResult::Child) =&gt; {  // 在子进程中  println!(“hello, I am child (pid:{})”, getpid());  }  Err(_) =&gt; {  // fork 创建子进程失败  println!(“Fork creation failed!”);  }  }   //hello world (pid:13399)  //hello, I am parent of 13400 (pid:13399)  //hello, I am child (pid:13400) } 
 
    


 
    
      
    
 
     
将代码和静态数据加载到内存。
 
     
为程序创建和初始化栈（stack）和堆（heap）。
 
     
进行IO相关的设置和工作。
 
    
完成以上三步后，找到程序的入口，启动程序，将CPU的控制权转移到新建的进程中。

运行（running）：在运行状态下，进程正在处理器上运行。这意味着它正在执行指令。就绪（ready）：在就绪状态下，进程已准备好运行，但由于某种原因，操作系统选择不在此时运行。阻塞（blocked）：在阻塞状态下，一个进程执行了某种操作，直到发生其他事件时才会准备运行。一个常见的例子是，当进程向磁盘发起 I/O 请求时，它会被阻塞，因此其他进程可以使用处理器。状态转换的过程： 
    
      
    
 
      
    


使用时分共享（time sharing）CPU技术来虚拟化CPU有两个主要的问题： 
    
      
    
 
     
性能：如何在不增加系统开销的情况下实现虚拟化？
 
     
控制权：如何有效地运行进程，同时保留对CPU的控制权？
 
    
也就是如何高效、可控地虚拟化CPU？这就是操作系统开发人员想出来的技术：受限直接执行（limited direct execution）。直接执行很容易理解：只需直接在 CPU 上运行程序即可。即，当 OS 希望启动程序运行时，它会在进程列表中为其创建一个进程条目，为其分配一些内存，将程序代码（从磁盘）加载到内存中，找到入口点（main()函数或类似的），跳转到那里，并开始运行用户的代码。
受限的部分是什么呢？如果操作系统对运行的程序没有限制，任何程序能够随意地访问硬件，那么操作系统就不能控制任何事情，操作系统本身也就退化为一个库而已。但是必须允许程序执行I/O等受限制的操作，因为硬件本身就是给运行在其上的程序使用的，不可能因噎废食。
LDE 背后的想法很简单：让程序运行的大部分指令直接访问硬件，只在一些关键点（如进程发起系统调用或发生时钟中断）由操作系统介入来确保“在正确时间， 正确的地点，做正确的事”。为了实现高效的虚拟化，操作系统应该尽量让程序自己运行， 同时通过在关键点的及时介入（interposing），来保持对硬件的控制。高效和控制是现代操 作系统的两个主要目标。
那就是说一个进程必须能够执行 I/O 和其他一些受限制的操作，但又不能让进程完全控制系统。操作系统和硬件如何协作实现这一点？
这是通过不同的执行模式来实现的，硬件通过提供不同的执行模式来协助操作系统：内核模式（kernel mode）在此模式下，运行的代码可以做它喜欢的事，包括特权操作，如发出 I/O请求和执行所有类型的受限指令。操作系统就是以这种模式运行。
用户模式（user mode）在此模式下运行的代码会受到限制。例如，在用户模式下运行时，进程不能发出 I/O 请求。这样做会导致处理器引发异常，操作系统可能会终止进程。但是它允许内核小心地向用户程序暴露某些关键功能，例如访问文件系统、创建和销毁进程、与其他进程通信，以及分配更多内存。大多数操作系统会提供几百个系统级的API，以使用户程序能够间接执行特权操作，从而进行系统调用。

如果一个进程在 CPU 上运行，这就意味着操作系统没有运行。如果操作系统没有运行，操作系统如何重新获得 CPU 的控制权（regain control），以便它可以在进程之间切换？
早期操作系统采用的方式，协作方式：等待系统调用 。 
    
      
    
 
     
进程通过系统调用，将CPU的控制权转移给操作系统。
 
     
应用程序执行非法操作，将控制权转移给操作系统。
 
    
如果上述两种情况都没有发生，比如进程拒绝进行系统调用，也没有出错，那么操作系统无法做任何事情，只能采用重启大法。
第二种方式，非协作方式：操作系统进行控制。时钟设备可以编程为每隔几毫秒产生一次中断，即：时钟中断（timer interrupt） 。产生中断时，当前正在运行的进程停止，操作系统中预先配置的中断处理程序（interrupt handler）会运行。此时，操作系统重新获得 CPU 的控制权，因此可以做它想做的事：停止当前进程，并启动另一个进程。
操作系统重新获得控制权的过程中主要做两件事： 
    
      
    
 
     
通知硬件，哪些代码在时钟中断时运行，因此硬件有责任为正在运行的程序保存足够的状态。
 
     
启动时钟，一旦时钟开始运行，操作系统就感到安全了，因为控制权最终会归还给它，因此操作系统可以自由运行用户程序。
 
    

上下文切换（context switch）操作系统一旦获得控制权，就必须做出决定：是继续运行当前正在运行的进程，还是切换到另一个进程。这个决定是由调度程序（scheduler）做出的，具体的调度策略稍后讨论。不论如何，假设操作系统决定进行进程切换，OS就会执行一些底层代码，即上下文切换（context switch）:即，保存当前正在运行的进程的上下文，也就是操作系统会执行一些底层汇编代码，来保存通用寄存器、程序计数器，以及当前正在运行的进程的内核栈指针，然后恢复寄存器、程序计数器，并切换内核栈，供即将运行的进程使用。通过切换栈，内核在进入切换代码调用时，是一个进程（被中断的进程）的上下文，在返回时，是另一进程（即将执行的进程） 的上下文。
上下文切换需要多长时间？可以使用为 lmbench 这个工具衡量操作系统的性能指标。现代操作系统，在具有 2 GHz 或 3 GHz 处理器的系统上的性能可以达到亚微秒级。（1 μs = 10^−6 秒，也就是说在几十到几百微秒（μs））

前面说过，操作系统的调度程序（scheduler）会做出执行当前进程还是切换到下一个进程的决策，那么到底是按照什么样的策略（policy）做出决定，执行调度的呢？在认识不同的调度策略之前，先需要了解两个概念：
工作负载假设工作负载假设和经济学中的理性人假设一样，是非常不切合实际的，但是为了对比不同的调度策略，简化描述问题的框架，我们可以做出如下假设： 
    
      
    
 
     
每一个工作运行相同的时间。 
 
     
所有的工作同时到达。 
 
     
一旦开始，每个工作保持运行直到完成。 
 
     
所有的工作只是用 CPU（即它们不执行 IO 操作）。 
 
     
每个工作的运行时间是已知的。
 
    

调度指标在进程调度中，有不同的指标，同样地把它简化成只用一个指标：周转时间（turnaround time）。任务的周转时间定义为任务完成时间减去任务到达系统的时间，即：T 周转时间 = T 完成时间 − T 到达时间 
非常简单，先到先服务，先到达系统的任务先运行，如果一切按照工作负载假设第一条说的那样，那这种策略非常好，比如下面的例子，三个任务的平均周转时间是（10 + 20 + 30）/ 3 = 20s： 
    
      
    
 
      
    

但是实际上，每个任务的实际运行时间可能差别很大，比如A任务的运行时间可能特别长，比如下面这样： 
    
      
    
 
      
    
那么三个任务的平均周转时间是（100 + 110 + 120）/ 3 = 110s
这个策略就是运行时间越短的任务，越优先运行，比如对上面的例子，可以先运行B和C，再运行A任务： 
    
      
    
 
      
    
这样三个任务的平均周转时间是（10 + 20 + 120）/3 = 50s。
但是实际上，工作负载假设第二条说的也不现实，三个任务可能先后到达，假设 A 在 t = 0 时到达，且需要运行 100s。而 B 和 C 在 t = 10 到达，且各需要运行 10s。则： 
    
      
    
 
      
    
这样三个任务的平均周转时间是（100+（110−10）+（120−10））/3 = 103.33s。
要解决上面的问题，就要放弃工作负载假设第三条（工作必须保持运行直到完成）：每当新工作进入系统时，确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作。
在上面的例子中，STCF 将抢占 A 并运行 B 和 C 以完成。只有在它们完成后，才能调度 A 的剩余时间： 
    
      
    
 
      
    
这样三个任务的平均周转时间是（120 + 10 + 20）/3 = 50s。
新度量指标：响应时间上面的例子都是以T 周转时间作为衡量指标，现在提出一个新的指标：响应时间。响应时间定义为从任务到达系统到首次运行的时间。即：T 响应时间= T 首次运行−T 到达时间
对于上面的例子，三个作业的平均响应时间为（0+0+10）/3 = 3.33s。平均每个作业都要过3.33s才会开始运行，从响应时间的指标上看，结果很差。如何解决呢？引入一种新的调度算法：
基本思想很简单：RR 在一个时间片（time slice，有时称为调度量子，scheduling quantum）内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直 到结束。它反复执行，直到所有任务完成。因此，RR 有时被称为时间切片（time-slicing）。请注意，时间片长度必须是时钟中断周期的倍数。因此，如果时钟中断是每 10ms 中断一次， 则时间片可以是 10ms、20ms 或 10ms 的任何其他倍数。
为了更好的理解轮转（Round-Robin， RR）调度，举一个新的例子：假设 3 个任务 A、B 和 C 在系统中同时到达， 并且它们都希望运行 5s。
按照最短任务优先（SJF）算法： 
    
      
    
 
      
    
SJF 算法平均响应时间是：（0 + 5 + 10）/ 3 = 5s。SJF 算法平均周转时间是（5 + 10+ 15）/3 = 10s。
按照轮转（Round-Robin， RR）调度： 
    
      
    
 
      
    
RR 的平均响应时间是：（0 + 1 + 2）/3 = 1s。RR 的平均周转时间是：（13 + 14 + 15）/3 = 14s。
可以发现响应时间和周转时间两个指标属于鱼和熊掌不可兼得： 
    
      
    
 
     
如果你愿意不公平，你可以运行较短的工作直到完成，但是要以响应时间为代价。
 
     
如果你重视公平性，则响应时间会较短，但会以周转时间为代价。
 
    

结合I/O进行调度现在到了放弃工作负载假设第四条的时候，基本上很少有程序没有任何I/O，调度策略如何调度一个有I/O的程序呢？假设有两项工作 A 和 B，每项工作需要 50ms 的 CPU时间。但是，有一个明显的区别：A 运行 10ms，然后发出 I/O 请求（假设 I/O 每个都需要 10ms），而 B 只是使用 CPU 50ms，不执行 I/O。
需要考虑的就是，当一个进程在I/O上被阻塞时，应该让其他的进程使用CPU，而不是闲置，所以调度程序要是先运行A，再运行B就是一个差的调度策略： 
    
      
    
 
      
    
上图所示，A进程I/O期间，CPU是空闲的。一个好的调度策略应该是当这些交互式作业正在执行 I/O 时，其他 CPU 密集型作业将运行，从而更好地利用处理器。比如使用STCF在I/O 期间抢占CPU： 
    
      
    
 
      
    

现在我们还剩下最后一个不切实际的假设，工作负载假设第五条：操作系统无法看到未来，并不能事先确定地知道每个工作的运行时间。
MLFQ需要解决两个问题： 
    
      
    
 
     
优化周转时间
 
     
优化响应时间
 
    
但是在解决这两个问题之前，首先面对的难题是对进程的运行时间一无所知，MLFQ采用的方式是用历史经验来预测未来，调度程序如何在运行过程中学习进程的特征。
 
    
      
    
 
     
MLFQ 中有许多独立的队列（queue），每个队列有不同的优先级（priority level）。
 
     
任何时刻，一个工作只能存在于一个队列中。
 
     
MLFQ 总是优先执行较高优先级的工作（即在较高级队列中的工作）。 
 
     
当然，每个队列中可能会有多个工作，因此具有同样的优先级，在这种情况下，我们 就对这些工作采用轮转调度。
 
    

下面的图可以表达的很清楚： 
    
      
    
 
      
    

上面的例子展示了MLFQ两条基本规则： 
    
      
    
 
     
规则 1：如果 A 的优先级 &gt; B 的优先级，运行 A（不运行 B）。 
 
     
规则 2：如果 A 的优先级 = B 的优先级，轮转运行 A 和 B。
 
    

从上面的图上看，操作系统将交替地调度A和B，在A和B执行完成之前，C和D都没有机会被执行。但实际上，上面是一张静态的图，进程的优先级是不断变化的。
降低优先级MLFQ 没有为每个工作指定不变的优先级，而是根据观察到的行为调整它的优先级。例如，如果一个工作不断放弃CPU 去等待键盘输入，这是交互型进程的可能行为，MLFQ 因此会让它保持高优先级。相反，如果一个工作长时间地占用 CPU，MLFQ 会降低其优先级。通过这种方式，MLFQ 在进程运行过程中学习其行为，从而利用工作的历史来预测它未来的行为。
 
    
      
    
 
     
规则 3：工作进入系统时，放在最高优先级（最上层队列）。 
 
     
规则 4a：工作用完整个时间片后，降低其优先级（移入下一个队列）。 
 
     
规则 4b：如果工作在其时间片以内主动释放 CPU， 则优先级不变。
 
    

第一个例子：对于一个需要长时间运行的工作，会不断降低它的优先级： 
    
      
    
 
      
    

第二个例子：有两个工作：A（用黑色表示） 是一个长时间运行的 CPU 密集型工作，B（用灰色表示） 是一个运行时间很短的交互型工作。假设 A 执行 一段时间后 B 到达： 
    
      
    
 
      
    
通过这个例子可以体会到这个算法的一个主要目标：如果不知道工作是短工作还是长工作，那么就在开始的时候假设其是短工作，并赋予最高优先级。如果确实是短工作，则很快会执行完毕，否则将被慢慢移入低优先级队列，而这时该工作也被认为是长工作了。
第三个例子：交互型工作 B（用灰色表示）每执行 1ms 便需要进行 I/O操作，它与长时间运行的工作 A（用黑色表示）竞争 CPU： 
    
      
    
 
      
    


上面的三个例子都是优先级降低的例子，如果只进行优先级降低的操作，会有三个问题： 
    
      
    
 
     
饥饿（starvation）问题：如果系统有“太多”交互型工作，就会不断占用CPU，导致长工作永远无法得到 CPU（它们饿死了）
 
     
有些应用程序会欺骗调度程序，让OS给出远超公平的资源；比如进程在时间片用完之前，调用一个 I/O 操作（比如访问一个无关的文件），从而主动释放 CPU。如此便可以保持在高优先级，占用更多的 CPU 时间。
 
     
一个程序可能在不同时间表现不同，一个计算密集的进程可能在某段时间表现为一个交互型的进程。
 
    


解决的方法就是，改变优先级除了降低，还需要有提升的操作：提升优先级为了让 CPU 密集型工作也能取得一些进展（即使不多），我们能做些什么？一个简单的思路是周期性地提升（boost）所有工作的优先级：
 
    
      
    
 
     
规则 5：经过一段时间 S，就将系统中所有工作重新加入最高优先级队列。
 
    

新规则一下解决了两个问题。首先，进程不会饿死——在最高优先级队列中，它会以轮转的方式，与其他高优先级工作分享 CPU，从而最终获得执行。其次，如果一个 CPU 密集型工作变成了交互型，当它优先级提升时，调度程序会正确对待它。
下面是一个长工作与两个交互型短工作竞争 CPU 时的行为。左边没有优先级提升，长工作在两个短工作到达后被饿死。右边每 50ms 就有一次优先级提升（这里只是举例，这个值可能过小），因此至少保证长工作会有一些进展，每过 50ms 就被提升到最高优先级，从而定期获得执行。 
    
      
    
 
      
    


现在还有一个问题没解决：如何阻止调度程序被愚弄？这里的解决方案，是为 MLFQ 的每层队列提供更完善的 CPU 计时方式（accounting）。调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时。只要进程用完了自己的配额，就将它降到低一优先级的队列中去。不论它是一次用完的，还是拆成很多次用完。因此，我们重写规则 4a 和 4b：
规则 4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）。
下面的例子，对比了在规则 4a、4b 的策略下（左图），以及在新的规则 4（右图）的策略下，同样试图愚弄调度程序的进程的表现。没有规则 4 的保护时，进程可以在每个时间片结束前发起一次 I/O 操作，从而垄断 CPU 时间。有了这样的保护后，不论进程的 I/O 行为如何，都会慢慢地降低优先级，因而无法获得超过公平的 CPU 时间比例。 
    
      
    
 
      
    


三个问题都解决了，除此之外，MLFQ 还有可以优化的地方。
MLFQ 调优大多数的 MLFQ 变体都支持不同队列可变的时间片长度。高优先级队列通常只有较短的时间片（比如 10ms 或者更少），因而这一层的交互工作可以更快地切换。相反，低优先级队列中更多的是 CPU 密集型工作，配置更长的时间片会取得更好的效果。
下面的例子，两个长工作在高优先级队列执行 10ms，中间队列执行 20ms，最后在最低优先级队列执行 40ms： 
    
      
    
 
      
    


Solaris 操作系统的 MLFQ 实现（时分调度类 TS）很容易配置。它提供了一组表来决定进程在其生命周期中如何调整优先级，每层的时间片多大，以及多久提升一个工作的优先级。管理员可以通过这些表，让调度程序的行为方式不同。该表默认有 60 层队列，时间片长度从 20ms（最高优先级），到几百 ms（最低优先级），每一秒左右提升一次进程的优先级。其他一些 MLFQ 调度程序没用表，甚至没用前面讲到的规则，有些采用数学公式来调整优先级。
MLFQ小结  
    
      
    
 
     
规则 1：如果 A 的优先级 &gt; B 的优先级，运行 A（不运行 B）。 
 
     
规则 2：如果 A 的优先级 = B 的优先级，轮转运行 A 和 B。 
 
     
规则 3：工作进入系统时，放在最高优先级（最上层队列）。 
 
     
规则 4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）。 
 
     
规则 5：经过一段时间 S，就将系统中所有工作重新加入最高优先级队列。
 
    


比例调度程序的最终目标，是确保每个工作获得一定比例的 CPU 时间，而不是优化周转时间和响应时间。如何设计调度程序来按比例分配 CPU？其关键的机制是什么？效率如何？
比例份额调度程序有一个非常优秀的现代例子，由 Waldspurger 和 Weihl 发现，名为：
彩票调度（lottery scheduling）彩票调度背后是一个非常基本的概念：票数（ticket）代表了进程（或用户或其他）占有某个资源的份额。一个进程拥有的彩票数占总票数的百分比，就是它占有资源的份额。通过不断定时地（比如，每个时间片）抽取彩票，彩票调度从概率上（但不是确定的）获得这种份额比例。
假设有两个互相竞争工作的完成时间，每个工作都有相同数目的 100 张彩票，以及相同的运行时间 R。这种情况下，我们希望两个工作在大约同时完成，但由于彩票调度算法的随机性，有时一个工作会先于另一个完成。为了量化这种区别，我们定义了一个简单的不公平指标 U（unfairness metric），将两个工作完成时刻相除得到 U 的值。如果两个工作几乎同时完成，U 的值将很接近于 1。在这种情况下，我们的目标是： 完美的公平调度程序可以做到 U=1。下图展示了当两个工作的运行时间从 1 到 1000 变化时，30 次试验的平均 U 值。可以看出，当工作执行时间很短时，平均不公平度非常糟糕。只有当工作执行非常多的时间片时，彩票调度算法才能得到期望的结果： 
    
      
    
 
      
    


从上面的内容可以看出，虽然随机方式可以使得调度程序的实现简单（且大致正确），但偶尔并不能产生正确的比例，尤其在工作运行时间很短的情况下。由于这个原因，Waldspurger 提出了一个确定性的公平分配算法：
步长调度（stride scheduling）步长调度也很简单。系统中的每个工作都有自己的步长，这个值与票数值成反比。假设A、B、C 这 3 个工作的票数分别是 100、50 和 250，我们通过用一个大数分别除以他们的票数来获得每个进程的步长。比如用 10000 除以这些票数值，得到了 3 个进程的步长分别为 100、200 和 40。我们称这个值为每个进程的步长（stride）。每次进程运 行后，我们会让它的计数器 [称为行程（pass）值] 增加它的步长，记录它的总体进展。
调度程序使用进程的步长及行程值来确定调度哪个进程。基本思路很简单：当需要进行调度时，选择目前拥有最小行程值的进程，并且在运行之后将该进程的行程值增加一个步长。
下面的表记录了A、B、C 这 3 个工作一段时间内的调度记录： 
    
      
    
 
      
    


到目前为止，我们讨论了许多单处理器调度的原则，那么如何将这些想法扩展到多处理器上呢？为了理解多处理器调度带来的新问题，必须先知道它与单 CPU 之间的基本区别。区别的核心在于对硬件缓存（cache）的使用，以及多处理器之间共享数据的方式，如下图： 
    
      
    
 
      
    
程序第一次读取数据时，数据在内存中，因此需要花费较长的时间（可能数十或数百纳秒）。处理器判断该数据很可能会被再次使用，因此将其放入 CPU 缓存中。如果之后程序再次需要使用同样的数据，CPU 会先查找缓存。因为在缓存中找到了数据，所以取数据快得多（比如几纳秒），程序也就运行更快。
但是如上图右图所示，多个处理器共享一个内存，会有三个问题：
缓存一致性（cache coherence）问题：假设一个运行在 CPU 1 上的程序从内存地址 A 读取数据。由于不在 CPU 1 的缓存中，所以系统直接访问内存，得到值 D。程序然后修改了地址 A 处的值，只是将它的缓存更新为新值 D’。将数据写回内存比较慢，因此系统（通常）会稍后再做。假设这时操作系统中断了该程序的运行，并将其交给 CPU 2， 重新读取地址 A 的数据，由于 CPU 2 的缓存中并没有该数据，所以会直接从内存中读取， 得到了旧值 D，而不是正确的值 D‘。
硬件提供了这个问题的基本解决方案：通过监控内存访问，硬件可以保证获得正确的数据，并保证共享内存的唯一性。在基于总线的系统中，一种方式是使用总线窥探（bus snooping）。每个缓存都通过监听链接所有缓存和内存的总线，来发现内存访问。如 果 CPU 发现对它放在缓存中的数据的更新，会作废（invalidate）本地副本（从缓存中移除），或更新（update）它（修改为新值）。
同步问题：跨 CPU 访问（尤其是写入）共享数据或数据结构时，需要使用互斥原语（比如锁），才能保证正确性。例如，假设多 CPU 并发访问一个共享队列。如果没有锁，即使有底层一致性协议，并发地从队列增加或删除元素，依然不会得到预期结果。需要用锁来保证数据结构状态更新的原子性。
缓存亲和度（cache affinity）问题：所谓的缓存亲和度（cache affinity）是指：：一个进程在某个 CPU 上运行时，会在该 CPU 的缓存中维护许多状态。下次 该进程在相同 CPU 上运行时，由于缓存中的数据而执行得更快。相反，在不同的 CPU 上执行，会由于需要重新加载数据而很慢（好在硬件保证的缓存一致性可以保证正确执行）。因此多处理器调度应该考虑到这种缓存亲和性，并尽可能将进程保持在同一个 CPU 上。

认识了上面三个多处理器系统的调度程序需要面对的问题，就可以讨论第一种调度程序：简单地复用单处理器调度的基本架构，将所有需要调度的工作放入一个单独的队列中，我们称之为单队列多处理器调度（Single Queue Multiprocessor Scheduling，SQMS）。这个方法最大的优点是简单。它不需要太多修改，就可以将原有的策略用于多个 CPU，选择最适合的工作来运行（例如，如果有两个 CPU，它可能选择两个最合适的工作）。
SQMS 有两个明显的短板：第一个是缺乏可扩展性（scalability）：为了保证在多CPU 上正常运行，调度程序的开发者需要在代码中通过加锁（locking）来保证原子性。然而，锁可能带来巨大的性能损失，尤其是随着系统中的 CPU 数增加时。随着这种单个锁的争用增加，系统花费了越来越多的时间在锁的开销上，较少的时间用于系统应该完成的工作。
第二个是缓存亲和性：假设我们有 5 个工作（A、B、C、D、 E）和 4 个处理器。调度队列如下： 
    
      
    
 
      
    
一段时间后，假设每个工作依次执行一个时间片，然后选择另一个工作，下面是每个CPU 可能的调度序列： 
    
      
    
 
      
    
由于每个 CPU 都简单地从全局共享的队列中选取下一个工作执行，因此每个工作都不断在不同 CPU 之间转移，这与缓存亲和的目标背道而驰。为了解决这个问题，大多数 SQMS 调度程序都引入了一些亲和度机制，尽可能让进程在同一个 CPU 上运行。保持一些工作的亲和度的同时，可能需要牺牲其他工作的亲和度来实现负载均衡。例如，针对同样的 5 个工作的调度如下： 
    
      
    
 
      
    
这种调度中，A、B、C、D 这 4 个工作都保持在同一个 CPU 上，只有工作 E 不断地来回迁移（migrating），从而尽可能多地获得缓存亲和度。

正是由于单队列调度程序的这些问题，有些系统使用了多队列的方案，比如每个 CPU 一个队列。称之为多队列多处理器调度（Multi-Queue Multiprocessor Scheduling，MQMS）MQMS 中，基本调度框架包含多个调度队列，每个队列可以使用不同的调度规则， 比如轮转或其他任何可能的算法。当一个工作进入系统后，系统会依照一些启发性规则（如随机或选择较空的队列）将其放入某个调度队列。这样一来，每个 CPU 调度之间相互独立，就避免了单队列的方式中由于数据共享及同步带来的问题。
例如，假设系统中有两个 CPU（CPU 0 和 CPU 1）。这时一些工作进入系统：A、B、C 和 D。由于每个 CPU 都有自己的调度队列，操作系统需要决定每个工作放入哪个队列。可能像下面这样做： 
    
      
    
 
      
    
根据不同队列的调度策略，每个 CPU 从两个工作中选择，决定谁将运行。例如，利用轮转，调度结果可能如下所示： 
    
      
    
 
      
    


MQMS的优势：它天生更具有可扩展性。队列的数量会随着 CPU 的增加而增加，因此锁和缓存争用的开销不是大问题。MQMS 天生具有良好的缓存亲和度。所有工作都保持在固定的 CPU 上，因而可以很好地利用缓存数据。
但是也有个缺点：
负载不均在上面的例子中，假设一段时间后工作C执行完毕，现在调度队列如下： 
    
      
    
 
      
    
如果对系统中每个队列都执行轮转调度策略，会获得如下调度结果： 
    
      
    
 
      
    
从图中可以看出，A 获得了 B 和 D 两倍的 CPU 时间，这不是期望的结果。更糟的是， 假设 A 和 C 都执行完毕，系统中只有 B 和 D。调度队列看起来如下： 
    
      
    
 
      
    
因此 CPU 使用时间线看起来令人难过： 
    
      
    
 
      
    


如何解决负载不均的问题呢？答案是不断地迁移一个或多个工作。一种可能的解决方案是不断切换工作，如下面的时间线所示。可以看到，开始的时候 A 独享 CPU 0，B 和 D 在 CPU 1。一些时间片后，B 迁移到 CPU 0 与 A 竞争，D 则独享 CPU 1 一段时间。这样就实现了负载均衡。 
    
      
    
 
      
    

系统如何决定发起这样的迁移？一个基本的方法是采用一种技术，名为工作窃取（work stealing）。通过这种方法，工作量较少的（源）队列不定期地“偷看”其他（目标）队列是不是比自己的工作多。如果目标队列比源队列（显著地）更满，就从目标队列“窃取”一个或多个工作，实现负载均衡。当然，这种方法也有让人抓狂的地方——如果太频繁地检查其他队列，就会带来较高的开销，可扩展性不好，而这是多队列调度最初的全部目标！相反，如果检查间隔太长，又可能会带来严重的负载不均。找到合适的阈值仍然是黑魔法，这在系统策略设计中很常见。 操作系统导论（OSTEP） pdf 最新版 文字版 百度网盘 下载如果日常工作中和底层打交道的话会遇到很多操作系统相关的问题，比如： 
    
      
    
 
     
为何系统会出现 load 值高 cpu 利用率却不高的情况？
 
     
为何会有那么多僵尸进程？
 
     
某些场景下如何快速创建进程的 snapshot ？
 
     
如何高效利用 CPU Cache Line（利用 Cache Friendly 的数据结构）？
 
     
如何避免 False Sharing ?
 
     
并发情况下如何避免死锁？
 
     
zero-copy 为何高效？
 
     
单纯的 context switch 都是 micro second 级的，为何频繁的线程调度会导致性能低下？
 
     
各种锁（互斥锁、自旋锁、读写锁）的适用场景等。
 
    
如何去理解以及解决以上这些问题就需要我们对操作系统的底层工作机制有一定的了解。这本书来自美国威斯康星大学课程的教材。为什么要介绍这本书呢？主要由于以下几个方面： 
    
      
    
 
     
 阅读体验良好。书中以短句居多，配图丰富，整体下来阅读过程的非常的愉快。 
 
     
 讨论问题由浅入深。就像我们有时候做题一样，先考虑简单的情况，然后再一点一点增加条件逐步解决。基本在本书中的论述都是先制定衡量标准，然后将情况一点一点复杂化来对比各种设计的优劣。 
 
     
 给出了非常多的阅读材料。 
 
    
本书围绕虚拟化、并发和持久性这三个主要概念展开，介绍了所有现代系统的主要组件（包括调度、虚拟内存管理、磁盘和 I/O 子系统、文件系统）。全书共 50 章，分为 3 个部分，分别讲述虚拟化、并发和持久性的相关内容。作者以对话形式引入所介绍的主题概念，行文诙谐幽默却又鞭辟入里，力求帮助读者理解操作系统中虚拟化、并发和持久性的原理。 本书内容全面，并给出了真实可运行的代码（而非伪代码），还提供了相应的练习，很适合高等院校相关专业的教师开展教学和高校学生进行自学。作者：[美] 雷姆兹·H.阿帕希杜塞尔（ Remzi H. Arpaci-Dusseau）， [美]安德莉亚·C.阿帕希杜塞尔（Andrea C. Arpaci-Dusseau）译者：王海鹏操作系统导论（OSTEP）