Midterm Study

Question 1

Draw Von Neumann’s architecture of a computer.

Answer 1

Question 2

What are the five main categories of modern computer systems?

Answer 2

Personal Mobile Device (PMD)

Desktop Computing

Servers

Clusters/Warehouse Scale Computers

Embedded Computers

Question 3

What is the primary task of an “operating system?”

Answer 3

Answer 1: A program that acts as an intermediary between a user of a computer and the computer hardware.

Answer 2: OS is a resource allocator, which manages all resources, decides between conflicting requests for efficient and fair resource use, and controls programs within allocated space.

Question 4

What are the two main characteristics of an OS?

Answer 4

Efficiency and convenience.

Efficiency means that the OS can manage multiple processes and allocate memory to these processes fairly and efficiently. For example, if one process is trying to hug a large number of frames, the other processes should not be denied active frames. If a process is not using its frame or CPU assets, that process should be deactivated. In servers, efficiency is of main importance.

Convenience is a factor that a user of the system expects from the OS. Allowing a user to access programs and applications easily is an example. In mobile devices, convenience is a major factor.

Question 5

For networked distributed computing, the networks are categorized into four groups in terms of the distance between members. What are these four types of networks?

Answer 5

LAN, WAN, MAN, PAN

Question 6

Computing environments, in terms of the role of connected members of a network, are divided into two types. What are these two types of networks?

Answer 6

1. Client-server
2. Peer-to-peer

Question 7

What is the difference between “emulation” and “virtualization?”

Answer 7

Emulation: Emulation is used when the source CPU type (physically present) is different from the target CPU type (the CPU that a program is compiled for). For example, Apple desktops switched from IBM CPU to Intel CPU, and old software used Rosetta to run on emulated IBM CPU.

Virtualization: Virtualization allows a guest OS to run as an application on a host OS.

Question 8

What is the difference between “full virtualization” and “para-virtualization?”

Answer 8

In full virtualization, the guest is an original OS and wants to manage the memory, perform protection, etc.

In para-virtualization, guest OS is designed to run as a guest in a virtual environment and is aware of other operating systems, and knows its limitations.

Question 9

What are the three types of “cloud computing?”

Answer 9

Private, public, hybrid

Question 10

What are the three advantages of a “multiprocessor system” over a single processor?

Answer 10

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

Question 11

What is the difference between “symmetric” and “asymmetric” multiprocessors?

Answer 11

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.

Question 12

What are the five activities of “process management?”

Answer 12

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 mechanims for deadlock handling

Question 13

What is the difference between “program” and “process”?

Answer 13

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

Question 14

What is a memory unit exposed to?

Answer 14

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

Question 15

How long does one memory access take?

Answer 15

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

Question 16

How long does one register access take?

Answer 16

It takes one clock cycle (or less)

Question 17

What do we mean by “throughput of memory”?

Answer 17

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

Question 18

What does “memory management” mean?

Answer 18

A system that determines what is 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)

Question 19

What does memory management do?

Answer 19

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. 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. It allocates and deallocates the memory space as needed. It means that the table should be updated as the processes come in or go out.

Question 20

What is meant by the performance difference between DRAM and CPU?

Answer 20

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

Question 21

What is “memory hierarchy”?

Answer 21

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

Question 22

What is “locality of reference”?

Answer 22

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

Question 23

How could we overcome the performance difference?

Answer 23

By using memory hierarchy.

Question 24

What is the effect of “low” locality of reference?

Answer 24

Low locality causes a high miss rate which forces the memory management to refer to slower parts of the hierarchy.

Question 25

Suppose reading one word from the main memory takes 50 clocks, and reading one block of words from memory would take 100 clocks. Also, assume that reading one word from cache would take 2clocks. What should be the maximum cache “miss rate” for this memory system to worth having the cache rather than directly accessing the main memory?

Answer 25

50>2+miss_rate*100. miss_rate<0.48

Question 26

What are the primary and secondary memory layers?

Answer 26

Question 27

What are the four categories of memories in terms of “access-type”?

Answer 27

RAM, SAM, DASD, CAM

Question 28

What is the “inclusion principle” in the context of the memory hierarchy?

Answer 28

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

Question 29

