CS计算机代考程序代写 data structure concurrency assembler Slide 1

Slide 1

Operating Systems

Hubertus Franke

.edu

CSCI-GA.2250-001

Processes and Threads

Details of Lecture

• Process Model

• Process Creation ( fork , exec )

• Signals

• Process State / Transition Models

• Multi-programming

• Threads

OS Management
of Application Execution

• Resources are made available to multiple applications

• A “processor” can only run one unit of execution
(process/thread) at a time.

• The processor is switched among multiple applications
so all will appear to be progressing (albeit potentially
at reduced speed)

[ this is called a “context switch”, more later]

• The processor and I/O devices can be used
efficiently
– When application performs I/O, the processor can be used

for a different application.

Program code

Processor
executes the code

When the processor begins to execute the program
code, we refer to this executing entity as a process

Resides on storage
(just a sequence of bytes
[ code , data ])

What is exactly a “processor”
from an OS perspective

FXU, IXPU

HW
thread0

FXU, IXPU

HW
thread1

HW
thread0

HW
thread1

Core-0 Core-1

FXU, IXPU

HW
thread0

FXU, IXPU

HW
thread1

HW
thread0

HW
thread1

Core-2 Core-3

CPU-0 CPU-1

Each HW-thread
expose register set
(typically,
32 integer regs
32 floating point regs
special regs
[ see ABI ]

OS can schedule an independent unit of execution onto
each Hardware-Thread (HW-Thread)

What Is a Process?

An abstraction of a running program

Program Counter
(points at current instruction)

The Process Model

• A process has a program, input, output, and
state (data).

• A process is an instance of an executing
program and includes
– Variables ( memory )

– Code

– Program counter ( really hardware resource)

– Registers ( – “ – )

– …
If a program is running twice, does it count as two processes? or one?

Process: a running program
• A process includes

– Process State (state, registers save areas)
• Open files, thread(s) state, resources held

– Address space (view of its private memory)

All state is accessible as an entry in the process
(entry) table

• A process tree
– A created two child processes, B and C
– B created three child processes, D, E, and F

Address Space

• Defines where sections of data and
code are located in 32 or 64 address
space

• Defines protection of such sections

• ReadOnly, ReadWrite, Execute

• Confined “private” addressing concept
➔ requires form of address virtualization

( will get to it during
memory memory management )

Text/Code

Data

mmap

mmap

Process

CreationTermination

StateImplementation

Process Creation
• System initialization

– At boot time
– Foreground
– Background (daemons)

• Execution of a process creation system call by a
running process

• A user request

• A batch job

• Created by OS to provide a service

• Interactive logon

Process Termination

• Normal exit (voluntary)

• Error exit (voluntary)

• Fatal error (involuntary)

• Killed by another process (involuntary)

Process Termination: More Scenarios

Implementation of Processes

• OS maintains a process table
Process procs[];

• An array (or a hash table) of structures

• One entry per process ( pid is the uniq id)

procs[pid];

Implementation of Processes:
Process Control Block (PCB)

▪ Contains the process
elements

▪ It is possible to interrupt a
running process and later
resume execution as if the
interruption had not
occurred → state

▪ Created and managed by
the operating system

▪ Key tool that allows support
for multiple processes

OS objects related to process

Conceptual view of the
tables that OS maintains
in order to manage execution
of processes on resources.

Though there is one PCB per
process, there is a “mesh” of
multiple objects to allow
for sharing between processes
where appropriate
– Memory tables, io-tables, ….

Linux Process (Task) object

• Linux Process ~= struct task

~1.5KB + 2*stacks ( user + kernel )

Need to separate
to ensure isolation between
Kernel and User
(recall systemcall)

user: stack growth till out of space
Kernel: 4KB or 8KB

Some Unix Details

• Creation of a new process: fork()

• Executing a program in that new process

• Signal notifications

• The kernel boot manually creates ONE
process (the init process (pid=0)),
all other processes are created by fork()).

fork()

!

parent

parent

child

Before

After

Only LOGICALLY duplicates
the whole process
(will cover in MemMgmt)

fork()
#include

#include

int main(int argc, char **argv)

{

pid_t pid = fork();

if (pid == 0)

{

// child process

}

else if (pid > 0)

{

// parent process

}

else

{

// fork failed

printf(“fork() failed!\n”);

return 1;

}

}

syscall that creates new PCB and duplicates
Address Space

Child runs now here

Parent continues here

execv()

execv()
#include

#include

int main(int argc, char **argv)

