Brainscape's Knowledge GenomeTM

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


See full index

os final > chapter 10 - multiprocessor and real time scheduling > Flashcards

chapter 10 - multiprocessor and real time scheduling Flashcards

1
Q

classification of multiprocessor systems?

A

loosely coupled, tightly coupled, functionally specialized processors

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

what is a loosely coupled multiprocessor?

A

distributed multiprocessor/cluster

Relatively autonomous systems, with each processor having its own memory and I/O channels

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

what is tightly coupled multiprocessesing?

A

Processors share main memory and are controlled by an operating system

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

what are functionally specialized processors?

A

Such as I/O processor controlled by a master processor

specialized processor controlled by a master processor

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

what is granularity?

A

the frequency of synchronization between the processes in a system.

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

what are the types of granularity?

A

independent parallelism, fine-grained, medium-grained, coarse, very coarse

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

what is independent parallelism?

A

unrelated processes, no synchronization

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

what is coarse-grained parallelism?

A

multiprocessing of concurrent processes in a multiprogramming environment

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

what is very coarse-grained parallelism?

A

distributed processing across network nodes to form a single computing environment

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

what is medium grained parallelism?

A

parallel processing or multitasking within a single application (threads)

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

what is fine-grained parallelism?

A

parallelism inherent in a single instruction stream

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

what do independent, coarse, and very coarse parallelism have in common?

A

supported by either a multiprogrammed uniprocessor or multiprocessor with little to no impact on scheduling

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

what makes medium grained parallelism unique?

A

scheduling decisions of one thread can affect the entire application’s performance

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

3 issues that come with scheduling on a multiprocessor

A
  • assignment of processes to processor
  • use of multiprogramming on individual processors
  • actual dispatching of a process
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

assignment of processes to processor (issue 1) - static assignment

A

assigns process to a processor where it stays until finished

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

assignment of processes to processor (issue 1) - static assignment - advantages

A

May require less overhead in the scheduling function since processor assignment is only made once.
Permits group or gang scheduling

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

assignment of processes to processor (issue 1) - static assignment - disadvantages

A

Doesn’t distribute workload well (process could wait while a CPU is free)
Could periodically redistribute processes to balance the queues.

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

assignment of processes to processor (issue 1) - variable assignment -

A

Assign process from single queue to any free processor.
Distributes work-load more evenly among processors.

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

2 approaches for assignment of processes to processors (issue 1)

A

master/slave, peer approach

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

what is the master/slave approach in assignment of processes to processors (issue 1)

A

one CPU (or set of CPUs) is dedicated to OS. Schedules all jobs. Simplifies OS, but not as fault-tolerant and may be performance bottleneck.
a variation uses multiple CPUs for kernel processes

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

what is the peer approach in assignment of processes to processors (issue 1)

A

processors do self-scheduling. Complicates the OS but is more fault-tolerant

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

why is multiprogramming desirable in uniprocessor systems? (issue 2)

A

achieves better processor utilization

having a single processor be busy all the time when there are many processors may not be ideal as having applications perform better on average

23
Q

explain process dispatching (issue 3)

A

When a single processor is used, different scheduling algorithms may be used to increase system performance or meet system objectives.

However, studies show that the particular scheduling algorithm chosen for multiprocessor systems is less important than for uniprocessor systems.

FCFS is the best for a multiprocessor system

24
Q

what are the 4 approaches for multiprocessor thread scheduling?

A

load sharing, gang scheduling, dedicated processor assignment, dynamic scheduling

25
Q

what is load sharing (approach 1)?

A

one of the simplest, most used schemes. processes not assigned to any particular processor, CPUs self schedule from a global queue of ready threads

26
Q

what are the advantages of load sharing (approach 1)?

A

Even distribution of work across CPUs.

No centralized scheduler required (each CPU self-schedules).

Each processor selects a process from a global ready queue using any of the schemes

27
Q

what are the disadvantages of load sharing (approach 1)?

A

The global queue may become a bottleneck to system performance.

Preempted threads unlikely to resume on same CPU, therefore less efficient caching.

Unlikely to have all threads of a program in execution at the same time, so if threads have high degree of coordination, not very efficient.

28
Q

what is gang scheduling (approach 2)

A

Scheduling threads of a single process to run at the same time.

