Алгоритм обедающих философов python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Задача об обедающих философах

License

dbond762/dining_philosophers

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Пять безмолвных философов сидят вокруг круглого стола, перед каждым философом стоит тарелка спагетти. Вилки лежат на столе между каждой парой ближайших философов.

Каждый философ может либо есть, либо размышлять. Приём пищи не ограничен количеством оставшихся спагетти — подразумевается бесконечный запас. Тем не менее, философ может есть только тогда, когда держит две вилки — взятую справа и слева.

Каждый философ может взять ближайшую вилку (если она доступна), или положить — если он уже держит её. Взятие каждой вилки и возвращение её на стол являются раздельными действиями, которые должны выполняться одно за другим.

Суть проблемы заключается в том, чтобы разработать модель поведения (параллельный алгоритм), при котором ни один из философов не будет голодать, то есть будет вечно чередовать приём пищи и размышления.

git clone https://github.com/dbond762/dining_philosophers.git cd dining_philosophers git build ./dining_philosophers

Источник

romech / levit.py

Levit’s algorithm (also «Pape-Levit’s») for finding the shortest paths from one `start` node to all another, Python 3 implementation.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

»’

Levit’s algorithm for finding the shortest path from one `start` node to all another.

Written according to this article: https://goo.gl/GoeKS5

Doesn’t work with negative cycles.

See example at the end.

»’

from collections import defaultdict , OrderedDict

from itertools import chain

from math import inf

class IndexedQueue ( OrderedDict ):

«Queue-like container with fast search»

def push ( self , item ):

self [ item ] = None

def pop ( self ):

return OrderedDict . popitem ( self , last = False )[ 0 ]

«(d,(c,(b,(a,())))) => (a, b, c, d)»

restore_path = lambda tup : ( * restore_path ( tup [ 1 ]), tup [ 0 ]) if tup else ()

def levit ( gr , start , end = None ):

»’

`gr` is an adjancety list < u:[(v, cost), . ] | (u,v) ∈ E >,

`end` is the desired target node, yet all graph nodes are processed anyway.

Returns cost and path if `end` is provided.

Else returns costs and paths as dicts. `restore_path(paths[end])` should be used for each desired end node.

»’

dist = defaultdict ( lambda : inf )

dist [ start ] = 0

path =

m0 = set ()

m1 , m1_urg = IndexedQueue . fromkeys ([ start ]), IndexedQueue ()

m2 = set ( chain . from_iterable (( v for v , _ in from_u ) for from_u in gr . values ())) — < start >#(u,v)∈E => v∈m2

def relax ( u , v , w ):

if ( dist [ v ] > dist [ u ] + w ):

dist [ v ] = dist [ u ] + w

path [ v ] = ( v , path [ u ])

return True

return False

while m1 or m1_urg :

u = m1_urg . pop () if m1_urg else m1 . pop ()

for v , c in gr . get ( u , ()):

if v in m2 :

m1 . push ( v )

m2 . discard ( v )

relax ( u , v , c )

elif v in m1 :

relax ( u , v , c )

elif v in m0 and relax ( u , v , c ):

m1_urg . push ( v )

m0 . discard ( v )

m0 . add ( u )

if end is None :

return dist , path

elif end in path :

return dist [ end ], restore_path ( path [ end ])

else :

return inf , ()

if __name__ == ‘__main__’ :

edges = [( ‘a’ , ‘b’ , 1 ), ( ‘b’ , ‘c’ , 2 ), ( ‘c’ , ‘a’ , 0 ), ( ‘c’ , ‘d’ , 1 ), ( ‘a’ , ‘5’ , 5 )]

adj_list = defaultdict ( list )

for u , v , w in edges :

adj_list [ u ]. append (( v , w ))

print ( adj_list )

cost , path = levit ( adj_list , ‘a’ , ‘d’ )

print ( cost , path ) # => 4 (‘a’, ‘b’, ‘c’, ‘d’)

costs , paths = levit ( adj_list , ‘a’ )

targets = [ ‘b’ , ‘c’ , ‘d’ ]

for t in targets :

print ( costs [ t ], restore_path ( paths [ t ]))

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

philosopher with threads/mutex and processes/semaphore (ecole 42).

luta-wolf/philosophers

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

В этом проекте вы изучите основы многопоточности процесса.Вы увидите, как создавать потоки, и откроете для себя мьютексы.

Описание задачи обедающий философов

