Figure 1

For example: we have a program as the following

public class foo {

    static private int yv = 0;
    static private int nv = 0;

    public static void main() {
	foo foo_obj = new foo;
	foo_obj->cheat();
    }

    public cheat() {
	int tyv = yv;
	yv = yv + 1;
	if (tyv < 10) {
	    cheat();
	}
    }
}

The questions are:

How to map a program like this to a Von Neuman machine?

Where to keep yv, nv?

What about foo_obj and tyv?

How to do foo->cheat()?

For the variable like yv, nv, we can easily give them some space on the memory. However, why can’t we do the same for the local variable as tyv? Because while program is executing, we don’t know it will invoke the procedure cheat() how many times, it means we don’t know how much space we need to allocate for this variable. In this case, we will use stack, every time a new cheat() is called, the current tyv will be put in the stack, then we can pop it later when the program returns to this procedure. To find data allocated dynamically on stack, a stack pointer which always point at current activation record is used. We will discuss about activation record on section 2.2.

Figure 2

What about new objects? Of course, a memory location will be allocated for foo_obj. Is the stack an appropriate place to keep this object? Since this kind of object has many reusable code (all methods of class), we will waste a lot of our limited memory when we still use the stack for the new object. Heap is used in this case. Suppose we execute as the following:

Figure 3

Whenever you call a procedure there is certain information the program associates with that procedure call. The return address is a good example of some information the program maintains for a specific procedure call. Parameters and automatic local variables (i.e., those you declare in the VAR section) are additional examples of information the program maintains for each procedure call. Activation record is the term we'll use to describe the information the program associates with a specific call to a procedure.

Activation record is an appropriate name for this data structure. The program creates an activation record when calling (activating) a procedure and the data in the structure is organized in a manner identical to records. Perhaps the only thing unusual about an activation record (when comparing it to a standard record) is that the base address of the record is in the middle of the data structure, so you must access fields of the record at positive and negative offsets.

Construction of an activation record begins in the code that calls a procedure. The caller pushes the parameter data (if any) onto the stack. Then the execution of the CALL instruction pushes the return address onto the stack. At this point, construction of the activation record continues within in the procedure itself. The procedure pushes registers and other important state information and then makes room in the activation record for local variables. The procedure must also update the EBP register so that it points at the base address of the activation record.

To see what a typical activation record looks like, consider the following HLA procedure declaration:

procedure ARDemo( i:uns32; j:int32; k:dword ); nodisplay;
var
	a:int32;
	r:real32;
	c:char;
	b:boolean;
	w:word;
begin ARDemo;
	.
	.
	.
end ARDemo;

Whenever an HLA program calls this ARDemo procedure, it begins by pushing the data for the parameters onto the stack. The calling code will push the parameters onto the stack in the order they appear in the parameter list, from left to right. Therefore, the calling code first pushes the value for the i parameter, then it pushes the value for the j parameter, and it finally pushes the data for the k parameter. After pushing the parameters, the program calls the ARDemo procedure. Immediately upon entry into the ARDemo procedure, the stack contains these four items arranged as shown in Figure 3.1

Figure 4

Figure 3.1 Stack Organization Immediately Upon Entry into ARDemo

The first few instructions in ARDemo (note that it does not have the @NOFRAME option) will push the current value of EBP onto the stack and then copy the value of ESP into EBP. Next, the code drops the stack pointer down in memory to make room for the local variables. This produces the stack organization shown in Figure 3.2

Figure 5

Figure 3.2 Activation Record for ARDemo

To access objects in the activation record you must use offsets from the EBP register to the desired object. The two items of immediate interest to you are the parameters and the local variables. You can access the parameters at positive offsets from the EBP register, you can access the local variables at negative offsets from the EBP register as Figure 3.3 shows:

Figure 6

Figure 3.3 Offsets of Objects in the ARDemo Activation Record

Intel specifically reserves the EBP (extended base pointer) for use as a pointer to the base of the activation record. This is why you should never use the EBP register for general calculations. If you arbitrarily change the value in the EBP register you will lose access to the current procedure's parameters and local variables.

Implementations differ, but in general a PCB will include, directly or indirectly:

the Program Counter value for the process

During a context switch, the running process is stopped and another process is given a chance to run. The kernel must stop the execution of the running process, copy out the values in hardware registers to its PCB, and update the hardware registers with the values from the PCB of the new process.

Since the PCB contains the critical information for the process, it must be kept in an area of memory protected from normal user access. In some operating systems the PCB is placed in the beginning of the kernel stack of the process since that is a convenient protected location.

Preemptive: user thread executing ® clock interrupt ® PC modified by hardware to “vector” to interrupt handler ® user thread state is saved for restart ® clock interrupt handler is invoked ® disable interrupt checking ® check whether current thread has run “long enough” ® if yes, post asynchronous software trap (AST) ® enable interrupt checking ® exit interrupt handler ® enter “return-to-user” code ® check whether AST was posted ® if not, restore user thread state and return to executing user thread; if AST was posted, call context switch code

