lOMoARcPSD|50016256

LP1(SPOS & SPM) student manual

Computer Engineering (Savitribai Phule Pune University)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

LABORATORY PRACTICE 1

Student Manual

2022-2023

Department of Computer Engineering 1

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Amrutvahini College of Engineering, Sangamner

Department of Computer Engineering
Laboratory Practice 1
INDEX
Sr. Page Date of Remark Signature
Title of Experiments
No No Performance Submission
Part 1 - Group A:
Design suitable Data structures
and implement Pass-I and Pass-
II of a two-pass assembler for
pseudo-machine.
Implementation should consist
1 of a few instructions from each
category and few assembler
directives. The output of Pass-I
(intermediate code file and
symbol table) should be input
for Pass-II.
Design suitable data structures
and implement Pass-I and Pass-
II of a two-pass macro-
2 processor. The output of Pass-I
(MNT, MDT and intermediate
code file without any macro
definitions) should be input for
Pass-II.
Write a program to create
Dynamic Link Library for any
3 mathematical operation and
write an application program to
test it. (Java Native Interface /
Use VB or VC++).
Part 1 - Group B:
Write a program to solve
4 Classical Problems of
Synchronization using Mutex
and Semaphore.
Write a program to simulate
CPU Scheduling Algorithms:
5 FCFS, SJF (Preemptive), Priority
(Non-Preemptive) and Round
Robin (Preemptive).
6 Write a program to simulate

Department of Computer Engineering 2

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Memory placement strategies –

best fit, first fit, next fit and
worst fit.
7 Write a program to simulate
Page replacement algorithm.
Part-II Software Project Management

8 Create project plan for any

project statement.
Execute and monitor Project
9 Plan implemented in
assignment 1.
10 Generate dashboard and
reports.

CERTIFICATE
This is to certify that Mr/Ms __________________________________________Roll no-________
Examination seat no-________________ has performed above mentioned practical’s in the college.

Prof. R. L. Paikrao & Ms. K. U. Rahane Prof. R. L. Paikrao

Faculty member Incharge Head of the Department
Date: / / 2022

Department of Computer Engineering 3

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Experiment No.: 1
Title: Design suitable Data structures and implement Pass-I and Pass-II of a two- pass
assembler for pseudo-machine. Implementation should consist of a few instructions from
each category and few assembler directives. The output of Pass-I (intermediate code file and
symbol table) should be input for Pass-II.
1.1 Prerequisite:
 Basic Data Structure in Java.
 Concepts of Assembler.
1.2 Software Requirements:
 Eclipse SDK
1.3 Tools/Framework/Language Used:
 Java.
1.4 Hardware Requirement:
 PIV, 2GB RAM, 500 GB HDD.
1.5 Learning Objectives:
To interpret the data structures required in pass-I and pass-II and implementation of a
two-pass assembler.
1.6 Outcomes:
After completion of this assignment students can :
• Understand various data structures used in Two pass Assembler
• Implement two pass assembler for pseudo-machine.
1.7 Theory Concepts:

Assembler is a System program which is used to translate program written in Assembly

Language into machine language (Fig1.1). The translated program is called as object program.

Fig. 1.1 Assembler

Two Pass Assembler:
It handles forward reference problem easily (Fig 1.2).
Pass-I: (Analysis)
• Symbols are entered in the Symbol table
• Mnemonics and the corresponding opcodes are stored in a table called Mnemonic
table

Department of Computer Engineering 4

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

• Perform LC Processing
 Generate Intermediate code

Pass-II: (Synthesis)
• Synthesis the target form using the address information found in Symbol table.
• First pass constructs an Intermediated Representation (IR) of the source program for
use by the second pass.

Fig 1.2: Pass-I and Pass-II Assembler

Pass-I uses the following data structures:

1. OPTAB: -A table of mnemonic opcodes and related info.
2. SYMTAB: -Symbol Table.
3. LITTAB: -A table of literals used in the program
4. POOLTAB: - contains the literal no. of starting literal of each literal pool.
OPTAB: It contains the fields mnemonic, class and mnemonic opcode. The ‗class‘ field
indicates whether the opcode corresponds to an imperative statement (IS), a declaration
statement (DL) or an assembler directive (AD).If an imperative statement is present, then
the mnemonic info field contains the pair (machine opcode, instruction length) else it
contains the pair id of a routine to handle the declaration or directive statement.

Mnemonic TYPE OP-Code Mnemonic TYPE OP-Code

STOP IS 00 READ IS 09
ADD IS 01 PRINT IS 10
SUB IS 02 DC DL 01
MUL IS 03 DS DL 02
MOVER IS 04 START AD 01
MOVEM IS 05 END AD 02
COMP IS 06 ORIGIN AD 03
BC IS 07 EQU AD 04
DIV IS 08 LTORG AD 05

SYMTAB: It contains the fields address and length. The processing of an assembly statement

Department of Computer Engineering 5

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

begins with the processing of its label field. If it contains a symbol, the symbol and the value
in LC is copied into a new entry of SYMTAB. If it is an imperative statement, then length of
the machine instruction is simply added to the LC. The length is also entered into the symbol
table
LITTAB and POOLTAB: Literal table stores the literals used in the program and
POOLTAB stores the pointers to the literals in the current literal pool.

Algorithm for Pass-I:

1) loc_cntr := 0; (default value) pooltab_ptr :=1; POOLTAB[1]:=1; littab_ptr:=1;
2) While next statement is not an END statement
a) If label is present then
{
this_label:= symbol in label field; Enter(this_label, loc_cntr) in SYMTAB.
}
b) If an LTORG statement then
{
i Process literals LITTAB[POOLTAB[pooltab_ptr]…LITTAB[lit_tab_ptr-1] to
allocate memory and put the address in the address field. Update location
counter accordingly.
ii pooltab_ptr := pooltab_ptr +1;
iii POOLTAB[pooltab_ptr]:=littab_ptr;
}
c) If START or ORIGIN statement then
{
loc_cntr := value specified in the operand field;
}
d) If an EQU statement then
{
i. this_addr := value of <address_spec>;
ii. Correct the symbtab entry for this_label to (this_label,this_addr).
}
e) If a declaration statement then
{
i. code:= code of the declaration statement;
ii. size := size of memory are required by DC/DS
iii. loc_cntr := loc_cntr + size;
iv. Generate IC ‗(DL, code)…‘
}
f) If an imperative statement then
{
i. code:= machine opcode from OPTAB;
ii. loc_cntr := loc_cntr + instruction length from OPTAB;
iii. If operand is a literal then
{
this_literal := literal in operand field; LITTAB[littab_ptr]:= this_literal;

Department of Computer Engineering 6

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

littab_ptr= littab_ptr +1;

}
else (i.e. operand is a symbol)
{
this_entry := SYMTAB entry number of operand
Generate IC ‗(IS,code)(S,this_entry)‘;
}
3.
a) Perform step 2(b).
b) Generate IC‘(AD, 02)‘.
c) Go to Pass II.

Pass-II: (Synthesis)
PASS-II takes intermediate code as an input from PASS-I and converts it into
equivalent machine code.
Pass-II uses the following data structures:
1. SYMTAB: -Symbol Table.
2. LITTAB: -A table of literals used in the program
3. Intermediate Code
Pass-II reads each instruction in intermediate code and converts it into machine
language instruction.
Machine code format is:

Algorithm of Pass II Assembler

It has been assumed that the target code is to be assembled in the area named
code_area.
1. Code_area_adress= address of code_area; Pooltab_ptr=1; Loc_cntr=0;
2. While next statement is not an END statement
a) Clear machine_code_buffer;
b) If an LTORG statement
i) Process literalsin LITTAB and assemble the
literalsin machine_code_buffer.
ii) Size= size of memory area required for literals
iii) Pooltab_ptr=pooltab_ptr +1;
c) If a START or ORIGIN statement
i) Loc_cntr=value specified in operand field;
ii) Size=0;
d) If a declaration statement
i) If a DC statement then assembles the constant

Department of Computer Engineering 7

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

in machine_code_buffer;
ii) Size= size of memory area required by DC/DS;
e) If an imperative statement
i) Get operand address from SYMTAB or LITTAB
ii) Assemble instruction in machine_code_buffer;
iii) Size=size of instruction;
f) If size≠ 0 then
i) Move contents of machine_code_buffer to the address
code_area_address + loc_cntr;
ii) Loc_cntr=loc_cntr+size;
3. Processing end statement
a) Perform steps 2(b) and 2(f)
b) Write code_area into output file.

Testing:
SAMPLE PROGRAM Input
Source Code
START 200
MOVER AREG =‘5’
MOVEM AREG A
LOOP MOVER AREG A
MOVER CREG B
ADD CREG =‘1’
LTORG
NEXT1 SUB AREG =‘1’
ORIGIN LOOP+6
MUL CREG B
A DS 2
B DC ‘3’
NEXT2 EQU LOOP
END

EXPECTED OUTPUT:
POOLTAB
Index PoolNo
1 1
2 3

Department of Computer Engineering 8

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

SYMTAB LITTAB

SymNo SYMBOL ADDRESS SIZE LitNo LITERAL ADDRESS

01 A 209 2 01 =‘5’ 205
02 LOOP 202 1 02 =‘1’ 206
03 B 211 1 03 =‘1’ 212
04 NEXT1 207 1
05 NEXT2 202 1

Intermediate Code Machine Code

(PASS-I output) (PASS-II output)
(AD,01) (C,200)
200) (IS,04) (RG,01) (L,01) 200) +04 1 005
201) (IS,05) (RG,01) (S,01) 201) +05 1 209
202) (IS,04) (RG,01) (S,01) 202) +04 1 209
203) (IS,04) (RG,03) (S,03) 203) +04 3 211
204) (IS,01) (RG,03) (L,02) 204) +01 3 206
205) (DL,01) (C,5) 205) +00 0 005
206) (DL,01) (C,1) 206) +00 0 001
207) (IS,02) (RG,01) (L,03) 207) +02 1 212
(AD,03) (C,208
208) (IS,04) (RG,03) (S,03) 208) +04 3 211
209) (DL,02) (C,2)
211) (DL,01) (C,3)
(AD,04) (C,202)
(AD,02)
212) (DL,01) (C,1) 212) +00 0 001

