Lab Assignment: Operating System - Suwarnika Srivastava

**LAB ASSIGNMENT** **[Name]- Suwarnika Srivastava** **[Reg. NO.]- 23BSA10092** **[Subj]- Operating System** **[Course Code]- CSE3003** **[Slot]- A21+A22+A23** **Ques.1) Process Creation and Management** ** Objective: Understand process creation, termination, and management in the OS.** ** Tasks:** **o Write a C program to create a new process using fork().** **o Implement the parent-child process relationship and demonstrate process** **termination.** **o Use exec() to replace a process image.** **o Demonstrate the use of process IDs and status handling.** **Ans-** - **C program to create a new process using fork() -** **\#include \** **\#include \** **\#include \** **int main() {** **pid\_t pid;** **// Create a new process using fork()** **pid = fork();** **if (pid \< 0) {** **// fork failed** **perror(\"Fork failed\");** **exit(1);** **}** **else if (pid == 0) {** **// This block will be executed by the child process** **printf(\"Child Process: PID = %d, Parent PID = %d\\n\", getpid(), getppid());** **}** **else {** **// This block will be executed by the parent process** **printf(\"Parent Process: PID = %d, Child PID = %d\\n\", getpid(), pid);** **}** **return 0;** **}** - **Implement the parent-child process relationship and demonstrate process. -** **\#include \** **\#include \** **\#include \** **\#include \** **int main() {** **pid\_t pid;** **int status;** **// Create a new process using fork()** **pid = fork();** **if (pid \< 0) {** **// fork failed** **perror(\"Fork failed\");** **exit(1);** **}** **else if (pid == 0) {** **// Child process code** **printf(\"Child Process: PID = %d, Parent PID = %d\\n\", getpid(), getppid());** **// Simulate some work in the child process** **sleep(2); // Child sleeps for 2 seconds before exiting** **printf(\"Child Process: Exiting\...\\n\");** **exit(0); // Child process terminates with exit status 0** **}** **else {** **// Parent process code** **printf(\"Parent Process: PID = %d, Child PID = %d\\n\", getpid(), pid);** **// Wait for the child process to terminate** **wait(&status);** **// Check if the child process terminated normally** **if (WIFEXITED(status)) {** **printf(\"Parent Process: Child exited with status %d\\n\", WEXITSTATUS(status));** **} else if (WIFSIGNALED(status)) {** **printf(\"Parent Process: Child terminated by signal %d\\n\", WTERMSIG(status));** **}** **printf(\"Parent Process: Exiting\...\\n\");** **}** **return 0;** **}** - **Termination-** **\#include \** **\#include \** **\#include \** **\#include \** **int main() {** **pid\_t pid;** **int status;** **// Create a new process using fork()** **pid = fork();** **if (pid \< 0) {** **// fork failed** **perror(\"Fork failed\");** **exit(1);** **}** **else if (pid == 0) {** **// This block will be executed by the child process** **printf(\"Child Process: PID = %d, Parent PID = %d\\n\", getpid(), getppid());** **// Simulate some work in the child process** **sleep(3); // Child sleeps for 3 seconds before exiting** **// Child process terminates with exit status 10** **printf(\"Child Process: Exiting\...\\n\");** **exit(10); // Terminate with status 10** **}** **else {** **// This block will be executed by the parent process** **printf(\"Parent Process: PID = %d, Child PID = %d\\n\", getpid(), pid);** **// Parent process waits for the child to terminate** **wait(&status);** **// Check how the child process terminated** **if (WIFEXITED(status)) {** **// If the child exited normally, get the exit status** **printf(\"Parent Process: Child exited normally with status %d\\n\", WEXITSTATUS(status));** **} else if (WIFSIGNALED(status)) {** **// If the child was terminated by a signal, get the signal number** **printf(\"Parent Process: Child terminated by signal %d\\n\", WTERMSIG(status));** **} else if (WIFSTOPPED(status)) {** **// If the child was stopped by a signal, get the signal number** **printf(\"Parent Process: Child stopped by signal %d\\n\", WSTOPSIG(status));** **}** **// Parent process terminates** **printf(\"Parent Process: Exiting\...\\n\");** **}** **return 0;** **}** - **Use exec() to replace a process image.-** **\#include \** **\#include \** **int main() {** **printf(\"Before exec() call.\\n\");** **// Replacing the current process image with the \"ls\" command** **// execl() accepts a list of arguments to pass to the new program** **execl(\"/bin/ls\", \"ls\", \"-l\", NULL);** **// If exec() is successful, this line will never be reached** **perror(\"exec failed\");** **return 1; // If exec() fails, it returns -1, and we print an error** **}** - **Demonstrate the use of process IDs and status handling.** To demonstrate the use of **process IDs (PIDs)** and **status handling**, we need to create a parent-child relationship where the parent can check the child\'s termination status and interact with the process IDs. The child process will have its own PID, and the parent process will monitor the child's termination using the wait() function and handle the status appropriately. ### **Key Concepts:** 1. **Process ID (PID)**: a. Each process in a Unix-like operating system has a unique **PID**. The parent process can retrieve the PID of its child using fork(), and both the parent and child can use getpid() to get their respective PIDs. 2. **Parent-Child Relationship**: b. The parent creates a child process using fork(). After the child terminates, the parent can retrieve its exit status using wait(). 3. **Status Handling**: c. The wait() function allows the parent to wait for the child process to terminate and retrieve the exit status. d. We can use macros like WIFEXITED(status), WEXITSTATUS(status), and WIFSIGNALED(status) to handle and check the termination status of the child process. ### **C Program: Demonstrating Process IDs and Status Handling** \#include \\ \#include \\ \#include \\ \#include \\ \ int main() {\ pid\_t pid;\ int status;\ \ // Create a new process using fork()\ pid = fork();\ \ if (pid \< 0) {\ // fork failed\ perror(\"Fork failed\");\ exit(1);\ }\ else if (pid == 0) {\ // This block will be executed by the child process\ printf(\"Child Process: PID = %d, Parent PID = %d\\n\", getpid(), getppid());\ \ // Simulate some work in the child process\ sleep(2); // Child sleeps for 2 seconds before exiting\ \ printf(\"Child Process: Exiting\...\\n\");\ exit(42); // Child exits with status 42\ }\ else {\ // This block will be executed by the parent process\ printf(\"Parent Process: PID = %d, Child PID = %d\\n\", getpid(), pid);\ \ // Parent process waits for the child to terminate\ wait(&status);\ \ // Check if the child process exited normally\ if (WIFEXITED(status)) {\ printf(\"Parent Process: Child exited normally with status %d\\n\", WEXITSTATUS(status));\ } else if (WIFSIGNALED(status)) {\ printf(\"Parent Process: Child terminated by signal %d\\n\", WTERMSIG(status));\ } else if (WIFSTOPPED(status)) {\ printf(\"Parent Process: Child stopped by signal %d\\n\", WSTOPSIG(status));\ }\ \ // Parent process terminates\ printf(\"Parent Process: Exiting\...\\n\");\ }\ \ return 0;\ } ### **Explanation:** 1. **fork()**: a. The fork() system call is used to create a new child process. The return value is 0 for the child process and the child\'s PID (positive integer) for the parent process. b. The child process can use getpid() to get its own PID and getppid() to get its parent's PID. 2. **Process ID (PID)**: c. The **child process** prints its PID using getpid() and the parent's PID using getppid(). d. The **parent process** prints its own PID using getpid() and the child's PID (which it received from fork()). 3. **exit()**: e. The **child process** uses exit(42) to terminate itself with an exit status of 42. 4. **wait()**: f. The **parent process** calls wait(&status) to wait for the child to terminate. This ensures the parent knows when the child process has finished. g. The parent can then check the exit status of the child using macros like: i. WIFEXITED(status) --- Returns true if the child terminated normally. ii. WEXITSTATUS(status) --- Retrieves the exit status of the child if it exited normally. iii. WIFSIGNALED(status) --- Returns true if the child was terminated by a signal. iv. WTERMSIG(status) --- Retrieves the signal number that terminated the child. 5. **Child Exit Status**: h. The exit status of the child process is passed back to the parent process. If the child exits normally, the parent can retrieve the exit status using WEXITSTATUS(status). ### **Expected Output:** When you run the program, the output might look like this: Parent Process: PID = 12345, Child PID = 12346\ Child Process: PID = 12346, Parent PID = 12345\ Child Process: Exiting\...\ Parent Process: Child exited normally with status 42\ Parent Process: Exiting\... - The **child process** prints its PID and its parent's PID, sleeps for 2 seconds, then exits with an exit status of 42. - The **parent process** waits for the child to exit, retrieves the exit status, and then prints it. ### **Key Points:** 1. **PID Management**: a. The parent can access the child's PID directly after fork(). b. The child can access the parent's PID using getppid(). 2. **Exit Status Handling**: c. The parent process uses wait(&status) to wait for the child to terminate and retrieves the exit status using WEXITSTATUS(status) if the child exits normally. d. The program also checks whether the child was terminated by a signal (using WIFSIGNALED(status)) or was stopped by a signal (using WIFSTOPPED(status)). 3. **Process IDs**: e. getpid() provides the current process ID of the process calling it. f. getppid() provides the parent process ID of the current process. This program demonstrates **process IDs**, **termination** using exit(), and how the **parent process** handles the child\'s exit status using wait(). The **status handling** mechanism ensures that the parent can make decisions based on how the child terminated. **Ques.2) Objective: Learn and practice basic OS commands.** ** Tasks:** **o File management (e.g., ls, cp, mv, rm, touch).** **o Process management (e.g., ps, kill, top).** **o Directory navigation (e.g., cd, pwd, mkdir).** **o I/O redirection and piping (e.g., \|, >, >>).** **Ans-** To accomplish the **tasks** outlined for learning and practicing basic **OS commands**, I'll give you an overview of common Unix-like system commands related to: 1. **File Management**: ls, cp, mv, rm, touch 2. **Process Management**: ps, kill, top 3. **Directory Navigation**: cd, pwd, mkdir 4. **I/O Redirection and Piping**: \|, \>, \>\> ### **1. File Management Commands:** These commands allow you to manage files and directories in a Unix-like operating system. #### **ls (List files and directories):** - **Basic usage**: ls - Lists files and directories in the current directory. - **Show detailed information**: ls -l - Shows permissions, number of links, owner, group, size, and modification time. - **Show hidden files**: ls -a - Lists all files, including hidden files (those starting with.). #### **cp (Copy files and directories):** - **Basic usage**: cp source.txt destination.txt - Copies a file named source.txt to destination.txt. - **Copy directories**: cp -r source\_directory destination\_directory - Recursively copies a directory and its contents. #### **mv (Move or rename files and directories):** - **Basic usage**: mv old\_name.txt new\_name.txt - Renames a file or moves it to a different location. - **Move files to a directory**: mv file.txt /path/to/destination/ - Moves file.txt to the specified directory. #### **rm (Remove files and directories):** - **Remove a file**: rm file.txt - Deletes the file file.txt. - **Remove a directory**: rm -r directory\_name - Recursively removes a directory and its contents. - **Force removal**: rm -f file.txt - Forcibly deletes the file without asking for confirmation. #### **touch (Create an empty file or update file timestamps):** - **Create a new file**: touch newfile.txt - Creates an empty file named newfile.txt if it doesn't already exist. - **Update timestamp**: touch existingfile.txt - Updates the access and modification times of existingfile.txt. ### **2. Process Management Commands:** These commands allow you to view and manage processes running on your system. #### **ps (Process status):** - **List running processes**: ps - Shows processes running in the current shell session. - **Show all processes**: ps -ef - Shows a list of all processes running on the system. - **Show processes with tree view**: ps aux \--forest - Shows processes in a hierarchical tree structure. #### **kill (Terminate a process):** - **Kill a process by PID**: kill \ - Terminates the process with the given PID (Process ID). - **Kill a process forcefully**: kill -9 \ - Sends a SIGKILL signal to forcefully terminate the process. #### **top (Task manager):** - **Basic usage**: top - Displays a real-time list of processes, sorted by CPU usage, along with memory and other resource usage. - **Filter by process**: While running top, you can type P to sort by CPU or M to sort by memory. ### **3. Directory Navigation Commands:** These commands allow you to navigate and manipulate directories in a Unix-like system. #### **cd (Change directory):** - **Navigate to a directory**: cd /path/to/directory - Changes the current working directory to the specified path. - **Go to home directory**: cd \~ or simply cd - Changes to the user\'s home directory. #### **pwd (Print working directory):** - **Display current directory**: pwd - Prints the absolute path of the current working directory. #### **mkdir (Make directory):** - **Create a directory**: mkdir new\_directory - Creates a new directory named new\_directory. - **Create parent directories if necessary**: mkdir -p /path/to/directory - Creates the full directory path, including any necessary parent directories. ### **4. I/O Redirection and Piping Commands:** These commands allow you to redirect the input and output of commands and combine multiple commands together. #### **\> (Output redirection):** - **Redirect standard output to a file**: echo \"Hello World\" \> output.txt - Writes \"Hello World\" to output.txt, overwriting its contents. - **Redirect output of a command**: ls \> directory\_list.txt - Saves the list of files in the current directory to directory\_list.txt. #### **\>\> (Append output to a file):** - **Append standard output to a file**: echo \"Another line\" \>\> output.txt - Appends \"Another line\" to output.txt without overwriting the existing content. #### **\| (Pipe):** - **Pipe output from one command to another**: ls \| less - The output of ls is piped into the less command, which allows you to view the output page by page. - **Pipe multiple commands together**: ps aux \| grep \'myprocess\' - The output of ps aux is passed to grep, which filters the processes to find myprocess. #### **& (Run command in the background):** - **Run a command in the background**: sleep 10 & - Runs the sleep 10 command in the background, allowing you to continue using the terminal. ### **Example Use Cases:** 1. **List files, copy, and move files**: ls -l\ cp file1.txt backup/\ mv file1.txt newname.txt\ rm oldfile.txt 2. **Process Management**: ps -ef \# List all processes\ kill 12345 \# Kill the process with PID 12345\ top \# View real-time process information 3. **Directory Navigation**: cd /home/user/documents\ mkdir newfolder\ pwd \# Show the current directory 4. **I/O Redirection and Piping**: echo \"Hello, world!\" \> hello.txt\ cat hello.txt\ ls \| grep \".txt\" \# List all.txt files in the current directory\ ps aux \| grep \"apache\" \# Find processes related to apache ### **Summary:** These commands are fundamental to working with Unix-like operating systems. Practicing these commands will help you gain familiarity with file management, process management, directory navigation, and I/O redirection, which are essential skills for system administration and everyday Linux usage. **Ques.3) CPU Scheduling Algorithms** ** Objective: Simulate different CPU scheduling algorithms.** ** Tasks:** **o Write a program to simulate First-Come-First-Served (FCFS) scheduling.** **o Implement Shortest Job First (SJF) scheduling with or without preemption.** **o Simulate Round Robin (RR) scheduling and calculate turnaround and waiting times.** **o Implement Priority Scheduling and test with different sets of priorities.** ### **Ans- CPU Scheduling Algorithms Simulation** The following program simulates various **CPU scheduling algorithms**, including **First-Come-First-Served (FCFS)**, **Shortest Job First (SJF)**, **Round Robin (RR)**, and **Priority Scheduling**. Each algorithm has its own characteristics, and we\'ll implement them in C to calculate important performance metrics like **waiting time** and **turnaround time**. ### **1. First-Come-First-Served (FCFS) Scheduling** In **FCFS**, processes are executed in the order they arrive. #### **C Code for FCFS Scheduling:** \#include \\ \ void findWaitingTime(int n, int bt\[\], int wt\[\]) {\ wt\[0\] = 0; // The first process has no waiting time\ for (int i = 1; i \< n; i++) {\ wt\[i\] = bt\[i - 1\] + wt\[i - 1\];\ }\ }\ \ void findTurnaroundTime(int n, int bt\[\], int wt\[\], int tat\[\]) {\ for (int i = 0; i \< n; i++) {\ tat\[i\] = bt\[i\] + wt\[i\];\ }\ }\ \ void findAverageTime(int n, int bt\[\]) {\ int wt\[n\], tat\[n\];\ findWaitingTime(n, bt, wt);\ findTurnaroundTime(n, bt, wt, tat);\ \ int total\_wt = 0, total\_tat = 0;\ \ for (int i = 0; i \< n; i++) {\ total\_wt += wt\[i\];\ total\_tat += tat\[i\];\ }\ \ printf(\"Average Waiting Time: %.2f\\n\", (float)total\_wt / n);\ printf(\"Average Turnaround Time: %.2f\\n\", (float)total\_tat / n);\ }\ \ int main() {\ int n;\ printf(\"Enter the number of processes: \");\ scanf(\"%d\", &n);\ \ int bt\[n\];\ printf(\"Enter burst times of the processes:\\n\");\ for (int i = 0; i \< n; i++) {\ printf(\"Burst time of P%d: \", i + 1);\ scanf(\"%d\", &bt\[i\]);\ }\ \ findAverageTime(n, bt);\ return 0;\ } ### **2. Shortest Job First (SJF) Scheduling (Non-Preemptive)** In **SJF**, the process with the shortest burst time is executed first. #### **C Code for SJF Scheduling:** \#include \\ \ void sortByBurstTime(int n, int bt\[\], int p\[\]) {\ int temp\_bt, temp\_p;\ for (int i = 0; i \< n - 1; i++) {\ for (int j = i + 1; j \< n; j++) {\ if (bt\[i\] \> bt\[j\]) {\ temp\_bt = bt\[i\];\ bt\[i\] = bt\[j\];\ bt\[j\] = temp\_bt;\ \ temp\_p = p\[i\];\ p\[i\] = p\[j\];\ p\[j\] = temp\_p;\ }\ }\ }\ }\ \ void findWaitingTime(int n, int bt\[\], int wt\[\]) {\ wt\[0\] = 0; // The first process has no waiting time\ for (int i = 1; i \< n; i++) {\ wt\[i\] = bt\[i - 1\] + wt\[i - 1\];\ }\ }\ \ void findTurnaroundTime(int n, int bt\[\], int wt\[\], int tat\[\]) {\ for (int i = 0; i \< n; i++) {\ tat\[i\] = bt\[i\] + wt\[i\];\ }\ }\ \ void findAverageTime(int n, int bt\[\]) {\ int wt\[n\], tat\[n\];\ findWaitingTime(n, bt, wt);\ findTurnaroundTime(n, bt, wt, tat);\ \ int total\_wt = 0, total\_tat = 0;\ \ for (int i = 0; i \< n; i++) {\ total\_wt += wt\[i\];\ total\_tat += tat\[i\];\ }\ \ printf(\"Average Waiting Time: %.2f\\n\", (float)total\_wt / n);\ printf(\"Average Turnaround Time: %.2f\\n\", (float)total\_tat / n);\ }\ \ int main() {\ int n;\ printf(\"Enter the number of processes: \");\ scanf(\"%d\", &n);\ \ int bt\[n\], p\[n\];\ printf(\"Enter burst times of the processes:\\n\");\ for (int i = 0; i \< n; i++) {\ p\[i\] = i + 1; // Process number\ printf(\"Burst time of P%d: \", i + 1);\ scanf(\"%d\", &bt\[i\]);\ }\ \ // Sort by burst time\ sortByBurstTime(n, bt, p);\ \ findAverageTime(n, bt);\ return 0;\ } ### **3. Round Robin (RR) Scheduling** **Round Robin (RR)** is a preemptive scheduling algorithm that gives each process a fixed time slice (quantum). If a process doesn\'t finish within its quantum, it is put back into the ready queue. #### **C Code for Round Robin Scheduling:** \#include \\ \ void findWaitingTime(int n, int bt\[\], int wt\[\], int tq) {\ int rem\_bt\[n\];\ for (int i = 0; i \< n; i++) {\ rem\_bt\[i\] = bt\[i\];\ }\ \ int t = 0; // Current time\ while (1) {\ int done = 1;\ for (int i = 0; i \< n; i++) {\ if (rem\_bt\[i\] \> 0) {\ done = 0;\ if (rem\_bt\[i\] \> tq) {\ t += tq;\ rem\_bt\[i\] -= tq;\ } else {\ t += rem\_bt\[i\];\ wt\[i\] = t - bt\[i\];\ rem\_bt\[i\] = 0;\ }\ }\ }\ if (done == 1) {\ break;\ }\ }\ }\ \ void findTurnaroundTime(int n, int bt\[\], int wt\[\], int tat\[\]) {\ for (int i = 0; i \< n; i++) {\ tat\[i\] = bt\[i\] + wt\[i\];\ }\ }\ \ void findAverageTime(int n, int bt\[\], int tq) {\ int wt\[n\], tat\[n\];\ findWaitingTime(n, bt, wt, tq);\ findTurnaroundTime(n, bt, wt, tat);\ \ int total\_wt = 0, total\_tat = 0;\ for (int i = 0; i \< n; i++) {\ total\_wt += wt\[i\];\ total\_tat += tat\[i\];\ }\ \ printf(\"Average Waiting Time: %.2f\\n\", (float)total\_wt / n);\ printf(\"Average Turnaround Time: %.2f\\n\", (float)total\_tat / n);\ }\ \ int main() {\ int n, tq;\ printf(\"Enter the number of processes: \");\ scanf(\"%d\", &n);\ printf(\"Enter the time quantum: \");\ scanf(\"%d\", &tq);\ \ int bt\[n\];\ printf(\"Enter burst times of the processes:\\n\");\ for (int i = 0; i \< n; i++) {\ printf(\"Burst time of P%d: \", i + 1);\ scanf(\"%d\", &bt\[i\]);\ }\ \ findAverageTime(n, bt, tq);\ return 0;\ } ### **4. Priority Scheduling (Non-Preemptive)** **Priority Scheduling** assigns priorities to processes, and the process with the highest priority (smallest number) is executed first. #### **C Code for Priority Scheduling:** \#include \\ \ void sortByPriority(int n, int bt\[\], int priority\[\], int p\[\]) {\ int temp;\ for (int i = 0; i \< n - 1; i++) {\ for (int j = i + 1; j \< n; j++) {\ if (priority\[i\] \> priority\[j\]) {\ temp = priority\[i\];\ priority\[i\] = priority\[j\];\ priority\[j\] = temp;\ \ temp = bt\[i\];\ bt\[i\] = bt\[j\];\ bt\[j\] = temp;\ }\ }\ }\ }\ \ void findWaitingTime(int n, int bt\[\], int wt\[\]) {\ wt\[0\] = 0;\ for (int i = 1; i \< n; i++) {\ wt\[i\] = bt\[i - 1\] + wt\[i - 1\];\ }\ }\ \ void findTurnaroundTime(int n, int bt\[\], int wt\[\], int tat\[\]) {\ for (int i = 0; i \< n; i++) {\ tat\[i\] = bt\[i\] + wt\[i\];\ }\ }\ \ void findAverageTime(int n, int bt\[\], int priority\[\]) {\ int wt\[n\], tat\[n\];\ findWaitingTime(n, bt, wt);\ findTurnaroundTime(n, bt, wt, tat);\ \ int total\_wt = 0, total\_tat = 0;\ for (int i = 0; i \< n; i++) {\ total\_wt += wt\[i\];\ total\_tat += tat\[i\];\ }\ \ printf(\"Average Waiting Time: %.2f\\n\", (float)total\_wt / n);\ printf(\"Average Turnaround Time: %.2f\\n\", (float)total\_tat / n);\ }\ \ int main() {\ int n;\ printf(\"Enter the number of processes: \");\ scanf(\"%d\", &n);\ \ int bt\[n\], priority\[n\], p\[n\];\ printf(\"Enter burst times and priorities of the processes:\\n\");\ for (int i = 0; i \< n; i++) {\ p\[i\] = i + 1; // Process number\ printf(\"Burst time of P%d: \", i + 1);\ scanf(\"%d\", &bt\[i\]);\ printf(\"Priority of P%d: \", i + 1);\ scanf(\"%d\", &priority\[i\]);\ }\ \ // Sort by priority\ sortByPriority(n, bt, priority, p);\ \ findAverageTime(n, bt, priority);\ return 0;\ } ### **Key Points:** - **FCFS**: Processes are executed in the order they arrive. Simple, but can have poor performance for processes with long burst times. - **SJF (Non-Preemptive)**: Processes with shorter burst times are executed first. Provides better average waiting time but requires knowing burst times in advance. - **Round Robin (RR)**: Fair, but may lead to higher waiting and turnaround times depending on the time quantum. - **Priority Scheduling**: Executes processes based on priority; lower numbers have higher priority. Can lead to starvation if low-priority processes never get executed. ### **Performance Metrics:** - **Waiting Time**: The time a process spends waiting in the ready queue. - **Turnaround Time**: Total time from arrival to completion (includes waiting time). - **Average Waiting Time**: The mean of all processes\' waiting times. - **Average Turnaround Time**: The mean of all processes\' turnaround times. These algorithms can be tested with various process sets and burst times to compare their performance. **Ques.4) Interprocess Communication (IPC)** ** Objective: Implement communication between processes.** ** Tasks:** **o Write a program using pipes for IPC between parent and child processes.** **o Implement shared memory for communication between multiple processes.** **o Use message queues to exchange data between processes.** **o Demonstrate use of semaphores for synchronization.** ### **Ans- Interprocess Communication (IPC) Simulation** Interprocess communication (IPC) allows processes to communicate with each other, either to share data or synchronize their execution. In this task, we\'ll demonstrate different IPC mechanisms in C: 1. **Pipes**: Used for communication between parent and child processes. 2. **Shared Memory**: Allows multiple processes to share a region of memory for communication. 3. **Message Queues**: A message-based IPC mechanism. 4. **Semaphores**: Used to synchronize processes to avoid race conditions. Let\'s look at each of these in more detail. ### **1. Pipes for IPC Between Parent and Child Processes** A **pipe** provides a unidirectional communication channel between processes. Data written by one process is read by the other. Pipes can be used for communication between related processes (parent and child). #### **C Code Using Pipes:** \#include \\ \#include \\ \#include \\ \ int main() {\ int pipefd\[2\];\ pid\_t pid;\ char write\_msg\[\] = \"Hello from Parent!\";\ char read\_msg\[100\];\ \ if (pipe(pipefd) == -1) {\ perror(\"pipe\");\ return 1;\ }\ \ pid = fork();\ if (pid == -1) {\ perror(\"fork\");\ return 1;\ }\ \ if (pid \> 0) { // Parent Process\ close(pipefd\[0\]); // Close unused read end\ write(pipefd\[1\], write\_msg, strlen(write\_msg) + 1); // Write to pipe\ close(pipefd\[1\]); // Close write end\ } else { // Child Process\ close(pipefd\[1\]); // Close unused write end\ read(pipefd\[0\], read\_msg, sizeof(read\_msg)); // Read from pipe\ printf(\"Child received: %s\\n\", read\_msg);\ close(pipefd\[0\]); // Close read end\ }\ \ return 0;\ } ### **Explanation:** - **Parent Process** writes the message \"Hello from Parent!\" to the pipe. - **Child Process** reads from the pipe and prints the received message. ### **2. Shared Memory for Communication Between Multiple Processes** **Shared memory** allows multiple processes to access a common memory area, enabling them to communicate by reading and writing to the shared memory space. #### **C Code Using Shared Memory:** \#include \\ \#include \\ \#include \\ \#include \\ \ \#define SHM\_SIZE 1024\ \ int main() {\ key\_t key = ftok(\"shmfile\", 65);\ int shmid = shmget(key, SHM\_SIZE, 0666\|IPC\_CREAT);\ char \*str = (char\*) shmat(shmid, (void\*)0, 0);\ \ pid\_t pid = fork();\ if (pid == 0) { // Child Process\ printf(\"Child Process: Enter message to share with Parent: \");\ fgets(str, SHM\_SIZE, stdin);\ printf(\"Child Process: Shared message: %s\\n\", str);\ } else { // Parent Process\ wait(NULL); // Wait for child to write the message\ printf(\"Parent Process: Received message from child: %s\\n\", str);\ shmdt(str); // Detach shared memory\ shmctl(shmid, IPC\_RMID, NULL); // Remove shared memory\ }\ \ return 0;\ } ### **Explanation:** - The **parent** creates a shared memory segment. - The **child** writes a message into the shared memory. - The **parent** reads the message from shared memory. ### **3. Message Queues for Exchanging Data Between Processes** A **message queue** is a system-level data structure that allows processes to send and receive messages. This is typically used for inter-process communication where the order of messages is important. #### **C Code Using Message Queues:** \#include \\ \#include \\ \#include \\ \#include \\ \ \#define MSG\_SIZE 100\ \ struct msg\_buffer {\ long msg\_type;\ char msg\_text\[MSG\_SIZE\];\ };\ \ int main() {\ key\_t key = ftok(\"msgqueue\", 65);\ int msgid = msgget(key, 0666 \| IPC\_CREAT);\ \ if (msgid == -1) {\ perror(\"msgget\");\ return 1;\ }\ \ pid\_t pid = fork();\ struct msg\_buffer message;\ \ if (pid == 0) { // Child Process\ message.msg\_type = 1;\ printf(\"Child: Enter message to send: \");\ fgets(message.msg\_text, MSG\_SIZE, stdin);\ message.msg\_text\[strcspn(message.msg\_text, \"\\n\")\] = 0; // Remove newline\ \ if (msgsnd(msgid, &message, sizeof(message), 0) == -1) {\ perror(\"msgsnd\");\ return 1;\ }\ printf(\"Child: Message sent\\n\");\ } else { // Parent Process\ wait(NULL); // Wait for child to send the message\ \ if (msgrcv(msgid, &message, sizeof(message), 1, 0) == -1) {\ perror(\"msgrcv\");\ return 1;\ }\ printf(\"Parent: Received message: %s\\n\", message.msg\_text);\ msgctl(msgid, IPC\_RMID, NULL); // Destroy message queue\ }\ \ return 0;\ } ### **Explanation:** - The **parent** and **child** communicate via a message queue. - The **child** sends a message to the queue, and the **parent** receives it. ### **4. Semaphores for Synchronization** **Semaphores** are used to manage concurrent access to shared resources. They are typically used to avoid race conditions in a multi-process environment. #### **C Code Using Semaphores for Synchronization:** \#include \\ \#include \\ \#include \\ \#include \\ \ sem\_t semaphore;\ \ void\* child\_process(void\* arg) {\ printf(\"Child: Waiting for semaphore\...\\n\");\ sem\_wait(&semaphore); // Wait on semaphore\ printf(\"Child: Critical section reached.\\n\");\ sleep(2); // Simulate some work in the critical section\ printf(\"Child: Leaving critical section.\\n\");\ sem\_post(&semaphore); // Signal semaphore\ return NULL;\ }\ \ int main() {\ pthread\_t child;\ sem\_init(&semaphore, 0, 1); // Initialize semaphore (binary semaphore)\ \ pthread\_create(&child, NULL, child\_process, NULL);\ \ printf(\"Parent: Waiting for semaphore\...\\n\");\ sem\_wait(&semaphore); // Wait on semaphore\ printf(\"Parent: Critical section reached.\\n\");\ sleep(2); // Simulate some work in the critical section\ printf(\"Parent: Leaving critical section.\\n\");\ sem\_post(&semaphore); // Signal semaphore\ \ pthread\_join(child, NULL); // Wait for child to finish\ \ sem\_destroy(&semaphore); // Destroy semaphore\ return 0;\ } ### **Explanation:** - **Semaphore Initialization**: A binary semaphore (sem\_init) is used to control access to a critical section. - **Child Process**: The child waits for the semaphore, enters the critical section, and then signals the semaphore when finished. - **Parent Process**: The parent does the same, ensuring mutual exclusion using the semaphore. ### **Summary of IPC Mechanisms:** - **Pipes**: Useful for simple, one-way communication between parent and child processes. - **Shared Memory**: Allows multiple processes to access a shared memory space, ideal for large data transfer. - **Message Queues**: Useful when multiple processes need to exchange discrete messages. - **Semaphores**: Help synchronize processes to avoid race conditions, ensuring that resources are accessed in a controlled manner. ### **Key Considerations:** - **Pipes** are generally used for communication between related processes (parent-child). - **Shared memory** allows for efficient communication but requires careful synchronization. - **Message queues** are ideal for asynchronous messaging between processes. - **Semaphores** provide synchronization but must be carefully managed to avoid deadlocks. Each IPC mechanism has its advantages and trade-offs depending on the use case, and they can often be combined in a single program to meet complex requirements. **Ques.5) Thread Creation and Synchronization** ** Objective: Work with multithreading in an OS.** ** Tasks:** **o Create multiple threads using POSIX threads (pthreads) in C.** **o Implement thread synchronization using mutexes or semaphores.** **o Write a program to demonstrate race conditions and resolve them using locks.** **o Simulate producer-consumer problem using multithreading.** ### **Ans- Thread Creation and Synchronization in C** Multithreading is a fundamental aspect of modern operating systems, allowing multiple tasks to be executed concurrently. In this task, we will use **POSIX threads** (pthreads) in C to demonstrate different threading concepts such as thread creation, synchronization, race conditions, and the producer-consumer problem. Let\'s go over each task one by one: ### **1. Create Multiple Threads Using POSIX Threads (pthreads)** POSIX threads (pthreads) are a standard set of APIs for creating and managing threads in C. Threads can be created using the pthread\_create function, and we can join them with pthread\_join. #### **C Program to Create Multiple Threads:** \#include \\ \#include \\ \ void\* print\_message(void\* arg) {\ printf(\"Thread ID: %ld\\n\", pthread\_self());\ return NULL;\ }\ \ int main() {\ pthread\_t threads\[3\];\ \ // Create 3 threads\ for (int i = 0; i \< 3; i++) {\ if (pthread\_create(&threads\[i\], NULL, print\_message, NULL) != 0) {\ perror(\"Thread creation failed\");\ }\ }\ \ // Wait for all threads to finish\ for (int i = 0; i \< 3; i++) {\ pthread\_join(threads\[i\], NULL);\ }\ \ printf(\"Main thread finished.\\n\");\ return 0;\ } ### **Explanation:** - **pthread\_create**: Creates a new thread. We pass the function print\_message that each thread will execute. - **pthread\_self**: Retrieves the ID of the current thread. - **pthread\_join**: Ensures the main thread waits for each child thread to finish. ### **2. Implement Thread Synchronization Using Mutexes or Semaphores** Thread synchronization is essential when multiple threads share common resources. We will use **mutexes** to ensure that only one thread can access a shared resource at a time. #### **C Program Using Mutex for Synchronization:** \#include \\ \#include \\ \ pthread\_mutex\_t mutex;\ int shared\_resource = 0;\ \ void\* increment\_resource(void\* arg) {\ pthread\_mutex\_lock(&mutex); // Lock the mutex to access the shared resource\ shared\_resource++;\ printf(\"Thread ID: %ld incremented resource. Shared resource: %d\\n\", pthread\_self(), shared\_resource);\ pthread\_mutex\_unlock(&mutex); // Unlock the mutex after using the shared resource\ return NULL;\ }\ \ int main() {\ pthread\_t threads\[5\];\ \ pthread\_mutex\_init(&mutex, NULL); // Initialize the mutex\ \ // Create 5 threads\ for (int i = 0; i \< 5; i++) {\ if (pthread\_create(&threads\[i\], NULL, increment\_resource, NULL) != 0) {\ perror(\"Thread creation failed\");\ }\ }\ \ // Wait for all threads to finish\ for (int i = 0; i \< 5; i++) {\ pthread\_join(threads\[i\], NULL);\ }\ \ pthread\_mutex\_destroy(&mutex); // Destroy the mutex after use\ \ printf(\"Final value of shared resource: %d\\n\", shared\_resource);\ return 0;\ } ### **Explanation:** - **pthread\_mutex\_t mutex**: Declares a mutex. - **pthread\_mutex\_lock** and **pthread\_mutex\_unlock**: Lock and unlock the mutex to ensure safe access to the shared resource. - **pthread\_mutex\_init** and **pthread\_mutex\_destroy**: Initialize and destroy the mutex, respectively. ### **3. Demonstrate Race Conditions and Resolve Them Using Locks** A **race condition** occurs when two or more threads concurrently access shared data, and the final result depends on the order of execution. We can demonstrate this by allowing threads to increment a shared counter without synchronization and then resolve the issue by adding a mutex. #### **C Program with Race Condition and Mutex to Resolve It:** \#include \\ \#include \\ \ int counter = 0; // Shared resource\ \ void\* increment\_without\_lock(void\* arg) {\ for (int i = 0; i \< 100000; i++) {\ counter++; // Race condition occurs here\ }\ return NULL;\ }\ \ void\* increment\_with\_lock(void\* arg) {\ pthread\_mutex\_t\* mutex = (pthread\_mutex\_t\*) arg;\ for (int i = 0; i \< 100000; i++) {\ pthread\_mutex\_lock(mutex);\ counter++; // Critical section, protected by mutex\ pthread\_mutex\_unlock(mutex);\ }\ return NULL;\ }\ \ int main() {\ pthread\_t threads\[2\];\ pthread\_mutex\_t mutex;\ pthread\_mutex\_init(&mutex, NULL);\ \ // Demonstrating race condition\ for (int i = 0; i \< 2; i++) {\ pthread\_create(&threads\[i\], NULL, increment\_without\_lock, NULL);\ }\ \ for (int i = 0; i \< 2; i++) {\ pthread\_join(threads\[i\], NULL);\ }\ printf(\"Counter value without lock: %d (Expected: 200000)\\n\", counter);\ \ // Resetting counter for demonstration with lock\ counter = 0;\ \ // Resolving race condition with lock\ for (int i = 0; i \< 2; i++) {\ pthread\_create(&threads\[i\], NULL, increment\_with\_lock, &mutex);\ }\ \ for (int i = 0; i \< 2; i++) {\ pthread\_join(threads\[i\], NULL);\ }\ printf(\"Counter value with lock: %d (Expected: 200000)\\n\", counter);\ \ pthread\_mutex\_destroy(&mutex);\ return 0;\ } ### **Explanation:** - **Race Condition**: The program first demonstrates a race condition by allowing two threads to increment the counter without any synchronization. - **Mutex Protection**: The program then resolves the race condition by using a mutex to ensure that only one thread modifies the shared counter at a time. ### **4. Simulate Producer-Consumer Problem Using Multithreading** The **producer-consumer problem** is a classic synchronization problem where one thread (the producer) produces data, and another thread (the consumer) consumes the data. A buffer is used to store the produced data, and synchronization is required to ensure that the producer and consumer do not access the buffer concurrently in an unsafe way. #### **C Program to Simulate Producer-Consumer Problem Using Mutex and Condition Variables:** \#include \\ \#include \\ \#include \\ \ \#define MAX\_ITEMS 5\ int buffer\[MAX\_ITEMS\];\ int count = 0; // Shared resource\ \ pthread\_mutex\_t mutex;\ pthread\_cond\_t cond\_producer, cond\_consumer;\ \ void\* producer(void\* arg) {\ for (int i = 0; i \< 10; i++) {\ pthread\_mutex\_lock(&mutex);\ while (count == MAX\_ITEMS) {\ pthread\_cond\_wait(&cond\_producer, &mutex); // Wait if buffer is full\ }\ buffer\[count\] = i;\ printf(\"Produced item: %d\\n\", i);\ count++;\ pthread\_cond\_signal(&cond\_consumer); // Signal consumer\ pthread\_mutex\_unlock(&mutex);\ sleep(1); // Simulate time taken to produce\ }\ return NULL;\ }\ \ void\* consumer(void\* arg) {\ for (int i = 0; i \< 10; i++) {\ pthread\_mutex\_lock(&mutex);\ while (count == 0) {\ pthread\_cond\_wait(&cond\_consumer, &mutex); // Wait if buffer is empty\ }\ int item = buffer\[count - 1\];\ printf(\"Consumed item: %d\\n\", item);\ count\--;\ pthread\_cond\_signal(&cond\_producer); // Signal producer\ pthread\_mutex\_unlock(&mutex);\ sleep(2); // Simulate time taken to consume\ }\ return NULL;\ }\ \ int main() {\ pthread\_t prod, cons;\ \ pthread\_mutex\_init(&mutex, NULL);\ pthread\_cond\_init(&cond\_producer, NULL);\ pthread\_cond\_init(&cond\_consumer, NULL);\ \ pthread\_create(&prod, NULL, producer, NULL);\ pthread\_create(&cons, NULL, consumer, NULL);\ \ pthread\_join(prod, NULL);\ pthread\_join(cons, NULL);\ \ pthread\_mutex\_destroy(&mutex);\ pthread\_cond\_destroy(&cond\_producer);\ pthread\_cond\_destroy(&cond\_consumer);\ \ return 0;\ } ### **Explanation:** - **Producer**: The producer generates items and places them into the buffer. If the buffer is full, the producer waits. - **Consumer**: The consumer consumes items from the buffer. If the buffer is empty, the consumer waits. - **Mutex**: A mutex ensures mutual exclusion when accessing the shared buffer. - **Condition Variables**: cond\_producer and cond\_consumer synchronize the producer and consumer. ### **Summary:** 1. **Thread Creation**: Use pthread\_create to create threads and pthread\_join to wait for them. 2. **Synchronization with Mutexes**: Use pthread\_mutex\_t to ensure that shared resources are accessed by only one thread at a time. 3. **Race Conditions**: A race condition occurs when multiple threads modify shared data concurrently. We can avoid this by using mutexes. 4. **Producer-Consumer Problem**: Using threads, mutexes, and condition variables, the producer-consumer problem can be simulated to allow safe data exchange between threads. By using these techniques, we can efficiently manage multithreading in an operating system while ensuring synchronization and resolving potential concurrency issues. **Ques.6) Deadlock Detection and Prevention** ** Objective: Implement deadlock avoidance and detection techniques.** ** Tasks:** **o Write a program to simulate a system with multiple resources and processes.** **o Implement Banker's Algorithm for deadlock avoidance.** **o Demonstrate deadlock detection using a resource allocation graph.** **o Analyze a situation where deadlock occurs and suggest ways to resolve it.** ### **Ans- Deadlock Detection and Prevention** Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource held by another process, creating a circular dependency. Deadlock can significantly affect system performance, and preventing or detecting it is crucial for ensuring system stability. We will focus on the following tasks: 1. **Simulating a system with multiple resources and processes**. 2. **Implementing the Banker's Algorithm for deadlock avoidance**. 3. **Demonstrating deadlock detection using a resource allocation graph**. 4. **Analyzing a deadlock situation and suggesting resolution methods**. ### **1. Simulating a System with Multiple Resources and Processes** In this simulation, we have multiple processes and multiple types of resources. We need to keep track of resources allocated to processes, resources requested by processes, and the maximum resources each process may need. #### **C Program: Simulating Multiple Processes and Resources** \#include \\ \ \#define P 5 // Number of processes\ \#define R 3 // Number of resource types\ \ int available\[\] = {3, 3, 2}; // Available instances of resources\ int maximum\[P\]\[R\] = {\ {7, 5, 3},\ {3, 2, 2},\ {9, 0, 2},\ {2, 2, 2},\ {4, 3, 3}\ }; // Maximum resources needed by each process\ int allocation\[P\]\[R\] = {\ {0, 1, 0},\ {2, 0, 0},\ {3, 0, 2},\ {2, 1, 1},\ {0, 0, 2}\ }; // Currently allocated resources to each process\ int need\[P\]\[R\]; // Remaining resources needed by each process\ \ // Function to calculate the need matrix\ void calculateNeed() {\ for (int i = 0; i \< P; i++) {\ for (int j = 0; j \< R; j++) {\ need\[i\]\[j\] = maximum\[i\]\[j\] - allocation\[i\]\[j\];\ }\ }\ }\ \ void printMatrices() {\ printf(\"Maximum Resources:\\n\");\ for (int i = 0; i \< P; i++) {\ for (int j = 0; j \< R; j++) {\ printf(\"%d \", maximum\[i\]\[j\]);\ }\ printf(\"\\n\");\ }\ \ printf(\"\\nAllocated Resources:\\n\");\ for (int i = 0; i \< P; i++) {\ for (int j = 0; j \< R; j++) {\ printf(\"%d \", allocation\[i\]\[j\]);\ }\ printf(\"\\n\");\ }\ \ printf(\"\\nNeed Resources:\\n\");\ for (int i = 0; i \< P; i++) {\ for (int j = 0; j \< R; j++) {\ printf(\"%d \", need\[i\]\[j\]);\ }\ printf(\"\\n\");\ }\ \ printf(\"\\nAvailable Resources: \");\ for (int i = 0; i \< R; i++) {\ printf(\"%d \", available\[i\]);\ }\ printf(\"\\n\");\ }\ \ int main() {\ calculateNeed();\ printMatrices();\ return 0;\ } ### **Explanation:** - **maximum\[\]\[\]**: Maximum resources each process may need. - **allocation\[\]\[\]**: Resources currently allocated to each process. - **need\[\]\[\]**: Remaining resources needed by each process (calculated as maximum - allocation). - **available\[\]**: Available instances of resources in the system. This program sets up the system for subsequent deadlock detection and avoidance techniques. ### **2. Implementing Banker's Algorithm for Deadlock Avoidance** The **Banker's Algorithm** is used to avoid deadlock by simulating resource allocation and checking if the system can enter a safe state after each allocation. The system is in a safe state if there exists a sequence of processes such that each process can finish executing, even if it requests resources. #### **C Program: Banker's Algorithm for Deadlock Avoidance** \#include \\ \#include \\ \ \#define P 5 // Number of processes\ \#define R 3 // Number of resource types\ \ int available\[\] = {3, 3, 2}; // Available instances of resources\ int maximum\[P\]\[R\] = {\ {7, 5, 3},\ {3, 2, 2},\ {9, 0, 2},\ {2, 2, 2},\ {4, 3, 3}\ }; // Maximum resources needed by each process\ int allocation\[P\]\[R\] = {\ {0, 1, 0},\ {2, 0, 0},\ {3, 0, 2},\ {2, 1, 1},\ {0, 0, 2}\ }; // Currently allocated resources to each process\ int need\[P\]\[R\]; // Remaining resources needed by each process\ \ void calculateNeed() {\ for (int i = 0; i \< P; i++) {\ for (int j = 0; j \< R; j++) {\ need\[i\]\[j\] = maximum\[i\]\[j\] - allocation\[i\]\[j\];\ }\ }\ }\ \ bool isSafe() {\ int work\[R\];\ bool finish\[P\] = {false}; // Finish array, false means the process is not finished\ \ // Initialize work with available resources\ for (int i = 0; i \< R; i++) {\ work\[i\] = available\[i\];\ }\ \ // Try to find a safe sequence\ int count = 0;\ while (count \< P) {\ bool found = false;\ for (int i = 0; i \< P; i++) {\ if (!finish\[i\]) {\ bool canAllocate = true;\ for (int j = 0; j \< R; j++) {\ if (need\[i\]\[j\] \> work\[j\]) {\ canAllocate = false;\ break;\ }\ }\ if (canAllocate) {\ // Simulate allocating resources\ for (int j = 0; j \< R; j++) {\ work\[j\] += allocation\[i\]\[j\];\ }\ finish\[i\] = true;\ found = true;\ count++;\ break;\ }\ }\ }\ if (!found) {\ return false; // If no process can proceed, the system is in an unsafe state\ }\ }\ return true; // If all processes can finish, the system is in a safe state\ }\ \ int main() {\ calculateNeed();\ \ if (isSafe()) {\ printf(\"System is in a safe state.\\n\");\ } else {\ printf(\"System is in an unsafe state.\\n\");\ }\ \ return 0;\ } ### **Explanation:** - **isSafe()**: Implements the Banker\'s algorithm to check if the system is in a safe state. It tries to find a process that can finish given the available resources and updates the work vector. If all processes can finish, the system is safe. - **need\[\]\[\]**: Remaining resources needed by each process. - **work\[\]**: The available resources that are updated as processes finish. - **finish\[\]**: Keeps track of whether a process can finish or not. ### **3. Deadlock Detection Using Resource Allocation Graph** A **Resource Allocation Graph (RAG)** is a directed graph where: - Processes are represented by nodes. - Resources are represented by nodes. - An edge from a process to a resource represents a request by the process. - An edge from a resource to a process represents an allocation of the resource to the process. To detect deadlock, we can look for cycles in the graph. #### **C Program: Resource Allocation Graph for Deadlock Detection** \#include \\ \#include \\ \ \#define P 5 // Number of processes\ \#define R 3 // Number of resource types\ \ int allocation\[P\]\[R\] = {\ {0, 1, 0},\ {2, 0, 0},\ {3, 0, 2},\ {2, 1, 1},\ {0, 0, 2}\ };\ \ int request\[P\]\[R\] = {\ {0, 0, 2},\ {1, 0, 2},\ {2, 1, 0},\ {1, 2, 1},\ {1, 0, 0}\ };\ \ bool isDeadlocked() {\ // Check for cycles in the resource allocation graph\ // This requires a more complex algorithm involving DFS or matrix operations,\ // which are typically handled by specialized libraries or algorithms.\ return true; // This is a simplified demonstration\ }\ \ int main() {\ if (isDeadlocked()) {\ printf(\"Deadlock detected in the system.\\n\");\ } else {\ printf(\"No deadlock detected.\\n\");\ }\ return 0;\ } ### **Explanation:** - **allocation\[\]\[\]**: Allocated resources to processes. - **request\[\]\[\]**: Resources requested by processes. - **isDeadlocked()**: Placeholder function for detecting cycles in the resource allocation graph, which would indicate a deadlock. ### **4. Analyzing Deadlock and Resolution** A deadlock can occur in a system when the following conditions are met: 1. **Mutual Exclusion**: At least one resource is held in a non-shareable mode. 2. **Hold and Wait**: A process holding one resource is waiting for additional resources. 3. **No Preemption**: Resources cannot be forcibly taken from processes holding them. 4. **Circular Wait**: A circular chain of processes exists where each process holds at least one resource that the next process in the chain is waiting for. #### **Ways to Resolve Deadlock:** 1. **Resource Preemption**: Forcefully take resources from one process and allocate them to another. 2. **Terminate Processes**: Terminate one or more processes involved in the deadlock. 3. **Avoid Circular Wait**: Ensure that a circular wait condition cannot arise by requiring processes to request all resources at once. ### **Summary:** - **Banker's Algorithm**: Prevents deadlock by ensuring that resource allocation keeps the system in a safe state. - **Deadlock Detection**: We can detect deadlock using a Resource Allocation Graph (RAG) and cycle detection techniques. - **Deadlock Resolution**: Deadlock can be resolved by preempting resources, terminating processes, or avoiding circular waits. **Ques.7) Memory Management Techniques** ** Objective: Implement and simulate different memory management techniques.** ** Tasks:** **o Simulate paging and segmentation using C or Java.** **o Implement page replacement algorithms (FIFO, LRU, Optimal).** **o Write a program to simulate allocation and deallocation of memory blocks using** **First Fit, Best Fit, and Worst Fit algorithms.** ### **Ans- Memory Management Techniques** Memory management is crucial in an operating system as it controls and coordinates the computer\'s memory, allocating blocks of memory to processes and ensuring efficient use of the system\'s resources. In this task, we will implement different memory management techniques, including **paging**, **segmentation**, and **page replacement algorithms** (FIFO, LRU, and Optimal). Additionally, we\'ll implement **First Fit**, **Best Fit**, and **Worst Fit** algorithms for memory allocation and deallocation. ### **1. Simulating Paging and Segmentation** #### **Paging:** In paging, memory is divided into fixed-size blocks called **pages**, and the physical memory is divided into blocks of the same size called **frames**. When a process is executed, its pages are mapped to available frames in the physical memory. #### **Segmentation:** In segmentation, memory is divided into variable-sized segments based on logical divisions such as functions, data, etc. Each segment can grow or shrink in size. We will implement both paging and segmentation in C. #### **C Program: Simulating Paging** \#include \\ \#include \\ \ \#define MEMORY\_SIZE 32 // Total size of memory\ \#define PAGE\_SIZE 4 // Size of each page\ \ int memory\[MEMORY\_SIZE\]; // Physical memory (frames)\ int pages\[MEMORY\_SIZE / PAGE\_SIZE\]; // Simulating a process with pages\ \ // Function to simulate paging (allocate pages to frames)\ void allocatePages() {\ int page\_number, frame\_number;\ for (page\_number = 0; page\_number \< MEMORY\_SIZE / PAGE\_SIZE; page\_number++) {\ frame\_number = page\_number \* PAGE\_SIZE;\ for (int i = 0; i \< PAGE\_SIZE; i++) {\ memory\[frame\_number + i\] = page\_number + 1; // Assigning page to frames\ }\ }\ }\ \ // Function to simulate accessing a page\ void accessPage(int page\_num) {\ int frame\_number = page\_num \* PAGE\_SIZE;\ printf(\"Accessing Page %d: Memory Content: \", page\_num);\ for (int i = 0; i \< PAGE\_SIZE; i++) {\ printf(\"%d \", memory\[frame\_number + i\]);\ }\ printf(\"\\n\");\ }\ \ int main() {\ allocatePages();\ accessPage(0); // Access first page\ accessPage(2); // Access third page\ return 0;\ } ### **Explanation:** - **Paging simulation**: We divide memory into frames and allocate them to pages. Each process will get a set of frames that correspond to its pages. - **accessPage()**: This function simulates accessing a specific page from memory. #### **C Program: Simulating Segmentation** \#include \\ \#include \\ \ \#define NUM\_SEGMENTS 3\ \#define MAX\_SEGMENT\_SIZE 10\ \ int segments\[NUM\_SEGMENTS\]\[MAX\_SEGMENT\_SIZE\]; // Each segment can have multiple memory units\ \ // Function to simulate segmentation (allocate segments)\ void allocateSegments() {\ for (int i = 0; i \< NUM\_SEGMENTS; i++) {\ for (int j = 0; j \< MAX\_SEGMENT\_SIZE; j++) {\ segments\[i\]\[j\] = i + 1; // Assigning segment ID to each memory unit\ }\ }\ }\ \ // Function to simulate accessing a segment\ void accessSegment(int segment\_num) {\ printf(\"Accessing Segment %d: \", segment\_num);\ for (int i = 0; i \< MAX\_SEGMENT\_SIZE; i++) {\ printf(\"%d \", segments\[segment\_num\]\[i\]);\ }\ printf(\"\\n\");\ }\ \ int main() {\ allocateSegments();\ accessSegment(1); // Accessing second segment\ accessSegment(2); // Accessing third segment\ return 0;\ } ### **Explanation:** - **Segmentation simulation**: Memory is divided into multiple segments, and each segment can have multiple memory units. - **accessSegment()**: This function simulates accessing a specific segment. ### **2. Implementing Page Replacement Algorithms** Page replacement algorithms are used when a process requests a page that is not currently in memory. The operating system needs to decide which page to swap out to make space for the new page. We will implement the following page replacement algorithms: #### **2.1 FIFO (First-In-First-Out) Algorithm** The FIFO algorithm replaces the oldest page in memory when a new page needs to be loaded. \#include \\ \ \#define NUM\_PAGES 4 // Number of page frames\ \#define NUM\_PROCESSES 10\ \ int memory\[NUM\_PAGES\]; // Physical memory (pages)\ \ void fifo(int processes\[\], int num\_processes) {\ int page\_faults = 0;\ int page\_pointer = 0;\ for (int i = 0; i \< num\_processes; i++) {\ int page = processes\[i\];\ int found = 0;\ \ // Check if the page is already in memory\ for (int j = 0; j \< NUM\_PAGES; j++) {\ if (memory\[j\] == page) {\ found = 1;\ break;\ }\ }\ \ // If page is not found in memory, replace the oldest page\ if (!found) {\ memory\[page\_pointer\] = page;\ page\_pointer = (page\_pointer + 1) % NUM\_PAGES;\ page\_faults++;\ }\ \ // Print memory after each page request\ printf(\"Accessing Page %d: Memory: \", page);\ for (int j = 0; j \< NUM\_PAGES; j++) {\ printf(\"%d \", memory\[j\]);\ }\ printf(\"\\n\");\ }\ printf(\"Total page faults: %d\\n\", page\_faults);\ }\ \ int main() {\ int processes\[NUM\_PROCESSES\] = {0, 1, 2, 3, 0, 4, 1, 2, 3, 0};\ fifo(processes, NUM\_PROCESSES);\ return 0;\ } ### **Explanation:** - **FIFO Algorithm**: We keep track of the pages currently in memory. When a page fault occurs, the oldest page is replaced. #### **2.2 LRU (Least Recently Used) Algorithm** The LRU algorithm replaces the page that has not been used for the longest period of time. \#include \\ \ \#define NUM\_PAGES 4\ \#define NUM\_PROCESSES 10\ \ int memory\[NUM\_PAGES\]; // Physical memory (pages)\ \ void lru(int processes\[\], int num\_processes) {\ int page\_faults = 0;\ int last\_used\[NUM\_PAGES\] = {0};\ \ for (int i = 0; i \< num\_processes; i++) {\ int page = processes\[i\];\ int found = 0;\ int oldest = 0;\ \ // Check if the page is already in memory\ for (int j = 0; j \< NUM\_PAGES; j++) {\ if (memory\[j\] == page) {\ found = 1;\ last\_used\[j\] = i; // Update last used time\ break;\ }\ // Find the least recently used page\ if (last\_used\[j\] \< last\_used\[oldest\]) {\ oldest = j;\ }\ }\ \ // If page is not found in memory, replace the least recently used page\ if (!found) {\ memory\[oldest\] = page;\ last\_used\[oldest\] = i;\ page\_faults++;\ }\ \ // Print memory after each page request\ printf(\"Accessing Page %d: Memory: \", page);\ for (int j = 0; j \< NUM\_PAGES; j++) {\ printf(\"%d \", memory\[j\]);\ }\ printf(\"\\n\");\ }\ printf(\"Total page faults: %d\\n\", page\_faults);\ }\ \ int main() {\ int processes\[NUM\_PROCESSES\] = {0, 1, 2, 3, 0, 4, 1, 2, 3, 0};\ lru(processes, NUM\_PROCESSES);\ return 0;\ } ### **Explanation:** - **LRU Algorithm**: The page that has not been used for the longest time is replaced when a page fault occurs. #### **2.3 Optimal Page Replacement Algorithm** The Optimal algorithm replaces the page that will not be used for the longest period in the future. \#include \\ \ \#define NUM\_PAGES 4\ \#define NUM\_PROCESSES 10\ \ int memory\[NUM\_PAGES\]; // Physical memory (pages)\ \ void optimal(int processes\[\], int num\_processes) {\ int page\_faults = 0;\ \ for (int i = 0; i \< num\_processes; i++) {\ int page = processes\[i\];\ int found = 0;\ \ // Check if the page is already in memory\ for (int j = 0; j \< NUM\_PAGES; j++) {\ if (memory\[j\] == page) {\ found = 1;\ break;\ }\ }\ \ // If page is not found in memory, replace the optimal page\ if (!found) {\ int furthest = -1;\ int replace\_page = 0;\ \ for (int j = 0; j \< NUM\_PAGES; j++) {\ int future\_use = -1;\ for (int k = i + 1; k \< num\_processes; k++) {\ if (processes\[k\] == memory\[j\]) {\ future\_use = k;\ break;\ }\ }\ if (future\_use == -1) {\ replace\_page = j;\ break;\ }\ if (future\_use \> furthest) {\ furthest = future\_use;\ replace\_page = j;\ }\ }\ memory\[replace\_page\] = page;\ page\_faults++;\ }\ \ // Print memory after each page request\ printf(\"Accessing Page %d: Memory: \", page);\ for (int j = 0; j \< NUM\_PAGES; j++) {\ printf(\"%d \", memory\[j\]);\ }\ printf(\"\\n\");\ }\ printf(\"Total page faults: %d\\n\", page\_faults);\ }\ \ int main() {\ int processes\[NUM\_PROCESSES\] = {0, 1, 2, 3, 0, 4, 1, 2, 3, 0};\ optimal(processes, NUM\_PROCESSES);\ return 0;\ } ### **Explanation:** - **Optimal Algorithm**: The page that will not be used for the longest period is replaced when a page fault occurs. ### **3. Memory Allocation Algorithms** #### **3.1 First Fit Algorithm** In the **First Fit** algorithm, memory is allocated to the first available block that is large enough to satisfy the process\'s request. \#include \\ \ \#define NUM\_BLOCKS 5\ \#define NUM\_PROCESSES 3\ \ int blocks\[NUM\_BLOCKS\] = {100, 500, 200, 300, 600}; // Memory blocks\ int processes\[NUM\_PROCESSES\] = {212, 417, 112}; // Process sizes\ \ void firstFit() {\ for (int i = 0; i \< NUM\_PROCESSES; i++) {\ int allocated = 0;\ for (int j = 0; j \< NUM\_BLOCKS; j++) {\ if (blocks\[j\] \>= processes\[i\]) {\ printf(\"Process %d allocated to Block %d\\n\", i + 1, j + 1);\ blocks\[j\] -= processes\[i\];\ allocated = 1;\ break;\ }\ }\ if (!allocated) {\ printf(\"Process %d cannot be allocated memory.\\n\", i + 1);\ }\ }\ }\ \ int main() {\ firstFit();\ return 0;\ } ### **Explanation:** - **First Fit Algorithm**: We go through the list of memory blocks and allocate the first block that fits the process. #### **3.2 Best Fit Algorithm** In the **Best Fit** algorithm, memory is allocated to the smallest block that is large enough to satisfy the process's request, minimizing wasted memory. \#include \\ \ \#define NUM\_BLOCKS 5\ \#define NUM\_PROCESSES 3\ \ int blocks\[NUM\_BLOCKS\] = {100, 500, 200, 300, 600}; // Memory blocks\ int processes\[NUM\_PROCESSES\] = {212, 417, 112}; // Process sizes\ \ void bestFit() {\ for (int i = 0; i \< NUM\_PROCESSES; i++) {\ int min\_diff = 99999;\ int block\_index = -1;\ \ for (int j = 0; j \< NUM\_BLOCKS; j++) {\ if (blocks\[j\] \>= processes\[i\]) {\ int diff = blocks\[j\] - processes\[i\];\ if (diff \< min\_diff) {\ min\_diff = diff;\ block\_index = j;\ }\ }\ }\ \ if (block\_index != -1) {\ printf(\"Process %d allocated to Block %d\\n\", i + 1, block\_index + 1);\ blocks\[block\_index\] -= processes\[i\];\ } else {\ printf(\"Process %d cannot be allocated memory.\\n\", i + 1);\ }\ }\ }\ \ int main() {\ bestFit();\ return 0;\ } ### **Explanation:** - **Best Fit Algorithm**: This algorithm finds the block that leaves the least amount of free space after allocating the process\'s memory. #### **3.3 Worst Fit Algorithm** In the **Worst Fit** algorithm, memory is allocated to the largest block that is large enough to satisfy the process's request. \#include \\ \ \#define NUM\_BLOCKS 5\ \#define NUM\_PROCESSES 3\ \ int blocks\[NUM\_BLOCKS\] = {100, 500, 200, 300, 600}; // Memory blocks\ int processes\[NUM\_PROCESSES\] = {212, 417, 112}; // Process sizes\ \ void worstFit() {\ for (int i = 0; i \< NUM\_PROCESSES; i++) {\ int max\_diff = -1;\ int block\_index = -1;\ \ for (int j = 0; j \< NUM\_BLOCKS; j++) {\ if (blocks\[j\] \>= processes\[i\]) {\ int diff = blocks\[j\] - processes\[i\];\ if (diff \> max\_diff) {\ max\_diff = diff;\ block\_index = j;\ }\ }\ }\ \ if (block\_index != -1) {\ printf(\"Process %d allocated to Block %d\\n\", i + 1, block\_index + 1);\ blocks\[block\_index\] -= processes\[i\];\ } else {\ printf(\"Process %d cannot be allocated memory.\\n\", i + 1);\ }\ }\ }\ \ int main() {\ worstFit();\ return 0;\ } ### **Explanation:** - **Worst Fit Algorithm**: This algorithm allocates memory from the largest available block, minimizing fragmentation by leaving the largest free space. ### **Summary:** - **Paging** divides memory into fixed-sized pages and maps them to available frames. - **Segmentation** divides memory into variable-sized segments based on logical divisions. - **Page replacement algorithms** (FIFO, LRU, Optimal) handle the replacement of pages in memory when a page fault occurs. - **Memory allocation algorithms** (First Fit, Best Fit, Worst Fit) allocate memory blocks to processes based on different strategies. **Ques.8) File System Implementation** ** Objective: Understand file system operations and implement basic file management.** ** Tasks:** **o Write a program to simulate the creation, deletion, and manipulation of files in a** **directory.** **o Implement file allocation methods (Contiguous, Linked, Indexed).** **o Simulate disk scheduling algorithms (FCFS, SSTF, SCAN, C-SCAN).** ### **Ans- File System Implementation** File systems manage how data is stored and retrieved on disk drives. The task here is to simulate various file system operations, including the creation, deletion, and manipulation of files in a directory, as well as implementing file allocation methods (Contiguous, Linked, Indexed), and simulating disk scheduling algorithms (FCFS, SSTF, SCAN, C-SCAN). ### **1. Simulating File Operations (Creation, Deletion, Manipulation)** We can simulate a basic directory structure where we can create, delete, and manipulate files (add or read file contents). #### **C Program: Simulating File Creation, Deletion, and Manipulation** \#include \\ \#include \\ \#include \\ \ \#define MAX\_FILES 10\ \#define FILENAME\_LENGTH 50\ \#define FILE\_CONTENT\_LENGTH 200\ \ typedef struct {\ char filename\[FILENAME\_LENGTH\];\ char content\[FILE\_CONTENT\_LENGTH\];\ int is\_deleted; // Flag to mark deleted files\ } File;\ \ typedef struct {\ File files\[MAX\_FILES\];\ int file\_count;\ } Directory;\ \ // Function to create a file\ void createFile(Directory \*dir, const char \*filename, const char \*content) {\ if (dir-\>file\_count \< MAX\_FILES) {\ File \*file = &dir-\>files\[dir-\>file\_count++\];\ strcpy(file-\>filename, filename);\ strcpy(file-\>content, content);\ file-\>is\_deleted = 0;\ printf(\"File \'%s\' created successfully.\\n\", filename);\ } else {\ printf(\"Directory is full, cannot create more files.\\n\");\ }\ }\ \ // Function to delete a file\ void deleteFile(Directory \*dir, const char \*filename) {\ for (int i = 0; i \< dir-\>file\_count; i++) {\ if (strcmp(dir-\>files\[i\].filename, filename) == 0 && !dir-\>files\[i\].is\_deleted) {\ dir-\>files\[i\].is\_deleted = 1;\ printf(\"File \'%s\' deleted successfully.\\n\", filename);\ return;\ }\ }\ printf(\"File \'%s\' not found or already deleted.\\n\", filename);\ }\ \ // Function to display file contents\ void displayFile(Directory \*dir, const char \*filename) {\ for (int i = 0; i \< dir-\>file\_count; i++) {\ if (strcmp(dir-\>files\[i\].filename, filename) == 0 && !dir-\>files\[i\].is\_deleted) {\ printf(\"File \'%s\' contents: %s\\n\", filename, dir-\>files\[i\].content);\ return;\ }\ }\ printf(\"File \'%s\' not found or deleted.\\n\", filename);\ }\ \ int main() {\ Directory dir = {0}; // Initialize directory with no files\ \ // Simulate file operations\ createFile(&dir, \"file1.txt\", \"This is the content of file 1.\");\ createFile(&dir, \"file2.txt\", \"This is the content of file 2.\");\ displayFile(&dir, \"file1.txt\");\ deleteFile(&dir, \"file1.txt\");\ displayFile(&dir, \"file1.txt\");\ \ return 0;\ } ### **Explanation:** - **Directory Structure**: We use a Directory struct to hold an array of files. Each file has a name, content, and a deletion flag (is\_deleted). - **Create File**: Adds a new file to the directory. - **Delete File**: Marks a file as deleted (using a flag, not actually removing it from the array). - **Display File**: Displays the content of a file if it exists and is not deleted. ### **2. File Allocation Methods** There are several methods for allocating files to disk blocks: **Contiguous Allocation**, **Linked Allocation**, and **Indexed Allocation**. #### **2.1 Contiguous Allocation** In Contiguous Allocation, each file occupies a set of contiguous blocks in memory. \#include \\ \#include \\ \ \#define MAX\_BLOCKS 5\ \#define MAX\_FILES 3\ \ typedef struct {\ char filename\[50\];\ int start\_block; // Starting block of the file\ int length; // Number of contiguous blocks allocated to the file\ } ContiguousFile;\ \ ContiguousFile files\[MAX\_FILES\];\ int blocks\[MAX\_BLOCKS\] = {0}; // 0 means free, 1 means occupied\ \ // Function to allocate contiguous blocks to a file\ int allocateContiguous(char \*filename, int length) {\ for (int i = 0; i \< MAX\_BLOCKS - length + 1; i++) {\ int available = 1;\ for (int j = i; j \< i + length; j++) {\ if (blocks\[j\] == 1) {\ available = 0;\ break;\ }\ }\ \ if (available) {\ for (int j = i; j \< i + length; j++) {\ blocks\[j\] = 1;\ }\ \ // Record file allocation\ ContiguousFile newFile;\ strcpy(newFile.filename, filename);\ newFile.start\_block = i;\ newFile.length = length;\ files\[0\] = newFile; // Only one file for simplicity\ \ printf(\"File \'%s\' allocated to blocks %d to %d.\\n\", filename, i, i + length - 1);\ return 1; // Success\ }\ }\ printf(\"Insufficient contiguous blocks available for file \'%s\'.\\n\", filename);\ return 0; // Failure\ }\ \ int main() {\ // Simulate file allocation\ allocateContiguous(\"file1.txt\", 3); // Allocating 3 contiguous blocks\ allocateContiguous(\"file2.txt\", 2); // Allocating 2 contiguous blocks\ \ return 0;\ } ### **Explanation:** - **Contiguous Allocation**: The function allocateContiguous checks for a sequence of free blocks of the required length and allocates them to the file. The blocks array keeps track of which blocks are free or occupied. #### **2.2 Linked Allocation** In Linked Allocation, each file is stored in non-contiguous blocks, with each block containing a pointer to the next block. \#include \\ \#include \\ \ \#define MAX\_BLOCKS 10\ \ typedef struct Block {\ int block\_num;\ struct Block \*next;\ } Block;\ \ typedef struct {\ char filename\[50\];\ Block \*head;\ } LinkedFile;\ \ LinkedFile files\[MAX\_BLOCKS\];\ int blocks\[MAX\_BLOCKS\] = {0}; // 0 means free, 1 means occupied\ \ // Function to allocate blocks using linked allocation\ int allocateLinked(char \*filename, int length) {\ Block \*head = NULL;\ Block \*tail = NULL;\ \ for (int i = 0; i \< MAX\_BLOCKS && length \> 0; i++) {\ if (blocks\[i\] == 0) {\ blocks\[i\] = 1;\ Block \*newBlock = (Block \*)malloc(sizeof(Block));\ newBlock-\>block\_num = i;\ newBlock-\>next = NULL;\ \ if (head == NULL) {\ head = newBlock;\ tail = newBlock;\ } else {\ tail-\>next = newBlock;\ tail = newBlock;\ }\ \ length\--;\ }\ }\ \ if (length == 0) {\ LinkedFile newFile;\ strcpy(newFile.filename, filename);\ newFile.head = head;\ files\[0\] = newFile; // Only one file for simplicity\ printf(\"File \'%s\' allocated with blocks linked.\\n\", filename);\ return 1;\ } else {\ printf(\"Not enough free blocks for file \'%s\'.\\n\", filename);\ return 0;\ }\ }\ \ int main() {\ // Simulate file allocation using linked allocation\ allocateLinked(\"file1.txt\", 3);\ allocateLinked(\"file2.txt\", 2);\ \ return 0;\ } ### **Explanation:** - **Linked Allocation**: The function allocateLinked allocates non-contiguous blocks to a file. Each block contains a pointer to the next block in the chain. #### **2.3 Indexed Allocation** In Indexed Allocation, each file has an index block, which contains pointers to all the blocks allocated to the file. \#include \\ \#include \\ \ \#define MAX\_BLOCKS 10\ \ typedef struct {\ char filename\[50\];\ int index\_block\[MAX\_BLOCKS\];\ int num\_blocks;\ } IndexedFile;\ \ IndexedFile files\[MAX\_BLOCKS\];\ int blocks\[MAX\_BLOCKS\] = {0}; // 0 means free, 1 means occupied\ \ // Function to allocate blocks using indexed allocation\ int allocateIndexed(char \*filename, int length) {\ int index\[MAX\_BLOCKS\];\ int num\_blocks = 0;\ \ for (int i = 0; i \< MAX\_BLOCKS && length \> 0; i++) {\ if (blocks\[i\] == 0) {\ blocks\[i\] = 1;\ index\[num\_blocks++\] = i;\ length\--;\ }\ }\ \ if (length == 0) {\ IndexedFile newFile;\ strcpy(newFile.filename, filename);\ for (int i = 0; i \< num\_blocks; i++) {\ newFile.index\_block\[i\] = index\[i\];\ }\ newFile.num\_blocks = num\_blocks;\ files\[0\] = newFile; // Only one file for simplicity\ printf(\"File \'%s\' allocated using indexed allocation.\\n\", filename);\ return 1;\ } else {\ printf(\"Not enough free blocks for file \'%s\'.\\n\", filename);\ return 0;\ }\ }\ \ int main() {\ // Simulate file allocation using indexed allocation\ allocateIndexed(\"file1.txt\", 3);\ allocateIndexed(\"file2.txt\", 2);\ \ return 0;\ } ### **Explanation:** - **Indexed Allocation**: The function allocateIndexed allocates blocks to a file and stores the block numbers in an index array. The file structure keeps track of these blocks. ### **3. Simulating Disk Scheduling Algorithms** #### **3.1 FCFS (First-Come, First-Served)** In FCFS, the disk services requests in the order they are received. \#include \\ \#include \\ \ void fcfs(int requests\[\], int size) {\ int total\_seek = 0;\ int head = 0; // Assume the initial head position is at 0\ \ printf(\"FCFS Disk Scheduling:\\n\");\ for (int i = 0; i \< size; i++) {\ total\_seek += abs(requests\[i\] - head);\ printf(\"Seek from %d to %d (Distance: %d)\\n\", head, requests\[i\], abs(requests\[i\] - head));\ head = requests\[i\];\ }\ printf(\"Total Seek Distance: %d\\n\", total\_seek);\ }\ \ int main() {\ int requests\[\] = {98, 183, 37, 122, 14, 124, 65, 67};\ int size = sizeof(requests) / sizeof(requests\[0\]);\ \ fcfs(requests, size);\ \ return 0;\ } ### **Explanation:** - **FCFS**: The requests are serviced in the order they are received, and the total seek distance is calculated. #### **3.2 SSTF (Shortest Seek Time First)** In SSTF, the disk selects the request closest to the current head position. \#include \\ \#include \\ \ void sstf(int requests\[\], int size) {\ int total\_seek = 0;\ int head = 0; // Assume the initial head position is at 0\ int visited\[size\];\ \ for (int i = 0; i \< size; i++) visited\[i\] = 0;\ \ printf(\"SSTF Disk Scheduling:\\n\");\ \ for (int i = 0; i \< size; i++) {\ int min\_distance = 9999999;\ int closest\_request = -1;\ \ // Find the closest unvisited request\ for (int j = 0; j \< size; j++) {\ if (!visited\[j\] && abs(requests\[j\] - head) \< min\_distance) {\ min\_distance = abs(requests\[j\] - head);\ closest\_request = j;\ }\ }\ \ visited\[closest\_request\] = 1;\ total\_seek += min\_distance;\ printf(\"Seek from %d to %d (Distance: %d)\\n\", head, requests\[closest\_request\], min\_distance);\ head = requests\[closest\_request\];\ }\ printf(\"Total Seek Distance: %d\\n\", total\_seek);\ }\ \ int main() {\ int requests\[\] = {98, 183, 37, 122, 14, 124, 65, 67};\ int size = sizeof(requests) / sizeof(requests\[0\]);\ \ sstf(requests, size);\ \ return 0;\ } ### **Explanation:** - **SSTF**: The closest request is selected first, minimizing the seek time at each step. #### **3.3 SCAN and C-SCAN** These two algorithms move the head across the disk from one end to the other and back, servicing requests as it goes. You can implement **SCAN** and **C-SCAN** similarly by moving in a direction until the end is reached, then reversing (SCAN) or jumping back to the beginning (C-SCAN). ### **Summary** - **File Operations**: We simulated basic file creation, deletion, and content display in a directory. - **File Allocation**: We implemented **Contiguous**, **Linked**, and **Indexed** allocation methods for file storage on disk. - **Disk Scheduling**: We simulated **FCFS**, **SSTF**, **SCAN**, and **C-SCAN** disk scheduling algorithms to service disk requests based on seek distances. These tasks provide a foundation for understanding file system management and operations such as file allocation and disk scheduling in operating systems. **Ques.9) Virtual Memory Management** ** Objective: Work with virtual memory and page management.** ** Tasks:** **o Implement a simulation of virtual memory using paging.** **o Write a program to simulate the demand paging concept.** **o Simulate page replacement policies (FIFO, LRU).** **o Implement a program to track page faults during process execution.** ### **Ans- Virtual Memory Management** Virtual memory is a memory management technique that provides an \"idealized abstraction of the storage resources\" that are actually available on a given machine. It creates the illusion to users of a very large (main) memory. In this task, we will simulate virtual memory using **paging**, **demand paging**, and **page replacement policies** like **FIFO** and **LRU**. We will also implement a program to track **page faults** during process execution. ### **1. Simulation of Virtual Memory using Paging** Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. In paging, the physical memory is divided into fixed-sized blocks called **frames**, while the logical memory is divided into blocks of the same size, called **pages**. We will implement a simple simulation that maps virtual pages to physical frames. #### **C Program: Virtual Memory Simulation Using Paging** \#include \\ \#include \\ \ \#define PAGE\_SIZE 4 // Size of a page (in terms of memory frames)\ \#define FRAME\_COUNT 3 // Number of frames in physical memory\ \#define TOTAL\_PAGES 6 // Total number of virtual pages\ \ // Physical memory (frame count)\ int physical\_memory\[FRAME\_COUNT\] = {-1, -1, -1}; // -1 represents empty frame\ \ // Function to display the current physical memory state\ void displayMemory() {\ printf(\"Physical Memory: \");\ for (int i = 0; i \< FRAME\_COUNT; i++) {\ printf(\"%d \", physical\_memory\[i\]);\ }\ printf(\"\\n\");\ }\ \ // Simulate paging by mapping pages to frames\ void simulatePaging(int \*page\_access\_sequence, int page\_count) {\ int page\_faults = 0;\ \ // Iterate over the sequence of page accesses\ for (int i = 0; i \< page\_count; i++) {\ int page = page\_access\_sequence\[i\];\ int page\_found = 0;\ \ // Check if the page is already in physical memory\ for (int j = 0; j \< FRAME\_COUNT; j++) {\ if (physical\_memory\[j\] == page) {\ page\_found = 1;\ break;\ }\ }\ \ // If the page is not in memory, we have a page fault\ if (!page\_found) {\ page\_faults++;\ // Find an empty frame or replace an existing one (FIFO strategy)\ int replaced = 0;\ for (int j = 0; j \< FRAME\_COUNT; j++) {\ if (physical\_memory\[j\] == -1) {\ physical\_memory\[j\] = page;\ replaced = 1;\ break;\ }\ }\ \ if (!replaced) {\ // Simulate FIFO: Replace the first page in memory\ for (int j = 0; j \< FRAME\_COUNT - 1; j++) {\ physical\_memory\[j\] = physical\_memory\[j + 1\];\ }\ physical\_memory\[FRAME\_COUNT - 1\] = page;\ }\ }\ \ // Display the current state of memory\ displayMemory();\ }\ \ printf(\"Total page faults: %d\\n\", page\_faults);\ }\ \ int main() {\ // Sequence of page accesses (pages requested by a process)\ int page\_access\_sequence\[\] = {0, 1, 2, 0, 3, 4, 0, 1, 2, 3, 4};\ int page\_count = sizeof(page\_access\_sequence) / sizeof(page\_access\_sequence\[0\]);\ \ // Simulate paging and handle page faults\ simulatePaging(page\_access\_sequence, page\_count);\ \ return 0;\ } ### **Explanation:** - **Physical Memory**: We have an array physical\_memory representing the available frames in physical memory. - **Paging**: We simulate a sequence of page accesses using the simulatePaging function. If a page is already in memory, no fault occurs. If it\'s not in memory, a **page fault** happens, and the page is loaded into an available frame. - **Page Replacement**: If memory is full, the first-in (FIFO) page is replaced by the new page. - **Page Fault Tracking**: We count how many page faults occurred during the process execution. ### **2. Simulating Demand Paging** Demand paging is a technique where pages are brought into memory only when they are needed (i.e., when a page fault occurs). #### **C Program: Demand Paging Simulation** \#include \\ \#include \\ \ \#define PAGE\_COUNT 5\ \#define FRAME\_COUNT 3\ \ // Physical memory (frame count)\ int physical\_memory\[FRAME\_COUNT\] = {-1, -1, -1}; // -1 represents empty frame\ \ // Function to display the current physical memory state\ void displayMemory() {\ printf(\"Physical Memory: \");\ for (int i = 0; i \< FRAME\_COUNT; i++) {\ printf(\"%d \", physical\_memory\[i\]);\ }\ printf(\"\\n\");\ }\ \ // Simulate demand paging by loading pages into memory on demand\ void demandPaging(int \*page\_access\_sequence, int page\_count) {\ int page\_faults = 0;\ \ for (int i = 0; i \< page\_count; i++) {\ int page = page\_access\_sequence\[i\];\ int page\_found = 0;\ \ // Check if the page is already in memory\ for (int j = 0; j \< FRAME\_COUNT; j++) {\ if (physical\_memory\[j\] == page) {\ page\_found = 1;\ break;\ }\ }\ \ // If the page is not in memory, it will be brought in (page fault)\ if (!page\_found) {\ page\_faults++;\ \ // Find an empty frame or replace an existing one (FIFO strategy)\ int replaced = 0;\ for (int j = 0; j \< FRAME\_COUNT; j++) {\ if (physical\_memory\[j\] == -1) {\ physical\_memory\[j\] = page;\ replaced = 1;\ break;\ }\ }\ \ if (!replaced) {\ // Simulate FIFO: Replace the first page in memory\ for (int j = 0; j \< FRAME\_COUNT - 1; j++) {\ physical\_memory\[j\] = physical\_memory\[j + 1\];\ }\ physical\_memory\[FRAME\_COUNT - 1\] = page;\ }\ }\ \ // Display the current state of memory\ displayMemory();\ }\ \ printf(\"Total page faults: %d\\n\", page\_faults);\ }\ \ int main() {\ // Sequence of page accesses (pages requested by a process)\ int page\_access\_sequence\[\] = {0, 1, 2, 0, 3, 4, 0, 1, 2, 3, 4};\ int page\_count = sizeof(page\_access\_sequence) / sizeof(page\_access\_sequence\[0\]);\ \ // Simulate demand paging\ demandPaging(page\_access\_sequence, page\_count);\ \ return 0;\ } ### **Explanation:** - **Demand Paging**: Similar to the previous simulation, the difference is that we load pages into memory only when they are needed, i.e., upon a page fault. ### **3. Page Replacement Policies (FIFO and LRU)** We will now implement the two common page replacement policies: **FIFO (First-In-First-Out)** and **LRU (Least Recently Used)**. #### **3.1 FIFO (First-In, First-Out)** In FIFO, the page that has been in memory the longest is replaced when a new page is required. The FIFO policy has already been demonstrated in the previous code examples, where we replaced the oldest page in memory (the first one) when a page fault occurs. #### **3.2 LRU (Least Recently Used)** In LRU, the page that has not been used for the longest period of time is replaced. #### **C Program: LRU Page Replacement Simulation** \#include \\ \#include \\ \ \#define FRAME\_COUNT 3\ \#define PAGE\_COUNT 10\ \ // Physical memory (frame count)\ int physical\_memory\[FRAME\_COUNT\] = {-1, -1, -1}; // -1 represents empty frame\ int time\_stamp\[FRAME\_COUNT\] = {0}; // Time stamps for LRU\ \ // Function to display the current physical memory state\ void displayMemory() {\ printf(\"Physical Memory: \");\ for (int i = 0; i \< FRAME\_COUNT; i++) {\ printf(\"%d \", physical\_memory\[i\]);\ }\ printf(\"\\n\");\ }\ \ // Simulate LRU page replacement\ void lruPaging(int \*page\_access\_sequence, int page\_count) {\ int page\_faults = 0;\ int time\_counter = 0;\ \ for (int i = 0; i \< page\_count; i++) {\ int page = page\_access\_sequence\[i\];\ int page\_found = 0;\ int lru\_page\_index = -1;\ int lru\_time = time\_counter;\ \ // Check if the page is already in memory\ for (int j = 0; j \< FRAME\_COUNT; j++) {\ if (physical\_memory\[j\] == page) {\ page\_found = 1;\ time\_stamp\[j\] = time\_counter;\ break;\ }\ }\ \ // If the page is not in memory, we have a page fault\ if (!page\_found) {\ page\_faults++;\ \ // Find the least recently used page (LRU)\ for (int j = 0; j \< FRAME\_COUNT; j++) {\ if (physical\_memory\[j\] == -1) {\ physical\_memory\[j\] = page;\ time\_stamp\[j\] = time\_counter;\ break;\ } else if (time\_stamp\[j\] \< lru\_time) {\ lru\_time = time\_stamp\[j\];\ lru\_page\_index = j;\ }\ }\ \ // Replace the LRU page\ if (lru\_page\_index != -1) {\ physical\_memory\[lru\_page\_index\] = page;\ time\_stamp\[lru\_page\_index\] = time\_counter;\ }\ }\ \ // Display the current state of memory\ displayMemory();\ time\_counter++;\ }\ \ printf(\"Total page faults: %d\\n\", page\_faults);\ }\ \ int main() {\ // Sequence of page accesses (pages requested by a process)\ int page\_access\_sequence\[\] = {0, 1, 2, 0, 3, 4, 0, 1, 2, 3, 4};\ int page\_count = sizeof(page\_access\_sequence) / sizeof(page\_access\_sequence\[0\]);\ \ // Simulate LRU paging\ lruPaging(page\_access\_sequence, page\_count);\ \ return 0;\ } ### **Explanation:** - **LRU**: The page that has not been used for the longest time is replaced. - We keep track of the **time stamps** of each page, and when a page fault occurs, we replace the page with the smallest time stamp. ### **4. Tracking Page Faults** In the above code snippets, page faults are tracked by maintaining a counter (page\_faults), which is incremented every time a page fault occurs. The state of memory (pages loaded into frames) is displayed after each page access. ### **Summary:** - **Paging**: We simulated virtual memory with paging, mapping virtual pages to physical frames. - **Demand Paging**: Implemented a simulation where pages are loaded into memory only when required, tracking page faults. - **Page Replacement**: We simulated the **FIFO** and **LRU** page replacement policies, tracking page faults and memory state. **Ques.10) Disk Scheduling Algorithms** ** Objective: Understand and implement various disk scheduling algorithms.** ** Tasks:** **o Simulate First-Come-First-Served (FCFS) disk scheduling.** **o Implement Shortest Seek Time First (SSTF) disk scheduling.** **o Write a program to simulate SCAN, C-SCAN disk scheduling.** ### **Ans- Disk Scheduling Algorithms** Disk scheduling algorithms are used to determine the order in which disk I/O requests should be processed in order to optimize performance, such as minimizing the seek time. Here, we\'ll implement and simulate several disk scheduling algorithms: 1. **First-Come, First-Served (FCFS)**: The simplest disk scheduling algorithm, where requests are served in the order they arrive. 2. **Shortest Seek Time First (SSTF)**: This algorithm selects the request that is closest to the current head position. 3. **SCAN and C-SCAN**: These algorithms move the disk arm towards the end (or beginning) of the disk and then reverse direction once the end is reached. ### **1. FCFS Disk Scheduling** In **FCFS**, requests are handled in the order they arrive. The seek time is simply the absolute difference between the current position of the disk head and the requested track. #### **C Program: FCFS Disk Scheduling** \#include \\ \#include \\ \ void FCFS(int \*requests, int n, int head) {\ int total\_seek = 0;\ \ printf(\"FCFS Disk Scheduling:\\n\");\ printf(\"Initial Head Position: %d\\n\", head);\ \ for (int i = 0; i \< n; i++) {\ total\_seek += abs(head - requests\[i\]);\ head = requests\[i\];\ printf(\"Serving request: %d, Seek distance: %d\\n\", requests\[i\], abs(head - requests\[i\]));\ }\ \ printf(\"Total seek time: %d\\n\", total\_seek);\ }\ \ int main() {\ int requests\[\] = {55, 58, 60, 98, 8, 16, 14}; // Example disk request queue\ int n = sizeof(requests) / sizeof(requests\[0\]);\ int head = 50; // Starting position of the disk head\ \ FCFS(requests, n, head);\ return 0;\ } ### **Explanation:** - The program calculates the seek time for each request by computing the absolute difference between the current head position and the requested track. - Requests are processed in the order they appear in the requests\[\] array. ### **2. Shortest Seek Time First (SSTF) Disk Scheduling** In **SSTF**, the request closest to the current head position is selected first. This minimizes the seek time at each step, but may lead to starvation for requests that are far away from the head. #### **C Program: SSTF Disk Scheduling** \#include \\ \#include \\ \ void SSTF(int \*requests, int n, int head) {\ int total\_seek = 0;\ int visited\[n\];\ for (int i = 0; i \< n; i++) {\ visited\[i\] = 0; // All requests are initially unvisited\ }\ \ printf(\"SSTF Disk Scheduling:\\n\");\ printf(\"Initial Head Position: %d\\n\", head);\ \ for (int count = 0; count \< n; count++) {\ int min\_seek = 10000; // A large value to start with\ int index = -1;\ \ // Find the request with the minimum seek time\ for (int i = 0; i \< n; i++) {\ if (!visited\[i\]) {\ int seek\_time = abs(requests\[i\] - head);\ if (seek\_time \< min\_seek) {\ min\_seek = seek\_time;\ index = i;\ }\ }\ }\ \ // Mark the selected request as visited\ visited\[index\] = 1;\ total\_seek += min\_seek;\ head = requests\[index\];\ printf(\"Serving request: %d, Seek distance: %d\\n\", requests\[index\], min\_seek);\ }\ \ printf(\"Total seek time: %d\\n\", total\_seek);\ }\ \ int main() {\ int requests\[\] = {55, 58, 60, 98, 8, 16, 14}; // Example disk request queue\ int n = sizeof(requests) / sizeof(requests\[0\]);\ int head = 50; // Starting position of the disk head\ \ SSTF(requests, n, head);\ return 0;\ } ### **Explanation:** - For each iteration, the program finds the unvisited request that is closest to the current disk head, ensuring the shortest seek time. - The seek time is accumulated, and the requests are marked as visited to avoid revisiting them. ### **3. SCAN and C-SCAN Disk Scheduling** In **SCAN**, the disk head moves in one direction (towards the end or start) until it reaches the last request, then it reverses direction. The **C-SCAN** variant only moves in one direction and resets to the beginning when it reaches the end. #### **C Program: SCAN and C-SCAN Disk Scheduling** \#include \\ \#include \\ \ void SCAN(int \*requests, int n, int head, int disk\_size) {\ int total\_seek = 0;\ int left\[disk\_size\], right\[disk\_size\];\ int left\_index = 0, right\_index = 0;\ \ // Divide the requests into left and right of the head\ for (int i = 0; i \< n; i++) {\ if (requests\[i\] \< head) {\ left\[left\_index++\] = requests\[i\];\ } else {\ right\[right\_index++\] = requests\[i\];\ }\ }\ \ // Sort both left and right\ for (int i = 0; i \< left\_index - 1; i++) {\ for (int j = i + 1; j \< left\_index; j++) {\ if (left\[i\] \< left\[j\]) {\ int temp = left\[i\];\ left\[i\] = left\[j\];\ left\[j\] = temp;\ }\ }\ }\ \ for (int i = 0; i \< right\_index - 1; i++) {\ for (int j = i + 1; j \< right\_index; j++) {\ if (right\[i\] \> right\[j\]) {\ int temp = right\[i\];\ right\[i\] = right\[j\];\ right\[j\] = temp;\ }\ }\ }\ \ printf(\"SCAN Disk Scheduling:\\n\");\ printf(\"Initial Head Position: %d\\n\", head);\ \ // Move towards the left end\ for (int i = left\_index - 1; i \>= 0; i\--) {\ total\_seek += abs(head - left\[i\]);\ head = left\[i\];\ }\ \ // Move towards the right end\ for (int i = 0; i \< right\_index; i++) {\ total\_seek += abs(head - right\[i\]);\ head = right\[i\];\ }\ \ printf(\"Total seek time: %d\\n\", total\_seek);\ }\ \ void C\_SCAN(int \*requests, int n, int head, int disk\_size) {\ int total\_seek = 0;\ int left\[disk\_size\], right\[disk\_size\];\ int left\_index = 0, right\_index = 0;\ \ // Divide the requests into left and right of the head\ for (int i = 0; i \< n; i++) {\ if (requests\[i\] \< head) {\ left\[left\_index++\] = requests\[i\];\ } else {\ right\[right\_index++\] = requests\[i\];\ }\ }\ \ // Sort both left and right\ for (int i = 0; i \< left\_index - 1; i++) {\ for (int j = i + 1; j \< left\_index; j++) {\ if (left\[i\] \< left\[j\]) {\ int temp = left\[i\];\ left\[i\] = left\[j\];\ left\[j\] = temp;\ }\ }\ }\ \ for (int i = 0; i \< right\_index - 1; i++) {\ for (int j = i + 1; j \< right\_index; j++) {\ if (right\[i\] \> right\[j\]) {\ int temp = right\[i\];\ right\[i\] = right\[j\];\ right\[j\] = temp;\ }\ }\ }\ \ printf(\"C-SCAN Disk Scheduling:\\n\");\ printf(\"Initial Head Position: %d\\n\", head);\ \ // Move towards the right end\ for (int i = 0; i \< right\_index; i++) {\ total\_seek += abs(head - right\[i\]);\ head = right\[i\];\ }\ \ // Jump to the left end and process requests\ total\_seek += head; // Seek from current head to the end\ head = 0;\ for (int i = 0; i \< left\_index; i++) {\ total\_seek += abs(head - left\[i\]);\ head = left\[i\];\ }\ \ printf(\"Total seek time: %d\\n\", total\_seek);\ }\ \ int main() {\ int requests\[\] = {55, 58, 60, 98, 8, 16, 14}; // Example disk request queue\ int n = sizeof(requests) / sizeof(requests\[0\]);\ int head = 50; // Starting position of the disk head\ int disk\_size = 200; // Assume disk size (total tracks)\ \ SCAN(requests, n, head, disk\_size);\ C\_SCAN(requests, n, head, disk\_size);\ \ return 0;\ } ### **Explanation:** - **SCAN**: The head moves to the leftmost end, serving requests in that direction, and then reverses direction after reaching the end. - **C-SCAN**: The head moves to the rightmost end and then resets to the leftmost end, serving requests along the way. - The requests are divided into two groups (left and right of the head), sorted, and then processed in the appropriate direction. ### **Summary:** - **FCFS**: Requests are processed in the order they arrive, with seek time calculated as the difference between consecutive requests. - **SSTF**: The closest request is processed first, minimizing seek time at each step but potentially causing starvation. **SCAN** and **C-SCAN**: These algorithms move the head to one end of the disk, then reverse direction (SCAN) or reset to the other end (C-SCAN) to process requests efficiently. **Thank** **You**

Lab Assignment: Operating System - Suwarnika Srivastava

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue