Midterm Flashcards

Question

What are the three types of services that cloud environments offer?

Answer 1

SaaS (software as a service), PaaS (platform as a service), and IaaS (infrastructure as a service).

Answer 2

Private, public, hybrid

Answer 3

1- Increased throughput, 2- Lower costthan using a collection of single processors, 3- Reliability is higher, and the system is more fault-tolerant

Answer 4

Asymmetric multiprocessor is a CPU scheduling method in which all scheduling decisions, I/O processing, and other system activities are handled by a single processor — the master server. The other processors execute only user code. This is a simple method because only one core accesses the system data structures, reducing the need for data sharing. The downfall of this approach is that the master server becomes a potential bottleneck where overall system performance may be reduced. Symmetric multiprocessor (SMT) is the standard approach for supporting multiprocessors where each processor is self-scheduling.

Answer 5

1-Creating and deleting both user and system processes 2-Suspending and resuming processes 3-Providing mechanisms for process synchronization 4-Providing mechanisms for process communication 5-Providing mechanisms for deadlock handling

Answer 6

A program is a collection of instructions and is a passive entity. A process is a program in execution and is an active entity.

Answer 7

1- A stream of addresses + read requests 2- A stream of addresses + data and write requests

Answer 8

It takes many CPU cycles. AMAT= cache-hit-time+ miss-rate*miss-penalty

Answer 9

It takes one clock cycle (or less)

Answer 10

Number of bytes accessed in a time unit (Bytes/sec)

Answer 11

A system that determines whatis in memory and when. It is a system that optimizes the CPU’s utilization and the overall computer’s response to users. (this question says what MM has to do, but we don’t say how it will be done)

Answer 12

This is how MM should implement its goal: It keeps track of which parts of the memory are currently being used. It means there is, for example, a table showing which frames are occupied by what pages. Next, it decides which processes (or parts thereof) and data to move into and out of the memory. It means that the tale has a column for the process IDs showing what pages each process owns. Finally, it allocates and deallocates the memory space as needed. The table should be updated as the processes come in or go out

Answer 13

The throughput of DRAM is much lower than what the CPU requires.

Answer 14

Creating a pyramid with slow, cheap, and large memory at the bottom and placing fast, expensive, and small memories at the top.

Answer 15

When a reference is made to memory, the same location, or locations near that, will be referenced soon.

Answer 16

By using memory hierarchy

Answer 17

Low locality causes a high miss rate, forcing memory management to refer to slower parts of the hierarchy

Answer 18

Answer: 50> 2 +miss_rate*100. miss_rate should be less than 0.48

Answer 19

RAM, SAM, DASD, CAM. Nowadays, SAM (sequential access memory) is not used anymore. RAM (Random access memory) is the method of accessing SSDs and main memory. DASD is the method of accessing hard disks, a combination of SAM and RAM. Finally, CAM (Content addressable memory or Associative Memory) is widely used. For example, CAM is used in TLBs, cache structures, routers to lookup destination IPs, image search to lookup image descriptions, etc.

Answer 20

The content of layer 𝑖𝑖 of the hierarchy has to exist in layer 𝑖𝑖 + 1.

Answer 21

1- placement policy, 2- identification policy, 3- replacement policy, 4- update policy.

Answer 22

conversion of virtual addresses to physical addresses is called mapping.

Answer 23

As a general definition, binding means mapping from one address space to another. Traditionally, binding is categorized into compile-time-binding, load-time-binding, and execution-timebinding.

Answer 24

Load time binding: The compiler translates symbolic addresses to relative (relocatable) addresses. The loader translates these to absolute addresses. If it is not known at compile time where the process will reside in memory, then the compiler must generate relocatable code. This is done once, and swapping cannot be performed, which makes the method static. Execution time binding: If the process can be moved during its execution from one memory segment to another, then binding must be delayed until run time. The absolute addresses are generated by hardware. Most general-purpose OSs use this method (Dynamic). Static-binding means locations are determined before execution. Dynamicbinding means locations are determined during execution.

Answer 25

Logical address – addresses generated by a program and sent to the CPU; also referred to as virtual address Physical addresses are addresses seen by the memory unit assigned to a program depending on where the program resides in the main memory.

Answer 26

The run-time mapping from virtual to physical addresses is performed by hardware called the memory-management unit (MMU).

Answer 27

Dynamic relocation is relocating data or codes currently in the computer’s memory to other parts of the computer, creating more efficient memory storage while a program is still active

Answer 28

A relocation register

Answer 29

A significant portion of the code is used for rare cases in some programs, and only a small piece of the code is frequently used. For such applications, dynamic relocation can be used efficiently. Such applications are known as 20- 80, which means that 20% of the code is used 80% of the time.

Answer 30

