CSE 430  – Operating Systems – Spring 2009
Assignment: #2,

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

Because a thread is smaller than a process, thread creation typically uses fewer resources than process creation. Creating a process requires allocating a process control block (PCB), a rather large data structure. The PCB includes a memory map, list 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, rather than the entire PCB.

 

  1. Provide one programming example of multithreading that do not improve performance over a single-threaded solution.

Any kind of program involving heavy sequential operations do not benefit from multithreading. For example, a long computation steps in accounting software where each operation depends on previous operation.

  1. A CPU scheduling algorithm determines an order for the execution of its scheduled processes. Given n processes to be scheduled on one processor, how many possible different schedules are there? Give a formula in terms of n.

Factorial of n

  1. What are two differences between user-level threads and kernel-level threads? Under what circumstances is one type better than the other?

Differences between user-level threads and kernel-level threads (Any two):

1)      Operating system has the knowledge of existence of kernel level threads while it does not know about the existence of user-level threads.

2)      Suppose a process P1 has 2 kernel level threads and P2 has 2 user-level threads. If one thread in P1 gets blocked, its second thread is not affected. But in case of P2 if one thread is blocked (say for I/O), the whole process P2 along with the 2nd thread gets blocked.

3)      Kernel level threads are slower to create compared to user-level threads.

4)      Switching in Kernel level thread involves OS scheduler while in user-level threads OS scheduler is not involved.

5)      Context switching between kernel level threads has high overhead, almost the same as a process. Context switching between user-level threads has almost no overhead as compared to kernel level threads.

6)      Kernel level threads can run on different processors simultaneously while user-level threads of a process will run on one processor only even if multiple processors are available.

  1. Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:

 Process

Burst Time

Priority

P1

10

3

P2

1

1

P3

2

3

P4

1

4

P5

5

2

 The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.

a.       Draw four Gantt charts illustrating the execution of these processes using FCFS, SJF, a nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1) scheduling.

b.      What is the waiting time of each process for each of the scheduling algorithms in part a?

 

 

FCFS:

 

SJF:

 

PRIORITY:

RR:

                Waiting Time     

       

  1. Prove that, in the Lamport Bakery algorithm, the following property holds: if Pi is in its critical section and Pk (k!=i) has already chosen its number[k] != 0, then (number[i], i) < (number[k], k).

There are two cases here. In case 1, a process k already executed line 2. if (num[i],i) < (num[k],k), then a process i will enter critical section, and process k will be unable to, so while process i is in the critical section, the hypothesis will hold. If (num[i],i) >= (num[k],k), the process i will wait until process k has exited the critical section before entering, since process k has exited the critical section by the time process i is in it, the criterion of process k having already chosen its number[k]!=0 will be false, and we’ll have to wait for it to come around again and choose a number in order to check the validity of hypothesis, but it comes back around, it will be the same as case 2. In case 2, process k executes line 2, it will choose a number greater than number[i], so the hypothetical condition (num[i],i) < (num[k],k) will hold as process i execute the critical section.

  1. Explain why spinlocks are not appropriate for uni-processor systems yet may be suitable for multi-processor systems. (multiprocessor and multicore is the same thing).

Spinlock is not appropriate for uniprocessor because it simply wastes CPU cycles while it spins for some resource (lock) to get free. The process in critical section will not release the resource unless it has CPU service. On the other hand, in multiprocessor, if one processor is spinning and waiting, the other processor can still have a chance to do the work in critical section. Thus the spinning continues for a short time only instead of wasting the whole time quanta.

 

  1. Show that, if the wait (or P) and signal (or V)operations on semaphores are not executed atomically, then mutual exclusion may be violated.

If two processes execute wait(S) at the same time, only one will enter, and the other one wait till signal is raised. If wait is not executed automatically, then there is a chance that both processes read the same value of S into a register, and then both processes see the same value and enter the critical section simultaneously. Similarly, same reason for signal.