Conclusion:-
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Department of Computer Engineering 9

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Questions: -

1. What is an assembler along with basic functions of it?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

2. What is cross assembler?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

3. What are various advanced assembler directives?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

4. What is Forward Referencing? How to solve it in two pass assembler??

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Department of Computer Engineering 10

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

5. What is output of pass 1 and pass 2 of assembler?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Staff Signature & Date

Department of Computer Engineering 11

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Experiment No.: 2
Title: Design suitable data structures and implement Pass-I and Pass-II of a two- pass macro-
processor. The output of Pass-I (MNT, MDT and intermediate code file without any macro
definitions) should be input for Pass-II.
1.1 Prerequisite:
 Basic Data Structure in Java.
 Concepts of macro-processor.
1.2 Software Requirements:
 Eclipse SDK
1.3 Tools/Framework/Language Used:
 Java.
1.4 Hardware Requirement:
 PIV, 2GB RAM, 500 GB HDD.
1.5 Learning Objectives:
To interpret the data structures and implement pass-I and pass-II two- pass macro-
processor.
1.6 Outcomes:
Students will be able to:
 Understand various data structures used in Two pass macro-processor
 Implement two pass macro-processor for pseudo-machine.
1.7 Theory:
Macro-Processor is a system program used to identify the macro call and
performing macro expansion.

Features of macro processor:

1. Recognize the macro definition
2. Save macro definition
3. Recognize the macro call
4. Perform macro expansion
Typically, MACRO is defined at start of program or at end of program.
Macro Definition Syntax: -
1) Macro header: - It contains keyword ‗MACRO‘.

Department of Computer Engineering 12

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

2) Macro prototype statement syntax :-

< Macro Name > [ & < Formal Parameters > ]
3) Model Statements: - It contains 1 or more simple assembly statements,
which willreplace MACRO CALL, while macro expansion.
4) MACRO END MARKER: - It contains keyword ‗MEND‘.
MACRO CALL :-
< MACRO NAME > [<ACTUAL Parameters > ]
Example of MACRO :-
MACRO
INCR & MEM, &
VAL, & RMOVER &
R, & MEM ADD &
R, & VAL
MOVEM & R, & MEM
MEND
START
300
INCR A, B,
BREGSTOP
A DS 1
B DS 1
END
Macro Expansion:-
Macro expansion is the task of replacing macro call by statements from macro body.
Example of MACRO Expansion for above program :-
START 300
MOVER BREG, A
ADD BREG, B
MOVEM BREG, A
STOP
A DS 1
B DS 1
END

Forward reference Problem

The assembler specifies that the macro definition should occur anywhere in the
program. So there can be chances of macro call before it‘s definition witch
gives rise to the forwards reference problem of macro.

Department of Computer Engineering 13

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Due to which macro is divided into two passes:

1. PASS 1-Recoganize macro definition save macro definition
2. PASS 2-Recoganize macro call perform macro expansion
Pass 1 data bases:
1. The input macro source deck.
2. The output macro source deck copy for use by pass 2.
3. The macro definition table (MDT), used to store the body of the macro
definitions.
4. The macro name table (MNT), used to store the names of defined macros.
5. The macro definition table counter (MDTC), used to indicate the next
availableentry in the MDT.
6. The macro name table counter (MNTC), used to indicate the next
availableentry in the MNT.
7. The argument list array (ALA).
Algorithm for Pass 1 of Macro
Processor –Processing Macro
Definitions
1. Initialize MDTC and MNTC.

2. Read the next source statement of the program.

3. If the statement contains MACRO pseudo-op. go to Step 6.
4. Output the instruction of the program.

5. If the statement contains END pseudo-op, go to Pass 2, else go to Step 2.

6. Read the next source statement of the program.

7. Make an entry of the macro name and MTDC into MNT at location
MNTC andincrement the MNTC by 1.
8. Prepare the parameter (arguments) list array.

9. Enter the macro name into the MDT and increment the MTDC by 1.

10. Read the next card and substitute index for the parameters (arguments).\

11. Enter the statement into the MDT and increment the MDT by 1.

12. If MEND pseudo-op found, go to Step 2, else go to Step 10.

Department of Computer Engineering 14

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Pass 2 data bases:

1. The copy of the input macro source deck.

2. The output expanded source deck to be used as input to the assembler.

3. The macro definition table (MDT), created in pass1.

4. The macro name table (MNT), created in pass1.

5. The macro definition table pointer (MDTP), used to indicate the next
line oftext to be used during macro expansion.
6. The argument list array (ALA), used to substitute macro call arguments
for theindex markers in the stored macro definition.
Algorithm for Pass 2 of Macro Processor –
Processing for Calls and Expansion of
Macro
1. Read the next source statement copied bypass 1.

2. Search into the MNT for a record and evaluate the operation code.

3. If the operation code has a macro name, go to Step 5.

4. Write the statement to the expanded source file.

5. If END pseudo-op found, pass the entire expanded code to the

