CSCB007 Операционни системи

Info

Записки от лекциите по CSCB007 Операционни системи, водени от доц. Росица Голева д-р.

Въведение

An Operating System is a program that acts as an intermediate interface between a user of a computer and the computer hardware.

Ако разделим ресурсите (диск, памет, мрежа, периферия, процесор) от консуматорите (потребители и програми), ОС се грижи за връзката между двете.

Преимущества на UNIX ОС:

• малко по размер
• гъвкава
• евтина

Недостатъци на UNIX ОС:

• няма поддръжка
• съдържа бъгове
• малко (или често никаква) документация

Преимуществата са надделяли на времето над недостатъците.

Services на OS

Services в помощ на потребителя:

• User Interface
• Program Execution
• I/O operations
• File-system manipulation
• Communications
• Error detection

Services за разпределение на ресурсите:

• Resource allocation: when multiple users or multiple jobs running concurrently, resources must be allocated to each of them;
• Accounting: to keep track of which users use how much and what kinds of computer resources;
• Protection & Security:
  • Protection: involves ensuring that all access to system resources is controlled;
  • Security: of the system from outsiders requires user authentication, extends to defending external I/O devices from invalid access attempts

Command Line Interface

Command interpreter allows direct command entry. Primarily fetches a command from user and executes it. It can be implemented directly in kernel, or alternatively by systems program - shell. Several shells are possible.

Commands of a shell can be built-in, or be just names of programs. If the latter, adding new features doesn’t require shell modification.

End-user and end-device interfaces

GUI