What are the four policies or questions in the management of a memory hierarchy?

Answer 29

1. Placement Policy
2. Identification policy
3. Replacement policy
4. Update policy

Question 30

What is “mapping” in the context of memory management?

Answer 30

Conversion of virtual addresses to physical addresses is called mapping.

Question 31

What is “address binding”?

Answer 31

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

Question 32

Explain why load-time binding is not “dynamically relocatable” and why execution-time binding is dynamically relocatable

Answer 32

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. Dynamic- binding means locations are determined during execution.

Question 33

What are “logical” and “physical” addresses?

Answer 33

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

Question 34

hat is the job of the memory management unit (MMU)?

Answer 34

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

Question 35

What is “dynamic relocation”?

Answer 35

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

Question 36

What are the minimum hardware requirements of an MMU for a dynamic relocation?

Answer 36

A relocation register.

Question 37

Which type of program benefits most from dynamic relocation?

Answer 37

In some programs, a significant portion of the code is used for rare cases, 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.

Question 38

What is a “stub”?

Answer 38

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.

Question 39

What is the “Contiguous allocation” of memory?

Answer 39

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

Question 40

Why is segmentation considered as “Contiguous” and paging is considered as “non-Contiguous”?

Answer 40

Segmentation allocates one piece of memory, called a segment, to one program. In paging, different parts of the memory, called pages, could contain a part of a program. These pages could be non- contiguous.

Question 41

What are the elements of the two-tuple that a segment is referred by?

Answer 41

segment number and offset.

Question 42

What are the minimum hardware requirements in a multiprogramming system to ensure each program only accesses its own memory space? Draw a simple block diagram for this protection system.

Answer 42

Base register and limit register are needed.

Question 43

a) How could we define efficiency in a “variable partitioning” memory system?
b) What happens when a new process arrives?
c) What happens when the process exists?
d) What kind of information does the OS maintain in such a system?

Answer 43

a) The percentage of occupied memory, when there is no room for a new process, is the efficiency. The higher this percentage, the lower is the size of 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. Adjacent accessible partitions are combined.
d) OS maintains information about: allocated partitions, and free partitions (holes)

Question 44

What strategies are possible for “placement policy” in a “dynamic allocation” memory system?

Answer 44

First fit, best fit, worst fit.

Question 45

What are the two types of memory fragmentation?

Answer 45

internal fragmentation, external fragmentation.

Question 46

Which type of fragmentation occurs in the Contiguous allocation system?

Answer 46

External fragmentation occurs in between segments.

Question 47

True or false?: The 50-percent rule states that 50% of memory is lost to external fragmentation when the first-fit policy is used. Explain your answer.

Answer 47

False. 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.

Question 48

What is a solution for memory fragmentation? What are the prerequisites of such a remedy, and what are the problems?

Answer 48

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

Question 49

How does the “paging” system partition a program? Does it have to bring the whole program into the memory?

Answer 49

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 they are needed.

Question 50

What is the difference between a “frame” and a “page”?

Answer 50

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.

Question 51

What is the job of a “page table”?

Answer 51

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

Question 52

Assume that the logical address is 24 bits and the physical memory is 1MB. Also, assume that each page or frame is 4KB.

a) Show how the logical and physical addresses are partitioned.
b) What is the size of the page table?
c) Assume the logical address is ABCDEF, the content of the page table in line DEF is AB, and in line ABC is F5. Where in the physical memory, this logical address is mapped?

Answer 52

a) Picture
- 4KB=2^12 -> 12 bits

p=12, d=12, f=8

b) Page table has 2^12 lines
c) Virtual address ABCDEF is at address F5DEF.

Question 53

Imagine that we have fixed block sizes of size 2048 bytes. Also, imagine that the process size is P. Write a C code that, for 10000 times, randomly generates an integer P, between 1 and 20000. Then for each value of P, determine the amount of internal fragmentation and calculate the mean value of that. Copy/paste your code in your solution file. Also, report the averagevalueofinternalfragmentation.

Answer 53

include

int main()

int c, p, frag, frag_avg;

int frag_sum=0;

int page=2048;

printf(“10000 random numbers in [1,30000]\n”);

srand(time(0));