assembler forassembling and stop. Else go to Step 1.
6. Update the MDTP to the MDT index from the MNT entry.
7. Prepare the parameter (argument) list array.
8. Increment the MDTP by 1.
9. Read the statement from the current MDT and substitute actual
parameters(arguments) from the macro call.
10. If the statement contains MEND pseudo-op, go to Step 1, else
write theexpanded source code and go to Step 8.
SAMPLE PROGRAM Input
MACRO INCR &M,&N
MOVEM &N, &M
ADD &N, &M
MEND
MACRO ADDITION &X, &Y,&AREG
ADD &AREG, &X
SUB &AREG, &Y
MEND
START
MOVER BREG, A
ADD BREG, B

Department of Computer Engineering 15

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

ADDITION A, B, CREG
MOVEM BREG, A
INCR B, CREG
STOP
A DS 1
B DS 1
END
Expected Output:

START
MOVER BREG, A
ADD BREG, B
ADD CREG, A
SUB CREG, B
MOVEM
BREG, A
MOVEM
CREG, BADD
CREG, B
STOP
A DS 1
B DS 1
END

MDT: MNT:
Index Card
0 MACRO INCR &M,&N S. No. Name DT index

1 MOVEM #1, #0 0 INCR 0

2 ADD #1, #0 1 ADDITION 4
3 MEND
4 MACRO ADDITION
&X,&Y,&AREG
5 ADD #2, #0
6 SUB #2, #1
7 MEND

Department of Computer Engineering 16

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

ALA (INCR) ALA(ADDITION)

Index Argument
Index Argument
0 A
0 B
1 B
1 CREG
2 CREG

Conclusion:-
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Questions:-

1. Distinguish between macro and a subroutine?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

2. Define and Distinguish between parameters that can be used in macros?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

3. Explain the role of stack in nested macros?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Department of Computer Engineering 17

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

4. Which database is used in pass 1 and pass 2 of macro processor?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

5. What is advantage of Macro definition?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Staff Signature & Date

Department of Computer Engineering 18

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Experiment No.: 3
Title: Write a program to create Dynamic Link Library for any mathematical operation and
write an application program to test it. (Java Native Interface / Use VB or VC++).
1.1 Prerequisite:
 Basic concepts of Dynamic Link Library.
 Basic of Visual Basic.
1.2 Software Requirements:
 VB or VC++.
1.3 Tools/Framework/Language Used:
 VB or VC++.
1.4 Hardware Requirement:
 PIV, 2GB RAM, 500 GB HDD.
1.5 Learning Objectives:
Understand Dynamic Link Library.
1.6 Outcomes:
Students will be able to
• Understand use and working of DLL
• Implement modular programming with the help of DLL.

1.7 Theory Concepts:

A dynamic link library (DLL) is a library of functions and procedures that can be
called from an application or another DLL.
DLL has two major functions: It permits the sharing of code. The same DLL can be
used by many other DLLs and applications. The Win32 API, for instance, is
implemented as a series of Windows DLLs. Moreover, as long as multiple
processes load the same DLL at the same base address, they can share the code in
the DLL. In other words, a single DLL in memory can be accessed by multiple
processes.
It allows for component-based and modular development, which makes
development and the upgrade process easier. Ordinarily, when a static library is
used in application development, the library's modules must be linked into the
finished application. With dynamic linking, the modules reside in a separate DLL
file that is loaded dynamically, either when the application loads or when its
member functions are needed.
A dynamic link library may include internal functions, which can be called only
from within the DLL. Its main purpose, however, is to provide exported functions-
- that is, functions that reside in a module of the DLL and can be called from other

Department of Computer Engineering 19

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

DLLs and applications. Frequently, a definition (.def) file is used in C/C++

projects to list a DLL's exports.
DLL implementation is done in two parts:
1. Create a dll containing four basic mathematical functions.
2. Create a console application in Visual Basic which links with the dll
just created and uses the function stored in the dll.

Part 1: Create DLL

Follow the steps given below:
1. Open visual studio 2010 from the start menu
2. From the file menu choose New Project option.
3. In the New window that appears choose Class library, give a valid project
name for. E.g. ClassLibrary1 and choose a valid project location if
required.
4. Write following code in
ClassLibrary Public Class
MyFunctions
Public Function AddMyValues (ByVal Value1 As Double, ByVal Value2 As Double)
Dim Result As Double
Result = Value1 + Value2
Return Result
End Function
End Class
5. Save and Build the solution. DLL is created (ClassLibrary1.dll) at the path.
(―C:\ Users \ Visual Studio\2010\Projects\ ClassLibrary1\
ClassLibrary1 \ bin\Debug\ClassLibrary1.dll).

Department of Computer Engineering 20

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Part II: Create console application to use a dll

1. Start ->Microsoft Visual Studio 2010 -> New ->Project -> Give Project name as
―WindowsApplication5‖->Design the following form

2. Solution Explorer -> right click on Project Name -> Add References ->

Department of Computer Engineering 21

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

3. Add the ―ClassLibrary1.dll‖ file(this file is stored at the path –―C:\Users\Visual

Studio2010\Projects\ClassLibrary1\ClassLibrary1\bin\Debug) (this path may vary
from computer to computer)

4. Write the following code in “WindowsApplication5”

