Monday, June 23, 2014

Process Simulator Solved

In this post we are going to solve the problem stated in the previous post; Process Simulator Problem. We used Java language and Object Oriented programming.

Problem Solved
To solve our problem, we have created two classes; Processes class and Simulator class.

Processes Class
Process class contains the characteristics and properties of the needed process as stated in Problem statement in the previous post along with their getters and setters methods. Following is a snippet of Process class. You can download the full code from here.




Simulator class
Simulator class is the driver for our project. It contains the main() method that instructs an object of class Simulator, open File object to read the input file, and output File object to write the results.

After than the program call method simulate on instance of class Simulator and pass it the input, and output file objects.

The following snippet of code shows the implementation of main() method.


The following figure shows an example about the input file, which contains the order of execution for the processes, and the desired states for each process.


 In method simulate(), we pass the input file object and the output file object. Then we open a BufferedReader to InputStreamReader which holds a FileInputStream, which in turn, wrapps the input file sent as input parameter. See the following figure.

After that, we read the input file line by line and append it to the out BufferedReader.




Then we split each single line to know the required operation; ( ‘C’ = create, ‘I’ = Interrupt, etc ). Then we pass this operation to the selected operation. See the following figure.



For more information about the program, you can download it from here; it contains the Simulator class, Process class, input text file, and the expected output text file.


Sunday, June 22, 2014

Process Simulator Problem

In this post we are going to see a full detailed description about simulation problem of OS work involved in managing processes using Java language.

Problem Statement
Out simulator should simulate the process management in a given a Hypothetical Operation System. Input should be read in from a file, and output should be written to a file. The format of the input file will be discussed below.

In the simulation, a Process ID (PID) identifies each process. To achieve this, our program keeps track of the parent of each process, all of the children of each process, and the remaining burst time for the process.

All processes are pre-emptible. That is mean, when any interrupt occurs; the running process is preempted, giving up control of the processor. Its remaining burst time is decrease by 1. When the remaining burst time of a process reaches 0, it terminates and all its children also must be destroyed. Otherwise, the process moves to the appropriate state.

 After the interrupt, the first process on the Ready queue becomes the running process. If there are no processes on the Ready queue, assume that a pseudo-process with PID 0 (e.g. getty() in Unix) runs, but this ``process'' is never put on the Ready queue. (Thus when the simulation first begins, the only thing in the system is the pseudo-process 0, and it is the parent of the first ``real'' process.) Input consists of a series of actions each of which is initiated by an interrupt. All requests come from the preempted process.

Following are the actions or the states that the process could be in:

C <n> <b>
Create a process with PID n with initial burst size b. The parent is the preempted process.

D <n>
Destroy the process with PID n and any children processes that it has. Only the parent of a process or the process itself can destroy a process. Other requests are ignored. You may assume that there will not be any requests to destroy PID 0.

I
TimerRunOut interrupt. The preempted process must move to the Ready state or terminate, as appropriate.

W <n>
Preempted process has initiated an event with Event ID (EID) n that it must wait for.

E <n>
Event n has taken place. The process waiting for this event moves to the Ready state. Note this action also preempts the current process.

X
Exit the program. The program should output the current state of the simulation before exiting.


In the next post Process Simulator Solved we are going to discuss the code and you can download it and try it on your own PC.

Wednesday, April 23, 2014

Telephone Game Simulator using C Language

This post shows the code for simulating game of Telephone using processes and pipes. The initial process will create n – 1 additional processes and n pipes, with the processes in chain, connected by pipes.
Text will be read by the initial processes and then be passed from process to process along the chain, using the pipes, which have been created. Each process will read from its incoming pipe and read from its outgoing pipe.

When the message reaches its last process that process will write the message it receives to (stdout) monitor.

To simulate errors in communication, each process may transmit some characters incorrectly.
The program have two command-line arguments, the number of processes n and a real number 0.0 <= p <= 1.0. p represents the probability that a character will be transferred incorrectly. C library function random() used to generate random numbers which is used to decide whether or not a given character should be transmitted correctly.

Following is the C program listing for the above problem description:

#include <time.h>
#include <string.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>

#define MAX_MESSAGE_LENGTH 2048

struct pipe_t{
  int fd[2];
};


/*
 * returns 0 if user did not pass correct arguments
 * returns 1 if user passed correct arguments and initializes
 * these arguments
 */
int check_args(int argc, char **argv, int *n_processes, double *p)
{
  if (argc < 3) {
    printf("Usage: ./program n_processes error_probability\n");
    return 0;
  }
  *n_processes = atoi(argv[1]);
  *p = atof(argv[2]);
  if (*p < 0 || *p > 1) {
    printf("Error probability must be between 0 and 1\n");
    return 0;
  }
  return 1;
}


/*
 * returns random character
 * from set:
 */
char rand_char()
{
  int printable_characters_num = 127 - 32;
  return 32 + (rand() % printable_characters_num);
}

/*
 * returns 1 with probability @p
 * 0 otherwise
 */
int rand_bool(double p)
{
  return (random() / (double)RAND_MAX) < p;
}

