读书笔记

并发&并行 并发程序含有多个逻辑上的独立执行块，他们可以独立的并行执行，也可以串行执行。 并行程序解决问题的速度比串行程序快的多，因为其可以同时执行整个任务的多个部分。并行程序可能有多个独立执行块，也可能只有一个。 引用Rob Pike的经典描述就是： 并发是同一时间应对多件事情的能力； 并行是同一时间动手做多件事情的能力。 常见的并发模型有： 线程与锁 函数式编程 actor模型和通信顺序是进行（Communicating Sequential Processes, CSP） 数据级并行 lambda 架构 分离标识与状态模型 这篇主要介绍线程与锁模型 线程与锁模型 线程与锁模型是对底层硬件运行过程的形式化，非常简单直接，几乎所有的编程语言都对其提供了支持，且不对其使用方法加以限制（易出错）。 这篇文章主要使用python语言来演示线程与锁模型。文章结构来自《七周七并发模型》 互斥和内存模型 创建线程 from threading import Thread def hello_world(): print("Hello from new thread") def main(): my_thread = Thread(target=hello_world) my_thread.start() print("Hello from main thread") my_thread.join() main() 这段代码创建并启动了一个Thread实例，首先从start() 开始，my_thread.start() main()函数的余下部分一起并发执行。最后调用join() 来等待my_thread线程结束。 运行这段代码输出结果有几种： Hello from new thread Hello from main thread 或者 Hello from main thread Hello from new thread 或者 ...

问题：有一个糖果公司需要设计一个糖果售卖机，控制流程如下图，需要怎么实现？ 这是一个状态图，每个圆圈都是一种状态。很明显，有有25分钱、 没有25分钱、 售出糖果、 糖果售罄四个状态，同时也对应四个动作：投入25分钱，退回25分钱，转动曲柄和发放糖果。 那如何从状态图得到真正的代码呢？ 简单代码实现如下： #! -*- coding: utf-8 -*- class GumballMachine: # 找出所有状态，并创建实例变量来持有当前状态，然后定义状态的值 STATE_SOLD_OUT = 0 STATE_NO_QUARTER = 1 STATE_HAS_QUARTER = 2 STATE_SOLD = 3 state = STATE_SOLD_OUT def __init__(self, count=0): self.count = count if count > 0: self.state = self.STATE_NO_QUARTER def __str__(self): return "Gumball machine current state: %s" % self.state def insert_quarter(self): # 投入25分钱 if self.state == self.STATE_HAS_QUARTER: # 如果已经投过 print("You can't insert another quarter") elif self.state == self.STATE_NO_QUARTER: # 如果没有投过 self.state = self.STATE_HAS_QUARTER print("You inserted a quarter") elif self.state == self.STATE_SOLD_OUT: # 如果已经售罄 print("You can't insert a quarter, the machine is sold out") elif self.state == self.STATE_SOLD: # 如果刚刚买了糖果 print("Please wait, we're already giving you a gumball") def eject_quarter(self): # 退回25分 if self.state == self.STATE_HAS_QUARTER: print("Quarter returned") self.state = self.STATE_NO_QUARTER elif self.state == self.STATE_NO_QUARTER: print("You haven't inserted a quarter") elif self.state == self.STATE_SOLD: print("Sorry, you alread turned the crank") elif self.state == self.SOLD_OUT: print("You can't eject, you haven't inserted") def turn_crank(self): # 转动曲柄 if self.state == self.STATE_SOLD: print("Turning twice doesn't get you another gumball") elif self.state == self.STATE_NO_QUARTER: print("You turned but there's no quarter") elif self.state == self.STATE_SOLD_OUT: print("You turned, but there are no gumballs") elif self.state == self.STATE_HAS_QUARTER: print("You turned...") self.state = self.STATE_SOLD self.dispense() def dispense(self): # 发放糖果 if self.state == self.STATE_SOLD: print("A gumball comes rolling out the slot") self.count -= 1 if self.count == 0: self.state = self.STATE_SOLD_OUT else: self.state = self.STATE_NO_QUARTER elif self.state == self.STATE_NO_QUARTER: print("You need to pay first") elif self.state == self.STATE_SOLD_OUT: print("No gumball dispensed") elif self.state == self.STATE_HAS_QUARTER: print("No gumball dispensed") if __name__ == "__main__": # 以下是代码测试 gumball_machine = GumballMachine(5) # 装入5 个糖果 print(gumball_machine) gumball_machine.insert_quarter() # 投入25分钱 gumball_machine.turn_crank() # 转动曲柄 print(gumball_machine) gumball_machine.insert_quarter() #投入25分钱 gumball_machine.eject_quarter() # 退钱 gumball_machine.turn_crank() # 转动曲柄 print(gumball_machine) gumball_machine.insert_quarter() # 投入25分钱 gumball_machine.turn_crank() # 转动曲柄 gumball_machine.insert_quarter() # 投入25分钱 gumball_machine.turn_crank() # 转动曲柄 gumball_machine.eject_quarter() # 退钱 print(gumball_machine) 这段代码有几个问题： ...