Stub is used for dynamic linking, where linking is postponed until execution time. A stub is a small piece of code used to locate the appropriate memory-resident library routine. Stub replaces itself with the address of the library routine and executes the routine.

Answer 31

Contiguous allocation means allocating a contiguous region of the main memory to a program.

Answer 32

Segmentation allocates one piece of memory, called a segment, to one program. Different parts of the memory, called pages, could contain a part of a program in paging. These pages could be noncontiguous.

Answer 33

segment number and offset.

Answer 34

a) The percentage of occupied memory when there is no room for a new process is the efficiency—the higher this percentage, the smaller the useless fragments. b) When a process arrives, it is allocated memory from a hole large enough to accommodate it. c) The exiting process frees its partition. Then, adjacent accessible partitions are combined. d) OS maintains information about allocated partitions, and free partitions (holes)

Answer 35

First fit, best fit, worst fit.

Answer 36

internal fragmentation, external fragmentation.

Answer 37

external fragmentation occurs between segments

Answer 38

False. The 50% rule means that 50% of the occupied space is useless fragments. Hence, if segments occupy N bytes, then N/2 bytes are fragments, which is 1/3 of the total memory space.

Answer 39

compaction is the solution. It requires that the code and data be relocatable.

Answer 40

Page size is a power of 2. In paging, only one page of a program or data has to bring into the memory. Other parts of the code or data are brought into the memory as needed.

Answer 41

The frame and page are of the same size. A frame is referred to as a physical piece of memory, and a page is referred to as the virtual address space.

Answer 42

t contains a translation (mapping) of virtual to physical addresses.

Answer 43

Use of tlb

Answer 44

a) The page table has 2^20 lines. (32bits-12bits)= bits for virtual page # b) EAT= 0.9*0.5+ 0.1*1=0.55 cycles c) D000EF is the page number that is mapped at frame number 56F. Hence, the physical address is 56F123. The logical address 12345F05 is found in the TLB and the page table. We take the TLB content, which tells us that the physical address is 567F05. d) FEDC05F2 is mapped to F565F2.

Answer 45

This bit is just for protection purposes. The “valid” bit indicates that the associated page is in the process’s logical address space and is, thus, a legal page. The page is not in the process’s logical address space when the bit is invalid. The use of the valid-invalid bit traps illegal addresses. The operating system sets this bit for each page to allow or disallow access to the page.

Answer 46

the Reentrant code is non-self-modifying: it never changes during execution. Thus, two or more processes can execute the same code simultaneously. Each process has its copy of registers and data storage to hold the data for its execution. The data for two different processes will, of course, be different. The reentrant page is a read-only copy of code shared among processes. Examples are text editors, compilers, C libraries, and Windows systems

Answer 47

Hierarchical Paging, Hashed Page Tables, Inverted Page Tables

Answer 48

Page num: P1 = 10 P2 = 10 Page offset: D=12

Answer 49

ABCDEF00 is mapped to 567F00. Virtual address F00BC000 is mapped to 345000. Logical address 12356FFF is not yet mapped to a physical address.

Answer 50

Even a threelevel page table requires a 2^32 line third-level table. If we use more page table layers, for example, eightlayers,then going through all layers to find the page’s address would be prohibitively long. Alternative approaches are using hash tables and TLBs.

Answer 51

we see that pages are 4KB since the low significant 12 bits of the physical and logical addresses are the same. P is the page number which is 52 bits, and the first 13 Hex digits of the address. r is 4FF, and d is CDE. q is another 52-bit page number that is hashed into the same place as p is hashed to. Since we don’t know the hash function, we can throw in any 52-bit number as q. For example, CADF13571234F is q.

Answer 52

a) The page table is as big as the number of physical pages. This method makes the page table size much smaller than using a table that has 2^(number of virtual pages). b) hashing could be used to limit the search. For example, the virtual page number is hashed in three different methods to restrict the search to only three entries of the inverted table

Answer 53

two hash tables are used. One table is used for the user codes, and one table for the OS. Also, a TLB is used for fast search. Page walk: If the address is not in the TLB, the system “walks back” and searches the hash tables.

Answer 54

swapping requires the transfer of data and code from the main memory to the backing store. The data transfer is time-consuming. In UNIX, swapping is disabled until the number of allocated pages becomes higher than a threshold.

Answer 55

Sometimes, a process has to be swapped into the backing store, and that process may have been transferring data from I/O. The swapped-out process would lose the data. OS could use its memory space to buffer the I/O data, and when the process is brought back into the main memory, OS should deliver the buffer data to the process. The data is moved twice, which is called double buffering.

Answer 56

Addresses in IA-32 systems consist of a selector and an offset. A selector is a 16-bit number consisting of s(13 bits), g(1 bit), p(2 bits). The s part designates the segment number, and g indicates whether the segment is in the global descriptor table (GDT) or the local descriptor table (LDT). Also, the 2 bits p is used for protection. An offset is a 32-bit number specifying the location of the byte within the segment in question. An offset of 32 bits means each segment could be as large as 4GB.

