Articles by "operating system"
Showing posts with label operating system. Show all posts
Print Friendly and PDF

at 0
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc


Operating System ConceptsOperating Systems: Internals and Design Principles Modern Operating Systems
Operating Systems Design and Implementation Operating Systems: Principles and PracticeOperating System Concepts
Absolute Beginner's Guide to Computer BasicsPHow Computers WorkComputer Basics Absolute Beginner's Guide
Continue reading
no image

at 0
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
Paged memory management, on the one hand the actual physical memory (also called main memory) is divided into a number of fixed-size blocks of memory, called a physical page, or a page frame (page frame); on the other hand again CPU (including programmers) see the virtual address space is divided into equally sized blocks, called virtual pages, or simply page, page (page). Page size requirements are an integer power of 2, generally between 256 bytes to 4M bytes. In this book, the page size is set to 4KB. In 32 of 86x86, the virtual address space is 4GB, physical address space is 4GB, so in theory the program accessible to 1M 1M virtual pages and physical pages. Each physical page software can be placed in any place in the main memory, paging system (CPU and other hardware needed to provide the appropriate hardware support for paging mechanism, as described in the next section) provides a virtual address used in the program and the main memory dynamic mapping of physical addresses. So that when the program accesses a virtual address, paging mechanism supports automatic virtual address associated hardware CPU access the virtual address is split into page number (possibly multiple levels of page numbers) and page offset, then the page number is mapped to The page frame number, and finally add in the page offset to form a physical address, so that the final reading of the complete address / write / execute other operations.

Assume that the program is running while you read the contents of the address 0x100 to register 1 (represented by REG1), execute the following command:
mov 0x100, REG1 

Virtual address 0x100 is sent to the CPU's internal memory management unit (MMU), and MMU paging mechanism by supporting the relevant hardware logic would put the virtual address is located 0 virtual page which (set page size is 4KB), inside The offset is 0x100; and the operating system paging management subsystem has been set up the first virtual page 0 corresponds to the first two physical page frame, the start address of the physical page frame is 0x2000, then add the offset within the page Address 0x100, so the resulting physical address is 0x2100. Then MMU will put the real physical address is sent to the computer system address bus, which can access the correct physical memory unit.

If the operating system's paging management subsystem not provided with 0 corresponding virtual page physical page frame, then the first virtual page 0 There are currently no corresponding physical page frame, which causes CPU generates a page fault exceptions handled by the operating system page fault processing service routine to choose how to handle. If the page fault processing service routine that this is an illegal access, it reports an error, terminate the software running; if it is considered to be a reasonable access, it will use physical means of distribution, such as establishing the correct page page map, making it possible to re-correct Executive abnormal memory access instructions.
Continue reading
no image

at 0
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
Question 1:
                   Some CPUs provide for more than modes operation. What are two possible uses of these multiple modes?
Answer:
 Although most system only distinguish between user and kernel modes, some CPUs have supported multiple modes. Multiple modes could be used to provide a finer-grained security policy. For example rather than distinguishing between just user and kernel mode, you could distinguish between different types of user mode. Perhaps user belonging to the same group could execute each other’s code. The machine would go into a specified mode when one of these user was running code. When the machine was in this mode, a member of the group could run belonging to anyone else in the group
Another possibility would be to provide different distinction within kernel code. For example a specific mode could allow USB device drivers to run. This would mean that USB device could be serviced without having to switch to kernel mode, thereby essentially allowing USB device drivers to run in a quasi-user/kernel mode


Question 2:
                     Describe some of the challenges of designing operating system for mobile device compared with designing operating system for traditional PCs.
Answer:
     The greatest challenges in designing mobile operating systems include:
· Less storage capacity means the operating system must manage memory carefully.
· The operating system must also manage power consumption carefully.
· Less processing power plus fewer processors mean the operating system must carefully apportion
processors to applications.
Question 3:
(i)
What does Bootstrap mean?
 Answer:
A bootstrap is the process of starting up a computer. It also refers to the program that initializes the operating system (OS) during start-up.