首先先介绍一下咖啡和茶的冲泡方法： 茶 1. 把水煮沸 2. 用沸水浸泡茶叶 3. 把茶放到杯子里 咖啡 1. 把水煮沸 2. 用沸水冲泡咖啡 3. 把咖啡倒进杯子 4. 加糖和牛奶 用python代码实现冲泡方法大概是这个样子： # 茶的制作方法 class Tea: def prepare_recipe(self): # 在下边实现具体步骤 self.boil_water() self.brew_tea_bag() self.pour_in_cup() def boil_water(self): print("Boiling water") def brew_tea_bag(self): print("Steeping the tea") def pour_in_cup(self): print("Pouring into cup") # 咖啡的制作方法 class Coffee: def prepare_recipe(self): # 在下边实现具体步骤 self.boil_water() self.brew_coffee_grinds() self.pour_in_cup() self.add_sugar_and_milk() def boil_water(self): print("Boiling water") def brew_coffee_grinds(self): print("Dripping Coffee through filter") def pour_in_cup(self): print("Pouring into cup") def add_sugar_and_milk(self): print("Adding Sugar and Milk") 仔细看上边两端代码会发现，茶和咖啡的实现方式基本类似，都有prepare_recipe，boil_water，pour_in_cup 这三个方法。 ...

