COMPX203 Computer Systems

Multitasking

h p://q.xorro.com/tyhu
tt


Recap
• CPU Architecture
• Datapath
• Instruction Cycle (fetch-decode-execute)
• Arithmetic Logic Unit

Multitasking

3
Multitasking
• Most operating systems allow more than one process
(or task) to run on a single CPU
• This is achieved by rapidly switching between
processes
• One process will run for a short while, then the next,
and so on
• This happens rapidly, giving the illusion that the
processes are running concurrently
the terms task and process will be used interchangeably

Multitasking Example
• CPU time shared between 3 processes (tasks)
• Time goes from left to right
• One process using the CPU at a time

P1 P1 P1

CPU P2 P2

P3 P3

Time
5

Multitasking Kernel
• The piece of code that facilitates multitasking is
called a Multitasking Kernel
• This is a fundamental part of an operating system

• The kernel allows each program to be written as if it

will run on its own CPU
• From the perspective of the program, it appears that
it has the CPU to itself, except for delays while other
processes are running



How do we share?
• Cooperative Multitasking:
• Tasks voluntarily release the CPU after doing some
processing
• For example, while waiting for I/O, or doing a small amount
of processing
• We have done this in assignment 3

• Pre-emptive Multitasking:
• Processes are forced to take turns
• A process can run on the CPU for a predefined duration of
time before giving the turn to another process
• Every process will eventually get its turn with the CPU

Scheduling
• The kernel must decide which process to run next
• This is called scheduling, and is performed by a piece of
code called the scheduler
• Scheduling decisions are not trivial, as there are often
conflicting goals:
• Are the processes "interactive", or "background"?
• Are some processes more important than others? Priorities?
• Are we trying to optimise throughput or response time?
• In trying to optimise decisions, will the future repeat the past?
• Besides, scheduling needs to run very efficiently
8

Round Robin Scheduling

• Round-robin has been widely used in operating systems
• Each process is allowed to run for some time (called a slice or
quantum) on the CPU
• Once that time slice expires, process is paused and switched out
• The next process is then given a new time slice, and allowed to
run on the CPU
• Once all processes have run, the first one will be chosen to run
again, afterwards the second and so forth
• Higher priority processes can be given a longer time slice
• It is possible that a process does not fully use its slice: it may
terminate or block waiting for something (e.g. I/O)

 Round Robin Scheduling Example

• Dark represents the process with the CPU, while grey
is waiting, and white is non-existent
• The first number in P(x,y) represents the arrival time
and the second, the time needed

10
By Ben Meiri - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=57518092

Context Switching
• Any running program has a particular state at any
point in time
• This can include:
• Code and data stored in RAM
• Values stored in registers
• The state of the stack
• The program counter (PC)
• The state of a process is collectively called its context

11

Context Switching
• When a process is taken off the CPU, we must make
sure it can resume its execution later on
• This is achieved by saving the various parts that make
up the process context to memory
• To resume a process, this context is loaded back from
memory, and thus the process continues to run
• Saving the context of one process and loading the
context of the next is known as a context switch

12

Multitasking Summary
• Illusion of multiple processes running simultaneously
on a single CPU is achieved by rapidly switching
between processes
• Switching between processes requires saving the
context of the currently running process to memory,
and loading the context of the next process
• Scheduling means choosing which process will run
next
• Round robin scheduling algorithm: processes take the
CPU for very small amounts of time (slices)

13

Multitasking
A WRAMP Implementation (and your assignment!)
Multitasking Kernel Parts
• Setup code: sets up interrupts and process-related
data structures
• Timer interrupt handler: checks if the running process
has run out of time
• Dispatcher: saves the context of the running process,
schedules (i.e. chooses) the next one tone run, and
restores its context

• Processes/tasks: each will run when loaded by the

dispatcher

15

Recap: Timer Interrupt Handling

• Setup Code: turns on interrupts and initialise timer

• Handler: determines the cause of the exception/

interrupt, and branches to the timer handler when
appropriate

• Timer handler: handles the timer interrupt,

acknowledges it, and returns from the interrupt

16




Multitasking Kernel Parts – Detailed
Setup Code Handler

Initialise processes Determine the cause of the interrupt

Turn on interrupts and initialise devices Branch to the timer handler if interrupt
Load the first process (via dispatcher) was caused by timer

Timer handler Dispatcher

Acknowledge interrupt Save the context of the current process
Subtract 1 from the current time slice Determine which process should run next
If the time slice has expired (i.e. is now (scheduling)
zero), branch to the dispatcher Load the context of the next process, and
Else return from exception set its time slice duration
Return from exception (i.e. continue
running the next process)

17

Program State
• Memory State:
• Instructions (machine code)
• Data (both .data and .bss)
• System Stack

• Register State:
• Register contents (including $sp and $ra)
• Program counter

18



Memory State: Instructions (code)

• Each process must have an entry point, analogous to
the main subroutine
• Each process may be written in its own .s file, as long
as its entry point is .global

process1_main:
# Code for process1

process2_main:
# Code for process2