The term bootstrap or bootstrapping originated in the early 1950s. It referred to a bootstrap load button that was used to initiate a hardwired bootstrap program, or smaller program that executed a larger program such as the OS. The term was said to be derived from the expression “pulling yourself up by your own bootstraps;” starting small and loading programs one at a time while each program is “laced” or connected to the next program to be executed in sequence.

Major component of boot strap process
  GNU grand unified boot loader (GRUB): a multiboot specification that allows the user to choose one of several OS.
  NT loader(NTLDR)
linux loader(LILO)
  Network interface controller(NIC)

A microsoft windows operating system bootstrap process runs "NT loader (NTLDR)" as we use already discuss ,while linux loader (LILO) runs the linux operating ststem 
Continue reading
no image

at 0
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
This example demonstrates how to "wait" for thread completions by using
the Pthread join routine.  Threads are explicitly created in a joinable
state for portability reasons. Use of the pthread_exit status argument is also shown. Compare to detached.c




#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#define NUM_THREADS 4

void *BusyWork(void *t)
{
   int i;
   long tid;
   double result=0.0;
   tid = (long)t;
   printf("Thread %ld starting...\n",tid);
   for (i=0; i<1000000; i++)
   {
      result = result + sin(i) * tan(i);
   }
   printf("Thread %ld done. Result = %e\n",tid, result);
   pthread_exit((void*) t);
}

int main (int argc, char *argv[])
{
   pthread_t thread[NUM_THREADS];
   pthread_attr_t attr;
   int rc;
   long t;
   void *status;

   /* Initialize and set thread detached attribute */
   pthread_attr_init(&attr);
   pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);

   for(t=0; t<NUM_THREADS; t++) {
      printf("Main: creating thread %ld\n", t);
      rc = pthread_create(&thread[t], &attr, BusyWork, (void *)t); 
      if (rc) {
         printf("ERROR; return code from pthread_create() is %d\n", rc);
         exit(-1);
         }
      }

   /* Free attribute and wait for the other threads */
   pthread_attr_destroy(&attr);
   for(t=0; t<NUM_THREADS; t++) {
      rc = pthread_join(thread[t], &status);
      if (rc) {
         printf("ERROR; return code from pthread_join() is %d\n", rc);
         exit(-1);
         }
      printf("Main: completed join with thread %ld having a status of %ld\n",t,(long)status);
      }
 
printf("Main: program completed. Exiting.\n");
pthread_exit(NULL);
}








Output








Main: creating thread 0
Main: creating thread 1
Thread 0 starting...
Main: creating thread 2
Thread 1 starting...
Main: creating thread 3
Thread 2 starting...
Thread 3 starting...
Thread 1 done. Result = -3.153838e+06
Thread 0 done. Result = -3.153838e+06
Main: completed join with thread 0 having a status of 0
Main: completed join with thread 1 having a status of 1
Thread 3 done. Result = -3.153838e+06
Thread 2 done. Result = -3.153838e+06
Main: completed join with thread 2 having a status of 2
Main: completed join with thread 3 having a status of 3
Main: program completed. Exiting.










Continue reading 

























no image


































at



0



Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc




This simple example code creates 5 threads with the pthread_create() routine. Each thread prints a "Hello World!" message, and then terminates with a call to pthread_exit().






#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#define NUM_THREADS 5

void *PrintHello(void *threadid)
{
   long tid;
   tid = (long)threadid;
   printf("Hello World! It's me, thread #%ld!\n", tid);
   pthread_exit(NULL);
}

int main(int argc, char *argv[])
{
   pthread_t threads[NUM_THREADS];
   int rc;
   long t;
   for(t=0;t<NUM_THREADS;t++){
     printf("In main: creating thread %ld\n", t);
     rc = pthread_create(&threads[t], NULL, PrintHello, (void *)t);
     if (rc){
       printf("ERROR; return code from pthread_create() is %d\n", rc);
       exit(-1);
       }
     }

   /* Last thing that main() should do */
   pthread_exit(NULL);
}










Output






