Process and Threads Operating Systems Assignments

Chapter: 3

3.1 Using the program shown in Figure 3.30, explain what the output will be at LINE A

#include <sys/types.h>

#include <stdio.h>

#include <unistd.h>

int value = 5;

int main()

{

pid t pid;

pid = fork();

if (pid == 0) { /* child process */

value += 15;

return 0;

}

else if (pid > 0) { /* parent process */

wait(NULL);

printf("PARENT: value = %d",value); /* LINE A */

return 0;

}

}

Ans:  PARENT: value = 5

3.8 Describe the differences among short-term, medium-term, and longterm scheduling

Ans:

•  Short-term (CPU scheduler): selects a process from those that are in memory and ready to execute, and and allocates the CPU to it.
• Medium-term (memory manager): selects processes from the ready or blocked queue and removes them from memory, then reinstates them later to continue running.
• Long-term (job scheduler): selects processes from this pool and loads them into memory for execution.

A primary difference is in the frequency of their execution. The short-term scheduler must select a new process quite often. Long-term is used much less often since it handles placing jobs in the system and may wait a while for a job to finish before it admits another one.

3.9 Describe the actions taken by a kernel to context-switch between processes.

Ans:

The kernel saves the context of the old process in its PCB and loads the saved context of the new process scheduled to run. Context-switch time is pure overhead, because the system does no useful work while switching. Switching speed varies from machine to machine, depending on the memory speed, the number of registers that must be copied, and the existence of special instructions (such as a single instruction to load or store all registers). A typical speed is a few milliseconds

3.12 Including the initial parent process, how many processes are created by the program shown in Figure 3.32?

#include <stdio.h>

#include <unistd.h>

int main()

{

int i;

for (i = 0; i < 4; i++)

fork();

return 0;

}

Figure 3.32 How many processes are created?

Ans: 16

3.14 Using the program in Figure 3.34, identify the values of pid at lines A, B, C, and D. (Assume that the actual pids of the parent and child are 2600 and 2603, respectively.)

#include <sys/types.h>

#include <stdio.h>

#include <unistd.h>

int main()

{

pid t pid, pid1;

/* fork a child process */

pid = fork();

if (pid < 0) { /* error occurred */

fprintf(stderr, "Fork Failed");

return 1;

}

else if (pid == 0) { /* child process */

pid1 = getpid();

printf("child: pid = %d",pid); /* A */

printf("child: pid1 = %d",pid1); /* B */

}

else { /* parent process */

pid1 = getpid();

printf("parent: pid = %d",pid); /* C */

printf("parent: pid1 = %d",pid1); /* D */

wait(NULL);

}

return 0;

}

Figure 3.34 What are the pid values?

Ans:

Pid values A = 0, B = 2603, C = 2603, D = 2600

Chapter: 4

4.4 What resources are used when a thread is created? How do they differ from those used when a process is created?

Ans:

Thread creation typically uses fewer resources than process creation. Creating a process requires allocating a process control block (PCB), rather large data structure. The PCB includes a memory map, lost of open files, and environment variables. Allocating and managing the memory map is typically the most time consuming activity. Creating either a user or kernel thread involves allocating a small data structure to hold a register set, stack and priority.

4.12 Using Amdahl’s Law, calculate the speedup gain of an application that has a 60 percent parallel component for (a) two processing cores and (b) four processing cores

Ans:

Speedup ≤ 1/(S + (1−S)/N)

a.      Speedup = 1.428

b.      Speedup = 1.818

4.17 The program shown in Figure 4.16 uses the Pthreads API. What would be the output from the program at LINE C and LINE P?

#include <pthread.h>

#include <stdio.h>

#include <types.h>

int value = 0;

void *runner(void *param); /* the thread */

int main(int argc, char *argv[])

{

pid t pid;

pthread t tid;

pthread attr t attr;

pid = fork();

if (pid == 0) { /* child process */

pthread attr init(&attr);

pthread create(&tid,&attr,runner,NULL);

pthread join(tid,NULL);

printf("CHILD: value = %d",value); /* LINE C */

}

else if (pid > 0) { /* parent process */

wait(NULL);

printf("PARENT: value = %d",value); /* LINE P */

}

}

