Description

CPSC380 Programming Assignment 1

Objective

The objective of this assignment is to familiarize yourself with the standard system calls and how to use them in a program.

Assignment: Simple File Concatenate Program

Write a C/C++ program that only uses only standard system calls to concatenate the contents of one file to another file. You should only have to use the open(), close(), read() and write() system calls. You can use printf() or fprintf() for error or informational messaging.  Your program should not explicitly prompt the user for input/output filenames but rather those should be provided on the command line.

Simple File Concatenate Program Implementation

The file concatenate program (filecat.c) is a simple text-based program that takes two arguments from the command line, again no prompting the user from within the program.

 

1. To start the filecat program

 

./filecat <input file> <output file>

where <input file> is the file to be concatenated to <output file>. Note: that <output file> can be an empty file or a file with previous contents. To make debugging easier use ASCII readable text files only.

After your program completes you should be able to do a “cat” command on the <output file> to verify it has been concatenated. Last step is to run your program with strace to determine the number/type of system calls made.

Error Handling

Perform the necessary error checking to ensure that the input file exists and that the output file can be written. You can use the system error “errno” and “strerror” to provide additional error messaging.

Grading

The program will be graded on the basic functionality, error handling and how well the implementation description was followed. Be sure to name your program filecat.c (no extra characters, capitals) and include the output from the strace command. Note that documentation and style are worth 10% of the assignment’s grade!

Submission

The program (source code only) should be posted to Blackboard on the due date

CPSC380 Programming Assignment 2

Objective

The objective of this assignment is to familiarize yourself with the notion of a process and the system call fork( ) used to create a new process and pipe( ) to communicate between processes.

Assignment: Using the Fork System Call

Write a simple shell interface program that takes a simple shell command as user input from the parent process then sends the simple shell command to the child process via a pipe IPC which actually executes the shell command.

 

 

The idea is to write a C/C++ program using the fork( ) system call to create a child process that blocks on the pipe waiting for some simple shell commands sent by the parent process via the pipe( ) IPC. The child process is then to execute the shell command read on the pipe IPC.

 

Simple Shell Program Implementation

The simple shell program (sshell.c) is a simple text-based program that takes user input from the parent then sends that input to the child process for execution. Both the parent and child process should loop waiting on either user input (parent) or pipe input (child). The program should run until the user types ‘quit’ or ‘q’ at the command prompt.

 

To start the simple shell program

 

./sshell 

osh> <simple shell command>   (where the user types in a shell command (ie ls –l))

 

The <simple shell command> is then sent to the child process via the pipe IPC which executes the command by invoking execlp( ). In the example above the directory contents would be displayed by the child process.

 

Basic Algorithm

1. Create the pipe for parent/child IPC
2. Fork the child which should start to block on the pipe waiting on shell commands
3. Parent should block waiting on user input
4. Once the shell command is input parent writes the command to the pipe
5. Child reads pipe, executes command, blocks on pipe waiting for next command.
6. Repeat steps 3-5 until ‘quit’ or ‘q’ is typed by user.

Error Handling

Perform the necessary error checking to ensure that a valid shell command was entered.

 

Grading

The program will be graded on the basic functionality, error handling and how well the implementation description was followed. Be sure to name your program sshell.c (no extra characters, capitals) Note that documentation and style are worth 10% of the assignment’s grade!

Submission

The program source code should be posted to Blackboard.

CPSC380 Programming Assignment 3

Objective

The objective of this assignment is to understand the use of threads and how threads can be used in multithreaded programs.

Assignment: Estimating Pi (π) using Monte Carlo Simulations

An interesting way of calculating π is to use a technique known as Monte Carlo, which involves randomization. This technique works as follows: Suppose you have a circle inscribed within a square, as shown in Figure below

 

 

(Assume that the radius of this circle is 1.) First, generate a series of random points as simple (x, y) coordinates. These points must fall within the Cartesian coordinates that bound the square. Of the total number of random points that are generated, some will occur within the circle. Next, estimate π by performing the following calculation:

 

 

Write a multithreaded version of this algorithm in C/C++ that creates a separate thread to generate a number of random points. The thread will count the number of points that occur within the circle and store that result in a global variable. When this thread has exited, the parent thread will calculate and output the estimated value of π. It is worth experimenting with the number of random points generated. As a general rule, the greater the number of points, the closer the approximation to π.

A code segment for generating random numbers, as well as determining if the random (x, y) point occurs within the circle is provided below:

 