/*
 * @str is initial string
 * p is probability of each character to be transimtted
 * incorrectly
 * returns changed @str
 */
void generate_incorrect_str(char *str, double p)
{
  int i;
  for (i = 0; i < strlen(str); i++) {
    if (rand_bool(p)) { // incorrect
      char ch = rand_char();
      str[i] = ch; // replace character
    }
  }
}

/*
 * last process in chain calls this function
 * @str is char* received from previous process
 * @str_origin is original message
 * this function compares them and displays results
 * on stdout
 */
void display_statistics(char *str, char *str_origin)
{
  int errors = 0;
  int i;
  for (i = 0; i < strlen(str); i++) {
    if (str[i] != str_origin[i]) { // compare 2 strings char by char
      errors++; // count errors
    }
  }
  printf("Received %d characters\n", (int) strlen(str));
  double error_rate = ((double) errors) / strlen(str);
  printf("Error rate is: %f percent\n", error_rate * 100);
  printf("Received string: %s\n", str);
  printf("\n\n");
  //  printf("Original string: %s\n", str_origin);
}

/*
 * child processes start here
 * each process reads from @readfd and writes to @writefd
 * if process is last in the chain, @islast is 1, otherwise 0
 * @originfd is file descriptor, from which the last process
 * reads original message
 */
void run_process(int readfd, int writefd,
               int islast, int originfd, double p)
{
  // each process will have differrent random seed
  srand(time(NULL) + getpid());
  char str[MAX_MESSAGE_LENGTH + 1];
  // read message send from previous process
  int status = read(readfd, str, MAX_MESSAGE_LENGTH + 1);
  // could not read - some error happened
  if (status == -1) {
    perror("read:");
  }
 
  // last process
  if (islast) {
    char str_origin[MAX_MESSAGE_LENGTH + 1];
    // read original message from parent process
       status = read(originfd, str_origin, MAX_MESSAGE_LENGTH + 1);
    if (status == -1) {
      // could not read - some error happened
         perror("read:");
    }
    // to standard output
       display_statistics(str, str_origin); 
  } else {
    generate_incorrect_str(str, p);
    // send message to the next process
       write(writefd, str, strlen(str) + 1);
  }
 
}

/*
 * @p is probability of error on each write
 * @n is number of child processes to be created
 * @pipes is an array of initialized pipe_t structs
 * @pipes length must be at least n + 1
 *
 * this function creates n child processes
 */
int create_processes(int n, double p,
                   struct pipe_t *pipes)
{
  int i;
  for (i = 0; i < n; i++) { // crete n child processes
   
    pid_t pid = fork();

    if (pid == -1) { // could not fork because of error
      perror("fork:");
      exit(-1);
    }

    if (pid == 0) { // child process
      if (i != n - 1) {
       run_process(pipes[i].fd[0], pipes[i + 1].fd[1], 0, -1, p); // one of the middle chain processes
      } else {
       run_process(pipes[i].fd[0], -1, 1, pipes[i + 1].fd[0], p); // last process in the chain
      }
      exit(EXIT_SUCCESS); // child has finished its job. good-bye;
    } else { // parent process
      // nothing to do
    }
  }

  return 1;
}

/*
 * waits until all child processes are finished
 */
int wait_processes()
{
  int status;
  while(1) {
    int res = wait(&status);
    if (res == -1) break; // no more child
  }
  return 1;
}

/*
 * iterateos over @pipes array, which has length of @n_pipes
 * and initializes each pipe;
 * returns 1 on success, 0 otherwise;
 */
int create_pipes(int n_pipes, struct pipe_t *pipes)
{
  int i;
  for (i = 0; i < n_pipes; i++) {
    struct pipe_t *pp = &pipes[i];
    if(pipe(pp->fd) == -1) {
      perror("pipe:"); // some error happened
      return 0;
    }
  }
  return 1;
}

/*
 * only parent process must call this function.
 * this function reads input from stdin and sends to
 * the next child process in chain.
 * and sends to last child process too.
 */
void send_message(struct pipe_t *pipes, int n_pipes)
{
  char str[MAX_MESSAGE_LENGTH + 1];
  fgets(str, MAX_MESSAGE_LENGTH + 1, stdin);
  write(pipes[0].fd[1], str, strlen(str) + 1); // send message to next process in the chain
  write(pipes[n_pipes - 1].fd[1], str, strlen(str) + 1); // send message to the last process
}



int main(int argc, char **argv)
{
  int n_processes; // processes to be created and be in chain
  double p; // probability of each character sending with error
  if(!check_args(argc, argv, &n_processes, &p)) { // initializes p and n_processes
    exit(-1); // if invalid arguments - exit
  }
  int n_pipes = n_processes; // they should be equal
  struct pipe_t pipes[n_pipes]; // create array of pipes
  if (!create_pipes(n_pipes, pipes)) exit(-1); // if could not create pipe - exit
  create_processes(n_processes - 1, p, pipes); // create n-1 process (n-th process is parent himself)
  send_message(pipes, n_pipes); // send initial message from parent to the chain
  wait_processes(); // wait child processes to finish

  return 0; // and return
}