In main: creating thread 0
In main: creating thread 1
Hello World! It's me, thread #0!
In main: creating thread 2
Hello World! It's me, thread #1!
Hello World! It's me, thread #2!
In main: creating thread 3
In main: creating thread 4
Hello World! It's me, thread #3!
Hello World! It's me, thread #4!

















Continue reading 

























no image


































at



0



Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc





This is the first correct solution proposed for the two-process case. Originally developed by Dekker in a different context, it was applied to the critical section problem by Dijkstra.



CONCEPT:



                      Both the turn variable and the status flags are combined in a careful way. The entry protocol begins as in Algorithm 3; we (the requesting process) set our flag and then check our neighbor's flag. If that flag is also set, the turn variable is used. There is no progress problem now because we know the other process is in its CS or entry protocol. If the turn is ours we wait for the flag of the other process to clear. No process will wait indefinitely with its flag set. If the turn belongs to the other process we wait, but we clear our flag before waiting to avoid blocking the other process. When the turn is given to us we reset our flag and proceed.



INITIALIZATION:






 typedef char boolean;
 ...
 shared boolean flags[n -1];
 shared int turn;
 ...
 turn = i ;
 ...
 flags[i ] = FREE;
 ...
 flags[j ] = FREE;
 ...


ENTRY PROTOCOL



 (for Process i ):


 /* claim the resource */
 flags[i ] = BUSY;

 /* wait if the other process is using the resource */
 while (flags[j ] == BUSY) {

  /* if waiting for the resource, also wait our turn */
  if (turn != i ) {
  
   /* but release the resource while waiting */
   flags[i ] = FREE;
   while (turn != i ) {
   }
   flags[i ] = BUSY;
  }

 } 

EXIT PROTOCOL

 (for Process i ):



/* pass the turn on, and release the resource */ turn = j ; < flags[i ] = FREE;





ANALYSIS:



The mutual exclusion requirement is assured. No process will enter its CS without setting its flag. Every process checks the other flag after setting its own. If both are set, the turn variable is used to allow only one process to proceed.



The progress requirement is assured. The turn variable is only considered when both processes are using, or trying to use, the resource.



Deadlock is not possible. No process waits with its flag continuously set, and one process always has the turn. The process with the turn will (eventually) discover the other flag free and will proceed.



Finally, bounded waiting is assured. Suppose Process j  exits its CS and re-enters immediately while Process i  is waiting. Then the turn has been given to Process i , and the flag of Process i  is set. Process j will clear its flag and wait, and Process i  will proceed.








Continue reading 




























































at



0



Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc




Assumption


    

  • assume that a variable (memory location) can only have one value; never ``between values''
    • 

  • if processes A and B write a value to the same memory location at the ``same time,'' either the value from A or the value from B will be written rather than some scrambling of bits
    • 


Peterson's Algorithm
    

  • a simple algorithm that can be run by two processes to ensure mutual exclusion for one resource (say one variable or data structure) 
    • 

  • does not require any special hardware 
    • 

  • it uses busy waiting (a spinlock)
    • 



    






Peterson's Algorithm

Shared variables are created and initialized before either process starts. The shared variables flag[0] and flag[1] are initialized to FALSE because neither process is yet interested in the critical section. The shared variable turn is set to either 0 or 1 randomly (or it can always be set to say 0).




var flag: array [0..1] of boolean; 
turn: 0..1;

%flag[k] means that process[k] is interested in the critical section
flag[0] := FALSE; 
flag[1] := FALSE; 
turn := random(0..1)







After initialization, each process, which is called process i in the code (the other process is process j), runs the following code:




repeat 
flag[i] := TRUE; 
turn := j; 
while (flag[j] and turn=j) do no-op; 
CRITICAL SECTION 
flag[i] := FALSE;




REMAINDER SECTION 






until FALSE;
Information common to both processes:
turn = 0
flag[0] = FALSE
flag[1] = FALSE

















EXAMPLE 1





Process 0



Process 1





i = 0, j = 1



i = 1, j = 0





flag[0] := TRUE



turn := 1



check (flag[1] = TRUE and turn = 1)



-  Condition is false because flag[1] = FALSE



- Since condition is false, no waiting in while loop



-  Enter the critical section



