CSS-430 Project 1 to 4 solutions

Description

CSS-430 Project 1—UNIX Shell

This project consists of designing a C program to serve as a shell interface that accepts user commands and then executes each command in a separate process.  Your implementation will support input and output redirection, as well as pipes as a form of IPC between a pair of commands.  Completing this project will involve using the UNIX fork(), exec(), wait(), dup2(), and pipe() system calls and can be completed on any Linux, UNIX, or macOS system.

1. Overview

A shell interface gives the user a prompt, after which the next command is entered. The example below illustrates the prompt osh> and the user’s next command: cat prog.c.  (This command displays the file prog.c on the terminal using the UNIX cat command.)

osh>cat prog.c

One technique for implementing a shell interface is to have the parent process first read what the user enters on the command line (in this case, cat prog.c) and then create a separate child process that performs the command.  Unless otherwise specified, the parent process waits for the child to exit before continuing.  This is similar in functionality to the new process creation illustrated in Figure 3.9. However, UNIX shells typically also allow the child process to run in the background, or concurrently.  To accomplish this, we add an ampersand (&) at the end of the command.  Thus, if we rewrite the above command as

osh>cat prog.c &

the parent and child processes will run concurrently.

The separate child process is created using the fork() system call, and the user’s command is executed using one of the system calls in the exec() family (as described in Section 3.3.1).

 

A C program that provides the general operations of a command-line shell is supplied in Figure 3.32. The main() function presents the prompt osh-> and outlines the steps to be taken after input from the user has been read. The main() function continually loops as long as should_run equals 1; when the user enters exit at the prompt, your program will set should_run to 0 and terminate.

 

#include <stdio.h>

#include <unistd.h>

 

#define MAX_LINE 80 /* The maximum length command */

 

int main(void)

{

char *args[MAX_LINE/2 + 1]; /* command line arguments */

int should_run = 1; /* flag to determine when to exit program */

 

while (should_run) {

printf(“osh>”);

fflush(stdout);

 

/**

* After reading user input, the steps are:

* (1) fork a child process using fork()

* (2) the child process will invoke execvp()

* (3) parent will invoke wait() unless command included &

*/

}

return 0;

}

 

Figure 3.32 Outline of simple shell.

 

This project is organized into several parts:

• 1. Creating the child process and executing the command in the child
• 2. Providing a history feature
• 3. Adding support of input and output redirection
• 4. Allowing the parent and child processes to communicate via a pipe

 

1. Executing Command in a Child Process

The first task is to modify the main() function in Figure 3.32 so that a child process is forked and executes the command specified by the user.  This will require parsing what the user has entered into separate tokens and storing the tokens in an array of character strings (args in Figure 3.32).  For example, if the user enters the command ps -ael at the osh> prompt, the values stored in the args array are:

args[0] = “ps”

args[1] = “-ael”

args[2] = NULL

 

This args array will be passed to the execvp() function, which has the following prototype:

execvp(char *command, char *params[])

 

Here, command represents the command to be performed and params stores the parameters to this command.  For this project, the execvp() function should be invoked as execvp(args[0], args).  Be sure to check whether the user included & to determine whether or not the parent process is to wait for the child to exit.

III. Creating a History Feature

The next task is to modify the shell interface program so that it provides a history feature to allow a user to execute the most recent command by entering !!.  For example, if a user enters the command ls −l, she can then execute that command again by entering !! at the prompt.  Any command executed in this fashion should be echoed on the user’s screen, and the command should also be placed in the history buffer as the next command.

 

Your program should also manage basic error handling. If there is no recent command in the history, entering !! should result in a message “No commands in history.”

1. Redirecting Input and Output

Your shell should then be modified to support the ‘>’ and ‘<’ redirection operators, where ‘>’ redirects the output of a command to a file and ‘<’ redirects the input to a command from a file.  For example, if a user enters

osh>ls > out.txt

the output from the ls command will be redirected to the file out.txt.  Similarly, input can be redirected as well.  For example, if the user enters

osh>sort < in.txt

the file in.txt will serve as input to the sort command.

 

Managing the redirection of both input and output will involve using the dup2() function, which duplicates an existing file descriptor to another file descriptor.  For example, if fd is a file descriptor to the file out.txt, the call

dup2(fd, STDOUT_FILENO);

duplicates fd to standard output (the terminal).  This means that any writes to standard output will in fact be sent to the out.txt file.

 

You can assume that commands will contain either one input or one output redirection and will not contain both.  In other words, you do not have to be concerned with command sequences such as sort < in.txt > out.txt.

1. Communication via a Pipe

The final modification to your shell is to allow the output of one command to serve as input to another using a pipe.  For example, the following command sequence

osh>ls -l | less

has the output of the command ls −l serve as the input to the less command.  Both the ls and less commands will run as separate processes and will communicate using the UNIX pipe() function described in Section 3.7.4.  Perhaps the easiest way to create these separate processes is to have the parent process create the child process (which will execute ls −l). This child will also create another child process (which will execute less) and will establish a pipe between itself and the child process it creates.  Implementing pipe functionality will also require using the dup2() function as described in the previous section.  Finally, although several commands can be chained together using multiple pipes, you can assume that commands will contain only one pipe character and will not be combined with any redirection operators.

