【2020-02-24】leetcode 多线程
多线程---并发
并发主要为多任务情况设计:
竞态条件：由于多进程之间的竞争执行，导致程序未按照期望的顺序输出。
死锁：并发程序等待一些必要资源，导致没有程序可以执行。
资源不足：进程被永久剥夺了运行所需的资源。
python threading模块
1114.按序打印
三个不同的线程将会共用一个 Foo 实例。
线程 A 将会调用 one() 方法
线程 B 将会调用 two() 方法
线程 C 将会调用 three() 方法
请设计修改程序，以确保 two() 方法在 one() 方法之后被执行，three() 方法在 two() 方法之后被执行。
示例
from threading import Lock
class Foo:
def __init__(self):
self.firstJobDone=Lock()
self.secondJobDone=Lock()
self.firstJobDone.acquire()
self.secondJobDone.acquire()
def first(self, printFirst: 'Callable[[], None]') -> None:
# printFirst() outputs "first". Do not change or remove this line.
printFirst()
self.firstJobDone.release()
def second(self, printSecond: 'Callable[[], None]') -> None:
# printSecond() outputs "second". Do not change or remove this line.
with self.firstJobDone:
printSecond()
# Notify the thread that is waiting for the second job to be done
self.secondJobDone.release()
def third(self, printThird: 'Callable[[], None]') -> None:
# printThird() outputs "third". Do not change or remove this line.
with self.secondJobDone:
printThird()
1115、、交替打印FooBar
我们提供一个类：
class FooBar {
public void foo() {
for (int i = 0; i < n; i++) {
print("foo");
}
}
public void bar() {
for (int i = 0; i < n; i++) {
print("bar");
}
}
}
两个不同的线程将会共用一个 FooBar 实例。其中一个线程将会调用 foo() 方法，另一个线程将会调用 bar() 方法。
请设计修改程序，以确保 "foobar" 被输出 n 次。
示例
import threading
class FooBar:
def __init__(self, n):
self.n = n
self.s1=threading.Semaphore(1)
self.s2=threading.Semaphore(0)
def foo(self, printFoo: 'Callable[[], None]') -> None:
for i in range(self.n):
# printFoo() outputs "foo". Do not change or remove this line.
self.s1.acquire()
printFoo()
self.s2.release()
def bar(self, printBar: 'Callable[[], None]') -> None:
for i in range(self.n):
# printBar() outputs "bar". Do not change or remove this line.
self.s2.acquire()
printBar()
self.s1.release()
1116、打印零和奇偶数
假设有这么一个类：
class ZeroEvenOdd {
public ZeroEvenOdd(int n) { ... } // 构造函数
public void zero(printNumber) { ... } // 仅打印出 0
public void even(printNumber) { ... } // 仅打印出 偶数
public void odd(printNumber) { ... } // 仅打印出 奇数
}
相同的一个 ZeroEvenOdd 类实例将会传递给三个不同的线程：
线程 A 将调用 zero()，它只输出 0 。
线程 B 将调用 even()，它只输出偶数。
线程 C 将调用 odd()，它只输出奇数。
每个线程都有一个 printNumber 方法来输出一个整数。请修改给出的代码以输出整数序列 010203040506... ，其中序列的长度必须为 2n。
示例
import threading
class ZeroEvenOdd:
def __init__(self, n):
self.n = n+1
self.Zero=threading.Semaphore(1)
self.Even=threading.Semaphore(0)
self.Odd=threading.Semaphore(0)
# printNumber(x) outputs "x", where x is an integer.
def zero(self, printNumber: 'Callable[[int], None]') -> None:
for i in range(1,self.n):
self.Zero.acquire()
printNumber(0)
if i%2==1:
self.Odd.release()
else:
self.Even.release()
def even(self, printNumber: 'Callable[[int], None]') -> None:
for i in range(1,self.n):
if i%2==0:
self.Even.acquire()
printNumber(i)
self.Zero.release()
def odd(self, printNumber: 'Callable[[int], None]') -> None:
for i in range(1,self.n):
if i%2==1:
self.Odd.acquire()
printNumber(i)
self.Zero.release()
1117、H2O生成
现在有两种线程，氢 oxygen 和氧 hydrogen，你的目标是组织这两种线程来产生水分子。
存在一个屏障（barrier）使得每个线程必须等候直到一个完整水分子能够被产生出来。
氢和氧线程会被分别给予 releaseHydrogen 和 releaseOxygen 方法来允许它们突破屏障。
这些线程应该三三成组突破屏障并能立即组合产生一个水分子。
你必须保证产生一个水分子所需线程的结合必须发生在下一个水分子产生之前。
换句话说:
如果一个氧线程到达屏障时没有氢线程到达，它必须等候直到两个氢线程到达。
如果一个氢线程到达屏障时没有其它线程到达，它必须等候直到一个氧线程和另一个氢线程到达。
书写满足这些限制条件的氢、氧线程同步代码。
class H2O:
def __init__(self):
self.h=collections.deque()
self.o=self.h.copy()
def hydrogen(self, releaseHydrogen: 'Callable[[], None]') -> None:
# releaseHydrogen() outputs "H". Do not change or remove this line.
self.h.append(releaseHydrogen)
self.res()
def oxygen(self, releaseOxygen: 'Callable[[], None]') -> None:
# releaseOxygen() outputs "O". Do not change or remove this line.
self.o.append(releaseOxygen)
self.res()
def res(self):
if len(self.h)>1 and len(self.o)>0:
self.h.popleft()()
self.h.popleft()()
self.o.popleft()()
1195、交替打印字符串
编写一个可以从 1 到 n 输出代表这个数字的字符串的程序，但是：
如果这个数字可以被 3 整除，输出 "fizz"。
如果这个数字可以被 5 整除，输出 "buzz"。
如果这个数字可以同时被 3 和 5 整除，输出 "fizzbuzz"。
例如，当 n = 15，输出： 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz。
假设有这么一个类：
class FizzBuzz {
public FizzBuzz(int n) { ... } // constructor
public void fizz(printFizz) { ... } // only output "fizz"
public void buzz(printBuzz) { ... } // only output "buzz"
public void fizzbuzz(printFizzBuzz) { ... } // only output "fizzbuzz"
public void number(printNumber) { ... } // only output the numbers
}
请你实现一个有四个线程的多线程版 FizzBuzz， 同一个 FizzBuzz 实例会被如下四个线程使用：
线程A将调用 fizz() 来判断是否能被 3 整除，如果可以，则输出 fizz。
线程B将调用 buzz() 来判断是否能被 5 整除，如果可以，则输出 buzz。
线程C将调用 fizzbuzz() 来判断是否同时能被 3 和 5 整除，如果可以，则输出 fizzbuzz。
线程D将调用 number() 来实现输出既不能被 3 整除也不能被 5 整除的数字。
####
# 运行不出来
####
class FizzBuzz:
def __init__(self, n: int):
self.n = n
self.d = {}
def fizz(self, printFizz: 'Callable[[], None]') -> None:
self.d['f'] = printFizz
self.res()
def buzz(self, printBuzz: 'Callable[[], None]') -> None:
self.d['b'] = printBuzz
self.res()
def fizzbuzz(self, printFizzBuzz: 'Callable[[], None]') -> None:
self.d['fb'] = printFizzBuzz
self.res()
def number(self, printNumber: 'Callable[[int], None]') -> None:
self.d['n'] = printNumber
self.res()
def res(self):
if len(self.d) == 4:
for i in range(1, self.n + 1):
if i % 15 == 0:
self.d['fb']()
elif i % 3 == 0:
self.d['f']()
elif i % 5 == 0:
self.d['b']()
else:
self.d['n'](i)
1226、哲学家进餐问题
5 个沉默寡言的哲学家围坐在圆桌前，每人面前一盘意面。叉子放在哲学家之间的桌面上。（5 个哲学家，5 根叉子）
所有的哲学家都只会在思考和进餐两种行为间交替。哲学家只有同时拿到左边和右边的叉子才能吃到面，而同一根叉子在同一时间只能被一个哲学家使用。每个哲学家吃完面后都需要把叉子放回桌面以供其他哲学家吃面。只要条件允许，哲学家可以拿起左边或者右边的叉子，但在没有同时拿到左右叉子时不能进食。
假设面的数量没有限制，哲学家也能随便吃，不需要考虑吃不吃得下。
设计一个进餐规则（并行算法）使得每个哲学家都不会挨饿；也就是说，在没有人知道别人什么时候想吃东西或思考的情况下，每个哲学家都可以在吃饭和思考之间一直交替下去。
import threading
class DiningPhilosophers:
def __init__(self):
self.lock=threading.Lock()
# call the functions directly to execute, for example, eat()
def wantsToEat(self,
philosopher: int,
pickLeftFork: 'Callable[[], None]',
pickRightFork: 'Callable[[], None]',
eat: 'Callable[[], None]',
putLeftFork: 'Callable[[], None]',
putRightFork: 'Callable[[], None]') -> None:
self.lock.acquire()
pickLeftFork()
pickRightFork()
eat()
putLeftFork()
putRightFork()
self.lock.release()