projectImports ClassLibrary1
Public Class Form1
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As
System.EventArgs) Handles Button1.Click
Dim Obj As New ClassLibrary1.MyFunctions TextBox3.Text =
Obj.AddMyValues(CDbl(TextBox1.Text),CDbl(TextBox2.Text)).ToString
End Sub
End Class
5. Run the application (Save All ->Build -> Build Solution -> Run)
Testing:
Give input in textboxes. Observe Result obtained when you click on command buttons.

Department of Computer Engineering 22

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Conclusion:-
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Questions:-

1. Explain the need of Dll?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

2. Explain the console application?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

3. Explain the various libraries which are need for creating the Dll?
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

4. Explain the method of declaration and definition of method?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Department of Computer Engineering 23

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

5. How to create a simple Dll?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Staff Signature & Date

Department of Computer Engineering 24

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Experiment No.: 4
Title: Write a program to solve classical problems of synchronization using mutex and
semaphore.
1.1 Prerequisite:
 Basic concepts of mutes and semaphore.
1.2 Software Requirements:
 Eclipse IDE.
1.3 Tools/Framework/Language Used:
 Java.
1.4 Hardware Requirement:
 PIV, 2GB RAM, 500 GB HDD.
1.5 Learning Objectives:
 To understand reader writer synchronization problem
 To solve reader-writer synchronization problem using mutex and semaphore
1.6 Outcomes:
After completion of this assignment students can implement synchronization using
mutex and semaphore.
1.7 Theory Concepts:
 There is a data area shared among a number of processor registers.
 The data area could be a file, a block of main memory, or even a bank of
processor registers.
 There are a number of processes that only read the data area (readers)
and a number that only write to the data area (writers).
The conditions that must be satisfied are
 Any number of readers may read simultaneously read the file.
 Only one write at a time may write to the file.
 If a writer is writing to the file, no reader may read it.
Semaphore:
Semaphores are system variables used for synchronization of process
Two types of Semaphore:
1. Counting semaphore – integer value can range over an unrestricted domain
2. Binary semaphore –
Integer value can range only between 0 and 1; can be simpler to implement.
Also known as mutex locks
Semaphore functions:
Package: import java.util.concurrent.Semaphore;
To initialize a semaphore:

Department of Computer Engineering 25

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Semaphore Sem1 = new Semaphore(1);

To wait on a semaphore:
/* Wait (S) while S<=0 no-op;
S - -;
*/ Sem1.acquire();
To signal on a semaphore:
/* Signal(S) S ++;
*/ mutex.release();

Algorithm for Reader Writer:

1. import java.util.concurrent.Semaphore;
2. Create a class RW
3. Declare semaphores – mutex and wrt
4. Declare integer variable readcount = 0
5. Create a nested class Reader implements Runnable
a. Override run method (Reader Logic)
 wait(mutex);
 readcount := readcount +1;
 if readcount = 1 then
 wait(wrt);
 signal(mutex);
 …
 reading is performed
 …
 wait(mutex);
 readcount := readcount – 1;
 if readcount = 0 then signal(wrt);
 signal(mutex):
Create a nested class Writer implements Runnable
a. Override run method (Writer Logic)
i. wait(wrt);
ii. …
iii. writing is performed
iv. …
v. signal(wrt);
Create a class main
a. Create Threads for Reader and Writer
b. Start these thread

Department of Computer Engineering 26

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Testing:
Input:
Enter Number of Readers
Enter Number of Writers

Output:
Execution of Readers and Writers
Test cases:
1) Create 5 readers first and then 5 writers and check their sequence of execution.
2) Create 5 writers first and then 5 readers and check their sequence of execution.
3) Create 5 writers and 5 readers alternatively and check their sequence of execution.

Conclusion:-
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Questions:-

1. What is semaphore and mutex?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

2. Explain different types of semaphore?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Department of Computer Engineering 27

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

3. Explain reader writer problem?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

4. What is critical section?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

5. Explain wait and sequence function?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Staff Signature & Date

Department of Computer Engineering 28

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Experiment No.: 5
Title: Write a program to simulate CPU Scheduling Algorithms: FCFS, SJF (Preemptive),
Priority (Non-Preemptive) and Round Robin (Preemptive).
1.1 Prerequisite:
 Basic Data Structure in Java.
 Concepts of scheduling.
1.2 Software Requirements:
 Eclipse SDK
1.3 Tools/Framework/Language Used:
 Java.
1.4 Hardware Requirement:
 PIV, 2GB RAM, 500 GB HDD.
1.5 Learning Objectives:
Understand the concept of scheduling algorithm.
1.6 Outcomes:
After completion of this assignment students can perform scheduling of process by
preemptive and non-preemptive methods in Java.
1.7 Theory Concepts:
CPU Scheduling is a process of determining which process will own CPU for
execution while another process is on hold. The main task of CPU scheduling is to
make sure that whenever the CPU remains idle, the OS at least select one of the
processes available in the ready queue for execution. The selection process will be
carried out by the CPU scheduler. It selects one of the processes in memory that
are ready for execution. Some process scheduling algorithms are −
1 First-Come, First-Served (FCFS) Scheduling
2 Shortest-Job- First(SJF) Scheduling
3 Priority Scheduling
4 Round Robin(RR) Scheduling
These algorithms are either non-preemptive or preemptive.
Non-preemptive algorithms are designed so that once a process enters the running
state, it cannot be preempted until it completes its allotted time, whereas the
preemptive scheduling is based on priority where a scheduler may preempt a low
priority running process anytime when a high priority process enters into a ready
state.

