Проблеми със синхронизацията в ОС. Проблемът със спящия бръснар
Литературата за операционните системи съдържа много интересни проблеми, които са били широко обсъждани и анализирани с помощта на различни техники за синхронизация. В този раздел ще разгледаме три от най-известните проблеми.
Проблемът с обядващите философи
През 1965 г. Дейкстра формулира и решава проблема със синхронизацията, който той нарича проблем на обядващи философи. Оттогава всеки, който е изобретил още един нов синхронизиращ примитив, смята за свой дълг да демонстрира достойнствата на новия примитив, като използва като пример проблема на обядващите философи. Проблемът може да се формулира по следния начин: петима философи седят на кръгла маса и всеки има чиния със спагети. Спагетите са толкова хлъзгави, че всеки философ се нуждае от две вилици, за да се справи с тях. Между всеки две чинии има по една вилица.
Животът на един философ се състои от редуващи се периоди на хранене и мислене. (Разбира се, това е абстракция, дори когато се прилага за философите, но другите жизнени процеси са маловажни за нашата задача.) Когато философът е гладен, той се опитва да вземе две вилици, лява и дясна, в произволен ред. Ако успее да вземе две вилици, той яде известно време, след което връща вилиците обратно и продължава да мисли. Въпросът е: възможно ли е да се напише алгоритъм, който моделира тези действия за всеки философ и никога да не се забива? (Някои хора смятат, че необходимостта от две вилици е малко изкуствена. Може би трябва да заменим италианската храна с китайска храна, спагетите с ориз и вилиците с подходящи пръчици.)
Можете да промените програмата, така че след получаване на лявата вилка да се проверява наличността на дясната. Ако дясната вилица не е налична, философът връща лявата назад, изчаква известно време и повтаря целия процес. Този подход също няма да работи, макар и по друга причина. Ако нямате късмет, всичките петима философи могат да започнат процеса едновременно, да вдигнат лявата вилица, да открият, че дясната липсва, да върнат лявата обратно на масата, да вдигнат лявата вилица едновременно и така нататък до безкрайност. Ситуация, при която всички програми продължават да работят за неопределено време, но не могат да постигнат поне някакъв напредък, се нарича замразяване на процеса (на английски, гладуване, буквално „гладуване“. Това
Терминът важи дори ако проблемът не е в италианския или китайския ресторант, а в компютрите).
Може да си помислите: „Ако философите медитират за някакъв произволен период от време, след като не успеят да хванат правилната вилица, вероятността всички процеси да продължат да са в застой поне за час е малка.“ Това е правилно и за повечето приложения повторният опит след известно време не е проблем. Например, в Ethernet локална мрежа, в ситуация, в която два компютъра изпращат пакети едновременно, всеки трябва да изчака произволно определено време и да опита отново - това решение работи добре на практика. В някои приложения обаче е за предпочитане друго решение, което винаги работи и не зависи от произволни числа (например в приложение за безопасност на атомна електроцентрала).
Направете подобрение, за да избегнете блокиране и спиране на процеса: защитете петте израза след заявката за мислене с двоичен семафор. Тогава философът ще трябва да извърши операция надолу върху променливата mutex, преди да посегне към вилиците. И след като върне вилиците на мястото им, той трябва да извърши операцията Up върху променливата mutex. От теоретична гледна точка решението е доста подходящо. От практическа гледна точка има проблеми с ефективността: само един философ може да яде спагети наведнъж. Но има пет вилици, така че двама философи трябва да имат право да ядат по всяко време.
Решението елиминира задънената улица и позволява възможно най-високия паралелизъм за произволен брой философи. Това използва масива от състояния, за да проследи състоянието на ума на всеки философ: той или яде, мисли или гладува (опитва се да вземе вилици). Философът може да започне да яде само ако никой от съседите му не яде. Съседите на философа с номер i се определят от макросите LEFT и RIGHT (т.е. ако i = 2, тогава LEFT=
Проблемът на читателите и писателите
Проблемът на обядващите философи е полезен за моделиране на процеси, които се конкурират за изключителен достъп до ограничен брой ресурси, като входно/изходни устройства. Друг добре известен проблем е проблемът с читателите и писателите, който моделира достъпа до базата данни. Представете си база данни за самолетни резервации, до която много процеси се опитват да получат достъп. Можете да разрешите едновременно четене на данни от базата данни, но ако процес записва информация в базата данни, достъпът до други процеси трябва да бъде отказан, дори достъпът за четене. Как да програмираме читатели и писатели?
За да избегнете тази ситуация, трябва малко да промените програмата: ако процесът на запис чака достъп до базата данни, новият процес на четене не получава достъп, а се нарежда на опашка зад процеса на запис. Сега процесът на запис трябва да изчака, докато процесите на четене, които вече са в него, напуснат базата данни, но няма нужда да прескачате напред процесите на четене, които са дошли в базата данни след него. Недостатъкът на това решение е загубата на производителност, причинена от по-слабата конкуренция. Представено е решение, при което на процесите на писане се дава по-висок приоритет.
Проблемът със спящия бръснар
Друг класически проблем с междупроцесната комуникация се случва във фризьорски салон. Във фризьорския салон има един бръснар, неговият стол и n стола за посетители. Ако няма желаещи да ползват услугите му, бръснарят сяда на стола си и спи. Ако клиент дойде при фризьора, той трябва да го събуди. Ако клиентът пристигне и види, че бръснарят е зает, той или сяда на стола (ако има място), или си тръгва (ако няма). Бръснарят и посетителите трябва да бъдат програмирани да избягват състезание. Тази задача има много аналози в областта на опашката, например информационна услуга, която обработва ограничен брой заявки едновременно, с компютъризирана система за изчакване на заявки.
Предлаганото решение използва три семафора: клиенти, за преброяване на чакащи посетители (клиентът, който седи на бръснарския стол, не се взема предвид - той вече не чака); бръснари, броят бръснари (0 или 1), които стоят без работа и чакат клиент, и мютекс за прилагане на взаимно изключване. Чакащата променлива се използва и за преброяване на чакащи посетители.
Това е копие на променливата на клиентите. Наличието на тази променлива в програмата се дължи на факта, че е невъзможно да се прочете текущата стойност на семафора. При това решение клиент, посещаващ фризьорски салон, трябва да преброи броя на чакащите клиенти. Ако посетителите са по-малко от столовете, новият посетител остава, в противен случай си тръгва.
Когато бръснарят идва на работа сутрин, той изпълнява бръснарската процедура, блокирайки семафора на клиента, тъй като стойността на семафора е 0. След това бръснарят заспива и спи до пристигането на първия клиент.
Когато посещава фризьорски салон, клиентът изпълнява клиентска процедура, като иска достъп до мютекс, за да влезе в критичната зона. Ако след него се появи друг посетител, той няма да може да направи нищо, докато първият посетител не освободи достъп до мютекса. След това посетителят проверява за свободни столове, ако не успее, освобождава достъпа до мютекса и си тръгва.
Ако има свободен стол, посетителят увеличава стойността на целочислената променлива чакане. След това изпълнява процедурата up на клиентския семафор, така че
Най-активиране на потока на бръснаря. В този момент и посетителят, и бръснарят са активни. Когато клиентът освободи достъп до мютекса, бръснарят го грабва, прави малко домакинска работа и започва да подстригва косата на клиента.
В края на прическата посетителят излиза от процедурата и напуска фризьора. За разлика от предишните програми, няма посетителски цикъл, тъй като всеки посетител се подстригва само веднъж. Бръснарският цикъл съществува и бръснарят се опитва да намери следващия клиент. Ако успее, подстригва следващия посетител, в противен случай бръснарят заспива.
Заслужава да се отбележи, че въпреки липсата на трансфер на данни в проблема Readers-Writers и проблема Sleeping Barber, и двата проблема са проблеми с междупроцесната комуникация, защото изискват синхронизиране на множество процеси.
проблем
Аналогията се основава на хипотетична бръснарница с един бръснар. Фризьорският салон разполага с едно работно място и рецепция с много столове. Когато бръснарят приключи с подстригването на клиента, той го освобождава и след това отива до рецепцията, за да види дали има чакащи клиенти. Ако има, кани един от тях и го подстригва. Ако няма чакащи клиенти, той се връща на стола си и спи в него.
Всеки клиент, който идва, гледа какво прави фризьорът. Ако фризьорът спи, клиентът го събужда и сяда на стол. Ако фризьорът работи, тогава клиентът отива на рецепцията. При наличие на свободен стол в рецепцията клиентът сяда и изчаква реда си. Ако няма свободен стол, клиентът си тръгва. Въз основа на наивен анализ, горното описание трябва да гарантира, че бръснарницата функционира правилно, като бръснарят подстригва косата на всеки, докато има клиенти, и след това спи, докато пристигне следващият клиент. На практика има много проблеми, които могат да възникнат, които илюстрират общи проблеми при планирането.
Всички проблеми идват от факта, че всички действия както на фризьора, така и на клиента (проверка на рецепцията, влизане във фризьора, заемане на място на рецепцията и т.н.) отнемат неизвестно колко време. Например, клиент може да влезе и да забележи, че фризьорът работи, след което отива на рецепцията. Докато върви, бръснарят завършва прическата, която прави, и отива да провери рецепцията. Тъй като там няма никой (клиентът още не е дошъл), той се връща на мястото си и спи. Сега фризьорът чака клиента, а клиентът чака фризьора. В друг пример двама клиенти могат да пристигнат едновременно, когато има само едно празно място в рецепцията. Забелязват, че фризьорът работи, отиват на рецепцията и двамата се опитват да заемат единствения стол.
Проблемът със спящия бръснар често се приписва на Edsger Dijkstra (1965), един от пионерите на компютърните науки.
Решение
Има много възможни решения. Основният елемент на всеки е mutex, който гарантира, че промяната на състоянието ( състояние) само един от участниците може. Бръснарят трябва да хване това изключение на mutex, преди да провери за клиенти, и да го освободи, когато започне или да спи, или да работи. Клиентът трябва да грабне мутекса преди да влезе в магазина и да го пусне, след като е заел място на рецепцията или при фризьора. Това коригира и двата проблема, споменати в предишния раздел. Необходими са и семафори, за да се покаже състоянието на системата. Например, броят на хората в чакалнята може да се запази.
Опцията за много бръснари има допълнителната сложност на координирането на множество бръснари сред чакащите клиенти.
Вижте също
- Проблем с пушачите
Връзки
- Съвременни операционни системи (2-ро издание)от Андрю С. Таненбаум (ISBN 0-13-031358-0)
- Малката книга на семафоритеот Алън Б. Дауни, http://greenteapress.com/semaphores
- Коопериране на последователни процесиот E.W. Дейкстра. Технически доклад EWD-123, 1965 г., Технологичен университет, Айндховен, Холандия.
Фондация Уикимедия. 2010 г.
Друг класически проблем с междупроцесната комуникация се случва във фризьорски салон. Във фризьорски салон има един бръснар, неговият стол и n стола за посетители. Ако няма желаещи да ползват услугите му, бръснарят сяда на стола си и спи. Ако клиент дойде при фризьора, трябва да събуди бръснаря. Ако клиентът пристигне и види, че бръснарят е зает, той или сяда на стола (ако има място), или си тръгва (ако няма). Бръснарят и посетителите трябва да бъдат програмирани да избягват състезание. Тази задача има много аналози в областта на опашките, например информационна услуга, която обработва ограничен брой заявки едновременно, с компютъризирана система за изчакване на заявки.
Предложеното решение използва три семафора: клиенти, за преброяване на чакащи посетители (клиентът, седнал на бръснарския стол, не се взема предвид); бръснари, броят бръснари (0 или 1), които стоят без работа и чакат клиент, и мютекс за прилагане на взаимно изключване. Чакащата променлива се използва и за преброяване на чакащи посетители.
Това е копие на променливата на клиентите. Наличието на тази променлива в програмата се дължи на факта, че е невъзможно да се прочете текущата стойност на семафора. При това решение клиент, посещаващ фризьорски салон, трябва да преброи броя на чакащите клиенти. Ако посетителите са по-малко от столовете, новият посетител остава, в противен случай си тръгва.
Планиране на процеса. Проблеми на алгоритмите за планиране.
Когато компютърът изпълнява много задачи, може да има множество активни процеси на компютъра, които се опитват да получат достъп до процесора едновременно. Тази ситуация възниква, когато има два или повече процеса в състояние на готовност. Ако е наличен само един процесор, трябва да изберете между процесите. Частта от операционната система, отговорна за това, се нарича плановик , а използваният алгоритъм е алгоритъм за планиране .
Планиранее разделянето на системните изчислителни ресурси между процеси и нишки.
Почти всички процеси редуват периоди на изчисление с (диск) I/O операции. Обикновено процесорът работи без прекъсване известно време, след което се прави системно повикване за четене или запис във файл. След изпълнение на системното повикване, процесорът брои отново, докато не се нуждае от нови данни или трябва да запише получените данни.
данни и др.
Ключов въпрос при планирането е времето за вземане на решения. Оказва се, че има много ситуации, в които е необходимо планиране.
Първо, когато се създава нов процес, трябва да решите кой процес да стартирате: родител или дете. Тъй като и двата процеса са в състояние на готовност, тази ситуация не е необичайна и планировчикът може да стартира всеки от двата процеса.
Второ, планирането е необходимо, когато един процес приключи. Този процес вече не съществува, следователно е необходимо да изберете и стартирате следващия от набор от готови процеси. Ако няма процеси в състояние на готовност, обикновено се стартира неактивен процес, предоставен от системата.
Трето, когато процес блокира на I/O, семафор или по някаква друга причина, трябва да се избере и стартира друг процес. Понякога причината за блокиране може да повлияе на избора. Например, ако A -
важен процес и той чака процес B да излезе от критичната област, можете да стартирате процес B следващия, така че той да излезе от критичната област и да позволи на процес A да продължи да работи. Трудността обаче е, че планиращият обикновено не разполага с необходимата информация, за да вземе правилното решение.
Четвърто, необходимостта от планиране може да възникне, когато възникне I/O прекъсване. Ако прекъсването идва от I/O устройство, което е приключило, можете да стартирате процес, който е бил блокиран в очакване на това събитие. Планировчикът трябва да избере кой процес да започне: нов, спрян от прекъсване или друг.
Различните среди изискват различни алгоритми за планиране. Това се дължи на факта, че различните операционни системи и различните приложения са фокусирани върху различни задачи. С други думи, за какво трябва да бъде оптимизиран планировчикът варира от система до система. Могат да се разграничат три среди:
1. Системи за пакетна обработка на данни.
2. Интерактивни системи.
3. Системи в реално време.
В системите за пакетна обработка няма потребители, които седят на терминалите и чакат отговор. В такива системи са приемливи алгоритми без превключване или с превключване, но с повече време, разпределено за всеки процес. Този метод намалява броя на превключванията между процесите и подобрява ефективността.
Интерактивните системи изискват превключване на алгоритми за планиране, за да се предотврати претоварването на процесора от един процес. Дори ако нито един процес умишлено не отвлича процесора за неопределено време, грешка в програмата може да накара един процес да блокира останалите. За да се елиминират такива ситуации, се използва планиране на превключване.
В системи с ограничения в реално време приоритетът, изненадващо, не винаги е необходим, тъй като процесите знаят, че времето им е ограничено и бързо завършват работата и след това блокират. Разликата от интерактивните системи е, че системите в реално време изпълняват само програми, предназначени да подпомагат конкретни приложения. Интерактивните системи са универсални системи. Те могат да изпълняват произволни програми, които не си сътрудничат помежду си и дори са враждебни помежду си.
Проблеми на алгоритмите за планиране.
За да проектирате алгоритъм за планиране, трябва да имате представа какво трябва да прави един добър алгоритъм. Някои задачи са специфични за средата (пакетни, интерактивни системи или системи в реално време), но някои задачи са еднакви във всички системи. Списъкът със задачи е представен в таблицата.
Планиране в системи за пакетна обработка на данни.
"Кой превари, той завари"
Процесите получават достъп до процесора в реда, в който са го поискали. Най-често се формира единична опашка от чакащи процеси. Веднага щом се появи първата задача, тя веднага стартира и работи толкова дълго, колкото е необходимо. Останалите задачи се поставят в края на опашката. Когато текущият процес е блокиран, се стартира следващият в опашката, а когато блокът бъде освободен, процесът се премества в края на опашката.
Основното предимство на този алгоритъм е, че е лесен за разбиране и също толкова лесен за програмиране.
Недостатъкът е, че планирането е напълно неоптимизирано.
"Най-краткият проблем е първият"
Нека разгледаме друг алгоритъм без превключване за системи за пакетна обработка, който предполага, че периодите от време на работа са известни предварително. Ако в опашката има няколко еднакво важни задачи, планировчикът първо избира най-кратката задача.
Предимството на алгоритъма е оптимизирането на проблема.
Недостатъкът е, че тази схема работи само ако има едновременни задачи.
Свързана информация.
| 1.cpp | |||
| bradobrej1.dsp | |||
| bradobrej1.dsw | |||
| bradobrej1.ncb | |||
| bradobrej1.опт | |||
| bradobrej1.plg | |||
| 1.obj | |||
| bradobrej1.exe | |||
| bradobrej1.ilk | |||
| bradobrej1.pch | |||
| bradobrej1.pdb | |||
| vc60.idb | |||
| vc60.pdb | |||
| bradobrej1.exe | |||
| 2.cpp | |||
| bradobrej2.dsp | |||
| bradobrej2.dsw | |||
| bradobrej2.ncb | |||
| bradobrej2.opt | |||
| bradobrej2.plg | |||
| 2.об | |||
| bradobrej2.exe | |||
| bradobrej2.ilk | |||
| bradobrej2.pch | |||
| bradobrej2.pdb | |||
| vc60.idb | |||
| vc60.pdb | |||
| bradobrej2.exe | |||
| 162kb. | 05.09.2008 12:01 |
- Вижте също:
Lr1.doc
ОПЕРАЦИОННА СИСТЕМА.
Лабораторна работа №1
Предмет:Подсистема за управление на процеси. Проблемът със спящия фризьор.
Мишена:Запознайте се с основните методи, които се използват в подсистемите за управление на процеси.
Материал за предварително проучване:
1. Концепция и организация на процесите.
2. Внедряване на процеси в Windows OS.
3. Инструменти на езика C за работа с процеси.
Теоретичен материал.
Процесите често трябва да комуникират помежду си. Например, в конвейер на ядрото, изходът от първия процес трябва да бъде предаден на втория и така нататък надолу по веригата. Следователно е необходимо правилно организирано взаимодействие между процесите (IPC, междупроцесна комуникация), ако е възможно без използване на прекъсвания.
Проблемът е разделен на три точки. Вече споменахме първото: прехвърляне на информация от един процес в друг. Второто е свързано с контрола на процесите: как да се гарантира, че два процеса не се пресичат в критични ситуации (представете си два процеса, всеки от които се опитва да заеме последния мегабайт памет). Третият се отнася до координацията на действията на процесите: ако процесът Атрябва да предостави данни и процеса INотпечатайте ги, след това процесът INтрябва да изчака и да не започва да печата, докато не пристигнат данните от процеса А.
Важно е да се разбере, че две от трите описани точки се отнасят еднакво за нишките. Първият - преносът на информация - не е проблем в случай на нишки, тъй като нишките имат общо адресно пространство (преносът на информация между нишки с различни адресни пространства вече е проблем на преноса на информация между процесите). Другите два еднакво добре се отнасят до нишки: същите проблеми и същите решения. Ще разгледаме тези ситуации в контекста на процесите, но имайте предвид, че същото разсъждение се отнася и за нишките.
^ 1. Състезание.
В някои операционни системи процесите, изпълнявани заедно, могат да споделят някакъв вид споделено съхранение на данни. Всеки процес може да чете и записва информация от споделеното хранилище на данни. Това хранилище е място в основната памет (вероятно в структурата на данните на ядрото) или споделен файл. Местоположението на споделената памет не влияе върху естеството на взаимодействието или проблемите, които възникват. Нека разгледаме комуникацията между процесите, използвайки прост, но много често срещан пример: спулер за печат.
Ако даден процес трябва да отпечата файл, той поставя името на файла в специална директория на спулера. Друг процес, демонът за печат, периодично проверява за файлове за отпечатване, отпечатва файла и премахва името му от директорията.
Представете си, че директорията на спулера се състои от голям брой сегменти, номерирани с 0, 1, 2, ..., всеки от които може да съхранява име на файл. Има и две споделени променливи: навън,сочи към следващия файл за печат и в,сочещи към следващия свободен сегмент. Тези две променливи могат да се съхраняват в един файл (състоящ се от две думи), който е достъпен за всички процеси. Нека сегменти от 0 до 3 са празни в момента (тези файлове вече са отпечатани), а сегменти от 4 до 6 са заети (тези файлове чакат своя ред за отпечатване). Повече или по-малко едновременни процеси А и Брешите да поставите файла на опашка за печат. Описаната ситуация е изобразена схематично на фиг. 2.14.
В съответствие със закона на Мърфи (той е нещо подобно: „Ако нещо лошо може да се случи, то със сигурност ще се случи“) е възможна следната ситуация. Процес Ачете стойността (7) на променливата ви го съхранява в локална променлива следващ_свободен_слот.След това възниква прекъсване на таймера и процесорът превключва към процеса IN.Процес IN,на свой ред чете стойността на променливата ви го съхранява (отново 7) в неговата локална променлива следващ_свободен_слот.В този момент и двата процеса смятат, че следващият свободен сегмент е седмият. Процес INзаписва името на файла в директорията на спулера и замества стойността вна 8 след това продължава да изпълнява задачите си без писане. Накрая контролът идва върху процеса А, и той продължава откъдето е спрял. Той има достъп до променливата следващ_свободен_слот,чете неговата стойност и записва името на файла в седмия сегмент (разбира се, изтривайки името на файла, записано там от процеса IN).След това замества стойността вот 8 (следващ_свободен_слот+1 = 8). Структурата на директорията на спулера е непокътната, така че демонът за печат няма да заподозре нещо нередно, но процесният файл INняма да бъдат отпечатани.
Ситуации, при които два (или повече) процеса четат или записват данни едновременно и крайният резултат зависи от това кой е първият, се наричат условия на състезание.
Критични зони.
Как да избегнем конкуренцията? Основният начин за предотвратяване на проблеми в тази и всяка друга ситуация, включваща споделяне на памет, файлове и всичко останало, е да се попречи на повече от един процес да записва и чете споделени данни едновременно. С други думи, необходимо е взаимно изключване. Това означава, че в момента, в който един процес използва споделените данни, на друг процес ще бъде забранено да го прави. Описаният по-горе проблем възникна, защото процесът INзапочна работа с една от споделените променливи преди процеса Азавърши го. Изборът на подходяща примитивна операция за реализиране на взаимно изключване е основно съображение при проектирането на операционната система.
Проблемът за премахване на условията на състезание може да бъде формулиран на абстрактно ниво. За известен период от време процесът е зает с вътрешни изчисления и други задачи, които не водят до условия на състезание. В други моменти процесът осъществява достъп до споделени данни или извършва някакво друго действие, което може да доведе до състояние на състезание. Частта от програмата, която има достъп до споделени данни, се нарича критична област или критична секция. Ако можем да избегнем наличието на два процеса в критични региони едновременно, можем да избегнем условията на състезание.
Въпреки че това изискване елиминира условията на състезание, то не е достатъчно, за да се гарантира, че паралелните процеси работят заедно и използват данните ефективно. За да направите това, трябва да бъдат изпълнени четири условия:
1. Невъзможно е процесът да чака вечно, за да попадне в критичната област.
2. Два процеса не трябва да бъдат едновременно в критични зони.
3. Програмата не трябва да прави предположения за скоростта или броя на процесорите.
4. Процес, разположен извън критичната област, не може да блокира други процеси.
В абстрактна форма изискваното поведение на процеса е представено на фиг. 2.15. Процес А навлиза в критичната област в даден момент T 1 . Малко по-късно, в един момент T 2 , процес INсе опитва да влезе в критичната област, но не успява, защото вече има процес в критичната област а,и два процеса не трябва да са в критични зони едновременно. Следователно процесът INвременно спряно до момента T 3 когато процесът Анапуска критичната област. В даден момент T 4 процес INсъщо напуска критичната област и се връщаме в първоначалното състояние, когато не е имало процеси в критичната област.
Семафори.
През 1965 г. E. W. Dijkstra предложи използването на целочислена променлива за преброяване на тригерни сигнали, съхранени за бъдеща употреба. Той предложи нов тип променливи, т.нар семафори, чиято стойност може да бъде нула (при липса на запаметени сигнали за активиране) или някакво положително число, съответстващо на броя на забавените сигнали за активиране.
Дейкстра предложи две операции, надолуИ нагоре(обобщения сънИ Събудете се). Операция надолусравнява стойността на семафора с нула. Ако стойността на семафора е по-голяма от нула, операцията надолунамалява го (т.е. консумира един от съхранените сигнали за активиране) и просто връща контрола. Ако стойността на семафора е нула, процедурата надолуне връща контрола на процеса и процесът се поставя в състояние на изчакване. Всички операции по проверка на стойността на семафора, промяната му и прехвърлянето на процеса в състояние на изчакване се извършват като едно и неделимо елементарно действие. Това гарантира, че след като операцията е започнала, нито един процес няма да получи достъп до семафора, докато операцията не бъде завършена или блокирана. Простотата на операцията е изключително важна за разрешаване на проблема със синхронизацията и предотвратяване на условия на състезание.
Операция нагореувеличава стойността на семафора. Ако този семафор има един или повече чакащи процеси, свързани с него, които не могат да завършат по-ранна операция надолу, един от тях се избира от системата (например произволно) и му е позволено да завърши своята операция надолу. Така след операцията нагореприложен към семафор, свързан с множество чакащи процеси, стойността на семафора ще остане 0, но броят на чакащите процеси ще намалее с един. Операцията за увеличаване на стойността на семафора и активиране на процеса също е неделима. Никой процес не може да бъде блокиран, докато операцията е в ход нагорекак нито един процес не може да бъде блокиран, докато операцията се изпълнява Събудете сев предишния модел.
В оригинала Dijkstra използва вместо това надолуИ нагоресъответно обозначения P и V. В бъдеще няма да използваме оригиналните обозначения, тъй като тези обозначения не означават нищо за тези, които не знаят датския език (и казват малко на тези, които знаят езика). За първи път обозначения надолуИ нагоресе появи в Algol 68.
Решаване на проблема производител и потребител с помощта на семафори .
Както е показано в списък 2.4, проблемът със загубените тригерни сигнали може да бъде решен чрез използване на семафори. Много е важно те да се изпълняват по неделим начин. Стандартният начин е да се изпълняват операции надолуИ нагорепод формата на системни заявки, като операционната система забранява всички прекъсвания за периода на проверка на семафора, промяна на стойността му и евентуално прехвърляне на процеса в състояние на изчакване. Тъй като всички тези действия изискват само няколко инструкции на процесора, деактивирането на прекъсванията не вреди. Ако се използват множество процесори, всеки семафор трябва да бъде защитен с променлива за заключване, като се използва TSL инструкцията, за да се гарантира, че само един процесор има достъп до семафора в даден момент. Важно е да се разбере, че използването на командата TSL е фундаментално различно от активното изчакване, при което производителят или потребителят чака буферът да се напълни или изпразни. Операция със семафор ще отнеме няколко микросекунди, докато активното изчакване може да отнеме значително по-дълъг период от време.
Листинг 2.4. Проблем на производителя и потребителя със семафори
#define N 100 /* брой сегменти в буфера */
Typedef int семафор; /* семафорите са специален тип целочислени променливи */ semaphore mutex =1; /* контрол на достъпа до критичната зона */
Семафор празен = N ; /* брой празни буферни сегменти /
Семафор пълен = ОТНОСНО; /* брой пълни буферни сегменти */
voidproducer(void)
Докато (ВЯРНО)
( /* TRUE - константа равна на 1*/
Елемент = protiuce_item(); /* създаване на данни за буфериране */
Надолу (&празно); /* намалява брояча на празните буферни сегменти */
Down(&mutex): /* въведете критичен регион */
Вмъкване на_елемент(елемент); /* поставя нов елемент в буфера */
Up(&mutex): /* излизане от критична област */
Нагоре(&ful1); /* увеличава брояча на пълните буферни сегменти */
Невалиден потребител (недействителен)
( /* безкраен цикъл */
Надолу (&пълно); /* намаляване на броя на пълните буферни сегменти */
Надолу (&mutex); /* влизане в критичната зона */
Елемент = remove_item(); /* премахване на елемент от буфер */
Нагоре(&mutex); /* излизане от критичната зона */
Up(&empty): /* увеличава брояча на празните буферни сегменти */
Consume_item(item): /* обработка на елемент */
Представеното решение използва три семафора: един за броене на запълнените буферни сегменти (пълен),друг за преброяване на празни сегменти (празен)а третият е предназначен да предотврати едновременния достъп до буфера на производителя и потребителя (мутекс).Стойност на брояча пъленпървоначално равен на нула, брояч празенравен на броя на сегментите в буфера, a мютексе равно на 1. Семафори, чиято начална стойност е равна на 1, използвани за изключване на едновременното присъствие на два процеса в критичната област, се наричат двоични семафори.Взаимно изключване се постига, ако всеки процес изпълнява операцията надолупреди да влезе в критичната зона Инагоре след излизане от него.
Сега, след като имаме примитивите за междупроцесна комуникация, нека се върнем към последователността на прекъсванията, показана в Таблица. 2.2. В системи, които използват семафори, естественият начин за скриване на прекъсване е да се асоциира семафор, първоначално зададен на нула на всяко I/O устройство. Веднага след стартиране на I/O устройството, управляващият процес изпълнява операцията надолуна съответния семафор, като по този начин влиза в състояние на блокиране. Ако възникне прекъсване, манипулаторът на прекъсванията се изпълнява нагорена съответния семафор, поставяйки процеса в състояние на готовност. В такъв модел, петата стъпка в табл. 2.2 е за изпълнение нагорена семафора на устройството, така че на следващата стъпка планировчикът да може да стартира програмата, която управлява устройството. Разбира се, ако в този момент няколко процеса са в състояние на готовност, планировчикът може да избере друг, по-значим процес.
В примера, показан в листинг 2.4, семафорите са използвани по два различни начина. Тази разлика е достатъчно значителна, за да заслужава специално споменаване. Семафор мютексизползва се за прилагане на взаимно изключване, тоест за предотвратяване на едновременен достъп до буфера и свързаните променливи на два процеса.
Останалите семафори бяха използвани за синхронизация пъленИ празенса необходими, за да се гарантира, че определени последователности от събития се случват или не се случват. В нашия случай те гарантират, че производителят спира да работи, когато буферът е пълен, а потребителят спира да работи, когато буферът е празен.
^ Формулиране на проблема:
Проблемът за фризьорския салон, който спи, е алегорична демонстрация на подсистемата за управление на процеса и е формулиран от Дейкстра през 1968 г. Проблемът е формулиран по следния начин: Фризьорският салон се състои от чакалня O и стая, в която има фризьорски стол Z. През врати D можете да стигнете от стая O до стая Z, а от стая Z до улицата. Ако фризьорът влезе в чакалнята и не намери никой там, тогава той си ляга. Ако клиент влезе във фризьора и намери фризьора да спи, той го събужда. Броят на местата в чакалнята е ограничен и равен на N.
Съгласно тази задача е необходимо да се определят елементите, които ще бъдат програмирани от отделните процеси, да се разработи алгоритъм и да се реализира програмно.
Решението предлага използването на три семафора:
клиенти,за преброяване на чакащи посетители (клиент, седнал на бръснарския стол, не се брои - той вече не чака);
бръснари,броят на бръснарите (0 или 1), бездействащи в очакване на клиент;
мютексза осъществяване на взаимно изключване.
Променливата също се използва очакване,предназначен да брои чакащите посетители. Това е копие на променливата клиенти.Наличието на тази променлива в програмата се дължи на факта, че е невъзможно да се прочете текущата стойност на семафора. При това решение клиент, посещаващ фризьорски салон, трябва да преброи броя на чакащите клиенти. Ако посетителите са по-малко от столовете, новият посетител остава, в противен случай си тръгва.
1. Тема и цел на работата.
2. Лабораторна работа.
3. Програмен алгоритъм.
4. Получени резултати.
5. Изводи от работата с анализа на внедрения модел на процесно взаимодействие.
Важна и често срещана задача, чието решаване изисква синхронизация, е задачата „Читатели - Писатели“. Тази задача има много вариации. Може да се определи по следния начин. Има данни, които се споделят между редица процеси. Данните могат да се намират във файл в блок от основната памет или дори в регистрите на процесора. Има няколко процеса, които само четат тези данни (четци), и няколко други, които само записват данните (писатели). Трябва да бъдат изпълнени следните условия: - Всеки четец може да чете файла едновременно - Само един записващ файл може да записва информация във файл в даден момент. Пример за използване е работа с библиотечен каталог. Друг типичен пример е автоматизирана система за билети. Процесите „Читатели“ ни предоставят справочна информация за наличността на билети за определен полет. Процесите “Writers” се стартират от конзолата на касата, когато той издаде определен билет за нас. Има голям брой както „Читатели“, така и „Писатели“. Най-типичната област на използване на тази задача в изчислителна система е изграждането на системи за управление на файлове. Два класа процеси имат достъп до някакъв ресурс (област на паметта, файлове). „Четците“ са процеси, които могат да четат информация паралелно от някаква споделена област на паметта, която е критичен ресурс. „Писачи“ са процеси, които записват информация в тази област на паметта, като същевременно изключват един друг и процесите „Четец“. Следните условия са широко разпространени: 1. Приоритетно четене: Задава се приоритет при използването на критичния ресурс на процеса Readers. Това означава, че ако поне един Читател използва ресурс, той е затворен за използване от всички Писатели и е достъпен за използване от всички Читатели. Когато се появи заявка от Writer, е необходимо да се блокира по-нататъшният достъп до всички онези процеси на Reader, които издават заявка за критичен ресурс след нея.
15 Проблем за спящия бръснар. Проблемът със спящия бръснар. Друго действие Класическата проблемна ситуация на междупроцесна комуникация се случва във фризьорски салон. В бръснарницата има един бръснар, неговият стол и нстолове за посетители. Ако няма желаещи да ползват услугите му, бръснарят сяда на стола си и спи. Ако клиент дойде при фризьора, трябва да събуди бръснаря. Ако клиентът пристигне и види, че бръснарят е зает, той или сяда на стола (ако има място), или си тръгва (ако няма). Необходимо е да програмирате бръснаря и посетителите по такъв начин, че да избегнете състояние на конкуренция. Решението може да използва три семафора: клиенти, за преброяване на чакащи посетители (клиент, седнал на бръснарски стол, не се брои - той вече не чака); бръснари, броят на бръснарите е 0 или 1), бездейства в очакване на клиента и мютексза осъществяване на взаимно изключване. Променливата също се използва очакване, предназначен да брои чакащите посетители. Това е копие на променливата клиенти. Наличието на тази променлива в програмата се дължи на факта, че е невъзможно да се прочете текущата стойност на семафора. При това решение посетител, който влиза във фризьорски салон, трябва да преброи броя на чакащите клиенти. Ако посетителите са по-малко от столовете, новият посетител остава, в противен случай си тръгва. Когато фризьорът идва на работа сутрин, той извършва процедурата бръснар, блокиране на семафор клиенти, тъй като стойността на семафора е 0. Тогава бръснарят заспива, както е показано на фигурата, и спи до пристигането на първия клиент. Идвайки при фризьора, посетителят извършва процедурата клиент, искащ достъп до мютексза навлизане в критичния регион. Ако след него се появи друг посетител, той няма да може да направи нищо, докато първият посетител не освободи достъп до мютекс. След това посетителят проверява за свободни столове; ако не успее, той освобождава достъп до мютекси листа. Ако има свободен стол, посетителят увеличава стойността на целочислената променлива очакване. След това изпълнява процедурата нагорена семафор клиенти, като по този начин активира потока брадо-брай. В този момент и посетителят, и бръснарят са активни. Когато посетител освободи достъп до мютекс, бръснарят го грабва, извършва домакинска работа и започва да подстригва клиента. В края на 7-мата прическа посетителят излиза от процедурата и напуска фризьора. За разлика от предишните програми, няма посетителски цикъл, тъй като всеки посетител се подстригва само веднъж. Цикълът на бръснаря съществува и бръснарят-брей се опитва да намери следващия посетител. Ако успее, подстригва следващия посетител, в противен случай бръснарят заспива. Струва си да се отбележи, че въпреки липсата на трансфер на данни в проблема четец-записвач и в проблема със спящия бръснар, и двата проблема са свързани с проблеми с междупроцесната комуникация, тъй като изискват синхронизиране на няколко процеса.
16 Алгоритми за планиране на процеси.
Алгоритми за планиране на процеси
Планирането на процеса включва решаване на следните задачи:
1. определяне на момента за промяна на извършвания процес;
2. избор на процес за изпълнение от опашка от готови процеси;
3. превключване на контекста на „старите” и „новите” процеси.
FCFS- Най-простият алгоритъм за планиране е алгоритъмът, който обикновено се обозначава със съкращението FCFS след първите букви от английското му име (first come, first served). Нека си представим, че процесите в състояние на готовност са подредени. Когато даден процес влезе в състояние на готовност, той или по-точно препратка към неговата печатна платка се поставя в края на тази опашка. Изборът на нов процес за изпълнение се извършва от началото на опашката и препратката към неговата PCB се премахва оттам. Опашка от този тип има специално име в програмирането - FIFO (first in, first out). Този алгоритъм за избор на процес извършва планиране без изпреварване. Предимството на алгоритъма FCFS е лекотата на внедряване, но в същото време има и много недостатъци. Round Robin (RR)Модификация на алгоритъма FCFS е алгоритъм, наречен Round Robin (Round Robin е вид детска въртележка в САЩ) или накратко RR. По същество това е същият алгоритъм, само че се прилага в режим на изпреварващо планиране. Можете да си представите целия набор от готови процеси, организирани циклично - процесите седят на въртележка. Въртележката се върти така, че всеки процес да е близо до процесора за малък фиксиран отрязък от време, обикновено 10 - 100 милисекунди. Докато процесът е близо до процесора, той има процесора на свое разположение и може да бъде изпълнен. Този алгоритъм се изпълнява по същия начин като предишния, като се организират процеси, които са в състояние на готовност в FIFO опашка. Планировчикът избира процеса в началото на опашката за следващо изпълнение и задава таймер за генериране на прекъсване след изтичане на определен период от време. Има два варианта при извършване на процеса. 1. Времето за непрекъснато използване на процесора, изисквано от процеса (останалата част от текущия CPU пакет) е по-малко или равно на продължителността на времевия отрязък. След това процесът доброволно освобождава процесора преди изтичането на кванта от време, нов процес от началото на опашката пристига за изпълнение и таймерът започва да отброява кванта наново. 2. Продължителността на остатъка от текущия процес на изстрелване на процесора е по-голяма от времевия отрязък. След това, след като този квант изтече, процесът се прекъсва от таймер и се поставя в края на опашката от процеси, готови за изпълнение, а процесорът се разпределя за използване от процеса в началото. Ефективността на RR алгоритъма е силно повлияна от размера на времевия отрязък. При много големи квантови стойности на времето, когато всеки процес успее да завърши своя CPU пакет преди да настъпи прекъсване във времето, алгоритъмът RR се изражда в алгоритъма FCFS. При много малки стойности се създава илюзията, че всеки от n процеса работи на свой собствен виртуален процесор с производителност ~1/n от производителността на реалния процесор (SJF). Гарантирано планиране. При разглеждане на алгоритми FCFSИ Р.Р.Видяхме колко важен е за тях редът на процесите в опашката от процеси, готови за изпълнение. Ако кратките задачи се поставят по-близо до началото на опашката, тогава общата производителност на тези алгоритми се увеличава значително. Ако знаехме времето на следващия Избухване на процесораза процесите в състояние на готовност те могат да изберат за изпълнение не процеса в началото на опашката, а процеса с минимална продължителност Избухване на процесора. Ако има два или повече такива процеса, тогава за избор на един от тях можем да използваме вече известния FCFS алгоритъм. В този случай не се прилага разделяне на времето. Описаният алгоритъм се нарича „първо най-кратката задача“ или първо най-кратката задача ( S.J.F.). SJF-алгоритъм за краткосрочно планиранеможе би като изместване, така нерепресивен. При без изместване SJF-планиранепроцесорът се предоставя на избрания процес за цялото време, от което се нуждае, независимо от събитията, настъпващи в компютърната система. При изместване на SJF-планиранеОтчита се появата на нови процеси в опашката, готови за изпълнение (от тези новородени или деблокирани), докато избраният процес работи. Гарантирано планиране-Когато N потребители работят интерактивно в изчислителна система, може да се приложи алгоритъм за планиране, който гарантира, че всеки потребител ще има ~1/N част от процесорното време на свое разположение. Нека номерираме всички потребители от 1 до N. За всеки потребител с номер i въвеждаме две стойности: T i - времето, през което потребителят е в системата или, с други думи, продължителността на неговата комуникационна сесия с машината и τ i - общото процесорно време, вече разпределено за всички негови процеси по време на сесията. Би било честно потребителят да получи T i /N процесорно време. Ако τ i<
Приоритетно планиране. SJF алгоритмиИ гарантирано планиранепредставляват специални случаи приоритетно планиране. При приоритетно планиранеНа всеки процес се присвоява определена числена стойност – приоритет, според което му се разпределя процесор. Процеси със същите приоритетиса планирани по ред FCFS. За SJF алгоритъмкато такъв приоритет епреценете продължителността на следващия Избухване на процесора. Колкото по-ниска е стойността на тази оценка, толкова по-висока е приоритетима процес. За алгоритъма гарантирано приоритетно планиранеслужи като изчислен коефициент на справедливост. Колкото по-малък е, толкова повече има процесът приоритет. Алгоритми за присвояване приоритетипроцесите могат да разчитат както на вътрешни параметри, свързани с това, което се случва вътре в изчислителната система, така и на външни по отношение на нея. Вътрешните параметри включват различни количествени и качествени характеристики на процеса, като например: времеви ограничения за използване на процесора, изисквания за размера на паметта, брой отворени файлове и използвани I/O устройства, съотношение на средна продължителност I/O спукванеДа се Избухване на процесораи т.н. Алгоритмите за SJF и гарантирано планиране използват вътрешни параметри. Външните параметри могат да включват важността на процеса за постигане на определени цели, цената на платеното процесорно време и други политически фактори. Висок външен приоритетможе да бъде възложена задача от лектор или някой, който е платил $100 за един час работа. Планиранеизползвайки приоритетиможе би като изместване, така нерепресивен. При превантивно планиранепроцес с висш приоритет, който се появява в опашката от готови процеси, измества изпълняващия се процес с по-нисък приоритет. Кога непревантивно планиранетой просто отива в началото на опашката от готови процеси. Нека да разгледаме примери за използване на различни режими приоритетно планиране. основният проблем приоритетно планиранее, че ако механизмът за присвояване и промяна на приоритетипроцесите с нисък приоритет може да не работят безкрайно. Обикновено се случва едно от двете неща. Или все още чакат своя ред за изпълнение. Или компютърната система трябва да бъде изключена и те се губят. Решение на този проблем може да се постигне чрез увеличаване на стойността с течение на времето приоритет на процеса, в състояние на готовност.