Non-preemptive: user thread executing ® system call to perform I/O ® user thread state is saved for restart ® OS code to perform system call is invoked ® I/O operation started (by invoking I/O driver) ® set thread status to waiting ® move thread’s TCB from run queue to wait queue associated with specific device ® call context switching code

Intel 80386 and higher CPUs contain hardware support for context switches. However, most modern operating systems perform software context switching, which can be used on any CPU, rather than hardware context switching in an attempt to obtain improved performance. Software context switching was first implemented in Linux for Intel-compatible processors with the 2.4 kernel.

One major advantage claimed for software context switching is that, whereas the hardware mechanism saves almost all of the CPU state, software can be more selective and save only that portion that actually needs to be saved and reloaded. However, there is some question as to how important this really is in increasing the efficiency of context switching. Its advocates also claim that software context switching allows for the possibility of improving the switching code, thereby further enhancing efficiency, and that it permits better control over the validity of the data that is being loaded.

Context switching is generally computationally intensive. That is, it requires considerable processor time, which can be on the order of nanoseconds for each of the tens or hundreds of switches per second. Thus, context switching represents a substantial cost to the system in terms of CPU time and can, in fact, be the most costly operation on an operating system.

Consequently, a major focus in the design of operating systems has been to avoid unnecessary context switching to the extent possible. However, this has not been easy to accomplish in practice. In fact, although the cost of context switching has been declining when measured in terms of the absolute amount of CPU time consumed, this appears to be due mainly to increases in CPU clock speeds rather than to improvements in the efficiency of context switching itself.

One of the many advantages claimed for Linux as compared with other operating systems, including some other Unix-like systems, is its extremely low cost of context switching and mode switching.

In a modern operating system, each user process runs in its own address space, and the kernel operates in its protected space. At the processor level (machine code level), the main distinction between the kernel and a user process is the ability to access certain resources such as executing privileged instructions, reading or writing special registers, and accessing certain memory locations.

The separation of user process from user process insures that each process will not disturb each other. The separation of user processes from the kernel insures that user processes will not be able to arbitrarily modify the kernel or jump into its code. It is important that processes cannot read the kernel's memory, and that it cannot directly call any function in the kernel. Allowing such operations to occur would invalidate any protection that the kernel wants to provide.

Operating systems provide a mechanism for selectively calling certain functions in the kernel. These select functions are called kernel calls or system calls, and act as gateways into the kernel. These gateways are carefully designed to provide safe functionality. They carefully check their parameters and understand how to move data from a user process into the kernel and back again. We will discuss this topic in more detail in the Memory Management section of the course.

The only way to enter the operating kernel is to generate a processor interrupt. Note the emphasis on the word "only". These interrupts come from several sources:

The flow of control is as follows (and illustrated below):

Note that one side effect of an interrupt might be to terminate the currently running process. In this case, of course, the current process will never be chosen to run next!

Figure 8

One of the most important uses of interrupts, and one of the least obvious when you first study about operating systems, is the system call. In your program, you might request a UNIX system to read some data from a file with a call that looks like:

rv = read(0,buff,sizeof(buff));

Somewhere, deep down in the operating system kernel, is a function that implements this read operation. For example, in Linux, the routine is called sys_read().

The path from the simple read() function call in your program to the sys_read() routine in the kernel takes you through some interesting and crucial magic. The path goes from your code to a system call stub function that contains a trap or interrupts instruction, to an interrupt handler in the kernel, to the actual kernel function. The return path is similar, with the addition of some important interactions with the process dispatcher.

Figure 9

The system call stub functions provide a high-level language interface to a function whose main job is to generate the software interrupt (trap) needed to get the kernel's attention. These functions are often called wrappers.

The stub functions on most operating systems do the same basic steps. While the details of implementation differ, they include the following:

(1)

set up the parameters,

(2)

trap to the kernel,

(3)

check the return value when the kernel returns, and

(4)

(a)

if no error: return immediately, else

(b)

if there is an error: set a global error number variable (called "errno") and return a value of -1.

Below are annotated examples of this code from both the Linux (x86) and Solaris (SPARC) version of the C library. As an exercise, for the Linux and Solaris versions of the code, divide the code into the parts described above and label each part.

x86 Linux read (glibc 2.1.3)

read:       push   %ebx
            mov    0x10(%esp,1),%edx           ; put the 3 parms in registers
            mov    0xc(%esp,1),%ecx
            mov    0x8(%esp,1),%ebx
            mov    $0x3,%eax                   ; 3 is the syscall # for read
            int    $0x80                       ; trap to kernel
            pop    %ebx
            cmp    $0xfffff001,%eax            ; check return value
            jae    read_err
read_ret:   ret                                ; return if OK.
read_err:   push   %ebx
            call   read_next                   ; push PC on stack
read_next:  pop    %ebx                        ; pop PC off stack to %ebx
            xor    %edx,%edx                   ; clear %edx
            add    $0x49a9,%ebx                ; the following is a bunch of
            sub    %eax,%edx                   ; ...messy stuff that sets the
            push   %edx                        ; ...value fo the errno variable
            call   0x4000dfc0 <__errno_location>
            pop    %ecx
            pop    %ebx
            mov    %ecx,(%eax)
            or     $0xffffffff,%eax            ; set return value to -1
            jmp    read_ret                    ; return

