Engineering Clinic

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 periodic The relative deadline of the tasks are equal to its period. No tasks has a non pre-emptible section. The cost of preemption is negligible. RMA Priorities are assigned based on the periods of the task. Lower the period, higher the priority As rate is the inverse of the period, higher the rate, higher the priority It is a static priority algorithm (priorities are assigned to tasks during their compilation time) Schedulability Test for RMA To find the schedulability Test of RM algorithm the 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 time Every job is assigned to atmost one processor at a time No job is scheduled before its release time Depending on the scheduling algorithms used, the total amount of processor time assigned to every job is equal to its actual execution time All 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 i

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=<s 0 ,s 1 ,s 2 …….s n-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). Wh

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++

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