-  Process 0 happens to lose the processor













flag[1] := TRUE



turn := 0



check (flag[0] = TRUE and turn = 0)



- Since condition is true, it keeps busy waiting until it loses the processor





- Process 0 resumes and continues until it finishes in the critical section



- Leave critical section



flag[0] := FALSE



- Start executing the remainder (anything else a process does besides using the critical section)



- Process 0 happens to lose the processor













check (flag[0] = TRUE and turn = 0)



- This condition fails because flag[0] = FALSE



- No more busy waiting



- Enter the critical section













EXAMPLE 2





Process 0



Process 1





i=0, j=1



i=1, j=0





flag[0] = TRUE



turn = 1



- Lose processor here













flag[1] := TRUE



turn := 0



check (flag[0] = TRUE and turn = 0)



- Condition is true so Process 1 busy waits until it loses the processor





check (flag[1] = TRUE and turn = 1)



-  This condition is false because turn = 0



- No waiting in loop



- Enters critical section

















EXAMPLE 3





Process 0



Process 1





i=0, j=1



i=1, j=0





flag[0] = TRUE



- Lose processor here













flag[1] = TRUE



turn = 0



check (flag[0] = TRUE and turn = 0)



- Condition is true so, Process 1 busy waits until it loses the processor





turn := 1



check (flag[1] = TRUE and turn = 1)



- Condition is true so Process 0 busy waits until it loses the processor













check (flag[0] = TRUE and turn = 0)



- The condition is false so, Process 1 enters the critical section










Summary of Techniques for Critical Section Problem

Software


    

  1. Peterson's Algorithm: based on busy waiting 
    2. 

  2. Semaphores: general facility provided by operating system (e.g., OS/2)
    3. 



    

  • based on low-level techniques such as busy waiting or hardware assistance 
    • 

  • described in more detail below
    • 



    

  1. Monitors: programming language technique
    2. 

      

    • see S&G, pp. 190--197 for more details
      • 

    


Hardware


    

  1. Exclusive access to memory location
    2. 

      

    • always assumed
      • 

    

  2. Interrupts that can be turned off
    3. 

      

    • must have only one processor for mutual exclusion
      • 

    

  3. Test-and-Set: special machine-level instruction
    4. 

      

    • described in more detail below
      • 

    

  4. Swap: atomically swaps contents of two words
    5. 

      

    • see S&G, pp. 173--174 for more details
      • 

    • for example, the Exchange instruction is available in the machine language used on Intel processors.
      • 

    




Test-and-Set


    

  • hardware assistance for process synchronization 
    • 

  • a special hardware instruction that does two operations atomically 
    • 

  • i.e., both operations are executed or neither is
    • 

      

    • sets the result to current value
      • 

    • changes current value to true
      • 

    • when describing machine language (CPU) operations, the verb 'set' means 'set to true'
      • 

    



Test-and-Set Solution to the Critical Section Problem
repeat





critical section 







remainder section 

until false
Test-and-Set(target)
result := target
target := TRUE
return result




Information common to both processes:
target = FALSE











Swap 


    

  • another type of hardware assistance for process synchronization 
    • 

  • a special hardware instruction that does a complete swap (ordinarily three operations) atomically 
    • 

  • i.e., the complete swap is executed or no part of it is 
    • 

  • given pass-by-reference parameters A and B, it swaps their values
    • 



    


Swap Solution to the Critical Section Problem


    

  • uses two variables called lock and key
    • 

  • intuition: if lock is false, then a process can enter the critical section, and otherwise it can't
    • 

  • initially, lock is false
    • 





repeat
var = true
while (var == true) swap(lock, var);
critical section
lock = false;
remainder section
until false



Semaphores


    

  • originally, semaphores were flags for signalling between ships
    • 

  • a variable used for signalling between processes
    • 




·         operations possible on a semaphore:



o        initialization


        

      • done before individual processes try to operate on the semaphore
        • 

      

    




o        two main operations:


        

      • wait (or acquire)
        • 

      • signal (or release)
        • 

      

    




o        the wait and signal operations are atomic operations (e.g., the test-and-set at the top of the loop of wait is done before losing the processor)



