Compiler Construction With Embedded Xinu

From Embedded Xinu
Revision as of 21:17, 26 July 2010 by Amallen (talk | contribs) (Created a page for the compiler course with XINU. NOTE: this page is NOT DONE! i'm just saving what I've written so far)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


Having students construct a compiler which targets a runtime that uses their own, or a provided, Xinu operating system is one of the potential tracks for a professor that is Teaching With Xinu.

Including Embedded Xinu in a compiler construction course allows students to explore the compilation of high level language constructs that rely on interacting with the underlying runtime. Many traditional compilers courses simply target a processor or simulator, but by targeting a platform (a processor and operating system combination) one can extend the source language to include more advanced language features such as I/O operations and thread creation, manipulation, and concurrency. This also allows students to run their test cases on real hardware and see these programs actually interacting with a real runtime. In modern programming these high level language features are vital, and it is important for students to see what the processor and runtime are doing when they use these features in their own programs.

Course Outcomes

Course development can parallel learning objectives and topics associated with many Programming Language Translation or Compiler Construction courses. [1] However, by targeting a platform students can also focus on learning how compilers interact with the runtime to achieve thread concurrency and synchronization; topics which many traditional compilers courses avoid. [2, 3, 4]


  • Overview of operating systems
  • Operating system principles
  • Concurrency
  • Scheduling and dispatch
  • Memory management
  • Device management
  • Security and protection
  • File systems
  • Evaluating system performance

Learning Objectives

  • Recognizing various classes of grammars, languages, and automata.
  • Ability to use existing compiler tools to scan and parse source code into abstract syntax trees.
  • Implementing a type-checker that enforce the type rules in a given grammar.
  • Translating an abstract syntax tree into an intermediate representation ready for assembling.
  • Understanding the principles and techniques behind register allocation.
  • Discuss the history of operating systems.
  • Overview of the general and specific purpose of an operating system.
  • Understanding concurrency and state flow diagrams.
  • Understanding deadlock and starvation.
  • Ability to decipher between scheduling algorithms.
  • Understanding the use of memory and virtual memory.
  • Characteristics of serial and parallel devices.
  • Deciphering the concepts behind various file systems
  • Understanding the necessity of security and locating potential system security holes

Potential Course Structure

An Operating Systems course using the below course outline or something similar will introduce students to some fundamental concepts of operating systems combined with the basics of networking and communications. Topics include: memory management, scheduling, concurrent processing, device management, file systems, networking, security, and system performance. A similar course structure is followed by Dr. Dennis Brylow at Marquette University in his sophomore level Operating Systems course. Most of the assignments where students are building Embedded Xinu are done in teams of two.

Course Outline
Week Topics Assignments Track One Assignments Track Two
01 C (basics) and OS Structures, Processes C Basics C Basics
02 C (functions, control flow) and Processes
03 C (pointers, arrays, structs) and Threads C Structs and Pointers C Structs and Pointers
04 CPU Scheduling Synchronous Serial Driver Synchronous Serial Driver
05 CPU Scheduling
06 Process Synchronization Context Switch and Non-Preemptive Scheduling Context Switch and Non-Preemptive Scheduling
07 Deadlocks Priority Scheduling and Process Termination Priority Scheduling & Preemption
08 Main Memory and Virtual Memory
09 File System Interface Preemption & Synchronization Interprocess Communication or LL/SC
10 File System Implementation
11 Mass-Storage Structure Delta Queues Delta Queues
12 I/O Systems Heap Memory Heap Memory
13 Protection, Security and Distributed System Structures Asynchronous Device Driver Ultra-Tiny File System
14 Distributed System Structures
15 Distributed File Systems Ultra-Tiny File System Basic Networking - Ping


[1] Course topics and learning objectives have been adapted from the ACM's Computing Curricula 2001 Computer Science.

This work funded in part by NSF grant DUE-CCLI-0737476.