CSS-430 : Operating Systems : P2 Sudoku Solution Validator

A Sudoku puzzle uses a 9 × 9 grid in which each column and row, as well as each of the nine 3 × 3 subgrids, must contain all of the digits 1 ⋯ 9.  The figure below  presents an example of a valid Sudoku puzzle. This project consists of designing a multithreaded application that determines whether the solution to a Sudoku puzzle is valid.

 

6	2	4	5	3	9	1	8	7
5	1	9	7	2	8	6	3	4
8	3	7	6	1	4	2	9	5
1	4	3	8	6	5	7	2	9
9	5	8	2	4	7	3	6	1
7	6	2	3	9	1	4	5	8
3	7	1	9	5	6	8	4	2
4	9	6	1	8	2	5	7	3
2	8	5	4	7	3	9	1	6

 

There are several different ways of multithreading this application. One suggested strategy is to create threads that check the following criteria:

• A thread to check that each column contains the digits 1 through 9
• A thread to check that each row contains the digits 1 through 9
• Nine threads to check that each of the 3 × 3 subgrids contains the digits 1 through 9

This would result in a total of eleven separate threads for validating a Sudoku puzzle.  However, you are welcome to create even more threads for this project.  For example, rather than creating one thread that checks all nine columns, you could create nine separate threads and have each of them check one column.

1. Passing Parameters to Each Thread

The parent thread will create the worker threads, passing each worker the location that it must check in the Sudoku grid.  This step will require passing several parameters to each thread. The easiest approach is to create a data structure using a struct.  For example, a structure to pass the row and column where a thread must begin validating would appear as follows:

/* structure for passing data to threads */

typedef struct

{

int row;

int column;

} parameters;

Pthreads will create worker threads using a strategy similar to that shown below:

parameters *data = (parameters *) malloc(sizeof(parameters));

data->row = 1;

data->column = 1;

/* Now create the thread passing it data as a parameter */

 

The data pointer will be passed to the pthread_create() function, which in turn will pass it as a parameter to the function that is to run as a separate thread.

1. Returning Results to the Parent Thread

Each worker thread is assigned the task of determining the validity of a particular region of the Sudoku puzzle. Once a worker has performed this check, it must pass its results back to the parent. One good way to handle this is to create an array of integer values that is visible to each thread. The i^th index in this array corresponds to the i^th worker thread. If a worker sets its corresponding value to 1, it is indicating that its region of the Sudoku puzzle is valid. Avalue of 0 indicates otherwise. When all worker threads have completed, the parent thread checks each entry in the result array to determine if the Sudoku puzzle is valid.

III. What to submit

• Write a multi-threaded program to check a Sudoku puzzle, as described above.
• Use pthreads
• Check that your program works on the grid above (it should find that it’s a valid solution)
• Change any one digit in the above grid; your checker should find the grid is no longer a valid solution
• Submit your source program: all .c files (just 1 is ok), and all .h files (0 or more is ok)

• CSS-430 : Operating Systems : P3 Scheduling Algorithms

This project involves implementing several different process scheduling algorithms. The scheduler will be assigned a predefined set of tasks and will schedule the tasks based on the selected scheduling algorithm.  Each task is assigned a priority and CPU burst. The following scheduling algorithms will be implemented:

• First-come, first-served (FCFS), which schedules tasks in the order in which they request the CPU.
• Shortest-job-first (SJF), which schedules tasks in order of the length of the tasks’ next CPU burst.
• Priority scheduling, which schedules tasks based on priority.
• Round-robin (RR) scheduling, where each task is run for a time quantum (or for the remainder of its CPU burst).
• Priority with round-robin, which schedules tasks in order of priority and uses round-robin scheduling for tasks with equal priority.

 

Priorities range from 1 to 10, where a higher numeric value indicates a higher relative priority.  For round-robin scheduling, the length of a time quantum is 10 milliseconds.

I. Implementation

