Final Review Flashcards
(115 cards)
1
Q
What is an Embedded System?
A
Computer system purpose built for a specific application
2
Q
What is a Real Time System?
A
Embedded system that returns results sufficiently quickly to affect current environment. Execution predictability is as important as speed
3
Q
What is a hard deadline?
A
Failure to meet the deadline leads to total system failure
4
Q
What is a firm deadline?
A
Infrequent misses can be tolerated but late data has no value
5
Q
What is a soft deadline
A
Misses are acceptable, but late data has diminishing value
6
Q
Why use C for RTS?
A
compact, compiled, no garbage colleciton.
7
Q
How does a struct differ from a class?
A
no member functions, no private/public protection
8
Q
Why do we define special types such as uint32_t?
A
Increases portability across systems
9
Q
What are the 5 components of a basic computer
A
Input, Output, Memory, ALU, Control
10
Q
How many memory locations are adressable with a 32 bit address?
A
2^32 Memory locations
11
Q
What is the difference between big and little endian
A
Big endian, most significant byte is stored in a lower address. Little endian, most significant byte is stored at the lower address.
12
Q
What are the four types of memory
A
Text, Data, Heap, Stack
13
Q
What is the difference between Volatile and Non Volatile memory
A
Volatile memory loses its contents when power is lost.
14
Q
What are examples of volatile memory
A
DRAM, SRAM
15
Q
What are examples of non volatile memory?
A
Disk, Tape, NAND Flash
16
Q
What is a MCU?
A
Memory Controller Unit. Processor with memory, I/O, UART and RTC
17
Q
What is memory mapped IO?
A
IO devices are mapped to memory locations and can be written to to change behavior or read from to recieve data.
18
Q
How does polling IO work
A
Repeatedly check I/O status register until data is ready.
19
Q
What are the downsides to polling IO?
A
Wastes time repeatedly checking the status register
20
Q
What is an alternative to polling IO?
A
Interrupt based IO
21
Q
How does interupt IO work?
A
IO device throws a IRQ which is mapped to a corresponding ISR using a vector table. The ISR handles the IO, and restores the context
22
Q
When can an ISR be interrupted?
A
When a higher priority IRQ is received. Otherwise, any incoming IRQs must wait for the ISR to finish
23
Q
What features must ISRs have
A
Must be re-entrent: no static variables
24
Q
What is Bare Metal Scheduling
A
Hard Code tasks to run at certain loop intervals, using lowest common denominator
25
What is Concurrency
multiple tasks running independently with their own context
26
What parameters define a task
Start Time, Deadline, Period, Execution Time
27
What is an easy check to see if a set of tasks is scheduable?
The summation of execution times over periods must be less than 1
28
What is non preemptive scheduling
Schedule is created in advance. Each task runs for a specified amount of time and cannot be interrupted
29
What is Round Robin Scheduling
Each task is given the same time slice (equal priority). Implemented using a queue.
30
What is EDF Scheduling?
Earliest Deadline First. Task with the closest deadline has highest priority. Can be pre-empted if a task with a earlier deadline arrives.
31
How is EDF implemented?
Using a ready queue and a waiting queue. (Heaps). A interrupt is set for the release time of the head of the waiting queue.
32
What is RM/Fixed Priority Preemptive Scheduling
Tasks with equal priority are run in round robin fashion. Can be interrupted if a higher priority task arrives
33
How is RM scheduling implemented
array of linked lists.
34
What is a Semaphore
A non-negative counter. Has a init, wait and signal funciton.
35
What is a Mutex
A mutex is a binary semaphore. Has a value of 0 or 1. TODO: Add functions
36
What is Condition Variable Synchronization
One task waits for another task to signal a semaphore once a certain event has occured.
37
What is Rendezvous Synchronization
Two semaphores are initialized to 0. Each task signals one semaphore and then waits on the other. Both tasks must wait until both have reached the rendezvous
38
What is Barrier Synchronization?
A extension of Rendezvous. There is a counting semaphore, a barrier semaphore and a locking mutex. When each task reaches the barrier it increments the counting semaphore and then waits on the barrier. The last task to arrive increments the counting semaphore to n, which allows the task to increment the barrier. Once past the barrier wait, each task signals the barrier semaphore so the other tasks can go through
39
What is mutual exclusion
Wrap shared memory access with a wait/signal block to prevent two tasks from modifying the same variable at the same time.
40
What is Priority Inversion?
A task with a lower priority blocks a higher priority task by holding a mutex
41
How do you prevent priority inversion
temporarily raise the priority of the mutex holder task to maximum priority
42
What is arecursive mutex
task can acquire mutex multiple times (recursively) without blocking. Mutex must be released an equal number of times.
43
What rule of thumb is there for mutex hold length
hold mutexs for the minimum possible duration
44
What is deadlock
No tasks can procede, as each task is waiting on a held mutex.
45
What is one possible solution to deadlock?
Ordered resource allocation. Have all tasks accept one pickup resources in the same direciton
46
What is the producer consumer communication model
One task produces data, another task consumes data. Data is passed via messages between them
47
What are some examples of producers and consumers
producers: sensor data, user input. Consumers: control tasks/
48
What is a handshake protocol
Producer must wait for the Consumer to be ready to recieve data before data can be sent. The Consumer must wait for a message to be ready before it can read data.
49
What problems are there with producer consumer?
The consumer must copy the data into a temporary variable. Not ideal for longer messages.
50
What is Double Buffering?
Two buffers, with a full count and empty count semaphore to indicate state. Allows producer to fill the second buffer while consumer reads the first
51
How do you allocate a double buffer?
```
const SIZE = 512;
uint8_t data[2*SIZE]
uint8_t buff_ptr[2] = {&data[0], &data[size]}
```
52
How does a double buffer operate?
producer waits for non 0 empty count, fills its indexed buffer, signals the full count then increments its index. The consumer waits on non 0 full count, consumes the data from its buffer, signals empty count then increments its index
53
What is a Message Queue?
multiple producers and consumers share a queue of arbitrary size
54
How is a message queue implemented?
array of memory locations, indexes for the start of full and the start of empty. semaphores for full and empty count and a mutex to enforce mutual exclusion when accessing and mutating
55
How can a message queue avoid copying data
only store pointers to the data in the queue, instead of the data itself
56
TODO: KEIL MAILBOXES
asdfasdf
57
How do you size a buffer with constant p(t) and c(t)
if c(t) < p(t), Buffer size = (p(t)-c(t))*burst time
58
How can you check if buffer sizing will prevent data loss
Compare average consumer rate and producer rate over the burst period. If c_avg > p_avg, no data will be lost
59
TODO: Variable p(t) and c(t)
sasdfasdf
60
What are the main variables of queuing theory
Average arrival rate: lambda, average service rate: u. Load factor: lambda/u
61
What are the two models of queing theory
Deterministic and Markov
62
In a deterministic model, what can be said about the arriavl time of clients and service?
Clients/servers have a regular period, equal to 1/lambda or 1/u.
63
What separates a markov process from a deterministic process
time between each arrival in a markov process is independent of the previous arrivals. It is a memory less, stochastic process
64
What equation governs the arrival time of a markov process
p(t) = lambda*e^(-lambda*t)
65
What is the average queue length in queuing theory?
L = rho/(1-rho)
66
What is the average time in the system in queuing theory?
W = L/lambda = (1/u)/(1-rho)
67
What is the probability of having more than k customers?
P(x>k) = rho^k
68
What law governs the relationship between queue length and average system time?
Little's Law: L = lambda*W
69
What is a PID Controller
Proportional Integral Differential Controller.
70
What is the purpose of the P in a PID controller
The response of the controller is proportional to the error. The larger the error, the larger the response
71
What is the purpose of the I in a PID controller?
The response of the controller increases as error accumulates. (The integral of the area can be estimated using a summation)
72
What is the purpose of the D in a PID controller
The Differential means that the response is proportional to the rate of changes. Sudden jumps in error lead to large responses.
73
What is a ADC and DAC?
Analog to Digital Converter, Digital to Analog Converter
74
What is CAN
Controller Area Network. High integrity, serial, broadcast bus. Speeds up to 1 Mbps
75
How many wires are in a CAN network
2, CAN Hi and CAN Lo.
76
What two modes are there on a CAN network
Dominent: Hi is 5V, Low is 0 V and Recessive: Hi is 2.5 V, Lo is 2.5V. The wires default to recessive when no signal is transmitted. Dominant is taken as a 0, recissive is taken as a 1.
77
How are CAN messages sent?
In Frames, to all other nodes in the network. (up to 112)
78
what are the four types of frames in CAN?
Data, Remote, error, overload?
79
What components are there in a CAN Frame Format
Start of frame, 11 bit ID, remote transit bit, data length code, data bytes, CRC,delimiter, ack, 7 bit EOF, 3 bit inter frame space.
80
How does CAN determine who is next to transmit
Nodes transmit once network is idle. If two nodes transmit at the same time, the logical and of their signals is received. If a node detects a difference between the network and its message, it goes idle. Therefore, nodes with lower IDs have higher priority.
81
How does CRC work
Cyclic Redundancy Check. Divide message by a 3rd order polynomial (1011). pad the original message with 0s to determine the CRC. To check message, add the CRC to the end of the message and confirm the remainder is 0.
82
What are the layers of the OSI Network Model
Application, Presentation, Session, Transport, Network, Data Link, Physical.
83
What is the role of the physical OSI Layer
transmit the bits from one host to another
84
What is the role of the data link OSI layer
packages data into frames, checks for errors and provides acknowledgment
85
What is the role of the network layer
Routes packets through the network, controls congestion
86
What is the role of the transport layer
creates connections, orders messages
87
what is the role of the session OSI layer
dialogue control and synchronization
88
what is the role of the presentation OSI layer
encoding, compression and encyrption
89
what is the role of the application OSI layer?
Http, ssh, ftp, smtp
90
What layer would a Hub be used at?
Physical. It broadcasts incoming packets to all ports
91
What layer would a switch be used at?
Data Link. It forwards packets based on MAC address.
92
What layer would a router be used at
Network. If forwards packets based on IP.
93
What is the difference between OSI layers 1-3 and 4-7
1-3 are between machines, while 4-7 are end to end protocols
94
What network was the predecessor to the internet
ARPANET (advancecd research projects agency). Connected super computers at universities
95
In TCP/IP, what OSI layers do the Application layers map to ?
App, Presentation and Session map to HTTP/SMTP
96
In TCP/IP what OSI layers do the Transport Layers map to?
Session and Transport. Goverend by the TCP/UDP protocol
97
In TCP/IP what OSI layer does the internet layer map to
Network, goverend by IP.
98
In TCP/IP what protocols govern the Data Link and Physical OSI layers
MAC, Ethernet, Wifi
99
How is a packet structured?
Each Protocol adds its own header, (Application, TCP, IP, Ethernet. Total packet length is between 46 and 1500 bytes.
100
Why is IP unreliable for packet routing?
routes packets hop by hop. Can lead to duplication, delay, or out of order recieving
101
What solutions are there for unreliable IP packet routing
TCP protocol. uses handshaking and sequence #s to ensure all data gets to host in order. Creates a virtual circuit between hosts with sockets at each end.
102
What are some common ports?
20: FTP, 80: HTTP, 443: HTTPS, 22 SSH, 143: IMAP, 587, SMTP.
103
What are the components of a TCP Header?
Source Port, Destination Port, Sequence Number, Ack, Hlen, flags, window, checksum, urgent pointer, options.
104
What differentiates UDP from TCP?
UDP is connectionless, it is faster but far less stable ( no ack or sequence number
105
What makes up a UDP Header?
Source Port, Destination Port, Length, Checksum
106
What steps are there on the server side fro socket programming
create socket, bind socket to port, listen for connection, accept connection, recieve/send data
107
What steps are there on the client side for socket programming?
Create a socket, request a connection, send/recieve data
108
What makes up a task control block?
Priority, delay time, stack pointer, next/previous pointers for wating list, state, ID
109
What are the three types of Exceptions?
Interrupter - request for service from peripherals, Faults- Problems executing instructions (Errors, Exceptions) Trap- Instruction that invokes a OS Service
110
What Items are in the Text, Data, Heap and Local Memory Segment
Text: The physical program and constants. Data: global and static variables. Heap: dynamically allocated memory. Stack: local variables, call stacks and pointers to dynamic memory.
111
How do you know if RM is schedulable?
Product of 1+Ci/Ti < 2
112
What are the four conditions for deadlock?
Hold and Wait, No Pre-emption of resources, Mutual Exclusion, Circular Waiting
113
What are the four task states
Running, Waiting (waiting to be run), Inactive and Ready
114
What is spin lock
Busy waiting (used for semaphore waits) useless.
115
What are alternatives to spin lock?
spin lock w/ coop : forfeit execution if waiting.
| Blocking Semaphore: Add task to waiting queue until semaphore is signaled, then its returned to the ready queue.
