Dining philosophers: Difference between revisions
Added version using the multiprocessing library.
Sevengraff (talk | contribs) m (→{{header|Java}}: giving example output) |
StatusAimSky (talk | contribs) (Added version using the multiprocessing library.) |
||
Line 6,631:
=={{header|Python}}==
===With the threading library===
This solution avoids deadlock by never waiting for a fork while having one in hand. If
a philosopher acquires one fork but can't acquire the second, he releases the first fork
Line 6,701 ⟶ 6,704:
DiningPhilosophers()</syntaxhighlight>
===With the multiprocessing library===
This version uses the multiprocessing library to achieve concurrency on multiple CPUs. (Threads run on a single CPU and are run in "turns". The Python threading library simulate concurrency.)
Some other improvements and modifications: configurable number of philosophers, "more deterministic" randomization by pre-allocating the thinking and dining schedules, time scaling to allow faster runs producing results that are essentially the same, collect statistics on wait times, attempt to check for deadlock, adds more algorithms, including a naive to demonstrate deadlock and two symmetry breaking one versions.
Changed forks to chopsticks. Sorry Edsger, nobody (not even philosophers) need two forks to eat with. Furthermore, using 'fork' may cause confusion, since fork has a meaning in the context of concurrent programming.
<syntaxhighlight lang="python">
"""Dining philosophers with multiprocessing module."""
import multiprocessing as mp
import random
import time
# Dining philosophers. See also comments at the threading
# version. Improvements, modifications:
# Support variable number of philosophers.
# "More deterministic" randomization by prealocating the schedules.
# Use scaling to allow faster runs producing results that are
# essentially the same.
# Collect statistics on wait times.
SCALE = 0.2
THINK = (3, 13)
DINE = (1, 10)
class Philosopher(mp.Process):
"""Independently running philosopher processes."""
def __init__(self, idx, name, run_flag, chopstick_left, chopstick_right,
stats, schedule_think, schedule_dine):
mp.Process.__init__(self)
self.idx = idx
self.name = name
self.run_flag = run_flag
self.chopstick_left = chopstick_left
self.chopstick_right = chopstick_right
self.stats = stats
self.schedule_think = schedule_think
self.schedule_dine = schedule_dine
self.counter = 0
self.num_dined = 0
self.hungry_time_total = 0.0
self.hungry_time_max = 0.0
def run(self):
while self.run_flag.value and self.counter < len(self.schedule_think):
# Philosopher is thinking (but really is sleeping).
time.sleep(self.schedule_think[self.counter]*SCALE)
duration = -time.perf_counter()
print(f'{self.name} is hungry', flush=True)
self.get_chopsticks2()
duration += time.perf_counter()
self.hungry_time_total += duration
self.hungry_time_max = max(self.hungry_time_max, duration)
self.dining()
# Populate self.stats:
self.stats.put({'name': self.name,
'num_dined': self.num_dined,
'hungry_time_total': self.hungry_time_total,
'hungry_time_max': self.hungry_time_max})
def get_chopsticks(self):
"""Use swaps and do not hold on to chopsticks."""
chopstick1, chopstick2 = self.chopstick_left, self.chopstick_right
while True:
chopstick1.acquire(True)
locked = chopstick2.acquire(False)
if locked:
return
chopstick1.release()
print(f'{self.name} swaps chopsticks', flush=True)
chopstick1, chopstick2 = chopstick2, chopstick1
def get_chopsticks0(self):
"""Naive greedy implementation to trigger deadlock."""
self.chopstick_left.acquire(True)
time.sleep(0.1)
self.chopstick_right.acquire(True)
def get_chopsticks1(self):
"""Break the symmetry by having one philosopher to be left handed."""
if self.idx == 0:
chopstick1, chopstick2 = self.chopstick_left, self.chopstick_right
else:
chopstick1, chopstick2 = self.chopstick_right, self.chopstick_left
chopstick1.acquire(True)
locked = chopstick2.acquire(False)
if not locked:
chopstick1.release()
chopstick2.acquire(True)
chopstick1.acquire(True)
def get_chopsticks2(self):
"""Break the symmetry by having the even numbered philosophers to be
left handed."""
if self.idx == 0:
chopstick1, chopstick2 = self.chopstick_left, self.chopstick_right
else:
chopstick1, chopstick2 = self.chopstick_right, self.chopstick_left
chopstick1.acquire(True)
locked = chopstick2.acquire(False)
if not locked:
chopstick1.release()
chopstick2.acquire(True)
chopstick1.acquire(True)
def dining(self):
"""Dining with two chopsticks."""
print(f'{self.name} starts eating', flush=True)
self.num_dined += 1
time.sleep(self.schedule_dine[self.counter]*SCALE)
self.counter += 1
print(f'{self.name} finishes eating and leaves to think.', flush=True)
self.chopstick_left.release()
self.chopstick_right.release()
def performance_report(stats):
"""Print some stats about the wait times."""
print("Performance report:")
for queue in stats:
data = queue.get()
print(f"Philosopher {data['name']} dined {data['num_dined']} times. ")
print(f" Total wait : {data['hungry_time_total'] / SCALE}")
print(f" Max wait : {data['hungry_time_max'] / SCALE}")
if data['num_dined'] > 0:
print(f" Average wait: "
f"{data['hungry_time_total'] / data['num_dined']/SCALE}")
def generate_philosophers(names, run_flag, chopsticks, stats, max_dine):
"""Gebnerate a list of philosophers with random schedules."""
num = len(names)
philosophers = [Philosopher(i, names[i], run_flag,
chopsticks[i % num],
chopsticks[(i+1) % num],
stats[i],
[random.uniform(THINK[0], THINK[1])
for j in range(max_dine)],
[random.uniform(DINE[0], DINE[1])
for j in range(max_dine)])
for i in range(num)]
return philosophers
def generate_philosophers0(names, run_flag, chopsticks, stats,
schedule_think, schedule_dine):
"""Allows the use of a predetermined thinking and dining schedule.
This may aid in triggering a deadlock."""
num = len(names)
philosophers = [Philosopher(i, names[i], run_flag,
chopsticks[i % num],
chopsticks[(i+1) % num],
stats[i],
schedule_think[i],
schedule_dine[i])
for i in range(num)]
return philosophers
def dining_philosophers(philosopher_names=(('Aristotle', 'Kant',
'Buddha', 'Marx', 'Russel')),
num_sec=100, max_dine=100):
"""Main routine."""
num = len(philosopher_names)
chopsticks = [mp.Lock() for n in range(num)]
random.seed(507129)
run_flag = mp.Value('b', True)
stats = [mp.Queue() for n in range(num)]
philosophers = generate_philosophers(philosopher_names, run_flag,
chopsticks, stats, max_dine)
# Use the following when trying to trigger a deadlock in conjunction with
# get_chopsticks0():
#philosophers = generate_philosophers(philosopher_names, run_flag,
# chopsticks, [3]*max_dine,
# [5]*max_dine)
for phi in philosophers:
phi.start()
time.sleep(num_sec*SCALE)
run_flag.value = False
print("Now we're finishing.", flush=True)
# We want to allow the philosophers to finish their meal. In fact,
# we even allow them to still start eating if they are presently
# hungry. This means we may need to wait at most num*DINE[1].
wait_time = num*DINE[1]
while wait_time >= 0 and sum(p.is_alive() for p in philosophers) > 0:
time.sleep(1)
wait_time -= 1.0
if wait_time < 0:
for phi in philosophers:
if phi.is_alive():
print(f"Ooops, {phi.name} has not finished!!")
phi.terminate()
return 1
performance_report(stats)
if __name__ == '__main__':
dining_philosophers()
</syntaxhighlight>
=={{header|Racket}}==
| |||