for (c = 1; c <= 10000; c++) {

p = rand() % 30000 + 1;

if (p

else { frag= p%page;}

frag_sum=frag_sum + frag;

frag=0;

} }

frag_avg= frag_sum/10000;

printf(“average fragmentation is %d\n”,frag_avg);

r

Question 54

Accessing the page table may have considerable delays. What is a solution to reduce the average delay of the page address mapping?

Answer 54

Use of TLB.

Question 55

Suppose the logical address is 32 bits. The physical memory is 16MB. Pages are 4KB. There is a TLB with 64 lines of associative memory with an access time of 0.5 cycles. The access time of the page table is one cycle. The miss rate of TLB is ten percent.

a) How big is the page table?
b) What is the average access time of this system?
c) Now consider the content of the page table and TLB as shown below. Suppose logical address D00EF123 is issued, which cannot be found in the TLB. Where in the physical memory is this address mapped? Where will the logical address 12345F05 be mapped in the main memory?

Answer 55

a) Page table has 2^20 lines. (32bits-12bits)= bits for virtual page #
b) EAT= HR*(Access Time) + MR*(1)= 0.9*0.5+0.1*1=0.55cycles
c) D000EF is the page # which is mapped at frame # 56F. Hence, the physical address is 56F123. 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.

Question 56

What is the purpose of using “valid bit” in the page memory table?

Answer 56

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. When the bit is set to invalid, the page is not in the process’s logical address space. Illegal addresses are trapped by the use of the valid-invalid bit. The operating system sets this bit for each page to allow or disallow access to the page.

Question 57

What is a “reentrant” page? Usually, reentrant pages belong to some specific processes. Name two examples of such processes.

Answer 57

The Reentrant code is non-self-modifying: it never changes during execution. Thus, two or more processes can execute the same code at the same time. Each process has its own copy of registers and data storage to hold the data for the process’s 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.

Question 58

Name three strategies that are used to reduce the size of page tables when the logical address is large.

Answer 58

Hierarchical Paging, Hashed Page Tables, Inverted Page Tables

Question 59

Suppose that the logical address is 32 bits and the page offset is 12 bits. Show an example of a hierarchical page address.

Answer 59

Question 60

Why a hierarchical page addressing is not possible for 64-bit logical addressing? What are the two alternative methods?

Answer 60

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

Question 61

Explain the following diagram. What are p, q, s, r, and d? Suppose the 64-bit logical address of F1234567890ABCDE is mapped into the physical address of 4FFCDE. What are the values of p, d, and r? Also, give an example of the value of q.

Answer 61

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

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.

Question 62

a) What is an “inverted page table?”
b) How can we limit the search process?

Answer 62

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.

Question 63

The 64-bit Sparc Solaris uses two hash tables. What are these two tables? What is “page walk” in the memory mapping process of this system?

Answer 63

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.

Question 64

Some operating systems occasionally deactivate “swapping.” What is the purpose, and what are the occasions?

Answer 64

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.

Question 65

Suppose that a process takes 200MB of the main memory. This process has to be swapped by sending it to the backing memory and bringing a new process, of the same size, into the main memory. The transfer rate is 150MB/sec. How long does this context switch will take?

Answer 65

200MB + 200MB=400 MB

=>

(400 MB)/(150MB/sec)

= 2.67 sec

Question 66

What is a “pending I/O” during process swapping? Explain “double buffering” that is used to remedy pending I/O.

Answer 66

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.

Question 67

What is the maximum size of a segment in an IA-32 system? What are the differences between LDT and GDT? The logical addresses in IA-32 systems consist of two parts. What are these two parts called, and what are their purposes?

Answer 67

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, 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 locationofthebytewithinthesegmentinquestion. Anoffsetof32bitmeans that each segment could be as large as 4GB.

Question 68

The following diagram shows the addressing system of the IA-32. What is the difference between addressing a 4KB page and a 4MB page?

Answer 68

If 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. There is a bit in the content of the page directory line that indicates if the page size is 4MB or 4KB. For 4MB pages, the page directory provides a 28-bit start address which 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, and 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.

Question 69

The addressing method in the ARM architecture is shown below. Explain how this architecture works for 4KB, 16KB, 1MB, and 16MB pages.

Answer 69

If 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 that indicate 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 points 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.