CPU Scheduling Criteria

A CPU scheduling algorithm tries to maximize and minimize the following:

Department of Computer Engineering 29

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Maximize:
CPU utilization: CPU utilization is the main task in which the operating system
needs to make sure that CPU remains as busy as possible. It can range from 0
to 100 percent. However, for the RTOS, it can be range from 40 percent for low-
level and 90 percent for the high-level system.
Throughput: The number of processes that finish their execution per unit time is
known Throughput. So, when the CPU is busy executing the process, at that time,
work is being done, and the work completed per unit time is called Throughput.

Minimize:
Waiting time: Waiting time is an amount that specific process needs to wait in the
ready queue.
Waiting Time=Turnaround Time - CPU Time

Response time: It is an amount to time in which the request was submitted until
the first response is produced.
Turnaround Time: Turnaround time is an amount of time to execute a specific
process. It is the calculation of the total time spent waiting to get into the memory,
waiting in the queue and, executing on the CPU. The period between the time of
process submission to the completion time is the turnaround time.
Turnaround Time= Finish Time - Arrival Time

First Come First Serve (FCFS)

Jobs are executed on first come, first serve basis. It is a non-preemptive scheduling
algorithm. Easy to understand and implement. Its implementation is based on
FIFO queue. Poor in performance as average wait time is high.

Example of First Come First Serve Scheduling Algorithm

Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

Department of Computer Engineering 30

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

CPU Arrival Start End Turnaround Waiting

Process Time Time Time Time time time
P1 24 0 0 24 24 0
P2 3 0 24 27 27 24
P3 3 0 27 30 30 27
Total 81 51
Average Turnaround Time= 81/3
=27
Average waiting time: 51/3 =
17
Shortest Job First (SJF)
SJF is a non-preemptive, pre-emptive scheduling algorithm. Best approach to
minimize waiting time. Easy to implement in Batch systems where required
CPU time is known in advance. Impossible to implement in interactive systems
where required CPU time is not known. The processer should know in advance
how much time process will take.
Example of Shortest Job First Scheduling Algorithm

The Gantt Chart for the schedule is:

CPU Arrival End Turnaround Waiting

Process Time Time Time time time
P1 7 0 16 16 9
P2 4 2 7 5 1
P3 1 4 5 1 0
P4 4 5 11 6 2
Total 28 12

Department of Computer Engineering 31

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Priority Based Scheduling

Priority scheduling is a non-preemptive algorithm and one of the most common
scheduling algorithms in batch systems. Each process is assigned a priority.
Process with highest priority is to be executed first and so on. Processes with
same priority are executed on first come first served basis. Priority can be decided
based on memory requirements, time requirements or any other resource
requirement.
Example Priority Scheduling Algorithm

Wait time of each process is as follows −

Process Wait Time : Service Time - Arrival Time
P0 9–0=9
P1 6–1=5
P2 14 – 2 = 12
P3 0–0=0
Average Wait Time: (9+5+12+0) / 4 = 6.5

Shortest Remaining Time

Shortest remaining time (SRT) is the preemptive version of the SJN algorithm. The processor
is allocated to the job closest to completion but it can be preempted by a newer ready job with
shorter time to completion. Impossible to implement in interactive systems where required
CPU time is not known. It is often used in batch environments where short jobs need to give
preference.

Round Robin Scheduling

Round Robin is the preemptive process scheduling algorithm. Each process is provided a fix
time to execute, it is called a quantum. Once a process is executed for a given time period, it is
preempted and other process executes for a given time period. Context switching is used to
save states of preempted processes.
Round Robin Scheduling Algorithm

Department of Computer Engineering 32

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Wait time of each process is as follows −

Process Wait Time : Service Time - Arrival Time
P0 (0 - 0) + (12 - 3) = 9
P1 (3 - 1) = 2
P2 (6 - 2) + (14 - 9) + (20 - 17) = 12
P3 (9 - 3) + (17 - 12) = 11
Average Wait Time: (9+2+12+11) / 4 = 8.5

Conclusion:-
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Questions:-

1. What is Scheduling?
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

2. What are different types of scheduling?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Department of Computer Engineering 33

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

3. What is premptive and non preemptive scheduling?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

4. Different preemptive and non preemptive scheduling algorithm?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

5. Which is the best scheduling algorithm for distributed operating system?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Staff Signature & Date

Department of Computer Engineering 34

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Experiment No.: 6
Title: Write a program to simulate memory placement strategies First Fit, Best Fit, Worst Fit
and Next Fit
1.1 Prerequisite:
 Basic Data Structure in Java.
 Memory placement strategies.
1.2 Software Requirements:
 Eclipse SDK
1.3 Tools/Framework/Language Used:
 Java.
1.4 Hardware Requirement:
 PIV, 2GB RAM, 500 GB HDD.
