OPERATING SYSTEM DESIGN

22/ 06 / 2006

In a two-dimensional universe of RxC cells, a cell may contain or not a live organism.Initially the universe is populated by a set of live organisms.A cell has 8 neighbors.

The population evolves according to the following generation rules:

  1. An organism survives for the next generation if it has 2 or 3neighbors
  2. An organism dies if it has more than 3 or less than 2neighbors
  3. Each void cell with 3 neighbors will contain a live organism in the next generation

Implement a concurrent C program with a CONTROLLER thread that

  • initialize the universe by reading a file init.dat and createsRxCorganisms (threads)
  • shows the generation maps when the user give the command ’s’ from the keyboard
  • stop showing the maps the user give the command ’n’ from the keyboard
  • exit the threads when the user give the command ’e’ from the keyboard

Each organism (thread) has associated a status - live or dead- according to rules 1. 2. and 3.

The thread must synchronize – using semaphores - to proceed per generation cycles, where in each cycle:

  • threads performs their update operations concurrently,
  • and then one of them displays the new generation map

All threads execute the same code, there is no coordinator.

// init.dat corresponding to the generation 0 map of the figure

10 10// R and C

4 3

5 3

6 3

5 4

Sequential pseudo code

initial_configuration (map);

display (map);

do {

clear(new_map);

// UPDATE – new generation

for (i = 1; i < R; i++) {

for (j = 1; j < C; j++) {

n = count_neighbors (map, i, j);

if (map[i][j]) { // live

if ((n == 2) || (n == 3))

new_map[i][j] = true;

}

else { // void

if ((n == 3))

new_map[i][j] = true;

}

} // END new generation

swap (map, new_map)

if (show) display (map);

scanf ("%c%c", &ans, &ans);

if (ans == 's') show = true; else if (ans == 'n') show = false;

} while (ans != 'e');

} …………

OPERATING SYSTEM DESIGN

22 / 06 / 2006

  1. Given this reference string

334444121122323314432255543

Compute the page fault frequency and the mean resident set for the Working Set strategy with control parameter  = 3.

  1. Write the sequence of instructions of a parent process that
  • creates a child, which executes a file print.exe,which takes anargument (a filename: foo), and prints on foowhat it receives from its standard input
  • loops forever sleeping 2 seconds, increments an integer number and writes its value on its standard output (code not necessary)
  • redirects its standard output to the standard input of the child process when it receives a SIGUSR1signal, and recovers the original redirection to the standard output when it receives again the same signal.
  1. Illustratethe use of thepopensystem call.
  1. Describe the distributed solution to the Mutual Exclusion problem.