Transcript Threads - BYU Computer Science Students Homepage Index

Today…



Project 1 (Shell) due today
Homework #2 due Friday (January 30)
Questions…
BYU CS 345
Threads
1
Control Tables
7. Operating System Control Tables
Task Control Block
BYU CS 345
Chapter 3 - Processes
2
P2 - Tasking
Task Control Block (tcb)
// task control block
typedef struct
{
char* name;
int (*task)(int,char**);
int state;
int priority;
int argc;
char** argv;
int signal;
void (*sigContHandler)(void);
void (*sigIntHandler)(void);
void (*sigKillHandler)(void);
void (*sigTermHandler)(void);
void (*sigTstpHandler)(void);
TID parent;
int RPT;
int cdir;
Semaphore *event;
void* stack;
jmp_buf context;
} TCB;
BYU CS 345
//
//
//
//
//
//
//
task
task
task
task
task
task
task
control block
name
address
state
priority (P2)
argument count (P1)
argument pointers (P1)
//
//
//
//
//
//
task
task
task
task
task
task
signals (P1)
mySIGCONT handler (P1)
mySIGINT handler (P1)
mySIGKILL handler (P1)
mySIGTERM handler (P1)
mySIGTSTP handler (P1)
//
//
//
//
//
//
task parent
task root page table (P4)
task directory (P6)
blocked task semaphore (P2)
task stack (P2)
task context pointer (P2)
Chapter 3 - Processes
3
Processes and Threads
Chapter 4
CS 345
Stalling’s Chapter
#
Project
1: Computer System Overview
2: Operating System Overview
4
P1: Shell
3: Process Description and Control
4: Threads
4
P2: Tasking
5: Concurrency: ME and Synchronization
6: Concurrency: Deadlock and Starvation
6
P3: Jurassic Park
7: Memory Management
8: Virtual memory
6
P4: Virtual Memory
9: Uniprocessor Scheduling
10: Multiprocessor and Real-Time Scheduling
6
P5: Scheduling
11: I/O Management and Disk Scheduling
12: File Management
8
P6: FAT
Student Presentations
6
BYU CS 345
Threads
5
Chapter 4 Learning Outcomes






Understand the distinction between process and thread.
Describe the basic design issues for threads.
Explain the difference between user-level threads and
kernel-level threads.
Describe the thread management facility in Windows 7.
Describe the thread management facility in Solaris.
Describe the thread management facility in Linux.
BYU CS 345
Threads
6
Questions…
1.
2.
3.
4.
5.
6.
7.
8.
What is a Process?
What is a Thread?
What are the different types of Threads?
What are the benefits of Threads?
What are possible Thread States?
What is a RPC?
How are Threads managed?
How are ULT’s created in C?
BYU CS 345
Threads
7
What is moving around?
BYU CS 345
Threads
8
Processes
1. What is a Process?


Traditionally, a process is considered an
instance of a computer program that is being
executed.
A process contains



System resources: program code, user data, buffers,
devices, I/O channels, files
Current activity: CPU, registers, state, execution
path, “On the clock”, interleaved with other processes
Can resources and CPU activity be treated
independently?


Unit of resource ownership  process or task
Unit of execution  thread or lightweight process
BYU CS 345
Threads
9
Processes
Processes

Resources owned by a process:







code ("text"),
data (VM),
stack,
heap,
files,
tables (signals, semaphores, buffers, I/O,…)
Context switching processes has a significant
amount of overhead:


Tables have to be flushed from the processor when
context switching.
Processes share information only through pipes and
shared memory.
BYU CS 345
Threads
10
Threads
2. What is a Thread?

A thread of execution


Threads reduce overhead by sharing the
resources of a process.



Smallest unit of processing that can be scheduled by an
operating system
Switching can happen more frequently and efficiently.
Sharing information is not so "difficult" anymore everything can be shared.
A Thread is an independent program counter
operating within a process.


Sometimes called a lightweight process (LWP)
A smaller execution unit than a process.
BYU CS 345
Threads
11
Threads
Threads and Processes
one process
one thread
multiple processes
one thread per process
BYU CS 345
one process
multiple threads
multiple processes
multiple threads per process
Threads
12
Threads
Multi-threading

Operating system or user may support multiple
threads of execution within a single process.



Traditional approach is single process, single
threaded.
Current support for mult-process, mult-threading.
Examples:




MS-DOS: single user process, single thread.
UNIX: multiple processes, one thread per process.
Java run-time environment: one process, multiple
threads.
Windows 2000 (W2K), Solaris, Linux, Mach, and
OS/2: multiple processes, each supports multiple
threads.
BYU CS 345
Threads
13
Threads
3. What Types of Threads?

There are two types of threads:



A thread consists of:







User-space (ULT) and
Kernel-space (KLT).
a thread execution state (Running, Ready, etc.)
a context (program counter, register set.)
an execution stack.
some per-tread static storage for local variables.
access to the memory and resources of its process (shared with
all other threads in that process.)
OS resources (open files, signals, etc.)
Thus, all of the threads of a process share the state and
resources of the parent process (memory space and code
section.)
BYU CS 345
Threads
14
Threads
4. What are the Benefits of Threads?

A process has at least one thread of execution



May launch other threads which execute concurrently
with the process.
Threads of a process share the instructions (code) and
process context (data).
Key benefits:





Far less time to create/terminate.
Switching between threads is faster.
No memory management issues, etc.
Can enhance communication efficiency.
Simplify the structure of a program.
BYU CS 345
Threads
15
Threads
Multi-threaded Process
Thread 1
Thread 2
Thread 3
Spawn additional threads
Sync
Sync
(a) Task graph of a program
BYU CS 345
(b) Thread structure of a task
Threads
16
Threads
Exclusive/Shared Resources
Multithreaded
Process Model
Single-Threaded
Process Model
Process
Control
Block
User
Address
Space
BYU CS 345
Thread
Thread
Thread
Control
Block
Thread
Control
Block
Thread
Control
Block
Process
Control
Block
User
Stack
User
Stack
User
Stack
User
Address
Space
Kernel
Stack
Kernel
Stack
Kernel
Stack
User
Stack
Kernel
Stack
Thread
Threads
17
Threads
Using Threads