process3_main:
# Code for process3

19

Memory State: Data

• Like instructions, the .data declarations may be
placed in a separate .s file (with the instructions for
that process) to keep things tidy
• If any data needs to be shared between separate
files, make the respective labels .global
• The assembler and linker take care of the rest!

20

Register State
• Each specific process/task will initialise its own
registers, as usual, not in the kernel
• Two exceptions: $sp and $ra
• $sp must be set to the top of the "stack block" of the
process
• $ra must be initialised to a subroutine address other than
the WRAMP monitor (which should remove the process
from the scheduling queue when it returns from the main
function)

21

Register State
• When first starting a process, the dispatcher should
begin by setting the PC to the address of the first
instruction of the process (i.e., its entry point)
• Each process can have its own value for $cctrl
• $cctrl must have the timer (IRQ2) and global
interrupts (IE) enabled while the processes are
running

22

Register State
• State stored in a Process Control Block (PCB)
$1
$2
$3
…
$4
.bss
$5 process1_pcb:
$6 .space 17
$7 …
$8
$9
$10
$11
$12
$13
$sp
$ra
$ear (PC)
$cctrl

23

Process Stacks
• If we wish to have our processes using stacks, then
we must set up a separate stack for each process
• If we do not have separate stacks, then processes
would interfere with each other
• To setup a stack we must:
• Allocate memory using a .space directive
• Set the stack pointer for the process to the address of the
end of that memory, i.e. the label should be after
the .space directive

24

Process Stacks
• How much memory should we allocate?
• The amount has implications for the number of nested
subroutine calls we can make
• Just make sure there is enough, otherwise bad stuff
happens

25

 Process Stacks
• For example, if we decide that 100 words is enough…
…
.bss
# Stack for process 1
.space 100
process1_stack:
Note that the stack labels are
# Stack for process 2 below the .space, because stacks
.space 100 grow from the top of the block
process2_stack: towards the lower addresses

# Stack for process 3

.space 100
process3_stack:
…

26






Managing Processes
• Dispatcher must know which process is currently
running
• Scheduler must know which process to run next

• Both of these points involve having a reference to

the PCBs of the relevant processes

27



Quick Diversion: the .equ directive
• Will make your life easier during the assignment!
• It allows us to define constants and refer to them
easily – much like #define in C
• Example:

…
.equ left_ssd_addr, 0x73002
…
sw $4, left_ssd_addr($0)
…

28

 PCB (With Link)

link
$1 …
.equ pcb_link, 0
$2
.equ pcb_reg1, 1
$3 .equ pcb_reg2, 2
$4 .equ pcb_reg3, 3
$5 …
$6 .equ pcb_ra, 15
$7 .equ pcb_ear, 16
$8 .equ pcb_cctrl, 17
$9 …
.bss
$10
process1_pcb:
$11 .space 18
$12 process2_pcb:
$13 .space 18
$sp process3_pcb:
$ra .space 18
$ear (PC)
$cctrl

PCB Linked List

Process 1 PCB Process 2 PCB Process 3 PCB
link link link
$1 $1 $1
$2 $2 $2
$3 $3 $3
$4 $4 $4
$5 $5 $5
$6 $6 $6
$7 $7 $7
$8 $8 $8
$9 $9 $9
$10 $10 $10
$11 $11 $11
$12 $12 $12
$13 $13 $13
$sp $sp $sp
$ra $ra $ra
$ear (PC) $ear (PC) $ear (PC)
$cctrl $cctrl $cctrl
Thus far…
• We’ve created a place for the instructions, data, and
stacks for each process
• We know what needs to be done to initialise registers
• We have allocated a PCB for each process to store its
context
• The PCB also has a link field to help the scheduler
choose the next process to run

31

Up Next…
• Initialisation
• Interrupt handler
• Dispatcher
• Saving context
• Choosing the next process
• Restoring context

32

 Kernel Structure
main:
# Setup processes
# Setup interrupts
# Start first process (via dispatcher)

handler:
# Check which exception occurred.
# If it is the timer interrupt, jump to handle_timer
# Otherwise we jump to the default exception handler

handle_timer:
# Acknowledge the interrupt.
# Subtract 1 from the timeslice counter
# If timeslice counter is zero, go to dispatcher
# Otherwise we return from exception

dispatcher:
# Save context for current process
# Select (schedule) the next process
# Reset the timeslice counter to an appropriate value
# Load context for next process
# Continue with next process (rfe)
…





Setting up Processes
• Before we can get our system going we need to
setup some fields in each of our PCBs
• link field must be set to point to the next PCB in the list
• stack pointer field must be set to the end of the stack
block for that process
• $ear field is the value of PC when an exception occurred
and therefore must be set to the entry point of the process
code
• $cctrl field (see the next slide…)

34

Initialising $cctrl
• We want to…
• …turn on the timer interrupt (IRQ2)
• …disable global interrupts (for now)
• …interrupts to become enabled when we execute an
rfe
• …ensure that we stay in kernel mode

IRQ2

OKU

OIE
KU

