Lecture 9 - Embedded operating systems Flashcards

1
Q

What is the difference between a process and the operating system?

A

The process defines the state of an executing program, and the OS provides mechanisms to switch execution between processes

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

Why can using OS and processes be beneficial in embedded systems?

A

Combining these can allow us to implement complex applications with greater flexibility that satisfy timing requirements.

When abstracting the control required to switch between processes to the OS, it is easier to meet timing requirement while keeping the control within the processes cleaner.

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

What is a RTOS?

A

Real-time Operating System

An OS that facilitates to meet real time requirements.

An RTOS allocates resources using algorithms that takes timing into account.

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

How does resource allocation differ in an OS and a RTOS?

A

An OS will try to allocate resources using the criteria of fairness, giving the different parts of the CPU equally much resources.

A RTOS need to take timing into account. If a RTOS allocate resources equally without thinking about timing, deadlines are likely to be missed.

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

Define the term “Task” in regards to real-time computing

A

A set of real-time programs that communicates.

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

What is a task-graph?

A

Graph showing the different subtask and dependencies between these.

The edge-arrows defines dependencies between subtasks

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

What is a process?

A

Single execution of a program.

Has its own state, memory and registers.

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

What are threads?

A

Processes that run in the same address space.

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

What is multirate systems?

A

A system where multiple rates of computation must be handled.

Certain operations must execute periodically, and each operation is executed at its own rate.

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

What are two types of timing requirements that are important for processes?

A

Initiation time and deadlines

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

What is the initiation time?

A

The time at which the process goes from the waiting state to the ready state.

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

How are aperiodic processes initialized?

A

The initiation time is measured from the event that initialises it (arrival of extern data, computation of data from another process)

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

How are periodic processes initialised?

A

Can be ready at the beginning of a period.

Others may set initiation time at the arrival time of certain data after the start of the period

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

What are deadlines?

A

Specifies when computation must be finished.

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

How are deadlines for aperiodic processes measured?

A

Deadlines are measured from the initiation time, as these are the only reasonable time references available.

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

How are deadlines for periodic processes measured?

A

Deadlines will generally occur at some time before the period ends.

Some scheduling policies simplify that the deadline occurs at the end of the period

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

What are rate requirements?

A

How quickly must processes be initialised

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

What is a period?

A

The time between successive executions in a process.

Specification of the expected behaviour of a task

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

What is the process’s rate?

A

Inverse of its period.
In multirate systems, each process executes at their own rate

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

What is a common requirement for periodic processes?

A

Initiation interval to be equal to the period

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

What is response time?

A

The time at which the process finishes.

If the schedule meets the requirements, the response time will be before the period end.

Computation time is a part of response time, but response time also includes time the process is de-scheduled by other tasks.

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

What is computation time?

A

How long it takes to execute.

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

What is the jitter of a task?

A

The allowable variation in its completion.

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

What can happen if a deadlines is missed?

A

In safety-critical systems it can be catastrophic if deadlines are missed, and they might want to take measures to i.e. approximating data or switching into a safety modes.

For systems where safety is not that important, simpler measures can be taken, or the failure can be ignored all together.

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

What is utilization?

A

Available CPU time, a way to measure the efficiency at which we use the CPU.

U = CPU-time-for-useful-work / total-available-CPU-time

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

What is scheduling?

A

The work of choosing the order of running processes

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

Name the 3 scheduling states

A

Waiting, ready and executing

Ready: Any process that could be executing are in the ready state, have received all data, has entered a new period

Waiting: A process waiting for data, completed all work for this period

Executing: Process selected by the scheduler to run

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

What is a scheduling algorithm?

A

Algorithm that decides how processes are selected for the promotion from the ready to the execute state.

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

What does scheduling algorithms take into account?

A

Timing requirements

The efficiency with which they use the CPU.
Utilization is a key metric in evaluating scheduling policies.

Scheduling overhead, execution time required to choose next execution

30
Q

What 2 concepts does RTOS depend on?

A

Preemption and priority-based scheduling

31
Q

What is preemptive scheduling?

A

Running tasks can be preempted during execution

Based on the system’s timing constraints, we are allowed to jump between functions whenever necessary.

The kernel is the part of the OS that determine what process is running.

The timer periodically activates the kernel.

The time quantum is the length of the timer period. This is generally shorter then the period of the processes being scheduled

The kernel decides what process is going to be run next.

32
Q

What is prioritised scheduling?

A

The processes are assigned priories. The kernel looks at these priorities to decide what process to run next. This would be the process with the highest priority, that is ready to run.

33
Q

What is context switching?

A

Switching from one process’s context to another one’s

This happens when the timer interrupts a process, the process state is saved by assembly language.

The kernel is then given execution rights and decide what process to schedule.

This new process’s state is restored

34
Q

What is a context?

A

The registers that defines a process

35
Q

What is a record?

A

The data structure that holds the state of a process

36
Q

What are active objects in UML?

A

When processes are described in UML they are active objects.

Active objects have independent threads of control.

Includes name, attributes, operations, signals

Signals: An object passed between an object for asynchronous communication

37
Q

What is the round robin scheduling algorithm?

A

Used in general-purpose OS

All processes kept on a list and scheduled one after another. Uses some preemption so that one proces does not keep all resources. Schedules to provide fairness.

Does not guarantee completion time. As list of processes increase, so does response time for all processes.

38
Q

How is scheduling often done in RTOS?

A

Priority based
Real time requirements are important

39
Q

What is the Rate-monotonic scheduling algorithm?

A