{

pid_t pid = fork();

if (pid == 0)

{

execv(path,executablename)

}

else if (pid > 0)

{

int status;

waitpid(pid,&status,option)

}

else

{

// fork failed

printf(“fork() failed!\n”);

return -1;

}

Creates new PCB and Address Space

Child starts new program image of new process
this will NEVER return but for an error

Parent waits for child process to finish

Fork , exec, wait (and their variants) are system calls

pid is the object handle that the operating system returns
for a process

clone()
See:

http://man7.org/linux/man-pages/man2/clone.2.html

For what things can be clone.

This is the bases on how threads
are created.

Linux/Unix internally uses
objects to create processes /
threads

How these objects interrelate
depends on fork/clone calls

Signal()
• Means to “signal a

process” (i.e. get its
attention).

• There are a set of
signals that can be sent
to a process (some
require permissions).

• Process indicates
which signal it wants to
catch and provides a call
back function

• When the signal is to be
sent (event or “kill
pid”) the kernel
delivers that signal.

Signal()
#include

#include

#include

void sig_handler(int signo) {

if (signo == SIGINT)

printf(“received SIGINT\n”);

}

int main(void) {

// install the handler

if (signal(SIGINT, sig_handler) == SIG_ERR)

printf(“\ncan’t catch SIGINT\n”);

// A long long wait so that we can easily

// issue a signal to this process

while(1) sleep(1);

return 0;

}

When signal is delivered:
* kernel stops threads in process
* kernel “adds a stack frame”
* kernel “switches IPC to sig_handler
* kernel continues process
* Process will continue with sig_handler
* Process on completion will call

back to kernel

A few basics to remember
• fork(), exec(), wait() and it’s variants are OS system calls to

create and manipulate processes
• PIDs are handles that the operating system identifies life processes by
• There are user processes and system processes

Process State Model

• Depending on the implementation, there
can be several possible state models.

• The Simplest one: Two-state diagram

Process State Model:
Three-State Model

Process State Model:
Five-State Model

Using Queues to Manage
Processes

Using Queues to Manage
Processes

One Extra State!

Swapped to disk
Whole process and its “address space” is moved to disk

One Extra State!

Multiprogramming

• One CPU and several processes

• CPU switches from process to process quickly

What Really Happens What We Think It Happens

Running the same program several times will not result
in the same execution times due to:
– interrupts
– multi-programming

Simple Modeling of
Multiprogramming

• A process spends fraction p waiting for I/O

• Assume n processes in memory at once

• The probability that all processes are waiting
for I/O at once is pn

• So -> CPU Utilization = 1 – pn

Degree of Multiprogramming

Multiprogramming lets processes use the CPU
when it would otherwise become idle.

How to do multiprogramming

• Really a question of how to increase
concurrency (e.g. multi-core system)
and overlap I/O with computation.

• Example Webserver:
– If single process, every system call that

blocks will block forward progress

– Let’s discuss !!!!!!!

Solution #1

• Multiple Processes

• What’s the issue ?
– Resource consumption

• Each process has its own address space
( code, stack, heap, files, ….. )

– Who owns perceived single resource:
• E.g. webserver port 80 / 1080 / 8080 ????

Threads

• Multiple threads of control within a
process
– unique execution

• All threads of a process share the same
address space and resources
(with exception of stack)

Why Threads?

• For some applications many activities can happen
at once
– With threads, programming becomes easier

• Otherwise application needs to actively manage different
logical executions in the process

• This requires significant state management

– Benefit applications with I/O and processing that can
overlap

• Lighter weight than processes
– Faster to create and restore

( we just really need a stack and an execution unit, but
don’t have create new address space etc. )

Example :
Multithreaded Web Server

Processes vs. Threads

OS internal Data Structure implications:

Processes vs Threads

• Process groups resources
– (Address Space, files)

• Threads are entities scheduled for execution
on CPU

• Threads can be in any of several states:
running, blocked, ready, and terminated
( remember the process state model ? )

• No protections among threads (unlike
processes) [Why?] → this is important

Processes vs Threads

• The unit of dispatching is referred to as a
thread or lightweight process (lwp)

• The unit of resource ownership is referred
to as a process or task
(unfortunately in linux struct task
represents both a process and thread)

• Multithreading – The ability of an OS to
support multiple, concurrent paths of
execution within a single process

Processes vs Threads

• Process is the unit for resource allocation and a
unit of protection.

• Process has its own (one) address space.

• A thread has:
– an execution state (Running, Ready, etc.)
– saved thread context when not running
– an execution stack
– some per-thread static storage for local variables
– access to the memory and resources of its process

(all threads of a process share this)

Multithreading on Uniprocessor
System

Where to Put The Thread
Implementation / Package?

User space Kernel space

Discussed in previous slides

Kernel-Level Threads (KLTs)

• Thread management
is done by the kernel

• no thread
management is done
by the application

Kernel-Level Threads (KLTs)

Advantages

• The kernel can
simultaneously schedule
multiple threads from the
same process on multiple
processors

• If one thread in a process
is blocked, the kernel can
schedule another thread
of the same process

• Kernel routines can be
multithreaded

Disadvantages

• The transfer of control
from one thread to
another within the same
process requires a mode
switch to the kernel

Implementing Threads
in Kernel Space

• Kernel knows about and manages the
threads

• No runtime is needed in each process

• Creating/destroying/(other thread
related operations) a thread involves a
system call

Implementing Threads
in Kernel Space

Advantages

• When a thread blocks
(due to page fault or
blocking system calls)
the OS can execute
another thread from
the same process

Disadvantages

• Scalability
( operating systems
had limited memory
dedicated to them )

• Cost of system call is
very high

Disagree because if you want to implement
interruption to do thread scheduling you
have to use “signal(SIGVTALARM)” which
is much more expensive.

User-Level Threads (ULT)

• All thread management is
done by the application

• Initially developed to run
on kernels that are not
multithreading capable.

• The kernel is not aware of
the existence of threads

Implementing Threads
in User Space

• Threads are implemented by a library

• Kernel knows nothing about threads

• Each process needs its own private thread
table in userspace

• Thread table is managed by the runtime
system

User-Level Threads (ULTs)
• The kernel continues to schedule the process

as a unit and assigns a single execution state .

User-Level Threads (ULTs)

Advantages

• Thread switch does not
require kernel-mode.

• Scheduling (of threads)
can be application
specific.

• Can run on any OS.

• Scales better.

Disadvantages

• A system-call by one
thread can block all
threads of that process.

• Page fault blocks the
whole process.

• In pure ULT,
multithreading cannot
take advantage of
multiprocessing.

Combined (Hybrid) Approach

• Thread creation is done
completely in user space.

• Bulk of scheduling and
synchronization of
threads is by the
application (i.e. user
space).

• Multiple ULTs from a
single application are
mapped onto (smaller or
equal) number of KLTs.

• Solaris is an example

PCB vs TCB
• Process Control Block handles global process resources

• Thread Control Block handles thread execution resources

• pids vs. tid

Different Naming Conventions

• Thread Models are also knows as general
ratio of user threads over kernels
threads

• 1:1 : each user thread == kernel thread

• M:1 : user level thread mode

• M:N : hybrid model

How are threads created ?

Assuming 1:1 model:
a) Allocates a new stack via malloc
b) Calls clone() to create a new