If a thread is running and needs to wait on another thread that is not running, a thread-switch must occur to bring in the needed thread. - can reduce performance

improves performance in medium-grained applications where synchronization is important

29
Q

what are the approaches for gang scheduling?

A

uniform division, division by weights

30
Q

what is uniform division?

A

gang scheduling approach

If there are M processes and N processors, give each process all N processors for 1/M amount of time.

Unfortunately, if for example there are two processes, one with 4 threads and one with 1 thread, then 3 CPUs are idle when the 1-thread process runs.

31
Q

what is division by weights?

A

gang scheduling approach

If there are M processes and N processors, give each process all N processors for 1/M amount of time.
Unfortunately, if for example there are two processes, one with 4 threads and one with 1 thread, then 3 CPUs are idle when the 1-thread process runs.

In the above situation, let the 4-thread process have 4/5 of the time, and the 1-thread process 1/5 of the time.

32
Q

what is dedicated processor assignment (approach 3)

A

extension of gang scheduling

dedicate group of processors to an application for duration of its execution

avoids process switching of the application - improves speedup

33
Q

what is dynamic scheduling? (approach 4)

A

Involves cooperation between the OS and the application in dynamically deciding on the number of threads to run.
The OS gives the process some number of processors on which to run.
The process makes decisions about which of its threads to run on the available processors.
Still somewhat experimental.

34
Q

what is real-time scheduling?

A

A real-time computing system must not only assure the correct results, but also assure the time at which they are produced.

35
Q

types of real-time tasks?

A

hard real-time task, soft real-time task, aperiodic, periodic

36
Q

what is a hard real-time task?

A

must meet deadline or system fails

37
Q

what is a soft real-time task?

A

should meet deadline but isn’t mandatory

38
Q

what is aperiodic real-time task?

A

has deadline or time constraint it needs to finish in

39
Q

what is periodic real-time task?

A

has to finish exactly T time units apart

40
Q

5 characteristics of real time operating systems?

A

determinism, responsiveness, user control, reliability, fail-soft operation

41
Q

what is determinism? (characteristic 1)

A

Determinism is the extent to which the OS performs an operation at fixed, predetermined times or within predetermined time intervals.

time to acknowledge interrupt/request

42
Q

what is responsiveness? (characteristic 2)

A

time to process request

Responsiveness is concerned with how long it takes to service an interrupt once it has been acknowledged.

Determinism (time to acknowledge interrupt) plus responsiveness (time to service interrupt) together make up the response time.

43
Q

what is user control? (characteristic 3)

A

user given high degree of control over scheduling of tasks in real-time OS

44
Q

what is reliability? (characteristic 4)

A

how reliable system is

45
Q

what is fail-soft operation? (characteristic 5)

A

ability to fail in a way to preserve as much capability and data as possible

stability is important aspect - meet the most critical ones if you can’t get all the requests

46
Q

how does fail-soft differ from fail-safe?

A

fail-soft: maintains partial functionality

fail-safe: avoids unsafe behavior

47
Q

4 approaches to real-time scheduling

A

static table-driven, static priority-driven, dynamic planning-based, dynamic best effort

48
Q

what is static table-driven approach?

A

real-time scheduling approach.

schedule is computed in advance from set of jobs and their requirements. Predictable, but not flexible. New job requires schedule to be redone.

49
Q

what is static priority-driven approach?

A

real-time scheduling approach.

priorities are assigned to jobs in advance from set of jobs and their requirements, but no explicit schedule is produced. Relies on normal priority-driven preemptive scheduler.

50
Q

what is dynamic planning based approach?

A

real-time scheduling approach.

allows accepting new tasks at run-time. Does feasibility analysis of existing jobs plus new job to see if new job can be fit in.

51
Q

what is dynamic best effort approach?

A

real-time scheduling approach.

assigns priorities based on task characteristics. System tries to meet all deadlines, and aborts jobs that do not. Easy to implement, but until a deadline arrives, it is unknown whether it will be met.

52
Q

7 scheduling factors

A

ready time, starting deadline, completion deadline, processing time, resource requirements, priority, subtask structure

53
Q

what is rate monotonic scheduling?

A

can be used for periodic tasks

assigns priorities to tasks on the basis of their periods (high priority = shorter period)

os final (5 decks)

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