CS 252 Homework 1 Solution

Part 1.

__T/F_ ELF stands for Executable Link Format. (Executable Link File)
__T_ A process has a stack for every thread it contains.
__T_ A process ID may be reused
__T_ Race conditons are more likely to happen in multiprocessor machines.
__F_ In POSIX threads, the thread calling fork will create a child process that is a copy of the parent inclluding all the threads in the process. (only in Solaris and by calling thr_create)

2. Write down the fields of an i-node

Major number – Identifier number that tells which device a file is on
Minor number – Identifier number that tells which actual file it is on the device
Permission modes – The permissions for owner, group, and others
Owners – ID of users and groups that own the file
Size – Size of file in bytes
Timestamps – Creation time, access time, modification time
Reference count – Number of times this file is referenced as hard link

3. Explain what is deadlock and what is starvation and give an example of each.

Deadlock happens when threads are waiting for resources that will not be available to them and will not proceed. The only way to end the deadlock is to kill the process. An example would be the Dining Philosophers Problem where every philosopher waits for a fork and no one is willing to give up the fork he/she is holding.

Starvation is not as serious as deadlock. It is a condition where a thread might take a long time to obtain resources because there are constantly other threads holding the locks. An example would be the read/write locks.

4. What are the advantages and disadvantages of using threads vs. using processes?

Threads		Processes
Advantages	Disadvantages	Advantages	Disadvantages
Faster thread creation Faster context switch Faster communication using global variables	Synchronization problem Less robust -- 1 thread crashing causes entire program to crash	No synchronization problem -- Every process has its own memory address space	Slower creation of new processes Slower context switch Slower communication with pipes and files

5. Mention three important files that are stored in /etc in UNIX.

/etc/passwd - Stores users information
/etc/group - Stores groups information
/etc/inetd.conf- Stores internet services configuration

6. In the following code,

T1:
a) mutex_lock(&m3)
b) mutex_lock(&m5);
c) mutex_lock(&m1);

T2:
d) mutex_lock(&m2)
e)mutex_lock(&m5);
f)mutex_lock(&m4);

T3:
g)mutex_lock(&m4);
h)mutex_lock(&m3);
i)mutex_lock(&m1);

a) give a sequence of steps using the letters at the left of each statement that will cause the threads to get into a deadlok. (Example: T1a, T2d, T3g ... etc)

T1:
a)
Context switch ->
.
.
.
b) Blocked
Context switch->

T2:
.
d)
e)
Context switch ->
.
.
f) Blocked

T3:
.
.
.
g)
h) Blocked
Context switch ->

b) Draw the graph representation of the deadlock.

m3->T1 ->m5->T2->m4->T3
^ |
|---------------------------------

c) Rewrite the code to prevent the deadlock.

T1:
a) mutex_lock(&m1)
b) mutex_lock(&m3);
c) mutex_lock(&m5);

T2:
d) mutex_lock(&m2)
e)mutex_lock(&m4);
f)mutex_lock(&m5);

T3:
g)mutex_lock(&m1);
h)mutex_lock(&m3);
i)mutex_lock(&m4);

7.Assume that the following code for adding items into an array. addToArray will return the index in the array where the value was added or -1 if the buffer is full. a) What problems do you see can happen if multiple threads try to run it? Rewrite the code to solve the problem.

a) If multiple threads try to run it, the array data structure can get messed up. For example:
First thread reaches the line “array[count] = value”, then context switch happens. Second thread reaches the same line and overwrites array[count]. The first value added is then lost. Also the return count-1; should be
substituted by return tmp; and have tmp be set to count-1 before the mutex_lock.

#define MAXCOUNT;
int count = 0;
int array[MAXCOUNT];

int addToArray(int value)
{
if (count == MAXCOUNT) {
return -1;
}

array[count]=value;

count = count + 1;

return count-1;

}

New Code
#include <pthread.h>
#define MAXCOUNT;
int count = 0;
int array[MAXCOUNT];
pthread_mutex_t _mutex;    //initialized by pthread_mutex_init()
int addToArray(int value)
{
pthread_mutex_lock(&_mutex);
if (count == MAXCOUNT) {
   pthread_mutex_unlock(&mutex);
      return -1;
}

array[count]=value;

count = count + 1;

int tmp = count-1;

pthread_mutex_unlock(&_mutex);

return tmp;

}

8. A program calls the system call write(file_descriptor, buffer, nbytes). Explain step by step the sequence of events, the checks, and the interrupts in user mode and kernel mode that happen from the time write() is called until it returns.

a) Program calls write(fd, buffer, nbytes).
b) Write wrapper in libc generates a software interrupt for system call.
c) OS checks in interrupt handler the arguments (fd is valid file descriptor and is opened in write mode, [buffer, buffer + nbytes – 1] is valid memory address. If error found, return -1 and set errno.
d) OS tells device to write to fd.
e) OS puts current process in wait state until disk operation is finished. OS switches to other processes.
f) When disk is done, it generates an interrupt.
g) Interrupt handler puts current process in ready state and the process will be scheduled by the OS.