Multiple threads in a single process




Separate control blocks for the process and each thread
Can quickly switch between threads
Can communicate without invoking the kernel
Four Examples




Foreground/Background – spreadsheet updates
Asynchronous Processing – Backing up in background
Faster Execution – Read one set of data while processing
another set
Organization – For a word processing program, may allow one
thread for each file being edited
BYU CS 345
Threads
18
Threads
5. What are Possible Thread States?

Thread operations





Generally, it is desirable that a thread can block
without blocking the remaining threads in the
process


Spawn – Creating a new thread
Block – Waiting for an event
Unblock – Event happened, start new
Finish – This thread is completed
Allow the process to start two operations at once, each thread
blocks on the appropriate event
Must handle synchronization between threads


System calls or local subroutines
Thread generally responsible for getting/releasing locks, etc.
BYU CS 345
Threads
19
RPC’s
6. What is a RPC?
1. Client calls the client stub (stack).
2. Client stub packs (marshalls) parameters.
3. Client's OS sends message to server.
4. Server OS passes packets to server stub.
5. Server stub unpacks (unmarshalls) message.
6. Server stub calls the server procedure.
7. Reply traces in the reverse direction.
“A remote procedure call (RPC) is an interprocess communication that allows a computer
program to cause a subroutine or procedure to
execute in another address space (commonly on
another computer on a shared network) without
the programmer explicitly coding the details for
this remote interaction.”
BYU CS 345
Threads
20
Thread Issues
7. How are Threads Managed?

How should threads be scheduled compared to
processes?



How are threads implemented?



Equal to processes
Within the parent processes quantum
kernel support (system calls)
user level threads
What about mutual exclusion?


Process resources are shared
Data coherency
BYU CS 345
Threads
21
ULT’s
8. User-Level Threads

User-level avoids the kernel and manages the
tables itself.




Often this is called "cooperative multitasking" where
the task defines a set of routines that get "switched
to" by manipulating the stack pointer.
Typically each thread "gives-up" the CPU by calling
an explicit switch, sending a signal or doing an
operation that involves the switcher.
Also, a timer signal can force switches.
User threads typically can switch faster than kernel
threads [however, Linux kernel threads' switching is
actually pretty close in performance].
BYU CS 345
Threads
22
ULT’s
User-Level Threads

Disadvantages.




User-space threads have a problem that a single thread can
monopolize the timeslice thus starving the other threads within
the task.
Also, it has no way of taking advantage of SMPs (Symmetric
MultiProcessor systems, e.g. dual-/quad-Pentiums).
Lastly, when a thread becomes I/O blocked, all other threads
within the task lose the timeslice as well.
Solutions/work arounds.



Timeslice monopolization can be controlled with an external
monitor that uses its own clock tick.
Some SMPs can support user-space multithreading by firing up
tasks on specified CPUs then starting the threads from there
[this form of SMP threading seems tenuous, at best].
Some libraries solve the I/O blocking problem with special
wrappers over system calls, or the task can be written for
nonblocking I/O.
BYU CS 345
Threads
23
KLT’s
Kernel-Level Threads

KLTs often are implemented in the kernel using several
tables (each task gets a table of threads).



The kernel schedules each thread within the timeslice of each
process.
There is a little more overhead with mode switching from user>kernel-> user and loading of larger contexts, but initial
performance measures indicate a negligible increase in time.
Advantages.



Since the clocktick will determine the switching times, a task is
less likely to hog the timeslice from the other threads within the
task.
I/O blocking is not a problem.
If properly coded, the process automatically can take advantage
of SMPs and will run incrementally faster with each added CPU.
BYU CS 345
Threads
24
Thread Management
User-Level and Kernel-Level Threads
BYU CS 345
Threads
25
Thread Management
Thread Management

Some implementations support both ULT and
KLT threads.





Can take advantage of each to the running task.
Since Linux's kernel-space threads nearly perform as
well as user-space, the only advantage of using userthreads would be the cooperative multitasking.
OS system calls could each be written as a
thread or OS could be single threaded.
Advantages: Speed and Concurrency
Disadvantages: Mutual exclusion and complexity
BYU CS 345
Threads
26
Thread Problems

In many other multithreaded OSs, threads are not
processes merely parts of a parent task.



Therefore, if a thread calls fork()’s or execve()'s some external
program, the whole task could be replaced.
The POSIX 1c standard defines a thread calling fork() to
duplicate only the calling thread in the new process; and an
execve() from a thread would stop all threads of that process.
Having two different implementations and schedulers for
processes is a flaw that has perpetuated from
implementation to implementation.


Some multitasking OSs have opted not to support threads due
to these problems (not to mention the effort needed to make the
kernel and libraries 100% reentrant).
For example, Windows NT opts not to support POSIX-compliant
threads (Windows NT does support threads but they are not
POSIX compliant).
BYU CS 345
Threads
27
Thread Problems

Most people have a hard enough time understanding
tasks.




“Chopped up tasks" or threads is difficult to envision.
"What can be threaded in my app?".
Deciding what to thread can be very laborious.
Another problem is locking.




All the nightmares about sharing, locking, deadlock, race
conditions, etc. come vividly alive in threads.
Processes don't usually have to deal with this, since most
shared data is passed through pipes.
Threads can share file handles, pipes, variables, signals, etc.
Test and duplicate error conditions can cause more gray hair
than a wayward child.
BYU CS 345
Threads
28
Thread Support

As of 1.3.56, Linux has supported kernel-level
multithreading.




User-level thread libraries around as early as 1.0.9.
On-going effort to refine and make the kernel more
reentrant.
With the introduction of 2.1.x, the memory space is
being revised so that the kernel can access the user
memory more quickly.
Windows NT opts not to support POSIXcompliant threads (Windows NT does support
threads but they are not POSIX compliant).
BYU CS 345
Threads
29
C Threads
Thread Review

How does a thread differ from a process?



Resource ownership
Smallest unit of processing that can be scheduled by
an operating system
What are the implications of having an
independent program counter?
Each thread has its own stack.
 Code and global data belong to the process and are
