Loading [MathJax]/jax/output/HTML-CSS/jax.js
Control Flows
Sequential, Parallel, and Concurrent
|
|
Prof. David Bernstein
James Madison University
|
|
|
|
Computer Science Department
|
|
bernstdh@jmu.edu
|
Review - Executable Programs
- Organization:
- For our purposes (i.e., for simplicity), an executable
program consists of a single file
- Format:
- Old - Assembler Output, Common Object File Format (COFF);
New - Executable and Linking Format (ELF)
- Executables contain metainformation the describe the format
- Contents:
- The machine language instructions
- The entry-point address
- Data
- Symbol and relocation tables
- Other information
Review - Execution of a Program
- Central Processing Unit (CPU):
- The device that interprets/executes instructions
- Program Counter:
- A register that contains the address of an instruction
- The Dynamics:
- The CPU repeatedly executes the instruction pointed to
by the PC and updates the PC
A Quick Introduction to Processes
- Definition:
- A process is an instance of a program execution
- The State/Context of a Process:
- The program's code (i.e., the instructions)
- The data stored in memory and in registers
- The program counter
- Everything else that can affect or be affected by a process
Control Transfer and the Control Flow
- Notation:
- The sequence of addresses are denoted by
a_0, a_1, \dots, a_{n-1}
- a_k denotes the address of
instruction I_k
- Control Transfer:
- A transition from a_k to a_{k+1}
is called a control transfer
and denoted by t_k
- The Flow of Control:
- A sequence of control transfers is called the
flow of control (or control flow)
of the processor
Logical Control Flow
- An Important Point:
- The OS can support multiple processes at the same time
- An Important Illusion:
- The processor appears to execute the instructions in a program
without interruption
- Logical Control Flow:
- The sequence of transitions for a single process
Concurrent Flows
- Definition:
- Two flows, X and Y,
are said to running concurrently iff
Y began after X began
and before X finished or
X began after Y began
and before Y finished
- Concurrent Flows on a Single Processor/Core:
- When multiple processes share a single processor/core
(i.e., "take turns") it is known as time slicing
- When the OS saves the state of the current process,
loads the state of another process, and passes control to the
newly loaded process it is known as a context switch
Parallel Flows
- Definition:
- Two concurrent flows, X and Y,
are said to be running in parallel iff
they are running on different processors/cores.
- An Important Observation:
- This definition says nothing about the physical location
of the processors/cores
There's Always More to Learn