Operating Systems

Chapter 2 Process and Threads

Tien Pham Van, Dr. rer. nat.

(Lecture compiled with reference to other

presentations)
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 1
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Process Concept
• A process is an instance of a computer program
that is being executed. It contains the program
code and its current activity.

• Depending on the operating system (OS), a process

may be made up of multiple threads of execution
that execute instructions concurrently

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 2
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Processes
• A process is a unique
execution of a program.
– Several copies of a program
may run simultaneously or at
different times.
• A process has its own state:
– registers;
– memory.
• The operating system
manages processes.

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 3
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Process
Process: a program in execution
• Text section:
– program code
– program counter (PC)
– data of registers
• Stack: to save temporary data
• Data section: store global variables
• Heap: for memory management

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 4
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Process in Memory

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 5
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Process State

• new: The process is being created

• running: Instructions are being executed
• waiting: The process is waiting for some event to
occur
• ready: The process is waiting to be assigned to a
process
• terminated: The process has finished execution

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 6
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Diagram of Process State

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 7
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Process Control Block (PCB)
• Each process is represented in a
operating system by a Process
Control Block (PCB)
– Process identifier
– Process state
– Program counter (PC)
– CPU scheduling information
– Memory-management information
– Accounting information
– I/O status information

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 8
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Process Control Block Process Identification

• Process Control Block

The collection of attributes is refereed to as process control
block.
• Unique numeric identifier
– may be an index into the primary process table

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 9
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Process Control

• Process Control Block (PCB)

• Process State Information
• Process Control Information
• Functions of an Operating-System Kernel
• Switch a Process
• Change of Process State
• Execution of the Operating System

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 10
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Memory Tables
• Allocation of main memory to processes
• Allocation of secondary memory to processes
• Protection attributes for access to shared memory
regions
• Information needed to manage virtual memory

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 11
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 I/O Tables
• I/O device is available or assigned
• Status of I/O operation
• Location in main memory being used as the source
or destination of the I/O transfer

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 12
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Further in programming...

• https://www.youtube.com/watch?v=n5lgc
Kch3Hk

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 13
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 File Tables
• Existence of files
• Location on secondary memory
• Current Status
• Attributes
• Sometimes this information is maintained by a file-
management system
(Think about struct stat and stat( ) )

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 14
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Process State Transition Diagram with Two
Suspend States - Seven-State Process Model

New

Admit Suspend
Admit

Activate Dispatch
Ready, Ready Running Exit
suspend
Suspend Time out

Event Event
Event
Occurs Wait
Occurs

Activate
Blocked, Blocked
suspend
Suspend
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 15
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 UNIX Process State Transition Diagram (1)
fork

Created
Preempted
return
enough not enough memory
to user
memory (swapping system only)

User
Running preempt swap out
return reschedule Ready to Run Ready to Run
in Memory Swapped
process
swap in
system call, Kernel
interrupt
Running

sleep wakeup wakeup

interrupt,
interrupt return exit

Asleep in swap out Sleep,

Zombie Swapped
Memory

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 16
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 UNIX Process State Transition Diagram (2)

• User running: Executing in user mode.

• Kernel running: Executing in kernel model.
• Ready to run, in memory: Ready to run as soon as
the kernel schedules it.

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 17
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 UNIX Process State Transition Diagram (3)

• Asleep in memory: unable to execute until an event

occurs; process in main memory.
• Ready to run, swapped: process is ready to run, but
the the swapper must swap the process into main
memory before the kernel can schedule it to
execute.
• Sleeping, swapped: The process is awaiting an event
and has been swapped to secondary storage.

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 18
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 UNIX Process State Transition Diagram (4)

• Preempted: process is returning from kernel to user

mode, but the kernel preempts it and does a process
switch to schedule another process.
• Created: process is newly created and not yet ready
to run.
• Zombie: process no longer exists, but it leaves a
record for its parent process to collect.

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 19
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 UNIX Process Control Table
• Process Identifiers
ID of this process and ID of parent process.
• User Identifiers
real user ID, effective user ID
• Pointers
To user area and process memory (text, data, stack)
• Process Size, Priority, Signal, Timers, ......

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 20
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Context switch
• Activation record: copy of
process state. PC
process 1
• Context switch:
– current CPU context goes
out;
registers
process 2
– new CPU context goes in.

... CPU

memory

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 21
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 CPU Switch From Process to Process

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 22
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Process Scheduling

• As processes entered the system, they are put into

