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 edf

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%.

Advertisements

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

  1. Priorities are assigned based on the periods of the task.
    1. Lower the period, higher the priority
    2. As rate is the inverse of the period, higher the rate, higher the priority
  2. 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

How to enable GUI root Login in Fedora 10

Steps to enable Root Login in Fedora 10
Step 1: Login with ordinary username and open the terminal and issue the
command su (su is a super user you need to input a password)
Step 2: Open the following file using the command
gedit /etc/pam.d/gdm or vi /etc/pam.d/gdm
Step 3: Comment the following line by including a #
(Eg. #auth required pam_succeed_if.so user != root quiet)
Step 4: Save the file and logout and then login with root.

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 is Preemptive Earliest Deadline First (EDF)

Phishing and Pharming

Phishing is the term derived from “fishing”. It leads to a criminal and a fraudulent method of acquiring confidential information relating to financial transactions, such as passwords, credit card/debit card information, PIN numbers etc. The most common targets are online banking, shopping portals, etc. The technique behind is to urge suspecting users to send sensitive information through emails, deceptive replication of reputed websites. Such data is used to take out money from one’s account.

Pharming is a successor of phishing and it operates when a link is clicked on an email purporting from the bank, you are trapped. At this point, even if the key for URL is entered correctly, the malware manipulates the PC such that the browser will only lead to the fraudulent website.

Solution

  • Updated Anti Virus and anti spyware
  • Always check the url of the bank to be https:// and not http://
  • Always enter the URL of the bank manually in the address bar, never take it from any other websites or through email.
  • To guard against, fake websites, give the username correctly and enter the password wrongly, so that the original bank website will tell wrong and the fake website will give you a “Thank you Message”

Source: CHIP Magazine and online resource

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.

  1. Same memory is used for all the members of union. At any time only one member can be accessed.
  2. 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 are

Push- inserting an element at the top of the stack

Push(s,i);

Pop – removing an element at the top of the stack

i=pop(s);

How do you implement the Stack definition in C. Use array implementation?

#define STACKSIZE

struct stack

{

int top;

int items[STACKSIZE];

};

Write the steps for implementing the pop operation.

    • If the stack is empty, print a warning message and halt execution
    • Remove the top element from the stack.
    • Return this element to the calling program

What is recursive definition?

An object in terms of simpler case of itself is called recursive definition.

Examples:

· To find the factorial of a given number

· To print the Fibonacci series.

Define a queue.

A queue is a ordered collection of items from which itesm may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (called the rear of the queue). It is also called as First in First out (FIFO).

How the queue is represented in C?

#define MAXQUEUE 100

struct queue

{

int items[MAXQUEUE];

int front, rear;

}q;

Define priority queue. What are the types of Priority queue?

The priority queue is a data structure in which the intrinsic ordering of the elements does determine the results. There are two types

· ascending priority queue

is a collection of items into which items can be inserted arbitrarily and from which only the smallest item can be removed.

· descending priority queue

What is the purpose of header node?

Sometimes it is desirable to keep an extra node at the front of the list. Such a node does not represent an item in the list and is called the header node or a list header.

How to create and delete a dynamic variable in C?

malloc() is a function helpful for creating a dynamic variable.

free() is a function helpful for deleting a dynamic variable.

How to create a node of a singly linked list using dynamic variables?

struct node

{

int info;

struct node *next;

};

typedef struct node *NODEPTR;

16. How to create a node of a Doubly linked list using dynamic variables?

struct node

{

int info;

struct node *next, *previous;

};

typedef struct node *NODEPTR;

17. Define a binary tree.

A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. One subset is the left and one subset of the right and the third subset is the root of the tree.

18. What is a strictly binary tree?

If every non leaf node in a binary tree has nonempty left and right subtrees, the tree is named as the strictly binary tree.

19. Define traversal in tree and what is the different type of traversals in tree?

To pass through the tree, enumerating each of its nodes once.

Three types of traversals

    • preorder traversal
      • visit the root
      • Traverse the left subtree in preorder.
      • Traverse the right subtree in preorder
    • inorder traversal
      • Traverse the left subtree in preorder.
      • visit the root
      • Traverse the right subtree in preorder
    • postorder traversal
      • Traverse the left subtree in preorder.
      • Traverse the right subtree in preorder
      • visit the root

20. How the binary tree node is represented dynamically?

struct nodetype

{

int info;

struct nodetype *left;

struct nodetype *right;

};

21. What are called leaf nodes?

The nodes which don’t have any sons are called as leaf nodes.

22. What are called internal and external nodes?

The leaf nodes are called as external nodes and the non leaf nodes are called as internal nodes.

23. Define O notation.

To capture the concept of one function becoming proportional to another as it grows, a notation is which is called as O notation.

24. Define a graph.

A graph consists of a set of nodes (or vertices) and set of arcs (or edges).

25. Define weighted graph.

A number is associated with each arc of a graph is called a weighted graph. The number associated with the arc is called the weight.

26. Define minimum spanning tree.

Given a connected weighted graph G, it is often desired to create a spanning tree T for G such that the sum of the weights of the tree edges in T is as small as possible. Such a tree is called minimum spanning tree.

27. Define Depth First Traversal.

Visits the successors of a visited node before visiting any of its brothers.

In DFT, each visited node is placed in the stack

28. Define Breadth First Traversal.

Visits all successors of a visited node before visiting any successors of any of those successors.

In BFT, each visited node is placed on the queue.

29. What are called Dynamic data structures?

Structures which grow or shrink as the data they hold changes.

Example: Lists

30. Define Binary Search.

A technique for searching an ordered list in which we first check the middle item and – based on that comparison – "discard" half the data. The same procedure is then applied to the remaining half until a match is found or there are no more items left.

31. What are the advantages of linked lists?

· Overflow can never occur unless the memory is actually full.

· Insertions and deletions are easier than for contiguous (array) lists.

· With large records, moving pointers is easier and faster than moving the items themselves.

32. What are the disadvantages of linked lists?

· The pointers require extra space.

· Linked lists do not allow random access.

· Time must be spent traversing and changing the pointers.

· Programming is typically trickier with pointers.

33. Define Binary Search Trees.

A binary search tree is a binary tree where each node contains a key such that:

· All keys in the left subtree lesser than the key in the root.

· All keys in the right subtree greater the key in the root.

· The left and right subtrees of the root are again binary search trees.

34. What is the difference Data types vs. Data Structures?

· A data type is a well-defined collection of data with a well-defined set of operations on it.

· A data structure is an actual implementation of a particular abstract data type.