SPARC Solaris 8

read:       st     %o0,[%sp+0x44]            ! save argument 1 (fd) on stack
read_retry: mov    3,%g1                     ! 3 is the syscall # for read
            ta     8                         ! trap to kernel
            bcc    read_ret                  ! branch if no error
            cmp    %o0,0x5b                  ! check for interrupt syscall
            be,a   read_retry                ! ... and restart if so
            ld     [%sp+0x44],%o0            ! restore 1st param (fd)
            mov    %o7,%g1                   ! save return address
            call   read_next                 ! set %o7 to PC
            sethi  %hi(0x1d800), %o5         ! the following is a bunch of
read_next:  or     %o5, 0x10, %o5            ! ...messy stuff that sets the
            add    %o5,%o7,%o5               ! ...value of the errno variable
            mov    %g1, %o7                  ! ...by calling _cerror.  also the
            ld     [%o5+0xe28],%o5           ! ...return value is set to -1
            jmp    %o5
            nop
read_ret:   retl
            nop

Below is a slightly simplified version of the Linux code that is called to handle a system call trap.

The first part of the code (starting at system_call) saves the registers of the user process and plays around with the memory management registers so that the kernel's internal data is accessible. It also finds the process table entry for this user process.

The trap instruction that caused the entry to the kernel has a parameter that specifies which system call is being invoked. The code starting at do_call checks to see if this number is in range, and then calls the function associated with this system call number. When this function returns, the return value (stored in the eax register) is saved in the place where all the other user registers are stored. As a result, when control is transferred from the kernel back to the user process, the return value will be in the right place.

After the system call is complete, it is time to return to the user process. There are two choices at this point: (1) either return directly the the user process that made the system call or (2) go through the dispatcher to select the next process to run. ret_from_sys_call

system_call:
        #
        #----Save orig_eax: system call number
        #    used to distinguish process that entered
        #    kernel via syscall from one that entered
        #    via some other interrupt
        #
        pushl %eax

        # 
        #----Save the user's registers
        # 
        pushl %es
        pushl %ds
        pushl %eax
        pushl %ebp
        pushl %edi
        pushl %esi
        pushl %edx
        pushl %ecx
        pushl %ebx

        # 
        #----Set up the memory segment registers so that the kernel's
        #    data segment can be accessed.
        # 
        movl $(__KERNEL_DS),%edx
        movl %edx,%ds
        movl %edx,%es

        # 
        #----Load pointer to task structure in EBX. The task structure
	#    resides below the 8KB per-process kernel stack.
        # 
        movl $-8192, %ebx
        andl %esp, %ebx

        # 
        #----Check to see if system call number is a valid one, then
        #    look-up the address of the kernel function that handles this
        #    system call.
        # 
do_call:
        cmpl $(NR_syscalls),%eax
        jae badsys
        call *SYMBOL_NAME(sys_call_table)(,%eax,4)

	# Put return value in EAX of saved user context
        movl %eax,EAX(%esp)

        # 
        #----If we can return directly to the user, then do so, else go to
        #    the dispatcher to select another process to run.
        # 
ret_from_sys_call:
        cli        # Block interrupts; iret effectively re-enables them
        cmpl $0,need_resched(%ebx)
        jne reschedule

        # restore user context (including data segments)
        popl %ebx
        popl %ecx
        popl %edx
        popl %esi
        popl %edi
        popl %ebp
        popl %eax
        popl %ds
        popl %es
        addl $4,%esp                   # ignore orig_eax
        iret

reschedule:
        call SYMBOL_NAME(schedule)
        jmp ret_from_sys_call

One that is independent of the rest of the universe.

There are many different ways in which a collection of independent processes might be executed on a processor:

How often are processes completely independent of the rest of the universe?

Figure 10

When discussing concurrent processes, multiprogramming is as dangerous as multiprocessing unless you have tight control over the multiprogramming. Also bear in mind that smart I/O devices are as bad as cooperating processes (they share the memory).

Why permit processes to cooperate?

Reading: Section 2.3.1 in Tanenbaum talks about similar stuff, but uses terms a little differently.

Basic assumption for cooperating process systems is that the order of some operations is irrelevant; certain operations are completely independent of certain other operations. Only a few things matter:

Figure 11

Race conditions: Suppose A=1 and A=2 are executed in parallel? Do not know what will happen; depends on which one goes fastest. What if they happen at EXACTLY the same time? Cannot tell anything without more information. Could end up with A=3!

Atomic operations: Before we can say ANYTHING about parallel processes, we must know that some operation is atomic, i.e. that it either happens in its entirety without interruption, or not at all. Cannot be interrupted in the middle. E.g. suppose that println is atomic -- what happens in println("ABC"); println("BCA") example?

In fact, if there is true concurrency, it is very hard to make a perfect atomic operation; most of the time we settle for things that only work "most" of the time.