A static scheduling policy: Processes gets fixed priorities

preemptive

Based on the rate-monotonis analysis (RMA) theory, this gives a quite simple scheduling policy.

Priorities are assigned by rank order of period, shorter periods gets higher priority

This policy is the optimum assignment of static priorities to processes, in that it provides highest utilisation while ensuring everyone meets deadlines.

40
Q

What is the Rate-monotonis analysis (RMA) theory

A

All processes run periodically on a CPU

Context switching time is ignored

No data dependencies between processes (resource sharing)

Execution time for a process is constant

All deadlines are at the end of their periods

The highest-priority ready process is always selected

41
Q

What is the critical instant for a process?

A

The instant during execution at which the task has the longest response time.

42
Q

What is the critical interval for a process?

A

The complete interval for which the process has the longest response time

43
Q

What is the critical instant for any process under RMS?

A

When the process is ready and all the higher priority processes also are ready

44
Q

Does RMS always provide feasible scheduling?

A

No, the scheduling algorithm might not provide scheduling of processes in a way that all deadlines are met

45
Q

What is the Earliest-deadline-first scheduling policy?

A

Its a dynamic priority scheme: Changes process priorities based on initiation time.

Preemptive

Assumption: Deadline=Period (in paper), no sharing, no context switching time

Updates priorities at every time quantum, and they are assigned based on nearest deadline. Highest priority to process where deadline is nearest.

Highest priority process that is ready is scheduled

If a process set is not schedulable by EDF, no other scheduling algorithm can schedule tthe task set

46
Q

Compare EDF and RMS scheduling

A

EDF can schedule some process-sets that RMS cannot.

47
Q

What is a race condition?

A

When multiple processes accesses the same data and modifies, making wrongful results when operating in different orders.

48
Q

What are mutexes?

A

Protects critical sections.

A mutex is called before a critical section is entered. The process calling the mutex reserves it.
If another process tries to get the mutex, it won’t be able to as long as it is reserved by someone else.

A process cannot enter a critical section without a mutex, and needs to wait until the mutex is released.

49
Q

What are semaphores?

A

Useful when several copies of resources are available.
They have a name property, which allows to create multiple semaphores in a system, and a counter keeping track of remaining available resources.

P() is called to get access to the resources. If max resources are given, the process waits until a semaphore is released and signaled using V().

50
Q

What operation is required to be able to implement mutexes and semaphores?

A

Atomic read/write.

i.e. when setting semaphores we use Test-and-set. We first read it, then if it is set we get returned false. If it is not set we set it and return true.

51
Q

Why does critical section provide problems in real time systems?

A

Because interrupts are disabled when working on a critical section. And other processes cannot be scheduled.

52
Q

What is priority inversion?

A

When a lower priority process blocks execution of a higher priority process by keeping hold of its resources (critical section).

53
Q

What is priority inheritance, and what problem does it solve?

A

Solves priority inversion.

The priority of a process is upgraded when the process requests a resource from the OS. The priority of this process becomes higher than the priority of other processes using this resource. This ensures that it can continue execution once it has this resource to be able to finish its work.

54
Q

What assumptions have we made with RMS and EDF?

A

Context switching takes 0 cycles

No data dependencies in RMS

Process execution time is constant: Can vary based on caching and data dependences

55
Q

What are the two ways a process can send communication?

A

Blocking and non-blocking

56
Q

What is blocking communication between processes?

A

The process goes into a waiting state until it receives a response.

57
Q

What is non-blocking communication between processes?

A

The process continues execution after sending the communication

58
Q

What are the 3 styles of interprocess communication?

A

Shared memory and message passing

Signals

59
Q

What is shared memory communication?

A

Processes can communicate by writing to and reading from a shared memory location

60
Q

What is message passing communication?

A

Each process has their own message passing/receive unit

Message is stored at the senders/receivers endpoints.

Use a queue to manage message. This queue uses FIFO.

61
Q

What is communication using signals?

A

Signals are software created, and generated by a process and passed to another by the OS.

62
Q

What do we need to take into account when evaluating RTOS performance

A

Context switching time

Variable process execution time

Latency from when interrupt is requested to when handling is finished

execution time of scheduler

63
Q

What is the layout of a single threaded process?

A

Code | data | files
registers | Stack
thread

64
Q

What is the layout of a multi threaded process?

A

each thread has its own registers and stack, in addition to shared code, data and files

65
Q

What are the properties of embedded OS

A

Customizable
resource-efficient: Small memory footprint
predictable or deterministic: real-time capabilities
energy efficient: dynamic power management

66
Q

Why are not desktop OSs suited for embedded systems?

A

Require large disk space

They are usually monolithic - provide numerous services for diverse hardware

No real-time guarantee

No features for reliability

67
Q

What is the Compare Fair Scheduling (CFS)

A

Used in OS

Chooses process with lowest execution time

Goal: Fairness

No real-time guarantee

68
Q

What does real-time mean for embedded systems?

A

The correctness of the system depends both the logical result and on the time at which the result was produced.

Predictability and determinism

deadlines and real-time requirements

69
Q

What is hard real time?

A

Catastrophic consequenses

70
Q

What is soft-real time

A

Desirable features (i.e. video playback)

71
Q

What information about a process does a real-time scheduler know?

A

Starting time
Execution time (Worst-case)
Deadline
Period (Common - periodic tasks)
Priority (rigorously respected)

72
Q

What is energy efficient scheduling?

A

Energy and power are main concerns especially in systems that are battery supplied.

Can use DVFS to lower power usage
Determine values that just meets the deadline