o        e.g., a resource such as a shared data structure is protected by a semaphore. You must acquire the semaphore before using the resource and release the semaphore when you are done with the shared resource.




wait(S):
while S  0 do
no-op;
S.value := S.value - 1;

signal(S): 
S := S + 1;









In either case, the initial value for S:


    

  1. equals 1 if only one process is allowed in the critical section (binary semaphore)
    2. 

  2. equals n if at most n processes are allowed in the critical section
    3. 




Semaphore Solution to the Critical Selection Problem

repeat 

critical section 

remainder section 
until false;






Alternative Implementation of Wait and Signal



wait(S): this code is executed atomically 
S.value := S.value - 1;
if S.value < 0
then begin 
add this process to S.L; 
suspend this process; 
end;

 actual waiting is done by the suspended process 

signal(S):
S.value := S.value + 1; 
if S.value  0 
then begin 
remove a process P from S.L; 
wakeup(P); 
end;











mutex: a binary semaphore used to enforce mutual exclusion (i.e., solve the critical section problem)

Implementing Semaphores


    

  • To ensure the atomic property, the OS implementation must either:
    • 

  • turn off interrupts 
    • 

  • use busy waiting: to make sure only one process does a wait operation at once 
    • 

  • Peterson's Algorithm 
    • 

  • Test-and-Set 
    • 

  • Swap 
    • 

  • Bounded Buffer Problem (Producer/Consumer Problem)
    • 

  •  for example, in UNIX a pipe between two processes is implemented as a 4Kb buffer between the two processes
    • 
















Producer


    

  • creates data and adds to the buffer
    • 

  • do not want to overflow the buffer
    • 






Consumer


    

  • removes data from buffer (consumes it) 
    • 

  • does not want to get ahead of producer
    • 





    




Information common to both processes:


empty := n
full := 0
mutex := 1

Producer Process
repeat
produce an item in nextp 

wait(empty); 
wait(mutex); 

add nextp to buffer 

signal(mutex); 
signal(full);
until false;









Consumer Process



repeat




wait(full); 
wait(mutex); 



remove an item from buffer to nextc 

signal(mutex); 



signal(empty);



consume the item in nextc


    

  • until false;
    • 

  • mutex: (semaphore) initialized to 1
    • 

  • empty: count of empty locations in the buffer
    • 

  • initialized to n, the buffer size
    • 

  • full: count of full locations in the buffer
    • 

  • initialized
    • 









The empty and full semaphores are used for process synchronization. The mutex semaphore is used to ensure mutually exclusive access to the buffer. if we were to change the code in the consumer process from:



wait(full) 
wait(mutex)
to
wait(mutex) 
wait(full),






then we could reach a deadlock where Process 1 is waiting for Process 2 and Process 2 is waiting for Process 1. 








Continue reading 



























































at



0



Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc





Problem

The dining philosophers problem is invented by E. W. Dijkstra. Imagine that five philosophers who spend their lives just thinking and easting. In the middle of the dining room is a circular table with five chairs. The table has a big plate of spaghetti. However, there are only five chopsticks available, as shown in the following figure. Each philosopher thinks. When he gets hungry, he sits down and picks up the two chopsticks that are closest to him. If a philosopher can pick up both chopsticks, he eats for a while. After a philosopher finishes eating, he puts down the chopsticks and starts to think.































Analysis

How do we write a threaded program to simulate philosophers? First, we notice that these philosophers are in a thinking-picking up chopsticks-eating-putting down chopsticks cycle as shown below.


















The "pick up chopsticks" part is the key point. How does a philosopher pick up chopsticks? Well, in a program, we simply print out messages such as ``Have left chopsticks'', which is very easy to do. The problem is each chopstick is shared by two philosophers and hence a shared resource. We certainly do not want a philosopher to pick up a chopstick that has already been picked up by his neighbor. This is arace condition. To address this problem, we may consider each chopstick as a shared item protected by a mutex lock. Each philosopher, before he can eat, locks his left chopstick and locks his right chopstick. If the acquisitions of both locks are successful, this philosopher now owns two locks (hence two chopsticks), and can eat. After finishes easting, this philosopher releases both chopsticks, and thinks! This execution flow is shown below.






