Answer 57

f the virtual address is 32 bits, then the physical address is usually less than 32 bits, for example, 28 bits. The high 10 bits of the virtual address are used to find a line in the page directory. A bit in the content of the page directory line indicates if the page size is 4MB or 4KB. For 4MB pages, the page directory provides a 28-bit start address, and we add our 4MB page offset of 22 bits to that. For 4KB pages, the page director offers a 28-bit address that points to the start of a page table. The page table has 2^10 lines, and using the page table part of the virtual address, we refer to the appropriate line of the table. The content of the page table is a 28-bit physical address which we add the 12-bit offset to it to get the physical address of the line of the 4KB page.

Answer 58

f the virtual page table is 32 bits,then the physical address is smaller, and it is, for example, 28 bits. The outer page table entries consist of two bits thatindicate the page size. For example,“00” means the page size is 4KB, “01” means 16KB, “10” means 1MB, and “11” means that the referenced page is 16MB. Besides these two bits, the content of the outer page table has 28 bits, which refer to either the inner page table or a 1MB or 16MB page. Hence, the offset part could be 12 bits, 14 bits, 20 bits, or 24 bits.

Answer 59

a) Only part of the program needs to be in memory for execution, b) Logical address space can be much larger than physical space, c) Several processes can share address spaces, d) More efficient utilization of physical memory, e) More programs can run concurrently, f) Less I/O needed to load processes

Answer 60

Demand paging and demand segmentation.

Answer 61

A program consists of a fixed-size code and different data types. The stack starts at the highest virtual address, and the code begins at address zero. On top of the code are data, and on top of the data, the heap of linked variables is placed.

Answer 62

t starts swapping segments only when the swap is needed to free space in the physical memory

Answer 63

it performs the swapping operation on “pages” rather than segments.

Answer 64

if there were no such a bit, then the table’s initial content may be considered valid frame numbers even if all the table entries were zero. Hence, initially, all of the “VI” bits are zero. Initially, the first demand page causes a “page fault” because the VI bit is zero. After the page is read, the bit becomes valid (one).

Answer 65

Line 0 of PT has 4, line 2 has 6, and line 5 has 9. Valid bits of these lines are 1. The rest of the page table is empty (valid bits are zero.)

Answer 66

a) CPU is referencing a page that is not in the physical memory, and it has an “invalid” bit in the page table b) A trap (interrupt) occurs, and OS takes over the execution process c) OS finds the demanded page in the hard disk d) OS brings the demanded page into the physical memory e) OS updates the page table’s frame number and valid bit. f) The interrupted instruction of the process takes back control and restarts execution.

Answer 67

OS adds a frame to the list of “free-frame-list” by zeroing the content of a frame.

Answer 68

No. It adds an overhead. It doesn’t help identify free frames because checking the zero content of a frame is a lengthy process. Testing the valid bit of a frame is much faster than seeing if the frame’s content is zero. Hence, the only reason for zeroing the content is for security purposes.

Answer 69

Occasionally, two identical processes are created. Each one should have its own memory space. But OS places only one set of pages for both processes to use. If process1 writes into the shared page A, then page A is copied for process1. As a result, process2 will have the original copy of page A. This process is known as copy-on-write (CoW).

Answer 70

OS has to replace a frame to bring in the demanded page

Answer 71

The valid shows whether the content of the page table is valid or not. The dirty bit shows whether the frame’s content has been changed. If the dirty bit is zero, writing back the frame into the disk is unnecessary.

Answer 72

Frame allocation determines which physical memory frames are assigned to virtual memory pages. In contrast, page replacement determines which virtual memory pages are moved from physical memory to make room for new pages.

Answer 73

If the main memory is only one frame, then a page fault occurs each time the sequence wants to access a new page. For example, if the sequence has four consecutive 1’s, then only the first reference to page 1 would cause a fault, and the other three references to page 1 are hits. Hence, in the above sequence, 11 page-faults occur if we only have one frame. If we have two frames in the memory, then four page-faults occur. If we have three frames, then three faults occur, and with four frames, we will have three page-faults

Answer 74

t considers that it knows the future and replaces the page that will not be used shortly.

Answer 75

1) Use a counter next to each frame. Every time that frame is referenced, the counter is incremented. The frame with the smallest counter value is replaced when replacing a frame. After each frame replacement, all counters are reset o zero. 2) We can use a stack. When a page enters the main memory, the page number will be on top of the stack. Every time a page is referenced, its number goes to the top of the stack. When we want to replace a frame, the one at the bottom of the stack is replaced

Answer 76