The implementation of this project should be completed in  C.  Program files supporting C are provided in the source code download for the text. (See https://www.os-book.com) These supporting files read in the schedule of tasks, insert the tasks into a list, and invoke the scheduler.

The schedule of tasks has the form [task name] [priority] [CPU burst], with the following example format:

T1, 4, 20

T2, 2, 25

T3, 3, 25

T4, 3, 15

T5, 10, 10

 

Thus, task T1 has priority 4 and a CPU burst of 20 milliseconds, and so forth.  It is assumed that all tasks arrive at the same time, so your scheduler algorithms do not have to support higher-priority processes preempting processes with lower priorities. In addition, tasks do not have to be placed into a queue or list in any particular order.

 

There are a few different strategies for organizing the list of tasks, as first presented in Section 5.1.2.  One approach is to place all tasks in a single unordered list, where the strategy for task selection depends on the scheduling algorithm.  For example, SJF scheduling would search the list to find the task with the shortest next CPU burst.  Alternatively, a list could be ordered according to scheduling criteria (that is, by priority).  One other strategy involves having a separate queue for each unique priority, as shown in Figure 5.7.  These approaches are briefly discussed in Section 5.3.6.  It is also worth highlighting that we are using the terms list and queue somewhat interchangeably.  However, a queue has very specific FIFO functionality, whereas a list does not have such strict insertion and deletion requirements. You are likely to find the functionality of a general list to be more suitable when completing this project.

II. C Implementation Details

The file driver.c reads in the schedule of tasks, inserts each task into a linked list, and invokes the process scheduler by calling the schedule() function.  The schedule() function executes each task according to the specified scheduling algorithm.  Tasks selected for execution on the CPU are determined by the pickNextTask() function and are executed by invoking the run() function defined in the CPU.c file.  A Makefile is used to determine the specific scheduling algorithm that will be invoked by driver.  For example, to build the FCFS scheduler, we would enter

make fcfs

and would execute the scheduler (using the schedule of tasks schedule.txt) as follows:

./fcfs schedule.txt

Refer to the README file in the source code download for further details.  Before proceeding, be sure to familiarize yourself with the source code provided as well as the Makefile.

 

What to Submit

Please upload your solutions in the following C files:

1.       schedule_fcfs.c

2.       schedule_sjf.c

3.       schedule_priority.c

4.       schedule_rr.c

5.       schedule_priority_rr.c

In addition, if you had to change any of the downloaded files to get your solution working, please upload those altered files too.  (Please aim to keep those changes small.  You might get by with a tiny change like inserting #include-guards into one or two .h files)

 

CSS-430 : P4 Contiguous Memory Allocation

Section 9.2 of the OSC book described several algorithms for contiguous memory allocation: First-Fit, Best-Fit and Worst-Fit.

 

This project asks you to manage allocations within a memory pool of size MEMSIZE.  Your program support five different requests:

1. Allocate N bytes for a process using one of the 3 allocation algorithms
2. Free all allocations for a given process
3. Show the status of the memory pool – allocated and free blocks
4. Read a script – a sequence of commands from a file, and execute them
5. Compact the allocations, making them into one contiguous block. (This somewhat resembles the operation of a mark-sweep garbage collector in C#)

MEMSIZE has a value of 80.  So we can think of the memory pool as holding 80 bytes.  (If you prefer, you can think of it as holding 80 KBytes, where allocations are made in multiples of 1 KByte)

Processes are named as a single letter, A thru Z.

Here is an example of the Show command after some allocations and frees:

AAAAAAAAAA……….BBBBBBBBBBFFFFFFFFFFFFFFFGGG..CCCCCH…………..DDDDD…..

(MEMSIZE was chosen as 80 so the display would fit nicely onto our console screen)

The 5 command formats are as follows:

• A <name>  <size>  <algo>
  Allocate <size> bytes for process <name> using algorithm <algo>.  <algo> can be any of F for First-Fit, B for Best-Fit or W for Worst-Fit.
  Eg:          A   P   20  F           Allocate 20 bytes for process P using First-Fit
  Eg:          A   X   14  B           Allocate 14 bytes for process X using Best-Fit
• F <name>
  Free all the allocations owned by <name>
  Eg:          F  P                       Free all allocations owned by process P
• S
  Show the state of the memory pool
• R <file>
  Read the script in the file called <file> and execute each command.
  Eg:          R   TXT
• C
  Compact the memory pool, sliding all allocations to lower addresses so they become one contiguous block, and so that all the free space lies to the right as one contiguous block

Here is an example script:

A  A  10  F

A  X  10  F

A  B  10  F

A  X  20  F

A  C   5  F

A  X  15  F

A  D   5  F

F  X

The first Show command produces:

AAAAAAAAAAXXXXXXXXXXBBBBBBBBBBXXXXXXXXXXXXXXXXXXXXCCCCCXXXXXXXXXXXXXXXDDDDD…..

After the “F  X” command, it becomes:

AAAAAAAAAA……….BBBBBBBBBB………………..CCCCC……………DDDDD…..

Compaction

Here is an example pool before compaction:

AAAAAAAAAA……….BBBBBBBBBBFFFFFFFFFFFFFFFGGG..CCCCCH…………..DDDDD…..

And after compaction:

AAAAAAAAAABBBBBBBBBBFFFFFFFFFFFFFFFGGGCCCCCHDDDDD………………………….

 

The OSC book suggests the “Compact” command.  In reality, however, an Operating System cannot move memory allocations around, willy-nilly.  What if that memory included pointers, such as a linked-list.  What would go wrong?

 

But virtual machines, as used by Java and C#, do track pointers.  They can, and do, compact memory.

Grading

Here is the script we will run to grade submissions:

 

A A 10 F

A X 10 F

A B 10 F

A X 20 F

A C  5 F

A X 15 F

A D  5 F

F X

S

A E 25 F

A F 15 F

A G  3 B

A H  1 W

S

C