logo

TechCodeview

Semafory v synchronizaci procesů

Semafory jsou jen normální proměnné používané ke koordinaci činností více procesů v počítačovém systému. Používají se k vynucení vzájemného vyloučení, vyhýbání se rasovým podmínkám a implementaci synchronizace mezi procesy.

Proces používání Semaforů poskytuje dvě operace: čekání (P) a signál (V). Operace čekání snižuje hodnotu semaforu a operace signálu zvyšuje hodnotu semaforu. Když je hodnota semaforu nula, každý proces, který provádí operaci čekání, bude zablokován, dokud jiný proces neprovede operaci signálu.



Semafory se používají k implementaci kritických sekcí, což jsou oblasti kódu, které musí v jednu chvíli spustit pouze jeden proces. Pomocí semaforů mohou procesy koordinovat přístup ke sdíleným zdrojům, jako je sdílená paměť nebo I/O zařízení.

Semafor je speciální druh synchronizačních dat, který lze použít pouze prostřednictvím specifických synchronizačních primitiv. Když proces provádí operaci čekání na semaforu, operace zkontroluje, zda je hodnota semaforu>0. Pokud ano, sníží hodnotu semaforu a nechá proces pokračovat v provádění; jinak blokuje proces na semaforu. Signální operace na semaforu aktivuje proces blokovaný na semaforu, pokud existuje, nebo zvýší hodnotu semaforu o 1. Kvůli této sémantice se semafory také nazývají počítací semafory. Počáteční hodnota semaforu určuje, kolik procesů může překonat operaci čekání.

Semafory jsou dvou typů:



  1. Binární semafor –
    Toto je také známé jako zámek mutex. Může mít pouze dvě hodnoty – 0 a 1. Jeho hodnota je inicializována na 1. Slouží k implementaci řešení problémů kritických úseků s více procesy.
  2. Počítací semafor –
    Jeho hodnota se může pohybovat v neomezené doméně. Používá se k řízení přístupu k prostředku, který má více instancí.

Nyní se podívejme, jak to dělá.

Nejprve se podívejte na dvě operace, které lze použít pro přístup a změnu hodnoty proměnné semaforu.

P-and-V-operace-in-OS



Některé body týkající se provozu P a V:

  1. Operace P se také nazývá operace čekání, spánku nebo dolů a operace V se také nazývá operace signalizace, probuzení nebo spuštění.
  2. Obě operace jsou atomické a semafor (semafory) je vždy inicializován na jeden. Zde atomický znamená, že proměnná, na které se čtení, úprava a aktualizace děje ve stejný čas/okamžik bez preempce, tj. mezi čtením, úpravou a aktualizací není provedena žádná další operace, která by mohla změnit proměnnou.
  3. Kritická část je obklopena oběma operacemi pro implementaci synchronizace procesů. Viz obrázek níže. Kritická část procesu P je mezi operací P a V.

Nyní se podívejme, jak implementuje vzájemné vyloučení. Nechť existují dva procesy P1 a P2 a semafor s je inicializován jako 1. Nyní, když předpokládejme, že P1 vstoupí do své kritické sekce, pak se hodnota semaforu s stane 0. Nyní, pokud chce P2 vstoupit do své kritické sekce, bude čekat, dokud s> 0, k tomu může dojít pouze tehdy, když P1 dokončí svůj kritický úsek a zavolá operaci V na semaforech.

Tímto způsobem je dosaženo vzájemného vyloučení. Podívejte se na níže uvedený obrázek pro podrobnosti, což je binární semafor.


Implementace: Binární semafory

