Operating systems 6

1.

Lecture 6. Mutual Exclusion in Synchronization.
Process and thread interaction and synchronization.

2.

During concurrent execution of processes, processes need to
enter the critical section (or the section of the program shared across
processes) at times for execution. It might so happen that because of
the execution of multiple processes at once, the values stored in the
critical section become inconsistent. In other words, the values
depend on the sequence of execution of instructions – also known as
a race condition. The primary task of process synchronization is to
get rid of race conditions while executing the critical section.
This is primarily achieved through mutual exclusion.
Процестерді параллель орындау кезінде процестер андасанда орындау үшін Критикалық бөлімге (немесе
процестермен ортақ бағдарламаның бөліміне) кіруі керек.
Бірнеше процестердің бір уақытта орындалуына байланысты
критикалық бөлімде сақталған мәндер сәйкес келмеуі мүмкін.
Басқаша айтқанда, мәндер нұсқаулардың орындалу ретіне
байланысты - жарыс шарты деп те аталады. Процесті
синхрондаудың негізгі міндеті – Критикалық бөлімді орындау
кезінде жарыс жағдайынан құтылу. Бұл, ең алдымен, өзара
Алып тастау арқылы жүзеге асырылады.

3.

Mutual
exclusion
is
a
property
of
process
synchronization which states that “no two processes can exist in the
critical section at any given point of time”. The term was first coined
by Dijkstra. Any process synchronization technique being used must
satisfy the property of mutual exclusion, without which it would not
be possible to get rid of a race condition.
To understand mutual exclusion, let’s take an example.
Өзара Алып тастау - бұл процестерді синхрондау қасиеті,
онда "кез-келген уақытта Критикалық бөлімде екі процесс бола
алмайды"делінген. Бұл терминді алғаш рет Дейкстра енгізген.
Процестерді синхрондаудың кез-келген әдісі өзара Алып тастау
қасиетін қанағаттандыруы керек, онсыз жарыс күйінен құтылу
мүмкін емес еді.
Өзара ерекшелікті түсіну үшін мысал келтірейік.

4.

Example:
In the clothes section of a supermarket, two people are shopping for clothes.
Мысал:Супермаркеттің киім бөлімінде екі адам киім сатып алады.

5.

Boy A decides upon some clothes to buy and heads to the changing room to try
them out. Now, while boy A is inside the changing room, there is an ‘occupied’
sign on it – indicating that no one else can come in. Girl B has to use the
changing room too, so she has to wait till boy A is done using the changing
room.
Бала А қандай да бір киім сатып алуды шешеді және оны киіп көру үшін
киім ауыстыратын бөлмеге барады. Енді А Бала киім ауыстыратын
бөлмеде болғандықтан, оған басқа ешкім кіре алмайтынын көрсететін "бос
емес" белгісі ілулі тұр. В қыз да киім ауыстыратын бөлмені пайдалануы
керек, сондықтан ол киім ауыстыратын бөлмені пайдалануды аяқтағанша
күтуі керек.

6.

Once boy A comes out of the changing room, the sign on it changes from
‘occupied’ to ‘vacant’ – indicating that another person can use it. Hence, girl
B proceeds to use the changing room, while the sign displays ‘occupied’
again.
Бала А киім ауыстыратын бөлмеден шыққаннан кейін, ондағы тақта
«бос емес» дегеннен «бос» болып өзгереді, бұл оны басқа адам
пайдалана алатынын көрсетеді. Демек, Б қызы киім ауыстыратын
бөлмені пайдалануды жалғастыруда, ал тақтайшада "бос емес" қайта
көрсетіледі.

7.

The changing room is nothing but the critical section,
boy A and girl B are two different processes, while the
sign outside the changing room indicates the process
synchronization mechanism being used.
Киім ауыстыратын бөлме - бұл А бала мен В қызы
екі түрлі процесс болатын критикалық бөлімнен
басқа ештеңе емес, ал киім ауыстыратын бөлменің
сыртындағы белгі процестерді синхрондау
механизмін көрсетеді.

8.

Inter Process Communication (IPC)
A process can be of two types:
Independent process.
Co-operating process.

9.

An independent process is not affected by the execution of other
processes while a co-operating process can be affected by other
executing processes. Though one can think that those processes,
which are running independently, will execute very efficiently, in
reality, there are many situations when co-operative nature can be
utilized for increasing computational speed, convenience, and
modularity. Inter-process communication (IPC) is a mechanism that
allows processes to communicate with each other and synchronize
their actions.
Тәуелсіз процеске басқа процестердің орындалуы әсер етпейді,
ал кооперативті (ынтымақтастық) процесіне басқа
орындалатын процестер әсер етуі мүмкін. Дербес орындалатын
процестер өте тиімді орындалады деп ойлағанымен, есептеу
жылдамдығын, ыңғайлылығы мен модульділігін арттыру үшін
кооперативті сипатты қолдануға болатын көптеген жағдайлар
бар. Процессаралық байланыс (IPC) - бұл процестердің бірбірімен өзара әрекеттесуіне және олардың әрекеттерін
синхрондауға мүмкіндік беретін механизм.

