Midterm Flashcards
Draw Von Neumann’s architecture of a computer.
What are the five main categories of modern computer systems?
Personal Mobile Device (PMD)
Desktop Computing
Servers
Clusters / Warehouse Scale Computers
Embedded Computers
What is the primary task of an “operating system?”
Answer1: A program that
acts as an intermediary between a user of a computer and the computer
hardware. Or Answer2: 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.
What are the two main characteristics of an OS?
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 system user expects from the OS. Allowing a user
to access programs and applications easily is an example. In mobile devices,
convenience is a major factor.
Explain the role of the OS as the resource manager
One of the main
tasks of an OS is to optimize the use of all computational resources to ensure good
overall performance while satisfying the requirements of specific applications,
including guaranteeing acceptable response times for interactive processes, meeting
deadlines of time-critical tasks, and allowing safe communication among different
tasks. A program typically alternates between phases of input, computation, and
output. Consequently, the CPU is underutilized during the I/O phases, while the I/O
devices are idle during the compute phase. The overall performance of all applications
can be improved by using concurrency. The OS tries to keep the CPU, main memory,
and all storage and I/O devices busy at all times by overlapping independent
operations whenever possible.
What is “multiprogramming?
Multiprogramming is a technique that keeps several
programs active in the main memory and switches execution among the different programs
to maximize the use of the CPU and other resources. Whenever a program enters an I/Obound phase where little CPU time is needed, other programs can resume and utilize the CPU
in the meantime. Similarly, whenever a device completes an operation, the OS activates
computations that can utilize the now available device.
What is time-sharing?
Time-sharing (multitasking) is an extension of
multiprogramming where the CPU is switched periodically among all active computations to
guarantee acceptable response times to each user. Time-sharing employs the concept of
virtualization by creating the illusion of having a separate virtual CPU for each computation
Situation 1 is a sequential system. First, program A is executed, and then program B.
Situation 2 is a multiprogramming case. Finally, situation 3 is time-sharing, where the
switching between programs A and B is done very quickly, and we are showing them as
running in parallel.
Multiprogramming generally improves CPU utilization and throughput. (True or False?)
True: Multiprogramming overlaps phases of computation and I/O from different
computations to better utilize the CPU and other resources, which improves overall
performance
The main objective of time-sharing is to improve resource utilization. (True or False?)
False: Resource utilization is improved by multiprogramming, which overlaps CPUbound and I/O-bound computations. On the other hand, Time-sharing only switches the
CPU among different computations to create the illusion of simultaneous execution, which
generally does not improve resource utilization beyond simple multiprogramming
Multiprogramming and time-sharing are not used together. (True or False?)
To achieve the best CPU utilization, _____ computations should run
simultaneously.
a) 2 b) more than 2 c) all available processes
B
Using more than two computations increases CPU utilization
but, at the same time, uses more memory and other resources. A careful
balance must be found to minimize overhead while still increasing overall
performance.
The use of time-sharing will _____.
a) speed up all computations
b) guarantee a reasonable response to each computation.
c) improve resource utilization
B
No computation can monopolize the CPU indefinitely
What is the OS kernel?
The kernel of an OS is the minimal set of
functions necessary to manage the system resources safely and efficiently. The
kernel typically provides essential services for memory and device management,
creating and managing computations, and communication among the different
concurrent activities within the system.
What are privileged instructions?
The instruction set provided
by the CPU is divided into two sets of privileged and non-privileged to deal with
security issues. A privileged instruction performs critical operations that access
I/O devices and the CPU’s status and control registers. Thus only the OS kernel is
allowed to execute privileged instructions.
What are the two modes that the CPU operates?
The CPU
operates in two different modes, indicated by a particular mode bit, to guarantee
that no programs outside the trusted kernel can use privileged instructions. Kernel
mode is the CPU state where both privileged and non-privileged instructions may
be used. User mode is the CPU state where only non-privileged instructions may be
used. Any attempt to execute a privileged instruction in user mode automatically
transfers control to the kernel.
What do interrupts and traps have in common? What are the differences between the two concepts?
Traps and interrupts both suspend the execution of the current
instruction sequence and temporarily divert control to a dedicated area within the OS kernel.
An external event causes an interrupt. Ex: The completion of an I/O operation or a timeout
signal from a clock. Interrupts are asynchronous to the current execution in that the
interruption may occur unpredictably between any two instructions. A trap is a particular case
of an interrupt caused by an event internal to the current execution. Ex: The execution of a
privileged instruction or an arithmetic overflow. Traps are synchronous to the current
execution in that the currently executing instruction causes the interruption. The interruption
can be unintentional, as in the case of an error, or intentional, as in the case of a supervisor call.
What is a process, and what is a process’s PCB?
A process is an instance of a program
being executed by an OS. For example, when a user opens a new application like a web browser
or text editor, the OS creates a new process. The OS itself is organized as a collection of
processes. The OS keeps track of each process using a process control block (PCB). PCB is a
data structure that holds information for a process, including the current instruction address,
the execution stack, the set of resources used by the process, and the program being executed
What is the content of the PCB of a process?
PCB contains a list of registers
of the process, program counter, memory management information, process id,
process state, and a list of files that are opened by the process.
A newly created process starts in the ready state. When the OS selects
the process for execution, it goes to the running state. When the OS interrupts
the process, for example, to let some other processes use the CPU, its state
changes to ready. When a process requests a currently unavailable resource,
such as a file already opened by another user or some input data, the process’s
state changes to “blocked.” When some other process releases the resource or
generates the data needed by the blocked process, the OS moves the blocked
process to ready.
The networks are categorized into four groups for networked distributed
computing in terms of the distance between members. What are these four types
of networks
LAN, WAN, MAN, PAN
In terms of the role of connected network members, computing environments are divided into two types. What are these two types of networks?
1) client-server, 2) peer-to-peer.
What is the difference between “emulation” and “virtualization?”
A. Emulation is used when the source CPU type (physically present) differs
from the target CPU type (the CPU for which 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.
B. Virtualization allows a guest OS to run as an application on a host OS.
What is the difference between “full virtualization” and “paravirtualization?
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, is aware of other operating systems, and knows its
limitations. Para-virtualization requires the guest operating system to be modified
to use the hypervisor’s APIs, making it more efficient than full virtualization in
terms of CPU utilization and memory access. Para-virtualization is best suited for
situations where a high level of performance is required, such as in highperformance computing or data-intensive workloads.
What are the three types of services that cloud environments offer?
SaaS (software as a service), PaaS (platform as a service), and IaaS
(infrastructure as a service).
What are the three types of “cloud computing?”
Private, public,
hybrid
What are the three advantages of a “multiprocessor system” over a single processor?
1- Increased throughput,
2- Lower costthan using a collection of single processors,
3- Reliability is higher, and the system is more fault-tolerant
What is the difference between “symmetric” and “asymmetric” multiprocessors?
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.
What are the five activities of “process management?”
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
What is the difference between “program” and “process”?
A program is a collection of instructions and is a passive entity. A process is a
program in execution and is an active entity.
What is a memory unit exposed to?
1- A stream of addresses + read requests
2- A stream of addresses + data and write requests
For a cache system, how long does one memory access take?
It takes many CPU cycles. AMAT= cache-hit-time+ miss-rate*miss-penalty
How long does one register access take?
It takes one clock cycle (or less)
What do we mean by “throughput of memory”?
Number of bytes accessed in a time unit (Bytes/sec)
What does “memory management” mean?
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)
What does memory management do?
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
What is meant by the performance difference (gap) between DRAM and
CPU?
The throughput of DRAM is much lower than what the CPU
requires.
What is “memory hierarchy”?
Creating a pyramid with slow, cheap, and large memory at the bottom and placing
fast, expensive, and small memories at the top.
What is the “locality of reference”
When a reference is made
to memory, the same location, or locations near that, will be referenced soon.
How could we overcome the performance difference
By using
memory hierarchy
What is the effect of a “low” locality of reference?
Low locality
causes a high miss rate, forcing memory management to refer to slower parts of
the hierarchy
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 the cache would take 2 clock cycles. What should be
the maximum cache “miss rate” for this memory system to be worth having the
cache rather than directly accessing the main memory
Answer: 50> 2
+miss_rate*100. miss_rate should be less than 0.48
What are the primary and secondary memory layers?
What are the four categories of memories in terms of “access type”?
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.
What is the “inclusion principle” in the memory hierarchy?
The
content of layer 𝑖𝑖 of the hierarchy has to exist in layer 𝑖𝑖 + 1.
What are the four policies or questions in managing a memory hierarchy?
1- placement policy, 2- identification policy, 3- replacement policy, 4- update policy.
What is “mapping” in the context of memory management?
conversion of virtual addresses to physical addresses is called mapping.
What is “address binding”?
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.
Explain why load-time binding is not “dynamically relocatable” and why execution-time binding is dynamically relocatable
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.
What are “logical” and “physical” addresses? Answer:
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.
What is the job of the memory management unit (MMU)?
The run-time mapping from virtual to physical addresses is performed by
hardware called the memory-management unit (MMU).
What is “dynamic relocation”?
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
What are the minimum hardware requirements in a multiprogramming
system to ensure that each program only accesses its memory space? Draw
a simple block diagram for this protection system.
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 is this
logical address mapped?
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?
d) Convert logical address FEDC05F2 to a physical address.
a) The page table has 2^20 lines. (32bits-12bits)= bits for virtual page #
b) EAT= 0.90.5+ 0.11=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.
We have 32-bit virtual addresses and 24-bit physical addresses. Assume that we have 4KB pages. Based on the following diagram’s content,
where is the virtual address ABCDEF00 mapped? Where do we map
F00BC000? Where do we map 12356FFF?
ABCDEF00 is mapped to 567F00. Virtual address F00BC000 is
mapped to 345000. Logical address 12356FFF is not yet mapped to a
physical address.
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.
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.
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 will this context switch take?
The following diagram shows the addressing system of the IA-32. What
is the difference between addressing a 4KB page and a 4MB page
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.
The addressing method in the ARM architecture is shown below. Explain
how this architecture works for 4KB, 16KB, 1MB, and 16MB pages.
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.
What are the contents of the entries on the page table below?
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.)
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.
For a demand paging system, assume that the page fault rate is 𝒑𝒑.
What is Effective Access Time (EAT) for such a system?
For a demand paging system, assume the following. The main
memory access time is 300 ns, and the access time to the hard disk is 11 ms
(including all the overheads and swap in and out time.) We want the
effective access time for such a system to be only 20% larger than the main
memory access time. What should be the maximum page fault rate?
Suppose that we have the following string of references:
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1.
Further, assume that we only have three frames in the main memory. We want
to use a FIFO strategy for page replacement. Fill out the frames in the image
below with the appropriate page number.
For the following string of references, fill out the image with
appropriate page numbers based on Belady’s Optimal replacement method:
For the following string of references, fill out the image with
appropriate page numbers based on LRU (least recently used) replacement
method:
Suppose we are using a stack to implement the LRU replacement
method. Consider the string of references shown below. Suppose that we
know the content of the stack after point a. What will be the content of the
stack after point b?
Suppose that the main memory consists of 4 frames. The following
sequence of frames has been referenced: 0,1,2,3,2,1,0,3,2,3. A page fault
occurs at the end of this sequence, and one of the frames must be replaced
using the “clock” strategy. Which frame is replaced
Let us assume we are using “proportional allocation” for two processes. We
have 62 frames available. One of the processes has 10 pages, and the other
127 pages. How many frames are allocated to each one?
Let us assume that each row of the following matrix is stored on
one page. Which of the two pieces of code would cause fewer page faults
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.
Consider the following figure, which shows a sequence of page
references. Why is the working set, at time t1, consisting of 1,2,5,6,7?
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