上一篇《python设计模式-适配器模式》介绍了如何将一个类的接口转换成另一个符合期望的接口。这一篇将要介绍需要一个为了简化接口而改变接口的新模式-外观模式（Facade-Pattern）。 问题 问题：如果你组装了一套家庭影院，内含播放器、投影机、自动屏幕、立体声音响、爆米花机等。如何设计一个遥控器，可以简单的操作这个系统中的各个组件呢？ 首先来看一下最笨方式观赏电影的步骤： 打开爆米花机 开始爆米花 将灯光调暗 放下屏幕 打开投影仪 将投影机的输入切换到播放器 将投影及设置在宽屏模式 打开功放 将功放的输入设置为播放器 将攻防设置为环绕立体声 将攻防音量调到适中 打开播放器 播放电影 写成类和方法的调用大概是以下的样子： # 打开爆米花机，开始爆米花 poper.on() poper.pop() # 灯光调暗 lights.dim(10) # 放下屏幕 screen.down() # 打开投影仪，设置为宽屏模式 projector.on() projector.setInput(dvd) projector.wideScreenMode() # 打开功放 设置为DVD 调整成环绕立体声模式，音量调到5 amp.on() amp.setDvd(dvd) amp.setSurroundSound() amp.setVolume(5) # 打开dvd 播放器 dvd.on() dvd.play(movie) 可以看到代码中涉及到6个不同的类，而且电影看完后还需要回退，一切都要再反着重来一遍。怎样简化一下操作呢？ 现在，外观模式就可以大展身手了。 使用外观模式，可以通过实现一个提供更合理的接口的外观类，将子系统变得更容易使用。当然，原来的接口还在。 解决方法 先来看一下外观模式如何运作 这里为家庭影院系统创建了一个新的外观类HomeTheaterFacade，这个类暴露出来几个简单的方法，比如watchMovie，endMovie。 这个外观类将家庭影院的多个组件看作一个子系统，通过调用这个子系统来实现watchMovie方法。 外观只提供了一个更直接的操作方式，并没有将原来的子系统隔离，子系统的功能还可以使用 注意： 可以有多个外观 外观提供简化的接口，但不隔离子系统 外观将实现从子系统中解耦，比如：现在有个子系统的组件需要升级换代，只需要把外观代码做相应的修改就可以实现 外观和适配器都可以包装多个类，但是外观的意图时简化接口的调用，而适配器的意图是将接口转换成不同的接口。 示例 class HomeTheaterFacade(object): #先声明需要用的子组件 amp = Amplifier() tuner = Tuner() dvd = DvdPlayer() cd = CdPlayer() projector = Projector() lights = TheaterLights() screen = Screen() popper = PopcornPopper() def watchMovie(self, movie): # watchMovie 将之前需要手动处理的任务批量处理 print("Get ready to watch a movie...") # 打开爆米花机，开始爆米花 self.poper.on() self.poper.pop() # 灯光调暗 self.lights.dim(10) # 放下屏幕 self.screen.down() # 打开投影仪，设置为宽屏模式 self.projector.on() self.projector.setInput(dvd) self.projector.wideScreenMode() # 打开功放 设置为DVD 调整成环绕立体声模式，音量调到5 self.amp.on() self.amp.setDvd(dvd) self.amp.setSurroundSound() self.amp.setVolume(5) # 打开dvd 播放器 self.dvd.on() self.dvd.play(movie) def endMovie(self): # endMovie 负责关闭一切，由子系统中的组件完成 print("Shutting movie theater down...") self.popper.off() self.lights.on() self.screen.up() self.projector.off() self.amp.off() self.dvd.stop() self.dvd.eject() self.dvd.off() 代码使用 def main(): home_theater = HomeTheaterFacade() # 实例化外观 home_theater.watchMovice() # 使用简化方法开启 关闭电影ß home_theater.endMovice() 定义 定义：外观模式提供了一个统一的接口，用来访问子系统中的一群接口。外观定义了一个高层接口，让子系统更容易使用。 ...

问题：假设有一个软件系统，你希望它能在不改变现有代码的前提下和一个新的厂商类库搭配使用，但是这个新厂商所设计出来的接口不同于旧厂商的接口 这个问题和下图的问题类似 美国标准的插头🔌无法在欧洲标准的插座上使用，通常的做法是什么呢？ 添加一个插头适配器，适配器的作用是将欧式插头转换成美式插座，以便于让美式插头可以使用。 解决方案 所以，面对一个有全新接口的类库而又不能改变现有代码时，最先想到的做法是，在这两个系统之间添加一个适配器。 简单的例子 有一个系统，需要一个鸭子🦆对象，但是现在只有一个火鸡🦃对象。鸭子和火鸡对象的功能简单描述如下： # 鸭子的简单描述 class Duck: def quack(self): # 会呱呱叫 print("Quack") def fly(self): # 飞的能力 print("I'm flying") # 火鸡的简单描述 class Turkey: def gobble(self): # 不会呱呱叫，只会咯咯叫 print("Gobble gobble") def fly(self): # 飞的能力 但是飞不远 print("I'm flying a short distance") 因为现在没有鸭子对象，只能那火鸡对象冒充。由于鸭子对象和火鸡对象功能不同，不能直接拿来用，现在就需要使用适配器来完成这个功能： class TurkeyAdapter(Duck): turkey = Turkey() # 这里实际使用的是火鸡对象 # 实现鸭子对象拥有的quack方法 def quack(self): self.turkey.gobble() def fly(self): # 假设火鸡比鸭子飞的短，为了模拟鸭子的动作，多飞几次 for i in range(5): turkey.fly() 接下来调用就可以像使用鸭子对象一样使用火鸡适配后的对象。 ...