C++ 
struct semaphore {    enum value(0, 1);  // q contains all Process Control Blocks (PCBs)  // corresponding to processes got blocked  // while performing down operation.  Queueq; }; P(semafor s) { if (s.hodnota == 1) { s.hodnota = 0;  } else { // přidání procesu do čekající fronty q.push(P) sleep();  } } V(semafor s) { if (s.q je prázdné) { s.hodnota = 1;  } else { // výběr procesu z čekající fronty Proces p = q.front();  // odebere proces z čekání, jak byl // odeslán pro CS q.pop();  probuzení(p);  } } // Tento kód upravil Susobhan Akhuli>
C 
#include  #include #include struct semaphore{  Queueq;  int hodnota; }; void P(struct semafor s) { if (s.hodnota == 1) { s.hodnota = 0;  } else { s.q.push(P);   spát();  } } void V(semafor s) { if (s.q je prázdné) { s.hodnota = 1;  } else { // Získání procesu z fronty čekání Proces p = q.front();  // Odebrání procesu z čekání q.pop();  probuzení(p);  } } int main() { printf('To je Hemiš!!');    // Tento kód je autorem Himesh Singh Chauhan return 0; } // Tento kód upravil Susobhan Akhuli>
Jáva 
import java.util.*; class Semaphore {  public enum Value { Zero, One }  public Queueq = nový LinkedList();  public Value value = Hodnota.Jedna;  public void P(Semafor s, Proces p) { if (s.hodnota == Hodnota.Jedna) { s.hodnota = Hodnota.Nula;  } else { // přidání procesu do čekající fronty q.add(p);  p.Spánek();  } } public void V(Semafor s) { if (s.q.size() == 0) { s.value = Hodnota.Jedna;  } else { // výběr procesu z čekající fronty Proces p = q.peek();  // odebere proces z čekání, protože // byl odeslán pro CS q.remove();  p.Wakeup();  } } }>
Python3 
from enum import Enum from queue import Queue class Semaphore: class Value(Enum): Zero = 0 One = 1 def __init__(self): self.q = Queue() self.value = Semaphore.Value.One def P(self, s, p): if s.value == Semaphore.Value.One: s.value = Semaphore.Value.Zero else: # add the process to the waiting queue s.q.put(p) p.Sleep() def V(self, s): if s.q.qsize() == 0: s.value = Semaphore.Value.One else: # select a process from waiting queue p = s.q.queue[0] # remove the process from waiting as it has # been sent for CS s.q.get() p.Wakeup()>
C# 
using System.Collections.Generic; class Semaphore {  public enum value { Zero, One }  public Queueq = nová fronta();  public void P(Semafor s, Proces p) { if (s.hodnota == hodnota.Jedna) { s.hodnota = hodnota.Nula;  } else { // přidání procesu do čekající fronty q.Enqueue(p);  p.Spánek();  } } public void V(Semafor s) { if (s.q.Count == 0) { s.value = hodnota.Jedna;  } else { // výběr procesu z čekající fronty Proces p = q.Peek();  // odebere proces z čekání, jak byl // odeslán pro CS q.Dequeue();  p.Wakeup();  } } }>
Javascript 
class Semaphore {  constructor() {  this.value = 0;  // q contains all Process Control Blocks (PCBs)  // corresponding to processes got blocked  // while performing down operation.  this.q = [];  }  P() {  if (this.value == 1) {  this.value = 0;  } else {  // add the process to the waiting queue  this.q.push(P);  sleep();  }  }  V() {  if (this.q.length == 0) {  this.value = 1;  } else {  // select a process from waiting queue  let p = this.q.shift();  // remove the process from waiting as it has been  // sent for CS  wakeup(p);  }  } }>

Výše uvedený popis je pro binární semafor, který může nabývat pouze dvou hodnot 0 a 1 a zajistit vzájemné vyloučení. Existuje ještě jeden typ semaforu zvaný počítací semafor, který může nabývat hodnot větších než jedna.

Nyní předpokládejme, že existuje zdroj, jehož počet instancí je 4. Nyní inicializujeme S = 4 a zbytek je stejný jako u binárního semaforu. Kdykoli proces chce tento zdroj, volá P nebo čeká na funkci a když je hotovo, volá V nebo signální funkci. Pokud se hodnota S stane nulovou, musí proces počkat, dokud se S nestane kladnou. Předpokládejme například, že existují 4 procesy P1, P2, P3, P4 a všechny volají operaci čekání na S (inicializované 4). Pokud jiný proces P5 požaduje zdroj, měl by počkat, dokud jeden ze čtyř procesů nezavolá signální funkci a hodnota semaforu se stane kladnou.

příkaz grep v linuxu

Omezení:

  1. Jedním z největších omezení semaforu je inverze priority.
  2. Zablokování, předpokládejme, že se proces pokouší probudit jiný proces, který není ve stavu spánku. Proto může zablokování blokovat neomezeně dlouho.
  3. Operační systém musí sledovat všechna volání na čekání a signalizovat semaforu.

Problém v této implementaci semaforu:

Hlavním problémem semaforů je, že vyžadují rušné čekání. Pokud je proces v kritické sekci, pak ostatní procesy, které se snaží vstoupit do kritické sekce, budou čekat, dokud kritická sekce nebude obsazena žádným procesem. Kdykoli nějaký proces čeká, pak nepřetržitě kontroluje hodnotu semaforu (podívejte se na tento řádek, zatímco (s==0); v provozu P) a plýtvá cyklem CPU.

Existuje také možnost zablokování, protože procesy se během čekání na zámek neustále točí. Aby se tomu zabránilo, je níže uvedena jiná implementace.

Implementace: Počítací semafor

CPP 
struct Semaphore {  int value;  // q contains all Process Control Blocks(PCBs)  // corresponding to processes got blocked  // while performing down operation.  Queueq; }; P(Semafor s) { s.hodnota = s.hodnota - 1;  if (s.hodnota< 0) {  // add process to queue  // here p is a process which is currently executing  q.push(p);  block();  }  else  return; } V(Semaphore s) {  s.value = s.value + 1;  if (s.value <= 0) {  // remove process p from queue  Process p = q.pop();  wakeup(p);  }  else  return; }>
Jáva 
import java.util.LinkedList; import java.util.Queue; // semaphore class  class Semaphore {  // our value  int value;  Queueq;  public Semafor(int hodnota) { this.value = hodnota;  q = new LinkedList();  } public void P(Proces p) { hodnota--;  jestliže (hodnota< 0) {  q.add(p);  p.block();  }  }  public void V()  {  value++;  if (value <= 0) {  Process p = q.remove();  p.wakeup();  }  } }>
Python3 
import heapq # Global Variable to track the Processes going into Critical Section COUNTER=1 class Semaphore: def __init__(self,value): # Value of the Semaphore passed to the Constructor self.value=value # The Waiting queue which will be using the heapq module of Python self.q=list() def getSemaphore(self):  ''' Function to print the Value of the Semaphore Variable ''' print(f'Semaphore Value: {self.value}') def block(process): print(f'Process {process} Blocked.') def wakeup(process): print(f'Process {process} Waked Up and Completed it's work.') def P(s): global COUNTER s.value=s.value-1 if(s.value<0): heapq.heappush(s.q,COUNTER) block(COUNTER) else: print(f'Process {COUNTER} gone inside the Critical Section.') COUNTER+=1 return def V(s): global COUNTER s.value=s.value+1 if(s.value<=0): p=heapq.heappop(s.q) wakeup(p) COUNTER-=1 else: print(f'Process {COUNTER} completed it's work.') COUNTER-=1 return # Can Pass the Value of the Counting Semaphore to the Class Constructor # Example for Counting Semaphore value as 2 s1=Semaphore(2) s1.getSemaphore() P(s1) s1.getSemaphore() P(s1) s1.getSemaphore() P(s1) s1.getSemaphore() V(s1) s1.getSemaphore() V(s1) s1.getSemaphore() V(s1) s1.getSemaphore() # This Code is Contributed by Himesh Singh Chauhan>
C# 
using System.Collections.Generic; public class Semaphore {  public int value;  // q contains all Process Control Blocks(PCBs)  // corresponding to processes got blocked  // while performing down operation.  Queueq = nová fronta();  public void P(Proces p) { hodnota--;  jestliže (hodnota< 0) {  // add process to queue  q.Enqueue(p);  p.block();  }  }  public void V()  {  value++;  if (value <= 0) {  // remove process p from queue  Process p = q.Dequeue();  p.wakeup();  }  } }>
JavaScript 
// Define a Semaphore object function Semaphore() {  this.value = 0;  this.q = []; // Initialize an array to act as a queue } // Implement the P operation Semaphore.prototype.P = function(p) {  this.value = this.value - 1;  if (this.value < 0) {  // Add process to queue  this.q.push(p);  // Assuming block() and wakeup() functions are defined elsewhere  block();  } }; // Implement the V operation Semaphore.prototype.V = function() {  this.value = this.value + 1;  if (this.value <= 0) {  // Remove process p from queue  var p = this.q.shift();  // Assuming wakeup() function is defined elsewhere  wakeup(p);  } }; // This code is contributed by Susobhan Akhuli>

V této implementaci, kdykoli proces čeká, je přidán do čekající fronty procesů spojených s tímto semaforem. To se provádí prostřednictvím systémového volání block() v tomto procesu. Po dokončení procesu zavolá funkci signálu a jeden proces ve frontě se obnoví. Používá systémové volání wakeup().

Výhody semaforů:

  • Jednoduchý a účinný mechanismus pro synchronizaci procesů
  • Podporuje koordinaci mezi více procesy
  • Poskytuje flexibilní a robustní způsob správy sdílených zdrojů.
  • Lze jej použít k implementaci kritických částí v programu.
  • Lze jej použít k vyhnutí se závodním podmínkám.

Nevýhody semaforů:

  • Může to vést ke snížení výkonu kvůli režii spojené s čekáním a operacemi signálu.
  • Při nesprávném použití může dojít k uváznutí.
  • Navrhl ji Dijkstra v roce 1965, což je velmi významná technika pro řízení souběžných procesů pomocí jednoduché celočíselné hodnoty, která je známá jako semafor. Semafor je jednoduše celočíselná proměnná, která je sdílena mezi vlákny. Tato proměnná se používá k řešení problému kritické sekce a k dosažení synchronizace procesů v prostředí multiprocessingu.
  • Pokud není správně používán, může způsobit problémy s výkonem v programu.
  • Může být obtížné ladit a udržovat.
  • Pokud není správně používán, může být náchylný k závodním podmínkám a dalším problémům se synchronizací.
  • Může být zranitelný vůči určitým typům útoků, jako jsou útoky odmítnutí služby.