Because we need to lock and unlock a chopstick, each chopstick is associated with a mutex lock. Since we have five philosophers who think and eat simultaneously, we need to create five threads, one for each philosopher. Since each philosopher must have access to the two mutex locks that are associated with its left and right chopsticks, these mutex locks are global variables.




Program

Let us see how the above analysis can be convert to a program. Since each philosopher should be run as a thread, we define a Philosopher class as a derived class of class Thread.












#include "ThreadClass.h" 
#define PHILOSOPHERS 5 
class Philosopher: public Thread
 { 
public: 
Philosopher(int Number, int iter); 
private: int No; 
int Iterations; void ThreadFunc();
 };














The constructor takes two arguments, Number for the number assigned to this philosopher thread, and iter for specifying the number of thinking-eating cycles.

The implementation of this class, as shown below, should have all thinking, eating, locking and unlocking mechanisms implemented. Since each chopstick must be protected by a mutex lock, we declare an array Chopstick[ ] of pointers to Mutex. Since the main program allocates these locks, they are declared as global variables using extern.

Function Filler() generates a char array that contains some spaces. Note that this function is declared to be static so that is can only be used within this file (i.e., Philosopher.cpp).

Let us look at the constructor. It receives two arguments. The first, Number, is assigned by the main program to indicate which philosopher this thread represents. The second, iter, gives the number of thinking-eating cycles for each philosopher. The constructor is very simple. It gives this thread a name. Thus, if the value of Number is 2 (i.e., philosopher 2), this thread will have the namePhilosopher2.









#include <iostream>



#include "Philosopher.h"







extern Mutex *Chopstick[PHILOSOPHERS];  // locks for chopsticks







static strstream *Filler(int n)



{



     int  i;



     strstream *Space;







     Space = new strstream;



     for (i = 0; i < n; i++)



          (*Space) << ' ';



     (*Space) << '\0';







     return Space;



}







Philosopher::Philosopher(int Number, int iter)



                        : No(Number), Iterations(iter)



{



     ThreadName.seekp(0, ios::beg);



     ThreadName << "Philosopher" << Number << '\0';



}







void Philosopher::ThreadFunc() 



{



     Thread::ThreadFunc();



     strstream *Space;



     int i;







     Space = Filler(No*2);







     for (i = 0; i < Iterations; i++) {



          Delay();                                     // think for a while



          Chopstick[No]->Lock();                       // get left chopstick



          Chopstick[(No+1) % PHILOSOPHERS]->Lock();    // gets right chopstick



          cout << Space->str() << ThreadName.str() 



               << " begin eating." << endl;            



          Delay();                                     // eat for a while



          cout << Space->str() << ThreadName.str()



               << " finish eating." << endl;            



          Chopstick[No]->Unlock();                     // release left chopstick



          Chopstick[(No+1) % PHILOSOPHERS]->Unlock();  // release right chopstick                       



     }



     Exit();



}










The function ThreadFunc() implements the executable code of a philosopher thread. First of all, it creates a char array of No*2 spaces so that this thread's output would be indented properly. After this, this thread iterates Iteration times. In each cycle, this thread simulates thinking and eating. To this end, we use a method of class Thread: Delay(). The purpose of Delay() is simply delaying the execution of the thread for a random number of times. This simulates ``think for a while'' and ``eat for a while.''

Let us look at how locking and unlocking of chopsticks is carried out. Suppose the chopsticks are numbered counter clockwise. For philosopher i, his left chopstick is i and his right chopstick is i+1. Of course, we cannot use i+1 directly, because when i=4, the right chopstick of philosopher is 0 rather than 5. This can easily be done with the remainder operator: (i+1) % PHILOSOPHERS, wherePHILOSOPHERS is the number of philosophers. In the above code, philosopher No thinks for a while, locks his left chopstick by calling the method Chopstick[No]->Lock(), locks his right chopstick by calling the method Chopstick[(No+1) % PHILOSOPHERS]->Lock(), eats for a while, unlocks his left chopstick by calling the method Chopstick[No]->Unlock(), and unlocks his right chopstick by calling the method Chopstick[(No+1) % PHILOSOPHERS]->Unlock(). This completes one thinking-eating cycle. This cycle repeats for Iteration number of times.