schedulable thread
c) Sets the threads stack pointer to (a)
d) Calls (*start_routine)(arg)

int pthread_create(pthread_t *thread,

const pthread_attr_t *attr,

void *(*start_routine) (void *),

void *arg );

Thread State Model:

• What changes to the state model in a kernel
based thread model ?

• Really replace “process” with “thread” and you
are basically there.

• Often we interchangeably use thread and
process scheduling.

Thread

#> sed –e “s/[P|p]rocess/thread/g”

Context Switch

• Scenarios:
1) Current process (or thread) blocks OR
2) Preemption.

• Operation(s) to be done
– Must release CPU resources (registers)
– Requires storing “all” non privileged registers

to the PCB or TCB save area
– Tricky as you need registers to do this
– All written in assembler
– Typically an architecture has a few privileged

registers so the kernel can accomplish this

0xFFFFFFFF
int call_io()
{

char buffer[128];
return read(0,buffer,128);

}

main() {
call_io();

}

main

get_buf

userstack

User Space

Kernel Space
int sys_read()
{

:
:
wait_for_comp()

}

Process

syscall_table

IntrService

asm(“trap”)

Marshall arguments + #sys-call-readGlibc_read

kernelstack

Save Registers
Call Scheduler
Restore Registers

Task struct

prio, proc,
memmaps

Reg_save_area

CtxSwitch: Process Blocks

1

2

3
4

5

0xFFFFFFFF

User Space

Kernel Space

int intr_timer
{

Save Registers
Call Scheduler
Restore Regs

}

IntrService
timerstack

Task struct

prio, proc,
memmaps

Reg_save_area

Task struct

prio, proc,
memmaps

Reg_save_area

int intr_timer
{

Save Registers
Call Scheduler
Restore Regs

}

timerstack

CtxSwitch: Preemption

2
1 3

4 5

67

Conclusions

• Process is one the most central concepts in
Operating Systems

• Process vs. Thread (understand difference)
– Process is a resource container with at least one

thread of execution
– Thread is a unit of execution that lives in a process

(no thread without a process)
– Threads share the resources of the owning process.

• Multiprogramming vs multithreading