Exercise 16, 2010

Preliminary Exam

I.                    Concept Questions

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

Answers:  

 

1. User 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

This component tracks every file in the system. These files include data files, assemblers, compilers, and applications. 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 system and explain how it works.

Answers:

Interrupt Request (IRQ)

      Is a signal that has a direct line to the computer processor, allowing it to stop the processor momentarily and decide what to do next.

Input/output (I/O)

      Represents the locations in memory that are designated by use of various devices to exchange information amongst themselves and the rest of the PC.

Direct memory access (DM)

      Are pathways provided by the hardware to allow the hardware direct access to the computer's memory.

 

3.       Explain the following:

a.       Internal fragmentation. How does it occur?

Answer: A form of fragmentation that arises when allocations of memory are made only in multiples of a subunit. A request of arbitrary size must be met by rounding up to the next highest multiple of the subunit, leaving a small amount of memory that is allocated but not in use. Internal fragmentation is reduced by reducing the size of the subunit; such a reduction increases external fragmentation.

b.      External fragmentation. How does it occur?

Answer: A form of fragmentation that arises when memory is allocated in units of arbitrary size. When a large amount of memory is released, part of it may be used to meet a subsequent request, leaving an unused part that is too small to meet any further requests.

c.       Compaction. Why is it needed?

Answer: It attacks the problem of fragmentation by moving all the allocated blocks to one end of memory, thus combining all the holes. Aside from the obvious cost of all that copying, there is an important limitation to compaction: Any pointers to a block need to be updated when the block is moved. Unless it is possible to find all such pointers, compaction is not possible. Pointers can stored in the allocated blocks themselves as well as other places in the client of the memory manager. In some situations, pointers can point not only to the start of blocks but also into their bodies. For example, if a block contains executable code, a branch instruction might be a pointer to another location in the same block. Compaction is performed in three phases. First, the new location of each block is calculated to determine the distance the block will be moved. Then each pointer is updated by adding to it the amount that the block it is pointing (in)to will be moved. Finally, the data is actually moved. There are various clever tricks possible to combine these operations.

 

4.       Cache memory how it works?

Answer: Cache memory works by attempting to predict which memory the processor is going to need next, and loading that memory before the processor needs it, and saving the results after the processor is done with it. Whenever the byte at a given memory address is needed to be read, the processor attempts to get the data from the cache memory.  If the cache doesn't have that data, the processor is halted while it is loaded from main memory into the cache.  At that time memory around the required data is also loaded into the cache. When data is loaded from main memory to the cache, it will have to replace something that is already in the cache.  So, when this happens, the cache determines if the memory that is going to be replaced has changed.  If it has, it first saves the changes to main memory, and then loads the new data.

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

Answer: L1-cache is the fastest cache and it usually comes within the processor chip itself. The L1 cache typically ranges in size from 8KB to 64KB and uses the high-speed SRAM (static RAM) instead of the slower and cheaper DRAM (dynamic RAM) used for main memory. The Intel Celeron processor uses two separate 16KB L1 caches, one for the instructions and one for the data.

 

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

 

Memory Block	Size
1132	700
1003	720
1114	800
2310	750
1755	610

 

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

Memory Block	Memory Block Size	Job Number	Job Size	Status	Internal Fragmentation
1132	700	J1	700KB	Busy	0
1003	720	J5	610KB	Busy	110KB
1114	800	J3	740KB	Busy	60KB
2310	750			Idle
1755	610	J2	500KB	Busy	110KB
Total Available:	3580	Total Used:	2550KB		280KB

 

 

 

 

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

Memory Block	Memory Block Size	Job Number	Job Size	Status	Internal Fragmentation
1132	700	J1	700KB	Busy	0
1003	720	J2	500KB	Busy	220KB
1114	800	J3	740KB	Busy	60KB
2310	750
1755	610	J5	610KB	Busy	0
Total Available:	3580	Total Used:	2550KB		280KB

 

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

Memory Block	Memory Block Size	Job Number	Job Size	Status	Internal Fragmentation
1132	700			Idle
1003	720	J5	610	Busy	110KB
1114	800	J3	740	Busy	60KB
2310	750	J1	700KB	Busy	50KB
1755	610	J2	500KB	Busy	110KB
Total Available:	3580	Total Used:	2550KB		330KB

 

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

 

Memory Block	Memory Block Size	Job Number	Job Size	Status	Internal Fragmentation
1132	700			Idle
1003	720	J5	610KB	Busy	110KB
1114	800	J1	700KB	Busy	100KB
2310	750	J2	500KB	Busy	250KB
1755	610			Idle
Total Available:	3580	Total Used:	2550KB		460KB

 

2.       Given the following information:

Table 2A 

                                               

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

 

Table 2B

Original State of  main Memory

100KB (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 Job6(30KB) and Job7(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:

Job 1 is 1600 lines long PS=200 and LNTBL=542.

LNTBL divided by PS and the result is the Page Number and the remainder is the displacement

 

542 ÷ 200=2 the remainder is 142

Therefore the displacement is 142

                       

                       

                        ­­­