IE
31
$cctrl Undefined (set to zero) 0 0 0 0 0 1 0 0 1 1 0 1

0x0000004d

35

 PCB Setup Code

# Unmask IRQ2,KU=1,OKU=1,IE=0,OIE=1
addi $5, $0, 0x4d
…
# Setup the pcb for process 1
la $1, process1_pcb
# Setup the link field
la $2, process2_pcb
sw $2, pcb_link($1)
# Setup the stack pointer
la $2, process1_stack We do this
sw $2, pcb_sp($1) for each process,
# Setup the $ear field Shown for Process 1
la $2, process1_main
sw $2, pcb_ear($1)
# Setup the $cctrl field
sw $5, pcb_cctrl($1)

Current Process Pointer

• We need to maintain a pointer to the PCB of the currently-
running process
• This will be initialised to the address of the PCB for Process 1
• We’ll see how the scheduler updates current_process
shortly

# Set first process as the current process

la $1, process1_pcb
sw $1, current_process($0)
…
.bss
current_process:
.word

37

Interrupt Handling
• Interrupt Handler
• Need to check interrupt is from the timer
• If so, jump to the timer handler

• Timer Handler
• Decrement the current process time slice
• If reached zero, branch to the dispatcher

38

Handler Code
handler:
# Get the exception status register
movsg $13, $estat
# Check for any other exceptions than timer (IRQ2)
andi $13, $13, 0xffb0
# If no other exceptions have occurred then
# branch to our handler.
beqz $13, handle_timer
# Otherwise, jump to the old exception handler.
lw $13, old_vector($0)
jr $13

handle_timer:
# Handle the timer interrupt
…

39

Recap: Register $13

• Recall that register $13 is automatically saved by the
CPU when an exception occurs
• The value of $13 is copied into the special register
$ers (Exception Register Save)
• When an rfe instruction is executed, the value of $ers
is copied back to $13

40

What does this mean for us?

• Since $13 is already saved we can freely use it for the
handler and dispatcher, but we must save the value
of $ers as part of the process context
• When we restore context, we must load the
appropriate value from the saved context into $ers,
so it will be restored correctly to $13 when we return
from exception

41

In terms of our code…

• The code in our handle_interrupt routine can
only safely use $13
• The dispatcher can use $13 as a base address of the
PCB of the running process, for saving its context
• The dispatcher can use other registers once their
values have been saved to the appropriate PCB

42

The Dispatcher and its roles

• Save the context of the current process
• Choose (schedule) which process will run next
• Restore the context of the next process to run
• Return to that process (rfe)

43

Saving Context
• When we take a process off the CPU we need to
remember where we were up to
• This involves saving some things to memory:
• All general purpose registers (including $sp and $ra)
• The exception address register ($ear) – i.e. the value of PC
when the exception occurred
• The CPU control register ($cctrl)
• This all goes into the PCB of the currently running
process

44

Saving Context
• Be very careful in dispatcher to not lose contents of
any registers before they are saved
• When loading context, ensure that the contents of
any registers are not accidentally changed after they
have been restored

45

Saving Context
dispatcher:
save_context:
# Get the base address of the current PCB
lw $13, current_process($0)

# Save the registers

sw $1, pcb_reg1($13)
sw $2, pcb_reg2($13)
…
# $1 is saved now so we can use it
# Get the old value of $13
movsg $1, $ers
# and save it to the pcb
sw $1, pcb_reg13($13)
…
# Save $ear
movsg $1, $ear
sw $1, pcb_ear($13)
# Save $cctrl
movsg $1, $cctrl
sw $1, pcb_cctrl($13)
…

46

Scheduler (Choose Next Process)

…
schedule:
lw $13, current_process($0) # Get current process
lw $13, pcb_link($13) # Get next process from pcb_link field
sw $13, current_process($0) # Set next process as current process

current_process

link link
$1 $1
$2 $2
$3 $3
$4 $4
$5 $5
$6 $6
$7 $7
$8 $8
$9 $9

47

Restoring Context
load_context:
lw $13, current_process($0) # Get PCB of current process

# Get the PCB value for $13 back into $ers

lw $1, pcb_reg13($13)
movgs $ers, $1

# Restore $ear
lw $1, pcb_ear($13)
movgs $ear, $1

# Restore $cctrl
lw $1, pcb_cctrl($13)
movgs $cctrl, $1

# Restore the other registers

lw $1, pcb_reg1($13)
lw $2, pcb_reg2($13)
…

# Return to the new process

rfe

48

One More Thing

• Now you have your PCBs initialised and arranged in a
linked list
• A current_process pointer is set to the address of the
first PCB
• The dispatcher will be called by timer interrupt
handler when it’s time to switch processes
• But how do we initially load the first process onto the
CPU and start it running?
• Hint: we have already written code to load context …

49

Summary
• The timer interrupt handler and dispatcher work
together to provide process switching
• They must be carefully coded to save and restore
processes exactly
• Each process has its own Process Control Block (PCB)
to save state while other processes are running
• The Process Queue is formed using links in the PCBs

50