Otázky a cvičení z Tůmových materiálů

Předmět poskytuje informace o architektuře operačních systémů a funkcích správy procesů, správy paměti, ovladačů periferií, systémů souborů, sítí, bezpečnosti. Všechny funkce jsou ilustrovány na současných operačních systémech, implementace vybraných funkcí je procvičována tvorbou výukového operačního systému.
Uživatelský avatar
CiTrus
Matfyz(ák|ačka) level I
Příspěvky: 19
Registrován: 22. 6. 2014 14:05
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Otázky a cvičení z Tůmových materiálů

Příspěvek od CiTrus »

Ahoj,
při přípravě na zkoušku z Operačních systémů jsem v Tůmových materiálech (viz http://d3s.mff.cuni.cz/~ceres/sch/osy/text/index.html) objevil celkem užitečné otázky / cvičení. Nejedná se o oficiální zkouškové otázky, ale určitě někomu pomůžou s procvičením látky. Zde je dávám seskupené podle témat.

Processes

Explain what is a process.

Explain how the operating system or the first application process gets started when a computer is switched on.

Explain what it means to relocate a program and when and how a program is relocated.

Explain what information is needed to relocate a program and where it is kept.

Explain what it means to link a program and when and how a program is linked.

Explain what information is needed to link a program and where it is kept.

Explain what the interface between processes and the operating system looks like, both for the case when the operating system code resides in the user space and for the case when the operating system code resides in the kernel space.

Propose an interface through which a process can start another process and wait for termination of another process.

Scheduler

Explain how multiple processes can run concurrently on a single processor hardware.

Explain what is a thread and what is the relationship between threads and processes.

Explain what happens when the thread context is switched.

Explain what happens when the process context is switched.

Using a step by step description of a context switch, show how an implementation of threads in the user space and an implementation of threads in the kernel space differ in the way the context is switched.

Na popisu přepnutí kontextu krok po kroku ukažte, jak se implementace vláken v uživatelském prostoru a implementace vláken v prostoru jádra liší ve způsobu přepínání kontextu.

Explain how the requirements of interactive and batch processes on the process scheduling can contradict each other.

List the typical requirements of an interactive process on the process scheduling.

List the typical requirements of a batch process on the process scheduling.

List the typical requirements of a realtime process on the process scheduling.

Explain the difference between soft and hard realtime scheduling requirements.

Define typical phases of a process lifecycle and draw a transition diagram explaining when and how a process passes from one phase to another.

Explain cooperative context switching and its advantages.

Explain preemptive context switching and its advantages.

Explain the round robin scheduling algorithm by outlining the code of a function GetProcessToRun that will return a process to be scheduled and a time after which another process should be scheduled.

Explain the simple priority scheduling algorithm with static priorities by outlining the code of a function GetProcessToRun that will return a process to be scheduled and a time after which another process should be scheduled.

Explain the simple priority scheduling algorithm with dynamically adjusted priorities by outlining the code of a function GetProcessToRun that will return a process to be scheduled and a time after which another process should be scheduled.

Explain the earliest deadline first scheduling algorithm by outlining the code of a function GetProcessToRun that will return a process to be scheduled and a time after which another process should be scheduled.

Explain the function of the Solaris process scheduler by describing how the algorithm decides what process to run and for how long.

Explain the function of the Linux process scheduler by describing how the algorithm decides what process to run and for how long.

Explain the function of the Windows process scheduler by describing how the algorithm decides what process to run and for how long.

Define processor affinity and explain how a scheduler observes it.

Propose an interface through which a thread can start another thread and wait for termination of another thread, including passing the initial arguments and the termination result of the thread.

Design a process scheduler that would support coexistence of batch, realtime and interactive processes. Describe how the processess communicate their scheduling requirements to the scheduler and what data structures the scheduler keeps. Describe the algorithm that uses these requirements and data structures to decide what process to run and for how long and analyze the time complexity of the algorithm.

Process Communication

Propose an interface through which a process can set up a shared memory block with another process.

Define synchronous and asynchronous message passing.

Define blocking and non blocking message sending and reception.

Explain how polling can be used to achieve non blocking message reception.

Explain how callbacks can be used to achieve non blocking message reception.

Explain when a synchronous message sending blocks the sender.

Explain when an asynchronous message sending blocks the sender.

Propose a blocking interface through which a process can send a message to another process. Use synchronous message passing with direct addressing.

Propose a blocking interface through which a process can send a message to another process. Use asynchronous message passing with indirect addressing.

Design a process communication mechanism based on message passing suitable for a microkernel operating system. Describe the interface used by a process to communicate with other processes. Include specialized support for very short messages that would be communicated as quickly as possible, and specialized support for very long messages that would be communicated as efficiently as possible. Compare the overhead introduced by the process communication mechanism with the overhead of a local procedure call.

Process Synchronization

Explain what is a race condition.

Explain what is a critical section.

Explain the conditions under which a simple

Kód: Vybrat vše

I++
code fragment on an integer variable can lead to a race condition when executed by multiple threads.

Explain the conditions under which omitting the

Kód: Vybrat vše

volatile
declaration on an integer variable can lead to a race condition when the variable is accessed by multiple threads.

Describe the Mutual Exclusion synchronization task. Draw a Petri net illustrating the synchronization task and present an example of the task in a parallel application.

Describe the Rendez Vous synchronization task. Draw a Petri net illustrating the synchronization task and present an example of the task in a parallel application.

Describe the Producer And Consumer synchronization task. Draw a Petri net illustrating the synchronization task and present an example of the task in a parallel application.

Describe the Readers And Writers synchronization task. Draw a Petri net illustrating the synchronization task and present an example of the task in a parallel application.

Describe the Dining Philosophers synchronization task. Draw a Petri net illustrating the synchronization task and present an example of the task in a parallel application.

Explain how a deadlock can occur in the Dining Philosophers synchronization task. Propose a modification of the synchronization task that will remove the possibility of the deadlock.

Explain the difference between active and passive waiting. Describe when active waiting and when passive waiting is more suitable.

Present a trivial solution to the mutual exclusion problem without considering liveness and fairness. Use active waiting over a shared variable. Explain the requirements that your solution has on the operations that access the shared variable.

Present a solution to the mutual exclusion problem of two processes including liveness and fairness. Use active waiting over a shared variable. Explain the requirements that your solution has on the operations that access the shared variable.

Describe the priority inversion problem.

Explain how priority inheritance can solve the priority inversion problem for simple synchronization primitives.

Present a formal definition of a deadlock.

Present a formal definition of starvation.

Present a formal definition of a wait free algorithm.

Describe the interface of a lock and the sematics of its methods.

Describe the interface of a read-write lock and the sematics of its methods.

Explain when a lock is a spin lock.

Explain when a lock is a recursive lock.

Explain why Windows offer Mutex and CriticalSection as two implementations of a lock.

Implement a solution for the mutual exclusion synchronization problem using locks.

Describe the interface of a semaphore and the sematics of its methods.

Implement a solution for the producer and consumer synchronization problem over a cyclic buffer using semaphores.

Describe the interface of a condition variable and the sematics of its methods.

Explain what is a monitor as a synchronization tool and what methods it provides.

Implement a spin lock and then a recursive lock using the spin lock and the Sleep and Wake functions, as well as suitable functions of your choice for managing lists and other details, all without any guarantees as to parallelism. Explain how this implementation works on a multiprocessor hardware.

Page Management

Internal fragmentation leads to poor utilization of memory that is marked as used by the operating system. Explain how internal fragmentation occurs and how it can be dealt with.

External fragmentation leads to poor utilization of memory that is marked as free by the operating system. Explain how external fragmentation occurs and how it can be dealt with.

Explain how memory virtualization through paging works and what kind of hardware and operating system support it requires.

At the level of individual address bits and entry flags, describe the process of obtaining physical address from virtual address on a processor that only has the Translation Lookaside Buffer. Explain the role of the operating system in this process.

Hint

Do not concentrate on the addresses alone. The address translation process also reads and writes some flags in the entries of the Translation Lookaside Buffer.

A thorough answer should also explain the relationship between the widths of the address fields and the sizes of the address translation structures.


At the level of individual address bits and entry flags, describe the process of obtaining physical address from virtual address on a processor that supports multilevel page tables. Explain the role of an operating system in this process.

Hint

Do not concentrate on the addresses alone. The address translation process also reads and writes some flags in the entries of the multilevel page tables.

A thorough answer should also explain the relationship between the widths of the address fields and the sizes of the address translation structures.

Explain the relation between the page size and the size of the information describing the mapping of virtual addresses to physical memory and list the advantages and disadvantages associated with using smaller and larger page sizes.

List the advantages and disadvantages of using multilevel page table as a data structure for storing the mapping of virtual to physical memory.

List the advantages and disadvantages of inverse page table as a data structure for storing the mapping of virtual to physical memory.

Explain what a Translation Lookaside Buffer is used for.

Describe the hardware realization of a Translation Lookaside Buffer and explain the principle and advantages of limited associativity.

How does the switching of process context influence the contents of the Translation Lookaside Buffer ? Describe ways to minimize the influence.

Provide at least two criteria that can be used to evaluate the performance of a page replacement algorithm.

Explain the principle of the First In First Out page replacement algorithm and evaluate the feasibility of its implementation on contemporary hardware along with its advantages and disadvantages.

Explain the principle of the Not Recently Used page replacement algorithm and evaluate the feasibility of its implementation on contemporary hardware along with its advantages and disadvantages.

Explain the principle of the Least Recently Used page replacement algorithm and evaluate the feasibility of its implementation on contemporary hardware along with its advantages and disadvantages.

Explain the principle of the Least Frequently Used page replacement algorithm and evaluate the feasibility of its implementation on contemporary hardware along with its advantages and disadvantages.

Explain what is a working set of a process.

Explain what is a locality of reference and how it can be exploited to design or enhance a page replacement algorithm.

Explain what is thrashing and what causes it. Describe what can the operating system do to prevent thrashing and how can the system detect it.

Explain the concept of memory mapped files.

Explain the priciple of the copy-on-write mechanism and provide an example of its application in an operating system.

Consider a system using 32 bit virtual and 32 bit physical addresses. Choose and describe a way the processor in this system should translate virtual addresses to physical. Choose a page size and explain what kind of operation is the page size well suited for.

Design a data structure for mapping virtual addresses to physical and describe in detail all the records used in the structure. When designing the data structure, take into account the choice of the address translation mechanism and explain why is the resulting data structure well suited for the system.

Describe the involvement of the operating system in the process of translating a virtual address to physical (if any), and provide a sketch of the algorithms for handling a page fault and selecting a page for eviction.

Hint

Among other things, approaches to address translation differ in the range of exceptions that the operating system must handle. These might include access protection exception, address translation exception, page fault exception. Does your description of the operating system involvement cover all the exceptions applicable in the chosen approach to address translation ?


Besides the addresses, the data structure for address mapping typically contains many other fields that control access protection or help page replacement. Is your description of the data structure detailed enough to include these fields ?

Consider the previous example except the system is using 32 bit virtual and 36 bit physical addresses.

Consider the previous example except the system is using 54 bit virtual and 44 bit physical addresses.

Allocators

Identify where the following function relies on the virtual address space to store executable code, static data, heap and stack.

Kód: Vybrat vše

void *SafeAlloc (size_t iSize)
{
  void *pResult = malloc (iSize);
  if (pResult == NULL)
  {
    printf ("Failed to allocate %z bytes.
", iSize);
    exit (ENOMEM);
  }
  return (pResult);
}
List four distinct types of content that reside in a virtual address space of a typical process .

Explain the advantages of segmentation over flat virtual memory address space.

Explain why random placement of allocated blocks in the virtual address space of a process can contribute to improved security.

Explain what the processor stack is used for with typical compiled procedural programming languages.

For a contemporary processor, explain how the same machine instructions with the same arguments can access local variables and arguments of a procedure regardless of their absolute address in the virtual address space. Explain why this is important.

Explain what is the function of a heap allocator.

Explain why the implementation of the heap allocator for user processes usually resides in user space rather than kernel space.

Design an interface of a heap allocator.

Explain the problems a heap allocator implementation must solve on multiprocessor hardware and sketch appropriate solutions.

Explain the rationale behind the Buddy Allocator and describe the function of the allocation algorithm.

Explain the rationale behind the Slab Allocator and describe the function of the allocation algorithm.

Describe what a heap allocator can do to reduce the overhead of the virtual memory manager.

Explain the function of a garbage collector.

Define precisely the conditions under which a memory block can be freed by a reference tracing garbage collector.

Describe the algorithm of a copying garbage collector.

Describe the algorithm of a mark and sweep garbage collector.

Describe the algorithm of a generational garbage collector. Assume knowledge of a basic copying garbage collector and a basic mark and sweep garbage collector.

Hint

Essential to the generational garbage collector is the ability to collect only part of the heap. How is this possible without the collector missing some references ?


Device Drivers

Popište obecnou architekturu ovladače zařízení a vysvětlete, jak tato architektura dovoluje zpracovávat současně asynchronní požadavky od hardware a synchronní požadavky od software.

Popište obvyklý průběh obsluhy přerušení jako asynchronního požadavku na obsluhu hardware ovladačem zařízení. Průběh popište od okamžiku přerušení do okamžiku ukončení obsluhy. Předpokládejte obvyklou architekturu ovladače, kde spolu asynchronně a synchronně volané části ovladače komunikují přes sdílenou frontu požadavků. Každý krok popište tak, aby bylo zřejmé, kdo jsou jeho účastníci a kde získají informace potřebné pro vykonání daného kroku.

Popište obvyklý průběh systémového volání jako synchronního požadavku na obsluhu software ovladačem zařízení. Předpokládejte obvyklou architekturu ovladače, kde spolu asynchronně a synchronně volané části ovladače komunikují přes sdílenou frontu požadavků. Průběh popište od okamžiku volání do okamžiku ukončení obsluhy. Každý krok popište tak, aby bylo zřejmé, kdo jsou jeho účastníci a kde získají informace potřebné pro vykonání daného kroku.

Devices

List the features that a hardware device that represent a bus typically provides.

List the features that a hardware clock device typically provides.

List the features that a hardware keyboard device typically provides.

List the features that a hardware mouse device typically provides.

List the features that a hardware terminal device with command interface typically provides.

List the features that a hardware terminal device with memory mapped interface typically provides.

List the features that a hardware disk device typically provides.

Explain the properties that a hardware disk interface must have to support hardware ordering of disk access requests.

Describe at least three strategies for ordering disk access requests. Evaluate how the strategies optimize the total time to execute the requests.

Explain the role of a disk partition table.

List the features that a network interface hardware device typically provides.

Navrhněte rozhraní mezi ovladačem disku nabízejícím funkce pro čtení a zápis bloku sektorů, schopné zpracovávat více požadavků současně, a vyššími vrstvami operačního systému. Pro vámi navržené rozhraní popište architekturu ovladače disku, která je schopna obsluhovat přerušení a volání z vyšších vrstev operačního systému, včetně algoritmu ošetření přerušení a algoritmů funkcí pro čtení a zápis bloku sektorů.

File IO

Popište obvyklé rozhraní operačního systému pro přístup k souborům pomocí operací čtení a zápisu. Funkce rozhraní uveďte včetně argumentů a sémantiky.

Vysvětlete, proč obvyklé rozhraní operačního systému pro přístup k souborům pomocí operací čtení a zápisu odděluje operace otevření a zavření souboru a operaci nastavení aktuální pozice v souboru od vlastních operací čtení a zápisu.

Popište obvyklé rozhraní operačního systému pro přístup k souborům pomocí operací mapování do paměti. Funkce rozhraní uveďte včetně argumentů a sémantiky.

Popište obvyklé rozhraní operačního systému pro práci s adresáři. Funkce rozhraní uveďte včetně argumentů a sémantiky.

Popište obvyklé rozhraní operačního systému pro zamykání souborů. Funkce rozhraní uveďte včetně argumentů a sémantiky.

Vysvětlete rozdíl mezi advisory a mandatory zámky pro zamykání souborů. Vysvětlete, proč tyto druhy zámků existují.

File Systems

Vysvětlete hlediska ovlivňující volbu velikosti bloků jako alokačních jednotek na disku.

Uveďte, jakými způsoby lze na disku ukládat informaci o blocích, ve kterých jsou umístěna data souborů. Jednotlivé způsoby ilustrujte na existujících systémech souborů a zhodnoťte.

Uveďte, jakými způsoby lze na disku ukládat strukturu adresářů. Jednotlivé způsoby ilustrujte na existujících systémech souborů a zhodnoťte.

Vysvětlete rozdíl mezi hard linkem a symbolic linkem. Porovnejte výhody a nevýhody obou typů linků.

Uveďte, jakými způsoby lze na disku ukládat informaci o volných blocích. Jednotlivé způsoby ilustrujte na existujících systémech souborů a zhodnoťte.

Popište způsob uložení informace o umístění dat souborů v systému souborů FAT. Uveďte přednosti a nedostatky tohoto způsobu uložení informace.

Popište způsob uložení informace o struktuře adresářů v systému souborů FAT. Uveďte přednosti a nedostatky tohoto způsobu uložení informace.

Popište způsob uložení informace o umístění volných bloků v systému souborů FAT. Uveďte přednosti a nedostatky tohoto způsobu uložení informace.

Popište způsob uložení informace o umístění dat souborů v systému souborů EXT2. Uveďte přednosti a nedostatky tohoto způsobu uložení informace.

Popište způsob uložení informace o struktuře adresářů v systému souborů EXT2. Uveďte přednosti a nedostatky tohoto způsobu uložení informace.

Popište způsob uložení informace o umístění volných bloků v systému souborů EXT2. Uveďte přednosti a nedostatky tohoto způsobu uložení informace.

Popište způsob uložení informace o umístění dat souborů v systému souborů NTFS. Uveďte přednosti a nedostatky tohoto způsobu uložení informace.

Popište způsob uložení informace o struktuře adresářů v systému souborů NTFS. Uveďte přednosti a nedostatky tohoto způsobu uložení informace.

Popište způsob uložení informace o umístění dat souborů v systému souborů na CD. Uveďte přednosti a nedostatky tohoto způsobu uložení informace.

Popište způsob uložení informace o struktuře adresářů v systému souborů na CD. Uveďte přednosti a nedostatky tohoto způsobu uložení informace.

Vysvětlete princip integrace více systémů souborů v operačním systému do jednoho prostoru jmen.

Popište strukturu systému souborů FAT na disku. Ilustrujte použití této struktury v operacích čtení dat ze souboru při zadané cestě a jménu souboru a pozici a délce dat v souboru a zápisu dat do nově vytvořeného souboru při zadané cestě a jménu souboru a délce dat. Uveďte přednosti a nedostatky tohoto systému souborů.

Popište strukturu systému souborů EXT2 na disku. Ilustrujte použití této struktury v operacích čtení dat ze souboru při zadané cestě a jménu souboru a pozici a délce dat v souboru a zápisu dat do nově vytvořeného souboru při zadané cestě a jménu souboru a délce dat. Uveďte přednosti a nedostatky tohoto systému souborů.

Navrhněte systém souborů, který je schopen efektivně podporovat neomezeně dlouhá jména souborů a linky. Popište strukturu dat ukládaných na disk a algoritmy přečtení a zapsání dat z a do souboru daného jménem včetně cesty a pozicí v rámci souboru. Vysvětlete přednosti vašeho návrhu.

Navrhněte systém souborů, který je schopen efektivně podporovat velmi krátké i velmi dlouhé soubory. Popište strukturu dat ukládaných na disk a algoritmy přečtení a zapsání dat z a do souboru daného jménem včetně cesty a pozicí v rámci souboru. Vysvětlete přednosti vašeho návrhu.

Networks

Popište socket jako abstrakci rozhraní operačního systému pro přístup k síti podle Berkeley sockets. Uveďte základní funkce tohoto rozhraní včetně hlavních argumentů a sémantiky.

Vysvětlete účel funkce select v rozhraní operačního systému pro přístup k síti podle Berkeley sockets.

Vysvětlete, k čemu slouží sockety v doméně PF_UNIX .

Vysvětlete, k čemu slouží sockety v doméně PF_NETLINK .

Popište princip funkce mechanismu vzdáleného volání procedur a načrtněte obvyklou architekturu jeho implementace.

Network Internals

Vysvětlete, proč při implementaci přístupu k síti v operačním systému může kopírování přenášených dat být problém. Zhodnoťte míru tohoto problému a uveďte, jakým způsobem jej lze odstranit.

Vysvětlete roli filtrování paketů v operačním systému. Uveďte příklady kritérií, podle kterých mohou být pakety filtrovány a příklady akcí, které mohou filtry s pakety vykonávat.

Vysvětlete roli plánovače paketů v operačním systému.

Popište Token Bucket algoritmus pro plánování paketů a vysvětlete, co je jeho cílem.

Popište Stochastic Fair Queuing algoritmus pro plánování paketů a vysvětlete, co je jeho cílem.

Popište Class Based Queuing algoritmus pro plánování paketů a vysvětlete, co je jeho cílem.

Popište Random Early Detection algoritmus pro plánování paketů a vysvětlete, co je jeho cílem.

Network File Systems

Popište architekturu síťového systému souborů NFS včetně používaných protokolů a hlavních operací těchto protokolů.

Vysvětlete, co to je a jaké položky zpravidla obsahuje file handle v síťovém systému souborů NFS.

Vysvětlete, jaké problémy přináší bezstavovost NFS při testování přístupových práv a jak jsou tyto problémy řešeny.

Vysvětlete, jaké problémy přináší bezstavovost NFS při mazání otevřených souborů a jak jsou tyto problémy řešeny.

Vysvětlete, jaké problémy přináší bezstavovost NFS při zamykání souborů a jak jsou tyto problémy řešeny.

Security

Vysvětlete termín authentication .

Access Control

Vysvětlete termín authorization .

Vysvětlete, co to je access control list .

Vysvětlete, co to je capability .
Odpovědět

Zpět na „SWI004 Operační systémy“