本文是《垃圾回收的算法与实现》读书笔记 上一篇为《GC 标记-清除算法》 引用计数算法 给对象中添加一个引用计数器，每当有一个地方引用它时，计数器的值就加1；当引用失效时，计数器值就减1；任何时刻计数器为0的对象就是不可能再被使用的。这也就是需要回收的对象。 引用计数算法是对象记录自己被多少程序引用，引用计数为零的对象将被清除。 计数器表示的是有多少程序引用了这个对象（被引用数）。计数器是无符号整数。 计数器的增减 引用计数法没有明确启动 GC 的语句，它与程序的执行密切相关，在程序的处理过程中通过增减计数器的值来进行内存管理。 new_obj() 函数 与GC标记-清除算法相同，程序在生成新对象的时候会调用 new_obj()函数。 func new_obj(size){ obj = pickup_chunk(size, $free_list) if(obj == NULL) allocation_fail() else obj.ref_cnt = 1 // 新对象第一只被分配是引用数为1 return obj } 这里 pickup_chunk()函数的用法与GC标记-清除算法中的用法大致相同。不同的是这里返回 NULL 时，分配就失败了。这里 ref_cnt 域代表的是 obj 的计数器。 在引用计数算法中，除了连接到空闲链表的对象，其他对象都是活跃对象。所以如果 pickup_chunk()返回 NULL，堆中也就没有其它大小合适的块了。 update_ptr() 函数 update_ptr() 函数用于更新指针 ptr，使其指向对象 obj，同时进行计数器值的增减。 func update_ptr(ptr, obj){ inc_ref_cnt(obj) // obj 引用计数+1 dec_ref_cnt(*ptr) // ptr之前指向的对象(*ptr)的引用计数-1 *ptr = obj } 这里 update_ptr 为什么需要先调用 inc_ref_cnt，再调用dec_ref_cnt呢？ 是因为有可能 *ptr和 obj 可能是同一个对象，如果先调用dec_ref_cnt可能会误伤。 **inc_ref_cnt()**函数 这里inc_ref_cnt函数只对对象 obj 引用计数+1 func inc_ref_cnt(obj){ obj.ref_cnt++ } dec_ref_cnt() 函数 ...

本文是《垃圾回收的算法与实现》读书笔记 什么是GC标记-清除算法（Mark Sweep GC） GC 标记-清除算法由标记阶段和清除阶段构成。在标记阶段会把所有的活动对象都做上标记，然后在清除阶段会把没有标记的对象，也就是非活动对象回收。 名词解释： 在 GC 的世界里对象指的是通过应用程序利用的数据的集合。是 GC 的基本单位。一般由头（header）和域（field）构成。 活动对象:能通过引用程序引用的对象就被称为活动对象。（可以直接或间接从全局变量空间中引出的对象） 非活动对象:不能通过程序引用的对象呗称为非活动对象。（这就是被清除的目标） 标记-清除算法的伪代码如下所示： func mark_sweep(){ mark_phase() // 标记阶段 sweep_phase() // 清除阶段 } 标记阶段 标记阶段就是遍历对象并标记的处理过程。 标记阶段伪代码如下： func mark_phase(){ for (r : $roots) // 在标记阶段，会给所有的活动对象打上标记 mark(*r) } func mark(){ if (obj.mark == False) obj.mark = True // 先标记找出的活动对象 for (child: children(obj)) // 然后递归的标记通过指针数组能访问到的对象 mark(*child) } 这里 $root 是指针对象的起点，通过$root 可以遍历全部活动对象。 下图是标记前和标记后内存中堆的状态 清除阶段 在清除阶段，collector 会遍历整个堆，回收没有打上标记的对象（垃圾），使其能再次利用。 sweep_phase() 函数伪代码实现如下： func sweep_phase(){ sweeping = $heap_start // 首先将堆的首地址赋值给 sweeping while(sweeping < $head_end){ if(sweeping.mark == TRUE) // 如果是标记状态就设为 FALSE，如果是活动对象，还会在标记阶段被标记为 TRUE sweeping.mark == FALSE else: sweeping.next = $free_list // 将非活动对象 拼接到 $free_list 头部位置 $free_list = sweeping sweeping += sweeping.size } } size 域指的是存储对象大小的域，在对象头中事先定义。 ...

上一篇我们了解了golang 的变量、函数和基本类型，这一篇将介绍一下控制流 现在我们看一个复杂点的例子: fibonacci(递归版) package main import "fmt" func main() { result := 0 for i := 0; i <= 10; i++ { result = fibonacci(i) fmt.Printf("fibonacci(%d) is: %d\n", i, result) } } func fibonacci(n int) (res int) { if n <= 1 { res = 1 } else { res = fibonacci(n-1) + fibonacci(n-2) } return } // outputs fibonacci(0) is: 1 fibonacci(1) is: 1 fibonacci(2) is: 2 fibonacci(3) is: 3 fibonacci(4) is: 5 fibonacci(5) is: 8 fibonacci(6) is: 13 fibonacci(7) is: 21 fibonacci(8) is: 34 fibonacci(9) is: 55 fibonacci(10) is: 89 for i := 0; i <= 10; i++ {} 第7行是一个循环结构 这里for 循环是一个控制流 控制流 For Go 只有一种循环接口– for 循环 ...

UNIX 进程 系统调用 Unix 系统是由用户空间（userland）和内核组成。Unix 内核位于计算机硬件之上，是与硬件交互的中介。这些交互包括通过问卷系统进程读/写、在网络上发送数据、分配内存，以及通过扬声器播放音频。这些都是用户应用程序所不能涉及的，只能通过系统调用来完成。 系统调用为内核和用户空间搭建了桥梁。规定了程序和计算机硬件直接所允许发生的一切交互。 进程是 Unix 系统的基石，所有的代码都是在进程中运行。 unix 中的进程创建是通过内核系统调用 fork() 实现的。当一个进程产生一个 fork 请求时，操作系统执行以下功能： 为新进程在进程表中分配一个空项 为子进程赋一个唯一的进程标识符 为一个父进程上下文的逻辑副本，不包括共享内存区 增加父进程拥有的所有文件的计数器，以表示有一个另外的进程现在也用户这些文件。 把子进程置为就绪态 向父进程返回子进程的进程号；对子进程返回0。 所有这些操作都在父进程的内核态下完成。 进程皆有标识 在系统中运行的所有进程都有一个唯一的进程标识符，称为 pid。 pid 并不传达关于进程本身的任何信息，仅仅是一个数字标识 在 python 中查看当前进程 pid 可以使用 getpid() 方法。 >>> import os >>> print os.getpid() 26164 在实际应用中，pid 可以加入都日志信息中，这样当多个进程向同一个文件写入日志的时候，就可以知道哪一行是由哪个进程写入的。 进程皆有父 系统中运行的每一个进程都有对应的父进程。每个进程都知道它父进程的标识符（ppid）。 在 python 中查看当前进程 pid 可以使用 getppid() 方法。 >>> import os >>> print os.getpid() 26164 >>> print os.getppid() 26125 进程皆有文件描述符 在 Unix 中，一切都是文件。 ...

这是操作系统进程系列文章第三篇-操作系统线程描述 文章是《操作系统-精髓与设计原理》学习笔记 线程（thread） 什么是线程 线程是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。 关于进程的两个概念： 资源所有权：一个进程包括一个存放进程映像的虚拟地址空间（进程映像是程序、数据、栈和进程控制块中定义的属性的集合）。一个进程总是拥有对资源的控制或所有权，这些资源包括内存、I/O 通道，I/O 设备和文件。 调度/执行：一个进程沿着通过一个或多个程序的一条执行路径执行，其执行过程可能与其他进程的执行过程交替执行。一个进程具有一个执行状态和一个分片的优先级，并且是一个可被操作系统调度和分配的实体。 这两个概念是独立的，操作系统可以独立的处理。 现代操作系统通常把分派单位称为线程（或轻量级进程），拥有资源所有权的单位称为进程。 多线程 多线程是指操作系统在单个进程内支持多个并发执行路径的能力。每个进程中只有一个线程在执行的方法称为单线程方法。进程支持多个线程的情况被称作多线程。 在多线程环境中，进程被定义成资源分配的单位和一个被保护的单位，与进程相关联的有： 存放进程映像的虚拟地址空间 受保护的对处理器、其他进程、文件和 I/O 资源的访问 在一个进程中，可能有一个或多个线程，每个线程有： 线程的执行状态（运行，就绪） 在未运行时保存的线程上下文 一个执行栈 用于每个线程局部变量的静态存储空间 与进程内的其他线程共享的对进程的内存和资源的访问 进程 VS 线程 下图说明了进程和线程的区别： 在单线程模型中，进程的标出包括他的进程控制块和用户地址空间，以及在进程执行中管理调用/返回 行为的用户栈和内核栈。当进程被控制时，处理器寄存器被该进程锁控制；当进程不运行时，这些处理器寄存器的内容被保存。 在多线程环境中，进程仍然只有一个与之关联的进程控制块和用户地址空间。但是每个线程都有一个独立的栈，还有独立的控制块用于包含寄存器值、优先级和其他与线程相关的状态信息。 进程中的所有线程共享该进程的状态和资源，它们驻留在同一块地址空间中，并且可以访问到相同的数据。当一个线程改变了内存中的一个数据项时，其他线程在访问这一数据项时能够看到变化后的结果。 线程的优点 在一个已有的进程中创建一个新的线程比创建一个全新的进程所需时间要少的多。 终止一个线程比终止一个进程花费的时间少 同一个进程内线程间切换比进程间切换花费的时间要少。 线程提高了不同的执行程序间通信的效率。（大多数操作系统中，独立进程间的通信需要内核的介入，由于同一进程中的线程共享内存和文件，它们间的通信无需调用内核） 线程状态 和进程一样，线程的关键状态有运行态、就绪态和阻塞态。挂起是进程级别的概念，一个进程被换出，它的所有线程都被换出。 有4个与线程状态改变相关的操作： 派生：当派生一个新进程时，同时也为改进程派生出一个线程。进程中的线程也可以在同一个进程中派生另一个线程，新的线程拥有自己的寄存器上下文和栈空间，且被放置在就绪队列中。 阻塞：当线程需要等待一个事件时，将被阻塞，此时处理器转而执行另一个就绪线程（可能是同一进程，也可能是不同进程） 解除阻塞：当阻塞一个线程的事件发生时，该线程被转移到就绪队列中 结束：当一个线程完成时，其寄存器上下文和栈都被释放。 用户级线程和内核级线程 线程的实现可以分为两大类：用户级线程（User-Level Thread ULT）和内核级线程（Kernel-Level Thread KLT）。 在用户级线程和内核级线程使用时，通常有以下三种模式： 在一个纯粹的用户级线程程序中，有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在。 使用用户级线程的优点： 线程切换不需要内核态特权，因此，进程不需要为了线程管理而切换到内核态，这节省了两次状态转换（从用户态到内核态，再从内核态返回用户态）的开销。 调度可以是用户程序相关的。（可以为特定的应用使用特定的调度算法） 用户级线程可以在任何操作系统中运行，不需要对底层内核进行修改以支持用户级线程。 使用用户级线程的缺点： 许多系统调用会被阻塞。因此当用户级线程执行一个系统调用时，不仅这个线程会被阻塞，进程中所有线程都会被阻塞。 不能使用多个处理器。内核一次只把一个进程分配给一个处理器，因此一个进程中只有一个线程可以执行。 解决这两个问题有两种方式： 使用多进程代替多线程，但这样消除了多线程的优势 使用 jacketing 技术。把一个产生阻塞的系统调用转换成一个非阻塞的系统调用。 在一个纯粹的内合辑线程程序中，有关线程管理的所有工作都由内核完成。内核为进程及其内部的每个线程维护上下文信息。调度由内核基于线程完成。 使用内核级线程客服了用户级线程的两个基本缺陷。首先内核可以把同一个进程的多个线程调度到多个处理器；其次一个进程中的线程被阻塞，内核可以调度同一个进程的另一个线程。 ...