3 Types of Algorithm Evaluation Methods in OS: Deterministic Modeling, Queuing Models and Simulations

Performance Comparison or Algorithm Evaluation:

 

·         How do we select CPU scheduling algorithm for a particular system?

 

·         First problem is defining the criteria to be used in selecting an algorithm.

 

·         These criteria are often defined in terms of CPU utilization, response time, and throughput.

 

·         Criteria may include several measures like:

 

1. Maximize CPU utilization under constraint that maximum response time is 1 second.
2. Maximize throughput such that turnaround time is on average linearly proportional to total execution time.

 

 Different Evaluation Methods:

 1.    Deterministic Modeling:

• Analytic evaluation uses given algorithm and the system workload to produce formula or a number that evaluates performance of algorithm for that workload.
• Deterministic modeling is one type of analytic evaluation.
• This method takes particular pre-determined workload and defines performance of each algorithm for that workload.
• For example, assume we have following workload. All five processes arrive at time 0, in the order given, with the length of CPU burst in milliseconds:

 

Process	Burst time
P1	10
P2	29
P3	03
P4	07
P5	12

 

Consider FCFS, SJF and RR (Quantum = 10 millisecond) for this set of processes. Which algorithm would give minimum average waiting time?

 For FCFS algorithm,

Average waiting time = (0 + 10 + 39 + 42 + 49)/5 = 28 milliseconds

 

With non-preemptive SJF algorithm,

Average waiting time = (10 + 32 + 0 + 3 +20)/5 = 13 milliseconds

  

With Round Robin algorithm,

Average waiting time = (0 + 32 + 20 + 23 + 40)/5 = 23 milliseconds

 

• The deterministic modeling is simple and faster technique.
• It gives exact numbers, allowing algorithms to be compared.
• The drawback of deterministic modeling is that, it requires exact numbers of inputs, and its answers apply to only those cases.
• Main uses of deterministic modeling are in describing a scheduling algorithms and providing examples.

    2. Queuing Models or Queuing Analysis:

• A computer system is described as a network of servers.
• Each server has a queue of waiting processes.
• CPU is a server with its ready queue, as is IO system with its device queues.
• Knowing arrival rates and service rates, we can compute utilization, average queue length, average waiting time, etc.
• This area of study is called queuing network analysis.
• For example, let ‘n’ be average queue length, ‘W’ be average waiting time in queue, ‘λ’ be average arrival rate for new processes in a queue.
• If the system is in steady state, then number of processes leaving the queue must be equal to the number of processes that arrive.
• So, n=λ x W, this formula is called as Little's formula.
• It is useful because it is valid for any scheduling algorithm and arrival distribution.
• We can use this formula to compute one of the three variables, if we know the other two variables.
• Queuing analysis can be useful in comparing scheduling algorithms but it also has certain limitations.
• Mathematics of complicated algorithms or distribution can be difficult to work with.

 

3.  Simulations or Simulators:

• To get a more accurate evaluation of scheduling algorithms we can use simulations.
• Simulations involve programming a model of a computer system.
• Software data structures represent major components of a system.
• Simulator has a variable representing a clock. As its value is increased or decreased, simulator modifies system state to reflect activities of devices, processes and scheduler.
• As simulation executes, statistics that indicate algorithm performance are gathered and printed.
• Data to drive simulation can be generated in several ways. Most common method used is random number generator which is programmed to generate processes, CPU burst time, arrivals, departures, etc. according to probability distributions.
• Distributions may be defined mathematically or empirically.
• For empirical distribution, measurements of actual system under study are taken.
• Distribution driven simulation may be inaccurate due to relationships between successive events in the system.
• Trace tapes are used to correct this problem. A trace tape is created by monitoring real system, recording sequence of actual events.
• This sequence is then used to drive simulation.
• Trace tapes provides excellent way to compare two algorithms on exactly the same set of real inputs.
• Accurate results are produced with this method. 

 Drawbacks of simulations are as follows:

1.  It can be expensive; requires hours of computer time.
2. Most detailed simulation provides more accurate results but also requires more computer time.
3. Trace tapes can require large amounts of storage space.
4. Designing, coding, debugging of simulator can be a major task.

 

Difference between Primary key and Foreign key in DBMS (Primary key vs. Foreign key)

 

Differences between Primary key & Foreign key:

Primary Key	Foreign Key
Helps you to uniquely identify a record in the table.	It is a field in the table that is the primary key of another table.
It never accepts null values.	It may accept multiple null values.
Primary key is a clustered index and data in the DBMS table are physically organized in the sequence of the clustered index.	A foreign key cannot automatically create an index, clustered or non-clustered. However, you can manually create an index on the foreign key.
You can have the single Primary key in a table.	You can have multiple foreign keys in a table.

Various DBMS Keys: Super, Primary, Candidate, Alternate, Foreign, Compound and Composite

 

Various Keys in DBMS: Super, Primary, Candidate, Alternate, Foreign, Compound and Composite

 

·      A key in DBMS is an attribute or set of attributes which helps you to identify a row (tuple) in a relation (table).

·      They allow you to find the relation between two tables.

·      Keys help you uniquely identify a row in a table by a combination of one or more columns in that table.

·      Key is also helpful for finding unique record or row from the table.

·     Database key is also helpful for finding unique record or row from the table.

 

Example:

Emp_ID	FirstName	LastName
101	Michelle	Johnson
202	Tom	Rogers
303	Alex	Wills

In the above-given example, Emp_ID is a primary key because it uniquely identifies an employee record. In this table, no other employee can have the same employee ID.

 

Why we need a Key?

Some reasons for using a key in the DBMS system are as follows:

