Processes
Abhijit A M
[Link]@[Link]
Processes – what we have already learnt
●
A program in execution
●
Consumes CPU time, instructions run on CPU
●
Occupies space in RAM
– Code, global variables (data), local variables &
Parameters (stack), heap, shared libraries, etc.
Processes – what we have already learnt
●
Most typically created using fork() and exec()
– fork() creates a duplicate process, identical with
caller process
●
Returns twice, in parent and in child
– exec() superimposes the specified executable on
the currently running process
●
Does not return
Processes – what we have already learnt
●
Multiprogramming and multitasking
●
Timer interrupt
●
Scheduler: a part of operating system
– Code invoked on timer interrupt
– Selects the next process to execute and passes
control over to it
Processes – what we have already learnt
●
Inter process communication using pipe()
– A lecture with demonstration during laboratory session
– Pipe() system call creates an operating system data structure, which
acts as a FIFO, a queue, with two ends – a write end and a read end,
both ends available as file descriptors
– After fork() pipe’s buffer is shared between parent and child , the Fds
get inherited
●
Hence one can write into it and another can read from it
– Concept of how the shell connects two processes using a pipe
Other Important concepts that we have
covered
●
Calling convention
– The convention documented for each processor
– To make function calls work properly
– Ensure that parameters are passed corrected, return value
is returned, often using the “stack” and/or the registers
– Rules for the compiler to generate additional code in the
caller function and called(callee) function
–
Other Important concepts that we have
covered
●
C Compiler
– Converts C code to machine code
●
Linker
– Links various object code files together, essentially connecting calls of functions to the
codes of function
– Stack and Dynamic Linking
●
Loader
– Basically code of exec(), inside OS
– Loads the executable file from Disk into OS memory
– Static and Dynamic Loading
Memory layout of a C program
$ size /bin/ls
text data bss dec hex filename
128069 4688 4824 137581 2196d /bin/ls
Memory layout of a C program
●
Compiler assumes that the program will be
located “like this” in the RAM when the program
starts executed (after exec()!)
●
Hence compiler is able to generate machine
code, assuming certain addresses for variables
and code in stack, heap, data, code areas
●
PCB
– A record representing a
process in operating system’s
data structures
– OS maintains a “list”of PCBs,
one for each process
– Called “struct task_struct” in
Linux kernel code and “struct
proc” in xv6 code
●
Fields in PCB
– We have already discussed
the array of file descriptors
– Process ID (PID)
– Program counter
– Registers
– Memory limits of the process
– Accounting information
– I/O status
– Scheduling information
– Process State
– ...etc
Process Queues/Lists inside OS
●
Different types of queues/lists can be maintained by
OS for the processes
– A queue of processes which need to be scheduled
– A queue of processes which have requested input/output
to a device and hence need to be put on hold/wait
●
List of processes currently running on multiple CPUs
// XV6 Code : Per-process state
struct proc {
uint sz; // Size of process memory (bytes)
pde_t* pgdir; // Page table
char *kstack; // Bottom of kernel stack for this process
enum procstate state; // Process state
int pid; // Process ID
struct proc *parent; // Parent process
struct trapframe *tf; // Trap frame for current syscall
struct context *context; // swtch() here to run process
void *chan; // If non-zero, sleeping on chan
int killed; // If non-zero, have been killed
struct file *ofile[NOFILE]; // Open files
struct inode *cwd; // Current directory
char name[16]; // Process name (debugging)
};
enum procstate { UNUSED, EMBRYO, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };
struct {
struct spinlock lock;
struct proc proc[NPROC];
} ptable;
// Linux data structure
struct task_struct {
long state;/*state of the process */
struct sched entity se; /* scheduling information */
struct task struct *parent; /*this process’s parent */
struct list head children; /*this process’s children */
struct files struct *files; /* list of open files */
struct mm struct *mm;/*address space */
Context Switch
●
Context
– Execution context of a process
– CPU registers, process state, memory management information, all
configurations of the CPU that are specific to execution of a process/kernel
●
Context Switch
– Change the context from one process/OS to OS/another process
– Need to save the old context and load new context
– Where to save? --> PCB of the process
Context Switch
●
Is an overhead
●
No useful work happenin while doing a context
switch
●
Time can vary from hardware to hardware
●
Special instructions may be available to save a
set of registers in one go
●
Pecularity of context switch
●
When a process is running, the function calls work in LIFO fashion
– Made possible due to calling convention
●
When an interrupt occurs
– It can occur anytime
– Context switch can happen in the middle of execution of any function
●
After context switch
– One process takes place of another
– This “switch” is obviously not going to happen using calling convention, as no “call” is
happening
– Code for context switch must be in assembly!
“Giving up” CPU by a processOS Syscall
sys_read(int fd, char *buf, int len) {
int main() {
file f = current->fdarray[fd];
i = j + k;
int offset = f->position;
scanf("%d", &k); ...
} disk_read(..., offset, ...);
int scanf(char *x, ...) { // Do what now?
//asynchronous read
...
//Interrupt will occur when the disk read is complete
read(0, ..., ...); // Mov the process to a wait queue and call scheduler!
} // code to move the current PCB from one queue to another
queue
int read(int fd, char *buf, int len) {
// This is called "blocking"
... }
__asm__ { "int 0x80..."} disk_read(...., offset, .... ) {
... __asm__("outb PORT ..");
return;
}
}
XV6 code overview
1. Understanding how traps are handled
2. How timer interrupt goes to scheduler
3. How scheduling takes place
4. How a “blocking” system call (e.g. read())
“blocks”
Handling Traps
Handling traps
Transition from user mode to kernel mode
On a system call
On a hardware interrupt
User program doing illegal work (exception)
Actions needed, particularly w.r.t. to hardware interrupts
Change to kernel mode & switch to kernel stack
Kernel to work with devices, if needed
Kernel to understand interface of device
Handling traps
Actions needed on a trap
Save the processor’s registers (context) for future use
Set up the system to run kernel code (kernel context) on kernel
stack
Start kernel in appropriate place (sys call, intr handler, etc)
Kernel to get all info related to event (which block I/O done?,
which sys call called, which process did exception and what
type, get arguments to system call, etc)
Privilege level
The x86 has 4 protection levels, numbered 0 (most
privilege) to 3 (least privilege).
In practice, most operating systems use only 2 levels: 0
and 3, which are then called kernel mode and user mode,
respectively.
The current privilege level with which the x86 executes
instructions is stored in %cs register, in the field CPL.
Privilege level
Changes automatically on
“int” instruction
hardware interrupt
exeception
Changes back on
iret
“int” 10 --> makes 10th hardware interrupt. S/w interrupt can be used
to create hardware interrupt’
Xv6 uses “int 64” for actual system calls
Interrupt Descriptor Table (IDT)
IDT defines intertupt handlers
Has 256 entries
each giving the %cs and %eip to be used when handling the
corresponding interrupt.
Interrupts 0-31 are defined for software exceptions, like divide
errors or attempts to access invalid memory addresses.
Xv6 maps the 32 hardware interrupts to the range 32-63
and uses interrupt 64 as the system call interrupt
Interrupt Descriptor Table (IDT) entries
// Gate descriptors for interrupts and traps
struct gatedesc {
uint off_15_0 : 16; // low 16 bits of offset in segment
uint cs : 16; // code segment selector
uint args : 5; // # args, 0 for interrupt/trap gates
uint rsv1 : 3; // reserved(should be zero I guess)
uint type : 4; // type(STS_{IG32,TG32})
uint s : 1; // must be 0 (system)
uint dpl : 2; // descriptor(meaning new) privilege
level
uint p : 1; // Present
uint off_31_16 : 16; // high bits of offset in segment
};
Setting IDT entries
void
tvinit(void)
{
int i;
for(i = 0; i < 256; i++)
SETGATE(idt[i], 0, SEG_KCODE<<3, vectors[i], 0);
SETGATE(idt[T_SYSCALL], 1, SEG_KCODE<<3,
vectors[T_SYSCALL], DPL_USER);
/* value 1 in second argument --> don't disable interrupts
* DPL_USER means that processes can raise this
interrupt. */
initlock(&tickslock, "time");
}
Setting IDT entries
#define SETGATE(gate, istrap, sel, off, d) \
{ \
(gate).off_15_0 = (uint)(off) & 0xffff; \
(gate).cs = (sel); \
(gate).args = 0; \
(gate).rsv1 = 0; \
(gate).type = (istrap) ? STS_TG32 : STS_IG32; \
(gate).s = 0; \
(gate).dpl = (d); \
(gate).p = 1; \
(gate).off_31_16 = (uint)(off) >> 16; \
}
Setting IDT entries
Vectors.S trapasm.S
# generated by [Link] - do not #include "mmu.h"
edit
# vectors.S sends all traps here.
# handlers
.globl alltraps .globl alltraps
.globl vector0 alltraps:
vector0: # Build trap frame.
pushl $0 pushl %ds
pushl $0 pushl %es
jmp alltraps pushl %fs
.globl vector1 pushl %gs
vector1: Pushal
pushl $0
....
pushl $1
jmp alltraps
How will interrupts be handled?
On int instruction/interrupt
the CPU does this:
Fetch the n’th descriptor from the IDT,
Push %ss. // optional
where n is the argument of int.
Push %esp. // optional (also
Check that CPL in %cs is <= DPL, changes ss,esp using TSS)
where DPL is the privilege level in the
descriptor.
Push %eflags.
Save %esp and %ss in CPU-internal
Push %cs.
registers, but only if the target
segment selector’s PL < CPL.
Push %eip.
Switching from user mode to kernel
Clear the IF bit in %eflags, but only
mode. Hence save user code’s SS and on an interrupt.
ESP
Load %ss and %esp from a task
Set %cs and %eip to the values in
segment descriptor. the descriptor.
Stack changes to kernel stack now. TS
descriptor is on GDT, index given by TR
register. See switchuvm()
After “int” ‘s job is done
IDT was already set
Remember vectors.S
So jump to 64th entry in vector’s
vector64:
pushl $0
pushl $64
jmp alltraps
So now stack has ss, esp,eflags, cs, eip, 0 (for error code), 64
Next run alltraps from trapasm.S
# Build trap frame.
pushl %ds alltraps:
pushl %es
pushl %fs
Now stack contains
pushl %gs
ss, esp,eflags, cs, eip, 0 (for
pushal // push all gen purpose regs error code), 64, ds, es, fs, gs,
eax, ecx, edx, ebx, oesp, ebp,
# Set up data segments.
esi, edi
movw $(SEG_KDATA<<3), %ax
This is the struct trapframe !
movw %ax, %ds
So the kernel stack now
movw %ax, %es contains the trapframe
# Call trap(tf), where tf=%esp
Trapframe is a part of kernel
pushl %esp # first arg to trap() stcak
call trap
addl $4, %esp
void
trap(struct trapframe *tf) trap()
{
if(tf->trapno == T_SYSCALL){
Argument is trapframe
if(myproc()->killed)
In alltraps
exit();
Before “call trap”, there was
myproc()->tf = tf; “push %esp” and stack had
syscall(); the trapframe
if(myproc()->killed)
Remember calling convention
exit(); --> when a function is called,
the stack contains the
return;
arguments in reverse order
} (here only 1 arg)
switch(tf->trapno){
.....
trap()
Has a switch
Timer
wakeup(&ticks)
switch(tf->trapno)
IDE: disk interrupt
Ideintr()
Q: who set this trapno?
KBD
Depending on the type of
Kbdintr()
trap
COM1
Uatrintr()
Call interrupt handler
If Timer
Call yield() -- calls sched()
If process was killed (how is that done?
Call exit()!
Stack had (trapframe)
when trap() returns
ss, esp,eflags, cs, eip, 0 (for error
code), 64, ds, es, fs, gs, eax, ecx,
edx, ebx, oesp, ebp, esi, edi, esp
#Back in alltraps
add $4 %esp
call trap
addl $4, %esp
esp
popal
# Return falls through to trapret...
.globl trapret
eax, ecx, edx, ebx, oesp, ebp, esi, edi
trapret:
Then gs, fs, es, ds
popal
popl %gs
add $0x8, %esp
popl %fs
0 (for error code), 64
popl %es
popl %ds
iret
addl $0x8, %esp # trapno and errcode
ss, esp,eflags, cs, eip,
iret
Scheduler
Scheduler – in most simple terms
Selects a process to execute and passes control to it !
The process is chosen out of “READY” state processes
Saving of context of “earlier” process and loading of context of
“next” process needs to happen
Questions
What are the different scenarios in which a scheduler called ?
What are the intricacies of “passing control”
What is “context” ?
Steps in scheduling scheduling
Suppose you want to switch from P1 to P2 on a timer
interrupt
P1 was doing
F() { i++; j++;}
P2 was doing
G() { x--; y++; }
P1 will experience a timer interrupt, switch to kernel
(scheduler) and scheduler will schedule P2
4 stacks need to change!
User stack of process ->
kernel stack of process
Switch to kernel stack
The normal sequence on any
interrupt !
Kernel stack of process ->
kernel stack of scheduler
Why?
Kernel stack of scheduler ->
kernel stack of new process . Why?
Kernel stack of new process ->
user stack of new process
scheduler()
Disable interrupts
Find a RUNNABLE process. Simple round-robin!
c->proc = p
switchuvm(p) : Save TSS of scheduler’s stack and make
CR3 to point to new process pagedir
p->state = RUNNING
swtch(&(c->scheduler), p->context)
scheduler()
swtch(&(c->scheduler), p->context)
Note that when scheduler() was called, when P1 was
running
After call to swtch() shown above
The call does NOT return!
The new process P2 given by ‘p’ starts running !
Let’s review swtch() again
swtch(old, new)
The magic function in swtch.S
Saves callee-save registers of old context
Switches esp to new-context’s stack
Pop callee-save registers from new context
ret
where? in the case of first process – returns to forkret() because stack was setup like
that !
in case of other processes, return where?
Return address given on kernel stack. But what’s that?
The EIP in p->context
When was EIP set in p->context ?
scheduler()
Called from?
mpmain() - already seen
No where else!
sched() is another scheduler function !
Who calls sched() ?
exit() - a process exiting calls sched ()
yield() - a process interrupted by timer calls yield()
sleep() - a process going to wait calls sleep()
void
sched(void)
sched()
get current process
{
int intena;
Error checking code (ignore as of now)
struct proc *p = myproc();
get interrupt enabled status on current
CPU (ignore as of now)
if(!holding(&[Link]))
panic("sched [Link]");
call to swtch
if(mycpu()->ncli != 1)
Note the arguments’ order
panic("sched locks");
p->context first, mycpu()->scheduler
second
if(p->state == RUNNING)
swtch() is a function call
panic("sched running");
pushes address of /*A*/ on stack of
if(readeflags()&FL_IF)
current process p
panic("sched interruptible");
switches stack to mycpu()->scheduler.
intena = mycpu()->intena; Then pops EIP from that stack and jumps
swtch(&p->context, mycpu()->scheduler); there.
/*A*/ mycpu()->intena = intena;
when was mycpu()->scheduler set? Ans:
during scheduler()!
}
sched() and schduler()
sched() { scheduler(void) {
... ...
swtch(&p->context, mycpu()->scheduler); /* X */
swtch(&(c->scheduler), p->context); /
* Y */
}
}
scheduler() saves context in c->scheduler, sched() saves context in p-
>context
after swtch() call in sched(), the control jumps to Y in scheduler
Switch from process stack to scheduler’s stack
after swtch() call in scheduler(), the control jumps to X in sched()
Switch from scheduler’s stack to new process’s stack
Set of co-operating functions
sched() and scheduler() as co-
routines
In sched()
swtch(&p->context, mycpu()->scheduler);
In scheduler()
swtch(&(c->scheduler), p->context);
These two keep switching between processes
These two functions work together to achieve scheduling
Using asynchronous jumps
Hence they are co-routines
To summarize
On a timer interrupt during P1
Now the loop in scheduler()
calls switchkvm()
trap() is called. Stack has
Then continues to find next process (P2)
changed from P1’s user stack to
to run
P1’s kernel stack
Then calls switchuvm(p): changing the
trap()->yield() page table to the P2’s page tables
yield()->sched()
then calls swtch(&c->scheduler, p2’s-
>context)
sched() -> swtch(&p->context,
Stack changes to P2’s kernel stack.
c->scheduler()
P2 runs the last instruction it was was in !
Stack changes to scheduler’s Where was it?
mycpu()->intena = intena; in sched()
kernel stack.
Then returns to the one who called sched() i.e.
Switches to location “Y” in exit/sleep, etc
scheduler().
Finally returns from it’s own “TRAP” handler
and returns to P2’s user stack and user code
Inter Process Communication
Revision of process related
concepts
PCB, struct proc
Process lifecycle – different states
Memory layout
Memory management
Interrupts handling, system call handling, code from
xv6
Scheduler, code of scheduler in xv6
IPC: Inter Process Communication
Processes within a system may be independent or cooperating
Cooperating process can affect or be affected by other processes, including sharing data
Reasons for cooperating processes:
Information sharing, e.g. copy paste
Computation speedup, e.g. matrix multiplication
Modularity, e.g. chrome – separate process for display, separate for fetching data
Convenience ,
Cooperating processes need interprocess communication (IPC)
Two models of IPC
Shared memory
Message passing
Shared Memory Vs Message Passing
Each requires OS to
provide system calls for
Creating the IPC
mechanism
To read/write using the IPC
mechanism
Delete the IPC mechanism
Note: processes
communicating with each
other with the help of OS!
Example of co-operating processes: Producer
Consumer Problem
Paradigm for cooperating processes, producer process
produces information that is consumed by a consumer
process
unbounded-buffer places no practical limit on the size of
the buffer
bounded-buffer assumes that there is a fixed buffer size
Example of co-operating processes: Producer
Consumer Problem
Shared data
#define BUFFER_SIZE 10
typedef struct {
. . .
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
Can only use BUFFER_SIZE-1 elements
Example of co-operating processes: Producer
Consumer Problem
Code of Producer
while (true) {
/* Produce an item */
while (((in = (in + 1) % BUFFER SIZE count) == out)
; /* do nothing -- no free buffers */
buffer[in] = item;
in = (in + 1) % BUFFER SIZE;
}
Example of co-operating processes: Producer
Consumer Problem
Code of Consumer
while (true) {
while (in == out)
; // do nothing -- nothing to consume
// remove an item from the buffer
item = buffer[out];
out = (out + 1) % BUFFER SIZE;
return item;
}
Message passing
Message Passing
Message system – processes communicate with each other using
send(), receive() like syscalls given by OS
IPC facility provides two operations:
send(message) – message size fixed or variable
Receive(message)
If P and Q wish to communicate, they need to:
establish a communication link between them
exchange messages via send/receive
Communication link can be implemented in a variety of ways
Message Passing using
“Naming”
Pass a message by “naming” the receiver
A) Direct communication with receiver
Receiver is identified by sender directly using it’s
name
B) Indirect communication with receiver
Receiver is identified by sender in-directly using it’s
‘location of receipt’
Message passing using direct communication
Processes must name each other explicitly:
send (P, message) – send a message to process P
receive(Q, message) – receive a message from process Q
Properties of communication link
Links are established automatically
A link is associated with exactly one pair of communicating processes
Between each pair there exists exactly one link
The link may be unidirectional, but is usually bi-directional
Message passing using IN-direct
communication
Messages are directed and received from mailboxes (also referred
to as ports)
Each mailbox has a unique id
Processes can communicate only if they share a mailbox
Properties of communication link
Link established only if processes share a common mailbox
A link may be associated with many processes
Each pair of processes may share several communication links
Link may be unidirectional or bi-directional
Message passing using IN-direct
communication
Operations
create a new mailbox
send and receive messages through mailbox
destroy a mailbox
Primitives are defined as:
send(A, message) – send a message to mailbox A
receive(A, message) – receive a message from mailbox A
Message passing using IN-direct
communication
Mailbox sharing
P1, P2, and P3 share mailbox A
P1, sends; P2 and P3 receive
Who gets the message?
Solutions
Allow a link to be associated with at most two processes
Allow only one process at a time to execute a receive operation
Allow the system to select arbitrarily the receiver. Sender is notified
who the receiver was.
Message Passing implementation:
Synchronization issues
Message passing may be either blocking or non-blocking
Blocking is considered synchronous
Blocking send has the sender block until the message is received
Blocking receive has the receiver block until a message is available
Non-blocking is considered asynchronous
Non-blocking send has the sender send the message and continue
Non-blocking receive has the receiver receive a valid message or null
Producer consumer using blocking send and
receive
Producer Consumer
message next produced; message next consumed;
while (true) { while (true) {
/* produce an item in next
produced */
receive(next consumed);
send(next produced); }
}
Message Passing implementation: choice of
Buffering
Queue of messages attached to the link;
implemented in one of three ways
1. Zero capacity – 0 messages
Sender must wait for receiver (rendezvous)
2. Bounded capacity – finite length of n messages
Sender must wait if link full
3. Unbounded capacity – infinite length
Sender never waits
Example of Shared memory
POSIX Shared Memory
What is POSIX?
Portable Operating System Interface (POSIX)
family of standards
specified by the IEEE Computer Society
for maintaining compatibility between operating systems.
API (system calls), shells, utility commands for
compatibility among UNIXes and variants
POSIX Shared Memory
Process first creates shared memory segment
segment id = shmget(IPC PRIVATE, size, S IRUSR | S IWUSR);
Process wanting access to that shared memory must attach to it
shared_memory = (char *) shmat(id, NULL, 0);
Now the process could write to the shared memory
sprintf(shared_memory, "Writing to shared memory");
When done a process can detach the shared memory from its
address space
shmdt(shared_memory);
Pipes
Pipes for IPC
We have already studies pipes and pipe()
system call
Two types
Unnamed Pipes or ordinary pipes
Named Pipe
Ordinary pipes
Ordinary Pipes allow communication in standard producer-
consumer style
Producer writes to one end (the write-end of the pipe)
Consumer reads from the other end (the read-end of the
pipe)
Ordinary pipes are therefore unidirectional
Require parent-child relationship between communicating
processes
Named pipes
Also called FIFO
Processes can create a “file” that acts as pipe. Multiple processes can share the
file to read/write as a FIFO
Named Pipes are more powerful than ordinary pipes
Communication is bidirectional
No parent-child relationship is necessary between the communicating processes
Several processes can use the named pipe for communication
Provided on both UNIX and Windows systems
Is not deleted automatically by OS
Named pipes
int mkfifo(const char *pathname, mode_t
mode);
Example