- Forward


Control Flows
Sequential, Parallel, and Concurrent


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Review - Executable Programs
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back -