Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CMPSC 473 > Exam 1 (up to Scheduling) > Flashcards

Exam 1 (up to Scheduling) Flashcards

1
Q

What is the mode of communication between the CPU and Main Memory?

A

Memory Bus (DDRX)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Instructions come from

A

Memory hierarchy (iL1 cache)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What holds the address of each new instruction executed by the CPU?

A

Program Counter (PC)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

PC is updated after each instruction with what?

A

Either the next instruction (move 4/8 bytes) or the target of a branch address to be taken

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Four components of a CPU

A

Registers (temporary data storage), ALUs or Functional Units, PC for next instruction to fetch, Stack Pointer (SP) for top of stack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is an ISA?

A

Instruction Set Architecture, a model of a computer. Involves Memory Operations (load, store), Arithmetic Operations (add, or), and Control Flow Operations (jne, jmp)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the purpose of a CPU interrupt?

A

To handle asynchronous events, possible external. These are handled at the end of instruction execution (the boundaries of instructions).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is ISR?

A

Interrupt Service Routine. This is what happens when a CPU handles an interrupt. After the interrupt the PC will push the next instruction (before the interruption).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is memory hierarchy?

A

The concept that smaller SRAM cells are kept closer to the CPU (more frequently used data is kept closer). When data is not found in SRAM, the CPU will go as far as DRAM.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How to determine if something is in the cache?

A

Cache is broken into blocks, then sets (which contain a certain number of blocks). If number of blocks in a set is one, it is called direct mapped. If there are n-blocks in a set, it is called n-way associative. You must find the set where the block exists and then search every block in the set by using the tag (tag comparison)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What happens on a cache miss?

A

Bring in a block from deeper in the hierarchy (maybe even DRAM) and evict a block in the SRAM (Least Recently Used, a.k.a. LRU).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What happens when a block is modified after it is evicted?

A

The data will need to be written again (write-back cache).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is Memory Mapped IO?

A

The CPU can access IO devices like regular memory, using addresses. Events from IO devices are handled as interrupts.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What’s the problem with Memory Mapped IO?

A

It causes a lot of CPU resource usage. Everything the IO devices does needs to be handled by the CPU. Solution is to add controllers to the IO devices to take the usage off of the CPU.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Components of a Program

A

Code, Data, Stack, Heap. Space occupied by each part is called a segment.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Where are heap and stack located before execution in memory?

A

Heap starts at a lower address and grows toward higher addresses. Stack starts at the highest address and grows toward lower addresses. Both are empty before execution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

How does a computer know how to execute a program?

A

Load code and data into memory, set Heap and Stack pointers, and set the PC to main.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What’s the difference between a program and a process?

A

A process is a program in execution. A process has a program and a state at any point in time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

How to create a process in UNIX?

A

Call either fork() or exec(). fork() will create a duplicate of the already running process, and both will execute the next instruction from the PC. exec() will override the calling process with a new one.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What happens when you type a.out() in the shell?

A

The shell itself is a process that then calls fork() to make a duplicate of itself. The duplicate then calls exec() with a.out as a parameter, which runs the program.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is it called to perform one activity after another when you have many to run?

A

Batching

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What does it mean to time-multiplex the CPU amongst the processes?

A

It means even if one activity is done, we may still want to move on to processing another.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Is batching or multiprocessing preferred?

A

It is always better to use multiprocessing in modern computers. Early computers used batching. Do you want to stare at the oven while a cake bakes for 30 minutes?

24
Q

What does it mean to pre-empt a CPU?

A

Take the CPU away from currently executing processes.

25
Q

What is context-switching?

A

Re-assigning the CPU from one process to another.

26
Q

When should an OS perform context-switching?

A

Any time a process can’t proceed (waiting for I/O, etc.), periodically (using a timer).

27
Q

What does it mean for context-switching to be transparent?

A

An application should never know that it is being context-switched.

28
Q

How do we implement context-switching?

A

We need to save the context of a current process, restore the context of another process. This ensures the application never knows of the context-switching.

29
Q

What is the context of an application?

A

