Transcript int - Parent Directory - Universidade de Coimbra

Operating
Systems
2006/2007
2. Processes
Paulo Marques
Departamento de Eng. Informática
Universidade de Coimbra
[email protected]
Disclaimer

This slides and notes are heavily based on the companion material of
[Silberschatz05].The original material can be found at:


In some cases, material from [Stallings04] may also be used. The
original material can be found at:


http://codex.cs.yale.edu/avi/os-book/os7/slide-dir/index.html
http://williamstallings.com/OS/OS5e.html
The respective copyrights belong to their owners.
2
What’s a Process?
MS Word
(1 process)


MS Excel
(1 process)
Program = Binary Image (Executable)
Process = The living “Image” of a program running

It includes information like:
- Program Counter
- Allocated Memory / Address Space
- Identifier, Owner, Security Attributes, etc.
3
A process in Memory
Address Space
4GB
My Process
0
4
The “Process Memory Image” in Unix

text  Where the code of the program goes


data  Where all variables are



.data section  global and static initialized variables to non-zero
.bss section  global and static non-initialized variables
(or initialized to 0)
heap  Where all dynamically allocated memory is set


Called .text section
e.g. as a result of malloc()
stack  Where all automatic variables exist


Variables that are automatically created and destroyed in methods
It grows down
5
The “Process Memory Image” in Unix (2)
(high address)
stack
.stack segment
possible hole in
address space!
heap
non-initialized
static data
.bss segment
initialized
static data
.data segment
code
(shared)
.text segment
(low address)
Basically, these are the
ones that take space
in the executable…
6
Quiz: Where does everything go?
#define KB (1024)
#define MB (1024*1024)
char buf[10*MB];
char command[KB] = "command?";
int n_lines = 0;
int n_tries = 20;
int total;
int f(int n) {
int result;
static int number_calls = 0;
}
++number_calls; result = n*n;
return result;
int main() {
int x = 5;
}
printf("f(%d)=%d\n", x, f(x));
return 0;
.bss
.data
.bss
.data
.bss
.stack
.bss
.stack
What about the globals:
char buf[10*MB] = {0};
char buf[10*MB] = {1};
7
Finding things out: size & objdump
8
Process States
Notes:
 “Waiting” is also known as “Blocked”
 Processes in the Ready and Blocked states do not consume CPU!
This is very important!
9
Process Control Block (PCB)

One of the most important data structures of the OS


Represents a running process
The PCB includes:










Process identifier
Process state
Program Counter
CPU registers
CPU scheduling information
Memory-management information
Accounting information
I/O status information
List of open files
…
10
Context Switch from Process to Process
11
Execution of three processes over time…
12
Process Queues

So, where are all the PCBs saved?


Job queue


Set of all processes in the system
Ready queue


Processes migrate among the various queues…
Set of all processes residing in main memory,
ready and waiting to execute
Device queues

Set of processes waiting for an I/O device
(also known as blocked queues)
13
Device Queues
(i.e. works like a global blocked queue)
The Several Queues…
14
PCBs Flow Among Queues
Process Scheduler
Note that events do not necessarily
correspond to I/O… (more on this latter)
15
Why Event Driven? … A “Human Perspective”
Characteristic
CPU frequency
Processor Cycle Time
L2 cache access
Memory access
Thread context switch
Disk access
Process quantum
Scaled to Human Time
2GHz
0.5
10
80
5000
8000000
100000000
ns
ns
ns
ns (5us)
ns (8ms)
ns (100ms)
1
20
160
10000
16000000
200000000
s
s
s
s
s
s
(2.6 mins)
(2.7 hours)
(185 days)
(6.3 years)
In blue
►Things improving very fast
In orange ►Things improving to a degree
In red
►Things not really improving
16
What’s the Best Scheduler?
What’s the Best Plane?
Capacity
(Passengers)
Autonomy
(Km)
Velocity
(Km/h)
Throughput
Boeing 777
375
7,408
976
366,000
Boeing 747
470
6,640
976
458,720
Concorde
132
6,400
2,160
285,120
Douglas DC8
146
13,952
870
127,020
Plane
(Passengers x
Km/h)
It all depends on what you are optimizing for!
17
What’s the Best Scheduler?
It all depends…

Server Multitasking Operating
Systems

User Multitasking Operating
Systems

Batch Operating Systems

Real-time Operating Systems

Embedded Operating Systems

Multimedia Operating Systems

…
Even in Windows 
18
Interactive Systems


Multitasking “user” operating systems must be quite
careful about the degree of multiprogramming introduced
Response time is quite important!
Loosing money by
transforming an expert
into an idiot…
19
Suspended States

In some operating systems, additional states are
introduced for describing processes that have been
swapped to disk
20
Two Suspended States
21
Scheduling with Suspended States

In systems with suspended states it is common to have:

A long term (or medium term) scheduler
… Selects which processes should be brought from disk into
the ready queue

A short-term (or CPU) scheduler

… Selects which process should be executed next and allocates CPU
22
Types of Processes

I/O Bounded


CPU Bounded


Spend more time doing I/O than computation
(Live mostly in the blocked queue)
Spend more time doing computation than I/O
(Live mostly in the ready queue)
For a good utilization of computer resources it’s important
to have a good mix of I/O bounded and CPU bounded
processes: the long-term scheduler is responsible for this
23
Process Creation

Parent process create children processes, which in turn
create other processes, forming a tree of processes
Process Tree
in Solaris
24
Different Heritance Models…

The way resources are shared between parent and child
processes varies widely among operating systems…

Resource sharing