/* Generates a double precision random number */

double random_double()

{

return random() / ((double)RAND_MAX + 1);

}

 

/* Check for points inside circle

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

/* generate random numbers between -1.0 and +1.0 (exclusive) */

x = random_double() * 2.0 – 1.0;

y = random_double() * 2.0 – 1.0;

 

if (sqrt(x*x + y*y) < 1.0 )

++hit_count;

}

 

Name the program mcarlo.c or mcarlo.cpp and provide the number of points of the command line:

• ./mcarlo <number of points>

 

Use at least two worker threads to calculate the total number of points as well and the number of points inside the circle.

Error Handling

Perform the necessary error checking to ensure the correct number of command-line parameters. Verify the number of points is a valid number and during test vary significantly the number of points to see the difference in the accuracy of the estimation of π.

Grading

The program will be graded on the basic functionality, error handling and how well the implementation description was followed. Be sure to name your program mcarlo.c (mcarlo.cpp) (no extra characters, capitals) Note that documentation and style are worth 10% of the assignment’s grade!

Submission

The program source code should be posted to Blackboard.

CPSC380 Programming Assignment 4 Thread Synchronization

Objective

The objective of this assignment is to use semaphores to protect the critical section between two competing threads.

Assignment: Using Threads and Mutex/Counting Semaphores

The idea is to write a C/C++ program that creates two threads. The first thread is the consumer thread that consumes the data written to a shared memory buffer. The second thread is the producer thread that “produces” the data for the shared memory buffer. In order to prevent a race condition (e.g. the consumer reading before the producer writing) use a mutex semaphore and counting semaphores to coordinate when each thread can safely write or read to/from a common shared memory region.

 

Prodcon Program Implementation

The producer/consumer program (prodcon.c) that takes three arguments from the command line (no prompting the user from within the program).

 

1. To start the prodcon program

 

./prodcon <memsize> <ntimes> where <memsize> determines the overall size (multiple of 32) and total number of blocks (memsize/32) of the shared memory region. The argument <ntimes> indicates the number of times the producer writes to and the consumer reads from the shared memory region.

 

2. The main process is to create the shared memory region from the heap based upon memsize, initialize the mutex and counting semaphores and create both the producer and consumer threads then wait for both threads to finish.

 

3. The producer thread is to create 30 bytes of random data (0-255) then store the checksum (use the Internet checksum) in the last 2 bytes of the shared memory block. The producer is to do this ntimes synchronizing with the consumer.

 

4. The consumer thread is to read the shared memory buffer of 30 bytes, calculate the checksum based upon the 30 bytes and compare that with the value stored in the shared memory buffer to ensure that the data did not get corrupted. The consumer is to do this ntimes synchronizing each read with the producer.

 

 

Error Handling

Perform the necessary error checking to ensure the correct number of command-line parameters.  Limit memsize to 64K and ensure ntimes is a positive integer. If the consumer detects a mismatched checksum it is to report the error along with the expected checksum and the calculated checksum and exit the program.

Grading

The program will be graded on the basic functionality, error handling and how well the implementation description was followed. Be sure to name your program prodcon.c (no extra characters, capitals) Note that documentation and style are worth 10% of the assignment’s grade!

Submission

The source code for program should be available on Blackboard.

CPSC380 Programming Assignment 5

Objective

The objective of this assignment is to use POSIX-based semaphores to implement a simulated real-time scheduling algorithm.

Assignment: Implementing a pseudo real-time scheduler

The idea is to write a C program that simulates a Rate Monotonic (RM) real-scheduler. The scheduler will create n number of threads (based upon the tasks defined in the task set file). Then simulate the scheduling of those threads using posix based semaphores. Each thread will wait in a while loop waiting to acquire the semaphore. Once acquired the thread will print-out just its task name then go wait for the next semaphore post by the scheduler (Only one function should be needed to implement the thread tasks). The scheduler will release or post a semaphore (so n tasks means n sempahores) based upon the RM scheduling algorithm. A “clock tick” will be simulated through each iteration of the main scheduling loop (i.e. one iteration first clock tick, two iterations, second clock tick,). Assume all task are periodic and released at time 0.

 

Scheduler Program Implementation

The RM scheduler program (rmsched.c) that takes three arguments from the command line (no prompting the user from within the program).

 

1. To start the rmsched program

 

