ソフトウェアエンジニアの技術ブログ：Software engineer tech blog

“to solve mutual exclusion problems among concurrent threads”

Birrell’s mechanisms: Pthreads:

-mutex
pthread_mutex_t aMutex; // mutex type
-Lock(mutex)
// explicit lock
int pthread_mutex_lock(pthread_mutex_t
*mutex);
// explicit unlock
int pthread_mutex_unlock(pthread_mutex_t
*mutex);

Other mutex operation

int pthread_mutex_init(pthread_mutex_t *mutex,
	const pthread_mutexattr_t *attr);
// mutex attributes == specifies mutex behavior when
// a mutex is shared among processes

int pthread_mutex_trylock(pthread_mutex_t *mutex);
-shared data should always be accessed through a single mutex
-mutex scope must be visible to all
-globally order lock
for all threads, lock mutexes in order
-always unlock a mutex
always unlock the correct mutex

Pthread Condition Variables
-condition
pthread_cond_t aCond; // type of cond variable
-wait
int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex)
-signal
int pthread_cond_signal(pthread_cond_t *cond);
-broadcast
int pthread_cond_broadcast(pthread_cond_t *cond);

int pthread_cond_init(pthread_cond_t *cond,
	const pthread_condattr_t *attr);
// attributes --e.g., if it's shared

int pthread_cond_destory(pthread_cond_t *cond);

#include 
#include 
#define NUM_THREADS 4

void *threadFunc (void *arg){
	int *p = (int*)pArg;
	int myNum = *p;
	printf("Thread number %d\n", myNum);
	return 0;
}

int main(void){
	int i;
	pthread_t tid[NUM_THREADS];
	for (i=0; i < NUM_THREADS; i++){ /* create/fork threads */
		pthread_create(&tid[i], NULL, threadFunc, &i);
	}
	for (i=0; i < NUM_THREADS; i++){
		pthread_join(tid[i], NULL);
	}
	return 0;
}

#include <stdio.h>
#include <pthread.h>

void *foo (void *arg){
	printf("Foobar!\n");
	pthread_exit(NULL);
}

int main(void){

	int i;
	pthread_t tid;

	pthread_attr_t attr;
	pthread_attr_init(&attr);
	pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
	pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSYEM);
	pthread_create(NULL, &attr, foo, NULL);

	return 0;
}

Compiling PThreads
1. #include in main file
2. compile source with -lpthread or -pthread
Intro to OS ~ ==> gcc -o main main.c -lpthread
3. check return values of common functions

#include 
#include 
#define NUM_THREADS 4

void *hello (void *arg){
	printf("Hello Thread\n");
	return 0;
}

int main(void){
	int i;
	pthread_t tid[NUM_THREADS];
	for (i=0; i < NUM_THREADS; i++){ /* create/fork threads */
		pthread_create(&tid[i], NULL, hello, NULL);
	}
	for (i=0; i < NUM_THREADS; i++){
		pthread_join(tid[i], NULL);
	}
	return 0;
}

PThread == POSIX Threads
POSIX == Portable Operating System Interface
POSIX Thread
– POSIX versions of Birrell’s API
– specifies syntax and semantics of the operations

Thread, Fork(proc, args), Join(thread)

pthread_t aThread;
int pthread_create(pthread_t *thread,
	const pthread_attr_t *attr,
	void * (*start_routine)(void *)
	void *arg);
int pthread_join(pthread_t thread,
	void **status);

stack size, inheritance, joinable, scheduling policy, priority, system/process scope

Condition type

Wait(mutex, cond)
– mutex is automatically released z re-acquired on wait
Signal(cond)
– notify only one thread waiting on condition
Broadcast(cond)
– notify all waiting threads

Can be accessed by reading shared variable

create new list element element
set e.value = X
read list and list.p_next
set e.pointer = list.p_next
set list.p_next = e

Mutex, Lock(mutex), blocked_threads

List<int> my_list;
Mutex m;
void safe_insert(int i){
	Lock(m){
		my_list.insert(i);
	}
}

for i=0..10
	producers[i] = fork(safe_insert, NULL)
consumer = fork(print_and_clear, my_list)

Lock(m){
	list->insert(my_thread_id)
} // unlock

Lock(m){
	if my_list.full -> print; clear up to limit of elements of list
	else -> release lock and try again (later)
}

Condition Variable

Lock(m){
	while (my_list.not_full())
Wait(m. list_full);
	m_list.print_and_remove_all();
}

Lock(m){
	my_list.insert(my_thread_id);
	if my_list.full()
		Signal(list_full);
}

Thread data structure
– identify threads, keep track of resource usage…
mechanisms to create and manage threads
mechanisms to safely coordinate among threads
running concurrently in the same address space

Processes, Threads
VA_p1, VA_p2

Concurrency Control & Coordination
-Mutual Exclusion
exclusive access to only one thread at a time
-Mutex

waiting on other threads
– specific condition before proceeding

Threads and Thread creation

Thread type
– thread data structure

Fork(proc, args)
– create a thread
– not unix fork

Join(thread)
^ terminate a thread

Thread thread1;
Shared_list list;
thread1 = fork(safe_insert, 4);
safe_insert(6);
join(thread1); // Optional

ready queue -> cpu
I/O <- I/O queue <- I/O request time slice expired, fork a child, wait for an interrupt Scheduler Responsibility - maintaining the ready queue - decision on when to context switch P1(web server) P2(Database) mm, cpu Inter Process communication IPC mechanisms -transfer data/info between address spaces -maintain protection and isolation Threads to the rescue! threads -> multithreaded process -> core1, core2, core3 …

parallelization => speed up
specialization => hot cache!
efficiency => lower mm requirement & cheaper IPC

Are threads useful on a signle CPU?
or when (#of Threads) > (# of CPUs)?
t_ctx_switch -> t_idle -> t_ctx_switch

State of execution
-program counter, stack
Parts & temporary holding area
May require special hardware
-I/O devices

What is a process?
OS manages hardware on behalf of applications
application == program of disk, flash memory(static entity)

process == state of a program when executing loaded in memory(active entity)

What does a process look like?
stack, heap, data, text

address space == “in memory”
representation of a process
physical addresses: locations in physical memory

How does the OS know what a process is doing?
-program counter
-cpu registers
-stack pointer

Process Control Block(PCB)
registers
memory limits
list of open files
priority
signal mask
CPU scheduling info

-PCB created when process is created
-Certain fields are updated when process state changes
-Other fields change too frequently

CPU process
running, ready state

mechanisms for process creation
-fork == copies the parent PCB into new child PCB
child continues execution at instruction after fork
-exec == replace child image, load new program and start from first instr.

unix-based os, the parent of all process: init
the parent of all app processes: zygote

OS must
-preempt
-schedule
-dispatch

User process, kernel

to make a system call an application must
– write argoments
– save relevant data at well-defined location
– make system call

User/Kernel Transitions
・hardware supported
e.g. traps on illegal instructions or memory accesses requiring special privilege
・involves a number of insturctions
e.g. -50-100ns on a 2GHz machine running Linux
・switches locality
-> affects hardware cache

・process management
・file management
・device management

kill
setgid
mount
sysctl

monolithic OS
+everthing included, inlining, compile time optimizations
-customization, portability, manageability, momory footprint, performance

module OS
-operating system, module(Interface)

Microkernel
operating system, address space, threads

Linux architecture
Hardware(cpu, memory, disks, terminal), Linux operating system(process management, memory management, the file system;I/O, etc), standard library(open, close, read, write, fork, etc), standards utility programs(shell, editor, compilers, etc), users