Process Management

processes

• What is the difference between a process and a program?
• What are the text section and data section of a process? What are the other components of a process?
• What information is stored in a PCB?
• Describe the running, waiting, and ready states.
• In batch systems, process scheduling is often divided into two components: long-term scheduling and short-term scheduling. Explain.
• Describe how register sets can speed up context switching.
• What are the roles of the sched and init processes in Solaris?
• Explain how to find the pid of a particular process in Solaris.
• Describe some aspects of process creation that are OS design decisions.
• Explain fork, execlp, wait, and exit.
• Write a few lines of Java code to invoke the UNIX hostname command and display the result.
• What is the main limitation of process creation in Java?
• What happens to memory dynamically allocated by a process when it terminates?
• What is cascading termination?
• In UNIX, what happens to the child of a process that terminates?
• What is returned by the wait call?
• What happens when wait is invoked with a NULL parameter?
• What output will the following code generate?

int main()
{
   int x = 0;
   pid_t pid = fork();
   if (pid == 0)
      x++;
   else {
     wait(NULL);
     printf("%d", x);
   }
   printf("%d", x);
}

• What output will be generated by lines C and P? What if line N is commented out?

  int value = 0; 
  
  void* f(void* param); 
  
  int main(int argc, char* argv[]) 
  { 
     int pid = fork(); 
     if (pid == 0) { 
        pthread_t tid; 
        pthread_create(&tid, NULL, f, NULL); 
        pthread_join(tid, NULL);                // line N 
        printf("CHILD: value = %d\n", value);   // line C 
     } 
     else { 
        wait(NULL); 
        printf("PARENT: value = %d\n", value);  // line P 
     } 
  }
  
  void* f(void* param) 
  { 
    value = 5; 
    pthread_exit(0); 
  } 
  

• Fill in the missing details so that the program creates ten threads, passing a unique integer to each. Each thread writes the integer that it receives to the output stream.

  #include  
  #include  
  #include  
  #define NUM_THREADS 10; 
  
  void* f(void* id); 
  
  int main(int argc, char *argv[]) 
  { 
    pthread_t threads[NUM_THREADS]; 
    for( int t = 0; t < NUM_THREADS; t++) 
       // MISSING (create the threads) 
       
    // MISSING (keep process alive until all threads terminate) 
  } 
  
  void* f(void* param) 
  { 
     // MISSING 
     printf("My number is %d!\n", n); 
  } 
  

interprocess communication

• Describe the two main models of IPC and discuss their relative merits?
• Explain direct and indirect communication in the message passing model.
• Describe a problem that complicates direct communication?
• Message passing may be blocking or non-blocking. Explain.
• What does it mean for two processes to rendezvous.
• What is a socket? How is a socket identified?
• What is one diffulty in using sockets compared to RPCs or RMI?
• Write a few lines of Java to create a server socket, listen for a connection, and send the current date to each client.
• Write the client code for the previous problem.
• What is the role of a rendezvous daemon in an RPC system?
• Name some technical difficulties in implementing an RPC system.
• What is Remote Method Invocation? What does “remote” mean in this context?

threads

• What components of program state are shared across threads in a process?
• What data or data structures are associated with each individual thread in a process?
• Describe the actions taken by the thread library to context switch between user-level threads.
• Why might it be desirable for a web server to create a thread to handle a client request instead of a separate process?
• What is deferred cancellation?
• What is a signal in UNIX? How is it different from an interrupt?
• Explain the difference between synchronous and asynchronous signals. Give an example of each.
• Describe the arguments to pthread_create.
• What does pthread_join do?
• Describe two potential problems of the many-to-one thread model.
• What is the drawback of the one-to-one model?
• Describe the many-to-many model. What are its advantages compared to many-to-one and one-to-one? Explain any liabilities.

cpu scheduling

• What is the difference between preemptive and non-preemptive scheduling?
• What does the dispatcher do? What is the dispatch latency?
• List and define the five major scheduling criteria.
• Describe how the goals of optimizing both CPU utilization and response time might be mutually exlusive. Do the same for average turnaround time versus maximum waiting time.
• Using the following table, what are the turnaround times for FCFS, SJF, nonpreemptive priority, and RR? Assume that a smaller priority number indicates a higher priority.

  process	burst length	priority
  A	10	3
  B	1	1
  C	2	3
  D	1	4
  E	5	2

• Continuing the previous question, what are the waiting times of each process using the same five algorithms? Which algorithm mimimizes the average waiting time?
• What is the general justification for giving higher priority to I/O-bound processes than to those that are CPU intensive?
• FCFS favors CPU-bound processes. Explain.
• Give an example of CPU burst lengths for three or more processes to show that the average waiting time for FCFS is sensitive to the order in which the processes arrive.
• How does SJF work? n what sense is it provably optimal? Why is it impossible to implement?
• Contrast preemptive and non-preemptive SJF.
• Give an example of CPU burst lengths for three or more processes in which the average waiting time using preemptive SJF differs from that of non-preemptive SJF.
• Write a recurrence relation that defines the exponential average of the predicted and actual lengths of previous CPU bursts. Use the following notation:
  • s_n — the prediction for the n-th burst
  • t_n — the measured length of the n-th burst
  • α — the relative weight parameter.
  Describe the recurrence for the special cases when α = 0 and α = 1.