Note that in the above code each philosopher picks up, or locks, his left chopstick first followed by the right one.The main program, as usual, is easy as shown below. The number of thinking-eating cycles a philosopher must perform is the only command line argument. 



Since mutex locks must be created before their uses, the main program allocates the mutex locks before the creation of threads.



In the following, each mutex lock is created with a name like ChopStick0, ChopStick1, ..., ChopStick4. After all chopstick locks are created, the main thread continues to create philosopher threads and joins with all of its child threads. When all philosopher threads terminate, the main thread returns (i.e., terminates).













#include <iostream>



#include <stdlib.h>







#include "Philosopher.h"







Mutex *Chopstick[PHILOSOPHERS];  // locks for chopsticks







int main(int argc, char *argv[]) 



{



     Philosopher *Philosophers[PHILOSOPHERS];



     int i, iter;



     strstream name;







     if (argc != 2) {



          cout << "Use " << argv[0] << " #-of-iterations." << endl;



          exit(0);          



     }      



     else



          iter = abs(atoi(argv[1]));







     for (i=0; i < PHILOSOPHERS; i++) {  // initialize chopstick mutex locks



          name.seekp(0, ios::beg);



          name << "ChopStick" << i << '\0';



          Chopstick[i] = new Mutex(name.str());



     }







     for (i=0; i < PHILOSOPHERS; i++) {  // initialize and run philosopher threads



          Philosophers[i] = new Philosopher(i, iter);



          Philosophers[i]->Begin();



     }







     for (i=0; i < PHILOSOPHERS; i++) 



          Philosophers[i]->Join();







     Exit();



     



     return 0;



}
















Discussion


    

  • Here are some very important facts about this program:
    • 

  • If you read the program carefully, we implicitly assign philosopher No to use chopstick ChopStick[No] and chopstick ChopStick[(No+1) % PHILOSOPHERS]. In other word, each philosopher is assigned to a fixed chair. Is it necessary? It is certainly not. For example, when a philosopher is hungry, we can generate a random integer i in the range of 0 and 4. If that chair is occupied, generate another random integer. In this way, we simulate the activity of finding an un-occupied chair. Once an un-occupied chair, say i, is found, this philosopher uses chopstick i and (i + 1) % PHILOSOPHERS. In doing so, our program may be very complex and blur our original focus. After you understand the above program, you can certainly try to make it more realistic. 
    • 

  • The above program forces each philosopher to pick up and put down his left chopstick, followed by his right one. This is also for the purpose of simplicity. In fact, it is easy to see that the order of putting down the chopsticks is irrelevant. Try to reasoning about this yourself. 
    • 

  • The most serious problem of this program is that deadlock could occur! 
    • 

  • What if every philosopher sits down about the same time and picks up his left chopstick as shown in the following figure? In this case, all chopsticks are locked and none of the philosophers can successfully lock his right chopstick. As a result, we have a circular waiting (i.e., every philosopher waits for his right chopstick that is currently being locked by his right neighbor), and hence a deadlock occurs.
    • 








 
 
    


    • 

  • Starvation is also a problem! 
    • 


    • 

  • Imagine that two philosophers are fast thinkers and fast eaters. They think fast and get hungry fast. Then, they sit down in opposite chairs as shown below. Because they are so fast, it is possible that they can lock their chopsticks and eat. After finish eating and before their neighbors can lock the chopsticks and eat, they come back again and lock the chopsticks and eat. In this case, the other three philosophers, even though they have been sitting for a long time, they have no chance to eat. This is a starvation. Note that it is not a deadlock because there is no circular waiting, and every one has a chance to eat
    • 


    • 

    • 

  • The above shows a simple example of starvation. You can find more complicated thinking-eating sequence that also generate starvation.
    • 















Continue reading 

































Subscribe to:
Posts (Atom)