Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
31 Cards in this Set
- Front
- Back
- 3rd side (hint)
|
What is the Halting Problem? |
Given a problem P that requires exactly one string input, and a string x, determine whether P halts on input x. does-halt(P,x) = { true, if P(x) halts false, if P(x) runs forever} |
does- halt always halts |
|
|
Solve Problem 3.1 in book |
(cons 'B 'C) (cons 'A (cons 'B 'C) ) (cons (cons 'A (cons 'B 'C) ) (cons 'B 'C) ) |
|
|
|
Also Problem 3.1 car -> 'A cdr -> 'B 'C |
lambda(x) (cons ( cons 'A x ) x ) (cons 'B 'C) |
|
|
|
What does it mean to be Turing Complete? |
All standard general-purpose programming languages give us the same class of computable functions |
|
|
|
Define Partiality |
Recursively defined functions may be partial functions. They are not always total functions. A func may be partial bc a basic operation is not defined on some argument or because a computation doe not terminate. |
|
|
|
Define Computability |
Some functions are computable and others are not. Programming langs can be used to define computable functions; we cannot write programs for funcs that are not computable in principle. |
|
|
|
Define Undecidability |
Many important properties of programs cannot be determined by any computable func. In particular, the halting problem is undecidable |
|
|
|
Lexer / Parser |
* Combines sequence of characters to lexems ( REGEX ) * Derives a sentence from a sequence of tokens ( GRAMMAR ) |
|
|
|
4 Main elements of a computer |
Processor, Main Memory, I/O modules, System Bus |
|
|
|
What is a Processor? |
Controls the operations of the computer and performs its data processing functions. CPU (central processing unit ) when there is only 1 |
|
|
|
What is Main Memory? |
Stores data and programs. Typically volatile; i.e. when the computer is shut down the contents are lost. Often referred to as Real Memory or Primary Memory |
|
|
|
What are I/O modules? |
move data between the computer and its external environment. |
|
|
|
What is the System Bus? |
Provides for communication among processors, main memory, and I/O modules |
|
|
|
What is an interrupt? |
a signal that tells the OS to stop its current operations and decide the best course of action next |
|
|
|
4 classes of Interrupts |
Program, Timer, I/O, Hardware Failure |
|
|
|
Difference between simple paging & Virtual Memory paging |
|
|
|
|
Explain Thrashing |
|
|
|
|
Internal vs External Fragmentation |
|
|
|
|
3 objectives to OS Design |
Convenience, Efficiency, Ability to Evolve |
|
|
|
What is the kernel of the OS? |
the Nucleus which contains the most frequently used functions in the OS and, at a given time, other portions of the OS currently in use |
|
|
|
Multiprogramming |
allowing memory to be able to hold 3, 4 or more processes at a time switching between them |
also known as multitasking |
|
|
What is a process? |
a program in execution, an instance of a running program, the entity that can be assigned to/executed on a processor |
|
|
|
4 main causes of OS errors |
Improper synchronization, failed mutual exclusion, nondeterminate program operation, Deadlocks |
|
|
|
5 Memory Management OS responsibilities |
Process isolation, Automatic allocation and management, support of modular programming, protection and access control, long-term storage |
|
|
|
difference between a real address & a virtual address |
Virtual address consists of a page number and an offset within that page; Real address is the physical address in main memory |
Specifically with regards to Operating systems |
|
|
what is the round robin scheduling technique? |
to give each process in the queue some time in turn; a circular queue |
|
|
|
monolithic kernel vs microkernel |
one large kernel that was prominent until recently- provided most of the OS functionality; a small kernel and only assigns a few essential functions at a time to the kernel |
|
|
|
What is multithreading? |
a technique in which a process, executing an application, is divided into threads that can run concurrently |
|
|
|
Key design issues of the SMP operating system |
Simultaneous concurrent processes or threads, scheduling, synchronization, memory management, reliability & fault tolerance |
SMP - symmetric multiprocessing |
|
|
What is an instruction trace? |
the sequence of instructions that execute for that process |
|
|
|
Different ways a program will be uniquely characterized |
Identifier, State, Priority, Program Counter (PC), Memory pointers, Context data, I/O status information, Accounting information |
|