Parent and children share all resources
Children share subset of parent’s resources
Parent and children share no resources
Execution



Parent and children execute concurrently
Parent waits until children terminate
Children terminate if parent terminates (cascading termination)
25
Process Model in UNIX

Process creation in Unix is
based on spawning child
processes which inherit all the
characteristics of their fathers



Variables, program counter,
open files, etc.
Spawning a process is done
using the fork() system call
After forking, each process will
be executing having different
variables and different state.


The Program Counter will be
pointing to the next instruction
Changing a variable in the child
program doesn’t affect its
father (and vice-versa)
State
Original Process
a = f();
fork();
b = g();
Original
Process
Child
Process
State
State
a = f();
fork();
b = g();
a = f();
fork();
b = g();
26
Forking in Unix
#include
#include
#include
#include
<stdio.h>
<unistd.h>
<sys/wait.h>
<sys/types.h>
int main()
{
pid_t id;
id = fork();
if (id == 0)
{
printf("[%d] I'm the son!\n", getpid());
printf("[%d] My parent is: %d\n", getpid(), getppid());
}
else
{
printf("[%d] I'm the father!\n", getpid());
wait(NULL);
}
return 0;
}
27
Copy-on-Write




Nowadays, the memory of a process is organized in pages
of typically 4KB
After a fork(), the child process and the parent process
share the same pages
The operating system detects when a page is being
written either by the parent process or the child process.
When that happens, a copy is made on demand, before
the write is allowed to proceed! This is called copy-onwrite
Thus, changing a variable on a child process doesn’t affect
its parent and vice-versa
28
Shared Address Space with the Kernel

For making system calls and traps fast, it is necessary that is possible
to jump directly to the kernel handler routine without remapping any
memory

The address space of each process is divided into two parts:



One that is specific of that process
One that corresponds to the kernel and is shared by all processes
How does it work?


The user process does not have direct access to the kernel memory; it
cannot read nor write that part of the address space
Whenever a trap occurs, it enters in “kernel mode” and thus has access to
the already mapped memory
29
Address Space in Linux (32-bit)
0xFFFFFFFF
1GB
Kernel
0xC0000000
Program Stack
(Shared Libraries)
0x40000000
3GB
Program Data
Program Text
Kernel
0x08048000
0x00000000
30
Process Termination in UNIX

A process is only truly eliminated by the operating system
when its father calls wait()/waitpid() on it.


Zombie Process: One that has died and its parent has
not acknowledged its death (by calling wait())


This allows the parent to check things like the exit code of its sons
Be careful with this if your are designing servers. They are eating
up resources!!
Orphan Process: One whose original parent has died. In
that case, its parent becomes init (process 1).
31
Let’s generate some Zombies
#include
#include
#include
#include
#include
<stdio.h>
<stdlib.h>
<unistd.h>
<sys/wait.h>
<sys/types.h>
void worker() {
printf("[%d] Hi, I'm a worker process! Going to die...\n",
getpid());
}
int main()
{
for (int i=0; i<10; i++) {
if (fork() == 0) {
worker();
exit(0);
}
}
printf("[%d] Big father is sleeping!\n", getpid());
sleep(10);
return 0;
}
32
Zombies (2)
33
Let’s see adoption by init
#include (...)
void worker()
{
sleep(10);
printf("[%d] Let's see who my dady is: %d\n", getpid(),
getppid());
}
int main()
{
for (int i=0; i<10; i++)
{
if (fork() == 0)
{
worker();
exit(0);
}
}
printf("[%d] Big dady is going away!\n", getpid());
return 0;
}
34
And the result is...
35
But…
If all new processes come from the same
original process, how is it possible to execute
new programs (e.g. run Microsoft Word, which
is not part of Microsoft Windows)???
36
How a process becomes another executable…

Somehow the OS must be able to execute code starting
from an executable file



int
int
int
int
int
e.g. how does the shell (‘bash’) becomes ‘ls’?
execl(const char *path, const char *arg, ...);
execlp(const char *file, const char *arg, ...);
execle(const char *path, const char *arg, ..., char *const envp[]);
execv(const char *path, char *const argv[]);
execvp(const char *file, char *const argv[]);
“exec family” of functions



Allow to substitute the current process executable image by
another one. The substitution is complete!
The functions that have a ‘p’ make use of the environment PATH;
The functions that have a ‘v’ make use of a pointer to an array on
parameters; The functions that have an ‘l’ have the parameters
passed separated by commas
Make sure that the first parameter is the name of the program!
37
Example

Simple program that lists the files in the current directory

Note: A successful exec() never returns

The code, the stack, the heap, it’s all replaced by the new
executable
exec()
Original Code
“ls code”
“ls code”
38
The corresponding code...
#include
#include
#include
#include
<stdio.h>
<stdlib.h>
<unistd.h>
<sys/types.h>
int main()
{
if (execlp("ls", "ls", "-a", NULL) == -1)
perror("Error executing ls: ");
else
printf("This cannot happen!\n");
return 0;
}
Using an array
can be more
flexible...
char* ls_param[] = { "ls", "-a", NULL };
if (execvp(ls_param[0], ls_param) == -1)
perror("Error executing ls: ");
39
Reasons for Process Termination











Normal completion
Time limit exceeded
Memory unavailable
Bounds violation
Protection error
I/O failure
Invalid instruction
Operating system intervention (e.g. on deadlock)
Parent terminates so child processes terminate
Parent request
…
40
Reference

[Silberschatz05]
Chapter 3: Processes


3.1, 3.2, 3.3
[Robbins03]
Chapter 2: Programs, Processes and Threads
Chapter 3: Processes in Unix
41