2. Threads, Processes, and Dispatching

Threads and Processes

• Thread: a sequential execution stream 
  • Executes a series of instructions in order (only one thing happens at a time)
• Execution state: everything that can affect, or be affected by, a thread:
  • code, data, registers, call stack, open files, network connections, time of day, etc
• Process: one or more threads, along with their execution state
  • Part is shared among all threads in the process
  • Part of the process state is private to a thread
• Evolution of operating system process model:
  • Early operating systems supported a single process with a single thread at a time (single tasking). They ran batch jobs (one user at a time).
  • By late 1970's most operating systems were multitasking systems: they supported multiple processes, but each proceess had only a single thread.
  • Some early personal computer operating systems used single-tasking (e.g. MS-DOS), but these systems are almost unheard of today.
  • In the 1990's systems converted to multithreading: multiple threads within each process.
• Is a process the Same as a program? (NO)

 

Dispatching

• Almost all computers today can execute multiple threads simultaneously:
  • Each processor chip typically contains multiple cores
  • Each core contains a complete CPU capable of executing a thread
  • Many modern processors ssuppot hyperthreading: each physical core behaves as if it is actually two cores, so it can run two threads simultaneously (e.g. execute one thread while the other is waiting on a cache miss).
  • For example, a server might contain 2 Intel processor chips, each with 12 cores, where each core supports 2-way hyperthreading. Overall, this server can run 48 threads simultaneously.
• Typically have more threads than cores
• At any given time, most threads do not need to execute (they are waiting for somemthing).
• OS uses a process control block to keep track of each process:
  • Saved execution state for each thread (saved registers, etc.)
  • Scheduling information
  • Information about memory used by this process
  • Information about open files
  • Accounting and other rmiscellaneous information
• At any given time a thread is in one of 3 states:
  • Running
  • Blocked: waiting for an event (dist I/O, incoming network packet, etc.)
  • Ready: waiting for CPU time
• Dispatcher: innermost portion of the OS that runs on each core:
  • Let a thread run for a while
  • Save its execution state
  • Load state of another thread
  • Let it run ...
• Context switch: changing the thread currently running on a core by first saving the state of the old thread, then loading the state of the new thread.
• What causes the dispatcher to run?
• Traps (events occurring in current thread that cause a change of control into the operating system):
  • System call.
  • Error (illegal instruction, addressing violation, etc.).
  • Page fault.
• Interrupts (events ocurring outside the current thread that cause a state switch into the operating system):
  • Character typed at keyboard.
  • Completion of dist operation.
  • Timer: to make sure OS eventually gets control.
• The dispatcher is not itself a thread
  • It is just code that is invoked to perform the dispatching function
• How does dispatcher decide which thread to run next (assuming just one core)?
  • Simplest approach: Link together the ready threads into a queue. Dispatcher grabs first thread from the queue. When threads become ready, insert at back of queue.
  • More complex/powerful: give each thread a priority, organize the queue according to priority. Or, perhaps have multiple queues, one for each priority class.

 

Process Creation

• Basic steps in creating a new process:
  • Allocate and initialize process control block.
  • Load code and data into memory.
  • Create structures for first thread, such as call stack.
  • Provide initial values for "saved state" for the thread
  • Make thread known to dispatcher; dispatcher "resumes" to start of new program.

 

 

Summary

 

- Thread: 순차적인 실행 흐름

- Execution state: thread에 영향을 주거나 받는 모든 것들 (code, data, registers, call stack, network connections, etc.)

- Process: 한 개 이상의 thread와 execution state

- 한 개의 thread를 필요로 하는 하나의 process만 실행할 수 있었는데 시간이 지나면서 동시에 돌릴 수 있는 process의 수가 늘어나고 두 개 이상의 thread를 필요로 하는 process 또한 지원하게 되었다.

- 현재 processor chip은 여러 개의 core를 가지고 있고 각 core는 하나의 thread를 실행시킬 수 있다.

- hyperthreading이라는 논리적 접근으로 한 core에서 두 개의 thread를 실행시킬 수 있다.

 

- 일반적으로 실행시킬 수 있는 thread 수가 실행하고자 하는 thread 수보다 작다. 따라서 Process Control Block(PCB)를 통해 process의 정보를 기록해둔다. (execution state, scheduling information, information about memory used by this process, information about open files, etc) 

- thread는 running, blocked, ready 중 한 가지 state를 가진다.

 

- Dispatcher는 각 코어에 thread를 올렸다 내렸다하는 작업을 한다. (내릴 때 execution state를 PCB에 저장, 올릴 때 load)

- 이 과정을 context switch라 한다.

 

- 현재 thread 안에서 control change를 일으키는 사건을 trap이라 한다. (error, system call, page fault)

- 현재 thread 밖에서 state switch를 일으키는 사건을 interrupt라 한다. (키 입력, I/O 작업 완료, timer)

 

- dispatcher 자체가 thread가 아니고 dispatching 함수를 수행하기 위해 불러지는 code이다.

- dispatcher는 단순히 ready queue에 있는 thread를 순차적으로 실행시킬 수도 있고 priority에 따라 실행시킬 수도 있다.

 

- 새로운 process를 만드는 과정: PCB 할당, 초기화 -> code와 data를 memory에 load -> 첫 번째 thread를 위해 call stack과 같은 구조 생성 -> thread를 위해 저장된 상태를 초기 값에 적용 -> dispatcher에 thread가 생성되었음을 알려 dispatcher가 새로운 프로그램의 시작을 재개

 

- System calls: fork, exec, waitpid in UNIX, CreateProcess (fork + exec), WaitForSiingleObject in Windows, exec (fork + exec) in Pintos