Экзаменационный билет № 29
1. Scheduling:Multilevel Feedback Queues (MLFQ)
The Multilevel feedback queue scheduling algorithm is what is used in Linux and Unix systems. The MLFQ algorithm tries to pick jobs to run based on their observed behavior. It does this by analyzing whether a job runs for its full time slice or if it relinquishes the CPU early to do I/O. This allows the scheduler to determine if a job is I/O bound or CPU bound so that they can be treated differently.
Advantage: Adaptive behavior can distinguish between CPU and I/O bound tasks and schedule them
Disadvantage: More complicated. Uses past behavior to predict future.
2. Paging: a TLB and demand paging. How is one used?
IMPLEMENTATION OF DEMAND PAGING
A copy of the entire program must be stored on disk. (Why?)
Valid bit in page table indicates if page is in memory.
1: in memory 0: not in memory (either on disk or bogus address). If the page is not in memory, trap to the OS on first the reference
The OS checks that the address is valid. If so, it
1. selects a page to replace (page replacement algorithm)
2. invalidates the old page in the page table
3. starts loading new page into memory from disk
4. context switches to another process while I/O is being done
5. gets interrupt that page is loaded in memory
6. updates the page table entry
7. continues faulting process
In some implementations, the hardware loads the TLB on a TLB miss.
If the TLB hit rate is very high, use software to load the TLB
1. Valid bit in the TLB indicates if page is in memory.
2. on a TLB hit, use the frame number to access memory
3. trap on a TLB miss, the OS then:
a) checks if the page is in memory
b) if page is in memory, OS picks a TLB entry to replace and then fills it in the new entry
c) if page is not in memory, OS picks a TLB entry to replace and fills it in as follows:
v invalidates TLB entry
v perform page fault operations as described earlier
v updates TLB entry
v restarts faulting process
All of this is still functionally transparent to the user.
File Organization: On-Disk Data Structures
The structure used to describe where the file is on the disk and
the attributes of the file is the file descriptor (FileDesc). File
descriptors have to be stored on disks just like files.
• Most systems fit the following profile:
1. Most files are small.
2. Most disk space is taken up by large files.
3. I/O operations target both small and large files.
=> The per-file cost must be low, but large files must also have
good performance.
Экзаменационный билет № 30
1. Планирование и диспетчеризация процесс Scheduling: Lottery Scheduling
Lottery Scheduling!
• Give every job some number of lottery tickets.
• On each time slice, randomly pick a winning ticket.
• On average, CPU time is proportional to the number of tickets
given to each job.
• Assign tickets by giving the most to short running jobs, and fewer
to long running jobs (approximating SJF). To avoid starvation,
every job gets at least one ticket.
• Degrades gracefully as load changes. Adding or deleting a job
affects all jobs proportionately, independent of the number of
tickets a job has.
2. OS LINUX:History and Structure
History of Linux
Free operating system based on UNIX standards
• UNIX is a proprietary OS developed in the 60’s, still used for mainframes
• First version of Linux was developed in 1991 by Linus Torvalds
• Goal was to provide basic functionality of UNIX in a free system
• Version 0.01 (May 1991): no networking, ran only on 80386-compatible Intel
processors and on PC hardware, had extremely limited device-drive support,
and supported only the Minix file system
• Version 2.6.34 (Summer 2010): most common OS for servers, supports
dozens of file systems, runs on anything from cell phones to super computers
Linux structure
Linux separates user and kernel mode to provide protection and abstraction
Kernel modules - extensions to the kernel that can be dynamically loaded or
unloaded as needed: device drivers, file systems, network protocol, etc
3. Contiguous Allocation. Linked files. (Advantages, Disadvantages)
Keep a list of all the free sectors/blocks.
• In the file descriptor, keep a pointer to the first sector/block.
• In each sector, keep a pointer to the next sector.
With linked allocation, each directory entry has a pointer to the first disk block of the file. This pointer is initialized to nil (the end-of-list pointer value) to signify an empty file. A write to a file removes the first free block and writes to that block. This new block is then linked to the end of the file. To read a file, the pointers are just followed from block to block.
Disadvantages
Used only for sequential access of files.
-Direct access is not supported
-Memory space required for the pointers.
- Reliability is compromised if the pointers are lost or damaged
A dvantages
-Fragmentation
– File size changes
– Efficiently supports types of access
Экзаменационный билет № 31
1. Synchronization for Readers/Writers Problem
An object is shared among may threads, each belonging to one of
two classes:
– Readers: read data, never modify it
– Writers: read data and modify it
• Using a single lock on the data object is overly restrictive
=> Want many readers reading the object at once
– Allow only one writer at any point
– How do we control access to the object to permit this protocol?
• Correctness criteria:
– Each read or write of the shared data must happen within a critical section.
– Guarantee mutual exclusion for writers.
– Allow multiple readers to execute in the critical section at once.
2. OS WINDOWS: History and Structure
The history of Windows operating system began on November 10, 1983. This is when Microsoft announced Microsoft Windows, which was an extension of the MS DOS operating system. In the beginning, MS Windows was a mere extension of MS DOS, with DOS serving as the operating system. However, as the product grew in popularity, Microsoft made windows the operating system. By 1995, with the
introduction of Windows 95, windows could be found on the majority of home computers. With many versions introduced between 1983 and today, Microsoft has created a system that now acts as the OS for many computers.
Windows NT Structure
NT runs in two modes:
- Kernel mode (Ring 0) - Executive which runs in protected memory mode with full privileges.
- User mode (Ring 3) - Runs with privileges to access its own memory area. User applications and environmental subsystems execute in this mode.
Applications are allocated a virtual 4Gb of memory with 2 for the user and 2 for executive services.
NT is modular in nature allowing it to have cross platform portability due primarily to the HAL module described below. The NT Architecture has 5 layers.
- Application - Runs in user mode.
- Subsystems - Runs in user mode.
- Executive Services - Runs in kernel mode.
- Kernel - Runs in kernel mode.
- HAL - Runs in kernel mode.
3. Indexed files. Multilevel indexed files. (Advantages, Disadvantages)
Indexed files!
• OS keeps an array of block pointers for each file.
• The user or OS must declare the maximum length of the file when
it is created.
• OS allocates an array to hold the pointers to all the blocks when it
creates the file, but allocates the blocks only on demand.
• OS fills in the pointers as it allocates blocks.
Advantages
– Not much wasted space.
– Both sequential and random accesses are easy.
• Disadvantages
– Sets a maximum file size.
– Lots of seeks because data is not contiguous.
• Examples: Nachos
Multilevel indexed files
Each file descriptor contains 14 block pointers.
• First 12 pointers point to data blocks.
• 13 th pointer points to a block of 1024 pointers to 1024 more data blocks. (One
indirection)
• 14 th pointer points to a block of pointers to indirect blocks. (Two indirections)
Advantages
– Simple to implement
– Supports incremental file growth
– Small files?
• Disadvantages
– Indirect access is inefficient for random access to very large files.
– Lots of seeks because data is not contiguous
Экзаменационный билет № 32
1. Secondary Storage Management: Typical Disk Parameters and Disk Head Scheduling
DISK HEAD SCHEDULING
Idea: Permute the order of disk requests from the order that they arrive from the users to an order that reduces the length and number of seeks.
1. First-come, first-served (FCFS)
2. Shortest seek time first (SSTF)
3. SCAN algorithm (0 to 100, 100 to 0, 0 to 100,...). If there is no request between current position and the extreme (0 or N), we don't have to seek there.
4. C-SCAN circular scan algorithm (0 to 100, 0 to 100,...)
SCAN Disk Head Scheduling
SCAN: head moves back and forth across the disk (0 to 100, 100 to 0, 0 to 100,...), servicing requests as it passes them
– Order of seeks, assuming the head is currently moving to lower numbered blocks: 18, 40, 65, 78
– Distance of seeks: 12 + 22 + 25 + 13 = 72
– Requires a sorted list of requests.
– Simple optimization does not go all the way to the edge of the disk each time, but just as far as the last request.
.
2. OS LINUX: Policy Dependent & Security
1 Open Source vs дизассемблер
2 Удаленный доступ
3 Комплектность штатной поставки
4 Механизмы аутентификации
5 Повышение своих привилегий
6 Угроза переполнения буфера
7 Доступ к чужому адресному пространству
8 Межпроцессорные коммуникации
| характеристика | NT | UNIX |
| качество и полнота документирования | документирована поверхностно | документирована весьма обстоятельно |
| доступность исходных текстов | исходные тексты недоступны | исходные Тексты доступны |
Выявление вторжений
} СКАНИРОВАНИЕ
◦ короткие или легкие пароли;
◦ неавторизованные set-uid программы;
◦ неавторизованные программы в системных директориях;
◦ долго выполняющиеся программы;
◦ нелогичная защита как пользовательских, так и системных директорий и файлов;
◦ потенциально опасные списки поиска файлов;
◦ изменения в системных программах.
АУДИТ и МОНИТОРИНГ
◦ вход или выход из системы;
◦ операции с файлами (открыть, закрыть, переименовать, удалить);
◦ обращение к удаленной системе;
◦ смена привилегий или иных атрибутов безопасности.
3. CPU Scheduling: an I/O bound process and a CPU bound process. Is there any reason to treat them differently for scheduling purposes