job queue
• The processes that stay in main memory and are
ready and waiting to execute are kept on a list called
ready queue
• A ready queue contains pointers to the first and
final PCBs in the list
• The list of processes waiting for a particular I/O is
called a device queue

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 23
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Queueing Diagram

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 24
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Schedulers
• Long-term scheduler
(or job scheduler) –selects which processes should
be brought into the ready queue

• Short-term scheduler
(or CPU scheduler) –selects which process should
be executed next and allocates CPU

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 25
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Schedulers
• Short-term scheduler is invoked very frequently
(milliseconds) ⇒(must be fast)
• Long-term scheduler is invoked very infrequently
(seconds, minutes) ⇒(may be slow)
• The long-term scheduler controls the degree of
multiprogramming

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 26
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Process Creation
• A process may create several new processes. The
creating process is called a parent process, and new
processes are called children process
• Each of these processes may create other
processes, forming a tree processes

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 27
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Process Tree

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 28
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Process Creation

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 29
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 C Program Forking Separate Process

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 30
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Process Termination

• Process executes last statement and asks the

operating system to delete it (exit)
• Output data from child to parent (via wait)
• Process’resources are deallocated by operating
system

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 31
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Co-operative multitasking

• Improvement on co-routines:
– hides context switching mechanism;
– still relies on processes to give up CPU.
• Each process allows a context switch at cswitch()
call.
• Separate scheduler chooses which process runs
next.

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 32
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Problems with co-operative multitasking

• Programming errors can keep other processes out:

– process never gives up CPU;
– process waits too long to switch, missing input.

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 33
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Preemptive multitasking

• Most powerful form of multitasking:

– OS controls when contexts switches;
– OS determines what process runs next.
• Use timer to call OS, switch contexts:

interrupt

timer
CPU

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 34
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Preemptive context switching

• Timer interrupt gives control to OS, which saves

interrupted process’s state in an activation record.
• OS chooses next process to run.

interrupt interrupt

P1 OS P1 OS P2

time

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 35
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 When to Switch a Process

• Trap
– error occurred
– may cause process to be moved to Exit state
• Supervisor call
– such as file open

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 36
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 When to Switch a Process
• Memory fault
– memory address is in virtual memory so it must be
brought into main memory
• Interrupts
– Clock
• process has executed for the maximum allowable time
slice
– I/O

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 37
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Process Synchronization

Concurrent access to shared data may result in data