User-friendly desktop metaphor interface. Usually needs mouse, keyboard, and monitor. Icons represent files, programs, actions, etc. Various mouse buttons over objects in the interface cause various actions (provide information, options, execute function, open directory (known as a folder).

System calls

System Calls provide Programming interface to the services of the OS. Mostly, they are accessed by programs via a high-level Application Program Interface (API) rather than direct system call use.

Typically, a number is associated with each system call. This number is often, but not always, called PID – Process Identifier.

System-call interface maintains a table indexed according to these numbers. The system call interface invokes intended system call in OS kernel and returns status of the system call and any return values.

Three methods used to pass parameters to the OS:

• (simplest) pass the parameters in registers. In some cases, may be more parameters than registers (pass by value in C)
• Parameters stored in a block, or table, in memory, and address of block passed as a parameter in a register (pass by pointer in C)
• Parameters are placed, or pushed onto the stack by the program and popped off the stack by the operating system;

Block and stack methods do not limit the number or length of parameters being passed.

OS as a…

Resource Manager

• Manages and protects multiple computer resources: CPU, Processes, Internal/External memory, Tasks, Applications, Users, Communication channels, etc;
• Handles and allocates resources to multiple users or multiple programs running at the same time and space (e.g., processor time, memory, I/O devices);
• Decides between conflicting requests for efficient and fair resource use (e.g., maximize throughput, minimize response time);

Control Program

• Manages all the components of a complex computer system in an integrated manner;
• Controls the execution of user programs and I/O devices to prevent errors and improper use of computer resources;
• Looks over and protects the computer: Monitor, Supervisor, Executive module, Controller, Master, Coordinator, etc;

Command Executer

• Interfaces between the users and machine.
• Supplies services/utilities to users.
• Provides the users with a convenient CLI (Command Line Interface), also called a Shell (in UNIX), for entering the user commands.

Virtual Machine

An interface between the user and hardware that hides the details of the hardware (e.g., I/O). Constructs higher-level (virtual) resources out of lower-level (physical) resources (e.g., files).

Definition: OS is a collection of software enhancements, executed on the bare hardware, culminating in a high-level virtual machine that serves as an advanced programming environment.

virtual machine = software enhancement = extended machine = abstract machine = layer = level.

Mainframe Systems

Simple Batch System

A simple batch system consists of:

• Monitor: resident software that controls the sequence of events;
• Memory protection: some memory areas are accessible only to the monitor
• Privileged mode instructions: only accessible to the monitor
• Interrupts (early machines did not have this)

Such a system reduces setup time by batching similar jobs:

• Initially control is given to the monitor;
• The monitor automatically transfers control from one job to another;
• When a job completes control is transferred back to the monitor.

Uniprogramming vs Multiprogramming

Uniprogramming: one job (program) at a time; Processor must wait for I/O instructions to complete before proceeding

Multiprogramming: switching between jobs when possible; When one job needs to wait for I/O, the processor can switch to the other job; event driven and time slotted;

Архитектура и организация

Компютри с фон Нойманова архитектура

Компютърна архитектура

Под архитектура на компютърна система се разбира начина, по който са свързани и взаимодействат отделните части на компютъра. Обикновено архитектурата на компютърната система се представя чрез блокова схема. От системна гледна точка, компютърът е система, която получава входна информация (данни), обработва информацията и показва получените резултати. От функционална гледна точка, компютърът е изграден от следните функционални компоненти:

1. Данни: това, което се обработва
2. Хардуер: компоненти, които реализират технологиите използвани в компютъра
3. Софтуер: множество от компютърни програми, осъществяващи обработката на информацията
4. Периферия: обикновено външни устройства, подключени към основния компютърен компонент за въвеждане/извеждане на информацията
5. Потребителски интерфейс: хардуерни или софтуерни средства за връзка с потребителя
6. Комуникация: хардуерни или софтуерни средства за връзка с други компютри/устройства/системи

Компютри с фон Нойманова архитектура

по избор: През 1945-1946г. Джон фон Нойман въз основа на натрупания опит е стигнал до извода за целесъобразността от двоичното представяне на числата и данните и за съхраняването им в една памет. Тези негови възгледи са заложени в първия действащ компютър UNIVAC, в който на практика е реализиран компютъра на Джон Атанасов.

• Използването на два знака (0 или 1) опростява електронните схеми в процеса, което ги прави по-надеждни и по-малко грешат
• За физическата реализация на 0 и 1 се използват различни състояния:
  • високо / ниско напрежение
  • включен / изключен светлинен поток
  • незареден / зареден кондензатор

Принципи на фон Нойман

• Първи принцип:
  • компютърът е електронно устройство;
  • всичко в него се извършва от електронни схеми.
• Втори принцип:
  • информацията в компютъра се представя в двоична бройна система;
  • всички операции се изпълняват от електронни схеми над операнди, представени в двоичен код;
  • електронните схеми работят на основата на булевата алгебра.
• Трети принцип:
  • компютърът е програмно управляемо устройство;
  • програмите и данните се съхраняват в памет

Схема

Основни компоненти

Процесор

Процесорът управлява цялостната работа на компютъра. Изпълнява набор от инструкции, изпълнявайки по този начин някакъв алгоритъм.

Електронните схеми се сглобяват от примитивни електронни елементи, реализиращи булевите функции конюнкция, дизюнкция и отрицание.

Компоненти на процесора:

• Аритметико-логическо устройство (АЛУ): изграден от логически схеми. Извършва аритметични и логически операции.
• Управляващо устройство (УУ): този блок управлява всички функции на CPU: какви операции трябва да бъдат извършени, кога трябва да бъдат извършени и кои компоненти на CPU участват в тези операции.
• Магистрали - проводници, по които се предават данни, адреси и управляващи и синхронизиращи сигнали от едно устройство към друго. Процесорът има вътрешни магистрали, които използва за предаване на данни, инстуркции, конфигурации и състояния между неговите компоненти. Съществуват и магистрали за обслужване на външни устройства, които представляват линии за прекъсване и взимане на състояние на устройствата.
• Регистри: малки и бързи памети. Променливите и указателите се “местят” от оперативната памет в регистрите, когато се използват от процесора. Това ускорява обработката. Типове регистри:
  • регистри за данни - помнят данните,
  • адресни регистри - помнят адреси (за чете или писане),
  • регистри за инструкции - помнят текущата инструкция,
  • брояч на инструкциите - помни адреса на следващата инструкция
  • регистри за флагове - групирани отделни битове, които представят състоянието на дадена операция или на процесора
  • конфигурационни регистри: някои от функциите на процесора могат да бъдат конфигурирани. Конфигурационните регистри съдържат текущата конфигурация на процесора. Те също могат да съдържат информация за адресирането, например, коя част от паметта е защитена и коя не.
• Флагове: индикатори, които показват състоянието на системата. Всеки флаг е представен с един бит.
• Буфери: тип памет, която съхранява резултата от работата на процесори различни от главния процесор (напр. видеопроцесори, процесори за входно-изходни устройства, т.н.). Когато някой процесор се нуждае от резултата на друг процесор, той го изтегля от буфера.
• Стек: временна памет. Процесорът извършва със стека две операции:
  • да запомни стойност на регистър на върха на стека;
  • да отстрани данните от върха на стека и да ги запомни в регистър.
• Входно-изходни портове: осъществяват връзки между процесора и външните устройства.
• Централен процесорен блок (CPU): извършва изпълнението на всички инструкции, както и необходимите изчисления за определяне на различните адреси
• Вътрешна памет: малка, много бърза памет, предназначена за вътрешни (бързи) изчисления, без обръщения към оперативната памет
• Буфер за данни: двупосочно устройство, което съхранява изходящите данни (докато магистралата на паметта стане готова да ги приеме) и входящите данни (докато CPU стане готов за тях)
• Адресни тригери: група от тригери, управляващи адресите от паметта, с които процесорът желае да обменя данни
• Декодер на инструкциите: всички инструкции се помнят в двоични стойности. Декодерът получава инструкцията от паметта, интерпретира стойността, за да определи какво да се извърши, и указва на АЛУ и регистрите кои електронни схеми да се активират, за да се изпълни инструкцията.

Как работи процесорът:

1. УУ извлича от ОП (оперативна памет) инструкциите, чийто адрес е в брояч на инструкциите.
2. След това инструкцията се анализира, като се определят какво да се изпълни и кои са адресите, в които се съхраняват данните, необходими за изпълнение на инструкцията
3. Данните се извличат от адресите.
4. За изпълнение на инструкцията се стартира съответната логическа схема.
5. След изпълнение на инструкцията се определя ново съдържание на брояч на инструкциите

Всеки процесор изпълнява набор от инструкции. Инструкциите се декодират в двоични числа, наречени машинен код. Процесорът може да изпълнява единствено машинен код на неговия машинен език. Това е езикът на най-ниско ниво, езикът на схемите.

За да се окажат два сигнала на входа на един елемент в едно и също време, е необходимо да се синхронизира тяхното движение. Това се постига, като процесите на изчисление се извършват на тактове.

Ритъмът / тактовете за работа на процесора се задават от устройство, наречено тактов генератор. Колкото по-висока е честотата на тактовия генератор, толкова по-бързо ще работи компютърът.

Памет

Паметта е изградена от електронни компоненти, наречени тригери, организирани във вид на матрица.

Тригерът е проста електронна схема, която има на изхода си само две стабилни състояния, условно обозначени като 0 и 1.

Матрицата от клетки памет е организирана така, че всеки ред представлява множество битове, които се намират на един адрес и в които могат да се записват инструкциите или данни. Колоните представляват различните битове в това множество. Паметта изглежда като матрица, където броят на редовете определя броят различни адреси от паметта, а броят на колоните определя броят битове на всеки адрес.

За да запише или извлече данни от паметта, процесорът трябва да подаде двоичния код на адреса на специални шини, наречени адресни (address lines).

Клетките от сътоветния адрес се свързват с двупосочни шини за данни (data lines), които позволяват да се прочете информацията от тези клетки.

Обменът на данни между процесора и паметта се контролира чрез линии за три допълнителни сигнала:

• chip select (избор на схема)
• read enable (разрешено четене)
• write enable (разрешен запис).

Адресният декодер (address decoder) е електронна схема с входа и изхода, при която само един изход ще остане активен, ако се появи комбинация от нули и единици на неговите входове. Така адресният декодер избира точно един ред от матрицата, в който пишем или от който четем.

Пример, ако на адресните шини се появи числото , се избира третия ред от паметта и той се свързва с шината за данни.

Процесорът използва входовете read enable и write enable, за да определи дали ще четем или ще записваме в избраният ред от матрицата на паметта. Тези сигнали са ниско активни¹. read enable и write enable никога не могат да бъдат активни едновременно.

Входът chip select разрешава или забранява схемата на паметта. Причината е, че процесорът работи с много памети и в даден момент трябва да комуникира само с една. Ако chip select е 0 ⇒ паметта е активна и всички нейни входни и изходни сигнали се използват за предаване на данни.

За да няма колизия и при използване на шината за данни от различни устройства, се използва chip select. Всяко устройство памет има свой собствен вход chip select, и не е възможно по едно и също време два сигнала chip select, на две различни устройства, да са нули.

Типове памет

Оперативна:

• RAM:
  • съхранява данните и програмите, които се използват в момента
  • контролира се от ОС
  • бърза при четене и запис
  • при изключване се губят записаните данни
  • има два вида:
    • SRAM (static RAM) - по-бърза, но скъпа
    • DRAM (dynamic RAM)
• ROM:
  • памет само за четене
  • фабрично записана
  • не се чисти при изключване
  • процесорът може да се записва в нея само със специални допълнителни механизми
• Cache:
  • междинна памет, в която процесора чете преди да се обърне към RAM
  • за кеш се използва SRAM
  • може да бъде разделена на две: кеш памет за инструкции и кеш памет за данни
• Регистър:
  • малка бърза памет за специфични функции: да запомни цяло число, адрес от паметта, да конфигурира входно/изходно устройство или да покаже състоянието на процеса.

Шини

Адресните шини се контролират изцяло от процесора и се използват за да се определи с кой ред от матрицата на паметта процесорът желае да комуникира. Понеже този единствен ред може да се намира в различни схеми памет, адресните шини се използват и за определяне на коя схема памет е разрешена.

По управляващите шини текат сигнали, използвани за управление на процеса на предаване на данни - кога се предават данните, в коя посока и др. Процесорът контролира управляващите шини.

Периферни устройства

Компонент от фон Нойманова архитектура. Може да бъдат принтери, скенери, клавиатура, мишка и др.

---

Link to original

Процеси

A process is a single unit consisting of sequentially implemented events. The term is also used for the description of such unit.

The operating system must:

• allocate resources to processes,
• enable processes to share and exchange information,
• protect the resources of each process from other processes,
• enable synchronisation among processes.

To meet these requirements, the operating system have to maintain an appropriate data structure for each process that describes the state and resource ownership of that process and that enables the operating system to exert process control.

The data structure is called “process control block”:

• identifier: to distinguish it from all other processes
• state: is the process running, ready, blocked, etc
• priority: priority level relative to other processes
• program counter: the address of the next instruction to be executed
• memory pointer: includes pointers to the program code and associated data
• context data: data present in registers in the process while the process is executing
• I/O status: outstanding I/O requests, I/O devices assigned to this process, a list of files in use by the process, etc
• accounting: running time used, time limits, account numbers, etc

All this information allows for the process to be interrupted and then resumed, as if the interruption had not occurred.

In order to create a new process the OS builds a data structure to manage it, allocates memory and assigns the process to the queue. OS takes the process out of the queue, de-allocates and deletes the data structure associated with the process.

Five State models & transition of states:

• Null → New
• New → Ready
• Ready → Running
• Running → Exit
• Running → Ready
• Running → Blocked
• Blocked → Ready
• Ready → Exit (user terminated)
• Blocked → Exit (user terminated)

Processor is faster than I/O so many processes could be waiting for I/O. The idea of swapping is to move these processes to disk to free up more memory and use processor on more processes.

Suspended Processes:

A new state – ”suspend” must be introduced to describe the situation Blocked state becomes suspend state when swapped to disk. Processes in Ready, Running or Blocked state are in the main memory.

Reasons for suspending:

• swapping
• other os reason
• interactive user request
• timing
• parent process request

Suspending Processes with 2 suspend states:

• Blocked/Suspended
• Ready/Suspended

Process control with the 2 new states:

• New → Ready: if there are enough available resources
• New → Ready/Suspended: if higher priority processes are consuming the available resources
• Ready → Ready/Suspended: can be moved between Ready and Ready/Suspend state depending on their priority
• Blocked/Suspended → Ready/Suspended: if the unblocking event has occurred
• Blocked/Suspend → Blocked: depending on priority or expectations of soon unblocking
• Running → Ready/Suspended: if higher priority processes need the available resources

Complete specification of a process is kept in a process image. For managing different processes OS maintains a primary process table with one entry for each process. Each entry contains, at least, a pointer to a process image.

Management tables

Memory tables are used to keep track of both main and secondary memory. Must include information for:

• Allocation of main/secondary memory to processes
• Protection attributes for access to shared memory regions
• Information needed to manage virtual memory

I/O Tables are used by the OS to manage the I/O devices of the computer. The OS needs to know:

• Whether the I/O device is available or assigned
• The status of I/O operation
• The location in main memory being used for the I/O transfer

File tables provide information about:

• Existence of files
• Location on secondary memory
• Current Status
• Other attributes. Sometimes this information is maintained by a file management system.

Process Image

A complete process specification consists of:

• A program or set of programs to be executed
• Associated with these programs set of data locations for variables and constants (thus, a process will consist of at least sufficient memory to hold the programs and data of that process)
• Associated with programs stacks used to keep track of procedure calls and parameter passing between procedures
• Finally, each process has associated with it a number of attributes that are used by the OS for process control

The collection of program, data, stack, and attributes associated with a process is referred as the process image. The collection of attributes is referred to as a process control block.

Numeric identifiers that may be stored with the process control block include:

• Identifier of the process: each process is assigned a unique numeric identifier, which may simply be an index into the primary process table.
• Identifier of the process that created this process (parent process)
• User identifier indicates the user responsible for the job

Processor State information consists of the contents of:

• Processor registers: while a process is running, of course, the information is in the registers. When a process is interrupted, all of this register information must be saved so that it can be restored when the process resumes execution.
• Stack pointers

Process Control Information

Process Control Information is the additional information needed by the OS to control and coordinate the various active processes.

• Scheduling and State Information: is the information that is needed by the OS to perform its scheduling function. Typical items of information are:

  • Process state: Defines the readiness of the process to be scheduled for execution (e.g., running, ready, waiting, halted).
  • Priority: One or more fields may be used to describe the scheduling priority of the process.
  • Scheduling-related information: This will depend on the scheduling algorithm used. Examples are the amount of time that the process has been waiting and the amount of time that the process executed the last time it was running.
  • Event: Identity of event the process is awaiting before it can be resumed

• Interprocess Communication: various flags, signals, and messages may be associated with communication between two independent processes.

• Memory Management: this section may include pointers to segment and/or page tables that describe the virtual memory assigned to the process.

• Resource Ownership Resources, such as opened files, controlled by the process may be indicated.

• Process Privileges Processes are granted privileges in for the memory that may be used or for the use of system utilities and services.