Independent and Cooperating Processes

Chapter 6 in Operating Systems Concepts.
Independent process: one that is independent of the rest of the universe.
• Its state is not shared in any way by any other process.
• Deterministic: input state alone determines results.
• Reproducible.
• Can stop and restart with no bad effects (only time varies).
Example: program that sums the integers from 1 to i (input).
There are many different ways in which a collection of independent processes might be executed on a processor:
• Uniprogramming: a single process is run to completion before anything else can be run on the processor.
• Multiprogramming: share one processor among several processes. If no shared state, then order of dispatching is irrelevant.
• Multiprocessing: if multiprogramming works, then it should also be ok to run processes in parallel on separate processors.
o A given process runs on only one processor at a time.
o A process may run on different processors at different times (move state, assume processors are identical).
o Cannot distinguish multiprocessing from multiprogramming on a very fine grain.
How often are processes completely independent of the rest of the universe?
________________________________________
Cooperating processes:
• Machine must model the social structures of the people that use it. People cooperate, so machine must support that cooperation. Cooperation means shared state, e.g. a single file system.
• Cooperating processes are those that share state. (May or may not actually be "cooperating")
• Behavior is nondeterministic: depends on relative execution sequence and cannot be predicted a priori.
• Behavior is irreproducible.
• Example: one process writes "ABC", another writes "CBA".


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?
• Want to share resources:
o One computer, many users.
o One file of checking account records, many tellers.
• Want to do things faster:
o Read next block while processing current one.
o Divide job into sub-jobs, execute in parallel.
• Want to construct systems in modular fashion. (e.g. tbl | eqn | troff)
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:
• Example: A = 1; B = 2; has same result as B = 2; A = 1;
• Another example: A = B+1; B = 2*B cannot be re-ordered.


Race conditions: Suppose A=1 and A=2 are executed in parallel?
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?
• References and assignments are atomic in almost all systems. A=B will always get a good value for B, will always set a good value for A (not necessarily true for arrays, records, or even floating-point numbers).
• In uniprocessor systems, anything between interrupts is atomic.
• If you do not have an atomic operation, you cannot make one. Fortunately, the hardware folks give us atomic ops.
• If you have any atomic operation, you can use it to generate higher-level constructs and make parallel programs work correctly. This is the approach we will take in this class.
________________________________________

Copyright © 2001, 2008 Barton P. Miller
Non-University of Wisconsin students and teachers are welcome to print these notes their personal use. Further reproduction requires permission of the author. 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