Simplifying(I)

 1 P0
 2 
 3 Reminder Section 0
 4 
 5 Critical Section 1
 6 
 7 Remider Section 1
 8 
 9 Critical Section 2
10 
11 Reminer Section 2
12 
13 Critical Section 1
14 
15 ........

 1 P1
 2 
 3 Reminder Section 0
 4 
 5 Critical Section 1
 6 
 7 Reminder Section 1
 8 
 9 Critical Section 2
10 
11 Reminder Section 2
12 
13 Critical Section 1
14 
15 Critical Section 2
16 
17 ........

Simplifying(II)

 1 P0_rs0
 2 
 3 Entry CS1
 4 CS1
 5 Exit CS1
 6 
 7 P0_rs1
 8 
 9 Entry CS2
10 CS2
11 Exit CS2
12 
13 P0_rs3
14 
15 Entry CS1
16 CS1
17 Exit CS1
18 
19 ........

 1 P1_rs0
 2 
 3 Entry CS1
 4 CS1
 5 Exit CS1
 6 
 7 P1_rs1
 8 
 9 Entry CS1
10 CS2
11 Exit CS1
12 
13 P0_rs2
14 
15 Entry CS1
16 CS1
17 Exit CS1
18 
19 Entry CS2
20 CS2
21 Exit CS2
22 
23 ........

 1 do{
 2 
 3   Entry
 4 
 5   Critical Section
 6 
 7   Exit
 8 
 9   Reminder Section
10 
11 }while(1);

Python Code

1 class MyShare:
2   turn = 0
3   need = [False, False]
4 
5 def P_i(sh1):
6   i, j = 0, 1
7   for k in range(1000):
8     sh1.need[i] = True
9     sh1.turn = j
10     while sh1.need[j] == True and sh1.turn == j:
11       pass
12 
13     print("Critical Section")
14 
15     sh1.need[0] = False
16     
17     print("Reminder Section")
18 
19 sh1 = MyShare()
20 th1 = threading.Thread(target=P_0, args=(sh1,))
21 th2 = threading.Thread(target=P_1, args=(sh1,));
22 th1.start();th2.start();

Software Soloution n processes(II)

1  // Share section
2  int number[n] = {0};

1  // Each process
2  number[i] = max(number, n)+1;
3  for(j = (i+1) % n; j != i; j = (j+1) % n)
4    while(number[i] >= number[j] && number[j] != 0)
5        ;
6  /* Critical Section */
7  number[i] = 0;

1. \(P_1\) 2: Before assignment
2. \(P_2\) 2: Get the same number as P1
3. \(P_1\) 2: After assignment
4. \(P_1\) 3: Only for P2 with the same number
5. \(P_1\) 4: number[1] >= number[2] then wait
6. \(P_2\) 3: Only for P1 with the same number
7. \(P_2\) 4: number[2] >= number[1] then wait
8. Unlimited wait or Dead Lock ∞

Software Soloution n processes(III)

1  // Share section
2  int number[n]={0};

1  // Each process
2  number[i] = max(number, n)+1;
3  for(j = (i+1) % n; j != i; j = (j+1) % n)
4    while(number[i] >= number[j]
5        && number[j] != 0 && i < j)
6        ;
7  /* Critical Section */
8  number[i] = 0;

Software Soloution n processes(IV)

1  // Share section
2  int number[n] = {0};

