Assignment

Multiple-Processor Scheduling Simulation

The goal of this simulation is to give you some experiences using POSIX Pthreads library functions for thread creations and synchronizations. You will learn how to solve the critical section problems using pthread_mutex_lock(),  pthread_mutex_unlock(), pthread_cond_wait(), and pthread_cond_signal().

Write a program scheduler in C under Linux environment to simulate the operations of 3-Processor Scheduling Simulation. The programs for this simulator should include the following features:

1) There is one Ready-Queue, where the processes are waiting for three CPUs, CPU-1, CPU-2, and CPU-3. Assume that initially the queue is empty, and all CPUs are waiting for the processes. Assume the queue has capacity only for m processes.

2) Each CPU is waiting for processes arriving in the queue. The arrival of a process (to the queue) should interrupt any of the waiting CPUs, which will grab the process, and execute it. Use pthread_cond_wait( ) and pthread_cond_signal( ) functions to simulate this step.

3) Assume that a job list is stored in a file, job_file. A job in the file is represented as:

job#  cpu_burst

where job# is a positive integer, and the cpu_burst is another positive integer (in second). Note that, each  job may have different  cpu_burst. Create yourself the job_file that contains 200 jobs with random cpu_burst (1 to 50).

4) Write a routine  job() that takes jobs from the  job_file and puts them into the FIFO Ready_Queue. For each job placed in the queue, the job()  routine should write this activity into a file, simulation_log.

Job#: cpu_burst

Arrival time: 13:42:51

where the arrival time is the time the job is placed into the queue (actual time).

5) Write a routine cpu() that simulates the operations of each CPU. When there is process in the queue, one of the CPUs takes the process from the queue, and executes it for its entire cpu_burst. Simulate this event, for example, using a sleep call.

6) When CPU-1, for example, takes one process from the queue, the CPU should write the following information in the simulation_log:

Statistics for CPU-1:

Process #n

Arrival time: 13:42:55

Service time: 13:42:57

The service time is the time the CPU picked up the process from the queue. Notice that the process's waiting time is its service time minus arrival time.

7) When  CPU-1, for example, finishes with one process, the CPU should write the following information in the simulation_log:

Statistics for CPU-1:

Process #n

Arrival time: 13:42:55

Completion time: 13:42:57

where the completion time is the time when the CPU finished servicing the process #n. Notice that the process's turnaround time is its completion time minus its arrival time.

8) The simulator terminates when there is no more process (NOT when the queue is empty). The simulator should write the following information to the log file:

Number of processes: #of processes

Average waiting time: w seconds

Average turn around time: t seconds

where #of processes is the total processes serviced by the 3 CPUs. The average waiting time, and turn around time are computed by dividing the total waiting time and turn around time with #of processes over all the three CPUs, respectively. Note that you may have variables num_processes, total_waiting_time and total_turnaround_time shared by the three CPUs.

9) Note, the assignment does not require high degree of precision for the time.

10) To test for the correctness of your program, you should run the program as follows:

scheduler job_file m

Implementation using Pthreads

1. Create a thread job that runs the job() routine, and three threads CPU-1, CPU-2, and CPU-3 each runs the cpu()  routine. Each CPU thread blocks when the ready queue is empty, and job thread blocks when the queue is full.

Use pthread mutual exclusion functions, pthread_mutex_wait(), pthread_mutex_signal(), pthread_cond_wait(), and pthread_cond_signal() to solve the critical section and synchronization problems in the simulator. Make sure you consider all possible race conditions in the simulator.

3. You have to describe/discuss in detail each of the variables, including its data structure, the threads that access them, and how mutual exclusion is achieved.

4. Remember to clean up all resources created in your program.