shared among threads.
 Threads “own” local data.
Thread state is defined by processor registers and the
stack.


BYU CS 345
Threads
30
Project 2 - Tasking
P2 - Tasking
Project 2

Change the scheduler from a 2 state to a 5 state
scheduler using semaphores with priority queues.






int scheduler() in os345.c
semWait(), semSignal, semTryLock in os345semaphores.c
Tasks are functions and are added to the task scheduler
ready queue via the “createTask()” function.
The first task scheduled is your shell from Project 1.
The “SWAP” directive replaces clock interrupts for context
switching between tasks (cooperative scheduling).
Context switching directives may be placed anywhere in
your user task code.

SWAP, SEM_SIGNAL, SEM_WAIT, SEM_TRYLOCK
BYU CS 345
Project 2 - Tasking
32
P2 - Tasking
Project 2 (continued…)




The highest priority, unblocked, ready task should always
be executing.
Tasks of the same priority should be scheduled in a
round-robin, FIFO fashion.
Any change of events (SEM_SIGNAL) should cause a
context switch.
To simulate interrupts, character inputs and timers need
to be “polled” in the scheduling loop.


void pollInterrupts() in OS345p1.c
Parsed command line arguments are passed to tasks (ie.
functions) via argc/argv variables.
BYU CS 345
Project 2 - Tasking
33
P2 - Tasking
Step 1: Priority Queue

Create a priority queue




typedef int TID;
// task ID
typedef int Priority;
// task priority
typedef int* PQueue;
// priority queue
PQueue rq;
// ready queue
rq = (int*)malloc(MAX_TASKS * sizeof(int));
rq[0] = 0;
// init ready queue
Priority/TID
Priority/TID
int enQ(PQueue q, TID tid, Priority p);
q
tid
p
int

Priority/TID
# of entries
Queue functions