A reference bit (W) is assigned to each frame. Every time that a frame is referenced, its W bit is set to 1. When a frame is replaced, all W bits are reset to zero. The FIFO strategy is implemented. When a page fault occurs, the frames are tested based on FIFO. If the frame has a zero W, then it is replaced. If the frame has one W, then it is given a second chance, and its W is reset to zero. Then the next frame based on FIFO is checked, and so on

Answer 77

it uses two bits for each frame, a dirty-bit and a reference bit. “00” means that the page is not referenced since the last page-fault, and is not modified. Such a frame has the highest priority for replacement. “10” shows that the frame is referred to but has not been changed. This page has the second-highest replacement priority since it does not need a write-back. “01” indicates that the page is not referenced but modified. This page has the second-lowest priority for removal since we need to write it back into the disk. “11” means that the page has been referenced and has been modified. This page has the lowest priority for replacement. Based on FIFO, frames are tested. If the pair of bits are 00, then the page is replaced. Otherwise, the reference bit of the page is set to zero, and the next frame is tested. A second round is performed if no frame is found in the first round.

Answer 78

Least frequently used page is replaced. Each page has a counter, and every time it is referenced, its counter is incremented. The page with the lowest number of references is replaced. The goal is to replace a page that is not very useful and is referred to not very often. The shortcoming is that a page that is just brought in may be replaced

Answer 79

The system keeps a pool of free frames. When a page fault occurs, a victim frame is chosen as before. However, the desired page is read into a free frame from the pool before the victim is written out. This procedure allows the process to restart as soon as possible without waiting for the victim page to be written out. When the victim is later written out, its frame is added to the free-frame pool.

Answer 80

A page fault would occur if a process uses all of its allocated memory space and needs another page. An active page of this process has to be replaced, which causes another page fault. Hence, each page fault replaces a frame that is being used and causes another page fault. Continuous page faults severely reduce performance. This situation is known as “thrashing.”

Answer 81

If the overall locality of all active processes is larger than the physical memory, then thrashing occurs. This situation means that active processes need to refer to a more extensive space than the main memory. Hence, one active frame has to be replaced by a new page, and this loop causes threshing.

Answer 82

Answer: In the local replacement strategy, each process selects only from its set of allocated frames. Hence, this method would result in a consistent perprocess performance but could result in underutilized memory. In the global replacement, the system selects a replacement frame from the set of all frames; one process can take a frame from another. This method’s execution time can vary greatly because information about all processes should be considered. But the overall throughput is better than local replacement, which is currently the common method

Answer 83

Reclaiming pages is the process of freeing up memory pages that are no longer being used by a program or process to make that memory available for other programs or processes. (When a program or process requests memory, the operating system allocates memory pages to that program or process. However, as the program or process runs, it may no longer need all the memory pages allocated to it. For example, if a program finishes using a particular data structure, the memory pages allocated to that data structure can be reclaimed and made available for other programs. The operating system typically keeps track of which each program or process is using memory pages. When a program or process no longer needs a particular page, the operating system can mark it as free and add it to a pool of available memory pages. These free pages can then be allocated to other programs or processes that need them.)

Answer 84

code in part B) reads one i and 128 j, which is one row of the matrix. For example, data[0][0],....,data[0][127] are read all from one page. Hence, for each row of the matrix, one page-fault occurs. Overall, the code in part B) causes 128 page-faults, one for reading each matrix row. On the other hand, the code of part A) causes one page-fault for each element of the matrix, totaling 128×128 page-faults.

Answer 85

Besides bringing in the demanded page, it also brings in the surrounding pages. For example, if page number N from the virtual space is demanded, then pages N-1 and N+1 are also brought into the main memory.

Answer 86

The list of all pages referenced in the most recent ∆ time steps.

Answer 87

The value of Δ is 10; hence, the list of pages referenced in the past ten steps, at time t1, consists of 1,2,5,6,7

Answer 88

It means that the locality of the process is very high; hence, the process needs to reference only a few pages.

Answer 89

The working set minimum is the minimum number of pages the process is guaranteed to have in memory. A process may be assigned as many pages up to its working set maximum.

Answer 90

They all use demand paging and copy-on-write. Each system also uses a variation of LRU approximation known as the clock algorithm.

Answer 91

Windows will take away frames from processes that have frames more than their “working set minimum” and give them to those that have frames less than their minimum

Answer 92

When a process starts, it has a high page fault rate because none of its needed pages are resident in the main memory. We want to avoid high page faults; hence all or most of the pages of the process are brought into the main memory before they are demanded and before generating page faults. After a while, if some of these pages are not being used, they will be replaced.

Answer 93

number of page faults that occur in a unit of time for a process is called page fault frequency. For example, suppose the number of faults that arise for a process in every 10000 references is very low. In that case, it means that the process has a high locality and is not using all of its allocated frames, and we can take away some of its unused frames. On the other hand, if the page-fault frequency is very high, the process needs more frames, and we should assign more frames to that process.