Code + data + stack + heap are what is referred to as the address space. There’s also the PC, SP, HP, and registers. Every process has something called a PCB (Process Control Block) into which context is saved and restored from.

30
Q

What is the advantage of a “process” view?

A

Implement concurrency between users, activities of a user. Also, insulating one activity from another.

31
Q

Drawbacks of a process view?

A

They are heavy weight, have higher scheduling costs (direct and indirect, like cache flushes). State sharing is also a problem.

32
Q

What are the overheads of a process view?

A

Switching code, data, stack and heap. Saving and restoring registers. Saving and restoring state maintained by OS.

33
Q

What are threads?

A

They are activities within the same address space, they share code, data, and heap. Only stacks are disjoint. All you have to do to switch between threads is to switch stacks. There is NO PROTECTION between threads, but this is okay since they are meant to be cooperative.

34
Q

How do we create a thread?

A

pthread_create()

35
Q

How do we terminate a thread?

A

pthread_exit()

36
Q

How do we wait for a thread to exit?

A

pthread_join()

37
Q

How do we get the thread ID?

A

pthread_self()

38
Q

What are the three process states?

A

Running, Ready, and Blocked. The OS maintains a queue for each of these states.

39
Q

What does it mean to Dispatch in the context of a state transition diagram?

A

Dispatching is moving from the ready state to the running state (assigning the CPU).

40
Q

Criteria for process selection: utilization

A

We should try to keep the CPU busy 100% of the time.

41
Q

Criteria for process selection: throughput

A

Maximize the number of jobs processed per hour

42
Q

Criteria for process selection: turnaround time

A

From the time of submission to the time of completion

43
Q

Criteria for process selection: waiting time

A

Sum of times spent in ready queue waiting to be scheduled on the CPU.

44
Q

Criteria for process selection: response time

A

Time from submission till the first response is produced (mainly for interactive jobs)

45
Q

Criteria for process selection: fairness

A

Make sure each process gets a fair share of the CPU

46
Q

Pre-emptive versus non-pre-emptive

A

With no pre-empting, a process has to terminate or be blocked before another can run. There is no transition from Running to Ready.

47
Q

FCFS Algorithm (Scheduling)

A

Serves jobs in the order they arrive, with no pre-empting. Very easy to implement, it’s just a FCFS queue. Very fair.

48
Q

Shortest Job First (SJF) Algorithm (Scheduling)

A

Pick the job that has the shortest duration after the current job is done. Could be pre-emptive or not. Has low turnaround time, but hard to know job duration and may be unfair.

49
Q

How do we estimate duration in a SJF scheduling implementation?

A

The same job could be coming back many times, so we could use a history. We use an exponential averaging technique to determine average time of a job.

50
Q

Priority Algorithm (Scheduling)

A

Every process has a priority value, we always schedule the process with the highest priority. FCFS and SJF are specialized forms of priority scheduling.

51
Q

Round Robin Algorithm (Scheduling)

A

This is pre-emptive. Periodically switch from 1 process to another. When a process arrives, add it to the end of the queue. When the time quantum expires, pre-empt the running process and put it at the end of the queue. Give the CPU to the process at the head of the ready queue. If the process blocks, put it in the blocked queue and give CPU to head of ready queue, resetting the time quantum.

52
Q

Rules of thumb with time quanta

A

Keep quanta large enough to accommodate most CPU bursts within one quantum. Keep large enough to keep context-switching overheads relatively low. Typically, context switch costs are in the 10s of microseconds. Time quanta are in the 10s/100s of milliseconds.

53
Q

Round robin queue with Priority

A

Has a different queue for each priority, always service the non-null queue at the highest priority level. Perform round robin scheduling on each queue.

54
Q

Multi Level Feedback Queues (MLFQ) (Scheduling)

A

Pick the process at the head of the highest priority non-null queue. Give it the allotted time quantum. If the CPU burst is not done, move it to the tail of the queue of a lower priority level.

55
Q

Sun Solaris Example

A

An MLFQ implementation example with 60 priority levels. Time quantum for highest level is 20ms, for lowest level is 200ms

CMPSC 473 (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions