Skip to main content

Posts

Showing posts from December, 2008

Earliest Deadline First (EDF) Algorithm

It is an Optimal dynamic Priority Scheduling Algorithm Priorities are assigned based on the absolute deadlines of the task, earlier the deadline, higher the priority.It is also called as Deadline Monotonic Scheduling (DM). If two tasks have the same deadline, then EDF randomly select  one to execute next.The Schedulability condition for EDF is where U is the processor Utilisation Factor and it never be greater than 1. In practical, no processor will be utilised for more than 100%.

Rate Monotonic Scheduling (RM)

Rate Monotonic Scheduling is the optimal static priority algorithm. Shortly it is referred as RM or RMA or RMS. To solve for the RM schedule, the following are the assumptions.Assumptions:All the tasks are assumed to be periodicThe relative deadline of the tasks are equal to its period.No tasks has a non pre-emptible section.The cost of preemption is negligible.RMAPriorities are assigned based on the periods of the task. Lower the period, higher the priorityAs rate is the inverse of the period, higher the rate, higher the priorityIt is a static priority algorithm (priorities are assigned to tasks during their compilation time) Schedulability Test for RMATo find the schedulability Test of RM algorithmthe sufficient condition for schedulability test for RM is The necessary and sufficient condition for testing the schedulability test is

Scheduling Hierarchies

Valid Schedule
A scheduler is responsible for managing the resource allocation to the tasks and it is based on the scheduling algorithms. A scheduler produces a valid schedules should obey these rules
Every process is assigned to atmost one job at a timeEvery job is assigned to atmost one processor at a timeNo job is scheduled before its release timeDepending on the scheduling algorithms used, the total amount of processor time assigned to every job is equal to its actual execution timeAll the precedence and resource usage constraints are satisfied.Feasible Schedule
All tasks of valid schedule meets deadlines, then the schedule is said to be feasible

Optimal Schedule
Every feasible schedule is said to be optimal, if there exists a scheduling algorithm which does not schedule a particular task set, then no other scheduling algorithm can schedule that task set feasibly.
Eg. The optimal static scheduling policy is Rate Monotonic Algorithm (RMA)
The Optimal dynamic Scheduling Policy is Preemptiv…

DATA STRUCTURES – Q & A

Define Abstract Data Type (ADT). Abstract data type is a collection of value definitions and the operations on those values.Value definitions Operator definitions Define a sequence. A sequence is an ordered set of elements. S=<s0,s1,s2…….sn-1>Write short notes on structures in C. A basic data structure in C is called as the structure. A Structure is a group of items in which each item is identified by its own identifier. Example:struct nametype{char first[10];int roll;}sname, ename;What is the difference between a structure and union in C. Same memory is used for all the members of union. At any time only one member can be accessed. Individual memory is used for structure members. Define a Stack.A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end called the top of the stack.It is also called as Last In First Out (LIFO).What are the primitive operations that are performed on a Stack?The primitive operations…

Introduction to Real Time Systems

System
Set of one or more inputs entering the black box and a set of outputs exiting the black box is called a system.

Response Time
The time between the presentation of set of inputs and the appearance of the associated outputs.

Real time System
A System that must satisfy the response tine constraints or it will be a failure.

Embedded System
A software system that is completely encapsulated by the hardware that it controls.

Deadline
The instant of time at which the execution of task is required to be completed.
* absolute deadline
* relative deadline = absolute deadline – release time

Release time
The instant of time at which the task or job is ready for execution

Challenges or Issues in Real time Systems
Selection of hardware and Software (Hardware includes sensors, actuators, timers, controllers or processors)Selection of the operating Systems (Real Time Operating System) (RTOS works under the preemption principle.)Selection of Programming language. (C, C++, ADA, Java, …

Basic Networking Concepts

Basic Networking Concepts
Introduction
A network can be defined as a group of computers and other devices connected in some ways so as to be able to exchange data.
Each of the devices on the network can be thought of as a node; each node has a unique address.
Addresses are numeric quantities that are easy for computers to work with, but not for humans to remember.
Example: 204.160.241.98
Some networks also provide names that humans can more easily remember than numbers.
Network Hardware
So what is a computer network? A network is a collection (two or more) of computers that are connected together for sharing data and resources. Networks are commonly categorized by their geographical size.
A local area network (a LAN) is a group of computers and associated devices that share a common communication line and are typically located within a small geographic area, such as in your home or in an office building, or even a single department in a company. A local area network may c…