1.5 Learning Objectives:
Understand the concept of memory placement strategies.
1.6 Outcomes:
After completion of this assignment students can:
• Differentiate various memory placement algorithms
• Simulate and Implement memory placement algorithms.
1.7 Theory Concepts:
In the operating system, the following are four common memory management techniques.
Single contiguous allocation: Simplest allocation method used by MS-DOS. All memory
(except some reserved for OS) is available to a process.
Partitioned allocation: Memory is divided into different blocks or partitions. Each process is
allocated according to the requirement.
Paged memory management: Memory is divided into fixed-sized units called page frames,
used in a virtual memory environment.
Segmented memory management: Memory is divided into different segments (a segment is
a logical grouping of the process‘ data or code).In this management, allocated memory
doesn‘t have to be contiguous.
Fragmentation
As processes are loaded and removed from memory, the free memory space is broken into
little pieces. It happens after sometimes that processes cannot be allocated to memory blocks
considering their small size and memory blocks remains unused. This problem is known as
Fragmentation.
Fragmentation is of two types –
1. External fragmentation
Total memory space is enough to satisfy a request or to reside a process in it, but it is not
contiguous, so it cannot be used.

Department of Computer Engineering 35

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

2. Internal fragmentation
Memory block assigned to process is bigger. Some portion of memory is left unused, as it
cannot be used by another process.
Most of the operating systems (for example Windows and Linux) use Segmentation with
Paging. A process is divided into segments and individual segments have pages.
In Partition Allocation, when there is more than one partition freely available to
accommodate a process‘s request, a partition must be selected. To choose a particular
partition, a partition allocation method is needed. A partition allocation method is
considered better if it avoids internal fragmentation.
When it is time to load a process into the main memory and if there is more than one free
block of memory of sufficient size then the OS decides which free block to allocate.
There are different Placement Algorithm:
A. First Fit
B. Best Fit
C. Worst Fit
D. Next Fit

A. First Fit
In the first fit approach is to allocate the first free partition or hole large enough which can
accommodate the process. It finishes after finding the first suitable free partition.
Advantage
Fastest algorithm because it searches as little as possible.
Disadvantage
The remaining unused memory areas left after allocation become waste if it is too smaller.
Thus request for larger memory requirement cannot be accomplished.

B. Best Fit
The best fit deals with allocating the smallest free partition which meets the requirement of
the requesting process. This algorithm first searches the entire list of free partitions and
considers the smallest hole that is adequate. It then tries to find a hole which is close to
actual process size needed.
Advantage
Memory utilization is much better than first fit as it searches the smallest free partition first
available.

Disadvantage
It is slower and may even tend to fill up memory with tiny useless holes.
C. Worst fit
In worst fit approach is to locate largest available free portion so that the portion left will be

Department of Computer Engineering 36

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

big enough to be useful. It is the reverse of best fit.

Advantage
Reduces the rate of production of small gaps.
Disadvantage
If a process requiring larger memory arrives at a later stage, then it cannot be
accommodated as the largest hole is already split and occupied.

D. Next fit
Next fit is a modified version of first fit. It begins as first fit to find a free partition. When
called next time it starts searching from where it left off, not from the beginning.

Algorithms:
1. First Fit algorithm/pseudo code
o Read all required input
o FOR i<-0 to all jobs ‗js‘
 FOR j<-0 to all blocks ‗bs‘
o IF block[j]>=jobs[i]
 Check jth block is already in use or free
 Continue and search next free block
 Otherwise allocate jth block to ith job
o Display all job with allocated blocks and fragmentation
2. First Fit algorithm/pseudo code

Department of Computer Engineering 37

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

o Read all required input

o FOR i<-0 to all jobs ‗js‘
 SET BestInd= -1
 FOR j<-0 to all blocks ‗bs‘
o IF block[j]>=jobs[i]
 IF Block is free and BestInd==-1 THEN
SETBestInd=j
 ELSEIF Block is free and
block[BestInd]>block[j] THEN SET
BestInd=j
 ELSE continue with next block
 Continue and search next free block
 IF BestInd!=-1 THEN allocate jth block to ith job
o Display all job with allocated blocks and fragmentation
3. Worst Fit Algorithm/Pseudo code
o Read all required input
o FOR i<-0 to all jobs ‗js‘
 SET WstInd=-1
 FOR j<-0 to all blocks ‗bs‘
o IF block[j]>=jobs[i]
 IF Block is free and WstInd==-1
THEN SETWstInd=j
 ELSEIF Block is free and
block[WstInd]<block[j] THEN SET
WstInd=j
 ELSE continue with next block
 Continue and search next free block
 IF WstInd!=-1 THEN allocate jth block to ith job
o Display all job with allocated blocks and fragmentation

Input:
• No. of jobs (js) & No. of blocks (bs)

Department of Computer Engineering 38

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

• Job size of all jobs & Block size of all

blocksFor Example:
js=4 bs=5
block[] = {100, 500, 200, 300, 600};
jobs[] = {212, 417, 112, 426};
Output:
Sample output of Worst Fit algorithm (same way generate o/p for other algorithms)-
Process No. Process Size Block no.
1 212 5
2 417 2
3 112 4
4 426 Not Allocated

Conclusion:-
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Questions:-

