Process Scheduling Memory Interrupts and Scheduling

Operating systems

1. Processes
Chester Rebeiro
IIT Madras

2. 2
Executing Apps
(Process)
•Process
–A program in execution
–Most important abstraction in
an OS
–Comprises of
•Code
•Data
•Stack
•Heap
•State in the OS
•Kernel stack
–State contains : registers, list
of open files, related
processes, etc.
ELF
Executable
(a.out)
$gcc hello.c
Process
$./a.out
from ELFIn the
user space
of process
In the kernel
space

3. 3
Program ≠ Process
ProgramProcess
code + static and global dataDynamic instantiation of code +
data + heap + stack + process
state
One program can create several
processes
A process is unique isolated entity

4. 4
Process Address Space
•Virtual Address Map
–All memory a process can
address
–Large contiguous array of
addresses from 0 to MAXVA
Text
(instructions)
Data
Heap
Stack
0
MAXVAtrampoline
trapframe
User
mode

5. 5
Process Address Space
•Each process has a different address space
•This is achieved by the use of virtual memory
•Ie. 0 to MAXVA are virtual memory addresses
Process A Process B
Process A
Page TableProcess B
Page Table
Text
(instructions)
Data
Heap
Stack
0
MAXVAtrampoline
trapframe
Text
(instructions)
Data
Heap
Stack
0
MAXVAtrampoline
trapframe

6. 6
Virtual Address Mapping
Text
(instructions)
Data
Stack
Heap
Text
(instructions)
Data
Stack
Heap
Process A Process B
Virtual MemoryPhysical MemoryVirtual Memory
Process A
Page
Table
Process B
Page
Table

7. 7
Advantages of Virtual Address Map
•Isolation (private address space)
–One process cannot access another process’
memory
•Relocatable
–Data and code within the process is relocatable
•Size
–Processes can be much larger than physical memory

8. 8
Process Stacks
•Each process has 2 stacks
–User space stack
•Used when executing user code
–Kernel space stack
•Used when executing kernel
code (for eg. during system
calls)
–Advantage :Kernel can execute even if
user stack is corrupted
(Attacks that target the stack, such as
buffer overflow attack, will not affect the
kernel)
Text
(instructions)
Data
Heap
User stack
for process
Kernel Stack
for process
Process Address
Space
trapframe
trampoline
Kernel Address
Space
proc

9. 9
Process Management in xv6
•Each process has a PCB (process control block)
defined by struct procin xv6
•Holds important process specific information
•Why?
–Allows process to resume execution after a while
–Keep track of resources used
–Track the process state
ref : proc.h (struct proc)

10. 10
Summary of entries in PCB
proc.c
proc.h

11. 11
Entries in PCB
•PID
–Process Identifier
–Number incremented sequentially
•When maximum is reached
•Reset and continue to increment.
•This time skip already allocated PID numbers

12. 12
Process States
Process State : specifies the state of the process
UNUSED
SLEEPING
RUNNABLE
RUNNING
UNUSED àUnused PID
RUNNABLE àReady to run
RUNNING àCurrently executing
SLEEPING àBlocked for an I/O
Other states ZOMBIE (later)
ref : proc.h (enum procstate)

13. Scheduling Runnable Processes
Scheduler triggered to run when timer interrupt occurs or when
running process is blocked on I/O
Scheduler picks another process from the ready queue
Performs a context switch
Running
Process
CPU
Scheduler
Queue of RUNNABLE Processes
interrupt
every 100ms

14. 14
Page Directory Pointer
Page Directory Pointer
Text
(instructions)
Data
Heap
Stack
Process A
Virtual Memory
Process A
Page
Table
Physical Memory

15. Entries in PCB
•Pointer to trapframe
15
trapframe
Text
(instructions)
Data
Heap
Stack
0
MAXVAtrampoline
trapframe

16. Progress of a system call
16
openLibrary
ecall
trampoline
usertrap
syscall
sys_open
usertrapret
userret
User mode
Process’ Virtual Space
Supervisor mode
Process’ Virtual Space
Supervisor mode
Kernel Virtual Space

17. 17
Context Pointer
•Context pointer
–Contains registers used for
context switches.
–Callee saved registers