10.

The communication between these processes can be seen as
a method of co-operation between them. Processes can
communicate with each other through both:
Shared Memory
Message passing
Бұл процестер арасындағы байланысты олардың
арасындағы ынтымақтастық әдісі ретінде қарастыруға
болады. Процестер төмендегі екеуі арқылы бір бірімен
әрекеттесе алады:
Жалпы жады
Хабарламаларды жіберу

11.

Figure 1 below shows a basic structure of communication between processes via the shared memory method
and via the message passing method.
Төмендегі 1-суретте Жалпы жад әдісі мен хабарлама жіберу әдісі арқылы процестер арасындағы
мәліметтер алмасудың негізгі құрылымы көрсетілген.

12.

An operating system can implement both methods of communication. First, we will discuss the shared
memory methods of communication and then message passing. Communication between processes using
shared memory requires processes to share some variable, and it completely depends on how the
programmer will implement it. One way of communication using shared memory can be imagined like
this: Suppose process1 and process2 are executing simultaneously, and they share some resources or use
some information from another process. Process 1 generates information about certain computations or
resources being used and keeps it as a record in shared memory. When process 2 needs to use the shared
information, it will check in the record stored in shared memory and take note of the information
generated by process1 and act accordingly. Processes can use shared memory for extracting information
as a record from another process as well as for delivering any specific information to other processes.
Операциялық жүйе екі байланыс әдісін де жүзеге асыра алады. Алдымен біз ортақ жадпен
байланысу әдістерін, содан кейін хабарламаларды жіберуді талқылаймыз. Ортақ жадты
пайдаланатын процестер арасындағы байланыс процестерден кейбір айнымалыларды бөлісуді
талап етеді және бұл бағдарламашының оны қалай жүзеге асыратынына байланысты. Ортақ жадты
пайдалану арқылы байланысудың бір жолы келесідей болуы мүмкін: process1 және process2 бір
уақытта орындалады және олар кейбір ресурстарды бөліседі немесе басқа процестен кейбір
ақпаратты пайдаланады делік.
1-Процесс белгілі бір есептеулер немесе пайдаланылған ресурстар туралы ақпарат жасайды және
оны жалпы жадта жазба ретінде сақтайды.
2-процесс жалпы ақпаратты пайдалануды талап еткенде, ол ортақ жадта сақталған жазбаны
тексереді, 1-процесс жасаған ақпаратты ескереді және соған сәйкес әрекет етеді. Процестер ортақ
жадты басқа процестен жазба түрінде ақпарат алу үшін, сондай-ақ кез-келген нақты ақпаратты
басқа процестерге жеткізу үшін қолдана алады.

13.

Let’s discuss an example of communication between processes using the shared memory
method.
Ортақ жад әдісін қолдана отырып, процестер арасындағы өзара әрекеттесу мысалын
талқылайық.

14.

i) Shared Memory Method
Ex: Producer-Consumer problem
There are two processes: Producer and Consumer. The producer produces some
items and the Consumer consumes that item. The two processes share a common
space or memory location known as a buffer where the item produced by the
Producer is stored and from which the Consumer consumes the item if needed.
There are two versions of this problem: the first one is known as the unbounded
buffer problem in which the Producer can keep on producing items and there is no
limit on the size of the buffer, the second one is known as the bounded buffer
problem in which the Producer can produce up to a certain number of items before it
starts waiting for Consumer to consume it. We will discuss the bounded buffer
problem. First, the Producer and the Consumer will share some common memory,
then the producer will start producing items. If the total produced item is equal to
the size of the buffer, the producer will wait to get it consumed by the Consumer.
Similarly, the consumer will first check for the availability of the item. If no item is
available, the Consumer will wait for the Producer to produce it. If there are items
available, Consumer will consume them. The pseudo-code to demonstrate is
provided below:

15.

Мысал: өндіруші мен тұтынушы мәселесі
Екі процесс бар: өндіруші және тұтынушы. Өндіруші кейбір
тауарларды шығарады, ал тұтынушы бұл затты тұтынады. Екі процесс
өндіруші шығарған және тұтынушы қажет болған жағдайда тауарды
тұтынатын тауарды сақтайтын буфер деп аталатын ортақ кеңістікті
немесе жад ұяшығын пайдаланады.
Бұл мәселенің екі нұсқасы бар: біріншісі шектеусіз буфер мәселесі
ретінде белгілі, онда өндіруші элементтерді шығаруды жалғастыра
алады және буфер өлшеміне шектеулер жоқ, екіншісі өндіруші белгілі
бір элементтер санына дейін шығара алатын шектеулі буфер мәселесі
ретінде белгілі. тұтынушы оны тұтынғанша күте бастағанға дейін
тауарлар. Біз шектеулі буфер мәселесін талқылаймыз. Алдымен
өндіруші мен тұтынушының ортақ жады болады, содан кейін өндіруші
тауарлар шығара бастайды. Егер өндірілген элементтің жалпы көлемі
буфердің өлшеміне тең болса, өндіруші оны тұтынушы тұтынғанша
күтеді. Сол сияқты, тұтынушы алдымен тауардың бар-жоғын
тексереді. Егер өнім қол жетімді болмаса, тұтынушы оны өндіруші
шығарғанша күтеді. Егер қол жетімді тауарлар болса, тұтынушы
оларды тұтынады. Көрсету үшін жалған код төменде келтірілген:

