Advanced Embedded Linux C and Posix Programming

Duration: 5 Days

Course Background

The C programming language is over 40 years old. It is a testament to the genius of the gifted researchers at Bell Labs who developed it that it is still very widely used. C programming is a mainstay of embedded systems programming. In an age where traditional analog systems have. laregely, been replaced by digital systems capable of capturing and processing analog inputs digitally and controlling analog outputs digitally knowing how to program in C is an essential skill. The genius of C is that it is both a high level programming language, and yet, one that is very close to assembler. The aim of an advanced C programming course is to provide an overview of more advanced C programming techniques. These include coverage of dynamic data structures and algorithms such as linked lists and binary trees, the implementation and use of circular buffers and simple memory management systems as well as the use of state machine based approaches to areas such as protocol implementation and multi-tasking.

Course Prerequisites and Target Audience

A sound basic knowledge of C, preferably in the context of embedded systems application development is assumed, to the level covered e.g. in the Introduction to Embedded Linux C programming course.

Course Overview

The course emphasises the implementation of disciplined and well structured code and the design of modules with clean interfaces. Topics include:

Advanced use of dynamic data structures and algorithms for manipulating them.
Structured interrupt handling
Implementation of simple schedulers and operating systems
Working with embedded operating systems
Understanding standard techniques for inter-process communication, and their uses.
Finite state machines, statecharts, and their uses
Advanced algorithms and research-oriented approaches

Lab exercises are used to consolidate key concepts.

The course uses PC workstation and Embedded Linux systems as a platform for hands-on work. The course also covers basic multi-tasking techniques using state machine driven scheduling approaches and simple timer interrupt driven deterministic scheduling techniques. The course uses the Eclipse IDE and the GNU C compiler.

Course Benefits

Students successfully completing this course will have a sound understanding of C and Posix API programming. You will understand the basic C data types, arrays and pointers. You will have a good appreciation of data structures and their uses, and the use of pointers to data structures and arrays of data structures. You'll learn how to use arrays to implement circular buffers and how to use them, and how to use arrays to implement stacks, and the uses of software stacks.
You will also be introduced to basic techniques of memory management and programming with dynamic data structures - and to circular buffers and stacks and linked lists. You'll also learn techniques multi-tasking and multi-thread programming and inter-task / inter-thread communication patterns.

Students completing this course will considerably improve the discipline and rigour with which they design and write embedded systems applications in C.

You'll be able to implement classical data structures such as circular buffers, linked lists, and trees -- and you'll know when it's appropriate to use them.

You'll be exposed to a variety of advanced programming idioms and algorithms with their associated data structures, for tasks such as indexing, data compression and error detection.

You'll learn to write event driven programs, to implement Finite State Machines, and to design hierarchical state machines using statecharts.

You'll learn structured programming techniques for implementing multi-tasking applications.

Course Outline

Intensive overview of essential C concepts and idioms

Data types, data structures, pointers and arrays
Using pointers to search collections of data

Arrays and buffers

Circular buffers
Polygonal buffers
I/O vectors

Linked Lists in depth

Singly linked and doubly linked lists
Using lists to implements FIFO queues and LIFO queues (stacks)
Using lists of linked lists
Using linked list nodes containing void * pointers to implement heterogeneous collections of data
Using linked lists to implement resizeable arrays

Binary trees, their uses and their relations

Basic binary trees
Self-balancing binary trees (AVL, Red-Black, Splay)
Heaps and their uses
Huffman encoding
Priority queues

Error detection

CRC checksums (16 bit and 32 bit)

Implementing simple memory management schemes
Implementing simple flash memory file systems
State Machines and Statecharts

Event driven programming
Basic FSMs
Pattern matching
Parsing
State driven hardware and communication protocols
Implementing FSMs using switch statements
Implementing FSMs using a table driven approach
Limitations of FSMs
Extended FSMs and hierarchical FSMs
Extending FSMs by adding variables and conditional transitions
Nesting state machines (push down automata)

Statecharts

Hierachical FSMs and extended FSMs (simple statecharts)
Orthogonal statecharts and concurrency
Active objects - linking multi-tasking, message passing and event driven programming

The Posix API

An overview of the Posix Standards
Posix Standards used in Linux
Kernel space vs. User space
System calls for switching between kernel space and user space
Manipulating file systems, files and directories in Posix
Using fork and exec to spawn new tasks
Inter process communication using pipes and named pipes
Threads under Linux and the PThreads API
The Sockets API and network programming
Virtual memory and memory mapping
Mutexes, Semaphores and Condition Variables

An Introduction to Important Inter-Process Communication Idioms

Producer - Consumer
Monitors
Readers and Writers
Workcrew

Synchronous vs. asynchronous programming idioms - an Overview

Blocking vs. non-blocking system calls
Asynchronous socket programming
Remote Procedure Call (RPC) Programming
Introduction to load balancing and proxy servers