9. Write a shell script that will run forever and it will check every minute if a file has been modified and it will send e-mail to the user running the script when it has been modified with the changes made using "diff".

#!/bin/bash
if [ ! -e $1 ]; then
    echo "File does not exist"
    exit
fi cp $1 $1.last

while [ 1 ]; do
    sleep 60
    diff $1 $1.last > $1.tmp
    if [ -s $1.tmp ]; then
        /usr/bin/mailx -s "File changed" $USER < $1.tmp
        echo "Message sent"
    fi
    cp $1 $1.last
done

10. Write a program "grepsort arg1 arg2 arg3" that implements the command "grep arg1 | sort < arg2 >> arg3". The program should not return until the command finishes. "arg1", "arg2", and "arg3" are passed as arguments to the program. Example of the usage is "grepsort hello infile outfile". This command will print the entries in file infile that contain the string hello and will append the output sorted to file outfile. Do error checking. Notice that the output is appended to arg3.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <wait.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

const char *usage = "Usage:\tgrepsort arg1 arg2 arg3\n\tgrep arg1 | sort < arg2 >> arg3\n";
int main(int argc, char **argv)
{
            if (argc != 4)
            {
                        fprintf(stderr, "%s\n", usage);
                        exit(1);
            }

            int defaultin = dup(STDIN_FILENO);
            int defaultout = dup(STDOUT_FILENO);
            int pipefd[2];

            if (pipe(pipefd) == -1)
            {
                        perror("pipe");
                        exit(1);
            }

            int infd = open(argv[2], O_RDONLY);
            if (infd < 0)
            {
                        perror("open in");
                        exit(1);
            }

            dup2(infd, STDIN_FILENO);
            close(infd);

            dup2(pipefd[1], STDOUT_FILENO);
            close(pipefd[1]);

            int ret = fork();
            //child
            if (ret == 0)
            {
                        close(pipefd[0]);

                        char *args[3];
                        args[0] = "grep";
                        args[1] = argv[1];
                        args[2] = NULL;

                        execvp(args[0], args);
                        perror("execvp");
                        _exit(1);
            }
            else if (ret < 0)
            {
                        perror("fork");
                        exit(1);
            }

            int outfd = open(argv[3], O_WRONLY | O_APPEND | O_CREAT, 0666);
            if (outfd < 0)
            {
                        perror("open out");
                        exit(1);
            }

            dup2(outfd, STDOUT_FILENO);
            close(outfd);

            dup2(pipefd[0], STDIN_FILENO);
            close(pipefd[0]);

            ret = fork();
            if (ret == 0)
            {
                        close(pipefd[1]);

                        char *args[2];
                        args[0] = "sort";
                        args[1] = NULL;

                        execvp(args[0], args);
                        perror("execvp");
                        _exit(1);
            }
            else if (ret < 0)
            {
                        perror("fork");
                        exit(1);
            }

            dup2(defaultin, STDIN_FILENO);
            dup2(defaultout, STDOUT_FILENO);
            close(defaultin);
            close(defaultout);

            waitpid(ret, 0, 0);

            return 0;
}

11. Using C++ and Semaphores write a class SynchronizedStackSemaphores of int values where pop() will block if the stack is empty and push will block if the stack is full. Write the member variables that you think are necessary. Implement the stack with an array of int's and allocate it dynamically in the constructor. Hint: Use the "Bounded Buffer Problem" with semaphores as an example in your implementation.

#include <synch.h>
#include <pthread.h>

class SynchronizedStackSemaphores {
    // Add your member variables here
    int top;
    int * stack;
    sema_t emptySem, fullSem;
    pthread_mutex_t lock;
    public:
        SynchronizedStackSemaphores(int maxStackSize);
        void push(int val);
        int pop();
};

SynchronizedStackSemaphores::SynchronizedStackSemaphores(int maxStackSize) {
        top = 0;
        stack = new int[maxStackSize];
        sema_init(&emptySem, 0, USYNC_THREAD, NULL);
        sema_init(&fullSem, maxStackSize, USYNC_THREAD, NULL);
        pthread_mutex_init(&lock, NULL);
}

void SynchronizedStackSemaphores::push(int val) {
        sema_wait(&fullSem);
        pthread_mutex_lock(&lock);
        stack[top] = val;
        top++;
        pthread_mutex_unlock(&lock);
        sema_post(&emptySem);
}

int SynchronizedStackSemaphores::pop(){
        sema_wait(&emptySem);
        pthread_mutex_lock(&lock);
        int retval = stack[top-1];
        top--;
        pthread_mutex_unlock(&lock);
        sema_post(&fullSem);
        return retval;
}