-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathЛекции по информатике.cpp
1148 lines (1021 loc) · 69.5 KB
/
Лекции по информатике.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
Карпов Владимир Ефимвич - основы ОС
Лекция 1 - Структура вычислительных систем {
Стректура вычислительных систем
Техническое обеспечение
Пользователь
Прикладные программы
Системные программы
ОС
Прочие системные программы
Операционные системы (точки зрения)
Распределение ресурсов
Защита пользователей и программ
Виртуальная машина
Кот в мешке
Простоянно функционирующее ярдо
Факторы
Эффективность
Стоимость
Безопасность
Эволюция вычислительных систем
1945 - 1955
Ламповые машины (до 10'000 ламп)
Нет разделение персонала
Нет ОС
Ввод программы с пульта или колоды перфокарт
Отладка программ с пульта
Одновременное выполнение только 1 операции
Появление праобразов первых компиляторов
Научно-исследовательская работа в области вычислительной техники
1955 - 1960
Транзисторные машины
Разделение персонала
Бурное развитие алгоритмических языков
Ввод задания с колоды перфокарт
Отладка программы по изучению распечаток
Пакеты заданий и системной пакетной обработки
Начало использования ЭВМ в научных и коммерческих целях
1960 - 1980
Машины на интегральных схемах
Использование spooling - доп. процессоры ввода\вывода
Планирование заданий
Магнитные ленты
Мультипрограмные пакетные схемы
Система разделения времени (time-sharing)
Виртуальная память
Интерактивная отладка программ
Развитые файловые системы
Широкое использование ЭВМ в научных и коммерческих целях
1980 - 2005
Машины на больших интегральных схемах (БИС)
Персональные ЭВМ
Дружественное программное обеспечение
Сетевые и распределенные ОС
Широкое использование ЭВМ в быту, в образовании, на производстве
Идеи мультипрограммирования
Software
Планирование заданий
Управление памятью
Сохранение контекста
Планирование пользования процессора
Системные вызовы
Средства коммуникации
Среда синхрониации
Hardware
Защита памяти
Сохранение контекста
Механизм прерываний
Привилегированные команды (что-то сможет сделать только ОС)
Основные функции ОС в процессе своей эволюции
Планирование заданий и использования процессора
Обеспечение программ средствами коммуникации и синхронизации
Управление памятью
Управление файловой системой
Управление вводом\выводом
Обеспечение безопасности
Внутреннее строение ОС
Монолитное ядро
Каждая процедура может вызывать каждую
Все процессы работают в привилегированном режиме
Ядро совпадает со всей ОС
Пользовательские программы
Многоуровневые системы
N - интерфейс пользователя
4 - Управление вводом\выводом
3 - Драйвер связи с консолью
2 - Управление памятью
1 - Планирование задач и процессов
0 - Hardware
Микроядерная архитектура
Приложение <-> Микроядро <-> Менеджер сети
Менеждер памяти
{ Приложение 1 <-> }
{ } <-> Микроядро
{ Приложение 2 <-> }
{ Приложение 1 <-> }
{ } <-> Библоиотеки <-> Экзоядро
{ Приложение 2 <-> }
Виртуальные машины
{ Виртуальное Hardware <-> Linux <-> Пользователь }
Реальные ОС и Hardware <-> { Виртуальное Hardware <-> Windows <-> Пользователь }
{ Виртуальное Hardware <-> DOS <-> Пользователь }
}
Лекция 2 - Процессы {
{ Программа }
{ } - Cтатические
{ Задания }
Процесс - динамический
Процесс != программа
1 программа - несколько процессов
Состояния процесса
Вход
Процесс не исполняется
Приостановка | | Возобновление
Исполнение
Выход
Операции
Создение\завершение
Запуск\приостановка
Блокировка\разблокировка
Изменение приоритета
Procces Control Block контекст процесса
Состояние процесса
Програмный счетчик
Содержимое регистров
Данные для планирования
Учеьная информация
Сведения об устройствах ввода\вывода
Код и данные в адресном пространстве - пользовательский контекст
Linux - rootprocces - init
Создание процесса
Порождение PCB с состоянием процесса "рождение"
Присвоение индефикационных номеров
Выделение ресурсов
Из реусрсов родителя
Из ресурсов ОС
Завершение процесса
Изменение состояния процесса на "закончил исполнение"
Освободление ресурсов
Очиства соответствующих элементов в PCB
Сохранение в PCB записи причины завершения
Запуск процесса
Выбор одно из процессов находящихся в состоянии готовноси
Изменение состояния выбранного процесса на "исполнение"
Обеспечение наличия в оперативной памятии инв.
Восстановление значений регистров
Приостановка процесса
Автоматическое сохранение программного счетчика и части регистров
Передача управленичя по специальному адресу
Сохранение динамической части регистров и стстемных конекстов в PCB
Изменение состояния процесса на "готовность"
Блокировка
Сохранение контекста процесса в PCB
Обработка системных вызовов
Разблокировка
Уточнение как именно произошло событие
Проверка наличия процесса
Перевод в состояние "готовность"
(1-4)*10^3 тактов на переключение контекста
}
Лекция 3 - Планирование процесса {
Уровни планирвоания процессов:
Долгосрочное планирование - планирование заданий
Среднесрочное планирвоание - swapping
Краткосрочное планирование - планирвоание использования процесса
Цели планирования:
Справедливость
Эффективность
Сокращение полного времени выполнение (turn around time)
Сокращение времени ожидания (waiting time)
Сокращение времени отклика (response time)
Желательные свойства алгоритмов планирования:
Предсказуемость
Минимизация накладных расходов
Равномерность загрузки вычислительной системы
Масштабируемость
Параметры планирования:
Статические:
Предельные значения ее ресурсов
Кем запущен, степень важности, запрошенное процессорное время, какие нужны ресурсы и т.д.
Динамические:
Кол-во свободных ресурсов в данный момент
Текщий приоритет, использованое процессорное время, размер занимаемой памяти
CPU burst и I\O brust:
a = 1 - CPU
b = 2 - CPU
read с - CPU
Ожидание окончание ввода - I\O
a = a + с*b - CPU
print a - CPU
Ожидание окончание вывода - I\O
Вытесняющее и невытесняющее планирование:
Вынужденное принятие решения: - невытесняющее планирование:
Перевод процесса из состояния "исполнение" в состояние "закончил исполнение"
Перевод процесса из состояния "исполнение" в состояние "ожидание"
Невынужденное принятие решения: - вытесняющее планирование:
Перевод процесса из состояния "исполнение" в состояние "готовность"
Перевод процесса из состояния " ожидание " в состояние "готовность"
Алгоритмы планирования:
FCFS (First Come - First Served):
Резко зависит время работы и ожидания от порядка (1, 4, 13) и (13, 4, 1)
RR (Round Robin) - карусель:
Сильно зависит от кванта времени
Остаток времени CPU burst <= кванта времени
Остаток времени CPU burst >= кванта времени
SJF (Shortest Job First):
Невытесняющий
Вытесняющий
Теоретический
Приблежение:
t(n) - время n-го CPU burst
T(n+1) - предсказание n+1 CPU burst
a - параметр от 0 до 1
T(n+1) = a*t(n) + (1-a)*T(n), T(0) - произвольно
a = 1/2 (удобно и быстро вычислять - всего 2 машинные команды т.к. сложение и битовый сдвиг)
Алгоритм гарантированного планирования:
В системе разделения времени находятся N пользователей
Ti - время нахождения пользователя в системе
ti - суммарное процессорное время процессов пользователя
ti << Ti*N - обделен
ti >> Ti*N - любимчик
(ti*N)/Ti -коэффициент справедливости
На исполнение выбираются готовы процессы с наименьшим коэффициентом справедливости
Но на практике косяк - ибо не все время работы - полезное
}
Лекция 4 - Алгоритмы планирования {
Приоритетное планирование:
Каждому процессц процессор выделяется в соответствии с приписенным ему числовым значением - приоритетом
Параметры для назначения приоритета:
Внешние
Внутренние
Политика изменения приоритета:
Статический приоритет
Динамический приоритет
Многоуровневые очереди связью(Multilevel Queue):
Процесс, который ждал 6 лет где-то в IBM
Многоуровневые очереди с обратной связью(Multilevel Feedback Queue):
Понижение приоритета:
0 уровень - RR с квантом 8
1 уровень - RR с квантом 16
2 уровень - RR с квантом 32
3 уровень - FCFS
Возвращается в свою очередь, если CPU brust закончился, либо в более высокой очереди появился процесс
Понижается, если не хватает процессорного времени
Повышаеься, если процесс закончил ввод\вывод, либо начал интерактивные действия с пользователем.
Дисковый I\O - 2 приоритет
Интерактив - 0\1 приоритет
Для полного описания необходимо знать:
Сколько очередей в состоянии готовность
Алгоритм планирования между очередями
Алгоритмы планирования ввнутри очередей
Куда помещается вновь родившийся процесс
Правила перехода процессов их одной очереди в другую
}
Лекция 4 - Кооперация процессов и основные аспекты ее логической организации {
Причины объединения усилий процессов:
Повышение скорости решения задач
Совместное использование данных
Модульная конструкция какой-либо системы
Для удобства работы пользователя
Кооперативные или взаимодействующие процессы - влияют друг на друга путем обмена информацией
Категории средств обмена информации:
Сигнальные
Канальные
Разделяемая память
Как устанавливается связь:
Нужна или не нужна инициализация?
Способы адресации
Прямая адресация
Симметричная
Асимметричная
Напрямая или косвенная адресация
Информационная валентность процессов и средств связи:
Сколько процессов может быть ассоциированно с конкретным средством связи
Сколько идентичных средств всязи может быть задействованно между двумя процессами
Направление связи
Симплексная
Полудуплексная
Дуплексная
Особенности канальных средств связи
Буфферизация:
Буффера нет (0 емкость)
Процесс передатчик обязан ждать приема
Буффер конечной емкости
При отсутствие места в буффера, передатчки обязан ждать его освобождения
Буффер неограниченной емкости (нереализуемо!)
Процесс передатчик никогда не ждет
Модель передачи данных:
Потоковая модель
Операции приема\передачи не интересуются содержимым данных и их происхождением. Данные не структурируются
Pipe
FIFO (именнованный pipe)
Модель передачи сообщений
На передаваеммые данные накладывается определенная структура
Модель сообщений
Надежность средств связи:
Надежно, если:
Нет потери информации
Нет повреждения информации
Не нарушается порядок поступления информации
Не появляется лишней информации
Завершение связи:
Требуется ли определенная информация ОС для прекращения связи
Как влияет прекращение средства связи одним процессов на поведения других участников взаимодействия
}
Лекция 5 - Потоки (threads, нити, легковесные процессы) {
Процесс базируется на
- Владение ресурсами
- Поток исполняемых команд
Потоки имеют собственные:
Программный счетчик
Стек
Регистры
Потоки-потомки
Состояние
Потоки разделяют:
Адресное пространство
Глобальные переменнеы
Открытые файлы
Таймеры
Семафоры
Ститистическую информацию
Преимущество использования потоков:
Совместное использование данных
Легкость создания и уничтожения
Сокрытие блокирующих операций
Кооперация для обработки данных
Повышение производительности
Реализация потоков
Реализания в пространстве пользователя и ядре
Пример реализации потоков в ядре OS Windows, структура ETHREAD
Linux. Библиотека pthread, системный вызов clone
}
Лекция 5 - Планирование процессов {
*zzzzzzzzzzzzzzzzzzzzzzzzz*
}
Лекция 6 - Алгоритмы синхронизации {
Активности и атомарные операции
Активность - последовательность выполнения некоторых действий, направленных на достижение определенных целей
Например активность приготовления бутерброда
Отрезать ломтик хлеба
Отрезать ломтик колбасы
Намазать хлеб маслом
Положить колбасу на хлеб
Каждая операция атомарна, или неделима. Т.к. можно оттяпать кусок пальца
Активность - рядатомарных операций
Активность P: a, b, c
Активность Q: d, e, а
Последовательно выполнение PQ: abcdef
Режим разделение времени:
abdcef
abdecf
Interleaving - перемешивание атомарных операций между ними (переключение времени), но без перемешивания порядка между ними
Недетерминированный набор - при одинаковых начальных данных возможны разные результаты работы
Детерминированный набор - при одинаковых начальных данных всегда будет один результат
Условия Бернстайна (Bernstain)
x = u + v
y = x * w
Входоные переменные R(P) = (u, v, x, w)
Выходные переменные W(P) = (x, y)
Ecли
1) W(P) не пересекается с W(Q)
2) W(P) не пересекается с R(Q)
3) R(P) не пересекается с W(Q)
то жетерминированный.
Если P и Q - идентичны, то условия не выполняются, а активности детерминированны
Состояние гонки и взаимоисключение
P: x = 2, y = x - 1
Q: x = 3, y = x + 1
В недетерминированных наборах всегда встречается race condition
Избежать недетерминированного поведения при невежности очередности доступа можно с помощью взаимоисключения (mutual exclusion)
Критическая секция:
Состязания, кто из 3-х студентов первым купит пиво?
Вышел в магазин, купил, пренес - объединяем в атомарную операцию "Достает 6 бутылок пива"
Студент вышел, закрыл дверь, вылез в окно, остальные ждут его возвращения в окно в состоянии "готовность", пока он изнутри не отодвинет засов
Структура процесса, участвующего во взаимодействии
while (condition) {
entery section
critical section
exit section
remainder section
}
Программные алгоритмы организации взаимодействия
Требования к алгоритмам:
Программный алгоритм должен быть программым
Нет предположений об относительных скоростях выполнения и числе процессоров
Выполняется условия взаимоисключения для критических участков
Выполняется уловие прогресса (progress):
Только процессы, которые готовы войти в кти.зону принимают решение
Решение не hgbybvftncz бесконечно долго
Выполняется условие ограниченного ожидания (bound waiting)
Отсутствует дискриминация
Запрет прерываний:
while (condition) {
запретить прерывания
critical section
разрешить прерывания
remainder section
}
Но тогда если в критической секции есть косяк вроде бесконечного цикла, то все печально + юзер не может использовать подобные дерективы
Переменная-замок:
shared int lock = 0;
while (condition) {
while (lock);
lock = 1;
critical section
lock = 0;
remainder section
}
Но вдруг две программы из-за распределения времени войдут оба в открытый замок
Строгое чередование (нерпимер для двух процессов P0 и P1):
shared int turn = 0;
while (condition) {
while (turn != i);
critical section
turn = 1 - i;
remainder section
}
Нарушается требование прогресса - т.е. проесс 1 готов войти в критическую секцию и он ждет, пока процессу 0 дадут квант времени и он выставит флаг
Флаги готовности:
shared int ready[2] = {0, 0}
while (condition) {
ready[i] = 1;
while (ready[1-i]);
critical section
ready[i] = 0;
remainder section
}
Нарушается т.к. могут оба поднять флаги
Алгоритм Петерсона (очередность и флаги готовности)
shared int ready[2] = {0, 0}
shared int turn;
while (condition) {
ready[i] = 1;
turn = 1 - i;
while (ready[1-i] && turn == 1 - i);
critical section
ready[i] = 0;
remainder section
}
Команда Test-And-Set - атомарная операция проверить значения и выставить флаг
Команда Swap - поменять значения переменных местами одной операцией
}
Лекция 7 - Механизмы синхронизации {
Недостатки программынх алгоритмов:
Непроизводительная трата процессорного времени в циклах пролога
Семафоры Дейкстры
- целая разделяемая переменная
Допустимые атомарные операции
P(S): пока S == 0 , процесс блокируется
S = S - 1
V(S): S = S + 1
Проблема producer-Consumer
Semaphore mut_ex = 1
Semaphore full = 0
Semaphore empty = N
Producer:
while (1) {
produce_item()
P(empty)
P(mut_ex)
put_item()
V(mut_ex)
V(full)
}
Consumer:
while (1) {
P(mut_ex)
P(full)
get_item()
put_item()
V(mut_ex)
V(empty)
consume_item()
}
Мониторы Хора
Условные переменные
Condition C
С.wait
процесс, выполнивший операацию над переменной блокируется
C.signal
Monitor PC {
condition Full, empty;
int count;
void put() {
if (count == N)
Full.wait
put_item();
count++;
if (count == 1)
empty.signal();
}
void get() {
if (count == 0)
empty.wait;
get_item();
count--;
....
}
}
Сообщения
send, resieve
блокируется при попытке неверной операции
Семафоры, мониторы, сообщения - эквивалентны
}
root@lk3.mipt.ru:/home/public/osstud/
ls -al /home/samba/public
Лекция 8 - Управление памятью простейшие механизмы {
Память (стоимость убывает, время доступа падает)
Регистры процессора
Кэш
Оперативная - Управляется ОС, Менеджером памяти
Вторичная память - Управляется ОС
Принцип локальности
Большинство реальных программ в течении некоторого отрезка времени работают с небольшим набором адресов памяти
Связан с особенностями человеческого мышления
Проблема разрешения адресов
Человеку свойственно символическое мышление. Ардеса пермеменных описываются идентификаторами, формируя символьного адресного пространства
| - переходит в
Оперативная физическая память может быть представленна в виде массива ячеек с линейными адресами
Совокупность всех доступных физических пдресов в вычислительной системе - это ее физическое адресное пространство
Связывание адресов
Исходная программа -> Компилятор -> Объектный модуль -> Редактор связи -> Загрузочный модуль -> Загрузчик -> Двоичный образ в памяти -> Процессор и Блок Управления Памяти
-> Другие модули -> -> Системные библиотеки -> -> Динамические библиотеки ->
Логическое адресное пространство
Символьное адресное пространство - совокупность всех допустимых идентификаторов переменных
Логическое адресное пространство - совокупность всех допустимых адресов, с которыми работает процессов
Физическое адресное пространство - совокупность всех доступных физических адресов в вычислительной системе
Функции ОС и hardware для управления памятью
Отображение логического адресного пространства на физической адресного пространства
Разделение памяти между конкурирующими процессами
Контроль доступа к адресны пространствам процессов
Выгрузка процессов (целиком или частично) во внешнюю память
Учет свободной и занятой памяти
Однопрограммная вычислительная система (кто занимает младшие адреса физюпамяти)
ОС - Пользовательская
Пользовательская - ОС
Схема с фиксированными разделами
ОС в младших адресах физ.памяти
Делим память на фиксированные куски, называемые разделами памяти
Очереди заданий, которые формируются по размеру необходимой памяти
Внутренняя фрагментация
Способы организации больших программ
Оверлейная структура
Программа разбивается на несколько частей. Постоянно в памяти находится только загрузчик оверлеев, набольшое кол-во общих данных и процедур, а части загружаются по очередни
Динамическая загрузка процедур
Процедуры загружаются только по мере необходимости - только после обращения к ним
Схема с динамическими разделами
ОС - А далее очередь программ и динамические границы...
Стратегии размещения нового процесса в памяти
Первый подходящий (first-fit) Процесс размещается в первое подходящее по размеру пустое мессто
Наиболее подходящий (best-fit) Процесс размещается в наименьшее подходящее по размеру пустое место
Наименее подходящий (worst-fit) Процесс размещается в наибольшее пустое место
Внешняя фрагментация
Невозможность использования памяти, неиспользуемой процессами, из-за ее раздробелнности
Возможна и внутренная фрагметнация при почти полном занятии фрагмента, чтобы не тратить болше памяти на учет остатка (осталось 2 байта, а на его учет нужно 4 + 4 = 8 байт)
Дефрагментация
CPU - логический адрес - xor - физический адрес - память
| сегментный регистр
Линейное непрерывное отображение
Обязательно будет фрагментация, либо же придется слишком часто выполнять дефрагментацию, что достаточно трудоемко
}
Лекция 9 - Простейшие схемы управления памятью {
Блок Управления Памятью (Memory Management Unit)
Ленейное непрерывное отбражение
Линейное кусочно-непрерывное отображение
Страничная организация памяти
Логическое адресное пространство разбивается на страницы
Физическое адресное пространство разбивается на кадры
Возможна и свойственна внутренняя фрагментация
Логический адрес -> таблица страниц -> физичский адрес
Сегментная организация памяти
Разбиение фрагментами в realtime, причем для доступа нужно знать начало сегмента в оперативной памяти и сдвиг внетри сегмента
Свойственна внешняя сегментация
Сегментно-страничная организация памяти
Сегмент бьем на страницы, а память - на кадры
}
Лекция 10 - Виртуальная память {
Логическое адресное пространство процесса разбито на участки и линейно кусочно-непрерывно отображается на линейное адресное пространство
Связывание адресов происходит на этапе выполнения
В физической памяти одновременно размещаются не все участки логического адресного пространства, остальные находятся во вторичной памяти
При обращении к участку логического адресного рпостранства, находящемуся во вторичной памяти, он подкачивается в опретивную память, воззможно с выталкиванием некоторых других данных
Преимущества:
Процесс не ограничен объемом фищической памяти. Упрощается разработка программ
Повышается степерь мультипрограммирования
выгрузка во вторичную память части процесса происходит быстрее, чем выгрузка всего процесса. Повышается эффективность работы системы, использующей среднесрочное планирвоания
Необходимо хранить бит, указывающий на то, загружена ли страница в память, или же нет
Ассоциотивная память (TLB)
Среднее время досутпа к данным = h(t1+t0) + (1-h)(t1+3*t0)
Среднее время обращения к оперативной памяти t0
Среднее время обращения к ассоциативной памяти t1
Вероятность наличия информации в оассоциативной памяти - hit ratio = h
Стретегии управления виртулаьной памяти
Стратегия выборки - кодга подкачать участок
по запросу
заранее
Стратегия размещения - когда подкачать участок
Стратегия замещения - что из основной памяти убрать
Алгоритм замещения страниц
Виды алгоритмов
Локальные
Процессу выделяется определенное начальное количество кадров и только с ними он и работает
Глобальные
Можно использовать кадры других процессов
Анализ алгоритма
Строка обращений к памяти(строка запросов)
122223333111122223334444221111 -> 123123421
FirstInFirstOut - FIFO
LeastRecentlyUsed - LRU
NotFragmentlyUsed - NFU
Трешинг (Trashing)
Алгоритм границ
}
Лекция 11 - Файловые системы {
Файл, как некая абстракция, с которой удобно работь
То, как это абстракция реализована на уровне железа
Виды теоретических абстрактных файлов:
регулярный файл VS директория
линейный доступ VS произвольный доступ
Понятие текущей позиции в файле
При возврате назад, приходится возвращаться в начало и вновь доходить до нужного момента
Операции над файлами последовательного доступа
read - считать
write - записать
rewind - вернуться в начало
Операции над файлами произвольного доступа:
read - считать
write - запись
seek - установить текущую позицию
Операции над структурированными файлами:
read record - считать запись
write record - запись запись
seek - установить текущую позицию
Записи могут имать нафиксированную длину. Тогда вводятся маркеры - чтение происходит от одного маркера начала записи, до другого маркера начала
Но если я хочу положить запись вместо другой, она должна иметь строго фиксированную длину
Индексированный файл:
read record - считать запись
write record - запись запись
search - найти запись с определенным номером
Что из себя представляет пространство имен для файла?
UNIX
имя файла не содержит '\' и '0'
имя файла не превышает столько-то символов
DOS
имя_8_символов.расширение_3_символа
Операции:
new
delete
read
write
copy = read + new + write
rename - не представима в виде других операций
read attribute
set attribute
remane = set attribute
Имя - один из атрибутов файла.
Другие возможые атрибуты:
время создания
время последнего изменения
кто создал
права доступа
etc...
При введении структуры начинают меняться операции.
2 вида файлов:
регулярные - последовательный или прямой доступ
директория - структурированный файл
rewind
read record
write record
Тогда усложняется операция new
Появляется операция монтирования - одна ФС внутри другой
Внешняя и внутренняя фрагментация
Хранится в виде связанного списка
Потеря информации, => связный список может сыпаться, вводим двусвязный список
А если будем хранить эти ссылки не в блоках, а отдельно в таблице на жестком диске?
А если хранить две таблицы, вдруг одна испортится?
FAT - file allocation table
Обычно имеет 3 копии файловой таблицы
inode = index node - записи атрибутов и блоков
Функции ОС (или же файловой системы с недавнего времени):
Именования файлов и отображение имени в размещении
Учет пустого пространства
Поддержание целостности файловой системы
Надежность данных
Защита информации
Обеспечения производительностиработы с файловой системой
Связи:
Soft link
Hard link
Memory Mapped File - файл в оперативной памяти
}
Лекция 12 - Ввод-вывод {
Виды дейтельности ОС:
обработка информации
ввод-вывод
С т.з. программиста
обработка информации - выполнгения команд процессора над данными, находящимся в памяти, независимо от уровня иерархии
ввод-вывод - обмен данными между памятью и устройствами внешними по отношению к процессору
С т.з. ОС:
обрабока информации - выполнение команд процессора над данными, лежащими в памяти на уровне не ниже основной памяти
ввод-вывод - все остальное
Обработка информации
Что делается - алгоритмы и алгоритмические языки
Как делается - часть 2 курса
Операции ввода-выода
Что делается
Как делается
Общие сведения об архитектуре компьютера
Процессор Память Диск
Монитор Клавиатура
Линии и локальные магистрали. Шины.
Шины:
Данных
Адреса
Управления \ Состояния
Количество линий в шине - шириша шины
Передача данных из процессора в память:
На адресной шине выставить сигналы для адреса памяти
На шине данных выставить сигналы для данных
На шине управления выставить сигналы работы с память. и операции записи
Память и устройства I/O
Память:
локализована в пространстве
ячейки взаимно обнозначно отображаются на линейное адресное пространство
Устройство I/O
пространственно разнесены и подключаются к локальной магистрали через порты ввода\вывода
порты ввода-вывода взаимно однозначно отображаются на линейное пространство ввода-вывода (иногда на линейное адресное пространсво в памяти)
Передача информации из процесса в порт, отображенный в адресное пространство ввода-вывода
на адресной шине выставить сигналы для адреса порта
на шине данных выставить сигналы для данных
на шине управления выставить сингалы работы с устройствами ввода-вывода и операции записи
Память и устройства I\O
Занесение информации в память завершает операцию записи
Занесение информации в порт часто инициализирует реальное совершение ввода-вывода
Что делать после получаения информации через порт и как предостаить информацию... Аррррргх!!! А пофиг, в принципе
Устройства ввода вывода подключа.тся к локальной магистрали через порты
Могут существовать два адресных пространства (памяти и ввода-вывода)
Порты обычно отображаются в адресное пространство, иногда - в адресное пространство памяти
Какое адресное пространство использовать - определяется типом команды или операнда
Управлением занимаются контроллеры
Структура контроллера устройства:
Регистр состояния
Read Only
Бит занятости
Бит готовности данных
Бит ошибки
Регистр управления
Write Only
Биты кода команды
Биты режима работы
Биты готовности команды
Регистр выходных данных
Read Only
Регистр входных данных
Write Only
Процессор
Контроллер
Чтение из порта регистра состояния, пока устройство занято
Запись кода команды в порт регистра управления
Занести данные в порт регистра входных данных контроллера устройств
Запись бита готовности команды в порт регистра управления
Установить бит занятости
Анализ кода команды. Инициализация операции вывода
После завершения операции - сбросить бит готовности команды
Быставить бит ошибки и сбросить бит занятости
Чтение из порта регистра состояния (и считывание кода ошибки, например)
Polling или опрос устройств - достаточно медленно
Линия внешних прерываний - возможность уйти от polling
После выполнения команды процессор обнаруживает сигнал на линии прерываний
Сохраняет часть регистрв
Передает управление по зранее определенному адресу
Обрабатывает прерывание
Но если много устройств, то что делать?
Опрашивать кто из них дал прерывание - т.е. тоже polling устройств, а не регистров состояния и только после вызова прерывания
Контроллер прерываний
В него входят линии прерывания всех устройств, с процессором связан своей шиной. Он может на своей шине обработать и передать номер устройства с прерыванием
Прямой доступ к памяти (Direct Memory Access)
Контроллер DMA программируется
После получения сигнала от устройства I\O pfghfibdftn e ghjwtccjhf eghfdktybz vfubcnhfkm.
Gjkexbd eghfdktybt? dscnfdkztn flhtc b bpdtoftn ecnhjqcndj I/O
Использование шины данных с устройством I/O - передает информацию
}
Лекция 13 - Система управления вводом-выводом {
Внешние прерывания, исключительные ситуации и программные прерывания
Поддержка протоколов
Порты -> адресное пространство
Номер прерывания
Номер канала DMA
Внешние прерывания
Обнаруживаются процессором _между_ выполнением команд
Сохраняется часть контекста перед выполнением _следующей_ команды
_Не связаны_ с работой процессора и _непредсказуемы_
Исключительные ситуации
Обнаруживается _во время_ выполнения команды
Сохренение части контекста перед выполнением _текущей_ команды
_Связаны_ с работой процессора, но _непредсказуемы_
Программные прерывания
Происходят _в результате_ выполнения команды
Сохраняется часть контекста перед выполнением _следующей_ команды
_Связаны_ с работой процессора и _предсказуемы)
Основные направления различия устройств ввода-вывода
Скорость обмена информацией (от нескольких байтов до нескольких гигбайтов в секунду)
Возможность использования несколькими процессорами параллельно
Запоминение введенной информации для последующего ввода
Символьные и блочные
Только для ввода информации, только для вывобда информации и read-write устройства
etc
=> многоуровневая структура
Структура системы ввода-вывода
Клавиатура, мышь, монитор, IDE диски, SCSI контроллер - hardware
Контроллеры - hardware
Драйвера - software
Базовая подсистема - software
Остальные части ядра ОС и пользовательские процессы - software
Систематизация внешних устройст
Символьные
Клавиатура
Можем
Терминал
Блочные устройства
Магнитные и оптические диски
Ленты
Сетевые устройства
Сетевые карты
Все остальное
Таймеры
Графические дисплеи
Видеокамеры
Символьные устройства
get - прочитать символ
put - вывести символ
Блочные устройства
read - прочитать блок
write - записать блок
seek - найти блок
Допольнительные функции
ioctl - вывести любые данные в любой порт контроллера
open - (ре)инициализировать устройство
close - временно завершить работы с устройством
stop - остановиьт работу драйвера
halt - остановить устройство
poll - опросить состояние устройства
Функции базовой подсистемы ввода-вывода
Поддержка блокирующихся, неблокирующихся и асинхронных вызовов
Буферизация и кэширование входных и выходных данных
Осуществления spooling'a и монопольного захвата внешних устройств
Обработка ошибок и прерываний
планирование последовательности запросов на выполнение операций ввода-вывода
Блокирующиеся, неблокирующиеся и асинхронные вызовы
При блокирующемся системном выхове процесс переходит из состояния "исполнение" в состояние "ожидание". После выполнения операций в полном объеме он разблокируется
При неблокирующемся системном вызове операции ввода-вывода могут быть выполненны неполностью. Процесс либо неблокируется совсем, либо блокирутся не более чем на определенное время
При асинхронном системном вызове процесс никогда не блокируется. Операции ввода-вывода выполняются в полном объеме
Например процесс пнул ОС и дальше опрашивает, закончила ли она что-то
Буферизация и кэширование
Буфер - область памяти для запоминания информации при обмене данными медлу устройствами, процесссами или между устройством и процессом
Разные скорости приема и передачи информации участников обмена
Разные объемы данных, которые могут быть приняты или переданы участниками обмена единовременно
Необходимость копирования данных из приложения в ядро ОС и обратно
Кэш - область быстрой памяти, содержащая копию данных, расположенных где-либо в более медленной памяти, предназначенноая для ускорения работы вычислительной системы
Разница между буфером и кэшем
Буфер служит для согласования параметров участников обмена информацией и для ее промежуточного хранения. Кэш применяется для ускорения доступа к данным
Кэш всегда хранит копию данных, существующих где-то еще. Буфер часто содержит единственный экземпляр данных в системе
Spooling и захват устройств
Способы использования неразделяемых устройств
Монопольный захват устройства
Spooling
Spool - буфер, содержащий входные или выходные данные для устройства, на котором следует избегать чередования его использования различными процессами
Обработка прерываний и ошибок
Действия ОС
Определение устройства, выдавшего прерывание
Взаимодействие с устройством
Проверка успешности выполнения операции
Попытка устранения возможных ошибок
Определение процесса, ожидающего это прерывания. Перевод его из состояния "ожидание" в состояние "готовность"
Если еще есть процессы с неудовлетворенными запросами к этому устройству - инициализация нового запроса
Действия по обработке прерывания и компенсации ошибок могут быть частичто делегированы драйверу устройства - функция intr в инерфейсе драйвера
}
Лекция 14 - Система управления вводом-выводом {
Планирование запросов
Для блокирующихся и ассинхронных системных вызовов
При занятости устройства запрос ставится в очередь к данному устройству
После освобождения устройства необходимо принять решение: какой из запросов в очереди инициировать слудующим - планирование запросов
Действия по планированию процессов могут быть частично или полностью делегированы драйверу устройства - функция strategy винтерфейсе драйвера
Алгоритмы планирвоания запросов к жесткому диску
Параметры планирования
Запрос характеризуется
Тип операции
Номер цилиндра
Номер дорожки
Номер сектора
Параметр планирования - время, необходимое для выполнения запроса
T = Transfer time + positioning time
Positioning time = seek time + positioning latency
Единственное, что можно оптимизировать - seek time