南京大学《操做系统》笔记(二)

2021年11月20日 阅读数:1
这篇文章主要向大家介绍南京大学《操做系统》笔记(二),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

并发与并行

并行:容许多个执行流同时执行(要求多个处理器);
并发:多个执行流能够不按照一个特定的顺序执行。
图片名称算法

多任务操做系统中的并发

并发性的来源:进程会调用操做系统的API,操做系统在并发执行两个执行流的时候,要保证它们互不干扰,所以,对处理器和内存提出了要求。编程

处理器 内存 典型的并发系统 并发/并行
单处理器 共享内存 OS内核/多线程程序 并发不并行
多处理器 共享内存 OS内核/多线程程序 并发、并行
多处理器 不共享内存 分布式系统(消息通讯) 并发、并行

多处理器编程(多线程编程)

多线程之间,寄存器组的值、堆栈(包括堆栈中的局部变量)是互相独立的;代码是共享的。
在C++中,可使用pthread_create和pthread_join获得共享代码、共享数据、独立堆栈的多个线程。(will新开一个博客写)多线程

Q1:每一个线程的堆栈范围和大小?
A1:每一个线程有8MB的内存映射区域和先后各4KB的保护页。并发

Q2:每一个线程有8M的堆栈,那么为何1000个线程没有耗尽内存?
A2:由于虽然每一个线程有8MB的内存区域,可是它们是虚拟内存,而且在没有被使用的时候不会映射到物理内存上(Lazy allocate),所以物理内存的占用并无那么多。分布式

多处理器编程的困难

  • 编译器优化->顺序的丧失:指令的执行不保证按照代码书写的顺序发生;
  • 中断/并行->原子性的丧失:代码的原子性随时被破坏;
  • 乱序执行->可见性的丧失:执行过的指令可能在多处理器之间不可见。

串行程序的状态机模型

从状态机的理论去理解程序,程序的状态(内存/寄存器的快照)能够当作有限状态机的节点,程序的运行能够当作状态转换的过程。假如系统上有16MB的内存,即16*8Mb,那么能够有2^(16*8M)种状态。
大部分状态有惟一的后续状态,执行一条指令能够获得肯定的结果。不肯定的指令可能有多个后续状态,例如执行rdrand指令(生成真随机数),会对rax指令赋予不一样的值,所以能够带给状态机不肯定性。
对于程序来讲,不肯定性的来源多是:工具

  • (时间)rdtsc/rdtscp:获取处理器的“时间戳”用于精肯定时;
  • (机器状态)rdrand:处理器自身提供的“真”随机数指令;
  • (系统调用)syscall:应用程序的最大不肯定性来源,包括用户的键入、磁盘文件的读取等。

状态机模型的应用

  • 在计算机硬件上的应用:高性能处理器实现,当状态机的执行具备肯定性的时候,A->B->C的状态转换能够优化为A->C。
  • 在计算机系统上的应用:程序分析技术。静态分析是根据程序代码推导出状态机的性质;动态分析是运行时观测到状态机的执行。

应用:Time-Travel Debugging

程序的执行是随着时间“前进”的(\(s_1\)->\(s_2\)->\(s_3\)->...),可否在时间上“后退”(Time-travel)?记录全部的状态\(s_i\),就能实现time-traveling。
若是记录下全部的状态,就能够回到任意一个状态去查看当时的信息。但难点在于,上文讨论过,状态的数量很是庞大,这样的记录很是耗费空间。已知每条指令只会对状态中不多一部分的寄存器/内存进行修改。
由此一个好主意是只记录初始状态和每条指令先后状态的diff。
gdb提供了这样的time-travel debugging功能:性能

  • target record-full 开始记录(须要程序开始执行);
  • record stop 结束记录;
  • reverse-step/reverse-stepi “时间旅行调试”。

并发程序的状态机模型

系统中有n个线程,线程之间是共享内存的,则并发程序的状态s = (M, R1, R2, R3, ..., Rn)
并发系统执行指令的顺序是不肯定的,每一个(M, R1), (M, R2), (M, R3), ...均可以当作是一个串行程序,在任意一个状态,能够选择任意一个线程执行一条指令。
即便每一个线程都是肯定的,在任意一个时刻,处理器能够选择任意线程执行,此处带有不肯定性,所以即便没有上述的程序三大不肯定性来源,多线程程序也拥有天生的不肯定性。
假若有n个线程,每一个线程都执行m个在线程和时间上都独一无二的操做,那么从初始状态到结束状态(程序运行结束)是O(n^(mn)),这是一个很是大的数值。优化

理解并发程序的执行

状态机是理解程序执行的重要工具。
程序是指令序列的静态描述,高度归纳、精简,行为有时难以理解;
状态机是全部动态行为的集合,将静态时的分支、循环所有展开为了顺序结构,行为明确、容易理解。spa

Peterson算法正确性分析