1  // Each process
2  number[i]=max(number,n)+1;
3  for(j=(i+1)%n;j!=i;j=(j+1)%n){
4    while((number[i]>number[j] && number[j]!=0) ||
5          ((number[i]==number[j]) && i<j  ) )
6        ;
7  /* Critical Section */
8  number[i] = 0;

Software Soloution n processes(V)

1  // Share section
2  int number[3] = {0};

 1  // P0
 2  t=max(number,3);
 3  number[0]=t+1;
 4  for(j=(0+1)%3;j!=0;j=(j+1)%3){
 5    while((number[0]>number[j] && number[j]!=0)||
 6          ((number[0]==number[j])&& 0<j))
 7        ;
 8  /* Critical Section */
 9  number[0] = 0;

 1  // P1
 2  t=max(number,3);
 3  number[1]=t+1;
 4  for(j=(1+1)%n;j!=1;j=(j+1)%n){
 5    while((number[1]>number[j] && number[j]!=0)||
 6          ((number[1]==number[j])&& 1<j))
 7        ;
 8  /* Critical Section */
 9  number[1] = 0;

1. P0-2 (number[0]== 0)
2. P1-2 (number[1]== 0)
3. P0-3 (number[0]== 1)
4. P0-4,5(all other number[j]==0)
5. P0-6,7
6. P0-8 (critical section)
7. P1-3 (number[1] == 1)
8. P1-4, 5
9. P1-6 ( i < j , 1 < 0 ? )
10. P1-7,8 (in critical section)
11. Mutual exclusion violation

Hardware Soloution(I)

1 bool testAndSet(bool& lock){
2   bool temp = lock;
3   lock = true;
4   return temp;
5 }

1   // Share section
2   bool lock=false;

1   // Each process
2   while(testAndSet(lock))
3         ;
4 
5   //    CRITICAL SECTION
6 
7   lock=false;

Assembly implementation

1 Start_Share_region:
2 
3   move lock, #0
4   ret

; Process or Thread

; Reminder Secion

CALL enter_region

; Critical Section

CALL exit_region

; Reminder Secion

1  exit_region:
2 
3    move lock, #0
4    ret

Hardware Soloution( without Starvation)

1 // Share section
2 const int n=20;
3 bool waiting[n]=
4 {false, ... , false};
5 bool lock=false;

 1 do{// Each Process
 2   waiting[i] = true;
 3   bool key=true;
 4   while(waiting[i] && key)
 5     key = testAndSet(lock);
 6   waiting[i]=false;
 7   // CRITICAL SECTION
 8   int j=(i+1)%n;
 9   while((j!=i) && !waiting[j])
10      j=(j+1)%n;
11   if(j==i)  lock=false;
12   else      waiting[j]=false;
13   // REMINDER SECTION
14 }while(1); // busy waiting

Is it possible to use Queue?

1 const int max;
2 int Queue[max];
3 bool lock = false;
4 bool busyQueue = false;

 1   while(testAndset(busyQueue));
 2   Queue.Append(process_number);
 3   busyQueue = false;
 4   bool key = true;
 5   while(Queue.front() != process_number || key)
 6     key = testAndSet(lock);
 7   //Critical Section
 8   while(testAndset(busyQueue));
 9   Queue.remove();
10   busyQueue = false;
11   lock = false;
12   // Reminder Section

Hardware Soloution swap

1 void swap(booelan& a, boolean& b){
2     boolean temp = a;
3     a = b;
4     b = temp;
5 }

1 bool lock = false

1 bool key = true;
2 while( key == true )
3   swap(lock, key);
4 
5 // CS
6 
7 lock = false;

Disable / Enable Interrupt ?

 1 // RS
 2 
 3 DisableInterrupt()
 4 
 5 // CS
 6 
 7 EnableInterrupt()
 8 
 9 // RS

Semaphore(I)

 1   class Semaphore{
 2     int s;
 3     public:
 4     Semaphore(int n){s=n;}
 5     P(void){
 6       while(s<=0)
 7         ;
 8       s--;
 9     }
10 
11     V(void){
12       s++;
13     }
14   }

1   // Shared section
2   Semaphore mutex=1;

 1   // Each process
 2   void f(void){
 3     do{
 4       mutex.P();
 5         // CS
 6       mutex.V();
 7         // RS
 8     }while(true);
 9   }

Semaphore(II - no busy waiting)

 1   class semaphore{
 2     int s; myIntQueue q;
 3     public:
 4     void P(){
 5       s--;
 6       if(s < 0){
 7         q.add(getMyProcessPID());
 8         blockMe();
 9       }
10     }
11     void V(){
12       s++;
13       if(s <= 0){
14         int i = q.del();
15         wakeupProcess(i);
16       }
17     }
18     semaphore(int i){s=i;}
19   };

1   // Shared section
2   Semaphore mutex=1;

1   void f(void){
2     do{
3       mutex.P();
4         // CS
5       mutex.V();
6         // RS
7     }while(true);
8   }

Sempahore(III) extra functions

 1   bool testAndSet(bool& target)
 2   {bool rv=target;target=true;return rv;}
 3   class myIntQueue{
 4     static const int MAX = 1000;
 5     int bufferOfQueue[MAX];
 6     int first, last;
 7     public:
 8     myIntQueue(){first=last=0;}
 9     int add(int i){
10       bufferOfQueue[last]=i;
11       last=(last+1) % MAX;
12       return i;
13     }
14     int del(void){
15       int i = bufferOfQueue[first];
16       first = (first+1) % MAX;
17       return i;
18     }
19   };
20   void wakeupProcess(int pid);
21   void blockMe(void);
22   int getMyProcessPID(void);

 1   class semaphore{
 2     int s;
 3     myIntQueue q;
 4     bool lock;
 5     public:
 6     void P(void){
 7       while(testAndSet(lock)) ;
 8       s--;
 9       if(s < 0){
10         q.add(getMyProcessPID());
11         lock = false;
12         blockMe();
13       }else lock = false;
14     }
15     void V(void){
16       while(testAndSet(lock)) ;
17       s++;
18       if(s <= 0)
19         wakeupProcess(q.del());
20       lock = false;
21     }
22     semaphore(int i)
23     {s = i;lock = false;}
24   };

Semaphore(IV) Simple Usage

1 // shared section
2 semaphore mutex=1;

 1 // Pi
 2 
 3 mutex.P();
 4 
 5 //   Critical Section
 6 
 7 mutex.V()
 8 
 9 //   Reminder Section

1 semaphore sem_printer=1, sem_scanner=1;

 1 // Pi
 2 
 3 sem_printer.P();
 4 
 5 // work with printer
 6 
 7 sem_printer.V();
 8 
 9 ....
10 
11 sem_scanner.P();
12 
13 // Work with scanner
14 
15 sem_sanner.V();

Another Forms of Semaphore

1 semaphore mutex = 1;

 1 // Each process
 2 
 3 void f1(void){
 4   while(true){
 5 
 6     P(mutex);
 7 
 8     // Critical Section
 9 
10     V(mutex);
11 
12     // Reminder Section
13 
14   }
15 }

1   semaphore mutex = 1;

 1  // Each process
 2 
 3  void f1(void){
 4    while(true){
 5 
 6      wait(mutex);
 7 
 8      // Critical Section
 9 
10      signal(mutex);
11 
12      // Reminder Section
13 
14    }
15  }

Simple Deadlock

1 semaphore sem_printer=1
2 semaphore sem_scanner=1;

 1 // P0
 2 
 3 sem_scanner.P();
 4 
 5 sem_printer.P();
 6 
 7 // work with printer
 8 
 9 sem_printer.V();
10 
11 sem_scanner.V();

 1 // P1
 2 
 3 sem_printer.P();
 4 
 5 sem_scanner.P();
 6 
 7 // Work with scanner
 8 
 9 sem_sanner.V();
10 
11 sem_printer.V();

Python Semaphore

1 # Share section
2 full = Semaphore(1)
3 
4 class MyShare:
5   n = 0

src/ps/semaphore10.py

 1 def f1(sh1):
 2   i = 1
 3   while i < 999999:
 4     full.acquire() # full.P()
 5 
 6     sh1.n = i
 7     i += 1
 8 
 9     full.release() # full.V()

 1 if __name__ == "__main__":
 2   sh1 = MyShare()
 3   th1=Thread(target=f1,args=(sh1,))
 4   th2=Thread(target=f1,args=(sh1,))
 5   th1.start()
 6   th2.start()
 7   th1.join()
 8   th2.join()
 9   print("counter ", sh1.n)

Producer consumer(II)

 1 class MyShare:
 2   counter = 0
 3   n = 100000
 4   buf = [-1] * n
 5 
 6 def produce():
 7   x = random()
 8   print('produce ', (x+1)%100)
 9   return (x+1)%100
10 
11 def consume(x):
12   print('consume ',x)

 1 if __name__ == "__main__":
 2   sh1 = MyShare()
 3   th1=Thread(target=consumer,args=(sh1,))
 4   th2=Thread(target=producer,args=(sh1,))
 5   th1.start();
 6   th2.start();
 7   th1.join();
 8   th2.join()
 9   for i in range(4): print(sh1.buf[i])
10   print("counter ", sh1.counter)

1 def producer(sh1):
2   x = -1
3   in1 = 0
4   for i in range(5000):
5     x = produce()
6     sh1.buf[in1] = x
7     in1 = in1 + 1

1 def consumer(sh1):
2   out = 0
3   x=0
4   for i in range(5000):
5     x = sh1.buf[out];
6     out = out +1
7     consume(x)
8     sh1.buf[out-1] = -1

Bounded Buffer(II)

1 class MyShare:
2   counter = 0
3   n = 100000
4   buf = [-1] * n

1 full = Semaphore(0)
2 
3 empty= Semaphore(MyShare.n)

 1 def producer(sh1):
 2   x = -1
 3   in1 = 0
 4   for i in range(5000):
 5     x = produce()
 6     empty.acquire() # empty.P()
 7     sh1.buf[in1] = x
 8     full.release(); # empty.V()
 9     in1 = (in1 + 1) % sh1.n

 1 def consumer(sh1):
 2   out = 0
 3   x=0
 4   for i in range(5000):
 5     full.acquire() # full.P()
 6     x = sh1.buf[out];
 7     empty.release() # empty.V()
 8     out = (out +1) % sh1.n
 9     consume(x)

Using any kind of Queue

1 Q = Any kind of complex Queue
2 full = Semaphore(0)
3 empty= Semaphore(10)
4 mutex = Semaphore(1)

src/ps/producer_consumer.8.py

 1 def producer(sh1):
 2   x = -1
 3   for i in range(5000):
 4     x = produce()
 5     empty.acquire() # empty.P()
 6     mutex.acquire()
 7     Q.append(x)
 8     mutex.release()
 9     full.release(); # empty.V()

 1 def consumer(sh1):
 2   x=0
 3   for i in range(5000):
 4     full.acquire() # full.P()
 5     mutex.acquire()
 6     x = Q.delete()
 7     mutex.release()
 8     empty.release() # empty.V()
 9     consume(x)

Bounded Buffer(Percent Empty)

1 class MyShare:
2   counter = 0
3   n = 100000
4   buf = [-1] * n

1 full = Semaphore(0)
2 m = int(MyShare.n * 0.9)
3 empty= Semaphore(m)

 1 def producer(sh1):
 2   x = -1
 3   in1 = 0
 4   for i in range(5000):
 5     x = produce(x, in1)
 6     empty.acquire() # empty.P()
 7     sh1.buf[in1] = x
 8     full.release(); # empty.V()
 9     in1 = (in1 + 1) % sh1.n

 1 def consumer(sh1):
 2   out = 0
 3   x=0
 4   for i in range(5000):
 5     full.acquire() # full.P()
 6     x = sh1.buf[out];
 7     empty.release() # empty.V()
 8     out = (out +1) % sh1.n
 9     consume(x,out)

Readers and Writers(I)

1 void write()
2 {}
3 
4 void read()
5 {}

1 void writer(){
2   do{
3     write();
4     RemainingTasks();
5   }while(1);
6 }

1 void reader(){
2   do{
3     read();
4     RemainingTasks();
5   }while(1);
6 }

Readers and Writers(IV)

1 semaphore wrt = 1, mutex = 1;
2 int readCount = 0;

1 void writer(){
2   wrt.P();
3   wirte();
4   wrt.V();
5 }

 1 void readers(){
 2   mutex.P();
 3   readCount++;
 4   if(readCount==1)
 5     wrt.P();
 6   mutex.V();
 7   read();
 8   mutex.P();
 9   readCount--;
10   if(readCount==0)
11     wrt.V();
12   mutex.V();
13 }

Dininig Philosophers(II)

1 //
2 // Shared Eating Objects
3 // Forks
4 // Food (Spagetti)
5 //

1 void philosopher(int i){
2   while (1){
3     think();
4     eat();
5     Rest();
6   }
7 }

1 int main(){
2   cobegin{ // C--
3     philosopher(0); philosopher(1);
4     philosopher(2); philosopher(3);
5     philosopher(4);
6   }
7 }

Dininig Philosophers(III)

1 // Shared Eating
2 
3 void think(){cout<<"thinking"<<endl;}
4 void eat(){cout <<"Eating"<<endl;}
5 semaphore forks[5]={1,1,1,1,1};

 1 void philosopher(int i){
 2   while (1){
 3     think();
 4     forks[i].P();
 5     forks[(i+1)%5].P();
 6     eat();
 7     forks[(i+1)%5].V();
 8     forks[i].V();
 9   }
10 }

1 int main(){
2   cobegin{ philosopher(0);
3     philosopher(1); philosopher(2);
4     philosopher(3); philosopher(4);
5   }
6 }

Dininig Philosophers(IV)

1 // Shared Eating
2 
3 void think(){cout <<"Eating"<<endl;}
4 void eat(){cout<<"thinking"<<endl;}
5 semaphore forks[5]={1,1,1,1,1};

 1 void philosopher(int i){
 2   while (1){
 3     think();
 4     forks[i].P();
 5     forks[(i+1)%5].P();
 6     eat();
 7     forks[(i+1)%5].V();
 8     forks[i].V();
 9   }
10 }