Priority/TID
priority queue (# | pr1/tid1 | pr2/tid2 | …)
task id
task priority
return tid
int deQ(PQueue q, TID tid);
q
tid
int
BYU CS 345
priority queue
find and delete tid from q
(tid == -1  find/delete highest priority)
deleted tid
(tid == -1  q empty or task not found)
Project 2 - Tasking
rq[5]
rq[4]
10 / 3
rq[3]
5/2
rq[2]
5/0
rq[1]
2/1
rq[0]
4
34
P2 - Tasking
Step 2: Schedule w/Ready Queue

Create a ready priority queue


Add new task to ready queue in createTask



PQueue rq;
// ready queue
rq = (int*)malloc(MAX_TASKS * sizeof(int));
rq[0] = 0;
// init ready queue
enQ(rq, tid, tcb[tid].priority);
NOTE: priority count be internal to enQ/deQ
Change scheduler() to deQueue and then
enQueue next task
if ((nextTask = deQ(rq, -1)) >= 0)
{
enQ(rq, nextTask);
}
BYU CS 345
Project 2 - Tasking

Priority/TID
Priority/TID
Priority/TID
Priority/TID
# of entries
rq[5]
rq[4]
10 / 3
rq[3]
5/2
rq[2]
5/0
rq[1]
2/1
rq[0]
4
35
P2 - Tasking
2-State Scheduler
createTask()
New
Ready
Queue
dispatch()
killTask()
Running
Exit
swapTask()
nextTask = enQueue(rq, deQueue(rq, -1));
BYU CS 345
Project 2 - Tasking
36
P2 - Tasking
Step 3: 5-State Scheduling

Add priority queue to semaphore struct



// semaphore
// link to next semaphore
// semaphore name (malloc)
// state (count)
// type (binary/counting)
// tid of creator
// blocked queue
Malloc semaphore queue in createSemaphore


typedef struct semaphore
{
struct semaphore* semLink;
char* name;
int state;
int type;
int taskNum;
PQueue q;
} Semaphore;
semaphore->q = (int*)malloc(MAX_TASKS * sizeof(int));
semaphore->q[0] = 0;
// init queue
semWait: deQueue current task from ready queue and
enQueue in semaphore queue
semSignal: deQueue task from blocked queue and
enQueue in ready queue.
BYU CS 345
Project 2 - Tasking
37
P2 - Tasking
5-State Scheduler
#define
#define
#define
#define
New
SWAP
SEM_WAIT(s)
SEM_SIGNAL(s)
SEM_TRYLOCK(s)
createTask()
Ready
Queue
swapTask();
semWait(s);
semSignal(s);
semTryLock(s);
dispatch()
Running
swapTask()
killTask()
Exit
Blocked
Queues
BYU CS 345
Project 2 - Tasking
38
Scheduling
Task Scheduling
Scheduler / Dispatcher
Ready Priority Queue
Executing
SWAP
SEM_SIGNAL
SEM_SIGNAL
SEM_SIGNAL
Semaphore Priority Queue
Semaphore Priority Queue
Semaphore Priority Queue
SEM_WAIT
SEM_WAIT
SEM_WAIT
…
BYU CS 345
Project 2 - Tasking
39
P2 - Tasking
Step 4: Counting Semaphore



Implement counting functionality to semaphores
Add a 10 second timer (tics10sec) counting semaphore
to the polling routine (pollInterrupts). This can be done
by including the <time.h> header and calling the C
function time(time_t *timer). semSignal the tics10sec
semaphore every 10 seconds.
Create a reentrant high priority task that blocks
(SEM_WAIT) on the 10 second timer semaphore
(tics10sec). When activated, output a message with
the current task number and time and then block again.
BYU CS 345
Project 2 - Tasking
40
P2 - Tasking
Task Control Block (tcb)
State = { NEW, READY, RUNNING, BLOCKED, EXIT }
// task control block
Priority = { LOW, MED, HIGH, VERY_HIGH, HIGHEST }
typedef struct
// task control block
{
char* name;
// task name
int (*task)(int,char**);
// task address
int state;
// task state (P2)
int priority;
// task priority (P2)
int argc;
// task argument count (P1)
char** argv;
// task argument pointers (P1)
int signal;
// task signals (P1)
// void (*sigContHandler)(void);
// task mySIGCONT handler
void (*sigIntHandler)(void);
// task mySIGINT handler
// void (*sigKillHandler)(void);
// task mySIGKILL handler
Pending semaphore when blocked.
// void (*sigTermHandler)(void);
// task mySIGTERM handler
// void (*sigTstpHandler)(void);
// task mySIGTSTP handler
TID parent;
// task parent
int RPT;
// task root page table (P4)
int cdir;
// task directory (P6)
Semaphore *event;
// blocked task semaphore (P2)
void* stack;
// task stack (P1)
jmp_buf context;
// task context pointer (P1)
} TCB;
BYU CS 345
Project 2 - Tasking
41
P2 - Tasking
Step 5: List Tasks

Modify the list tasks command to display all tasks in the
system queues in execution/priority order indicating the
task name, if the task is ready, paused, executing, or
blocked, and the task priority. If the task is blocked, list
the reason for the block.
BYU CS 345
Project 2 - Tasking
42
P2 - Tasking
Step 6: Verification
The project2 command schedule timer tasks 1 through
9, 2 signal tasks and 2 “ImAlive” tasks. The tics10sec
task about the current time every 10 seconds in a round
robin order. The “ImAlive” tasks will periodically say
hello. The high priority “Signal” tasks should respond
immediately when semaphore signaled.

#
Task Name
Priority
Time slice
Blocking Semaphore
0
CLI w/pseudo-input interrupts
5
1
inBufferReady
1-9
TenSeconds
10
1
tics10sec
10
sTask1
20
1
sTask10
11
sTask2
20
1
sTask11
12
ImAlive
1
1
None
13
ImAlive
1
1
None
BYU CS 345
Project 2 - Tasking
43
P2 - Tasking
Step 7: Bonus Credit

Implement a buffered pseudo-interrupt driven character
output and demonstrate that it works by implementing a
my_printf function.
#include <stdarg.h>
void my_printf(char* fmt, ...)
{
va_list arg_ptr;
char pBuffer[128];
char* s = pBuffer;
va_start(arg_ptr, fmt);
vsprintf(pBuffer, fmt, arg_ptr);
while (*s) putIObuffer(*s++);
va_end(arg_ptr);
} // end my_printf

Implement time slices that adjust task execution times
when scheduled.
createTask(
"myShell",
P1_shellTask,
5,
argc,
argv
//
//
//
//
//
task
task
task
task
task
name
priority
arg count
argument pointers
);
BYU CS 345
Project 2 - Tasking
44
setjmp/longjmp
setjmp / longjmp


#include <setjmp.h>
jmp_buf struct


setjmp(jmp_buf env);



stack pointer (sp), frame pointer (fp), and program
counter (pc).
saves the program state (sp, fp, pc) in env so that
longjmp() can restore them later.
returns 0 value.
longjmp(jmp_buf env, int val);


resets the registers to the values saved in env.
longjmp() returns as if you have just called the
setjmp() call that saved env with non-zero value.
BYU CS 345
Project 2 - Tasking
45
setjmp/longjmp
Multi-tasking in C
BYU CS 345
Project 2 - Tasking
46
createTask
Creating a Task
int createTask(
{
char* name,
int (*task)(int, char**),
int priority,
int argc,
char* argv[ ])
// task name
// task address
// task priority
// task argument count
// task argument pointers
int tid, j;
for(tid=0; tid<MAX_TASKS; tid++)
{
if(tcb[tid].name[0] == 0) break;
// find an open tcb entry slot
}
if(tid == MAX_TASKS) return -1;
// too many tasks
strncpy(tcb[tid].name, name, MAX_NAME_SIZE-1);
// task name
tcb[tid].task = task;
// task address
tcb[tid].state = S_NEW;
// NEW task state
tcb[tid].priority = priority;
// task priority
tcb[tid].parent = curTask;
// parent
tcb[tid].argc = argc;
// argument count
// ?? malloc new argv parameters (Project 1)
tcb[tid].argv = argv;
// argument pointers
BYU CS 345
Project 2 - Tasking
47
createTask
Creating a Task (continued…)
tcb[tid].event = 0;
// suspend semaphore
tcb[tid].RPT = 0;
// root page table (project 5)
tcb[tid].cdir = cDir;
// inherit parent cDir (project 6)
// allocate own stack and stack pointer
tcb[tid].stack = malloc(STACK_SIZE * sizeof(int));
// signals
tcb[tid].signal = 0;
// Project 1
if (tid)
{
tcb[tid].sigIntHandler = tcb[curTask].sigIntHandler;
// SIGINT handler
}
else
{
tcb[tid].sigIntHandler = defaultSigIntHandler;
// default
}
// ?? inserting task into "ready" queue (Project 2)
return tid;
} // end createTask
BYU CS 345
// return tcb index (curTask)
Project 2 - Tasking
48
SWAP
SWAP (Context Switch)
// ***********************************************************************
// Do a context switch to next task.
// 1. Save the state of the current task and enter kernel mode.
// 2. Return from here when task is rescheduled.
void swapTask()
{
swapCount++;
// increment swap cycle counter
if(setjmp(tcb[curTask].context)) return;
// resume execution of task
// task context has been saved in tcb
// if task RUNNING, set to READY
if(tcb[curTask].state == S_RUNNING) tcb[curTask].state = S_READY;
longjmp(k_context, 2);
} // end swapTask
BYU CS 345
// kernel context
Project 2 - Tasking
49
Scheduling
Task Scheduling
// ***********************************************************************
// scheduler
int scheduler()
{
int i, t, nextTask;
if (numTasks == 0) return -1;
// no task ready
nextTask = rq[0];
// take 1st (highest priority)
for (i = 0; i < (numTasks-1); ++i)
// roll to bottom of priority (RR)
{
if (tcb[rq[i]].priority > tcb[rq[i+1]].priority) break;
t = rq[i];
rq[i] = rq[i+1];
rq[i+1] = t;
}
return nextTask;
// return task # to dispatcher
} // end scheduler
BYU CS 345
Project 2 - Tasking
50
Project 2
Task Dispatching
int dispatcher(int curTask)
{ int result;
switch(tcb[curTask].state)
// schedule task
{ case S_NEW:
tcb[curTask].state = S_RUNNING;
// set task to run state
if(setjmp(k_context)) break;
// context switch to new task
temp = (int*)tcb[curTask].stack + (STACK_SIZE-8);
SET_STACK(temp)
// move to new stack
result = (*tcb[curTask].task)(tcb[curTask].argument);
tcb[curTask].state = S_EXIT;
// set task to exit state
longjmp(k_context, 1);
// return to kernel
case S_READY:
tcb[curTask].state = S_RUNNING;
// set task to run
case S_RUNNING: if(setjmp(k_context)) break;
if (signals()) break;
longjmp(tcb[curTask].context, 3);
// return from task
case S_EXIT:
// if CLI, then quit scheduler
// kill current task
if(curTask == 0) return -1;
syskillTask(curTask);
case S_BLOCKED: break;
// blocked / exit state
}
return 0;
} // end dispatcher
BYU CS 345
// restore task context
Project 2 - Tasking
51
Project 2
Project 2 Grading Criteria






5 pts – Replace the simplistic 2-state scheduler with a 5-state, preemptive,
prioritized, round-robin scheduler using ready and blocked task
queues. (Be sure to handle the SIGSTOP signal.)
3 pts – Implement counting semaphores within the semSignal, semWait, and
semTryLock functions. Add blocked queues to your semSignal and
semWait semaphore functions. Validate that the SEM_SIGNAL /
SEM_WAIT / SEM_TRYLOCK binary and counting semaphore
functions work properly with your scheduler.
2 pts – Modify the createTask( ) function to malloc argv arguments and insert
the new task into the ready queue. Implement the killTask( ) function
such that individual tasks can be terminated and resources recovered.
2 pts – Add a 10 second timer (tics10sec) counting semaphore to the polling
routine (pollInterrupts). This can be done by including the <time.h>
header and calling the C function time(time_t *timer). semSignal the
tics10sec semaphore every 10 seconds.
2 pts – Modify the list tasks command to display all tasks in the system
queues in execution/priority order indicating the task name, if the task
is ready, paused, executing, or blocked, and the task priority. If the
task is blocked, list the reason for the block.
1 pt – Create a reentrant high priority task that blocks (SEM_WAIT) on the
10 second timer semaphore (tics10sec). When activated, output a
message with the current task number and time and then block again.
BYU CS 345
Project 2 - Tasking
52
Project 2
Project 2 Grading Criteria

5 pts – Upon entering main, schedule your CLI as task 0. Have the project2
command schedule timer tasks 1 through 9 and observe that they are
functioning correctly. The “CLI” task blocks (SEM_WAIT) on the
binary semaphore inBufferReady, while the “TenSeconds” tasks block
on the counting semaphore tics10sec. The “ImAlive” tasks do not
block but rather immediately swap (context switches) after
incrementing their local counters. The high priority “Signal” tasks
should respond immediately when semaphore signaled.
#
Task Name
Priority
Time slice
Blocking Semaphore
0
CLI w/pseudo-input interrupts
5
1
inBufferReady
1-9
TenSeconds
10
1
tics10sec
10
sTask1
20
1
sTask10
11
sTask2
20
1
sTask11
12
ImAlive
1
1
None
13
ImAlive
1
1
None
BYU CS 345
Project 2 - Tasking
53
Project 2
Project 2 Grading Criteria

In addition to the possible 20 points, the following
bonus/penalties apply:




+2 pts – bonus for early pass-off (at least one day before due date.)
+2 pts – for implementing buffered pseudo-interrupt driven
character output and demonstrate that it works by
implementing a my_printf function.
+1 pt – for implementing time slices that adjust task execution
times when scheduled.
–2 pts – penalty for each school day late.
BYU CS 345
Project 2 - Tasking
54
Project 2
Project 2 Bonus Points

Buffered pseudo-interrupt driven character output –
my_printf
#include <stdarg.h>
void my_printf(char* fmt, ...)
{
va_list arg_ptr;
char pBuffer[128];
char* s = pBuffer;
va_start(arg_ptr, fmt);
vsprintf(pBuffer, fmt, arg_ptr);
while (*s) putchar(*s++);
va_end(arg_ptr);
} // end my_printf
BYU CS 345
Project 2 - Tasking
55
Project 2
Project 2 Bonus Points

Task time slices
// schedule shell task
createTask( "myShell",
//
P1_shellTask, //
5,
//
4,
//
argc,
//
argv
//
);
BYU CS 345
task
task
task
task
task
task
Project 2 - Tasking
name
priority
time slice
arg count
argument pointers
56
BYU CS 345
Project 2 - Tasking
57
Project 2
STDARG - Variable Arguments

Usage:
#include <stdarg.h>
TYPE func(TYPE arg1,TYPE arg2, ...)
{
va_list ap;
TYPE x;
va_start(ap,arg2);
x = va_arg(ap,TYPE);
/* and so on */
va_end(ap);
}
BYU CS 345
Project 2 - Tasking
58
Project 2
VSPRINTF - Print Variable Arguments


Usage:
 #include <stdarg.h>
 #include <stdio.h>
 nout = vsprintf(str,format,varlist);
Description:




"vsprintf" is the same as "sprintf" except that it prints out a number of
values from a variable argument list. The "varlist" variable must have
been initialized with the "va_start" macro.
If there have already been calls to "va_arg" to obtain arguments from the
variable list, "vsprintf" will start at the first argument that has not yet been
obtained through "va_arg".
"vsprintf" effectively uses "va_arg" to obtain arguments from the variable
list; therefore a call to "va_arg" after "vsprintf" will obtain the argument
AFTER the last argument printed.
After a call to "vsprintf", the "varlist" variable should be assumed to be in
an undefined state. If you want to use "varlist" again, you must call
"va_end" to clean up, then "va_start" to reinitialize it.
BYU CS 345
Project 2 - Tasking
59
BYU CS 345
Project 2 - Tasking
60
SWAP (Context Switch)
// ***********************************************************************
// Do a context switch to next task.
// Save the state of the current task and return to the kernel.
// Return here when task is rescheduled.
void swapTask()
{ // increment swap cycle counter
swapCount++;
// either capture state and enter kernel mode (k_context)
// or resume execution by “return”ing
if(setjmp(tcb[curTask].context)) return;
// task context has been saved in tcb, set task state as “READY”
if(tcb[curTask].state == S_RUNNING) tcb[curTask].state = S_READY;
// enter kernel context and select highest priority ready task
longjmp(k_context, 2);
} // end swapTask
BYU CS 345
Project 2 - Tasking
61
STDARG - Variable Arguments


Usage:
#include <stdarg.h>
TYPE func(TYPE arg1,TYPE arg2, ...)
{
va_list ap;
TYPE x;
va_start(ap,arg2);
x = va_arg(ap,TYPE);
/* and so on */
va_end(ap);
}
Description:

The beginning of the function definition uses the normal format to declare arguments that are always
present. In addition, it uses an ellipsis (...) to stand for the variable part of the argument list. In its local
declarations, the function should declare a variable of the type "va_list". This type is defined with a
typedef statement in <stdarg.h>.

To begin processing the variable part of the argument list, you must issue the macro call
va_start(ap,lastparm); where "ap" is the variable of type "va_list" and "lastparm" is the last named
parameter (i.e. the one that immediately precedes the ellipsis).

To obtain an argument value from the variable part of the argument list, you use the macro call
va_arg(ap,TYPE) where TYPE is the type of value that you want to obtain from the variable part of the
argument list. The result of "va_arg" is an expression whose value is the next value from the argument
list. For example, i = va_arg(ap,int); obtains an integer from the variable part of the argument list and
assigns it to "i".

To finish processing the variable part of the argument list, you must issue the macro call va_end(ap);
You can issue "va_end", even if you have
not read
argument from the variable part of the list.62
BYU CS 345
Project
2 - every
Tasking
After issuing "va_end", you can issue "va_start" again to go back to the beginning of the list and start
VSPRINTF - Print Variable Arguments

Usage:




#include <stdarg.h>
#include <stdio.h>
nout = vsprintf(str,format,varlist);
Where:

char *str;


const char *format;


is a variable argument list consisting of the values to be printed.
int nout;


is a standard "printf" format string.
va_list varlist;


points to the string where the output will be written.
is the number of characters output (not counting the '\0' on the end of the string). If the print operation
failed for some reason, a negative number is returned.
Description:

"vsprintf" is the same as "sprintf" except that it prints out a number of values from a
variable argument list. The "varlist" variable must have been initialized with the
"va_start" macro. If there have already been calls to "va_arg" to obtain arguments
from the variable list, "vsprintf" will start at the first argument that has not yet been
obtained through "va_arg". "vsprintf" effectively uses "va_arg" to obtain arguments
from the variable list; therefore a call to "va_arg" after "vsprintf" will obtain the
argument AFTER the last argument printed.

After a call to "vsprintf", the "varlist" variable should be assumed to be in an
undefined state. If you want to use "varlist" again, you must call "va_end" to clean
up, then "va_start" to reinitialize it.
BYU CS 345
Project 2 - Tasking
63
Lab 2
Task Dispatching
int dispatcher(int curTask)
{
int result;
switch(tcb[curTask].state)
{
case S_NEW:
tcb[curTask].state = S_RUNNING;
if(setjmp(k_context)) break;
temp = (int*)tcb[curTask].stack + (STACK_SIZE-8);
SET_STACK(temp)
result = (*tcb[curTask].task)(tcb[curTask].argument);
tcb[curTask].state = S_EXIT;
longjmp(k_context, 1);
case S_READY:
tcb[curTask].state = S_RUNNING;
// schedule task
// new task, start executing
// set task to run state
// context switch to new task
// move to new stack
Calls
to Signal
handlers
// begin execution
of task
// set task
to exit state
inserted
here…
// return to kernel
// set task to run
case S_RUNNING: if(setjmp(k_context)) break;
if (signals()) break;
longjmp(tcb[curTask].context, 3);
// return from task
case S_BLOCKED: break;
// ?? Could check here to unblock task
case S_EXIT:
if(curTask == 0) return -1;
syskillTask(curTask);
break;
// if CLI, then quit scheduler
// kill current task
default:
powerDown(-1);
// problem!!
}
return 0;
} // end dispatcher
BYU CS 345
Project 2 - Tasking
// restore task context
64
Lab 2
Task Dispatching
int dispatcher(int curTask)
{
int result;
switch(tcb[curTask].state)
// schedule task
{
case S_NEW:
tcb[curTask].state = S_RUNNING;
// set task to run state
if(setjmp(k_context)) break;
// context switch to new task
temp = (int*)tcb[curTask].stack + (STACK_SIZE-8);
SET_STACK(temp)
// move to new stack
result = (*tcb[curTask].task)(tcb[curTask].argument);
tcb[curTask].state = S_EXIT;
// set task to exit state
longjmp(k_context, 1);
// return to kernel
case S_READY:
tcb[curTask].state = S_RUNNING;
case S_RUNNING: if(setjmp(k_context)) break;
if (signals()) break;
longjmp(tcb[curTask].context, 3);
// return from task
case S_EXIT:
// if CLI, then quit scheduler
// kill current task
if(curTask == 0) return -1;
syskillTask(curTask);
break;
default:
powerDown(-1);
case S_BLOCKED: break;
// restore task context
// problem!!
// NEVER HAPPEN!
}
return 0;
} // end dispatcher
BYU CS 345
// set task to run
Project 2 - Tasking
65
Step 1: Priority Queue

Create a priority queue



typedef int TID;
typedel int Priority;
typedef int* PQueue;
Priority/TID
// task ID
// task priority
// priority queue
Priority/TID
Priority/TID
Write queue functions to add/delete elements


int enQ(PQueue q, TID tid, Priority p);
int deQ(PQueue q, TID tid);

q
tid

int

BYU CS 345
# | pr1/tid1 | pr2/tid2 | …
>=0
find and delete tid from q
-1
return highest priority tid
tid
(if found and deleted from q)
-1
(if q empty or task not found)
Project 2 - Tasking
Priority/TID
# of entries
typedef struct
{ int size;
union
{ int element;
struct
{ uint8 tid;
uint8 priority;
} entry;
} queue[100];
} PQueue;
66
BYU CS 345
Project 2 - Tasking
67
P2 - Tasking
Project 2

Change the scheduler from a 2 state to a 5 state
scheduler using semaphores with priority queues.






int scheduler() in os345.c
semWait(), semSignal, semTryLock in os345semaphores.c
Tasks are functions and are added to the task scheduler
ready queue via the “createTask()” function.
The first task scheduled is your shell from Project 1.
The “SWAP” directive replaces clock interrupts for context
switching between tasks (cooperative scheduling).
Context switching directives may be placed anywhere in
your user task code.

SWAP, SEM_SIGNAL, SEM_WAIT, SEM_TRYLOCK
BYU CS 345
Project 2 - Tasking
68
P2 - Tasking
Project 2 (continued…)




The highest priority, unblocked, ready task should always
be executing.
Tasks of the same priority should be scheduled in a
round-robin, FIFO fashion.
Any change of events (SEM_SIGNAL) should cause a
context switch.
To simulate interrupts, character inputs and timers need
to be “polled” in the scheduling loop.


void pollInterrupts() in OS345p1.c
Parsed command line arguments are passed to tasks (ie.
functions) via argc/argv variables.
BYU CS 345
Project 2 - Tasking
69
Project 2 Assignment
Step 1: Priority Queue

Create a priority queue




Priority/TID
typedef int TID;
// task ID
typedel int Priority;
// task priority
typedef int* PQueue;
// priority queue
PQueue rq;
// ready queue
rq = (int*)malloc(MAX_TASKS * sizeof(int));
rq[0] = 0;
// init ready queue
Queue functions



q
tid

int
BYU CS 345
Priority/TID
Priority/TID
# of entries
rq[5]
int enQ(PQueue q, TID tid, Priority p);
int deQ(PQueue q, TID tid);

Priority/TID
# | pr1/tid1 | pr2/tid2 | …
>=0
find and delete tid from q
-1
return highest priority tid
tid
(if found and deleted from q)
-1
(if q empty or task not found)
Project 2 - Tasking
rq[4]
10 / 3
rq[3]
5/2
rq[2]
5/0
rq[1]
2/1
rq[0]
4
70
C Threads
State Change in C






The setjmp/longjmp set of macros implemented in the C
provide the perfect platform to perform complex flow-control.
The setjmp function saves the state of a program. The state
of a program, to be precise, are the values of sp (stack
pointer), fp (frame pointer), pc (program counter).
A program state is completely defined by this set of registers
and the contents of the memory, which includes the stack.
Executing a setjmp returns 0 after saving the stack
environment.
If setjmp returns as a result of a longjmp call, the value is the
argument of the longjmp (0 is never returned).
A call to longjmp restores the saved environment and returns
control to the point just after the corresponding setjmp call.
BYU CS 345
Project 2 - Tasking
71
Project 2 Assignment
Step 2: Schedule w/Ready Queue

Create a ready priority queue


Add new task to ready queue in createTask


PQueue rq;
// ready queue
rq = (int*)malloc(MAX_TASKS * sizeof(int));
rq[0] = 0;
// init ready queue
enQ(rq, tid, tcb[tid].priority);
Change scheduler() to deQueue and then
enQueue next task

if ((nextTask = deQ(rq, -1)) >= 0)
{
enQ(rq, nextTask);
}
BYU CS 345
Project 2 - Tasking

Priority/TID
Priority/TID
Priority/TID
Priority/TID
# of entries
rq[5]
rq[4]
10 / 3
rq[3]
5/2
rq[2]
5/0
rq[1]
2/1
rq[0]
4
72
Project 2 Assignment
Step 3: 5-State Scheduling

Add priority queue to semaphore struct



// semaphore
// link to next semaphore
// semaphore name (malloc)
// state (count)
// type (binary/counting)
// tid of creator
// blocked queue
Malloc semaphore queue in createSemaphore


typedef struct semaphore
{
struct semaphore* semLink;
char* name;
int state;
int type;
int taskNum;
PQueue q;
} Semaphore;
semaphore->q = (int*)malloc(MAX_TASKS * sizeof(int));
semaphore->q[0] = 0;
// init queue
semWait: deQueue current task from ready queue and
enQueue in semaphore queue
semSignal: deQueue task from blocked queue and
enQueue in ready queue.
BYU CS 345
Project 2 - Tasking
73
Project 2 Assignment
Step 4a: Counting Semaphore

Add counting functionality to semaphores



Add a 10 second timer (tics10sec) counting semaphore
to the polling routine (os345interrupts.c).




os345semaphores.c: semSignal, semWait, semTryLock
Replace goto temp;
#include <time.h> header.
Call the C function time(time_t *timer).
semSignal the tics10sec semaphore every 10 seconds.
Create a reentrant high priority timing task that


blocks (SEM_WAIT) on the 10 second timer semaphore
(tics10sec).
when activated, outputs a message with the current task
number and time and then blocks again.
BYU CS 345
Project 2 - Tasking
74
Project 2 Assignment
Step 4b: List Tasks

Modify the list tasks command to




Display all tasks in all system queues in execution/priority order
List task name, if the task is ready, paused, executing, or
blocked, and the task priority.
If the task is blocked, list the reason for the block.
Use the project2 command to schedule timer tasks 1
through 9, 2 signal tasks and 2 “ImAlive” tasks.



The tics10sec task about the current time every 10 seconds in
a round robin order. (Round Robin)
The “ImAlive” tasks will periodically say hello. (Blocking)
The high priority “Signal” tasks should respond immediately
when semaphore signaled. (Priority)
BYU CS 345
Project 2 - Tasking
75
Project 2 Assignment
Step 4c: Verification
Demo

#
Task Name
Priority
Time slice
Blocking Semaphore
0
CLI w/pseudo-input interrupts
5
1
inBufferReady
1-9
TenSeconds
10
1
tics10sec
10
sTask1
20
1
sTask10
11
sTask2
20
1
sTask11
12
ImAlive
1
1
None
13
ImAlive
1
1
None
BYU CS 345
Project 2 - Tasking
76
P2 - Tasking
Step 5: Bonus Credit

Implement a buffered pseudo-interrupt driven character
output and demonstrate that it works by implementing a
my_printf function.
#include <stdarg.h>
void my_printf(char* fmt, ...)
{
va_list arg_ptr;
char pBuffer[128];
char* s = pBuffer;
va_start(arg_ptr, fmt);
vsprintf(pBuffer, fmt, arg_ptr);
while (*s) putIObuffer(*s++);
va_end(arg_ptr);
} // end my_printf

Implement time slices that adjust task execution times
when scheduled.
createTask(
"myShell",
P1_shellTask,
5,
argc,
argv
//
//
//
//
//
task
task
task
task
task
name
priority
arg count
argument pointers
);
BYU CS 345
Project 2 - Tasking
77
BYU CS 345
Project 2 - Tasking
78
Project 2 – Tasking (Step 1)

Create a priority ready queue



Create enQ and deQ functions:



int enQ(PQueue q, TID tid);
int deQ(PQueue q, TID tid);
 q
# | tid1 | tid2 | …
Add new tasks to the ready queue in createTask()


typedef int* PQueue;
// priority queue
PQueue rq = (int*)malloc(MAX_TASKS * sizeof(int));
rq[0] = 0;
// init ready queue
tid = enQ(rq, tid));
// add task to ready queue
Change scheduler() to use a priority queue:

if ((nextTask = deQ(rq, -1)) >= 0) enQ(rq, nextTask);
BYU CS 345
Threads
79
Project 2 – Tasking (Step 2)

Add a priority ready queue to semaphores:



typedef int* PQueue;
// priority queue
PQueue rq = (int*)malloc(MAX_TASKS * sizeof(int));
rq[0] = 0;
// init ready queue
Move blocking tasks from ready to blocked queue:


int enQ(PQueue q, TID tid);
int deQ(PQueue q, TID tid);
 q
# | tid1 | tid2 | …
BYU CS 345
Threads
80
Scheduling
Task Scheduling
Scheduler / Dispatcher
Ready Priority Queue
Executing
SWAP
SEM_SIGNAL
SEM_SIGNAL
SEM_SIGNAL
Semaphore Priority Queue
Semaphore Priority Queue
Semaphore Priority Queue
SEM_WAIT
SEM_WAIT
SEM_WAIT
…
BYU CS 345
Project 2 - Tasking
81
C Threads
State Change in C






The setjmp/longjmp set of macros implemented in the C
provide the perfect platform to perform complex flow-control.
The setjmp function saves the state of a program. The state
of a program, to be precise, are the values of sp (stack
pointer), fp (frame pointer), pc (program counter).
A program state is completely defined by this set of registers
and the contents of the memory, which includes the stack.
Executing a setjmp returns 0 after saving the stack
environment.
If setjmp returns as a result of a longjmp call, the value is the
argument of the longjmp (0 is never returned).
A call to longjmp restores the saved environment and returns
control to the point just after the corresponding setjmp call.
BYU CS 345
Threads
82
setjmp/longjmp
setjmp / longjmp