void *runner(void *param) {

value = 5;

pthread exit(0);

}

Figure 4.16 C program for Exercise 4.17.

Ans: CHILD: value = 5 

PARENT: value = 0

Chapter: 5

5.3  What is the meaning of the term busy waiting? What other kinds of waiting are there in an operating system? Can busy waiting be avoided altogether? Explain your answer.

Ans:

The main disadvantage of the implementation mutex is that it requires busy waiting. While a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the call to acquire(). In fact, this type of mutex lock is also called a spinlock because the process “spins” while waiting for the lock to become available. (We see the same issue with the code examples illustrating the test and set() instruction and the compare and swap() instruction.) This continual looping is clearly a problem in a real multiprogramming system, where a single CPU is shared among many processes. Busy waiting wastes CPU cycles that some other process might be able to use productively. Busy waiting can be avoided but incurs the overhead associated with putting a process to sleep and having to wake it up when the appropriate program state is reached.

5.4 Explain why spinlocks are not appropriate for single-processor systems yet are often used in multiprocessor systems.

Ans:

Spinlocks do have an advantage, however, in that no context switch is required when a process must wait on a lock, and a context switch may take considerable time. Thus, when locks are expected to be held for short times, spinlocks are useful. They are often employed on multiprocessor systems where one thread can “spin” on one processor while another thread performs its critical section on another processor.

5.7 Race conditions are possible in many computer systems. Consider a banking system that maintains an account balance with two functions: deposit(amount) and withdraw(amount). These two functions are passed the amount that is to be deposited or withdrawn from the bank account balance. Assume that a husband and wife share a bank account. Concurrently, the husband calls the withdraw() function and the wife calls deposit(). Describe how a race condition is possible and what might be done to prevent the race condition from occurring.

Ans:

A situation like this, where several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place, is called a race condition. Here in this case when husband and wife wanted to access the same bank account concurrently and when withdraw is in process, wife is depositing there may be chance of race condition which changes the order of the execution. To guard against the race condition above, we need to ensure that only one process at a time can be manipulating the variable counter. To make such a guarantee, we require that the processes be synchronized in some way.

5.15 Consider how to implement a mutex lock using an atomic hardware instruction. Assume that the following structure defining the mutex lock is available:

typedef struct {

int available;

} lock;

(available == 0) indicates that the lock is available, and a value of 1 indicates that the lock is unavailable. Using this struct, illustrate how the following functions can be implemented using the test and set() and compare and swap() instructions:

• void acquire(lock *mutex)

• void release(lock *mutex)

Be sure to include any initialization that may be necessary.

Ans:

Test and Set:

typedef struct

    {

        int available;

    }lock;

           

void init(lock *mutex)

{

// available==0 -> lock is available, available==1 -> lock unavailable

mutex->available=0;

}

int test_And_Set(int *target)

{

                        int rv = *target;

                        *target = true;

                        return rv

}

void acquire(lock *mutex)

{

        while(test_and_set(&mutex->available,1)==1)

                        ;

       

}

void release(lock *mutex)

{

        mutex->available=0;

}   

Compare and Swap:    

int compare_and_Swap(int *ptr,int expected,int new)

{

                     int actual = *ptr;

                     if(actual == expected)

                     *ptr = new;

                     return actual;

}

void acquire(lock *mutex)

{

        while(compare_and_swap(&mutex->available,0,1)==1)

                        ;

      

}

void release(lock *mutex)

{

        mutex->available=0;

}                      

5.17 Assume that a system has multiple processing cores. For each of the following scenarios, describe which is a better locking mechanism—a spinlock or a mutex lock where waiting processes sleep while waiting for the lock to become available:

• The lock is to be held for a short duration.

• The lock is to be held for a long duration.

• A thread may be put to sleep while holding the lock.

Ans:

The lock is to be held for a short duration - It makes more sense to use a spinlock as it may in fact be faster than using a mutex lock which requires suspending –and awakening - the waiting process.

The lock is to be held for a long duration - a mutex lock is preferable as this allows the other processing core to schedule another process while the locked process waits.

A thread may be put to sleep while holding the lock - a mutex lock is definitely preferable as you wouldn’t want the waiting process to be spinning while waiting for the other process to wake up.