Operating Systems Key Terms and Concepts
Operating System Concepts
Definitions of key terms related to operating systems.
Memory Management
- Address Space: The range of addresses available to a computer program.
- Address Translator: A functional unit that transforms virtual addresses to real addresses.
- Base Address: An address used as the origin for calculating addresses during program execution.
- Cache Memory: A smaller, faster memory between the processor and main memory, acting as a buffer for recently used locations.
- Disk Cache: A buffer in main memory that functions as a cache of disk blocks.
- Direct Memory Access (DMA): I/O where a special module controls data exchange between main memory and an I/O device. The processor is interrupted only after the entire block has been transferred.
- Dynamic Relocation: Assigns new absolute addresses to a program during execution so it can run from a different area of main storage.
- Hit Ratio: In a two-level memory, the fraction of all memory accesses found in the faster memory (e.g., the cache).
- Logical Address: A reference to a memory location independent of the current data assignment. Translation to a physical address is required before access.
- Main Memory: Internal, program-addressable memory that can be loaded into registers for execution.
- Memory Partitioning: Subdividing storage into independent sections.
- Page: In virtual storage, a fixed-length block with a virtual address, transferred as a unit between main and secondary memory.
- Page Fault: Occurs when the page containing a referenced word is not in main memory, causing an interrupt.
- Paging: The transfer of pages between main memory and secondary memory.
- Physical Address: The absolute location of a unit of data in memory.
- Secondary Memory: Memory located outside the computer system (e.g., disk, tape).
- Virtual Address: The address of a storage location in virtual storage.
- Stack: A list where the next item to retrieve is the most recently stored (Last-In, First-Out – LIFO).
Process and Thread Management
- Asynchronous Operation: An operation that occurs without a regular time relationship to a specified event.
- Busy Waiting: Repeated execution of a loop of code while waiting for an event.
- Client: A process that requests services by sending messages to server processes.
- Concurrency: Processes or threads that occur within a common time interval, potentially sharing resources.
- Critical Section: A part of an asynchronous procedure that cannot be executed simultaneously with an associated critical section of another.
- Deadlock: An impasse where multiple processes are waiting for a resource held by another process in a similar wait state.
- Disabled Interrupt: A condition where the processor ignores interrupt request signals of a specified class.
- Enabled Interrupt: A condition where the processor will respond to interrupt request signals of a specified class.
- Execution Context (Process State): All information needed to manage and execute a process.
- Interrupt: A suspension of a process caused by an external event, allowing for resumption.
- Interrupt Handler: A routine (usually part of the OS) that handles interrupts.
- Lightweight Process (Thread): A thread.
- Message (msg): A block of information exchanged between processes for communication.
- Mutual Exclusion: Only one process in a set can access a resource or perform a function at any time.
- Preemption: Reclaiming a resource from a process before it has finished using it.
- Process: A program in execution, controlled and scheduled by the OS. Same as a task.
- Process Control Block: The manifestation of a process in an OS, containing information about its characteristics and state.
- Process Descriptor: Same as Process Control Block.
- Process Image: All ingredients of a process, including program, data, stack, and process control block.
- Process State: All information the OS needs to manage a process and the processor needs to execute it.
- Process Switch: Switching the processor from one process to another by saving and restoring process information.
- Round Robin: A scheduling algorithm where processes are activated in a fixed cyclic order.
- Starvation: A condition where a process is indefinitely delayed because other processes are always given preference.
- Synchronization: Two or more processes coordinate activities based on a condition.
- Task: Same as Process.
- Thread: An execution context that is independently scheduled but shares an address space with other threads.
Operating System Structure and Functions
- Application Programming Interface (API): A standardized library of programming tools for software developers.
- Batch Processing: Executing a set of programs such that each completes before the next starts.
- Block: (1) Contiguous records recorded as a unit. (2) A group of bits transmitted as a unit.
- Device Driver: An OS module that deals directly with a device or I/O module.
- Distributed Operating System: A common OS shared by a network of computers, supporting interprocess communication, etc.
- File: A set of related records treated as a unit.
- File Allocation Table (FAT): A table indicating the physical location on secondary storage of a file’s allocated space.
- File Management System: System software providing services for file use, including access, directory maintenance, and access control.
- First In, First Out (FIFO): A queuing technique where the next item retrieved is the one that has been in the queue the longest.
- Hash File: Records accessed according to key field values; hashing is used for location.
- Hashing: Selecting a storage location by calculating the address as a function of data content.
- Indexed Access: Accessing records through a separate index.
- Indexed Sequential Access: Accessing records through an index of keys stored in partitioned sequential files.
- Job: A set of computational steps packaged to run as a unit.
- Job Control Language (JCL): A language to express statements in a job to identify it or describe its requirements to the OS.
- Kernel: The portion of the OS with the most heavily used software, usually maintained in main memory.
- Last In, First Out (LIFO): A queuing technique where the next item retrieved is the most recently placed.
- Macrokernel: A large OS core providing a wide range of services.
- Microkernel: A small, privileged OS core providing process scheduling, memory management, and communication.
- Mode Switch: A hardware operation causing the processor to execute in a different mode (kernel or process).
- Monolithic Kernel: A large kernel containing virtually the complete OS.
- Multiprocessing: Parallel processing by two or more processors of a multiprocessor.
- Multiprocessor: A computer with two or more processors with common access to main storage.
- Multiprogramming (Multitasking): Interleaved execution of two or more programs by a single processor.
- Network Operating System: Software, supplemental to the OS, supporting common server systems in a network.
- Non-privileged State: An execution context that does not allow sensitive hardware instructions.
- Operating System: Software controlling program execution and providing services like resource allocation, scheduling, I/O control, and data management.
- Privileged Instruction: An instruction executable only in a specific mode, usually by a supervisory program.
- Real-Time System: An OS that must schedule and manage real-time tasks.
- Sequential Access: Entering or obtaining data in the same sequence as it is ordered.
- Sequential File: Records ordered according to key fields and processed sequentially.
- Server: (1) A process responding to client requests. (2) A data station providing facilities in a network.
- Shell: The portion of the OS interpreting user commands and JCL commands.
- Spooling: Using secondary memory as buffer storage to reduce processing delays.
- Symmetric Multiprocessing (SMP): Multiprocessing allowing the OS to execute on any available processor or several simultaneously.
- Time Sharing: Concurrent use of a device by multiple users.
- Time Slicing: Assigning quanta of time to two or more processes on the same processor.
- Cluster: Interconnected computers working together as a unified resource, appearing as one machine.
Security
- Encryption: Converting plain text or data into an unintelligible form via a reversible computation.
- Trojan Horse: A secret, undocumented routine embedded within a useful program.
- Trusted System: A computer and OS verifiable to implement a given security policy.
- Virus: A secret, undocumented routine embedded within a useful program.
Additional Questions and Answers
Q: What are the three popular strategies for allocating free memory blocks to processes in dynamic memory partitioning? Explain briefly how each strategy works.
A:
- First-fit: Chooses the first free block large enough for the request.
- Best-fit: Chooses the free block closest in size to the request.
- Next-fit: Chooses the first free block large enough, starting from the last allocated block.
Q: True or False? The buddy strategy always allocates memory in chunks of size power of 2 and uses a data structure based on a binary tree.
A: True.
Q: What interrupt is created when a desired page frame is not currently resident in RAM?
A: Page fault trap.
Q: How does the hardware ‘know’ that a desired page frame is not currently resident in RAM?
A: Valid bit.
Q: What precisely does it mean if the ‘dirty bit’ is set for a page frame?
A: The page frame has been modified.
Q: What is ‘good’ vs. ‘bad’ program locality?
A: ‘Good’ locality means the process executes in clustered pages. ‘Bad’ locality means the process executes in scattered pages.
Q: Explain when/how internal fragmentation may occur.
A: When fixed-sized pages are used, the last page of a program may be partially filled. This is internal fragmentation.
Q: Explain when/how external fragmentation may occur.
A: A segmentation system breaks up memory into variable-sized pieces. After allocations and deallocations, free memory may become fragmented. Even if total free memory is large enough, a large request may fail due to lack of continuity. This is external fragmentation. Compaction is needed to combine free blocks.
Q: What is a global allocation scheme?
A: Global replacement allows a process to select a replacement frame from all frames, even if allocated to another process.
Q: What is a working set model?
A: The working set model assumes processes execute in localities. The working set is the set of pages in the current locality. Each process should have enough frames for its current working set.
Q: Comparing global allocation vs. working set allocation, which would be more adversely affected by a program with ‘bad’ locality? Why?
A: Working set allocation. A program with ‘bad’ locality has poorly defined working sets, leading to many page faults.
Q: True or False? While DMA (Direct Memory Access) is taking place, the processor is free to do other things. The processor is only involved at the beginning and end of the DMA transfer.
A: True.
Q: True or False? DMA uses “cycle stealing” to transfer data on the system bus. Each time cycle stealing is used, the CPU is interrupted.
A: False. Interrupts occur only at the beginning and end of DMA transfer.
Q: What is the “largest” program that could execute on a machine with a 24-bit virtual address?
A: 2^24 bytes.
Q: What is the “largest” program that could execute on a machine with a 24-bit physical address?
A: Can’t tell. Need the size of the virtual (logical) address.
Q: The address contained in a TLB entry is (physical | logical).
A: Physical.
Q: List at least three flags contained in a PTE.
A: Valid bit, reference bit, dirty bit.
Q: Define hit-ratio in a memory management context.
A: In a two-level memory, the fraction of all memory accesses found in the faster memory (i.e., the cache).
Q: True or False? If a virtual page number x generates a miss in the TLB, then the corresponding physical page number for x is guaranteed to be found in the page table entry.
A: False. x may not be resident in RAM (still in secondary memory).
Q: True or False? It is possible that page tables are stored in virtual (secondary) memory.
A: True, when multi-level paging schemes are used.
Q: True or False? In a virtual memory system with paging, page size must be large enough to offset the high cost of page faults.
A: True.
Q: True or False? The Least Recently Used (LRU) page replacement strategy is based on the principle of spatial locality as opposed to temporal locality.
A: False. LRU is based on temporal locality.
Q: True or False? Consider “clock policy” for page replacement, a newly arrived page will not get replaced before the clock pointer makes two full rotations.
A: True. use=1 at arrival, use=0 after the first rotation. If use=0 remains true after the second rotation, it may get replaced.
Q: True or False? In a virtual memory system with paging, you can run a program whose size is larger than the size of main memory.
A: True.
Q: How does the kernel ‘know’ where on disk the desired information is for a non-resident frame?
A: If the valid bit=0, the page table entry should contain the disk address.
Q: Describe what demand paging means.
A: Loading virtual pages into memory only as they are accessed. If not in memory, a page fault occurs, and the OS swaps them in.
Q: Describe what prepaging means.
A: Prepaging brings in more consecutive pages than needed. If a virtual page x causes a page fault, virtual page (x+1) is also brought in. It is less overhead to bring in contiguous pages.
Q: If a desired page frame is not currently resident in RAM, __________________ occurs.
A: A page fault.
Q: Since a paging system uses _____________________-sized pages, ____________ fragmentation may occur.
A: Fixed size; internal.
Q: If a memory management system uses dynamic partitioning, _______________ fragmentation may occur.
A: External.
Q: _____________________ is a form of I/O in which a special module controls the exchange of data between main memory and an I/O device. During this I/O transfer, the CPU is free to do other computations.
A: DMA (Direct Memory Access).
Q: The Least Recently Used (LRU) page replacement strategy is based on the principle of __________________ as opposed to ________________________.
A: Temporal locality; spatial locality.
Q: The top four levels in the memory hierarchy, starting with the fastest, are: _____________; ______________; ___________; ___________.
A: Registers; cache memory; RAM; disk.
Q: Swapping out a piece of a process just before that piece is needed is called ________________________.
A: Thrashing.
Q: True or False? A UNIX socket is used for communication between processes running on the same machine. An Internet socket cannot be used for communication between processes running on the same machine.
A: False. Internet sockets can be used for processes on the same or different machines.
Q: True or False? If clients are connected to a server through “connect()” and “accept()” calls and the server calls “listen(soc, 2)” before “accept()”, then at most 2 clients can get connected to the server at any time.
A: False. listen() determines the size of the wait queue, not the maximum number of connected clients.
Q: True or False? In RAID (Redundant Array of Independent Disks) level 1, every disk in the array has a mirror disk containing the same data.
A: True.
Q: True or False? In client/server architectures, the OS and platforms in the client and server machines must be the same.
A: False.
Q: True or False? In client/server applications, there is heavy emphasis on providing a user-friendly Graphical User Interface (GUI) on the client side.
A: True.
Q: True or False? In client/server applications, fat client models cannot take advantage of desktop power and therefore can only serve a small number of clients.
A: False.
Q: True or False? First-Come-First-Served (FCFS) process scheduling favors I/O-bound processes.
A: False.
Q: True or False? Most antivirus software is based on program emulation and virus signature analysis.
A: True.
Q: True or False? RAID 2 (Redundant Array of Independent Disks with level 2) is designed to provide error detection/correction.
A: True.
Q: True or False? User Datagram Protocol (UDP) provides unduplicated and reliable packet delivery.
A: False.
Q: True or False? Two periodic real-time processes A and B have periods T_a = 0.2 ms and T_b = 0.5 ms, respectively. Their execution times are C_a = 10 microsec and C_b = 40 microsec, respectively. If rate monotonic scheduling is used, A has higher priority than B.
A: True.
Q: True or False? The following I/O devices are sorted correctly in decreasing order according to the typical data rates they can sustain: Gigabit Ethernet, FireWire 800, laser printer, hard disk, keyboard, and modem.
A: False.
Q: True or False? DMA uses “cycle stealing” to transfer data on the system bus. Each time cycle stealing is used, the CPU is interrupted.
A: False.
Q: Explain what the following C calls do both when the call is successful and when it is unsuccessful.
- socket(AF_INET, SOCK_STREAM, 0)
- bind(sd, (struct sockaddr*)&server_addr, sizeof(server_addr))
- socket(AF_INET, SOCK_DGRAM, 0)
- accept(sd, (struct sockaddr*)&client_addr, &client_len)
A:
- Creates an Internet stream (TCP) socket and returns the socket descriptor. If it fails, it returns -1.
- Binds the definition of a socket (socket descriptor) to a port number. If it fails, it returns -1.
- Creates an Internet datagram (UDP) socket and returns the socket descriptor. If it fails, it returns -1.
- Blocks execution until a client connection is received. When that happens, it returns a descriptor for the connection. If it fails, it returns -1.
Q: Which one of the following is not among the 7-layers defined for the ISO Open Systems Interconnect (OSI) model?
(a) Application (b) Routing (c) Transport (d) Data link (e) Physical
A: (b)
Q: Which of the following are among the direct goals of process scheduling algorithms (circle all that apply):
a. Improve response time b. Minimize interrupts c. Improve throughput d. Minimize page faults e. Improve turnaround time for jobs f. Increase memory efficiency
A: a, c, e
Q: When we compare clusters with SMP (Symmetric Multiprocessors), which of the following are true (circle all that apply)?
a. Clusters are easier to manage and configure b. Clusters take up less space and draw less power c. Clusters are better for incremental and absolute scalability d. Clusters are superior in terms of availability e. Clusters have superior price/performance
A: c, d, e
Q: Which of the following malicious software need a host program to operate? (circle all that apply)
a. Logic bomb b. Worm c. Zombie (bots) d. Trojan horse e. Virus
A: a, d, e
Q: Which of the following scheduling policies may cause starvation for certain jobs? (circle all that apply)
a. First Come First Serve (FCFS) b. Feedback c. Round Robin d. Shortest Process Next (SPN) e. Shortest Remaining Time Next (SRT)
A: b, d, e
Q: Which of the following features are specific to real-time OS? (circle all that apply)
a. Small size b. Fast context switch c. Less user control d. Nondeterministic delays e. Fail-safe operation
A: a, b, e
Q: In which one of the following OSI layers are Transmission Control Protocol (TCP) and User Datagram Protocol (UDP) defined and implemented?
a. Application b. Physical c. Transport d. Data link e. Session
A: c
Q: What does an Internet Protocol do?
A: 1. Provides a naming scheme using a uniform format for host addresses. 2. Provides a delivery mechanism by defining a standard packet format.
Q: True or False? Sockets are bidirectional communication ports in UNIX. Once a socket is created, it can be bound to an Internet port using the socket() call.
A: False. The first statement is true, but the second is false. Sockets are bound to an Internet port using the bind() call.
Q: True or False? There is only one Internet port in each networked host.
A: False. There are many Internet ports in each host; some are reserved by the OS.
Q: True or False? The UNIX call listen(soc, n) allows only n clients to be connected to a socket at any time.
A: False. n specifies the length of the wait queue for waiting clients.
Q: True or False? The two lowest layers in the 7-layer ISO Open Systems Interconnect (OSI) model are the physical and data link layers, and their primary function is to implement the TCP/IP protocol.
A: False. The first part is true, but the second part is false because the transport layer (4th layer from the bottom) implements TCP/IP.
Q: What are the possible goals that any scheduling policy might try to accomplish (list at least 3)?
A: To improve: – Response time – Turnaround time (TAT) – Throughput – Processor efficiency
Q: True or False? The long-term scheduler controls the degree of multiprogramming.
A: True.
Q: True or False? Among the three scheduling disciplines (long-term, medium-term, and short-term), the long-term scheduler executes most frequently.
A: False. The short-term scheduler (dispatcher) executes most frequently.
Q: True or False? Among the short-term scheduling policies, the feedback policy penalizes jobs that have been running longer.
A: True.
Q: Which decisions are made by long-term, medium-term, and short-term scheduling? Be brief.
A:
- Long-term scheduling: Determines which programs are admitted for processing, controlling the degree of multiprogramming.
- Medium-term scheduling: Determines which programs will be resident. Part of the swapping function. Swapping-in is based on managing multiprogramming.
- Short-term scheduling: Determines which program will be executed on the CPU next. Known as the dispatcher, it executes most frequently.
Q: Name three things that are essential to launch a “‘bots” attack:
A: (1) Attack software (2) A large number of vulnerable machines (3) Locating these machines (scanning or fingerprinting)
Q: The two lowest layers in the 7-layer ISO Open Systems Interconnect (OSI) model are ______________ & ____________ layers & their primary function is to provide ______________ & ____________.
A: Physical; data link; signaling technology; frame management.
Q: Two transport protocols, __________________________________ & _________________________, are defined & handled at the transport layer.
A: Transmission Control Protocol (TCP); User Datagram Protocol (UDP)
Miscellaneous Questions Related to the Video: Triumph of the Nerds
Q: Fill in the blanks.
- ____________________ & _____________________ are generally credited with the invention of C/UNIX.
A: Dennis Ritchie, Ken Thompson
- ____________________ & _____________________ started Microsoft in 19______.
A: Bill Gates, Paul Allen, 1975.
- What corp./laboratory may fairly take credit for inventions like the mouse, windows, pull-down menus etc.?
A: Xerox/PARC
- ____________________ & ______________________ co-founded Apple. ________________ then started NeXT, & was the CEO of Pixar.
A: Steve Jobs, Steve Wozniak, Steve Jobs
- MS/DOS was 90% derived from a predecessor product named ________ which was written by _______________ & owned by _________________. Which in turn had been cloned from ____________ written by _______________________.
A: QDOS, Tim Patterson, Seattle Computer Products, CP/M, Gary Kildall
Q: Answer the following questions.
- What did Steve Jobs see while visiting PARC that inspired him to build a different kind of computer?
A: GUI
What did he see that he completely ignored?
A: Object-oriented programming & e-mail
What was the first computer that he built based on this inspiration (that flopped)?
A: Lisa
What was the second one that didn’t flop?
A; Macintosh
- What ‘product’ got Microsoft into the microcomputer software business?
A: BASIC language interpreter
8.what lucky event got microsoft into the operating system market?
gary kildall didn’t eagerly pursue ibm when they requested a new
os.his wife & attorney would not sign a nondisclosure
agreement.bill gates of microsoft saw this as an opportunity &
jumped in.
9.what company purchased next & their os nextstep?what year?
a.apple,in 1996
10.what is a ‘killer application’?
a: software that’s so useful that people will buy computers jst 2 run it.
11.what was the killer app 4 the apple ii?
a: visicalc
12.what was the killer app 4 the ibm pc?
a: lotus 1-2-3
13.what was the killer app 4 the apple macintosh?
a: wysiwyg – what U see is what U get —–> desktop publishing
14.why didn’t ibm create their own os 4 their 1st pc?
a: wanted 2 manufacture & market it very fast;within 1-year
“….1ce ibm decided 2 do a personal computer & 2 do it in a year –
they couldn’t really design anything,they jst had 2 slap it
together,so that’s what they did …”
15.who ‘should have’ sold ibm their operating system 4 the 1st ibm pc?
a: gary kildall of digital research
16.what was the 1 part of the 1st ibm pc that was proprietary (that
compaq had 2 later reverse engineer)?
a: rom-bios
17.why did ibm decide 2 build the pc using ‘open architecture’?
2 save time,instead of building a computer from scratch,ibm
initially decided 2 buy pc comp1nts off the shelf & assemble
them — in ibm terms,this was called an ‘open architecture’.
ibm made some changes 2 this initial decision.
what was the almost immediate result of ibm having made that decision?
ibm had 2 buy the os & other software from other companies as well.
18.what was ibm’s motivation 4 designing/building ps-2/os-2?
ibm planned 2 steal the market from gates with a brand new os
called os/2.
19.what person ______________ what company ________________ built the 1st
commercially available personal computer in 1975?
a: ed roberts;mits
20.gordon moore is 1 of the _______________ founders.
a: intel
21.world’s 1st personal computer,________________,was designed by
______________________ & was introduced in 19___
a: altair 8800;ed roberts;1975
22.the 1st mass market pc company is _____________.
a: apple