●     Keys help you to identify any row of data in a table. In a real-world application, a table could contain thousands of records. Moreover, the records could be duplicated. Keys ensure that you can uniquely identify a table record despite these challenges.

●     Allows you to establish a relationship between and identify the relation between tables

●     Help you to enforce identity and integrity in the relationship.

Types of Keys in Database Management System:

There are mainly 7 different types of keys in DBMS and each key has its different functionality. These keys are:

●     Super Key:

It is a group of single or multiple keys which identifies rows in a table.

 

●     Primary Key:

It is a column or group of columns in a table that uniquely identify every row in that table.

 

●     Candidate Key:

A candidate key is a set of attributes that uniquely identify tuples in a table. A candidate key is a super key with no repeated attributes.

 

●     Alternate Key:

An alternate key is a column or group of columns in a table that uniquely identify every row in that table.

 

●     Foreign Key:

A foreign key is a column that creates a relationship between two tables. The purpose of foreign key is to maintain data integrity and allow navigation between two different instances of an entity.

 

●     Compound Key:

It has two or more attributes that allow you to uniquely recognize a specific record. It is possible that each column may not be unique by itself within the database.

 

●     Composite Key:

An artificial key which aims to uniquely identify each record is called a surrogate key. These kinds of keys are unique because they are created when you don't have any natural primary key.

Super key:

A super key is a group of single or multiple keys which identifies rows in a table. A super key may have additional attributes that are not needed for unique identification.

Example:

EmpSSN	EmpNum	Empname
9812345098	AB05	Shawn
9876512345	AB06	Rosy
199937890	AB07	Mark

In the above-given example, EmpSSN and EmpNum, Empname are superkeys.

Primary Key:

A primary key is a column or group of columns in a table that uniquely identify every row in that table. The primary key cannot be a duplicate; meaning the same value can't appear more than once in the table. A table cannot have more than one primary key.

Rules for defining Primary key:

●     Two rows can't have the same primary key value

●     It must for every row to have a primary key value.

●     The primary key field cannot be null.

●     The value in a primary key column can never be modified or updated if any foreign key refers to that primary key.

Example:

In the following example, StudID is a Primary Key.

StudID	Roll No	First Name	LastName	Email
1	101	Tom	Price	abc@gmail.com
2	102	Nick	Cross	pqr@gmail.com
3	103	Dana	Nathan	xyz@yahoo.com

Alternate key:

An Alternate key is a column or group of columns in a table that uniquely identify every row in that table. A table can have multiple choices for a primary key but only one can be set as the primary key. All the keys which are not primary key are called an Alternate Key.

Example:

In this table, StudID, Roll No, Email are qualified to become a primary key. But since StudID is the primary key, Roll No, Email becomes the alternative key.

StudID	Roll No	First Name	LastName	Email
1	101	Tom	Price	abc@gmail.com
2	102	Nick	Cross	pqr@gmail.com
3	103	Dana	Nathan	xyz@yahoo.com

Candidate Key:

A candidate key is a set of attributes that uniquely identify tuples in a table. Candidate key is a super key with no repeated attributes. The Primary key should be selected from the candidate keys. Every table must have at least a single candidate key. A table can have multiple candidate keys but only a single primary key.

Properties of Candidate key:

●     It must contain unique values

●     Candidate key may have multiple attributes

●     Must not contain null values

●     It should contain minimum fields to ensure uniqueness

●     Uniquely identify each record in a table

Example: In the given table Stud ID, Roll No, and email are candidate keys which help us to uniquely identify the student record in the table.

StudID	Roll No	First Name	LastName	Email
1	101	Tom	Price	abc@gmail.com
2	102	Nick	Cross	pqr@gmail.com
3	103	Dana	Nathan	xyz@yahoo.com

 

Foreign key:

A foreign key is a column that creates a relationship between two tables. The purpose of foreign keys is to maintain data integrity and allow navigation between two different instances of an entity. It acts as a cross-reference between two tables as it references the primary key of another table.

Example:

DeptCode	DeptName
001	Science
002	English
005	Computer

 

Fig: Department table

 

Teacher ID	Fname	Lname
B002	Billy	Wright
B017	Sara	Jones
B009	Mike	Williams

 

Fig: Teacher table

 

In ex:, we have two table, teacher and department in a school. However, there is no way to see which teacher work in which department.

In this table, adding the foreign key in Deptcode to the Teacher name, we can create a relationship between the two tables.

Teacher ID	DeptCode	Fname	Lname
B002	002	Billy	Wright
B017	002	Sara	Jones
B009	001	Mike	Williams

 

Fig: Foreign key relationship

This concept is also known as Referential Integrity.

Compound key:

The compound key has two or more attributes that allow you to uniquely recognize a specific record. It is possible that each column may not be unique by itself within the database. However, when combined with the other column or columns the combination of composite keys become unique. The purpose of the compound key in database is to uniquely identify each record in the table.

Example:

OrderNo	ProductID	Product Name	Quantity
B005	JAP102459	Mouse	5
B005	DKT321573	USB	10
B005	OMG446789	LCD Monitor	20
B004	DKT321573	USB	15

 

In this ex:, OrderNo and ProductID can't be a primary key as it does not uniquely identify a record. However, a compound key of Order ID and Product ID could be used as it uniquely identified each record.

Composite key:

The composite key is a combination of two or more columns that uniquely identify rows in a table. The combination of columns guarantees uniqueness, though individually uniqueness is not guaranteed. Hence, they are combined to uniquely identify records in a table.

The difference between compound and the composite key is that any part of the compound key can be a foreign key, but the composite key may or maybe not a part of the foreign key.