16.

#define buff_max 25
#define mod %
struct item{
// different member of the produced data
// or consumed data
---------
Shared Data between the two Processes
}
// An array is needed for holding the items.
// This is the shared place which will be
// access by both process
// item shared_buff [ buff_max ];
// Two variables which will keep track of
// the indexes of the items produced by producer
// and consumer The free index points to
// the next free index. The full index points to
// the first full index.
int free_index = 0;
int full_index = 0;

17.

Producer Process Code
item nextProduced;
while(1){
full_index);
// check if there is no space
// for production.
// if so keep waiting.
while((free_index+1) mod buff_max ==
shared_buff[free_index] = nextProduced;
free_index = (free_index + 1) mod buff_max;
}

18.

Consumer Process Code
item nextConsumed;
while(1){
// check if there is an available
// item for consumption.
// if not keep on waiting for
// get them produced.
while((free_index == full_index);
nextConsumed = shared_buff[full_index];
full_index = (full_index + 1) mod buff_max;
}

19.

In the above code, the Producer will start producing again when the (free_index+1)
mod buff max will be free because if it it not free, this implies that there are still
items that can be consumed by the Consumer so there is no need to produce more.
Similarly, if free index and full index point to the same index, this implies that there
are no items to consume.
Жоғарыдағы кодта өндіруші (free_index + 1) mod buff max тегін болған кезде
өндірісті қайтадан бастайды, өйткені егер ол тегін болмаса, бұл тұтынушы
тұтынуы мүмкін тауарлар әлі де бар дегенді білдіреді, сондықтан көбірек
өндірудің қажеті жоқ. Сол сияқты, егер бос индекс пен толық индекс бірдей
индексті көрсетсе, бұл тұтынылатын элементтер жоқ дегенді білдіреді.

20.

Messaging Passing Method
Now, We will start our discussion of the communication between processes via message
passing. In this method, processes communicate with each other without using any kind of
shared memory. If two processes p1 and p2 want to communicate with each other, they
proceed as follows:
Establish a communication link (if a link already exists, no need to establish it again.)
Start exchanging messages using basic primitives.
We need at least two primitives:
– send(message, destination) or send(message)
– receive(message, host) or receive(message)
Енді біз хабарламаларды жіберу арқылы процестер арасындағы байланысты талқылауды
бастаймыз. Бұл әдісте процестер ортақ жадты пайдаланбай бір-бірімен әрекеттеседі.
Егер екі P1 және p2 процестері бір-бірімен әрекеттескісі келсе, олар келесідей әрекет
етеді:
Байланыс арнасын орнатыңыз (егер арна бұрыннан бар болса, оны қайта орнатудың
қажеті жоқ).
Негізгі примитивтерді пайдаланып хабар алмасуды бастаңыз.
Бізге кем дегенде екі примитив қажет:
- жіберу (хабарлама, баратын жер) немесе жіберу (хабарлама)
- қабылдау (хабарлама, хост) немесе қабылдау (хабарлама)

21.

22.

The message size can be of fixed size or of variable size. If it is of fixed
size, it is easy for an OS designer but complicated for a programmer and if it
is of variable size then it is easy for a programmer but complicated for the
OS designer. A standard message can have two parts: header and body.
The header part is used for storing message type, destination id, source id,
message length, and control information. The control information contains
information like what to do if runs out of buffer space, sequence number,
priority. Generally, message is sent using FIFO style.
Хабарлама мөлшері тұрақты немесе өзгермелі болуы мүмкін. Егер
оның өлшемі бекітілген болса, бұл ОЖ әзірлеушісі үшін оңай, бірақ
бағдарламашы үшін қиын, ал егер оның өлшемі өзгермелі болса, онда
бұл бағдарламашы үшін оңай, бірақ ОЖ әзірлеушісі үшін қиын.
Стандартты хабарлама екі бөліктен тұруы мүмкін: тақырып және дене.
Тақырыптың бір бөлігі хабарлама түрін, алушы идентификаторын,
дереккөз идентификаторын, хабарлама ұзындығын және басқару
ақпаратын сақтау үшін қолданылады. Басқару ақпаратында буфердегі
орын, реттік нөмір, басымдық аяқталса не істеу керек сияқты ақпарат
бар. Әдетте, хабарлама FIFO стилінде жіберіледі.