18. 18
Storing procs in xv6
•In a globally defined array present in ptable
•NPROC is the maximum number of processes that can
be present in the system (#define NPROC 64)
•Also present in ptable is a lock that seralizes access to
the array.
ref : proc.c (struct ptable) 2409, params.h (NPROC) 0150

19. 19
Creating a Process by Cloning
•Cloning
–Child process is an exact replica of the parent
–Fork system call
Process 1
Kernel
(execute fork)
system call
fork
Process 1
Kernel
(execute fork)
Process 2
Parent Child
=>

20. 20
Creating a Process by Cloning
(using fork system call)
•In parent
–fork returns child
pid
•In child process
–fork returns 0
•Other system
calls
–Wait, returns pid
of an exiting
child
int pid;
pid = fork();
if (pid > 0){
printf(“Parent : child PID = %d”, pid);
pid = wait();
printf(“Parent : child %d exited\n”, pid);
} else{
printf(“In child process”);
exit(0);
}

21. 21
•Making a copy of a process
is called forking.
–Parent (is the original)
–child (is the new process)
•When fork is invoked,
–child is an exact copy of
parent
•When fork is called all pages
are shared between parent
and child
•Easily done by copying the
parent’s page tables
Physical Memory
Parent
Page
Table
Child
Page
Table
Virtual Addressing Advantage
(easy to make copies of a process)

22. 22
Modifying Data in Parent or Child
Output
parent : 0
child : 1
int i=0, pid;
pid = fork();
if (pid > 0){
sleep(1);
printf("parent : %d\n", i);
wait();
} else{
i = i + 1;
printf("child : %d\n", i);
}

23. 23
Executing a Program
(exec system call)
•exec system call
–Load into memory and then
execute
•COW big advantagefor
exec
–Time not wasted in copying
pages.
–Common code (for example
shared libraries) would
continue to be shared
int pid;
pid = fork();
if (pid > 0){
pid = wait();
} else{
execlp("ls", "", NULL);
exit(0);

24. 24
Copy on Write
(COW)
•When data in any of the shared pages
change, OS intercepts and makes a copy
of the page.
•Thus, parent and child will have different
copies of thispage
•Why?
–A large portion of executables are not
used.
–Copying each page from parent and child
would incur significant disk swapping..
huge performance penalties.
–Postpone coping of pages as much as
possible thus optimizing performance
i of child here
i of parent here
Parent
Page
Table
Child
Page
Table
This page now is no longer shared

25. 25
Virtual Addressing Advantages
(Shared libraries)
•Many common functions such as printfimplemented in shared libraries
•Pages from shared libraries, shared between processes
Process A Process B
Virtual MemoryPhysical MemoryVirtual Memory
Process A
Page
Table
Process B
Page
Table
printf(){ …}printf(){ …}
printf(){ …}

26. How COW works
•When forking,
–Kernel makes COW pages as read only
–Any write to the pages would cause a page
fault
–The kernel detects that it is a COW page and
duplicates the page
26

27. 27
The first process
•Unix : /sbin/init
–Unlike the others, this is created by the kernel
during boot
–Super parent.
•Responsible for forking all other processes
•Typically starts several scripts present in /etc/init.d
in Linux

28. 28
Process tree
Processes in the
system arranged in
the form of a tree.
pstreein Linux
Who creates the first process?
init
NetworkManagerlightdm
dhclientdnsmasq
Init.d
gnome-session
compiz

29. 29
Process Termination
•Voluntary : exit(status)
–OS passes exit status to parent via wait(&status)
–OS frees process resources
•Involuntary : kill(pid, signal)
–Signal can be sent by another process or by OS
–pid is for the process to be killed
–signal a signal that the process needs to be killed
•Examples : SIGTERM, SIGQUIT (ctrl+\), SIGINT (ctrl+c),
SIGHUP

30. 30
Zombies
•When a process terminates it becomes a zombie(or
defunctprocess)
–PCB in OS still exists even though program no longer executing
–Why? So that the parent process can read the child’s exit status
(through waitsystem call)
•When parent reads status,
–zombie entries removed from OS… process reaped!
•Suppose parent does’nt read status
–Zombie will continue to exist infinitely … a resource leak
–These are typically found by a reaper process

31. 31
Orphans
•When a parent process terminates before its child
•Adopted by first process (/sbin/init)
=>

32. 32
Orphans contd.
•Unintentional orphans
–When parent crashes
•Intentional orphans
–Process becomes detached from user session and
runs in the background
–Called daemons, used to run background services
–See nohup

33. 33
The first process in xv6

34. The first process
•Initcode
•Creating the first process
–maininvokes userinit
–userinit
•allocate a process id, trapframe,
•Create page directory
•copy initcode.S to 0x0
•create a user stack at 0x0 (SP starts at 0x0+PGSIZE)
•set process to runnable
–the scheduler would then execute the process
34

35. userinit
35
proc.c

36. userinit
36
user/initcode.S

37. userinit
37
user/initcode.S

38. userinit
38
1.Find an unused proc entry
First entry will be used.
so, pid = 1
2.Create trapframe
3.Create empty user process’
page table
1.Map trampoline high
2.Map trapframe just
below it
4.Create context for process
1.ra points to forkret
2.Kernel stack pointer
set
1
2
3
4

39. userinit
39
1.Find an unused proc entry
First entry will be used.
so, pid = 1
2.Create trapframe
3.Create empty user process’
page table
1.Map trampoline high
2.Map trapframe just
below it
4.Create context for process
1.ra points to forkret
2.Kernel stack pointer
set
0

40. userinit
40
stack
Text0
4K

41. userinit
41

42. Executing User Code
•The kernel stack of the process has a trap frame
and context
•The process is set as RUNNABLE
•The scheduler is then invoked from main
main àscheduler
The initcode process is selected
(as it is the only process runnable)
–…and is then executed
42

43. 43
Scheduling the first process

44. What we need!
44
0x80000000
stack
text
0x0
before userinit
eip
esp
0x0
Initcode
(text+stack)
Paging Unit uses the kernel
page tables
Paging Unit uses the initcode’s
newly formed page tables
trapframe filled

45. Progress of a system call
45
initcode
scheduler
main
User mode
Process’ Virtual Space
Supervisor mode
Process’ Virtual Space
Supervisor mode
Kernel Virtual Space
swtch
forkret
usertrapret
userret
Context of
kernel
Context of
initcodeSupervisor mode
Kernel Virtual Space

46. Scheduler ()
46
extern struct proc *proc asm("%gs:4"); // this is a per cpu
variable
cpus[cpunum()].proc
1.Find the process which is RUNNABLE.
-currently only one process is RUNNABLE
-set it to RUNNING
-set CPU to run the initcode
2. context switch to initcode(swtch)
Switches context from scheduler’s
context to p
Function does not return
sched.c

47. swtch
47
For initcode,
* ra set to forkret
* sp set to kstack+PGSIZE
(refer allocproc)
This function returns to forkret and SP= kstack of initcode
swtch.S
a0 (1stparameter passed
to swtch) contains pointer to
scheduler context.
Here we store the
CPU registers into the
scheduler’s context
a1 (2ndparameter passed
to swtch) contains pointer to p-
>context. Here we load the
context intovCPU registers

48. forkret
48
proc.c

49. usertrapret
49
Set up interrupt handlers so in the trampoline
These trapframe entries will permit handling
syscalls, interrupts and traps
p->tf->epc set to 0 in userinit
trap.c
Set SPP so that when interrupt
returns, switches to user mode.
This will act as interrupt handler when
syscalls / interrupts occur.
satp is going as first argument (a1 register)
to userret

50. useret
50

51. finally … initcode.S J
•Invokes system call
exec to invoke /init
exec(‘/init’)
51

52. init.c
•forks and
creates a shell
(sh)
52
Handle orphans

53. System Calls for Process
Management
53

54. 54
Creating a Process by Cloning
•Cloning
–Child process is an exact replica of the parent
–Fork system call
Process 1
Kernel
(execute fork)
system call fork
Process 1
Kernel
(execute fork)
Process 2
Parent Child
=>

55. 55
Creating a Process by Cloning
(using fork system call)
int p;
p = fork();
if (p > 0){
printf(“Parent : child PID = %d”, p);
p = wait();
printf(“Parent : child %d exited\n”, p);
} else{
printf(“In child process”);
exit(0);
}
p=child’s PIDp=0
Parent process
child process

56. fork : from an OS perspective
56
contains PID, state, parent,
Files opened, pointers
to page table, kernel stack,
trapframe, context, etc.
kernel
Kernel
Stack
PCB
Page
Table
Page
Table
Kernel
Stack
PCB
Parent Process Information in kernel
Child Process Information in kernel
•Find an unused PID
•Set state to NEW
•Set pointers to newly
formed
•Pagetable
•Kernel stack
•trapframe and
context
•Copy information like
files opened, size, cwd,
from parent
Trap
frame
Trap
frame
Page
Table
Trap
frameKernel
Stack
PCB

57. fork : from an OS perspective
57
PCB
contains PID, state, parent,
Files opened, pointers
to page table, kernel stack,
trapframe, context, etc.
kernel
Kernel
Stack
Page
Table
Page
Table
Kernel
Stack
PCB
Parent Process Information in kernel
Child Process Information in kernel
•Find an unused PID
•Set state to NEW
•Set pointers to newly
formed
•Pagetable
•Kernel stack
•trapframeand
context
•Copy information like
files opened, size, cwd,
from parent
•Set process to Runnable
Trap
frame
Trap
frame
state RUNNABLE
means the
process is in the ready
queue and ready to run.

58. Child Process in Ready Queue
Running
Process
CPU
Scheduler
Queue of Runabble
Child process
added to ready
Run Queue

59. Return from fork
59
contains PID, state, parent,
Files opened, pointers
to page table, kernel stack,
trapframe, context, etc.
kernel
Kernel
Stack
PCB
Page
Table
Page
Table
Kernel
Stack
PCB
Parent Process Information in kernel
Child Process Information in kernel
•Find an unused PID
•Set state to NEW
•Set pointers to newly
formed
•Pagetable
•Kernel stack
•trapframe and
context
•Copy information like
files opened, size, cwd,
from parent
Trap
frame
Trap
frame
Page
Table
Trap
frameKernel
Stack
PCB
Pidof child
0

60. fork, fills in the proc structure for
a new process
60

61. The xv6 fork
61
(1) Pick an UNUSED proc. (2) allocate pid.
and (3) allocate trapframe(4) create empty page
directory; (5) setup context (p->context->ra =
forkret); (p->context->sp= p->kstack+ PGSIZE)
Copy page directory from the parent process
(pàpagetable) to the child (npàpagetable)
Set size of np same as that of parent
Set parent of np
Copy trapframe from parent to child
In child process, set eax register in
trapframe to 0. This is what fork
returns in the child process
Parent process returns the pid of the
child
Other things… copy file pointer from
parent, cwd, executable name
Child process is finally made runnable

62. The xv6 fork
62
(1)Pick an UNUSED proc.
(2)allocate pid.
(3) allocate trapframe
(4) create empty page directory;
(5) setup context
(p->context->ra = forkret);
(p->context->sp= p->kstack+ PGSIZE)
forkretwould ensure that the
new child process gets 0
when fork returns

63. 63
Copying Page Tables of Parent
•uvmcopy(in vm.c)
–replicates parents memory pages
–Constructs new table pointing to the new pages
–Steps involved
1.For each virtual page of the parent (starting from 0 to its sz)
i.Find its page table entry (function walk)
ii.Use kallocto allocate a page (mem) in memory for the child
iii.Use memmoveto copy the parent page to mem
iv.Use mappagesto add a page table entry formem
xv6 does not
support COW

64. 64
Register modifications w.r.t.
parent
Registers modified in child process
–%eax= 0so that pid= 0 in child process
–%eip= forkretso that child exclusively executes function forkret

65. 65
Exit system call
int pid;
pid = fork();
if (pid > 0){
printf(“Parent : child PID = %d”, pid);
pid = wait();
printf(“Parent : child %d exited\n”, pid);
} else{
printf(“In child process”);
exit();
}

66. 66
exit internals
•init, the first process, can never exit
•For all other processes on exit,
1.Decrement the usage count of all open files
•If usage count is 0, close file
•Drop reference to in-memory inode
2.wakeup parent
•If parent state is sleeping, make it runnable
•Needed, cause parent may be sleeping due to a wait
3.Make init adopt children of exited process
4.Set process state to ZOMBIE
5.Force context switch to scheduler
note : page directory, kernel stack, not
deallocated here
ref : proc.c (exit) 2604

67. exit
67
initproc can never exit
Close all open files
Decrement in-memory inode usage
Wakeup parent of child.
The child may be an orphan, in
which case initmust be woken up
For every child of exiting process,
Set its parent to initproc
Set exiting process state to zombie
invoke the scheduler, which
performs a context switch

68. 68
wait system call
•Invoked in
parent parent
•Parent ‘waits’
until child exits
int pid;
pid = fork();
if (pid > 0){
printf(“Parent : child PID = %d”, pid);
pid = wait();
printf(“Parent : child %d exited\n”, pid);
} else{
printf(“In child process”);
exit();
}

69. 69
wait internals
Wait system call
If p is a
child
Scan every
process ‘p’in ptable
no
If p is a
zombie
no
yes
Deallocate kernel stack
free page directory
Set p.state to UNUSED
next processIn ptable
yes
return pid(p)
sleep
return -1 if there are
no children
Sleep if there is at-least
one child which is not in a
zombie state
Will be
woken up by an exiting child.
return -1

70. wait
70
If ‘p’is infact a child of
proc and is in the ZOMBIE
state then free remaining
entries in p and return pid of p
Process will be set to
SLEEPING state and wakeup
only when the child exits
note :page directory, kernel stack,
deallocated here
… allows parent to peek into exited
child’s process
For every process in table, find
if (a) p is a parent and (b) if the
process is a zombie.
Copy the exit status of the child process
from kernel to user space.

71. wait
71
If ‘p’is infact a child of
proc and is in the ZOMBIE
state then free remaining
entries in p and return pid of p
Process will be set to
SLEEPING state and wakeup
only when the child exits
note : page directory, kernel stack,
deallocated here
… allows parent to peek into exited
child’s process
For every process in table, find
if (a) p is a parent and (b) if the
process is a zombie.
Copy the exit status of the child process
from kernel to user space.

72. 72
Executing a Program
(exec system call)
•exec system call
–Load a program into
memory and then
execute it
–Here ‘ls’executed.
int pid;
pid = fork();
if (pid > 0){
pid = wait();
} else{
execlp("ls", "", NULL);
exit(0);

73. ELF Executables
(linker view)
73
ref :www.skyfree.org/linux/references/ELF_Format.pdf
/bin/ls
This is an ELF
file
ELF Header
Section header table
Section 1
Section 2
Section 3
Section 4
---
---
ELF format of executable
ref :man elf

74. 74
ELF Header
Identification
type
Can have values relocatable object,
executable, shared object, core file
Machine details
Entry
virtual address where program
begins execution
Ptr to program header
Ptr to section header
ELF Header
Program header table
Segment 1
Segment 2
Segment 3
Segment 4
---
Section header table
i386, X86_64, ARM, MIPS, etc.
number of section headers
number of program headers

75. Hello World’s ELF Header
75
$ gcc hello.c –c
$ readelf –h hello.o

76. Section Headers
•Contains information about the various sections
76
$ readelf –S hello.o
Type of the section
PROGBITS : information defined by program
SYMTAB : symbol table
NULL : inactive section
NOBITS : Section that occupies no bits
RELA : Relocation table
Virtual address where the
Section should be loaded
(* all 0s because this is a .o file)
Offset and size of the section
Size of the table if present else 0

77. 77
Program Header
(executable view)
•Contains information about each
segment
•One program header for each segment
•A program header entry contains (among
others)
–Offset of segment in ELF file
–Virtual address of segment
–Segment size in file (filesz)
–Segment size in memory (memsz)
–Segment type
•Loadable segment
•Shared library
•etc
ELF Header
Program header table
Segment 1
Segment 2
Segment 3
Segment 4
---
---
Head 1
Head 2
Head 3
Head 4
---

78. Program Header Contents
78
type
offset
vaddr offset
paddr offset
Size in file image
Size in memory
flags
type of segment
Offset of segment in ELF file
Virtual address where the segment is to be loaded
physical address where the segment is to be loaded.
(ignored)
Can be smaller than size in memory because of
uninitialized data.

79. Program headers for Hello
World
•readelf –l hello
79
Mapping between segments and sections

80. 80
exec
•Executable files begin with a
signature.
•Sanity check for magic number. All
executables begin with aELF Magic
number string : “\x7fELF”
ref : exec.c
Get pointer to the inode for the executable
Parameters are the path of executable and
command line arguments
Set up a new set of page tables.
Do we really need to do this?
trampoline
trapframe
Process Memory Map
exec.c

81. exec contd.
(load segments into memory)
81
Parse through all the elf program headers.
Only load into memory segments of type LOAD
Add more page table entries to grow
page tables from old size to new size
(ph.vaddr+ ph.memsz)
Virtual Memory Map
trampoline
trapframe
Load segment into RAM
at the specified virtual
address (ph.vaddr)

82. uvmalloc
82
Virtual Memory Map
trampoline
trapframe
Grow the process from oldsz
(initially 0) to newsz(vaddr+memsz)
codesz

83. loadseg
83
Virtual Memory Map
trampoline
trapframe
Load segment pointed to by ip+ offset
to the specified virtual address va
codesz

84. exec contd.
(allocate user stacks)
84
Virtual Memory Map
trampoline
trapframe
code
sz
Guard page
stacksp
stackbase

85. exec contd. (fill user stack
with command line args)
85
arg0
arg 1
---
arg N
ptrto argN
…
ptrto arg1
ptrto arg0
0
ptr to 0
argc
0xffffffff
command line
args
NULL termination
pointer to
command
line args (argv)
argc
dummy return location
from main
Unused
User stack

86. exec contd.
(proc, trapframe, etc.)
86
Set the executable file name in proc
these specify where execution should
start for the new program.
Also specifies the stack pointer
Free the oldpagetablewhich was created during fork

87. Exercise
•How is the heap initialized in xv6?
see sys_sbrk and growproc
87