CS703 - Advanced Operating Systems
Course Page
Q & A
Short Question & Answers
Q27: How static analysis is performed and what are its limitations?
 Static analysis is performed in the following four phases:

Pointer Analysis: First, the heap and stack state is formulated at each point of the program by doing a pointer analysis that is based on symbolic expressions. The analysis has been modified to treat the heap allocation in a context-sensitive manner. The out of first stage is a mapping for each expression to a set of abstract locations. Each abstract location may have any forms e.g. a formal parameter, a global variable or a heap-allocated location.

Effect Interference: we have a functional control flow graph in the analysis. Here a forward dataflow algorithm is run on the graph to compute the effect for each function. Nodes of the graph show input, current and output effects. The input effects are formulated from its front edges. The output effect is computed by appending the current effect to the input effect and is propagated to a node’s successors until a fixed point is reached. Output effects that have no successors are joined to computer a function’s effect.

Loops: at this phase, lock counts effects flowing from back edges must be equivalent to the input effect of the same node. Due to this bound, we can efficiently encode loop effects: from the entrance to exit the counts of each lock should match. We take effect of the entire loop. The empty effect on all branches compensates for the case where a loop is not executed.

Effect Optimization: function effect repetitions should be avoids. For this optimization techniques are applied. One technique is to find the common prefixes and suffixes so that the number of branches may be reduced. Another technique for removing the nested loop is to take the nested loops out. We also trigger the data flow algorithm, which is CPU-intensive, only for functions that are known to contain lock operations, to avoid additional overheads.

Limitations are as follows:

Non C code: C language can be tightly dealt with our static analysis. However, library code cannot be handled by our analysis. In our assumptions, we take the library functions’ effect as empty effects. However, we can add user-defined notes for library functions. There is another limitation with our analysis that it cannot handle non-local jumps (including signals) and inline assembly.

Pointer analysis: our analysis is not capable of handling pointers arithmetic that involves locks in it. Our analysis also fails to track heap allocation at recursive functions and loops. Another limitation is that we need that lock pointers are changed only before they are shared between threads, and that locks pointed by with at least two levels of indirection are not aliased at function calls.

Conditional Execution: if the locks and their matching unlock operation happens to be executed in separate conditional statements, and they have similar guards, in this case, our analysis will not accept the program.
q28: What is are message-oriented models?
Special types of processes communicate among each other with special paths like sockets, ports, or channels etc.
Process communication paths are static. Creating, deleting or changing connection among processes is difficult.
Processes work in their separate spaces and rarely access the shared data

Message-oriented models bear the following characteristics:
1. Process synchronization is made possible through queues that are attached with processes
2. When more than one processes operate on data, the data structure are passed by reference
3. Peripheral devices are also work like messages. Signal is sent to devices and an interrupt is generated by devices in response
4. Priorities for process are set statically at the time of system design
5. Mostly one process is served at a time and served completely before looking into the queue for next process

Messages-oriented models provide the following facilities:
1. It carries a handle for identifying a message, and message data portion
2. Messages communication is established through channels and ports.
3. Messages are sent and received through operations like SendMessage, AwaitReply, WaitForMessage, and SendReply etc.
Course Instructor

Mr. Farhan Zaidi
MS Computer Science
University of Southern California, USA

Modern Operating Systems by Tanenbaum

Operating Systems Internals and Design Principles by William Stallings

Operating Systems by Gary Nutt

Computer Systems: A programmer’s perspective
by Randal E. Bryant & David R.