• Один или несколько философов сидят за круглым столом. Посреди стола стоит большая миска со спагетти.
• Философы альтернативно едят, думают или спят.
  • во время еды они не думают и не спят;
  • во время мышления они не едят и не спят;
  • и, конечно, во время сна они не едят и не думают.

  Правила для основной части:

  • Каждый философ должен быть потоком.
  • Между каждой парой философов есть одна развилка. Поэтому, если есть несколько философов, то у каждого философа есть вилка с левой стороны и вилка с правой. Если есть только один философ, то на столе должна быть только одна вилка.
  • Чтобы философы не дублировали вилки, вы должны защитить состояние вилки с помощью мьютекса для каждой из них.

  Правила для бонусной части:

  • Все вилки кладутся на середину стола.
  • У них нет состояний в памяти, но количество доступных вилок представлено семафором.
  • Каждый философ должен быть процессом. Но основной процесс не должен бытьфилософ.
  • Глобальные переменные запрещены!
  • Ваша программа должна принимать следующие аргументы:
    • number_of_philosophers (количество философов, а также количествовилок.)
    • time_to_die ((в миллисекундах): Если философ не начал есть time_to_die миллисекунды с начала своего последнего приема пищи или начала симуляции, он умирает.)
    • time_to_eat ((в миллисекундах): время, необходимое философу, чтобы поесть. За это время им нужно будет держать две вилки.)
    • time_to_sleep ((в миллисекундах): время, которое философ проведет во сне.)
    • [number_of_times_each_philosopher_must_eat] ((необязательный аргумент): Если все философы съели хотя бы number_of_times_each_philosopher_must_eat раз, симуляция прекращается. Если не указано иное, моделирование прекращается, когда философ умирает.)

    О журналах вашей программы:

    • Любое изменение состояния философа должно быть отформатировано следующим образом:
      • timestamp_in_ms X has taken a fork
      • timestamp_in_ms X is thinking
      • timestamp_in_ms X is sleeping
      • timestamp_in_ms X is thinking
      • timestamp_in_ms X is died

      (Замените timestamp_in_ms текущей меткой времени в миллисекундах, а X — числом философа.)

      • Отображаемое сообщение о состоянии не должно смешиваться с другим сообщением.
      • Сообщение о смерти философа должно отображаться не более чем через 10 мс после его фактической смерти.
      • Опять же, философы должны избегать смерти!

      Важное замечание: в вашей программе не должно быть гонки данных.

      

      

      для проверки гонки данных

      

      1.Клонируем этот репозиторий рядом с каталогом нашего проекта.

       git clone https://github.com/nesvoboda/socrates 

       cd socrates python3.7 socrates.py ../philosophers () 

      

      

      

      

      • Разбор обедающих философов в лекции от marmand, еще лекция.
      • Цикл лекций по потокам и процессам Unix Threads in C от CodeVault.
      • У Столярова «Программирование: введение в профессию» том 2 глава 7, страница 516 и «Введение в операционные системы» лекция 13, страница 162
      • Статьи по дедлоку, по потокам, по структуре процессов.
      • Про гонку данных

      50 210 100 100 199 2000 600 60

      на школьных Маках с одновременно работающей конференцией в Зуме.

      Проверяем сколько раз философы поели:

      ./philo 5 800 200 200 7 | grep eat | wc -l 

      About

      philosopher with threads/mutex and processes/semaphore (ecole 42).

      Источник

      Задача обедающих философов

      недавно начал знакомиться с многопоточным программированием и попалась задачка про обедающих философов:

      Пять безмолвных философов сидят вокруг круглого стола, перед каждым философом стоит тарелка спагетти. Вилки лежат на столе между каждой парой ближайших философов.

      Каждый философ может либо есть, либо размышлять. Приём пищи не ограничен количеством оставшихся спагетти — подразумевается бесконечный запас. Тем не менее, философ может есть только тогда, когда держит две вилки — взятую справа и слева (альтернативная формулировка проблемы подразумевает миски с рисом и палочки для еды вместо тарелок со спагетти и вилок).

      Каждый философ может взять ближайшую вилку (если она доступна) или положить — если он уже держит её. Взятие каждой вилки и возвращение её на стол являются раздельными действиями, которые должны выполняться одно за другим.

      Вопрос задачи заключается в том, чтобы разработать модель поведения (параллельный алгоритм), при котором ни один из философов не будет голодать, то есть будет вечно чередовать приём пищи и размышления.

      Алгоритм достаточно простой — на основе иерархии ресурсов, взят из википедии. Вкратце:

      Пусть ресурсы (вилки) будут пронумерованы от 1 до 5, и каждая рабочая единица (философ) всегда берёт сначала вилку с наименьшим номером, а потом вилку с наибольшим номером из двух доступных. Далее, философ кладёт сначала вилку с бо́льшим номером, потом — с меньшим. Когда он закончит использовать вилки, он в первую очередь положит на стол вилку с бо́льшим номером, потом — с меньшим, тем самым позволив другому философу взять недостающую вилку и приступить к еде.

      import threading from time import sleep import random forks = 5 philosophers = 5 forks_lock = [threading.Lock() for n in range(forks)] def philosophers_dinner(right_fork, left_fork, philosopher): while True: first_fork = min(right_fork, left_fork) second_fork = max(right_fork, left_fork) forks_lock[first_fork].acquire() forks_lock[second_fork].acquire() print(f'Философ ест') sleep(random.randint(1, 5)) forks_lock[second_fork].release() forks_lock[first_fork].release() for philosopher in range(philosophers): right_fork = philosopher left_fork = (philosopher+1) % philosophers threading.Thread(target=philosophers_dinner, args=(right_fork, left_fork, philosopher)).start() 

      Подскажите, верно ли я решил задачу? Дедлоков вроде нет, филисофы меняются, но не хватает экспертного мнения.

      Источник

      Читайте также:  Search elements in array javascript