7 Cases in deadlocks

1. Deadlocks on file requests

• Any other programs that require F1 or F2 are put on hold as long as this situation continues.

• If jobs can request and hold files for duration of their execution, deadlock can occur.

• Deadlock remains until a programs is withdrawn or forcibly removed and its file is released.

Example:

2. Deadlocks in databases

• Deadlock can occur if 2 processes access & lock records in database.

• 3 different levels of locking :

– entire database for duration of request

– a subsection of the database

– individual record until process is completed.

• If don’t use locks, can lead to a race condition

Example:

1. P1 accesses R1 and locks it.

2. P2 accesses R2 and locks it.

3. P1 requests R2, which is locked by P2.

4. P2 requests R1, which is locked by P1.

3. Deadlocks in dedicated device allocation

• Deadlock can occur when there is a limited number of dedicated devices.

• E.g., printers, plotters or tape drives.

Example:

1. P1 requests tape drive 1 and gets it.

2. P2 requests tape drive 2 and gets it.

3. P1 requests tape drive 2 but is blocked.

4. P2 requests tape drive 1 but is blocked.

4. Deadlocks in multiple device allocation

• Deadlocks can happen when several processes request, and hold on to, dedicated devices while other processes act in a similar manner.

Example:

5. Deadlocks in spooling

• Most systems have transformed dedicated devices such as a printer into a sharable device by installing a high-speed device, a disk, between it and the CPU.

• Disk accepts output from several users and acts as a temporary storage area for all output until printer is ready to accept it (spooling).

• If printer needs all of a job's output before it will begin printing, but spooling system fills available disk space with only partially completed output, then a deadlock can occur.

6. Deadlocks in disk sharing

• Disks are designed to be shared, so it’s not uncommon for 2 processes access different areas of same disk.

• Without controls to regulate use of disk drive, competing processes could send conflicting commands and deadlock the system.

7. Deadlocks in a network

• A network that’s congested (or filled large % of its I/O buffer space) can become deadlocked if it doesn’t have protocols to control flow of messages through network.

Example:

Lanugan, Ruby M.                                                                                                                                            Jan. 9 2010

 

Concept  Question.

1.      Name the five key concepts about an operating system that you think a user needs to know and understand.

Ans.

1. Command Interface -This  is the interface from which the user issues commands to the operating system. Also called the “shell” (container inside which the entire user interface is presented), this is the visible interface with which users interact. For most users, the User Interface is the operating system.

2. Device Manager- This component monitors all devices, channels, and control units. The Device Manager must select the most efficient method for allocation of a system’s devices, printers, terminals, disk drives, and other hardware. This is based on a pre-determined scheduling policy, and the Device Manager makes allocations, starts operations, and ultimately deallocates devices.

3. Processor Manager- This component is responsible for allocating the central processing unit (CPU). The status of each process must be tracked, and the Processor Manager handles matters such as process prioritization and multithreading. The tasks of the Processor Manager can be divided into two main categories: accepting or rejecting incoming jobs (handled by the Job Scheduler) and determining which process is given access to the CPU and for how long (handled by the Process Scheduler

4. Memory Manager- This component controls main memory. It evaluates the validity of each memory request, and allocates memory space (as needed and available). For multi-user systems, the Memory Manager maintains a log of what memory resources are in use by which users. When items stored in main memory are no longer needed, the Memory Manager handles memory deallocation

5. File Manager- The File Manager can use predetermined access policies to enforce restrictions on file access. It also handles all other file permissions. The File Manager allocates file resources by opening a particular file and deallocates resources by closing the file.

             2. List three tangible (physical) resources of a computer system and explain how  it     works.

Ans.

             3. Explain the following:

a.       Internal fragmentation. How does it occur?

Internal Fragmentation: Internal fragmentation is the space wasted inside of allocated memory blocks because of restriction on the allowed sizes of allocated blocks. Allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used.

b.       External fragmentation. How does it occur?

Answer: External Fragmentation happens when a dynamic memory allocation algorithm allocates some memory and a small piece is left over that cannot be effectively used. If too much external fragmentation occurs, the amount of usable memory is drastically reduced. Total memory space exists to satisfy a request, but it is not contiguous.

 

c.        Compaction. Why is it needed?

             4. Cache memory how it works?

             Answer.  A CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. The cache is a smaller, faster memory which stores copies of the data from the most frequently used main memory locations. As long as most memory accesses are cached memory locations, the average latency of memory accesses will be closer to the cache latency than to the latency of main memory.

             5. Which is the fastest cache’s L1, L2 or L3? Why?

            Answer: L1 cache is the smallest and the fastest, the smaller each transistor is, the more of them will fit in your CPU, allowing for faster CPUs with more stuff crammed in. Smaller transistors also switch faster, allowing higher clock speeds, and use less power..

II. Memory Utilization Problem.

1.      Given the following information:

  Table 1A

Job Number	Memory Requested
J1	700KB
J2	500KB
J3	740KB
J4	850KB
J5	610KB

          a. Use the best-fit algorithm to allocate the memory blocks to the five arriving jobs.

          b. Use the first-fit algorithm to allocate the memory blocks to the five arriving jobs.

          c. Use the next-fit algorithm to allocate the memory blocks to the five arriving jobs.

                   d. Use the worst-fit algorithm to allocate the memory blocks to the five arriving jobs.

2. Given the following information.

  

 

Table 2A

Job Number	Memory Requested
J1	30KB
J2	50KB
J3	30KB
J4	25KB
J5	35KB

 

 

 

               

     

ORIGINAL STATEOF MAIN MEMORY

1000KB(P1)

25KB(P2)

25KB(P3)

50KB(P4)

30KB(P5)

a.Create a memory layout for the fixed partition after job entry based on the given information( Table 2A and Table 2B).

b. Before Job 6(30KB) and Job 7(45KB)arrives, there are three jobs done ready for processing which J2, J3, J4. Create an initial memory layout for the dynamic partition based on the given information (Table 2A)
   

3.  Illustrate and find the page number with the displacement of a given program line:

Job1 is 1600 lines long PS=200 and LNTBL=542                                                                                                

Best-fit algorithm

Memory Block	Memory Size	JOB Number	JOB Size	Status	Internal Fragmentation
1132	700	J1	700KB	Busy	0
1003	720	J5	610KB	Busy	110
1114	800	J3	740KB	Busy	60
2310	750	-	-	Free
1755	610	J2	500KB	Busy	110

First-fit algorithm

Memory Block	Memory Size	JOB Number	JOB Size	Status	Internal Fragmentation
1132	700	J1	700	Busy	0
1003	720	J2	500	Busy	220
1114	800	J3	740	Busy	60
2310	750	J5	610	Busy	140
1755	610	-	-	Free

Next-fit algorithm

Memory Block	Memory Size	JOB Number	JOB Size	Status	Internal Fragmentation
1132	700	-	-	Free
1003	720	J5	610	Busy	110
1114	800	J3	740	Busy	60
2310	750	J1	700	Busy	50
1755	610	J2	500	Busy	110

            Worst-fit algorithm   

Memory Block	Memory Size	JOB Number	JOB Size	Status	Internal Fragmentation
1132	700	-	-	Free
1003	720	J5	610	Busy	110
1114	800	J1	700	Busy	100
2310	750	J2	500	Busy	250
1755	610	-	-	Free