./rmsched <nperiods> <task set> <schedule>  where <nperiods> defines the number of hyperperiods, <task set> is a file containing the task set descriptions, and scheduler is a file that contains the actual schedule. Hyperperiod is LCM of periods

 

The format of the <task set> file is as follows: (hyperperiod = 24)

T1              2          6

T2              3          12

T3              6          24

 

Where the first column represents the task name, the second column represents the task WCET and the third column represents the task period.

 

The example format of the <schedule> file is as follows:

 0    1    2    3   4   5    6   7   8   9   10   11  12   13  14 15 

 T1 T1 T2 T2 T2 T3 T1 T1 T3 T3  T3  T3  T1   T1  T2 T2

Where the first row represents the time (only needs to display once at the top of the file) and the second row represents the actual schedule for one hyperperiod. The next hyperperiod should begin on the next row.

 

2. The main process is to create the n threads and the n semaphores then determine which thread to release based upon the RM scheduling algorithm. The main process should also check to ensure that the task set is actually schedulable before attempting to create a schedule.

 

3. The task thread only has to wait for the appropriate semaphore then print-out its name to the <schedule> file and wait for the next semaphore post.

 

 

Error Handling

Perform the necessary error checking to ensure the correct number of command-line parameters as well as checking for capability to open/create/read/write to the two files. Make the sure the task-set is schedulable if not just abort the program.

Grading

The program will be graded on the basic functionality, error handling and how well the implementation description was followed. Be sure to name your program rmsched.c (no extra characters, capitals) Note that documentation and style are worth 10% of the assignment’s grade!

Submission

The program source code along with sample output should be posted onto Blackboard by the due date.

 

Thread Function:

While (1) {

sem_wait(semid)

printf(“Task Name: %s is running \n”);

fflush(stdout);

}

 

Print idle if nothing to run

Cast semid to void *

Choose which to run if tie in priority

 

Scheduler:

for (nperiods < hyperperiod) {

determine which task gets to run

release task semaphore

}

CPSC380 Programming Assignment 6

Objective

The objective of this assignment consists of writing a C/C++ program that translates logical to physical addresses for a virtual address space of size 256 = 65,536 bytes. Your program will read from a file containing logical addresses and, using a TLB as well as a page table, will translate each logical address to it’s corresponding physical address and output the value of the byte stored at the translated physical address. The goal behind this project is to simulate the steps involved in translating logical to physical addresses.

Assignment: Implementing a virtual address translator

Your program will read a file containing several 32-bit integer numbers that represent logical addresses. However, you need only be concerned with 16-bit addresses, so you must mask the rightmost 16 bits of each logical address. These 16 bits are divided into (1) an 8-bit page number and (2) 8-bit page offset. Hence, the addresses are structured as shown in figure below.

Other specifics include the following:

• 2⁸ entries in the page table
• Page size of 2⁸ bytes
• 16 entries in the TLB
• Frame size of 2⁸ bytes
• 256 frames
• Physical memory of 65,536 bytes (256 frames × 256-byte frame size)

 

Additionally, your program need only be concerned with reading logical addresses and translating them to their corresponding physical addresses. You do not need to support writing to the logical address space.

 

Address Translation

 

Your program will translate logical to physical addresses using a TLB and page table as outlined in Section 8.5. First, the page number is extracted from the logical address, and the TLB is consulted. In the case of a TLB-hit, the frame number is obtained from the TLB. In the case of a TLB-miss, the page table must be consulted. In the latter case, either the frame number is obtained from the page table or a page fault occurs. A visual representation of the address -translation is provided in the figure below:

Handling Page Faults

 

Your program will implement demand paging as described in Section 9.2. The backing store is represented by the file BACKING STORE.bin, a binary file of size 65,536 bytes. When a page fault occurs, you will read in a 256-byte page from the file BACKING STORE and store it in an available page frame in physical memory. For example, if a logical address with page number 15 resulted in a page fault, your program would read in page 15 from BACKING STORE (remember that pages begin at 0 and are 256 bytes in size) and store it in a page frame in physical memory. Once this frame is stored (and the page table and TLB are updated), subsequent accesses to page 15 will be resolved by either the TLB or the page table.

You will need to treat BACKING STORE.bin as a random-access file so that you can randomly seek to certain positions of the file for reading. We suggest using the standard C/C++ library functions for performing I/O, including fopen(), fread(), fseek(), and fclose().

The size of physical memory is the same as the size of the virtual address space—65,536 bytes—so you do not need to be concerned about page replacements during a page fault.

Run the Program

The file addresses.txt (provided on Blackboard), which contains integer values representing logical addresses ranging from 0 − 65535 (the size of the virtual address space). Your program will open this file, read each logical address and translate it to its corresponding physical address, and output the value of the signed byte at the physical address.

 

First, write a simple program that extracts the page number and offset from the following integer numbers:

 

1, 256, 32768, 32769, 128, 65534, 33153

 

Once you can correctly establish the page number and offset from an integer number, you are ready to begin. Initially, you bypass the TLB and use only a page table. You can integrate the TLB once your page table is working properly. Remember, address translation can work without a TLB; the TLB just makes it faster. When you are ready to implement the TLB, recall that it has only 16 entries, so you will need to use a replacement strategy when you update a full TLB. You may use a FIFO policy for updating your TLB.

Your program should run as follows:

 

./vmmgr addresses.txt

Your program will read in the file addresses.txt, which contains 1,000 logical addresses ranging from 0 to 65535. Your program is to translate each logical address to a physical address and determine the contents of the signed byte stored at the correct physical address. (Recall that in the C language, the char data type occupies a byte of storage, so we suggest using char values.)

 

Your program is to output the following values:

1. The logical address being translated (the integer value being read from addresses.txt).
2. The corresponding physical address (what your program translates the logical address to).
3. The signed byte value stored at the translated physical address.

 

After completion, your program is to report (output as well) the following statistics:

1. Page-fault rate—The percentage of address references that resulted in page faults.
2. TLB hit rate—The percentage of address references that were resolved in the TLB.

 

Error Handling

Perform the necessary error checking to ensure the correct number of command-line parameters as well as checking for the address file.

Grading

The program will be graded on the basic functionality, error handling and how well the implementation description was followed. Be sure to name your program vmmgr.c (no extra characters, capitals) Note that documentation and style are worth 10% of the assignment’s grade!

Submission

The program source code and program output should be posted to Blackboard.

 

 

Virtual Address: <virt addr> Physical Address: <physical Address>:

Page Faults = <num faults>

Page Fault Rate = <rate>

TLB Hits = <hits>

TLB Hit Rate = <hit rate>

 

./vmmgr <bs> <addr file> <addr_correct.txt>

 

 

Get Backing Store and Logical Address File from the Command Line

Open the BackingStore File (maybe use mmap)

Initialize the Page Table (you can use -1 if you like)

Initialize Summary Results

Loop through the Address File

Convert Logical Address to Physical Address

Get Page Number

Search the TLB for the Physical Page Address

If in TLB you have a hit

If not look in page table

If not in page table you have a page fault

If page fault copy page from backing store

Add to page table

Add to TLB

CPSC380 Programming Assignment 7

Objective

The objective of this assignment consists of writing a C/C++ program that simulates the various disk-scheduling algorithms

Assignment: Implementing a disk scheduler

Your program will implement the following disk-scheduling algorithms:

1. FCFS
2. SSTF
3. SCAN
4. C-SCAN
5. LOOK
6. C-LOOK

Your program will service a disk with 5,000 cylinders numbered 0 to 4,999. The program will read a file that contains a series of 1000 cylinder requests and services them according to each of the algorithms listed above. The program will be passed the initial position of the disk head (as a parameter on the command line) as well as the file name containing the random cylinder requests. The program is to report the total amount of head movement required by each algorithm as a summary at the end of the program.

 

Run the Program

The file cylinders.txt (provided on Blackboard), contains 1000 integer values representing a specific cylinder request which your program will open to calculate the total head movement for each algorithm.

Your program should run as follows:

 

./diskScheduler <initial cylinder position>  <cylinder request file>

 

After completion, your program is to report (output as well) the following statistics:

 

Total Head Movement for FCFS               : xxxxxxxx

Total Head Movement for SSTF               : xxxxxxxx

Total Head Movement for SCAN             : xxxxxxxx

Total Head Movement for C-SCAN         : xxxxxxxx

Total Head Movement for LOOK             : xxxxxxxx

Total Head Movement for C-LOOK         : xxxxxxxx

 

 

 

Error Handling

Perform the necessary error checking to ensure the correct number of command-line parameters as well as checking for the address file.

Grading

The program will be graded on the basic functionality, error handling and how well the implementation description was followed. Be sure to name your program diskScheduler (no extra characters, capitals) Note that documentation and style are worth 10% of the assignment’s grade!

Submission

The program source code and program output should be posted to Blackboard.