Control Flows

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