• Let α = 1/3. Then what is s₂, assuming s₀ = 2, t₀ = 3 and t₁ = 3?
• Describe the typical problem with priority scheduling. How is it typically handled?
• Describe round-robin scheduling. Under what condition is it basically the same as FCFS?
• A typical quantum for RR is between 10 and 100 milliseconds. Why not smaller?
• For which of the five scheduling criteria is RR especially suitable?
• Consider a system running ten I/O-bound processes and one CPU-bound process. Assume that the I/O-bound processes issue an I/O operation once for every millisecond of CPU computing, and that each I/O operation takes 10 milliseconds to complete. The context-switching overhead is a tenth of a millisecond. Suppose that all of the processes will run for a long time. What is the CPU utilization for a RR scheduler when the time quantum is 1 millisecond? What about 10 milliseconds?
• What is a multi-level feedback queue. What classes of processes are favored by this algorithm?
• What is processor affinity? What effect does it have on scheduling?
• In a multiprocessor system, what problem can arise when each CPU has its own queue of ready processes?
• Describe push migration and pull migration. What is the impact of load balancing on process migration? How do some systems deal with this?
• What is symmetric multithreading (hyperthreading)? Give an example of a scenario in which the operating system can improve performance by distinguishing physical from logical processors.
• What is the difference between local and global scheduling?
• What can you say about the JVM specification as it pertains to thread scheduling?
• How many Java thread priorities are there? What about Win32 or Solaris?
• Give an argument for allowing the JVM to ignore calls to setPriority.

process synchronization

• Suppose that two processes access an integer x. One process increments x and the other process decrements it. Explain why the concurrent execution of these processes creates a race condition.
• Describe the three conditions that must be satisfied by a solution to the critical-section problem.
• Describe Peterson's solution to the critical-section problem. Write out the entry and exit sections and explain how mutual exclusion, progress, and bounded waiting are achieved.
• What is a semaphore? How do counting and binary semaphores differ? Describe an application of counting semaphores for which binary semaphores could not be used.
• The acquire and release code of a semaphore cannot be interleaved, so how is access to the semaphore value synchronized in a single-processor environment?
• What is a spinlock? When are spinlocks appropriate?
• How can the basic concept of a semaphore be modified to overcome the problem associated with spinlocks? What would a semaphore value of -5 indicate in this case?
• Explain why implementing synchronization primitives by disabling interrupts is not appropriate in a single-processor system if the synchronization primitives are to be used in user-level programs.
• How are monitors different from semaphores?

The following block of questions deal with synchronizing threads in Java.

• What does it mean to declare a Java method as synchronized?
• Every Java object has a built in lock. How is this lock acquired?
• Can static methods be synchronized? Explain.
• We would not want to synchronize a long method in which the shared data was accessed only in a line or two of code. What feature of Java helps with this problem? Demonstrate the syntax.
• Consider a multithreaded stack using synchronized push and pop methods. If the stack is full, the producer can avoid busy waiting by calling Thread.yield(). What problem arises here?
• Where are wait, notify, and notifyAll defined? Explain what these methods do.
• Name a class that implements the Lock interface.
• Write code that creates a lock, obtains a condition object, and causes the current thread to wait on this condition until it is signalled. What method is used to wake up a thread waiting on a particular condition?
• Show how to use a ReentrantLock object to achieve the same effect as declaring a method to be synchronized.

deadlock

• Discuss the difference between deadlock avoidance and deadlock prevention.
• Describe a simple scheme to ensure that the hold-and-wait condition never occurs. Are there any practical drawbacks?
• Describe a simple scheme to prevent circular waiting.
• What is a safe sequence?
• What is the connection between cycles in the resource-allocation graph and deadlock? Answer for the case in which there is a single instance of each resource type and also in the more general case of multiple instances.
• Draw a resource-allocation graph in which there is a cycle and yet the system is not deadlocked. Use rectangles for resource nodes and circles for process nodes.
• For a given resource allocation state, decide if the system is in a safe state. For this you just need to know how to detect deadlock. Consider especially the case where there are multiple instances of resource types.
• Is a system in an unsafe state necessarily deadlocked?
• Describe how to use a resource-allocation graph to avoid deadlock in the case where there is only one instance of each resource type (this was called the resource-allocation-graph algorithm in the book). In particular, what are claim edges, how is the graph modified when a resource is requested, what property of the graph indicates that the request is unsafe, and what happens when a resource is released?
• Suppose that you have an algorithm that can detect deadlock. Explain in a single sentence how to use this algorithm to avoid deadlock (even if there are multiple instances of a resource type).
• Consider the dining-philosophers problem where the chopsticks are placed at the center of the table and any two of them could be used by a philosopher. Assume that requests for chopsticks are made one at a time. Describe a simple rule for determining whether a particular request could be satisfied without causing deadlock given the current allocation of chopsticks to philosophers.