inconsistency
Maintaining data consistency requires mechanisms to ensure
the orderly execution of cooperating processes
Suppose that we wanted to provide a solution to the
consumer-producer problem that fills all the buffers. We can
do so by having an integer count that keeps track of the
number of full buffers. Initially, count is set to 0. It is
incremented by the producer after it produces a new buffer
and is decremented by the consumer after it consumes a
buffer.

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 38
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Producer
while (true) {

/* produce an item and put in

nextProduced */
while (count == BUFFER_SIZE)
; // do nothing
buffer [in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
count++;
}

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 39
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Consumer
while (true) {
while (count == 0) ; // do nothing
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
count--;

/* consume the item in nextConsumed */

}

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 40
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Race Condition
count++ could be implemented as

register1 = count
register1 = register1 + 1
count = register1
count-- could be implemented as

register2 = count
register2 = register2 - 1
count = register2
Consider this execution interleaving with “count = 5” initially:
S0: producer execute register1 = count {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = count {register2 = 5}
S3: consumer execute register2 = register2 - 1 {register2 = 4}
S4: producer execute count = register1 {count = 6 }
S5: consumer execute count = register2 {count = 4}
https://www.youtube.com/watch?v=ZQb3DRy0g8U&ab_channel=Xovia
bcs
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 41
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Solution to Critical-Section Problem

1. Mutual Exclusion - If process Pi is executing in its critical section, then no

other processes can be executing in their critical sections
2. Progress - If no process is executing in its critical section and there exist
some processes that wish to enter their critical section, then the
selection of the processes that will enter the critical section next cannot
be postponed indefinitely
3. Bounded Waiting - A bound must exist on the number of times that
other processes are allowed to enter their critical sections after a
process has made a request to enter its critical section and before that
request is granted
 Assume that each process executes at a nonzero speed
 No assumption concerning relative speed of the N processes

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 42
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Peterson’s Solution
Two process solution
Assume that the LOAD and STORE instructions are
atomic; that is, cannot be interrupted.
The two processes share two variables:
int turn;
Boolean flag[2]
The variable turn indicates whose turn it is to enter the
critical section.
The flag array is used to indicate if a process is ready to
enter the critical section. flag[i] = true implies that
process Pi is ready!

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 43
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Algorithm for Process Pi

do {
flag[i] = TRUE;
turn = j;
while (flag[j] && turn == j);
critical section
flag[i] = FALSE;
remainder section
} while (TRUE);

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 44
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Solution to Critical-section Problem Using Locks

do {
acquire lock
critical section
release lock
remainder section
} while (TRUE);

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 45
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 TestAndndSet Instruction

Definition:

boolean TestAndSet (boolean *target)

{
boolean rv = *target;
*target = TRUE;
return rv;
}

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 46
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Solution using TestAndSet

Shared boolean variable lock., initialized to false.

Solution:

do {
while ( TestAndSet (&lock ))
; // do nothing

// critical section

lock = FALSE;

// remainder section

} while (TRUE);

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 47
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Swap Instruction

Definition:

void Swap (boolean *a, boolean *b)

{
boolean temp = *a;
*a = *b;
*b = temp;
}

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 48
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Solution using Swap
Shared Boolean variable lock initialized to FALSE; Each
process has a local Boolean variable key
Solution:
do {
key = TRUE;
while ( key == TRUE)
Swap (&lock, &key );

// critical section

lock = FALSE;

// remainder section

} while (TRUE);
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 49
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Lock implementation

Stanford CS140:
https://web.stanford.edu/~ouster/cgi-
bin/cs140-
spring20/lecture.php?topic=lockImpl

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 50
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Semaphore
Synchronization tool that does not require busy waiting
Semaphore S – integer variable
Two standard operations modify S: wait() and signal()
Originally called P() and V()
Less complicated
Can only be accessed via two indivisible (atomic) operations
wait (S) {
while S <= 0
; // no-op
S--;
}
signal (S) {
S++;
}

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 51
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Semaphore as General Synchronization Tool

Counting semaphore – integer value can range over an unrestricted domain

Binary semaphore – integer value can range only between 0
and 1; can be simpler to implement
Also known as mutex locks
Can implement a counting semaphore S as a binary semaphore
Provides mutual exclusion
Semaphore mutex; // initialized to 1
do {
wait (mutex);
// Critical Section
signal (mutex);
// remainder section
} while (TRUE);

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 52
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Condition Variables

condition x;

Two operations on a condition variable:

x.wait () – a process that invokes the operation
is
suspended.
x.signal () – resumes one of processes (if any)
that
invoked x.wait ()

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 53
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Monitors
A high-level abstraction that provides a convenient and effective
mechanism for process synchronization
Only one process may be active within the monitor at a time

monitor monitor-name
{
// shared variable declarations
procedure P1 (…) { …. }
…

procedure Pn (…) {……}

Initialization code ( ….) { … }

…
}
}

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 54
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Monitors

monitor account {
int balance := 0
function withdraw(int amount) {
if amount < 0 then error "Amount may not be negative"
else if balance < amount then error "Insufficient funds“
else balance := balance - amount
}
function deposit(int amount) {
if amount < 0 then error "Amount may not be negative“
else balance := balance + amount
}
}

CS 140: https://web.stanford.edu/~ouster/cgi-
bin/cs140-spring20/lecture.php?topic=locks

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 55
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Deadlock and Starvation

Deadlock – two or more processes are waiting indefinitely for an event that can be
caused by only one of the waiting processes
Let S and Q be two semaphores initialized to 1
P0 P1
wait (S); wait (Q);
wait (Q); wait (S);
. .
. .
. .
signal (S); signal (Q);
signal (Q); signal (S);
Starvation – indefinite blocking. A process may never be removed from the
semaphore queue in which it is suspended
Priority Inversion - Scheduling problem when lower-priority process holds a lock
needed by higher-priority process

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 56
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Deadlock and Starvation

https://web.stanford.edu/~ouster/cgi-
bin/cs140-
spring20/lecture.php?topic=deadlock

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 57
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Scheduling Algorithms

1. Open lecture:
https://www.youtube.com/watch?v=xlQ31WcTgOo&ab_cha
nnel=SomanshuChoudhary
2. Stanford CS140: https://web.stanford.edu/~ouster/cgi-
bin/cs140-spring20/lecture.php?topic=scheduling
https://www.youtube.com
Click to add text
/watch?v=xlQ31WcTgOo
&ab_channel=Somanshu
Choudhary

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 58
Email: tien.phamvan1@hust.edu.vn C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596