1. Explain various memory allocation strategies in detail?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

2. Which algorithm is best and why?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Department of Computer Engineering 39

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

3. What is collision and how to handle it?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

4. What is need of allocating blocks to jobs?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

5. What is the time taken by each algorithm for execution?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Staff Signature & Date

Department of Computer Engineering 40

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

Experiment No.: 7
Title: Write a Program to simulate page replacement algorithm

1.1 Prerequisite:
 Basic Data Structure in Java.
 Page replacement.
1.2 Software Requirements:
 Eclipse SDK
1.3 Tools/Framework/Language Used:
 Java.
1.4 Hardware Requirement:
 PIV, 2GB RAM, 500 GB HDD.
1.5 Learning Objectives:
 To study page replacement policies to understand memory management.
 To understand efficient frame management using replacement policies.
1.6 Outcomes:
After completion of this assignment students can perform:
 Differentiate various page replacement algorithms.
 Simulate and Implement page replacement algorithms

1.7 Theory Concepts:

PAGE REPLACEMENT:
Page Fault: Absence of page when referenced in main memory during paging leads to a
page fault.
Page Replacement: Replacement of already existing page from main memory by the
required new page is called as page replacement. And the techniques used for it are called
as page replacement algorithms.
NEED OF PAGE REPLACEMENT:
Page replacement is used primarily for the virtual memory management because in
virtual memory paging system principal issue is replacement i.e. which page is to be
removed so as to bring in the new page, thus the use of the page replacement algorithms.
Demand paging is the technique used to increase system throughput. To implement
demand paging page replacement is primary requirement. If a system has better page
replacement technique it improves demand paging which in turn drastically yields system
performance gains.
PAGE REPLACEMENT POLICIES:
1. Determine which page to be removed from main memory.
2. Find a free frame.

Department of Computer Engineering 41

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

a. If a frame is found use it

b. if no free frame found, use page replacement algorithm toselect a victim
frame.
c. Write the victim page to the disk.
3. Read the desired page into the new free frame, change the page and frame
tables.
4. Restart the user process.
PAGE REPLACEMENT ALGORITHMS:
1. FIFO
This is the simplest page replacement algorithm. In this algorithm, the operating
system keeps track of all pages in the memory in a queue, the oldest page is in the
front of the queue. When a page needs to be replaced page in the front of the
queue is selected for removal.

2. OPTIMAL PAGE REPLACEMENT ALGORITHM: Replace the page that will

not be used for longest period of time as compared to the other pages in main
memory. An optimal page replacement algorithm has lowest page fault rate of
allalgorithm. It is called as OPT or MIN.

ADVANTAGE:
This algorithm guarantees the lowest possible page-fault rate for a fixed no. of frames.

DISADVANTAGE:
The optimal page replacement algorithm is very difficult to implement, as it requires the
knowledge of reference strings i.e. strings of memory references.

3. LEAST RECENTLY USED (LRU): LRU algorithm uses the time of the page‘s last usage.
It uses the recent past as an approximation of the near future, then we can replace the

Department of Computer Engineering 42

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

page that has not been used for the longest period of the time i.e. the page having larger
idle time is replaced.
ADVANTAGE:
The LRU policy is often used for page replacement and isconsidered to be good.

DISADVANTAGES:
1) It is very difficult to implement.
2) Requires substantial hardware assistance.
3) The problematic determination of the order for the frames defined by the time
of last usage
Algorithm/Flowchart:
1. FIFO :
1. Start the process
2. Read number of pages n
3. Read number of pages no
4. Read page numbers into an array a[i]
5. Initialize avail[i]=0 .to check page hit
6. Replace the page with circular queue, while re-placing check page availability in
the frame Place avail[i]=1 if page is placed in the frame Count page faults
7. Print the results.
8. Stop the process.

2. LEAST RECENTLY USED

1. Start the process
2. Declare the size
3. Get the number of pages to be inserted
4. Get the value
5. Declare counter and stack
6. Select the least recently used page by counter value
7. Stack them according the selection.
8. Display the values
9. Stop the process

Department of Computer Engineering 43

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

3. OPTIMAL ALGORTHIM:
1. Start Program
2. Read Number Of Pages And Frames 3.Read Each Page Value
4. Search For Page In The Frames
5. If Not Available Allocate Free Frame
6. If No Frames Is Free Replace The Page With The Page That Is Least Used
7. Print Page Number Of Page Faults
8. 8.Stop process.
Input:
1. Number of frames
2. Number of pages
3. Page sequence
Output:
1. Sequence of allocation of pages in frames (for each algorithm)
2. Cache hit and cache miss ratio.
Conclusion:-
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
Questions:-

1. What is paging and page fault?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Department of Computer Engineering 44

Downloaded by Shweta Borse (shwetaborse58@gmail.com)
 lOMoARcPSD|50016256

2. Which Page replacement algorithm is best?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

3. Explain the scenario in which page replacement algorithm is used?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

4. Explain what is Belody‘s Anomaly?

______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
5. Explain what is counting based page replacement algorithms?
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________

Staff Signature & Date

Department of Computer Engineering 45

Downloaded by Shweta Borse (shwetaborse58@gmail.com)