Operating Systems Concepts for IoT (Internet of Things)

Fundamentals

A task is a program, program unit, process, or thread (lightweight process). It could be a sequential function with an infinite loop. Usually can be of two types user or kernel.

Why do we need an operating system (OS)?

• Manage hardware and software resources
• Power Management
• Task schedulers
• Task management
• supports multitasking
• Inter-process communications
• Memory allocation and management
• Managing I/O devices and peripherals 
• Analog 
• motors
• valves
• Digital
• Hardware Interrupts
• ISR (Interrupt Service Routines)

Task Scheduling Algorithms

• Time-sharing task scheduling 
• Pre-emptive
• Non-preemptive

• Priority-based Round Robin Scheduling

Timers

• Internal core timers
• Software timers
• One shot timers
• Auto-reloaded timers

Task Management

• Managing the Task States
• Running 
• Not Running
• Ready
• Suspended
• Blocked
• Context Switching

Race Condition

• Undesirable condition when multiple tasks (or threads) try to access and change the shared data simultaneously.

Thread Safety

• Locking shared resources/data using a critical section
• Intertask communication

Deadlock

Two tasks are waiting for the same resource held by the other

Deadlock Prevention

- planning resource allocation

Interprocess Communications

- Message Queues

- Interrupts

- Mutex - provides mutual exclusion when concurrent tasks access a shared resource

- semaphore 

Dynamic Memory Allocation

- Heap

- First Fit Memory Allocation

Static Memory Allocation

 - Stack

Characteristics

• Small Footprint
• Modularity
• Extensibility
• Flexible
• Easy to use API
• Portability
• Tools Support

Should we use an OS in IoT?

• to build an ecosystem for device drivers.
• support for extensibility
• Security

Why ecosystem

• vendor 
• open source community
• user support 
• community

IoT System

• managing processor

Types of Operating Systems

• General Purpose 
• rich functionality
• complex functionality
• Embedded OS for resource constraint device
• e.g. coffee machines, smart sensors, wireless routers
• small footprint
• high reliability
• for optimized performance
• e.g. FreeRTOS (real-time OS), Android Things
• limited file system support

Definition of Data Structures

Definition

A data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.


Understanding data structures is a must for every programmer as it clarifies the working of inner data for a program.

Below are the examples of data structures from real life

• shopping list
• bank statement - intentional list of transactions where each transaction is an intentional arrangement of data fields like information, date, amount,  involved parties etc. with a chronological order to
• telephone directory
• dictionary
• thesaurus
• encyclopedia
• movie ticket availability
• railway time table
• flight schedule
• mobile phone plans (showing various monthly packages)

Facebook Edgerank Algorithm Explained

the Edgerank algorithm is used in Facebook to determine the order of posts that should be shown on a user's Top News feed. 

Flyweight Design Pattern

The flyweight design pattern is used to dramatically increase the speed of code when using many similar objects.

To reduce memory usage the flyweight design pattern shares Objects that are the same rather than creating new ones.

Bridge Design Pattern

This pattern is used to build a group of classes that slowly adds functionality from one class to the next. 

Facade Design Pattern

English: Author: Alcides Carlos de Moraes Neto (wikipedia.10.alcides@spamgourmet.com) (Photo credit: Wikipedia)

The Facade pattern simplify methods so that most of the processing is done in the background. In technical terms it decouples the client from the sub components needed to perform an operation.

Iterator Design Pattern

The Iterator design pattern illustration, UML diagram. (Photo credit: Wikipedia)

The iterator pattern is used to access objects that are stored in many different types of collection.
This is done by creating a common interface that all the different collection classes share. Then an iterator is provided to traverse the objects they contain.

Because all different Collection classes share a common interface they can be treated polymorphically and it eliminate duplicate code.

Below is the video tutorial for the Iterator pattern

Related articles

• The For-Each Loop(iontech.wordpress.com)

  ---

State Design Pattern

English: UML Class Diagram of the State Design Pattern (Photo credit: Wikipedia)

Below is the video tutorial on State Design Pattern

Related articles

• Object Oriented Design Patterns for Model Attribute Events(stackoverflow.com)

  ---

Command Design Pattern

The UML diagram describing relations between objects of the Command design pattern. (Photo credit: Wikipedia)

The UML diagram which describes the structure of the Command design pattern. (Photo credit: Wikipedia)

public interface Computer {
   void start();
   void shutdown();
}

public class Laptop implements Computer {
   public void start() {
       System.out.print("Laptop is started");
    }

    public void shutdown() {
       System.out.print("Laptop is shutdown");
    }

}

public interface Command {
   void execute();
   void undo();
}

public class StartLaptop implements Command {
   Computer theComputer;
   
    public StartLaptop (Computer newComputer ) {
        theComputer = newComputer;
    }

    public void execute() {
        theComputer.start();
    }
    
    public void undo() {
        theComputer.shutdown();
    }         
}

Below is the video tutorial about the Command pattern. 

Related articles

• Command Pattern(slanto.wordpress.com)

  ---

Singleton Design Pattern Tutorial

Singleton Pattern is used to prevent instantiation of an object more than once.

Abstract Factory Design Pattern

Factory Design Pattern

Factory design pattern is used to define the class of an object at runtime. It allows encapsulating object creation to keep all object creation code in one place. (separation of concerns)

You cannot instantiate an abstract class. It is just there to facilitate polymorphism.

Basic Principles of Object Oriented Technology

Algorithm Types

Below are the list of categories into which various algorithm can be categorized:

1. Simple recursive algorithms
2. Backtracking algorithms
3. Divide and conquer algorithms
4. Dynamic programming algorithms
5. Greedy algorithms
6. Branch and Bound algorithms
7. Randomized algorithms

ArrayList or LinkedList ...??

ArrayList or LinkedList ...?? compares ArrayList and LinkedList

Lecture Series on Design & Analysis of Algorithms

Computer Sc - Design & Analysis of Algorithms
Lecture Series on Design & Analysis of Algorithms by Prof.Abhiram Ranade, Department of Computer Science Engineering,IIT Bombay.

Refcardz #08: Design Patterns

List of Algorithms

An algorithm is an unambiguous specification of how to solve a class of problems. It is a set of rules that precisely define a sequence of operations.

Algorithms are a sequence of steps for accomplishing a task. We use complex algorithms in our day to day tasks for eg. searching in Google, sending emails, booking air tickets etc.

an example on insertion sort (Photo credit: Wikipedia)

Characteristics of algorithms
Performance (memory & CPU)
Simplicity

List of Algorithms

• Finding Maximum
• Order Statistics
• Matrix Multiplication
• Comparison
• Linear Search
  String searching algorithm (Photo credit: Wikipedia)
• Binary Search
• Selection Sort
• Insertion Sort
• Bubble Sort
  English: an example on bubble sort. (Photo credit: Wikipedia)
  English: Sorting a random list using bubble sort (Photo credit: Wikipedia)
  
  
• Heap Sort
• Merge Sort
• English: Sorting a random list using merge sort. (Photo credit: Wikipedia)
  English: an example on merge sort. (Photo credit: Wikipedia)
• Radix or Bucket Sort
• Random algorithms - improves the worst case performance
• Quick Sort
• Finding Median
• Hashing
• Fibonacci sequence
• Spanning Tree
• Shortest Path - finding the shortest path from one point to another.
• Djikstra's algorithm
• String Searching
• String Matching

NP-complete or NP-hard problem has no known good optimal solution. If someone finds an efficient algorithm for one NP-hard problem, then that algorithm would be applicable to all NP-hard problems. 

Related articles

• Big-O Misconceptions(ssp.impulsetrain.com)

  ---

• Algorithm Headache(mayoiengineer.wordpress.com)

  ---

• insertion sort vs bubble sort vs quicksort algorithm(stackoverflow.com)

  ---

• What's really so bad about bubble sort?(nicknash.me)

  ---

• bubble sort help(daniweb.com)

  ---

• Radix sort(daniweb.com)

  ---

• A simple C program for Insertion sort(depthgr8.wordpress.com)

  ---

• How to teach Algorithms ?(kintali.wordpress.com)

  ---

List of Design Patterns

LazyList-Iterator (Photo credit: propella)

• singleton
• iterator / enumerator
• decorator
• facade
• listener
• publisher-subscriber
• factory
  Factory Method pattern in LePUS3 (Photo credit: Wikipedia)
• abstract factory - A tutorial about abstract factory design pattern
  The Abstract Factory pattern illustration, UML diagram. (Photo credit: Wikipedia)
  Abstract Factory (Photo credit: Wikipedia)
• Model View Controller (MVC)
  English: This diagram depicts how the Model View Controller Architecture works. (Photo credit: Wikipedia)
  English: The model, view, and controller (MVC) pattern relative to the user. (Photo credit: Wikipedia)
  Deutsch: Model View Controller (Photo credit: Wikipedia)
• Inversion of Control (IoC)

Related articles

• Inversion of Control Containers and the Dependency Injection pattern(lchandara.wordpress.com)

  ---

• Abstract Factory Design Pattern Explained(javacodegeeks.com)

  ---

• IoC container solves a problem you might not have but it's a nice problem to have(devlicio.us)

  ---

• Answer by jalf for Does Functional Programming Replace GoF Design Patterns?(stackoverflow.com)

  ---

• Abstract factory pattern in java(howtodoinjava.com)

  ---

• Factory Design Pattern(javabydesign.blogspot.com)

  ---

• Design Best practices using Factory Method Pattern(javacodegeeks.com)

  ---

• A Modern Alternative to Abstract Factory Filtered Dependencies(architects.dzone.com)

  ---

• An explanation to Factory Design Pattern...!(daniweb.com)

  ---

• Do These Design Patterns Stand the Test of Time?: Abstract Factory(architects.dzone.com)

  ---

List of Data Structures

Below is the list of important data structures

• Simple Data Structures
• Primitive Data Types
• Boolean
• Numbers
• String
• Structures (structs)
• Points (x & y coordinates), Color (red, green, blue, alpha)
• Objects (Custom Data Types)
• Collections
• Arrays
• single -dimensional arrays
• multi-dimensional arrays
• two-dimensional arrays (rectangular), 
• three-dimensional arrays,
• and so on...
• Jagged arrays (ex. daily sales per month ) 
• Lists
• ArrayList (resizable, dynamic or mutable arrays)
• Vector
• Operations
• Appending (Push) - adding an element at the end
• Insertion / Add - adding in the middle at a specified index
• Removing (Pop) - deleting an element at the end
• Deletion - removing an element at a specified index
• Splice - (adding and removing)
• Search / Find / Contains - searching for an item and returning location
• Sort - ordering the data
• Linked List 
• Singly Linked List
• Definition: A data structure consisting of a group of nodes where each node is composed of data and a reference (or a link) to the next node in the sequence.
• Operations
• Insertion
• Deletion
• Find / Search
• Traversal
• Iterative
• Recursive
• Reversal
• Iterative
• Recursive
• Doubly Linked List
• Definition: A data structure consisting of a group of nodes where each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.
• The two node links allow traversal of the list in either direction. While adding or removing a node in a doubly linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified.
• Operations
• Insertion
• Deletion
• Traversal
• Reverse Traversal
• Circular Linked List
• Abstract Data Type
• Queue - First In, First Out
• Examples - Job Queue
• Operations
• Enqueue - adding an element at Last
• Dequeue - removing an element from Front
• Stack - Last In, First Out
• Operations
• Push
• Pop
• Peek
• Priority Queue
• Double-ended Queue (Deque) - supports adding deletion from both ends
• Hash-Based Data Structures

hash table illustration, with three keys, funcbox, sparse range, no collisions, only the values stored. Inspired on File: HASHTB32.svg and other similar images. Created with make-hash-table-figure -nkeys 3 -funcbox 1 -sparse 1 -keys 0 -values 1 -collisions 0 -links 0 -overflow SP (Photo credit: Wikipedia)

hash table illustration, with three keys, sparse range, buckets are links, collisions resolved by separate chaining, keys and values stored. Inspired on File: HASHTB32.svg and other similar images. Created with make-hash-table-figure -nkeys 5 -funcbox 0 -sparse 1 -keys 1 -values 1 -collisions 1 -links 1 -overflow LL (Photo credit: Wikipedia)

• Associative Arrays 
• Invariants 
• Unique Keys
• Operations
• Add
• Remove
• Hash Tables / Hash Map / Dictionaries
• create with an initial capacity
• Hash Collision
• separate chaining
• Set / HashSet
• unordered collection of objects
• No sequence
• No duplicates
• Fast lookup - for checking membership, not retrieval
• Operations
• add
• remove
• contains
• Tree
• Binary Tree

A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. (Photo credit: Wikipedia)

• Binary Search Tree 
• invariants
• no duplicates
• operations
• add
• delete
• find
• traverse
• pre-order
• in-order
• post-order
• Self Balancing Trees
• AVL Tree
• Red-Black Tree - (implementation of TreeMap in Java uses this)
• Scapegoat Trees
• Splay Trees
• Segment Tree (for min/max/sum range queries)
• Fenwick Tree (Binary Indexed Tree)
• Heap (Min Heap or Max Heap)

A method for implementing Double ended priority queue(DEPQ) (Photo credit: Wikipedia)

• Graph
• Directed Graph
• Undirected Graph
• Weighted Graph
• Trie
• Disjoint Set
• Bloom Filter
• Consistent Hash Ring
• Maps
• Ternary Search Trees
• B-Trees
• Graph

Related articles

• Singly Linked List class using Collection hierarchy C++(stackoverflow.com)

  ---

• Five Myths about Hash Tables(hughewilliams.com)

  ---

• Open Data Structures: an open content textbook(opendatastructures.org)

  ---

• Implementing a binary tree using linear linked lists(en.nerdaholyc.com)

  ---