#include <setjmp.h>
jmp_buf struct


setjmp(jmp_buf env);



stack pointer (sp), frame pointer (fp), and program
counter (pc).
saves the program state (sp, fp, pc) in env so that
longjmp() can restore them later.
returns 0 value.
longjmp(jmp_buf env, int val);


resets the registers to the values saved in env.
longjmp() returns as if you have just called the
setjmp() call that saved env with non-zero value.
BYU CS 345
Project 2 - Tasking
83
setjmp/longjmp
Multi-threading in C
jmp_buf k_context;
int tid;
// my thread
void myThread()
{
while (1)
{
if(!setjmp(tcb[tid].context))
longjmp(k_context,2);
// execute function
}
}
BYU CS 345
// new threads
for (tid = 0; tid < 4; tid++)
{
if (setjmp(k_context) == 0)
{
temp = (int*)tcb[tid].stackEnd;
SET_STACK(temp);
if (setjmp(tcb[tid].context) == 0)
{
longjmp(k_context, 1);
}
myThread();
}
}
// schedule threads
while (1)
{
tid = scheduler();
if (setjmp(k_context) == 0)
{
longjmp(tcb[tid].context, 3);
}
}
Project 2 - Tasking
84
setjmp/longjmp
Multi-tasking in C
BYU CS 345
Project 2 - Tasking
85
BYU CS 345
Project 2 - Tasking
86
setjmp/longjmp
Multi-tasking in C
jmp_buf k_context;
int tid;
#define SWAP \
if(!setjmp(tcb[tid].context)) \
longjmp(k_context,2);
void myFunc()
{
while (1)
{
SWAP;
if(!setjmp(tcb[tid].context))
longjmp(k_context,2);
// execute function
}
}
BYU CS 345
for (tid = 0; tid < 4; tid++)
{
if (setjmp(k_context) == 0)
{
temp = (int*)tcb[tid].stackEnd;
SET_STACK(temp);
if (setjmp(tcb[tid].context) == 0)
{
longjmp(k_context, 1);
}
myFunc();
}
}
while (1)
{
tid = scheduler();
if (setjmp(k_context) == 0)
{
longjmp(tcb[tid].context, 3);
}
}
Project 2 - Tasking
87
P2 - Tasking
Step 1: Priority Queue

Create a priority queue




typedef int TID;
// task ID
typedef int Priority;
// task priority
typedef int* PQueue;
// priority queue
PQueue rq;
// ready queue
rq = (int*)malloc(MAX_TASKS * sizeof(int));
rq[0] = 0;
// init ready queue
Priority/TID
Priority/TID
Priority/TID
Priority/TID
# of entries
Queue functions


int enQ(PQueue q, TID tid, Priority p);
int deQ(PQueue q, TID tid);
 q

# | pr1/tid1 | pr2/tid2 | …
 tid
>=0
find and delete tid from q
-1
return highest priority tid
 int
tid
(if found and deleted from q)
-1
(if q empty or task not found)
BYU CS 345
Project 2 - Tasking
rq[5]
rq[4]
10 / 3
rq[3]
5/2
rq[2]
5/0
rq[1]
2/1
rq[0]
4
88