EECS 3221:
OPERATING SYSTEM FUNDAMENTALS
Hamzeh Khazaei
Department of Electrical Engineering and Computer Science
Week 2, Module 2: Processes
January 21, 2021
Operating System Concepts – 10th Edition 3.1 Silberschatz et al © 2018 updated by Khazaei @ 2021
1
Chapter 3: Processes
! Process Concept
! Process Scheduling
! Operations on Processes
! Interprocess Communication
! IPC in Shared-Memory Systems
! IPC in Message-Passing Systems
! Examples of IPC Systems
! Communication in Client-Server Systems
Operating System Concepts – 10th Edition 3.2 Silberschatz et al © 2018 updated by Khazaei @ 2021
2
1
Process Concept
! An operating system executes a variety of programs that run as a process.
! Process – a program in execution; process execution must progress in
sequential fashion
! Multiple parts
! The program code, also called text section
! Current activity including program counter, processor registers
! Stack containing temporary data
4 Function parameters, return addresses, local variables
! Data section containing global variables
! Heap containing memory dynamically allocated during run time
Operating System Concepts – 10th Edition 3.3 Silberschatz et al © 2018 updated by Khazaei @ 2021
3
Process Concept (Cont.)
! Program is passive entity stored on disk (executable file); process is active
! Program becomes process when executable file loaded into memory
! Execution of program started via GUI mouse clicks, command line entry of
its name, etc
! One program can be several processes
! Consider multiple users executing the same program
Operating System Concepts – 10th Edition 3.4 Silberschatz et al © 2018 updated by Khazaei @ 2021
4
2
Process in Memory
Operating System Concepts – 10th Edition 3.5 Silberschatz et al © 2018 updated by Khazaei @ 2021
5
Memory Layout of a C Program
Operating System Concepts – 10th Edition 3.6 Silberschatz et al © 2018 updated by Khazaei @ 2021
6
3
Process State
! As a process executes, it changes 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 processor
! Terminated: The process has finished execution
Operating System Concepts – 10th Edition 3.7 Silberschatz et al © 2018 updated by Khazaei @ 2021
7
Diagram of Process State
Operating System Concepts – 10th Edition 3.8 Silberschatz et al © 2018 updated by Khazaei @ 2021
8
4
Process Control Block (PCB)
Information associated with each process
(also called task control block)
! Process state – running, waiting, etc
! Program counter – location of instruction to next execute
! CPU registers – contents of all process-centric registers
! CPU scheduling information- priorities, scheduling queue pointers
! Memory-management information – memory allocated to the process
! Accounting information – CPU used, clock time elapsed since start, time limits
! I/O status information – I/O devices allocated to process, list of open files
Operating System Concepts – 10th Edition 3.9 Silberschatz et al © 2018 updated by Khazaei @ 2021
9
Threads
! So far, process has a single thread of execution
! Consider having multiple program counters per process
! Multiple locations can execute at once
4 Multiple threads of control -> threads
! Must then have storage for thread details, multiple program counters in PCB
! Explore in detail in Chapter 4
Operating System Concepts – 10th Edition 3.10 Silberschatz et al © 2018 updated by Khazaei @ 2021
10
5
Process Representation in Linux (PCB)
Represented by the C structure task_struct
pid t_pid;
long state;
unsigned int time_slice
struct task_struct *parent;
struct list_head children;
struct files_struct *files; /* list of open files */
struct mm_struct *mm; /* address space of this process */
…
Operating System Concepts – 10th Edition 3.11 Silberschatz et al © 2018 updated by Khazaei @ 2021
/* process identifier */
/* state of the process */ /* scheduling information */ /* this process’s parent */ /* this process’s children */
11
Process Scheduling
! Maximize CPU use, quickly switch processes onto CPU core
! Process scheduler selects among available processes for next execution
on CPU core
! Maintains scheduling queues of processes
! Ready queue – set of all processes residing in main memory, ready and waiting to execute
! Wait queues – set of processes waiting for an event (i.e. I/O)
! Processes migrate among the various queues
Operating System Concepts – 10th Edition 3.12 Silberschatz et al © 2018 updated by Khazaei @ 2021
12
6
Ready and Wait Queues
Operating System Concepts – 10th Edition 3.13 Silberschatz et al © 2018 updated by Khazaei @ 2021
13
Representation of Process Scheduling
Operating System Concepts – 10th Edition 3.14 Silberschatz et al © 2018 updated by Khazaei @ 2021
14
7
CPU Switch From Process to Process
A context switch occurs when the CPU switches from one process to another.
Operating System Concepts – 10th Edition 3.15 Silberschatz et al © 2018 updated by Khazaei @ 2021
15
Context Switch
! When CPU switches to another process, the system must save the state of the old process and load the saved state for the new process via a context switch
! Context of a process represented in the PCB
! Context-switch time is overhead; the system does no useful work while
switching
! The more complex the OS and the PCBèthe longer the context switch
! Time dependent on hardware support
! Some hardware provides multiple sets of registers per CPUè
multiple contexts loaded at once
Operating System Concepts – 10th Edition 3.16 Silberschatz et al © 2018 updated by Khazaei @ 2021
16
8
Multitasking in Mobile Systems
! Some mobile systems (e.g., early version of iOS) allow only one process to run, others suspended
! Due to screen real estate, user interface limits iOS provides for a
! Single foreground process- controlled via user interface
! Multiple background processes– in memory, running, but not on the display, and with limits
! Limits include single, short task, receiving notification of events, specific long-running tasks like audio playback
! Android runs foreground and background, with fewer limits
! Background process uses a service to perform tasks
! Service can keep running even if background process is suspended
! Service has no user interface, small memory use
Operating System Concepts – 10th Edition 3.17 Silberschatz et al © 2018 updated by Khazaei @ 2021
17
Operations on Processes
! System must provide mechanisms for:
! process creation
! process termination
Operating System Concepts – 10th Edition 3.18 Silberschatz et al © 2018 updated by Khazaei @ 2021
18
9
Process Creation
! Parent process create children processes, which, in turn create other processes, forming a tree of processes
! Generally, process identified and managed via a process identifier (pid)
! Resource sharing options
! Parent and children share all resources
! Children share subset of parent’s resources
! Parent and child share no resources
! Execution options
! Parent and children execute concurrently
! Parent waits until children terminate
Operating System Concepts – 10th Edition 3.19 Silberschatz et al © 2018 updated by Khazaei @ 2021
19
A Tree of Processes in Linux
Operating System Concepts – 10th Edition 3.20 Silberschatz et al © 2018 updated by Khazaei @ 2021
20
10
Process Creation (Cont.)
! Address space
! Child duplicate of parent
! Child has a program loaded into it
! UNIX examples
! fork()systemcallcreatesnewprocess
! exec()systemcallusedafterafork()toreplacetheprocess’ memory space with a new program
! Parent process calls wait() for the child to terminate
Operating System Concepts – 10th Edition 3.21 Silberschatz et al © 2018 updated by Khazaei @ 2021
21
C Program Forking Separate Process
Operating System Concepts – 10th Edition 3.22 Silberschatz et al © 2018 updated by Khazaei @ 2021
22
11
Creating a Separate Process via Windows API
Operating System Concepts – 10th Edition 3.23 Silberschatz et al © 2018 updated by Khazaei @ 2021
23
Process Termination
! Process executes last statement and then asks the operating system to delete it using the exit() system call.
! Returns status data from child to parent (via wait())
! Process’resources are deallocated by operating system
! Parent may terminate the execution of children processes using the abort() system call. Some reasons for doing so:
! Child has exceeded allocated resources
! Task assigned to child is no longer required
! The parent is exiting, and the operating systems does not allow a child to continue if its parent terminates
Operating System Concepts – 10th Edition 3.24 Silberschatz et al © 2018 updated by Khazaei @ 2021
24
12
Process Termination
! Some operating systems do not allow child to exists if its parent has terminated. If a process terminates, then all its children must also be terminated.
! cascading termination. All children, grandchildren, etc. are terminated.
! The termination is initiated by the operating system.
! The parent process may wait for termination of a child process by using the wait()system call. The call returns status information and the pid of the terminated process
pid t pid;
int status; …
pid = wait(&status);
! If no parent waiting (did not invoke wait()) process is a zombie
! If parent terminated without invoking wait , process is an orphan
Operating System Concepts – 10th Edition 3.25 Silberschatz et al © 2018 updated by Khazaei @ 2021
25
Zombie process
Operating System Concepts – 10th Edition 3.26 Silberschatz et al © 2018 updated by Khazaei @ 2021
26
13
Orphan Process
Operating System Concepts – 10th Edition 3.27 Silberschatz et al © 2018 updated by Khazaei @ 2021
27
Android Process Importance Hierarchy
! Mobile operating systems often must terminate processes to reclaim system resources such as memory. From most to least important:
o Foreground process o Visible process
o Service process
o Background process o Empty process
! Android will begin terminating processes that are least important.
Operating System Concepts – 10th Edition 3.28 Silberschatz et al © 2018 updated by Khazaei @ 2021
28
14
” ”
Multiprocess Architecture – Chrome Browser
Many web browsers ran as single process (some still do)
! If one web site causes trouble, entire browser can hang or crash
Google Chrome Browser is multiprocess with 3 different types of processes:
! Browser process manages user interface, disk and network I/O
! Renderer process renders web pages, deals with HTML, Javascript. A new renderer created for each website opened
4 RunsinsandboxrestrictingdiskandnetworkI/O,minimizingeffectof security exploits
! Plug-in process for each type of plug-in
Operating System Concepts – 10th Edition 3.29 Silberschatz et al © 2018 updated by Khazaei @ 2021
29
Interprocess 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
! Computation speedup
! Modularity
! Convenience
! Cooperating processes need interprocess communication (IPC)
! Two models of IPC
! Shared memory
! Message passing
Operating System Concepts – 10th Edition 3.30 Silberschatz et al © 2018 updated by Khazaei @ 2021
30
15
Communications Models
(a) Shared memory (b) Message passing
Operating System Concepts – 10th Edition 3.31 Silberschatz et al © 2018 updated by Khazaei @ 2021
31
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
Operating System Concepts – 10th Edition 3.32 Silberschatz et al © 2018 updated by Khazaei @ 2021
32
16
Interprocess Communication – Shared Memory
! An area of memory shared among the processes that wish to communicate
! The communication is under the control of the users processes not the
operating system.
! Major issues is to provide mechanism that will allow the user processes to synchronize their actions when they access shared memory.
! Synchronization is discussed in great details in Chapters 6 & 7.
Operating System Concepts – 10th Edition 3.33 Silberschatz et al © 2018 updated by Khazaei @ 2021
33
!
Bounded-Buffer – Shared-Memory Solution
Shared data
#define BUFFER_SIZE 10
typedef struct {
… } item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
Solution is correct, but can only use BUFFER_SIZE-1 elements
Operating System Concepts – 10th Edition 3.34 Silberschatz et al © 2018 updated by Khazaei @ 2021
!
34
17
item next_produced;
while (true) {
/* produce an item in next produced */ while (((in + 1) % BUFFER_SIZE) == out)
; /* do nothing */ buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE;
}
Operating System Concepts – 10th Edition 3.35 Silberschatz et al © 2018 updated by Khazaei @ 2021
35
item next_consumed;
while (true) {
while (in == out)
}
; /* do nothing */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
/* consume the item in next consumed */
Operating System Concepts – 10th Edition 3.36 Silberschatz et al © 2018 updated by Khazaei @ 2021
36
18
Interprocess Communication – Message Passing
! Mechanism for processes to communicate and to synchronize their actions
! Message system – processes communicate with each other without
resorting to shared variables
! IPC facility provides two operations: ! send(message)
! receive(message)
! The message size is either fixed or variable
Operating System Concepts – 10th Edition 3.37 Silberschatz et al © 2018 updated by Khazaei @ 2021
37
Message Passing (Cont.)
! If processes P and Q wish to communicate, they need to:
! Establish a communication link between them
! Exchange messages via send/receive
! Implementation issues:
! How are links established?
! Can a link be associated with more than two processes?
! How many links can there be between every pair of communicating processes?
! What is the capacity of a link?
! Is the size of a message that the link can accommodate fixed or
variable?
! Is a link unidirectional or bi-directional?
Operating System Concepts – 10th Edition 3.38 Silberschatz et al © 2018 updated by Khazaei @ 2021
38
19
Message Passing (Cont.)
! Implementation of communication link ! Physical:
4 Shared memory 4 Hardware bus 4 Network
! Logical:
4 Direct or indirect
4 Synchronous or asynchronous 4 Automatic or explicit buffering
Operating System Concepts – 10th Edition 3.39 Silberschatz et al © 2018 updated by Khazaei @ 2021
39
Direct Communication
! Processes must name each other explicitly:
! send(P,message)–sendamessagetoprocessP
! receive(Q,message)–receiveamessagefromprocessQ
! 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
Operating System Concepts – 10th Edition 3.40 Silberschatz et al © 2018 updated by Khazaei @ 2021
40
20
Indirect 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
Operating System Concepts – 10th Edition 3.41 Silberschatz et al © 2018 updated by Khazaei @ 2021
41
Indirect Communication
! Operations
! create a new mailbox (port)
! 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
Operating System Concepts – 10th Edition 3.42 Silberschatz et al © 2018 updated by Khazaei @ 2021
42
21
Indirect 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.
Operating System Concepts – 10th Edition 3.43 Silberschatz et al © 2018 updated by Khazaei @ 2021
43
Synchronization
! Message passing may be either blocking or non-blocking
! Blocking is considered synchronous
! Blocking send — the sender is blocked until the message is received
! Blocking receive — the receiver is blocked until a message is
available
! Non-blocking is considered asynchronous
! Non-blocking send — the sender sends the message and continue
! Non-blocking receive — the receiver receives:
! A valid message, or
! Null message
! Different combinations possible
! If both send and receive are blocking, we have a rendezvous
Operating System Concepts – 10th Edition 3.44 Silberschatz et al © 2018 updated by Khazaei @ 2021
44
22
Buffering
! Queue of messages attached to the link.
! Implemented in one of three ways
1. Zerocapacity–nomessagesarequeuedonalink. Sender must wait for receiver (rendezvous)
2. Boundedcapacity–finitelengthofnmessages Sender must wait if link full
3. Unboundedcapacity–infinitelength Sender never waits
Operating System Concepts – 10th Edition 3.45 Silberschatz et al © 2018 updated by Khazaei @ 2021
45
Examples of IPC Systems – POSIX
! POSIX Shared Memory
! Process first creates shared memory segment
shm_fd = shm_open(name, O_CREAT | O_RDWR, 0666);
! Also used to open an existing segment
! Set the size of the object
ftruncate(shm_fd, 4096);
! Use mmap()to memory-map a file pointer to the shared memory
object
! Reading and writing to shared memory is done by using the pointer
returned by mmap().
Operating System Concepts – 10th Edition 3.46 Silberschatz et al © 2018 updated by Khazaei @ 2021
46
23
IPC POSIX Producer
Operating System Concepts – 10th Edition 3.47 Silberschatz et al © 2018 updated by Khazaei @ 2021
47
IPC POSIX Consumer
Operating System Concepts – 10th Edition 3.48 Silberschatz et al © 2018 updated by Khazaei @ 2021
48
24
Pipes
! Acts as a conduit allowing two processes to communicate ! Issues:
! Is communication unidirectional or bidirectional?
! In the case of two-way communication, is it half or full-duplex?
! Must there exist a relationship (i.e., parent-child) between the communicating processes?
! Can the pipes be used over a network?
! Ordinary pipes – cannot be accessed from outside the process that created it. Typically, a parent process creates a pipe and uses it to communicate with a child process that it created.
! Named pipes – can be accessed without a parent-child relationship.
Operating System Concepts – 10th Edition 3.51 Silberschatz et al © 2018 updated by Khazaei @ 2021
51
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
! Windows calls these anonymous pipes
Operating System Concepts – 10th Edition 3.52 Silberschatz et al © 2018 updated by Khazaei @ 2021
52
25
Named Pipes
! 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
Operating System Concepts – 10th Edition 3.53 Silberschatz et al © 2018 updated by Khazaei @ 2021
53
Communications in Client-Server Systems
! Sockets
! Remote Procedure Calls
Operating System Concepts – 10th Edition 3.54 Silberschatz et al © 2018 updated by Khazaei @ 2021
54
26
Sockets
! A socket is defined as an endpoint for communication
! Concatenation of IP address and port – a number included at start of
message packet to differentiate network services on a host
! The socket 161.25.19.8:1625 refers to port 1625 on host 161.25.19.8
! Communication consists between a pair of sockets
! All ports below 1024 are well known, used for standard services
! Special IP address 127.0.0.1 (loopback) to refer to system on which process is running
Operating System Concepts – 10th Edition 3.55 Silberschatz et al © 2018 updated by Khazaei @ 2021
55
Operating System Concepts – 10th Edition 3.56 Silberschatz et al © 2018 updated by Khazaei @ 2021
56
27
Sockets in Java
! Three types of sockets
! Connection-oriented (TCP)
! Connectionless (UDP)
4 MulticastSocket class– data can be sent to multiple recipients
! Consider this “Date” server in Java:
Operating System Concepts – 10th Edition 3.57
Silberschatz et al © 2018 updated by Khazaei @ 2021
57
Sockets in Java
The equivalent Date client
Operating System Concepts – 10th Edition 3.58 Silberschatz et al © 2018 updated by Khazaei @ 2021
58
28
Remote Procedure Calls
! Remote procedure call (RPC) abstracts procedure calls between processes on networked systems
! Again uses ports for service differentiation
! Stubs – client-side proxy for the actual procedure on the server
! The client-side stub locates the server and marshalls the parameters
! The server-side stub receives this message, unpacks the marshalled parameters, and performs the procedure on the server
! On Windows, stub code compile from specification written in Microsoft Interface Definition Language (MIDL)
Operating System Concepts – 10th Edition 3.59 Silberschatz et al © 2018 updated by Khazaei @ 2021
59
Remote Procedure Calls (Cont.)
! Data representation handled via External Data Representation (XDR) format to account for different architectures
! Big-endian and little-endian
! Remote communication has more failure scenarios than local
! Messages can be delivered exactly once rather than at most once ! OS typically provides a rendezvous (or matchmaker) service to connect
client and server
! Why do we need a matchmaker?
Operating System Concepts – 10th Edition 3.60 Silberschatz et al © 2018 updated by Khazaei @ 2021
60
29
Execution of RPC
Operating System Concepts – 10th Edition 3.61 Silberschatz et al © 2018 updated by Khazaei @ 2021
61
End of Chapter 3 Any Question?
Operating System Concepts – 10th Edition Silberschatz et al © 2018 updated by Khazaei @ 2020
62
30