ДСв18_01-введение (1238932)
Текст из файла
Carnegie MellonВведениеОсновы информатикиКомпьютерные основы программированияgoo.gl/eY1xtHНа основе CMU 15-213/18-243:Introduction to Computer Systemsgoo.gl/Q7vgWw• Лекция 1, 05 февраля, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.ruw27001.vdi.mipt.ru/wp/?page_id=3461Литература¢Randal E. Bryant and David R. O Hallaron,§ Computer Systems: A Programmer s Perspective, Third Edition (CS:APP3e),§ http://csapp.cs.cmu.edu¢¢¢¢Взгляд программиста§ Брайант Р. , О`Халларон Д. Компьютерные системы: архитектура ипрограммирование.
ISBN 5-94157-433-9Учебник по Ассемблеру§ Ирвин, Кип. Язык ассемблера для процессоров Intel, 4е издание.ISBN 5-8459-0779-9Справочник по Ассемблеру§ Юров В.И., Assembler: Специальный справочник. ISBN 5-469-00003-6Учебник по архитектуре§ Э. Таненбаум Архитектура компьютераISBN 5-469-01274-32Первоисточники¢http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/index.html3Идея курса:Абстракции хороши, но знайте страшную правду¢1-й семестр посвящён абстракциям§ Абстрактные типы данных§ Асимптотический анализ производительности¢Абстракции имеют ограниченное применение§ Особенно при наличии ошибок§ Требуют понимания деталей реализации¢Предполагаемая польза данного курса:§ Ваш личный рост как эффективного программистаСпособность эффективно находить и устранять ошибки§ Способность улучшать быстродействие программ§ Подготовка к следующим компьютерным курсам§ Операционные системы, сети, компиляторы,…§4Страшная правда №1:Int-ы не целые, float-ы не вещественные¢Пример 1: x2 ≥ 0 ?§ Для float-ов: Да!§ Для int-ов:§§¢40000 * 40000 ➙ 160000000050000 * 50000 ➙ ??Пример 2: (x + y) + z = x + (y + z) ?§ Для unsigned и signed int-ов: Да!§ Для float-ов:§§(1e20 + -1e20) + 3.14 --> 3.141e20 + (-1e20 + 3.14) --> ??5Carnegie MellonАрифметика компьютера¢Не создаёт случайных значений§ У арифметических операций есть важные математические свойства¢Не предполагает всех “обычных” математических свойств§ Из-за ограниченности представления§ Целочисленные операции удовлетворяют свойствам «кольца»Коммутативность, ассоциативность, дистрибутивность§ Операции с плавающей точкой удовлетворяют свойству«упорядоченност軧 Монотонность, знаки§¢Наблюдение§ Необходимо понимать в каком случае какие абстракции применять§ Важно для разработчиков компиляторов и ответственных приложений6Страшная правда №2:Вы должны знать ассемблер¢Вероятно, вы никогда не будете программировать наассемблере§ Компиляторы много эффективнее и терпеливее вас¢Но: Понимание ассемблера – ключ к модели исполнениямашинного уровня§ Поведение программ при наличии ошибокМодели высокоуровневых языков – терпят неудачу§ Улучшение быстродействия программ§ Понимание оптимизаций [не]сделанных компилятором§ Понимание источников неэффективности программ§ Реализация системного ПО§ Цель компилятора – машинный код§ Операционная система управляет состоянием процесса§ Создание вредоносного кода и противодействие ему§ ассемблер x86 для ПК, ARM для мобильных, MIPS для IoT – то что надо!§7Пример ассемблерного кода¢Счётчик метки времени§ Специальный 64-битовый регистр в Intel-совместимых машинах§ Увеличивается с каждым циклом§ Считывается командой rdtsc¢Применение§ Измерение времени (в циклах) требуемого программойdouble t;start_counter();P();t = get_counter();printf("P требует %f циклов\n", t);8Код читающий счётчикНапишем немного ассемблерного кода, используя возможностьассемблерной вставки¢ Ассемблерный код вставляется в машинный код, порождаемыйкомпилятором¢static unsigned cyc_hi = 0;static unsigned cyc_lo = 0;/* Поместить в *hi and *lo старшие и младшие биты счётчикациклов.*/void access_counter(unsigned *hi, unsigned *lo){asm("rdtsc; movl %%edx,%0; movl %%eax,%1": "=r" (*hi), "=r" (*lo):: "%edx", "%eax");}9Страшная правда №3: Память имеет значение,ОЗУ(RAM) – далёкая от реальности абстракция¢Память не является неограниченной§ Память требует размещения и управления§ Во множестве приложений доминирует память¢Ошибки ссылок на фрагменты памяти – самые вредные§ Эффекты отстоят от причины во времени и пространстве¢Быстродействие памяти не однородно§ Эффекты кэша и виртуальной памяти значительно влияют набыстродействие§ Адаптация программы к характеристикам подсистемы памяти – основнойрезерв улучшения быстродействия10Carnegie MellonПример ошибки ссылки в памятьtypedef struct {int a[2];double d;} struct_t;double fun(int i) {volatile struct_t s;s.d = 3.14;s.a[i] = 1073741824; /* Возможно за границами допустимого */return s.d;}fun(0)fun(1)fun(2)fun(3)fun(4)fun(6)➙➙➙➙➙➙3.143.143.13999986648562.000000610351563.14Segmentation fault§ Результат зависит от архитектуры11Carnegie MellonПример ошибки ссылки в памятьtypedef struct {int a[2];double d;} struct_t;fun(0)fun(1)fun(2)fun(3)fun(4)fun(6)➙➙➙➙➙➙3.143.143.13999986648562.000000610351563.14Segmentation faultПояснение:struct_tЧасть сохранённого состояния6?5?4d7 ...
d43d3 ... d02a[1]1a[0]0Ячейки изменённыеfun(i)12Ошибки ссылок в память¢C и C++ не обеспечивают защиты памяти§ Выход за границы массивов§ Негодные значения указателей§ Некорректное использование malloc/free¢Могут приводить к скверным последствиям§ Эффект ошибки проявляется в зависимости от системы и компилятора§ Отложенное действи姧¢Повреждённый объект логически не связан с тем, к которомувыполняется доступЭффект ошибки может наблюдаться много позже возникновенияЧто с этим делать?§ Программировать на Java, Ruby, Scala, ML, …§ Понимать, какие возможные взаимодействия могут возникнуть§ Использовать или создавать средства обнаружения (напр. Valgrind)13Страшная правда №4: Быстродействие –не сводится к асимптотической сложностиПостоянные множители тоже имеют значение!¢ И даже точный подсчёт операций не предсказываетбыстродействия¢§ Легко увидеть 10-кратную разницу в зависимости от написания кода§ Оптимизация должна производиться на нескольких уровнях :алгоритм, представление данных, процедуры, циклы¢Для оптимизации необходимо понимать систему§ Как программы компилируются и исполняются§ Как измерять быстродействие программ и обнаруживать узкие места§ Как улучшать быстродействие не нарушая модульности и общности кода14Пример производительности памятиvoid copyij(intint{int i,j;for (i = 0; ifor (j = 0;dst[i][j]}src[2048][2048],dst[2048][2048])< 2048; i++)j < 2048; j++)= src[i][j];4.3msvoid copyji(intint{int i,j;for (j = 0; jfor (i = 0;dst[i][j]}2.0 GHz Intel Core i7 Haswellsrc[2048][2048],dst[2048][2048])< 2048; j++)i < 2048; i++)= src[i][j];81.8msИерархическая организация памяти¢ Производительность зависит от организации доступа¢§ включая способ перебора многомерного массива15Почему производительность разная ?copyijПроизводительность чтения (Mбай/с)160001400012000100008000600040002000copyji0s1s3s52ms7Шаг выборки (x8 байт) s98ms11128m32m512k128k32kРабочий набор (байт)16Страшная правда №5: Компьютеры нетолько исполняют программы¢Компьютеры вводят и выводят данные§ Подсистема ввода/вывода критически значима для надёжности ибыстродействия программ¢Компьютеры взаимодействуют друг с другом в сети§ Многие проблемы системного уровня порождаются сетью§§§§Параллельное выполнение автономных процессовКопирование на ненадёжный носительМежплатформенная совместимостьСложные проблемы производительности17Картина курса в целом¢Курс помещает программиста в «центр картины»§ Цель – показать как стать более эффективным программистом знаябольше об используемой системе§ Даёт вам возможность§ Создавать более надёжные и эффективные программы§ Это не курс для посвятивших себя хакерству§ Хакер сидит в каждом18Понятия программируемых действийПрограммаопределённый наборпредписанийПрограммаДанныенеопределённый набор битДанныеИсполнительРесурсыПроцессПроцессожидаемый набор событийРесурсы§ Время§ Энергия§ Пространство19Масштабы событийЦПАЛУОсновнаяпамятьУУУBBУBBУBBУBBРегистрыКрупнее: среда исполнения¢Загрузка кода программы¢Выделение ресурсов¢¢Среда взаимодействияПрограмма¢ Ваш процесс§§¢Выполнение командИзменение состоянияДругие процессыНормирование работы иреагирование на запросыОсвобождение ресурсовМельче: команда¢¢¢¢¢Выборка кода операцииДекодирование операцииВыборка операндовВыполнение операцииСохранение результата20Создание программыРедактирование⇓ Текст программыТрансляция⇓ Объектный кодКомпоновка⇓ Загрузочный кодЗагрузка⇓ Исполняемый кодВыполнение, отладка⇓ Результат21Создание программы вместеРедактирование⇓ Текст программыВаши изменения вручнуюТрансляция⇓ Объектный кодБиблиотечный исходный текстКомпоновка⇓ Загрузочный кодБиблиотечный машинный кодЗагрузка⇓ Исполняемый кодРешения среды исполненияВыполнение, отладка⇓ РезультатВнешние данные, коды, события22Создание программы в окруженииРедактирование⇓ Текст программыТрансляция⇓ Объектный кодКомпоновка⇓ Загрузочный кодЗагрузка⇓ Исполняемый кодG Предписания редакторуВаши изменения вручнуюE Предписания трансляцииБиблиотечный исходный текстE Предписания компоновкиБиблиотечный машинный кодE Предписания загрузкиРешения среды исполненияВыполнение, отладка E Предписания исполнения⇓ РезультатВнешние данные, коды, события23Алгоритм¢Определение (ISO 2382/1-84)§¢Свойства1.2.3.4.5.¢Конечный набор предписаний, определяющий решение задачипосредством конечного количества операцийДискретность: данных и действий над нимиПонятность: доступность и однозначность предписанийКонечность: решение задачи - за конечное число шаговОпределённость: воспроизводимость результатаМассовость: применимость к различным даннымПредставление - программа на формальном язык姧§§Действия: операции и операторыДанные: типы и экземплярыОрганизация: конструкции сложных данных и действийОкружение: взаимодействие со средой выполнения24Модели, языки, машины¢¢¢Модель – упрощённоепредставление законовповедения частей иотношений системыЯзык модели - знаковаяподсистема фиксации,переработки и передачиинформации.Машина – модельныйисполнитель, которомунаправленыпредписаниямодельного языка.Рынки¢ Потребители¢ Задачи¢Алгоритмы¢ Программы¢ Система/Аппаратура¢ Цифровые схемы¢ Аналоговые схемы¢Физические явления в[не]линейных структурах¢25Место ассемблера и архитектурыМодель – упрощённоепредставление законовповедения частей иотношений системы¢ Язык модели - знаковая...
фиксации,подсистемапереработкии передачиязыкинформации.ассемблера¢ Машина – модельный--------------------исполнитель, которомуязыкнаправленыпредписанияархитектурымодельного языка.¢команд...Рынки¢ Потребители¢ Задачи¢Алгоритмы¢ Программы¢ Система/Аппаратура¢ Цифровые схемы¢ Аналоговые схемы¢Физические явления в(не)линейных структурах¢26… среди компьютерных языков¢Алгоритмы¢Языки спецификаций¢Языки высокого уровня¢Программы¢Язык ассемблера¢Архитектура системы¢Язык системных вызовов¢Архитектура аппаратуры¢Язык команд аппаратуры¢Блоки архитектуры¢Язык микрокоманд¢Цифровые схемы¢Язык цифровых схем¢Аналоговые схемы¢Язык аналоговых схем27Carnegie Mellon(Само)обман¢Что есть (само)обман ?§§§§§¢Брать чужой код: копируя, перенабирая, подглядывая, принимая файлыПересказывать: устное описание кода одним человеком другомуНатаскивание: помощь другу в построчном написании заданийПоиск решения в сетиКопирование кода предыдущих кусов и экзаменовЧто НЕ есть (само)обман?§ Объяснять как использовать инструменты или системы§ Помогать другим в вопросах конструкции верхнего уровня28Рекомендации к практической работеЗапустить пример со счётчиком циклов§ Слайд 9¢ Запустить пример с перестановкой индексов§ Слайд 15¢ Найти способ выдачи ассемблерного листинга¢29.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
